The structure of the Reiser file system
static inline int is_key_format_1 (int type) {
return ( (type == 0 || type == 15) ? 1 : 0);
}
/* old keys (on i386) have k_offset_v2.k_type == 15 (direct and
indirect) or == 0 (dir items and stat data) */
/* */
int key_format (const struct key * key)
{
int type;
type = get_key_type_v2 (key);
if (is_key_format_1 (type))
return KEY_FORMAT_1;
return KEY_FORMAT_2;
}
This actually implies that stat items will always be assumed to have KEY_FORMAT_1, because they, also, have a type of zero in version 2. 
| Name |
Size |
Description |
| Directory ID |
4 |
the identifier of the directory where the object is located |
| Object ID |
4 |
the actual identifier of the object ("inode number") |
| Offset |
4 |
the offset in bytes that this key references |
| Type |
4 |
the type of item. Possible values are:
Stat: 0
Indirect: 0xfffffffe
Direct: 0xffffffff
Directory: 500
Any: 555 |
| Name |
Size |
Description |
| Directory ID |
4 |
the identifier of the directory where the object is located |
| Object ID |
4 |
the actual identifier of the object ("inode number") |
| Offset |
60 bits |
the offset in bytes that this key references |
| Type |
4 bits |
the type of item. Possible values are:
Stat: 0
Indirect: 1
Direct: 2
Directory: 3
Any: 15 |
Only stat items have an offset of 0. Files (direct and indirect items) and directories always start with an offset of 1 so that they are sorted behind the stat item in the leaf nodes. For directory items the "offset" field contains the hash value and generation number of the leftmost directory header of the directory item (see below), not the offset in bytes.
Examples:
The following shows the first two keys of the internal node that is contained in block 8482. The first one is of version 2, the second of version 1. 00000000 02 00 00 00 0e 00 00 00 00 00 00 00 00 00 00 00 ................
Directory id: 2
Object id: 14
Offset: 0
Type: Stat item (0)
00000000 03 00 00 00 04 00 00 00 01 00 00 00 f4 01 00 00 ............ô...
Directory id: 3
Object id: 4
Offset: 1
Type: Directory item (500)
Two keys are compared by comparing their directory ids first, and if those are equal, by comparing the object ids, and so on for offset and type. The fact that the Linux reiserfs code generates a warning when the type fields need to be compared for keys stored in memory indicates that the type field does not matter from a structural point of view. The only time the field needs to be compared seems to be during "tail conversion", where a direct item is changed into an indirect one.
Internal nodes An internal node block consists of the block header, keys, and pointers to child nodes. Other than the figure of the S+-tree above, the internal nodes have all the keys first, which are sorted by the key values. Then following the last key comes the pointers, starting with the pointer to the subtree containing all the keys smaller to the first key.
The level in the block header should always be larger than 1 for internal nodes. The number of items in the block header denotes the number of keys in the node, not the combined number of keys and pointers. There is always one more pointer than there are keys. The following figure describes the layout of the pointer structure:
|
