Re: BTRFS_IOC_TREE_SEARCH ioctl

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

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

On Mon, Jan 05, 2015 at 08:11:56PM +0100, Lennart Poettering wrote:
> On Mon, 05.01.15 18:22, Hugo Mills (hugo@carfax.org.uk) wrote:
> 
> > On Mon, Jan 05, 2015 at 06:15:12PM +0100, Lennart Poettering wrote:
> > > Heya,
> > > 
> > > I recently added some btrfs magic to systemd's machinectl/nspawn
> > > tool. More specifically it can now show the disk usage of a container
> > > that is stored in a btrfs subvolume. For that I made use of the btrfs
> > > quota logic. To read the current disk usage of a subvolume I took
> > > inspiration from btrfs-progs, most specifically the
> > > BTRFS_IOC_TREE_SEARCH ioctl(). Unfortunately, documentation for the
> > > ioctl seems to to be lacking, but there are some things about it I
> > > fail to grok:
> > > 
> > > What precisely are the semantics of the ioctl, regarding the search
> > > key min/max values (the fields of "struct btrfs_ioctl_search_key")? I
> > > kinda assumed that setting them would result in in only objects to be
> > > returned that are within the min/max ranges. However, that appears not
> > > to be the case. At least the min_offset/max_offset setting appears to
> > > be ignored?
> > 
> >    This is an old argument. :)
> > 
> >    Keys have three parts, so it's plausible (but, in this case, wrong)
> > to consider the space you're searching to be a 3-dimensional space of
> > (object, type, offset), which seems to be what you're expecting. A
> > min, max pair would then define an oblong subset of the keyspace from
> > which to retrieve keys.
> >
> >    However, that's not actually what's happening. Keys are indexed
> > within their tree(s) by a concatenation of the items in the key. A
> > key, therefore, should be thought of as a single 136-bit integer, and
> > the keys are lexically ordered, (object||type||offset), where "||" is
> > the concatenation operator. You get every key _lexically ordered_
> > between the min and max values. This is a superset of the
> > 3-dimensional results above.
> 
> Ah, I see. Makes sense.
> 
> I figure the comments in btrfs.h next to "struct
> btrfs_ioctl_search_key" could use some updating in this regard. They
> pretty explicitly suggest that the 3 axis were independent and each
> eleent individually would be between the respective min/max when
> returning...
> 
> Ideally the structure would just have two fields called "max", and
> "min" or so, of type btrfs_disk_key, right? In that case I figure the
> behaviour would have been clear. It's particular confusing that the
> disk key fields appear in a different order than otherwise used and
> with the min_transid+max_transid in the middle...

   Yes, it's not exactly the most obvious structure.

> Which brings me to my question: how does {min|max}_transid affect the
> search result? Is this axis orthogonal or is it neither?

   Hmm. Good question. I don't know the answer to that one, I'm
afraid. I _think_ it's orthogonal (since it's not indexed in the same
B-tree structures).

   Hugo.

-- 
Hugo Mills             | What do you give the man who has everything?
hugo@... carfax.org.uk | Penicillin is a good start...
http://carfax.org.uk/  |
PGP: 65E74AC0          |

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