Messages in this thread | | | Date | Mon, 17 May 1999 22:40:46 -0400 (EDT) | From | "Theodore Y. Ts'o" <> | Subject | Re: ext2 question |
| |
Date: Mon, 17 May 1999 20:11:23 +0200 From: Manfred Spraul <manfreds@colorfullife.com>
Do you have any plans how to store the extents? * NTFS uses a compressed list of all extents * Hfs (& Hfs+) stores the first 3 (8) extents in the file record, and it has one global BTree for all remaining entries, but that serializes the access to highly fragmented files. (Infact, our Hfs driver for 95 has to load all fragments in advance to avoid deadlocks). * BeFS uses a simple list.
The plan was to use a B-tree, with the root page being stored in the inode. That's enough for the 3 extents, and the block allocation policies already in ext2 are good enough that the *vast* majority of the files will fit in 1 or 2 extents.
If you do locking right with a B-tree, you don't need to serialize access. I've done a lot of thinking about how handle things so that you at most need to have three locks at any particular time in the tree, and most of the time you can release the lock on a node's parent once the lock on the node's child is grabbed. The worst case happens when you are inserting a block in the middle of a file, and you have to split a B-tree node, but even that can be handled if you use preemptive splitting.
Do you think that a linear search is acceptable?
No, because we have to support the worst case, which is an old-style dbm file which has lots of holes and lots of random inserts, causing severe fragmentation of the file.
If you store the list in a completely unsorted fashion, then you have to search through the whole list all the time, even when doing sequential access, which kills your performance. (You can assume that the list is usually sorted if it was written sequentially, but that's not always going to be true.) But if you store it linearly, then when you need to insert items into the middle of the list, and the list is longer than one block, life gets interesting. Using a B-tree trumps these issues.
- Ted
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |