Exploring referenced extents

Exploring referenced extents

[Steven Davies]

For curiosity I'm trying to write a tool which will show me the size of 
data extents belonging to which files in a snapshot are exclusive to 
that snapshot as a way to show how much space would be freed if the 
snapshot were to be deleted, and which files in the snapshot are taking 
up the most space.

I'm working with Hans van Kranenburg's python-btrfs python library but 
my knowledge of the filesystem structures isn't good enough to allow me 
to figure out which bits of data I need to be able to achieve this. I'd 
be grateful if anyone could help me along with this.

So far my idea is:

for each OS file in a subvolume:
   find its data extents
   for each extent:
     find what files reference it #1
     for each referencing file:
       determine which subvolumes it lives in #2
     if all references are within this subvolume:
       record the OS file path and extents it references

for each recorded file path
   find its data extents
   output its path and the total number of bytes in all recorded extents 
(those which are not shared)

#1 and #2 are where my understanding breaks down. How do I find which 
files reference an extent and which subvolume those files are in?

Alternatively, if such a script already exists I would be happy to use 
it.

Thanks for any pointers.
-- 
Steven Davies

Re: Exploring referenced extents

[Steven Davies]

On 2020-05-09 12:11, Steven Davies wrote:
> For curiosity I'm trying to write a tool which will show me the size
> of data extents belonging to which files in a snapshot are exclusive
> to that snapshot as a way to show how much space would be freed if the
> snapshot were to be deleted, and which files in the snapshot are
> taking up the most space.
> 
> I'm working with Hans van Kranenburg's python-btrfs python library but
> my knowledge of the filesystem structures isn't good enough to allow
> me to figure out which bits of data I need to be able to achieve this.
> I'd be grateful if anyone could help me along with this.

Apologies for the spam, I've got most of it figured out now. The only 
thing remaining is to remove the double-counting of extents referenced 
by multiple files in the same subvolume. The code is here: 
https://github.com/daviessm/btrfs-snapshots-diff/blob/master/btrfs-subvol-size.py

-- 
Steven Davies

Re: Exploring referenced extents

[Graham Cobb]

On 09/05/2020 12:11, Steven Davies wrote:
> For curiosity I'm trying to write a tool which will show me the size of
> data extents belonging to which files in a snapshot are exclusive to
> that snapshot as a way to show how much space would be freed if the
> snapshot were to be deleted, and which files in the snapshot are taking
> up the most space.

I have some scripts to do that. They are slow but seem to pretty much
work. See https://github.com/GrahamCobb/extents-lists

> I'm working with Hans van Kranenburg's python-btrfs python library but
> my knowledge of the filesystem structures isn't good enough to allow me
> to figure out which bits of data I need to be able to achieve this. I'd
> be grateful if anyone could help me along with this.

Rewriting them to use Hans' library is one of the things I plan to do
one day!

> So far my idea is:
> 
> for each OS file in a subvolume:
>   find its data extents
>   for each extent:
>     find what files reference it #1
>     for each referencing file:
>       determine which subvolumes it lives in #2
>     if all references are within this subvolume:
>       record the OS file path and extents it references
> 
> for each recorded file path
>   find its data extents
>   output its path and the total number of bytes in all recorded extents
> (those which are not shared)

My approach is different. I don't attempt to understand which files
share extents, or which subvolumes they are in. Instead, I just try to
analyse which extents are in use by a subvolume (or, actually, any set
of files you specify).

This is easy (but slow) to do. And makes answering some questions easy.
However, it makes answering questions like "how many extents would
really be freed if I deleted this subvolume" hard (the scripts end up
working out the complete list of extents in use on the filesystem, and,
separately,  the list of which would be in use if the subvolume was
removed - the difference is the space freed up by deleting the subvolume).

This often takes a day or two.

I would be interested if you find a more efficient approach to working
out how much space will be freed up if a set of files (such as
particular subvolumes) are removed, allowing for snapshots, reflink
copies and dedup.

Graham

Re: Exploring referenced extents

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 3099 bytes --]



On 2020/5/9 下午7:11, Steven Davies wrote:
> For curiosity I'm trying to write a tool which will show me the size of
> data extents belonging to which files in a snapshot are exclusive to
> that snapshot as a way to show how much space would be freed if the
> snapshot were to be deleted,

Isn't that what btrfs qgroup doing?

> and which files in the snapshot are taking
> up the most space.

That would be interesting as qgroup only works at subvolume level.

> 
> I'm working with Hans van Kranenburg's python-btrfs python library but
> my knowledge of the filesystem structures isn't good enough to allow me
> to figure out which bits of data I need to be able to achieve this. I'd
> be grateful if anyone could help me along with this.

You may want to look into the on-disk format first.

But spoiler alert, since qgroup has its performance impact (although
hugely reduced in recent releases), it's unavoidable.

So would be any similar methods.
In fact, in your particular case, you need more work than qgroup, thus
it would be slower than qgroup.
Considering how many extra ioctl and context switches needed, I won't be
surprised if it's way slower than qgroup.

> 
> So far my idea is:
> 
> for each OS file in a subvolume:

This can be done by ftw(), and don't cross subvolume boundary.

>   find its data extents

Fiemap.

>   for each extent:
>     find what files reference it #1

Btrfs tree search ioctl, to search extent tree, and do backref walk just
like what we did in qgroup code.

>     for each referencing file:
>       determine which subvolumes it lives in #2

Unlike kernel, you also need to do this using btrfs tree search ioctl.

>     if all references are within this subvolume:
>       record the OS file path and extents it references
> 
> for each recorded file path
>   find its data extents
>   output its path and the total number of bytes in all recorded extents
> (those which are not shared)
> 
> #1 and #2 are where my understanding breaks down. How do I find which
> files reference an extent and which subvolume those files are in?

In short, you need the following skills (which would make you a btrfs
developer already):
- Basic btrfs tree search
  Things like how btrfs btree works, and how to iterate them.

- Basic user space file system interface understanding
  Know tools like fiemap().

- Btrfs extent tree understanding
  Know how to interpret inline/keyed data/metadata indirect/direct
  backref item.
  This is the key and the most complex thing.
  IIRC I have added some comments about this in recent backref.c code.

- Btrfs subvolume tree understanding
  Know how btrfs organize files/dirs in its subvolume trees.
  This is the key to locate which (subvolume, ino) owns a file extent.
  There are some pitfalls, like the backref item to file extent mapping.
  But should be easier than extent tree.

Thanks,
Qu

> 
> Alternatively, if such a script already exists I would be happy to use it.
> 
> Thanks for any pointers.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Exploring referenced extents

[Steven Davies]

On 2020-05-10 02:20, Qu Wenruo wrote:
> On 2020/5/9 下午7:11, Steven Davies wrote:
>> For curiosity I'm trying to write a tool which will show me the size 
>> of
>> data extents belonging to which files in a snapshot are exclusive to
>> that snapshot as a way to show how much space would be freed if the
>> snapshot were to be deleted,
> 
> Isn't that what btrfs qgroup doing?
> 
>> and which files in the snapshot are taking
>> up the most space.
> 
> That would be interesting as qgroup only works at subvolume level.
> 
>> 
>> I'm working with Hans van Kranenburg's python-btrfs python library but
>> my knowledge of the filesystem structures isn't good enough to allow 
>> me
>> to figure out which bits of data I need to be able to achieve this. 
>> I'd
>> be grateful if anyone could help me along with this.
> 
> You may want to look into the on-disk format first.
> 
> But spoiler alert, since qgroup has its performance impact (although
> hugely reduced in recent releases), it's unavoidable.
> 
> So would be any similar methods.
> In fact, in your particular case, you need more work than qgroup, thus
> it would be slower than qgroup.
> Considering how many extra ioctl and context switches needed, I won't 
> be
> surprised if it's way slower than qgroup.
> 
>> 
>> So far my idea is:
>> 
>> for each OS file in a subvolume:
> 
> This can be done by ftw(), and don't cross subvolume boundary.
> 
>>   find its data extents
> 
> Fiemap.
> 
>>   for each extent:
>>     find what files reference it #1
> 
> Btrfs tree search ioctl, to search extent tree, and do backref walk 
> just
> like what we did in qgroup code.
> 
>>     for each referencing file:
>>       determine which subvolumes it lives in #2
> 
> Unlike kernel, you also need to do this using btrfs tree search ioctl.
> 
>>     if all references are within this subvolume:
>>       record the OS file path and extents it references
>> 
>> for each recorded file path
>>   find its data extents
>>   output its path and the total number of bytes in all recorded 
>> extents
>> (those which are not shared)
>> 
>> #1 and #2 are where my understanding breaks down. How do I find which
>> files reference an extent and which subvolume those files are in?
> 
> In short, you need the following skills (which would make you a btrfs
> developer already):
> - Basic btrfs tree search
>   Things like how btrfs btree works, and how to iterate them.
> 
> - Basic user space file system interface understanding
>   Know tools like fiemap().
> 
> - Btrfs extent tree understanding
>   Know how to interpret inline/keyed data/metadata indirect/direct
>   backref item.
>   This is the key and the most complex thing.
>   IIRC I have added some comments about this in recent backref.c code.

Yes, I'm now stuck with a btrfs_extent_inline_ref of type 
BTRFS_SHARED_DATA_REF_KEY which I understand is a direct backref to a 
metadata block[1], but I don't understand how to search for that block 
itself. I got lucky with the rest of the code and have found all 
EXTENT_ITEM_KEYs for a file. The python library makes looking through 
the EXTENT_DATA_REF_KEYs easy but not the shared data refs.

> - Btrfs subvolume tree understanding
>   Know how btrfs organize files/dirs in its subvolume trees.
>   This is the key to locate which (subvolume, ino) owns a file extent.
>   There are some pitfalls, like the backref item to file extent 
> mapping.
>   But should be easier than extent tree.

[1] 
https://btrfs.wiki.kernel.org/index.php/Data_Structures#btrfs_extent_inline_ref

Thanks,
-- 
Steven Davies

Re: Exploring referenced extents

[Steven Davies]

On 2020-05-09 22:32, Graham Cobb wrote:
> On 09/05/2020 12:11, Steven Davies wrote:
>> For curiosity I'm trying to write a tool which will show me the size 
>> of
>> data extents belonging to which files in a snapshot are exclusive to
>> that snapshot as a way to show how much space would be freed if the
>> snapshot were to be deleted, and which files in the snapshot are 
>> taking
>> up the most space.
> 
> I have some scripts to do that. They are slow but seem to pretty much
> work. See https://github.com/GrahamCobb/extents-lists
> 
>> I'm working with Hans van Kranenburg's python-btrfs python library but
>> my knowledge of the filesystem structures isn't good enough to allow 
>> me
>> to figure out which bits of data I need to be able to achieve this. 
>> I'd
>> be grateful if anyone could help me along with this.
> 
> Rewriting them to use Hans' library is one of the things I plan to do
> one day!
> 
>> So far my idea is:
>> 
>> for each OS file in a subvolume:
>>   find its data extents
>>   for each extent:
>>     find what files reference it #1
>>     for each referencing file:
>>       determine which subvolumes it lives in #2
>>     if all references are within this subvolume:
>>       record the OS file path and extents it references
>> 
>> for each recorded file path
>>   find its data extents
>>   output its path and the total number of bytes in all recorded 
>> extents
>> (those which are not shared)
> 
> My approach is different. I don't attempt to understand which files
> share extents, or which subvolumes they are in. Instead, I just try to
> analyse which extents are in use by a subvolume (or, actually, any set
> of files you specify).
> 
> This is easy (but slow) to do. And makes answering some questions easy.
> However, it makes answering questions like "how many extents would
> really be freed if I deleted this subvolume" hard (the scripts end up
> working out the complete list of extents in use on the filesystem, and,
> separately,  the list of which would be in use if the subvolume was
> removed - the difference is the space freed up by deleting the 
> subvolume).

The original goal for my script was to answer the question "why does 
qgroups show this snapshot has so much exclusive data?". I keep a record 
of the qgroups reported exclusive sizes over time and occasionally check 
whether backups or snapshotting need to be reconfigured. I figured that 
a list of files and their exclusive extent sizes would show what is 
contributing the most to the exclusive data shown by qgroups.

I suppose what I'm effectively doing is writing a more granular version 
of qgroups, as Qu said. Like yours, it'll be slow for large trees.

> This often takes a day or two.
> 
> I would be interested if you find a more efficient approach to working
> out how much space will be freed up if a set of files (such as
> particular subvolumes) are removed, allowing for snapshots, reflink
> copies and dedup.
> 
> Graham
-- 
Steven Davies

Re: Exploring referenced extents

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 4802 bytes --]



On 2020/5/10 下午6:55, Steven Davies wrote:
> On 2020-05-10 02:20, Qu Wenruo wrote:
>> On 2020/5/9 下午7:11, Steven Davies wrote:
>>> For curiosity I'm trying to write a tool which will show me the size of
>>> data extents belonging to which files in a snapshot are exclusive to
>>> that snapshot as a way to show how much space would be freed if the
>>> snapshot were to be deleted,
>>
>> Isn't that what btrfs qgroup doing?
>>
>>> and which files in the snapshot are taking
>>> up the most space.
>>
>> That would be interesting as qgroup only works at subvolume level.
>>
>>>
>>> I'm working with Hans van Kranenburg's python-btrfs python library but
>>> my knowledge of the filesystem structures isn't good enough to allow me
>>> to figure out which bits of data I need to be able to achieve this. I'd
>>> be grateful if anyone could help me along with this.
>>
>> You may want to look into the on-disk format first.
>>
>> But spoiler alert, since qgroup has its performance impact (although
>> hugely reduced in recent releases), it's unavoidable.
>>
>> So would be any similar methods.
>> In fact, in your particular case, you need more work than qgroup, thus
>> it would be slower than qgroup.
>> Considering how many extra ioctl and context switches needed, I won't be
>> surprised if it's way slower than qgroup.
>>
>>>
>>> So far my idea is:
>>>
>>> for each OS file in a subvolume:
>>
>> This can be done by ftw(), and don't cross subvolume boundary.
>>
>>>   find its data extents
>>
>> Fiemap.
>>
>>>   for each extent:
>>>     find what files reference it #1
>>
>> Btrfs tree search ioctl, to search extent tree, and do backref walk just
>> like what we did in qgroup code.
>>
>>>     for each referencing file:
>>>       determine which subvolumes it lives in #2
>>
>> Unlike kernel, you also need to do this using btrfs tree search ioctl.
>>
>>>     if all references are within this subvolume:
>>>       record the OS file path and extents it references
>>>
>>> for each recorded file path
>>>   find its data extents
>>>   output its path and the total number of bytes in all recorded extents
>>> (those which are not shared)
>>>
>>> #1 and #2 are where my understanding breaks down. How do I find which
>>> files reference an extent and which subvolume those files are in?
>>
>> In short, you need the following skills (which would make you a btrfs
>> developer already):
>> - Basic btrfs tree search
>>   Things like how btrfs btree works, and how to iterate them.
>>
>> - Basic user space file system interface understanding
>>   Know tools like fiemap().
>>
>> - Btrfs extent tree understanding
>>   Know how to interpret inline/keyed data/metadata indirect/direct
>>   backref item.
>>   This is the key and the most complex thing.
>>   IIRC I have added some comments about this in recent backref.c code.
> 
> Yes, I'm now stuck with a btrfs_extent_inline_ref of type
> BTRFS_SHARED_DATA_REF_KEY which I understand is a direct backref to a
> metadata block[1],

Yep, SHARED_DATA_REF is the type for direct (shows the direct parent)
for data.
But there is also an indirect (just tell you how to search) one,
EXTENT_DATA_REF, and under most case, EXTENT_DATA_REF is more common.

> but I don't understand how to search for that block
> itself. I got lucky with the rest of the code and have found all
> EXTENT_ITEM_KEYs for a file. The python library makes looking through
> the EXTENT_DATA_REF_KEYs easy but not the shared data refs.

For EXTENT_DATA_REF, it contains rootid, objectid (inode number), offset
(not file offset, but a calculated one), and count.
That's pretty simple, since it contains the rootid and inode number.

For SHARED_DATA_REF, you need to search the parent bytenr in extent tree.
It can be SHARED_BLOCK_REF (direct meta ref) or TREE_BLOCK_REF (indirect
meta ref).

For TREE_BLOCK_REF, although it contains the owner, you can't stop here,
but still do a search to build a full path towards that root node.
Then check each node to make sure if the node is also shared by other trees.

For SHARED_BLOCK_REF, you need to go to its parent again, until you
build the full path to the root node.

Now you can see why the backref code used in balance and qgroup is complex.

Thanks,
Qu

> 
>> - Btrfs subvolume tree understanding
>>   Know how btrfs organize files/dirs in its subvolume trees.
>>   This is the key to locate which (subvolume, ino) owns a file extent.
>>   There are some pitfalls, like the backref item to file extent mapping.
>>   But should be easier than extent tree.
> 
> [1]
> https://btrfs.wiki.kernel.org/index.php/Data_Structures#btrfs_extent_inline_ref
> 
> 
> Thanks,


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Exploring referenced extents

[Graham Cobb]

On 10/05/2020 12:07, Steven Davies wrote:
> The original goal for my script was to answer the question "why does
> qgroups show this snapshot has so much exclusive data?". I keep a record
> of the qgroups reported exclusive sizes over time and occasionally check
> whether backups or snapshotting need to be reconfigured. I figured that
> a list of files and their exclusive extent sizes would show what is
> contributing the most to the exclusive data shown by qgroups.

Ah. In my case I have found the notion of "exclusive" to be useless. I
don't use qgroups but I have on-disk snapshots of pretty much every
subvolume so nothing is really exclusive.

However, I do like to be able to answer questions like "if I was to
remove these three old snapshots, how much space would be freed", and
the other examples in the README for my scripts.

Still, I am very interested to see how you get on -- my scripts only use
FIEMAP today (effectively, using filefrag(8)).

I am seriously considering, after I switch to using the Python library,
building a userspace database of extent usage for files and directory
trees so that the queries can be fast. The challenge, then, is to
maintain it. It would, again, be very much like a usermode version of
qgroups.

Re: Exploring referenced extents

[Steven Davies]

On 2020-05-10 12:55, Qu Wenruo wrote:
> On 2020/5/10 下午6:55, Steven Davies wrote:
>> On 2020-05-10 02:20, Qu Wenruo wrote:

>> Yes, I'm now stuck with a btrfs_extent_inline_ref of type
>> BTRFS_SHARED_DATA_REF_KEY which I understand is a direct backref to a
>> metadata block[1],
> 
> Yep, SHARED_DATA_REF is the type for direct (shows the direct parent)
> for data.
> But there is also an indirect (just tell you how to search) one,
> EXTENT_DATA_REF, and under most case, EXTENT_DATA_REF is more common.
> 
>> but I don't understand how to search for that block
>> itself. I got lucky with the rest of the code and have found all
>> EXTENT_ITEM_KEYs for a file. The python library makes looking through
>> the EXTENT_DATA_REF_KEYs easy but not the shared data refs.
> 
> For EXTENT_DATA_REF, it contains rootid, objectid (inode number), 
> offset
> (not file offset, but a calculated one), and count.
> That's pretty simple, since it contains the rootid and inode number.
> 
> For SHARED_DATA_REF, you need to search the parent bytenr in extent 
> tree.
> It can be SHARED_BLOCK_REF (direct meta ref) or TREE_BLOCK_REF 
> (indirect
> meta ref).
> 
> For TREE_BLOCK_REF, although it contains the owner, you can't stop 
> here,
> but still do a search to build a full path towards that root node.
> Then check each node to make sure if the node is also shared by other 
> trees.
> 
> For SHARED_BLOCK_REF, you need to go to its parent again, until you
> build the full path to the root node.
> 
> Now you can see why the backref code used in balance and qgroup is 
> complex.

I can, I get the feeling that this is now way beyond my abilities and I 
can see why it will be very slow to run in practice - especially through 
the Python abstraction. Perhaps if knorrie adds backref walking helpers 
to python-btrfs it might become more feasible.

-- 
Steven Davies

Re: Exploring referenced extents

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 2624 bytes --]



On 2020/5/10 下午8:51, Steven Davies wrote:
> On 2020-05-10 12:55, Qu Wenruo wrote:
>> On 2020/5/10 下午6:55, Steven Davies wrote:
>>> On 2020-05-10 02:20, Qu Wenruo wrote:
> 
>>> Yes, I'm now stuck with a btrfs_extent_inline_ref of type
>>> BTRFS_SHARED_DATA_REF_KEY which I understand is a direct backref to a
>>> metadata block[1],
>>
>> Yep, SHARED_DATA_REF is the type for direct (shows the direct parent)
>> for data.
>> But there is also an indirect (just tell you how to search) one,
>> EXTENT_DATA_REF, and under most case, EXTENT_DATA_REF is more common.
>>
>>> but I don't understand how to search for that block
>>> itself. I got lucky with the rest of the code and have found all
>>> EXTENT_ITEM_KEYs for a file. The python library makes looking through
>>> the EXTENT_DATA_REF_KEYs easy but not the shared data refs.
>>
>> For EXTENT_DATA_REF, it contains rootid, objectid (inode number), offset
>> (not file offset, but a calculated one), and count.
>> That's pretty simple, since it contains the rootid and inode number.
>>
>> For SHARED_DATA_REF, you need to search the parent bytenr in extent tree.
>> It can be SHARED_BLOCK_REF (direct meta ref) or TREE_BLOCK_REF (indirect
>> meta ref).
>>
>> For TREE_BLOCK_REF, although it contains the owner, you can't stop here,
>> but still do a search to build a full path towards that root node.
>> Then check each node to make sure if the node is also shared by other
>> trees.
>>
>> For SHARED_BLOCK_REF, you need to go to its parent again, until you
>> build the full path to the root node.
>>
>> Now you can see why the backref code used in balance and qgroup is
>> complex.
> 
> I can, I get the feeling that this is now way beyond my abilities and I
> can see why it will be very slow to run in practice - especially through
> the Python abstraction. Perhaps if knorrie adds backref walking helpers
> to python-btrfs it might become more feasible.
> 
Another problem here is, the btrfs tree search operation is all done on
commit tree, which is the on-disk data (not the running transaction).

Further more, since we need to search extent tree several times, and
unlike kernel space, we can using a transaction handler to block current
transaction being committed (which switch commit root with current root).

In user space, we don't have such ability to control transaction
commitment, which means we can easily get transaction being committed
during our long search, resulting bad result.

It's already hard to do it in kernel space, it won't be any simpler for
user space.

Thanks,
Qu


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Exploring referenced extents

[Hans van Kranenburg]

Hi!

On 5/9/20 1:11 PM, Steven Davies wrote:
> For curiosity I'm trying to write a tool which will show me the size of 
> data extents belonging to which files in a snapshot are exclusive to 
> that snapshot as a way to show how much space would be freed if the 
> snapshot were to be deleted, and which files in the snapshot are taking 
> up the most space.

Yes, so that means that if a file in that snapshot (subvolume) is using
a data extent, you want to know if there's any file in a *different*
subvolume that is still referencing *any* data from the extent, which
will block the whole thing from getting freed.

Just putting that here to verify if this is actually what you thought,
because I think it is. And, it might not be immediately obvious to others.

> I'm working with Hans van Kranenburg's python-btrfs python library but 
> my knowledge of the filesystem structures isn't good enough to allow me 
> to figure out which bits of data I need to be able to achieve this. I'd 
> be grateful if anyone could help me along with this.
> 
> So far my idea is:
> 
> for each OS file in a subvolume:

I'd recommend to just dump the complete metadata tree with the subvolume
ID as number. That way you will just see all FileExtentItem of all files
in the subvol flying by in the results.

I see you already do a search with btrfs.ioctl.search_v2, now make that
a search for a whole tree by removing min and max that you currently use
to limit it to an inode num.

Using the 0 tree for search combined with opening the fs while pointing
to anything inside the subvol you want to inspect is clever, great.

Side note: the path that the fs object was initialized with is also
available as fs.path, you don't have to drag it around (e.g. second arg
in inspect_from).

https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ctree.FileSystem

>    find its data extents

Yes, these are all the FileExtentItem items that you see flying by.

https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ctree.FileExtentItem

>    for each extent:

FileExtentItem has attribute disk_bytenr, I see you're already using
that. Good.

>      find what files reference it #1
>      for each referencing file:
>        determine which subvolumes it lives in #2

For this, we delegate the work to the running linux kernel code, to ask
it who's using the extent at this disk_bytenr.

https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ioctl.logical_to_ino_v2

The main thing you're looking for is the ignore_offset option, which
will give you a list of *any* user of *any* data in that extent, instead
of only the first 4096 bytes in it which disk_bytenr itself is part of.

There's some more info in the git commit message that added _v2 (one day
this will end up in tutorial pages):

https://github.com/knorrie/python-btrfs/commit/38cd5528ff1ced0be908e1e697758c7431b92a0d

The show_block_group_data_extent_filenames.py implements it as example,
look at the using_v2 in there:

https://github.com/knorrie/python-btrfs/commit/7a0749d567abde425c11a43e5fe9177435d0cf28#diff-87cff59a5b983c0f3408b60d654f4f66

So, you want to end with bytes_missed 0, otherwise you're ignoring results.

Now look at the inode objects you get, they have a root attribute, which
is the subvol id of that inode. If inode.root is different than the
subvol ID you're analyzing, then you know that there's a file in another
subvol that uses the extent. Voila.

>      if all references are within this subvolume:
>        record the OS file path and extents it references

By looking at the inode number of the FileExtentItem all the time, you
will know when it jumps to the next number (next file), and then you can
finish up for the previous file.

Oh, I see the FileExtentItem class has no explicit helper attribute to
get the inode number. Ha, I will add that (makes a note). You can either
use item.key.objectid or header.objectid for now to get it.

> for each recorded file path
>    find its data extents
>    output its path and the total number of bytes in all recorded extents 
> (those which are not shared)

You already are using item.disk_num_bytes somewhere. This disk_num_bytes
is the size of the extent, so no extra lookup in the extent tree is
needed. While doing the above loop and looking at the FileExtentItem
objects, you can already gather the information about total disk space
that could be freed.

Now, the last missing part is of course that you have an inode number,
and want to know the file name that belongs to it.

For that, you use the INO_LOOKUP ioctl:

https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ioctl.ino_lookup

> #1 and #2 are where my understanding breaks down. How do I find which 
> files reference an extent and which subvolume those files are in?
> 
> Alternatively, if such a script already exists I would be happy to use 
> it.

Others will be happy with what you're doing now. :-)

Hans

Re: Exploring referenced extents

[Steven Davies]

On 2020-05-11 02:21, Hans van Kranenburg wrote:
> Hi!

Thanks for your insights!

> On 5/9/20 1:11 PM, Steven Davies wrote:
>> For curiosity I'm trying to write a tool which will show me the size 
>> of
>> data extents belonging to which files in a snapshot are exclusive to
>> that snapshot as a way to show how much space would be freed if the
>> snapshot were to be deleted, and which files in the snapshot are 
>> taking
>> up the most space.

<snip lots of useful information>

This is what I was missing when I read the documentation:

>>      find what files reference it #1
>>      for each referencing file:
>>        determine which subvolumes it lives in #2
> 
> For this, we delegate the work to the running linux kernel code, to ask
> it who's using the extent at this disk_bytenr.
> 
> https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ioctl.logical_to_ino_v2
> 
> The main thing you're looking for is the ignore_offset option, which
> will give you a list of *any* user of *any* data in that extent, 
> instead
> of only the first 4096 bytes in it which disk_bytenr itself is part of.

I did rework the script - albeit not the way you suggested (I still walk 
the file tree and look up the extents) because my subvolumes are small 
and stored on relatively fast SSDs, and this way allows me to narrow the 
search to a single directory - but it seems to work now. It isn't pretty 
yet either! It's succeeded in telling me that the reason the oldest 
snapshot of my / subvolume is huge is because it contains a dump of 
linux-firmware that's not shared by anything.

Next job - make it into a tree-like utility.

https://github.com/daviessm/btrfs-snapshots-diff/blob/4003a3fdec70c2a0de348e75a6576f9342754f54/btrfs-subvol-size.py

-- 
Steven Davies

Re: Exploring referenced extents

[Hans van Kranenburg]

Hi!

On 5/13/20 10:08 PM, Steven Davies wrote:
> On 2020-05-11 02:21, Hans van Kranenburg wrote:
>> Hi!
> 
> Thanks for your insights!
> 
>> On 5/9/20 1:11 PM, Steven Davies wrote:
>>> For curiosity I'm trying to write a tool which will show me the size 
>>> of
>>> data extents belonging to which files in a snapshot are exclusive to
>>> that snapshot as a way to show how much space would be freed if the
>>> snapshot were to be deleted, and which files in the snapshot are 
>>> taking
>>> up the most space.
> 
> <snip lots of useful information>
> 
> This is what I was missing when I read the documentation:
> 
>>>      find what files reference it #1
>>>      for each referencing file:
>>>        determine which subvolumes it lives in #2
>>
>> For this, we delegate the work to the running linux kernel code, to ask
>> it who's using the extent at this disk_bytenr.
>>
>> https://python-btrfs.readthedocs.io/en/stable/btrfs.html#btrfs.ioctl.logical_to_ino_v2
>>
>> The main thing you're looking for is the ignore_offset option, which
>> will give you a list of *any* user of *any* data in that extent, 
>> instead
>> of only the first 4096 bytes in it which disk_bytenr itself is part of.
> 
> I did rework the script - albeit not the way you suggested (I still walk 
> the file tree and look up the extents) because my subvolumes are small 
> and stored on relatively fast SSDs, and this way allows me to narrow the 
> search to a single directory - but it seems to work now.

Haha, wonderful! Of course, the thing you're learning here is that you
can do whatever you want, so that it best fits your own special
situation. You don't have to rely on a pre-baked tool with command line
options which just cannot do that single thing that you were looking for.

> It isn't pretty 
> yet either! It's succeeded in telling me that the reason the oldest 
> snapshot of my / subvolume is huge is because it contains a dump of 
> linux-firmware that's not shared by anything.
> 
> Next job - make it into a tree-like utility.

I trust there will be more ideas later... :) Have fun, and share some of
the results, they might inspire others, like you already have seen
happening in this mail thread.

> 
> https://github.com/daviessm/btrfs-snapshots-diff/blob/4003a3fdec70c2a0de348e75a6576f9342754f54/btrfs-subvol-size.py

Knorrie