[This was posted to reiserfs-dev list today. Please comment.] Hello,
let me summarize our latest talks about key structure in reiser4. LAYOUT: Key is three 64bit integers (24 bytes total) stored on a disk in LE format. First integer is "locality", second---"objectid" and third is "offset". Keys are much larger than in v3, but it's supposed that v4.1 will implement some form of key compression. For bodies of files and attributes offset is real offset from the beginning of a file. For names of files within directory and attributes within file it's hash:counter pair of some sort. Locality is 60 bitsful of "directory-id" (aka "major packing locality") and 4 bitsful of "item-type" (aka "minor packing locality"). Objectid is unique id of a file that fits within 60 bits. (higher 4 bits are zero, but see below). ORDERING: Default ordering of keys in reiser4 will be "Plan-A". It's "point-wise" ordering where key components are compared as integers in the following order: (major, minor, objectid, offset). Because of the layout described above, this ordering can be implemented as three comparisons of 64bit integers in CPU order. OBJECTID: It was agreed that 60bit for objectids is enough to stop reusing them. So we just keep one objectid counter in a super-block and increment it on each file creation, possibly warning user when objectid-space is about to be exhausted. OBJECTID-BANDS [proposal]: As described above key has 4 spare bits. They can be used to store a "band" of object referenced by this key. In this setting objects are referenced by 64bit (band, objectid) pair that can be used as inode number and where lower 60 bits are unique. Bands are used to group objects together and to add finer grained and user-controllable ordering of objects within tree (that is, effectively to prioritize them within parent directory). For example, mount option or ioctl can be implemented such that in given file-system or directory band of object depends on its mode, so that in tree order directories are grouped together and are located before regular files etc. Nikita.
