Logical to Physical Address Mapping/Translation in Btrfs
Hi,
May I know how the logical address is translated to the physical address in Btrfs?
I have read the official documentation of Btrfs available here
(https://btrfs.readthedocs.io/en/latest/Introduction.html). It is not covering the address translation part in detail.
I have also gone through the Btrfs source code
(https://github.com/torvalds/linux/tree/master/fs/btrfs). I could not figure out the address translation from the code also.
After referring to the following functions, what I could understand is that after getting the logical address of Chunk tree root from the superblock, we need to convert it into the corresponding physical address for parsing into the next level.
int __cold open_ctree(struct super_block *sb, struct btrfs_fs_devices *fs_devices, char *options)
int btrfs_read_chunk_tree(struct btrfs_fs_info *fs_info)
static int read_one_chunk(struct btrfs_key *key, struct extent_buffer *leaf, struct btrfs_chunk *chunk)
Any hints or pointers to the documentation on this is greatly appreciated. I want to know the implementation part in btrfs-progs/source code.
Thanks in advance
Saranya G
CDAC
------------------------------------------------------------------------------------------------------------
[ C-DAC is on Social-Media too. Kindly follow us at:
Facebook: https://www.facebook.com/CDACINDIA & Twitter: @cdacindia ]
This e-mail is for the sole use of the intended recipient(s) and may contain confidential and privileged information. If you are not the intended recipient, please contact the sender by reply e-mail and destroy all copies and the original message. Any unauthorized review, use, disclosure, dissemination, forwarding, printing or copying of this email is strictly prohibited and appropriate legal action will be taken.
------------------------------------------------------------------------------------------------------------
Quoted 4 lines · On 2023/12/19 21:59, [email protected] wrote:
Hi,
May I know how the logical address is translated to the physical address in Btrfs?
This is documented in btrfs-dev-docs/chunks.txt:
https://github.com/btrfs/btrfs-dev-docs/blob/master/chunks.txt
Quoted 17 lines
I have read the official documentation of Btrfs available here
(https://btrfs.readthedocs.io/en/latest/Introduction.html). It is not covering the address translation part in detail.I have also gone through the Btrfs source code
(https://github.com/torvalds/linux/tree/master/fs/btrfs). I could not figure out the address translation from the code also.After referring to the following functions, what I could understand is that after getting the logical address of Chunk tree root from the superblock, we need to convert it into the corresponding physical address for parsing into the next level.
int
__coldopen_ctree(struct super_block *sb, struct btrfs_fs_devices *fs_devices, char *options)
Quoted 7 lines
int
btrfs_read_chunk_tree(struct btrfs_fs_info *fs_info)static int
read_one_chunk(struct btrfs_key *key, struct extent_buffer *leaf, struct btrfs_chunk *chunk)Any hints or pointers to the documentation on this is greatly appreciated. I want to know the implementation part in btrfs-progs/source code.
For the implementation, you need to check btrfs_map_block() (the same name in both btrfs-progs and kernel), which is the core of logical -> physical mapping.
All your mentioned functions are just reading the chunk tree into memory.
Thanks,
Qu
Quoted 20 lines
Thanks in advance
Saranya G
CDAC------------------------------------------------------------------------------------------------------------
[ C-DAC is on Social-Media too. Kindly follow us at:
Facebook: https://www.facebook.com/CDACINDIA & Twitter: @cdacindia ]This e-mail is for the sole use of the intended recipient(s) and may contain confidential and privileged information. If you are not the intended recipient, please contact the sender by reply e-mail and destroy all copies and the original message. Any unauthorized review, use, disclosure, dissemination, forwarding, printing or copying of this email is strictly prohibited and appropriate legal action will be taken.
------------------------------------------------------------------------------------------------------------
Quoted 4 lines · Qu Wenruo
On 2023/12/19 21:59, [email protected] wrote:
Quoted 9 lines
Quoted 4 lines
Hi,
May I know how the logical address is translated to the physical address in Btrfs?
This is documented in
btrfs-dev-docs/chunks.txt:https://github.com/btrfs/btrfs-dev-docs/blob/master/chunks.txt
I tried to read it three times and I still do not understand it.
It starts with showing two chunks - metadata and data
--><--
item 3 key (FIRST_CHUNK_TREE CHUNK_ITEM 4593811456) itemoff 15863 itemsize 112 length 268435456 owner 2 stripe_len 65536 type METADATA|RAID1 io_align 65536 io_width 65536 sector_size 4096num_stripes 2 sub_stripes 1
stripe 0 devid 2 offset 2425356288dev_uuid a7963b67-1277-49ff-bb1d-9d81c5605f1b
stripe 1 devid 1 offset 2446327808dev_uuid 5f8b54f0-2a35-4330-a06b-9c8fd935bc36
item 2 key (FIRST_CHUNK_TREE CHUNK_ITEM 2446327808) itemoff 15975 itemsize 112 length 2147483648 owner 2 stripe_len 65536 type DATA|RAID0 io_align 65536 io_width 65536 sector_size 4096num_stripes 2 sub_stripes 1
stripe 0 devid 2 offset 1351614464dev_uuid a7963b67-1277-49ff-bb1d-9d81c5605f1b
stripe 1 devid 1 offset 1372585984dev_uuid 5f8b54f0-2a35-4330-a06b-9c8fd935bc36
--><--
Then it apparently talks about writing into metadata chunk, judging by the logical address
--><--
Consider we want to write 2m at at 4596957184 - that's 3m past the start of the data chunk in the previous example. In order to see where in the physical stripe this write will go into we need to derive the following values:
block group offset = [address within block group] - [start address of block group]block_group_offset = 4596957184 - 4593811456 = 3145728 => 3m --><--
The chunk start 4593811456 is metadata. But when talking about physical location it suddenly takes address of the device extent of the data chunk
--><--physical_address = [physical stripe start] + [logical_stripe] * [logical stripe_size]physical_address = 1351614464 + 48 * 64k = 1351614464 + 3145728 = 1354760192 --><--
1351614464 is the address of the stripe 0 of the data chunk. It is completely unclear whether it is intentional or not.
Nor does it explain how the device extent (physical stripe) is selected and how it jumps from the block_group_offset to the (physical) stripe number.
Intermixing "chunk" and "block group" does not help in understanding it either.
And I suspect RAID5/6 is something entirely different ...
Quoted 39 lines · Andrei Borzenkov
Quoted 4 lines · Qu Wenruo
On 2023/12/19 21:59, [email protected] wrote:
Quoted 9 lines
Quoted 4 lines
Hi,
May I know how the logical address is translated to the physical address in Btrfs?
This is documented in
btrfs-dev-docs/chunks.txt:https://github.com/btrfs/btrfs-dev-docs/blob/master/chunks.txt
I tried to read it three times and I still do not understand it.
It starts with showing two chunks - metadata and data
--><--
item 3 key (FIRST_CHUNK_TREECHUNK_ITEM4593811456) itemoff 15863 itemsize 112 length 268435456 owner 2stripe_len65536 type METADATA|RAID1io_align65536io_width65536sector_size4096num_stripes2sub_stripes1
stripe 0 devid 2 offset 2425356288dev_uuida7963b67-1277-49ff-bb1d-9d81c5605f1b
stripe 1 devid 1 offset 2446327808dev_uuid5f8b54f0-2a35-4330-a06b-9c8fd935bc36item 2 key (
FIRST_CHUNK_TREECHUNK_ITEM2446327808) itemoff 15975 itemsize 112 length 2147483648 owner 2stripe_len65536 type DATA|RAID0io_align65536io_width65536sector_size4096num_stripes2sub_stripes1
stripe 0 devid 2 offset 1351614464dev_uuida7963b67-1277-49ff-bb1d-9d81c5605f1b
stripe 1 devid 1 offset 1372585984dev_uuid5f8b54f0-2a35-4330-a06b-9c8fd935bc36
--><--
Quoted 2 lines
Then it apparently talks about writing into metadata chunk, judging by the logical address
Firstly, btrfs uses chunk and block groups interchangeably.
Block groups are more used inside extent tree, as we have BLOCK_GROUP_ITEM, focusing on the used/free space.
Meanwhile for logical -> physical mapping, we use chunk more frequently, as that's the name of the chunk tree, and CHUNK_ITEM.
Quoted 15 lines
--><--
Consider we want to write 2m at at 4596957184 - that's 3m past the start of the data chunk in the previous example. In order to see where in the physical stripe this write will go into we need to derive the following values:block group offset = [address within block group] - [start address of block group]
block_group_offset= 4596957184 - 4593811456 = 3145728 => 3m --><--The chunk start 4593811456 is metadata. But when talking about physical location it suddenly takes address of the device extent of the data chunk
Quoted 5 lines
--><--
physical_address= [physical stripe start] + [logical_stripe] * [logicalstripe_size]physical_address= 1351614464 + 48 * 64k = 1351614464 + 3145728 = 1354760192 --><--
Damn it, this part is for RAID0, and is not correct since our write should arrive in RAID1 METADATA chunk.
In that case, RAID1* is pretty simple, every mirror is the a full copy of each other, no striping/rotation.
Thus in that block group offset of 3M writes, we should write into both mirrors:
physical_address = [physical stripe start] + [offset inside bg]
Thus the result should be:
Mirror 1 [devid 2] physical address = 2425356288 + 3m Mirror 2 [devid 1] physical address = 2446327808 + 3m.
Quoted 7 lines
1351614464 is the address of the stripe 0 of the data chunk. It is completely unclear whether it is intentional or not.
Nor does it explain how the device extent (physical stripe) is selected and how it jumps from the
block_group_offsetto the (physical) stripe number.
For RAID0 the whole situation is a little complex, but still easy to understand.
Firstly for a RAID0 chunk, they are split into 64K length stripes, and each 64K stripe are spread into each device.
If we have a RAID0 chunk with 2 devices, just like the data chunk example:
Off inside bg 0 +64K +128K +192K
| Stripe 0 | Stripe 1 | Stripe 2 | ...Then Stripe 0 would be at the first dev extent of that data chunk, with offset 0 to the dev extent (devid 2 physical 1351614464 + offset 0) Stripe 1 would be at the second dev extent, with offset 0 to the dev extent. (devid 1 physical 1372585984 + offset 0).
And for stripe 2, it would be at the first dev extent again, but offset 64K to the dev extent.
So for the bg offset 1m write for the RAID0 data chunk, it would be at:
1) stripe_nr = bg_offset / stripe_length
1M / 64K = 16
2) Choose which dev-extent to be write into:
stripe_index = (bg_off / stripe_len) % nr_dev
( 1M / 64K ) % 2 = 0
Thus we choose the dev stripe 0 ( devid 2 offset 1351614464) of that data chunk.
3) Final physical offset
physical_off = dev_extent_off + offset_in_stripe + skipped_physical
= dev_extnet_off + (bg_off & stripe_mask) +
stripe_nr / nr_dev * stripe_len
= 1351614464 + (1M & (64K - 1)) + 16 / 2 * 64K
= 1351614464 + 0 + 8 * 64KRemember, all these calculation is the same for regular RAID0.
For RAID10, it's RAID1 for each RAID0 stripe.
Just make above nr_dev to be (nr_dev / 2).
In btrfs' case, we use sub_stripe to distinguish the calculation. For RAID10, sub_stripe would always be 2, and RAID0 would always have sub_stripe as 1.
Thus above nr_dev can be replaced to (nr_dev / sub_stripes), and then can cover both RAID0 and RAID10.
Quoted 4 lines
Intermixing "chunk" and "block group" does not help in understanding it either.
And I suspect RAID5/6 is something entirely different ...
RAID5/6 is mostly based on RAID0, but with more rotation involved, thus more complex.
I can explain RAID56 in more details, if you can grasp the RAID0 and RAID1, and RAID10 part first.
And RAID0 behavior are shared between LVM striped/dm-raid0/btrfs RAID0, following the same behavior (IIRC).
The same for RAID1, among LVM mirrored/dm-raid1/btrfs RAID1.
Thanks,
Qu