[Tux3] Development roadmap

Daniel Phillips phillips at phunq.net
Fri Aug 1 17:46:30 PDT 2008

Here is an initial list of development tasks goals, with the more
immediate tasks in higher resolution.  I will be updating this as
things proceed.  First I will just try to list all the code bits
that need writing, organized into initial prototype, then the march
to full feature set.

This is a very rough draft, to be refined as we go.


 - Initially use bitmap code lifted from ddsnap

Generic Btree

 - Generalize ddsnap btree operations to use tables of leaf and index
   node methods

Btree leaf methods

 - 11 leaf methods or so to implement for each of five different kinds
   of btree

 - Btree variants:
    - inode table
    - file index
    - free extents
    - atime table
    - directory

 - Leaf methods:
    - dump
    - check
    - lookup
    - insert
    - split
    - merge
    - delete (group of methods)
    - create
    - destroy
    - freespace
    - payload

 - Save time to prototype by only implementing two btrees, the inode
   table tree and the file index tree, leaving free extent tree, atime
   tree and dir tree till later.

Btree node methods:

 - Initially the same for file index and inode table btrees, save time
   by not abstracting just now


 - bitmap allocation lifted from ddsnap

Pointer versioning at file index leaf

 - This is the central architectural feature of Tux3

 - Assemble file index leaf operations into a "get_block" method to set
   up transfer to/from page cache.

     - Initially we will use the stock kernel block IO library

 - Integrate version delete with file index leaf delete method

Versioned inode attribute groups:

  - ctime/mode/uid/gid
  - size/mtime
  - immediate attribute data
  - direct file blocks
  - file blocks/btree
  - orphan

Version interface

 - create version
 - delete version
 - mount version
 - open versioned file
 - transport mounted filesystem to version


 - Initially use Ext2 directory.  Cut and paste from Ext2 for the dirent
   create and delete.  Linear scan for lookup is trivial.
     - dir operations
       - lookup
       - create
       - rename
       - delete
       - readdir

     - name operations
       - create
       - lookup
       - link
       - unlink
       - symlink
       - mkdir
       - rmdir
       - mknod
       - rename
       - setattr
       - permission

Put it all together
  - buffer.c kernel buffer emulation from ddsnap
  - emulate page cache?
  - at this point can read and write tux3 volume from a C program
  - choose a magic number "TUX3" { 0x54, 0x55, 0x58, 0x33 }

Port to kernel

 - super ops
    - mount argument parsing
    - fill super
 - bio interface
    - intially just the block library page ops + get_block
 - ioctl interface (default?)
 - locking
 - ddlink interface for version control

Shortcuts for first functional prototype:

 - Block pointers instead of extents
 - Bitmap allocation instead of btree
 - Linear Ext2 directory instead of PHTree
 - No extended attributes
 - No immediate file data (but better have symlinks)
 - Coarse btree locking using per-sb mutex
 - Only 255 versions
 - No atomic commit
 - No orphan cleanup
 - No atimes


After the prototype

 * Transaction model (ACID)
 * Versioned extents
 * Fine grained btree locking
 * Quota - bypass VFS quota files?
 * atime versioned btree - just a file?
 * replicate a version
 * fragmentation control
 * online defrag
 * online expand
 * online shrink
 * PHTree
 * More versions
    - leaf version mapping tables
 * endian neutrality

Tux3 mailing list
Tux3 at tux3.org

More information about the Tux3 mailing list