On Mon, Jan 27, 2014 at 08:10:52PM +0100, Goffredo Baroncelli wrote: > Hi, > > On 2014-01-27 14:28, Gerhard Heift wrote: > > This patch series adds a new ioctl TREE_SEARCH_V2 with which we could store > > the > > results in a varying buffer. Now even items larger than 3992 bytes or a > > large > > amount of items can be returned. > > > One of the main strangeness of the current TREE_SEARCH ioctl, which I > found is the fact that the search was not in a "rectangular" region, but > in a "linear" region.
> This is due the fact that after a ioctl call, we have to set the min_*
> fields with the sh->{objectid,offset,type} +1 rounding to 0 if case of
> overflow.
>
> This because the min_* fields are both the "lower bound" of the search
> and the "starting point" of the next search. Adding a new set of fields
> named start_* could solve this issue.
>
> I discussed this topic few years ago in [1].
>
> Because we are introducing a new ioctl, is it possible to solve this
> issue ? We could avoid some userspace<->kernelspace transition, which
> seems be one of the goal of your patch.
Aargh, not this again. :(
The keyspace is *linear*, consisting of a concatenation of three
data fields, sorted lexically. This is how they're stored in the
trees, and it's how they're returned by TREE_SEARCH. You can't
traverse the keyspace with an O(1) "next" operation in anything other
than that order. Each tree represents a linear keyspace (because
that's the fundamental nature of the data structure).
If you want to treat the keyspace as a 3-dimensional tuple space
(in a subspace of |N³), then you have to search separately in the tree
each time you come to the end of an (objectid, type, _) range. The
other alternative is to retrieve all of the linear range, and filter
out the unwanted keys whilst traversing the sequence.
Bottom line: it's a linear data structure, not a 3-dimensional one.
Please treat it as such, otherwise things are going to get complicated
and confusing.
Hugo.
> [1] http://www.spinics.net/lists/linux-btrfs/msg07617.html
--
=== Hugo Mills: hugo@... carfax.org.uk | darksatanic.net | lug.org.uk ===
PGP key: 65E74AC0 from wwwkeys.eu.pgp.net or http://www.carfax.org.uk
--- Great oxymorons of the world, no. 7: The Simple Truth ---
signature.asc
Description: Digital signature
