lkml.org 
[lkml]   [1999]   [May]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.307 / U:0.388 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site