Notes on libferris

Background knowledge on current filesystem designs and interfaces is presented in the section called “Background” which also contains a presentation of the terminology used throughout the paper. This is followed by a formal consideration of filesystems as the data for FCA.

This section describes modern filesystem design and interfaces. Particular attention is paid to libferris and what interfaces and functionality are offered by it.

Traditional filesystems arrange data using two main abstractions; files and directories. Directories can be nested within other directories. Files may be created in any directory. Files are restricted to containing a linear range of octets. Directories can not have octet content but can contain other files and directories. UNIX filesystems have various specilized objects which are presented as files but are implemented differently under the surface. Such specilized file like objects include; links, pipes and device files. Recent operating system design also exposes access to internal kernel data through specilized files such as located in the /proc filesystem in Linux [Linux Proc fileystem]. Note that UNIX systems support files such that the linear range of octet content may contain holes. A hole is an area within the octet range that appears to exist in that it consumes part of the linear range as far as lseek(2) is concerned but the hole consumes a nominal amount of disk storage and contains no data.

libferris [libferris website] is a Virtual Filesystem (VFS) which runs in the user address space rather than the kernel address space of traditional VFS. By moving the VFS into the user address space libferris can use other shared libraries to present data as a filesystem, for example a berkeley db can be mounted as a filesystem or an XML file can be mounted as a filesystem. In fact both db and XML files as seen though ferris appear just like normal directories. libferris does away with the notion that a directory can not have octet content and merges the abstractions file and directory into a single abstraction called a "Context". Context objects in libferris are exposed though smart pointers using intrusive reference counting. The type for a smart pointer to a class in libferris is the classname prefixed by an "fh_". The "file://" context objects maintain a hot view of the filesystem as presented by the kernel in that they modify themself automatically to reflect addtions and deletions made to the filesystem by other processes ^[1]. One can walk the children of a Context using STL style iterators. These iterators will remain valid through insertion and deletion including the deletion of the Context that the iterator currently points to.

Files and directories may have arbitrary key value data attached. Such a scheme is refered to as Extended Attributes (EA) [ACL]. The EA interface of the kernel is extended in libferris by allowing the values attached to the attribute to be either stored seperately as kernel level EA or generated dynamically. Examples of EA that can be generated include the width and height of an image, the bitrate of an mp3 file or the MD5 [MD5 digest] of a file. Access to EA in libferris is achieved with either a quick and dirty string interface or through extented std::iostreams. The string interface uses a function like

with the two last parameters being optional ones to control if all lines of data are obtained and if an exception is raised if the attribute doesn't exist or the default is returned. There is a similar function for setting attributes

Using the iostream interface one first gets a smart pointer to an Attribute using Context::getAttribute() and then calls getIStream() or getIOStream() on the attribute depending on if they intend to update the data or not. Note that once the final reference to an iostream goes out of scope then if the iostream was updated then the attribute will have its value set.

Another way libferris extends the EA interface is by offering schema data for attributes. Such metadata allows for default sorting orders to be set for a datatype, filtering to use the correct comparison operator (integer vs. string comparison), and GUIs to present data in a format which the user will find intuitive.

The standard IOStreams [Standard C++ IOStreams and Locales] system in C++ is extended in libferris to allow stream handles to be passed by value. The underlying streambuffer is not copied during this process. The ability to pass the iostream object by value solves the sticky issue of having a method return data in a newly created iostream. Another extension to the standard allows a streambuf to perform work when the last iostream reference is going out of scope. This can be used by plugins, attributes and methods to return data in an iostream and perform some work on data that the user puts into that iostream once the user is done with it. An iostream can also be monitored by a developers application by attaching to a SigC signal which is fired when the streambuf is about to be reclaimed. This is done by attaching to StreamHandlableSigEmitter::getCloseSig(). Note that all iostream classes are a subclass of StreamHandlableSigEmitter. Attached functors will be called with an iostream and a std::streamsize informing of how much of the iostream was written to.

IOStreams implementors can use the ferris_basic_streambuf and ferris_basic_double_buffered_streambuf classes as superclasses to reuse some of the boilerplate code of iostreams.

If one has an iostream and wishes to create another iostream that exposes only a range of bytes in the original then there is the following function

which pretends the start of iostream is a octet offset into the oringial iostream and the eof is at another octet location.

Transparent compression is implemented for contexts in libferris and a context can be converted to and from compressed state using ConvertToCompressedChunkContext() and ConvertFromCompressedChunkContext(). Note that there are many options as to what blocking sizes to use and what compression algorithmn is used to compress chunks. See the API documentation for ConvertToCompressedChunkContext() for more information.

An interesting iostream can be created with

which monitors the data that is written to it and if ss supports hole creation will replace any blocks of all zero with a hole instead.

There are also functions to obtain ferris iostream versions of cin, cout and cerr called fcin(), fcout() and fcerr() ^[2]. Standard iostreams can be wrapped using MakeProxyStream(). File descriptors can be wrapped using MakeFdIStream( int fd ), MakeFdOStream( int fd ) and MakeFdIOStream( int fd ). Memory regions can be wrapped as an iostream using MakeMemoryIStream( ptr, size ) and MakeMemoryIOStream( ptr, size ). And if the operating system supports it a file descriptor can be used to form a memory mapped iostream using MakeMMapIStream() and MakeMMapIOStream().

libferris provides the ability to create facade filesystems. Such filesystems accept another filesystem as an argument and modify the behaviour of access to the underlying filesystem while they themself present the same interface as the underlying filesystem. This design follows the Decorator pattern in [Design patterns]. Examples include sorting, filtering, set theoretic combinations such as unions and the collection of arbitrary filesystem objects into a single filesystem. Examples of when one may wish to combine multiple filesystem objects to appear as a single filesystem include; passing a selection, copy and paste, or returning a search result set. The filesystem that allows arbitrary collection not only presents a fake filesystem containing a list of its collected objects but also modifies what is reported as the filename of each object to be their URL. Such modification is needed because many applications implicitly expect the filename for all children of a directory to be distinct. It should be noted that many of the facade filesystems are hot in that they will notice what is happening to their underlying filesystem and adjust their contents to reflect file addition and removal in the base.

The two main ways for a filesystem to attach EA depend on how common the attribute is. If a Context subclass knows that an attribute will exist for all its Context objects then it can bind that attribute as "stateless" using the StateLessEAHolder::tryAddStateLessAttribute() method. A large saving in memory overhead can be achieved using stateless attributes because one attribute object can service any number of Context objects. A prime example of stateless attibutes are the "size", "mtime" and "is-fifo" EA that are bound for all NativeContext objects. Attributes can also be bound to a single Context object using one of the addAttribute() methods. An attribute carries atleast three things; the name of the attribute, a getIStream() functor, and the schema for the attribute. Attributes which permit writing also carry a getIOStream() method and a Closed() functor. The Closed() functor has the following signature

The changes that the user has made to a stream between getIOStream() and having the final fh_iostream handle drop out of scope are reflected in the iss stream.

The getIStream() and getIOStream() functons have the following templates

at many times the functors passed to tryAddStateLessAttribute() and addAttribute() for getIStream() and getIOStream() are actually to the same function.

The signatures of the getIStream(), getIOStream() and Closed() functions vary for Stateless attributes. The "Context*" parameter will be declared as a pointer to the derived Context classname. This allows a stateless attribute handler to access the internal methods and data of a derived Context class.

One should consider stateless attributes in the same way as a stateless object in an MTS [Microsoft transaction server] system. This means that the functors themself should not contain state but can access data in the Context object which is passed in as the first parameter. Thus a stateless functor should always perform the same task if the passed in Context has the same state.

Note that stateless attributes of a subclass can be augmented by calling Context::supplementStateLessAttributes() after the subcontext creates its own stateless attributes. Such a call will augment standard binary attributes with more human accessable versions. For example a "size" attribute will have a "size-human-readable" attribute added, a "mtime" attribute will be augmented with "mtime-ctime" and "mtime-display" the ctime version will convert a time_t value to a human readable version using ctime(3), the display version will use a time formating of the users choosing to present the time.

A schema can be bound to native disk EA by writing a new native disk EA with the prefix "schema:". Also for a entire directory a schema may be written for all current and future EA with a given name "ean" by writing to the "subtreeschema:ean" native EA in the parent directory.

/ 
  /tmp
       (NativeContext; is-dir, mtime, size, inode)
       (      Context: name, url, ea-names, size-human-readable)
     /tmp/myfile.xml
        /tmp/myfile.xml/baseitem
            (ferris.xml: author, title)
            (   Context: name, url, ea-names)
     /tmp/myimage.jpg
       (NativeContext; is-dir, mtime, size, inode)
       (      Context: name, url, ea-names, size-human-readable)
       (  ferris.jpeg: width, height, rgba-32bpp)

Access to the full text index that libferris maintains can be achieved either through an API or using a purely filesystem based interface. For example when one reads the URL \url{fulltextquery://ranked/mad hatter} a ranked query is performed on the full text index and a filesystem which contains the matches is displayed. libferris maintains an index of EA values in order to support find queries for arbitrary predicates. The interface to this index is presented both through and API and as a filesystem. For example, reading the URL "eaq://(|(size<=100)(name=\~.*c)" will perform a search though the index for any object in the entire filesystem with a small size or a extension of ".c" and return a filesystem containing all of these objects. Note that the predicate that defines the search has the same format as a ferris-filter string described in filter.

Two distinct methods of creating a formal context are presented; firstly using EA and predicates and then using facade filesystems as the attributes themselves. The main difference is that using predicates will create the attributes from a directory G, using filesystems for M one must derive G as the union of the children in each M.

With the inclusion of EA in the data model one can consider a specific directory d as a multi-valued context (G,M,W,J) with G a set of filesystem objects that reside with d as their immediate parent directory, M a set of EA attribute names, W a set of arbitrary bit strings, and J subseteq G * M * W with (g,m,w) in J indicating that the filesystem object g has an EA m with a bit string value w.

To generate a formal context (G,A,I) from the above multi-valued context (G,M,W,J) one can repeatedly bind predicates to G to create a in A which uses the values in M and W to determine if a object g in G should be associated in I subseteq G * A.

Filesystems themself can form a formal context (G,M,I) by including an implicit plain scale. Consider M={m_1,...,m_n} as a collection of filesystems, G = union forall z in M and I subseteq G * M with (g,m) in I indicating that the filesystem object g appears also in the filesystem m. To create an interesting formal context using the above method the filesystems in M are usually the result of a fulltext query or other filesystem that contains an arbitrary collection of objects from the underlying file system. The use of facade filesystems in M is to allow g in G to appear in I more than once.

Combinations of the above methods can be performed by either

The following is an example of creating a formal context from a collection of filesystems created using full text from project gutenberg [Project gutenburg] which had been added to the default fulltext index and the following commands

ferrisls -lh --show-columns="rank,size-human-readable,url" \
       --ferris-filter="" fulltextquery://ranked/alice
0.460043        149.9k  alice13a.txt

ferrisls -lh --show-columns="rank,size-human-readable,name" \
    --ferris-filter="" fulltextquery://ranked/war
0.0643407       47.8k   boysw10.txt
0.0548522       253.1k  dmoro11.txt
0.18801         109.6k  nobos10.txt
0.135122        355.4k  warw11.txt

ferrisls -lh --show-columns="rank,size-human-readable,name" \
    --ferris-filter="" fulltextquery://ranked/control
0.0378179       253.1k  dmoro11.txt
0.0524795       355.4k  warw11.txt

ferrisls -lh --show-columns="rank,size-human-readable,name" \
    --ferris-filter="" fulltextquery://ranked/tea
0.194187        149.9k  alice13a.txt
0.0762724       109.6k  nobos10.txt
0.0702319       39.7k   snark12.txt
0.048025        355.4k  warw11.txt

These filesystems can be combined using (G,M,I) as defined above to give the formal context

hmm