diff options
Diffstat (limited to 'src/libs/uio/doc')
-rw-r--r-- | src/libs/uio/doc/basics | 178 | ||||
-rw-r--r-- | src/libs/uio/doc/conventions | 30 | ||||
-rw-r--r-- | src/libs/uio/doc/todo | 144 |
3 files changed, 352 insertions, 0 deletions
diff --git a/src/libs/uio/doc/basics b/src/libs/uio/doc/basics new file mode 100644 index 0000000..e04afd8 --- /dev/null +++ b/src/libs/uio/doc/basics @@ -0,0 +1,178 @@ +-= Introduction =- + +The file io system I present here provides the user with a virtual file +systems on which normal POSIX-like file operations can be performed. + +A virtual file system consists of a number of underlying filesystems merged +together in one directory structure. +Underlying file systems can be POSIX filesystems, or zip archives, but +others can be added easilly. +Filesystems are grafted into the virtual filesystem either explicitely, by +mounting, or implicitely, by having files of a specific type (for instance +those ending on .zip) mounted automatically. +When a filesystem is mounted to a directory which already exists in an +earlier mounted file system, files in the later mounted file system hide +files in an earlier mounted file system. Files present in a filesystem +mounted earlier that don't exist in a filesystem mounted later will remain +visible. +Accessing compressed files inside compressed files is possible, though slow. + + +-= Nomenclature =- +'repository' +A collection of files from various sources as a virtual file system. + +'physical directory structure' +An underlying filesystem, such as a POSIX filesystem, or a .zip archive. + +'logical directory structure' +The merger of one or more Physical directory structures. + +'mounting' +Grafting a physical directory structure in a logical directory system. + +When mounting several dirs on top of eachother, I refer to later mounted +dirs as 'higher' dirs, and earlier mounted dirs as 'lower' dirs. + +'directory entry' +A file or subdirectory within a directory. + + +-= API =- + +Types: +uio_Repository - A struct describing a repository +uio_Handle - A handle for working on files +uio_DirHandle - A handle for working on directories + + +TODO: functions + + +-= Behaviour relating directory structures =- + +The design of the virtual filesystem is guided by the following rules: +- Combined directories contain the entries of each directory. + If some of the source directories contain an entry with the same name, + the combined directory will contain the entry of the topmost directory. + (this means a directory can hide a file and the other way around) +- Entries hidden in this way are never accessable. +- Where possible, actions on directory entries within a combined directory + are done as in a normal file system. +Because of these, some design decisions have been made: +- New entries are created in the topmost writable filesystem. If the path to + the directory where the entry is to be created does not exist, it is + created [1]. +- When a file is to be opened for writing, and the file in the combined + filesystem exists, but is not writable, and there exists a writable + filesystem, mounted higher than the filesystem where the existing file + resides, the file is first copied to the topmost writable filesystem. + +[1] I could have decided to use a pre-existing writable directory if one + is available. + With this choice, when no such pre-existing directory exists, + it would make sense to complete the path in the writable filesystem + in which the part of the path that does exist is the longest. + As you can't create a directory inside a specific filesystem, + this would complicate and confuse things for the user. + + +In specific, for various actions: + +opening a file: +- if O_RDONLY: + - open the file in the highest dir. +- if O_WRONLY or O_RDWR: + - if file already exists: + - if O_CREAT and O_EXCL: return EEXIST + - if file is writable, use that one + - if file is not writable, copy it to the highest writable location + higher than the location of that file (don't bother if O_TRUNC) and use + the new file. If necessary, create the path leading upto it. + If no such location exists, return EACCESS. + - if file does not exist: + - if not O_CREAT: return ENOENT + - if the path to the file does not exists, return ENOENT. + - find the highest writable dir and open the file there, creating + the path leading upto it if necessary. + +removing a file: +- try removing the specified file from all physical directory structures + for a repository. +- once a file is encountered that can't be removed, return an error for + that and don't try the rest. + +creating a directory: +- as for opening a file with O_WRONLY | O_CREAT | O_EXCL + +removing a directory: +- as for removing a file + (but a physical directory not being empty is a reason for failure) + + +-= Limitations =- + +There's no limit to the length of a path in the logical file system. +Paths in the underlying physical filesystem can be limited though. + +At the moment, the system is not thread safe. Only one thread should access +a repository at once. Seperate threads working on seperate repositories is +no problem, as long as the repositories don't overlap. + + +-= Internals =- + +Types: + +uio_MountTree + A node in a data structure describing the mounted directories. + +uio_PRoot + A struct describing the a physical file system. + +uio_PRootExtra + Filesystem-dependant extra data for a PRoot. + +uio_GPRoot + Generic filesystem-dependant data for a PRoot, used as uio_PRootExtra. + +uio_GPRootExtra + Extra filesystem-dependant data for a PRoot, when using uio_GPRoot for + generic filesystem-dependant data. + +uio_GPDir + Generic structure representing a node in a physical directory structure + describing one directory. + +uio_GPFile + Generic structure describing a file in a physical file system. + + +Helper functions (defined in ioaux.c): + +uio_copyFilePhysical + Copy a file from one physical directory to another. + +uio_getPathPhysicalDirs + Get handles to the (existing) physical dirs that are effective in a + path 'path' relative from 'dirHandle' + +uio_getPhysicalAccess + Find PDirHandle and MountInfo structures for reading and writing for a path + from a DirHandle. + +uio_makePath + Create a directory inside a physical directory. All non-existant + parent directories will be created as well. + +uio_resolvePath + Determine the absolute path given a path relative to a given directory. + +uio_verifyPath + Test whether a path is valid and exists. + +uio_walkPhysicalPath + Follow a path starting from a specified physical dir for as long as + possible. + + diff --git a/src/libs/uio/doc/conventions b/src/libs/uio/doc/conventions new file mode 100644 index 0000000..f156101 --- /dev/null +++ b/src/libs/uio/doc/conventions @@ -0,0 +1,30 @@ +This file describes the various conventions used in the source. + + +-= Naming of constructors and destructors =- + +uio_Thing *uio_Thing_new(args) + Allocates the structure, and initialises it from the arguments. + Arguments are always used as-is; if they are reference-counted, + and the caller still needs a reference, it is up to the caller + to increment the reference counter. +void uio_Thing_delete(uio_Thing *thing) + Frees the structure and all sub-structures. + Decrements reference counters to shared structures. +uio_Thing *uio_Thing_alloc() + Allocates memory for a new structure. + Could be omited for standard allocators. + Particularly relevant when a non-standard allocation scheme is + used (for instance, allocation from a pool of pre-allocated strucures). +void uio_Thing_free(Thing *thing) + Frees the memory allocated for thing (reverse of uio_Thing_alloc). + Could be omited for standard deallocators. +void uio_Thing_ref(Thing *thing) + Increments the reference counter to the structure. +void uio_Thing_unref(Thing *thing) + Decrements the reference counter to the structure. + Calls uio_Thing_Delete() if the refcounter becomes 0. + +These functions are always declared and defined in this order. + + diff --git a/src/libs/uio/doc/todo b/src/libs/uio/doc/todo new file mode 100644 index 0000000..b9f232c --- /dev/null +++ b/src/libs/uio/doc/todo @@ -0,0 +1,144 @@ +Needed for use in UQM: +- documentation +- configuring for GLOB +- when doing uio_getStdioPhysical(), if write access is required, but + not available on the original location, also copy the file to the + temporary dir. +- Call fsync() at appropriate times. + +Documentation: +- use doxygen +- Warning: getting (part of) the contents of a directory is fairly slow, + as dirs need to be merged. +- It would be (theoretically) possible to add HTTP and FTP support for + remote file systems. +- on adding extra file system types: + open, mkdir, rmdir, and unlink should themselves make sure that + the physical structure is kept up to date when an entry is + removed or added. +- stream stuff is not thread safe +- uio_fflush() does not accept NULL as argument to flush all streams, + like stdio fflush() does. +- uio_close() does never fail +- The physical open function should call uio_Handle_new and store its own + data in it. + The physical close function should delete its own data. It's called + Will cleanup the general Handle. + Analogous for mount/unmount with PRoot +- No need to store MountHandles. They will be automatically freed + when the repository is closed. +- You can use mount stuff from other repositories. +- ".." works by nullifying one path component, not by following the ".." link + in the directory. "/a/../b" will always be functionally equivalent to + "/b", even when "/a" is a symlink. + +Testing: +- Test mounting an UNC directory + +Bugs: +- 'openDir(repository, "dir/")' will have the trailing '/' + in the dirHandle, which will cause problems. +- 'openDirRelative(repository, "/")' causes segfaults later on +- uio_rename() doesn't work on directories +- uio_getPhysicalAccess() needs to be changed so that it works the same on + dirs as on files. stat() can be cleaned up too then. +- uio_getPhysicalAccess() will not return ENOENT when (only) the last + component does not exist, even when O_RDONLY is used. + For O_RDRW, O_CREAT should probably be checked too (function description + needs to be updated too then). +- A lot of inlining is not possible because of the order of function + definitions. +- sizeof(size_t) may be less than 4 on some platforms. Check what problems + this may cause. At least the size of zip_INPUT_BUFFER_SIZE is an + issue. SIZE_MAX can be used to check for sizeof(size_t) at runtime. +- remove() is probably more compatible than unlink(). remove() is part + of the C standard (as well as POSIX), unlink() is just POSIX. +- seeking in files opened as "text" on Windows goes wrong. +- Network paths on Windows are not accepted. +- No CRLF translation (and ^Z recognition) is done for files read from + zip files, even though that may be expected on Windows. +- The order in which "uio_unmountAllDirs() unmounts the directories, may lead + it to unmount a dir while there still is a file descriptor for another + dir open, causing a warning. + +Extra features (not necessary for UQM): +- Make functions to use for uio_malloc, uio_free and uio_realloc + configurable at init. +- add uio_mmap() +- add match_MATCH_ALL and match_MATCH_NONE +- automounting + - Unmount automounted filesystems when the originating filesystem + is unmounted. +- when doing stat() on a directory, merge the stat info of the underlying + physical dirs. +- read directory information from zip files. +- implement ungetc() +- make fileblocks public +- setmode() for windows? +- prevent aliasing of files/dirs, both between two physical file + systems (where possible), as within the same filesystem (in particular + stdio). On Windows, aliasing can occur easilly when a file or dir + is accessed with the long vs the short ("PROGRA~1") name, or when + capitalisation is involved. +- accept non-dir, non-regular-file dir entries in stdio. +- Add non-merging mounts. Make 'merging' an option for the mount. +- make uio_rename() work cross-fs, or provide a wrapper which does that. + (the system rename() doesn't work cross-fs either, so keeping uio_rename() + as it is makes sense, as I'm trying to stay close to the system functions, + even though hiding file systems from the user would be nicer) +- Add a readdir_r(). Right now, for Symbian readdir_r() is defined in + uioport.h, but the actual implementation is out of the uio tree. + +Optimisations (not necessary for UQM): +- use mmap for fileBlocks +- Use a pre-allocated pool of hash table entries for allocHashEntry. +- optimise certain strings (specifically directory entries) by making + a string type which has pointers to a shared char array. + Invariant: if two strings are the same, they point to the same + character array. Consequence: string comparison is pointer comparison. + Making a new string would imply checking the existing strings. + Existing strings should be in a hash table. +- optimise paths + Encode all paths internally as (double-linked) chains of path components + This way, operations like going up one path component, are cheap. + Each path component could either be represented by a pointer to a string, + (possibly shared as above), or as a pair of begin and end pointers + (or begin pointer and length). In the latter case, there's no need for + copying strings when parsing a user-supplied string, but sharing of strings + would not be possible. + It's probably possible to use both methods next to eachother; + shared strings for stored paths, and pointers into a path for user-supplied + strings (which would be freed when the call returns). + Instead of a linked list, perhaps an array can be used, as paths rarely + change. It would be a problem if for some reason, recursively path + components are added to a path. +- (maybe) keep track of already issued handles, so that the ref counter + could just be incremented, instead of issuing a new one. + (uio_getPDirEntryHandle) +- Make it possible for people to add their own file system, without giving + away the internals. (no wanton including of .h files) +- Don't cache stdio dir structure + (and don't read the dir leading up to the dir that is actually needed) +- mounting foo to /Foo and foo/bar to /Foo/Bar should result in only one + physical structure. Preferably, it shouldn't even lead to two mountInfo + structures for /Foo/Bar, so that merging the dirs is not unnecessarilly + expensive. +- add uio_access() + (uqm fileExists can be redone then) +- implement the physical function cleanup() to clean up the physical + structure. Int argument that specifies how thoroughly. + On it depends whether cache is cleaned, whether stuff is realloc'ed + to defragment memory, etc. + +Cleanups (not necessary for UQM): +- rename function names to be more like class names for as far as that's + not already done. + uio_PRoot_unref etc +- Add uio_fatal(), uio_error(), uio_warning() +- Clean up the include structure +- use stdint.h and stdbool.h types directly, instead of using uio_int16 etc. + Remove types.h, and instead, if these types are missing on some platforms, + put the fixes in port.h. + + + |