[lkml]   [1999]   [May]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: ext2 question
"Theodore Y. Ts'o" wrote:
> We could add this, but it would require locking the directory block so
> that we knew no other process was accessing the directory block when we
> compacted it. It would also significantly impact the implementation of
> the readdir and telldir, and seekdir system calls. So, it would be a
> non-trivial job.

Oops. I should think more before I type: nearly 80% of our
FindFirst()/FindNext() [~readdir()] implementation deals with these

But nevertheless, I have some more ideas:
> 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.
Unfortunately, the '95 specs clearly state that you must _not_ wait
during mmap() sector reads. You're only allowed to wait for the sector
access, and that call must be flaged as 'high priority', 'bypass queue'.

What's the worst case for Linux?
mmap() a sparse file, use the unmapped sector as the input/output buffer
of some kernel function?
use a sparse file as a swap file?

> 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.

Is it realy worth to support extents for such files?
e.g. I though about:
- most files are not sparse files.
- as long as you write sequentially, extents are used, as soon as you
start to jump, then the number of sectors in the extents are stored in
the inode, and the remaining sectors are stored with the old system.

That way, you can optimize further for the non-sparse files.

currently: 15 _u32 for the data blocks:

Use them as follows: (for a new, empty file)
- if sequential write: the first 11 _u32 are used for extents,
a special 'direct blocks are extents'-flag is set in the inode.
- if further sequential writes: 'indirect is extent'-flag set:
2 _u32 are required for the indirect block: the location of the block,
and the number of data sectors described by that block.
- that's it, (~130 extents for 1 kB blocks), the rest is always stored
in the current system.

The access to the extents is fast: the in-memory inode could
precompute the number of blocks stored in extents (add the numbers
from the inode), then only one compare for direct, another for
indirect extents <> the rest are required.

the indirect block:
you don't store 'first sector number of the extent', 'extent len', but
instead 'first sector number of the extent', 'the number
of the corresponding file block'.
Now you can binary search for the extent, and the extents len can be
computed if you need it (should be rare: fsck, grow the file)

> Using a B-tree trumps these issues.
sparse files, (nearly) unlimited number of extents should be implemented
with a btree. But this could penalize the normal files.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

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