BTRFS_IOC_TREE_SEARCH ioctl
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?
The code I hacked up is this one:
http://cgit.freedesktop.org/systemd/systemd/tree/src/shared/btrfs-util.c#n427
I try to read the BTRFS_QGROUP_STATUS_KEY and BTRFS_QGROUP_LIMIT_KEY objects for the subvolume I care about. Hence I initialize .min_type and .max_type to the two types (in the right order), and then .min_offset and .max_offset to subvolume id. However, the search ioctl will still give me entries back with offsets != the subvolume id...
Is this intended behaviour of the search ioctl? If so, what's the rationale?
My code currently invokes the search ioctl in a loop to work around the fact that .min_offset/.max_offset don't work as I wish they did... I wish I could get rid of this loop and filtering out of the entries I get back that aren't in th range I specified...
Lennart
Quoted 11 lines · Lennart Poettering
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_SEARCHioctl(). Unfortunately, documentation for the ioctl seems to to be lacking, but there are some things about it I fail to grok:
Quoted 6 lines
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.
About 3-4 years ago, we see-sawed through several messy patches in
userspace (and at least one in the kernel) before this distinction and difference in semantics was understood.
Quoted 4 lines
The code I hacked up is this one:
http://cgit.freedesktop.org/systemd/systemd/tree/src/shared/btrfs-util.c#n427
Quoted 8 lines
I try to read the
BTRFS_QGROUP_STATUS_KEYandBTRFS_QGROUP_LIMIT_KEYobjects for the subvolume I care about. Hence I initialize .min_type and .max_type to the two types (in the right order), and then .min_offset and .max_offset to subvolume id. However, the search ioctl will still give me entries back with offsets != the subvolume id...Is this intended behaviour of the search ioctl? If so, what's the rationale?
Yes, it is. The rationale is that it's simply walking through the
key values in the tree linearly until the max value is found.
Quoted 4 lines
My code currently invokes the search ioctl in a loop to work around the fact that .min_offset/.max_offset don't work as I wish they did... I wish I could get rid of this loop and filtering out of the entries I get back that aren't in th range I specified...
You'd have to do this in kernel space if you wanted the 3D
semantics instead of the concatenated semantics. There's no free lunch here. It might be a good idea for "libbtrfs" (such as it is) to implement this, as it's a (moderately rare) repeat request.
Hugo.
Signature · 4 lines
Hugo Mills | Klytus, I'm bored. What plaything can you offer me hugo@... carfax.org.uk | today? http://carfax.org.uk/ | PGP: 65E74AC0 | Ming the Merciless, Flash Gordon
Quoted 27 lines · Hugo Mills
Quoted 11 lines · Lennart Poettering
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_SEARCHioctl(). Unfortunately, documentation for the ioctl seems to to be lacking, but there are some things about it I fail to grok:Quoted 6 lines
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.
Quoted 7 lines
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_lexicallyordered_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...
Which brings me to my question: how does {min|max}_transid affect the search result? Is this axis orthogonal or is it neither?
Thanks for the explanations!
Lennart
Signature · 1 line
Lennart Poettering, Red Hat
Quoted 45 lines · Lennart Poettering
Quoted 27 lines · Hugo Mills
Quoted 11 lines · Lennart Poettering
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_SEARCHioctl(). Unfortunately, documentation for the ioctl seems to to be lacking, but there are some things about it I fail to grok:Quoted 6 lines
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.Quoted 7 lines
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_lexicallyordered_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.hnext to "structbtrfs_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...
Quoted 5 lines
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.
Quoted 2 lines
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.
Signature · 4 lines
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 |
A message that is not in the archive (sent off-list or not yet received): CAJSBqdfJ9EpR3AgLFkCEU+yYSPtJTyVvo5r15WaeF1UszQ_3Yg@mail.gmail.com
Quoted 2 lines · Nehemiah Dacres
Is libbtrfs documented or even stable yet? What stage of development is it in anyway? is there a design spec yet?
Note that the code we use in systemd is not based on libbtrfs, we just call the ioctls directly.
Lennart
Signature · 1 line
Lennart Poettering, Red Hat
Quoted 22 lines · Lennart Poettering
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_SEARCHioctl(). 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?The code I hacked up is this one:
http://cgit.freedesktop.org/systemd/systemd/tree/src/shared/btrfs-util.c#n427
Quoted 8 lines
I try to read the
BTRFS_QGROUP_STATUS_KEYandBTRFS_QGROUP_LIMIT_KEYobjects for the subvolume I care about. Hence I initialize .min_type and .max_type to the two types (in the right order), and then .min_offset and .max_offset to subvolume id. However, the search ioctl will still give me entries back with offsets != the subvolume id...Is this intended behaviour of the search ioctl? If so, what's the rationale?
The search is done linearity; the min_* are the starting point, and
the max_* are the ending point; in the past someone gave me this example:
if you think in two dimensions, the scan is *not* performed in a rectangular region but in a horizontal area...
My ascii art: this is what you are expecting:
............ ..XXXXXXXX.. ..XXXXXXXX.. ..XXXXXXXX.. ............
this is what BTRFS_IOC_TREE_SEARCH returns:
............ ..XXXXXXXXXX XXXXXXXXXXXX XXXXXXXXXX.. ............
Quoted 4 lines
My code currently invokes the search ioctl in a loop to work around the fact that .min_offset/.max_offset don't work as I wish they did...
On the best of my (limited) btrfs knowledge, your "workaround" is needed due to the ioctl behavior.
Quoted 2 lines
I wish I could get rid of this loop and filtering out of the entries I get back that aren't in th range I specified...
See this thread [1] for what happened to me long time ago
Quoted 2 lines
Lennart
Goffreo
Quoted 5 lines
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
[1] http://www.spinics.net/lists/linux-btrfs/msg07641.html
Signature · 2 lines
gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it> Key fingerprint BBF5 1610 0B64 DAC6 5F7D 17B2 0EDA 9B37 8B82 E0B5