Re: [PATCH RFCv2] new ioctl TREE_SEARCH_V2

[Hugo Mills <hugo@carfax.org.uk>]

[-- Attachment #1: Type: text/plain, Size: 2344 bytes --]

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 828 bytes --]