Re: [RFC] fsblock

On Tue, Jun 26, 2007 at 07:23:09PM +1000, David Chinner wrote:
On Tue, Jun 26, 2007 at 01:55:11PM +1000, Nick Piggin wrote:

[ ... fsblocks vs extent range mapping ]

iomaps can double as range locks simply because iomaps are
expressions of ranges within the file. Seeing as you can only
access a given range exclusively to modify it, inserting an empty
mapping into the tree as a range lock gives an effective method of
allowing safe parallel reads, writes and allocation into the file.

The fsblocks and the vm page cache interface cannot be used to
facilitate this because a radix tree is the wrong type of tree to
store this information in. A sparse, range based tree (e.g. btree)
is the right way to do this and it matches very well with
a range based API.

I'm really not against the extent based page cache idea, but I kind of
assumed it would be too big a change for this kind of generic setup. At
any rate, if we'd like to do it, it may be best to ditch the idea of
"attach mapping information to a page", and switch to "lookup mapping
information and range locking for a page".

A btree could be used to hold the range mapping and locking, but it
could just as easily be a radix tree where you do a gang lookup for the
end of the range (the same way my placeholder patch did). It'll still
find intersecting range locks but is much faster for random
insertion/deletion than the btrees.

-chris
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: [RFC] fsblock
    ... fsblocks vs extent range mapping] ... The fsblocks and the vm page cache interface cannot be used to ... facilitate this because a radix tree is the wrong type of tree to ... but we keep the dirty each buffer part. ...
    (Linux-Kernel)
  • Re: Review of Mueckenheims book.
    ... mapping does or does not exist. ... It is not excluded "a priori" that a model of ZFC might not map '0' to ... Geometry is USED for physics. ... than your tree. ...
    (sci.math)
  • Re: Enumerating all expression trees (not Catalan)
    ... The mapping that would enumerate each tree with unique ... integer would be ideal for my purposes. ... Here is asymptotics: ...
    (sci.math)
  • Re: Two results of set geometry
    ... >>> There is a bijection between the set of all paths representing real ... The mapping you gave is from nodes to paths. ... traversal of the tree still differs by some finite amount from 2/3. ... at which the approximation to 2/3 is closer than epsilon. ...
    (sci.math)
  • Enumerating all expression trees (not Catalan)
    ... The mapping that would enumerate each tree with unique ... corresponds to the tree or expression like this ... time would be wasted wading through the list of mostly useless codes. ...
    (sci.math)