On 2021/12/7 22:09, Qu Wenruo wrote:

On 2021/12/7 21:53, Maximilian Eichhorn wrote:

quoted

Dear Sir or Madam,

as part of a research project, I am working on the file system Btrfs and
its structures.
More specifically, I am learning about the extend tree and marking
individual areas as allocated.

In the course of this I also became aware of the wiki [1] and examined
the information to be found there.

I guess you mean this?

https://btrfs.wiki.kernel.org/index.php/On-disk_Format

quoted

However, not all aspects of the
Extend Tree are clear to me yet. Therefore I turn to you with the
question and request for further information.

In other file systems it is very easy to identify a certain block/sector
as allocated or to manually mark it as allocated because of the existing
structures. Unfortunately, I have not been able to do this with Btrfs so
far.

First thing first, other fses are mostly using bitmap to indicate which
blocks are allocated, that's why they are easy.

But that lacks a feature btrfs needs, to do backref lookup.

That's to say, when we know a block is allocated, we also want to know
which tree or inode owns it.

That's why btrfs extent tree is that complex.

Forgot to mention, for your traditional allocation bitmap, v2 space
cache (space cache tree) is your best equivalent, it only shows the free
space, without the hassle of full extent backrefs.

Although unlike regular bitmap one, it goes a mix of bitmap and extent.

But still way simpler than extent tree.

Another thing is, extent tree and v2 cache are all at btrfs logical
address space.

If you're going to check the free (unallocated) space for each device,
you need to go device tree, which is much simpler than extent tree.

Thanks,
Qu

But if your idea is just to get which blocks are in use, it's much easier.

(<logical> EXTENT_ITEM <size>) is for all DATA and some old metadata
backref. That indicates one range of bytes allocated.

All data extent should have one such key. For non-skinny metadata fs
(without skinny-metadata flag), all metadata should also have one such key.

(<logical> METADATA_ITEM <level>) is for METADATA backref.
With skinny metadata, all metadata should have either METADATA_ITEM or
EXTENT_ITEM. (For newer fs, there should be no EXTENT_ITEM for metadata,
the co-exist behavior is just for backward compatibility)

For METADATA_ITEM key, although we don't have the size in the key, since
btrfs uses fixed metadata size for the whole fs, the size is fixed to
nodesize from btrfs_superblock.


So just focusing on EXTENT_ITEM and METADATA_ITEM, you can get the
allocation info from extent tree.


Talking about the marking part, it's pretty hard, as although you can
mark one range allocated, you also need to insert the proper backref for
it. But since you're not really allocating the space, the backref will
not be valid and will trigger fsck error.

For a proper EXTENT_ITEM/METADATA insert, I guess you have to jump into
the rabbit hole of btrfs code, btrfs-progs will be a good start point.

Thanks,
Qu

quoted

Thanks in advance for your help and efforts!

Kind regards,
Maximilian Eichhorn