On Mon, 2 Mar 1998 14:37:34 +0200 (EET), Matti Aarnio
<matti.aarnio@tele.fi> said:
>> doesnt this change the speed of bmap() from O(1) to O(log(N))? With the
>> current scheme we exactly know where to look to get the index, with
>> extents we have to binary-search every table? And, why do we have to store
>> both logical and physical blocks, is there any nontrivial translation
>> between them?
> I have some practical experience with this -- I have code
> that does exactly this...
Great!
> I thought that for a few days at first -- shall I support HOLES ?
> I decided NOT TO DO SO IN THE EXTENT-CODED I-NODES.
Holes are pretty much a non-problem if we code the extent map as a
btree of (offset, extent) entries. Btree coding is already something
we really ought to implement for the directory case, and this would be
just a different type of key; we could reuse most of the btree code
between the two.
The btree approach has the advantage that sparse files of _any_ size
can be coded very efficiently, with no more levels in the indirection
tree than are needed for the number of extents actually used. There
is no tree size dependency on the size of the file offsets as there is
for static indirection trees.
--Stephen
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu