Hi.
I noticed, that the Superblock structure itself starts at the offset 0x200 inside the cluster 0. The Practical File System Design book states, the Superblock occupies cluster 0. The question is does the SB structure always start at the offset 0x200 or its position inside cluster 0 depends on the cluster size or disk block size? Say, if the disk block size is 4K, would the SB structure be placed at the offset 0x200 or 0x1000?
And yet, Haiku recommends 2048 as the cluster size, when formatting the drive. Again, what it would recommend if the disk block size is 4096?
Thanks.
while waiting for someone, knowing and wanting to reply to the previous questions, I’ve got some more. 
-
In the BFS B+ tree node structure, there is a so called
key length index. The book says it’s placed at the offset after the header, rounded up to be 4 multiple. analyzing the directory index, it turned out, that the aforementioned array is 8 byte aligned. The question is am I correct? -
The book describes the tree type, used in BFS as a B+ tree, but what is depicted in the book and how it’s described in the above mentioned node, doesn’t look as a B+ tree.
Because of one subtle, but important difference. The descriptions (and depictions) show the number of pointers to the child nodes the same as the number of the keys in the node. This is incorrect for any B tree, as the number of pointers is 1 more, than the number of keys. number of pointers equals to number of children, obviously, and is 1 more, than the number of the node keys. It’s for internal (non-leaf) nodes. Leaf nodes, oppositely have the same number of pointers (more precisely - number of value elements) as the number of key elements in the node. that’s because it’s not the same pointers, they point or correspond to data. Internal nodes, on the other hand, cover the key ranges and if the number of pointers (children) were the same as the number of keys, then there would not be possibility to point to the rightmost range, that is, in the case of string keys, - to the child node, containing strings, lexically greater, than the rightmost key in the parent node.
I illustrate this by the modified picture from the book. the red node was added by me. it shows, that were in the book “B+ tree” new directories “wacko” and “yay” about to get added, there wouldn’t be possibility to do so - there wouldn’t be mechanism for this, since every internal node only contains pointers to children, having lesser (lexically) strings. indeed, look at the book example - all the root element keys, have a pointer to the node with all elements, lesser, than the associated parent key. it’s incomplete.
the second pic is the correct B+ tree from wikipedia:
The question is maybe it’s just incorrectness/incompleteness of the book, since the node structure is the same for internal and leaf nodes, maybe in the case of the former, there is yet another pointer at the end of the pointer array, corresponding to the missing range. Because, as said, the book only talks about smaller ranges (children):
For interior nodes the value associated with a key is an offset to the corresponding node that contains elements less than this key.
Recreating this in the field is not easy, because one needs to mess with a hexdump of the index, containing so much elements, that there are levels in the tree. And thus, a related questions arises.
- What is the branching factor of a B+ tree in BFS? it’s the maximum allowed number of direct child nodes? Or the same - it’s the maximum amount of pointers for internal nodes?
PS. I am asking this all, because I want to use BFS as the Boot Volume FS in my osdev hobby project. 
1 Like
It’s probably easiest if you just read the source code to Haiku’s BFS driver to answer your questions. I’m not sure the few developers who are experts in this kind of low-level usage of BFS will have time to reply on the forum here…
surely I’ll do and already have done. just thought here would be a bit faster (in case, there are those who are able to answer).