next up previous
Next: Bibliography Up: Fast Indexing: Support for Previous: 9 Future Work


A. Code Sample

In this appendix we include a portion of the FiST code for Uuencodefs and explain the API to writing SCA file systems using FiST.

The full code to Uuencodefs and the other file systems in this paper, as well as additional papers, are available from http://www.cs.columbia.edu/~ezk/research/fist/. A comprehensive discussion of the FiST language is available elsewhere [ZadokZadok2001].

%{
#include "fist.h"
%}
debug on;
filter data;
filter sca;
%%

%%

/* encodes the data in page_data into hidden_pages_data. Returns -errno for
   error, and the size of hidden_pages_data for success */
int
encode_data(char *hidden_pages_data, /* A PAGE_SIZE buffer (already
                                        allocated) passed to us to fill in */
            char *page_data,    /* The data we are to encode */
            int *need_to_call,  /* Call us again? */
            void **opaque)      /* Opaque data (usu. "from") */
            unsigned to,        /* from + no. bytes to write */
            inode_t *inode,     /* The inode in question */
{
    int in_bytes_left;
    int out_bytes_left = PAGE_CACHE_SIZE;
    int startpt;
    unsigned char A, B, C;
    int bytes_written = 0;

    startpt = (int) *opaque;
    in_bytes_left = to - startpt;

    while ((in_bytes_left > 0) && (out_bytes_left >= 4)) {

        A = page_data[startpt];

        switch(in_bytes_left) {
        case 1:
            B = 0;
            C = 0;
            in_bytes_left--;
            startpt += 1;
            break;
        case 2:
            B = page_data[startpt + 1];
            C = 0;
            startpt += 2;
            in_bytes_left -= 2;
            break;
        default:
            B = page_data[startpt + 1];
            C = page_data[startpt + 2];
            startpt += 3;
            in_bytes_left -= 3;
            break;
        }

        hidden_pages_data[bytes_written] = 0x20 + (( A >> 2 ) & 0x3F);
        out_bytes_left--;
        bytes_written++;

        hidden_pages_data[bytes_written] =
          0x20 + ((( A << 4 ) | ((B >> 4) & 0xF)) & 0x3F);
        out_bytes_left--;
        bytes_written++;

        hidden_pages_data[bytes_written] =
          0x20 + ((( B << 2 ) | ((C >> 6) & 0x3)) & 0x3F);
        out_bytes_left--;
        bytes_written++;

        hidden_pages_data[bytes_written] = 0x20 + ((C) & 0x3F);
        out_bytes_left--;
        bytes_written++;

    }

    if (in_bytes_left > 0)
        *opaque = (void *)startpt;
    else
        *need_to_call = 0;

    return bytes_written;
}

The FiST input file begins with a standard C header inclusion and then follows with three declarations:

The bulk of the FiST input file comprises the data-encoding and decoding functions. In the above example we show the data-encoding function only; the data-decoding function is written similarly. A large portion of the data-encoding function is dedicated to the Uuencode algorithm itself--performing bitwise operations such as shifts, AND, and OR operations. The code above shows how easy it is to write a new file system with FiST: the programmer's main task is focused on the specifics of the file system in question, not on the details of operating system, the run-time environment, or usual concerns about implementing each operation of a file system (read, write, mkdir, rmdir, readdir, etc.).

The data-encoding function takes six arguments and returns an integer: the number of output bytes actually produced. This API was designed to afford the maximum flexibility to programmers.

  1. hidden_pages_data: This parameter is the address of an allocated buffer whose size is at most PAGE_SIZE (typically 4KB or 8KB). An encoding function would typically fill this buffer with as much data as it can. The encoding function is not obligated to fill it entirely.

  2. page_data: This parameter is the input data that we have to process (encode). The data-encoding function is not obligated to process all of the input data.

  3. need_to_call: If the data-encoding function did not process all of the input data, it must set this variable to 1.

  4. opaque: If not NULL, this variable determines the start offset within hidden_pages_data where the function must begin writing encoded data. If the encoding function was unable to process all of the input data (perhaps because the output buffer was too small), then it must set this variable to the address where it finished processing input data. FiST will use that information to call the encoding function again at a later time, to process the additional data bytes.

  5. to: This variable is a relative offset within hidden_pages_data where the encoding function must stop writing data. Together, opaque and to form a subrange within the entire data page pointed to by hidden_pages_data where data needs to be written. In this fashion, FiST is able to minimize the number of times it calls encoding and decoding functions, as well as minimize the number of bytes that must be processed each time.

  6. inode: This variable is used when a programmer invokes a FiST function that requires accessing Vnode-specific information, such as the file's owner.

After a developer writes a FiST input file such as the one above, the developer processes it through the FiST code generator, fistgen. Fistgen produces output source files and a Makefile that can be processed by make to build a dynamically-loadable kernel module. The module can then be loaded into a running kernel using system tools such as insmod or modload. Once the module is loaded into the kernel, the new file-system functionality is available and the new file system can be mounted using mount(8).


next up previous
Next: Bibliography Up: Fast Indexing: Support for Previous: 9 Future Work
Erez Zadok 2001-10-06