How to dump/find parity of RAID-5 file?

DISCUSSION Lakshmipathi.G 2 participants 7 messages Feb 3, 2017 – Apr 17, 2018 1 message not in the archive Btrfs file system

lore

Share & tools

lore

Lakshmipathi.G

author

2017-02-03 10:45 UTC #0 lore raw

Hi.

Came across this thread https://www.mail-archive.com/[email protected]/msg55161.html
Exploring possibility of adding test-scripts around these area using dump-tree & corrupt-block.But unable to figure-out how to get parity of file or find its location. dump-tree output gave,

    item 5 key (FIRST_CHUNK_TREE CHUNK_ITEM 145096704) itemoff 15557 itemsize 144
        length 134217728 owner 2 stripe_len 65536 type DATA|RAID5
        io_align 65536 io_width 65536 sector_size 4096
        num_stripes 3 sub_stripes 0
            stripe 0 devid 3 offset 63111168                 # Is this parity?Seems empty?
            dev_uuid f62df114-186c-4e48-8152-9ed15aa078b4
            stripe 1 devid 2 offset 63111168                 # Contains file data-stripe-1
            dev_uuid c0aeaab0-e57e-4f7a-9356-db1878876d9f
            stripe 2 devid 1 offset 83034112                 # Contains file data-stripe-2
            dev_uuid 637b3666-9d8f-4ec4-9969-53b0b933b9b1

thanks.

Cheers.
Lakshmipathi.G

Goffredo Baroncelli

2017-02-06 20:49 UTC #1 lore raw

Quoted 16 lines · Lakshmipathi.G

Hi.

    item 5 key (FIRST_CHUNK_TREE CHUNK_ITEM 145096704) itemoff 15557 itemsize 144
        length 134217728 owner 2 stripe_len 65536 type DATA|RAID5
        io_align 65536 io_width 65536 sector_size 4096
        num_stripes 3 sub_stripes 0
            stripe 0 devid 3 offset 63111168                 # Is this parity?Seems empty?
            dev_uuid f62df114-186c-4e48-8152-9ed15aa078b4
            stripe 1 devid 2 offset 63111168                 # Contains file data-stripe-1
            dev_uuid c0aeaab0-e57e-4f7a-9356-db1878876d9f
            stripe 2 devid 1 offset 83034112                 # Contains file data-stripe-2
            dev_uuid 637b3666-9d8f-4ec4-9969-53b0b933b9b1

Quoted 1 line

thanks.

IIRC, the parity is spread across the disk stripes of the chunk.

So first you have to find the logical-offset [LO] where the the file begins. Then you have to map this offset to the chunk which holds the data. The chunk has the following info:
- chunk start [CS], chunk length [CL]
- for each stripe:
where the stripe starts

If you subtract the chunk-start from the logical-offset [ CO == LO-CS], you will find the offset where the data belongs in the chunk.

As stated above, the PARITY is spread across the chunk stripes. So (supposing that the stripe size is 64K, the raid level is 5, the disks are three),

- the first 64k of stripe 0, is data [0..64K)
- the first 64k of stripe 1, is data [64..128K)
- the first 64k of stripe 2 is parity,

- the 2nd 64k of stripe 0 is parity,
- the 2nd 64k of stripe 1, is data [128..196K)
- the 2nd 64k of stripe 2, is data [192..256K)

- the 3rd 64k of stripe 0, is data [256..320K)
- the 3rd 64k of stripe 1 is parity,
- the 3rd 64k of stripe 2, is data [320..384K)
and so on,

To find the data, You have to compare the CO to the data [...) range.

If you look to an my old patch (unfinished :-( ), you can find some example to dump the different stripe

[BTRFS-PROGS][PATCH][V2] Add two new commands: 'btrfs insp physical-find' and 'btrfs insp physical-dump'

Quoted 7 lines

Cheers.
Lakshmipathi.G
--
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

Signature · 2 lines

gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Lakshmipathi.G

author

2017-02-14 20:10 UTC #2 lore raw

Quoted 25 lines · Goffredo Baroncelli

IIRC, the parity is spread across the disk stripes of the chunk.
So first you have to find the logical-offset [LO] where the the file begins. Then you have to map this offset to the chunk which holds the data. The chunk has the following info:
- chunk start [CS], chunk length [CL]
- for each stripe:
where the stripe starts
If you subtract the chunk-start from the logical-offset [ CO == LO-CS], you will find the offset where the data belongs in the chunk.
As stated above, the PARITY is spread across the chunk stripes. So (supposing that the stripe size is 64K, the raid level is 5, the disks are three),
- the first 64k of stripe 0, is data [0..64K)
- the first 64k of stripe 1, is data [64..128K)
- the first 64k of stripe 2 is parity,
- the 2nd 64k of stripe 0 is parity,
- the 2nd 64k of stripe 1, is data [128..196K)
- the 2nd 64k of stripe 2, is data [192..256K)
- the 3rd 64k of stripe 0, is data [256..320K)
- the 3rd 64k of stripe 1 is parity,
- the 3rd 64k of stripe 2, is data [320..384K)
and so on,

Quoted 7 lines

To find the data, You have to compare the CO to the data [...) range.
If you look to an my old patch (unfinished :-( ), you can find some example to dump the different stripe
[BTRFS-PROGS][PATCH][V2] Add two new commands: 'btrfs insp physical-find' and 'btrfs insp physical-dump'

Sorry for the delay, I was offline. Thanks for the details. I can understood "partiy spread across the chunk stripes" part. But unable to figure-out the first part regarding calculations.

Raid5 With 3-devices each 512MB. Create single 128KB file("print 'Ab'+'a'*65534+'aB'+'b'*65533"). 'debug-tree' shows chunk tree as:

	item 5 key (FIRST_CHUNK_TREE CHUNK_ITEM 145096704) itemoff 15557 itemsize 144
		length 134217728 owner 2 stripe_len 65536 type DATA|RAID5
		io_align 65536 io_width 65536 sector_size 4096
		num_stripes 3 sub_stripes 0
			stripe 0 devid 3 offset 63111168
			dev_uuid 9a2a18f1-6193-44b9-aafc-23d161d66110
			stripe 1 devid 2 offset 63111168
			dev_uuid e45ab907-c3a8-4dff-af9f-2ae5fd38ffd6
			stripe 2 devid 1 offset 83034112
			dev_uuid 428c04d9-37da-454a-b7b2-f6fe88580de2

and fs-tree shows:
item 13 key (145227776 EXTENT_ITEM 131072) itemoff 15788 itemsize 53
extent refs 1 gen 7 flags DATA
extent data backref root 5 objectid 257 offset 0 count 1

Quoted 1 line

From above, I assume:

LO=145227776 CS=145096704 and CL=134217728
CO=145227776 - 145096704 => CO = 131072

Quite confused from here :s I'll look into your patches to understand more. I hope sometime in future we will have your finished patches :) 'physical-find' and 'physical-find' commands will be really useful for debugging/testing and learning purposes. thanks.

Cheers.
Lakshmipathi.G

Goffredo Baroncelli

2017-02-15 18:25 UTC #3 lore raw

Quoted 53 lines · Lakshmipathi.G

Quoted 25 lines · Goffredo Baroncelli
IIRC, the parity is spread across the disk stripes of the chunk.
So first you have to find the logical-offset [LO] where the the file begins. Then you have to map this offset to the chunk which holds the data. The chunk has the following info:
- chunk start [CS], chunk length [CL]
- for each stripe:
where the stripe starts
If you subtract the chunk-start from the logical-offset [ CO == LO-CS], you will find the offset where the data belongs in the chunk.
As stated above, the PARITY is spread across the chunk stripes. So (supposing that the stripe size is 64K, the raid level is 5, the disks are three),
- the first 64k of stripe 0, is data [0..64K)
- the first 64k of stripe 1, is data [64..128K)
- the first 64k of stripe 2 is parity,
- the 2nd 64k of stripe 0 is parity,
- the 2nd 64k of stripe 1, is data [128..196K)
- the 2nd 64k of stripe 2, is data [192..256K)
- the 3rd 64k of stripe 0, is data [256..320K)
- the 3rd 64k of stripe 1 is parity,
- the 3rd 64k of stripe 2, is data [320..384K)
and so on,
Quoted 7 lines
To find the data, You have to compare the CO to the data [...) range.
If you look to an my old patch (unfinished :-( ), you can find some example to dump the different stripe
[BTRFS-PROGS][PATCH][V2] Add two new commands: 'btrfs insp physical-find' and 'btrfs insp physical-dump'
Sorry for the delay, I was offline. Thanks for the details. I can understood "partiy spread across the chunk stripes" part. But unable to figure-out the first part regarding calculations.
Raid5 With 3-devices each 512MB. Create single 128KB file("print 'Ab'+'a'*65534+'aB'+'b'*65533"). 'debug-tree' shows chunk tree as:
	item 5 key (FIRST_CHUNK_TREE CHUNK_ITEM 145096704) itemoff 15557 itemsize 144
		length 134217728 owner 2 stripe_len 65536 type DATA|RAID5
		io_align 65536 io_width 65536 sector_size 4096
		num_stripes 3 sub_stripes 0
			stripe 0 devid 3 offset 63111168
			dev_uuid 9a2a18f1-6193-44b9-aafc-23d161d66110
			stripe 1 devid 2 offset 63111168
			dev_uuid e45ab907-c3a8-4dff-af9f-2ae5fd38ffd6
			stripe 2 devid 1 offset 83034112
			dev_uuid 428c04d9-37da-454a-b7b2-f6fe88580de2
and fs-tree shows:
item 13 key (145227776 EXTENT_ITEM 131072) itemoff 15788 itemsize 53
extent refs 1 gen 7 flags DATA
extent data backref root 5 objectid 257 offset 0 count 1

Quoted 7 lines

Quoted 1 line
From above, I assume:
LO=145227776 CS=145096704 and CL=134217728
CO=145227776 - 145096704 => CO = 131072
Quite confused from here :s I'll look into your patches to understand more. I hope sometime in future we will have your finished patches :) 'physical-find' and 'physical-find' commands will be really useful for debugging/testing and learning purposes. thanks.

The chunk-tree maps the logical address [145096704...145096704+134217728) [size=128MB] to the physical ones

	devid3 : [63111168..63111168+67108864) [size=64MB]
	devid1 : [63111168..63111168+67108864) [size=64MB]
	devid2 : [83034112..83034112+67108864) [size=64MB]

So because the logical address is divided in pieces of 64k, interleaved by the parity, we know that:
* first 128kb

logical address [145096704      ..145096704+64k)   -> devid1, [63111168    ..63111168+64k)
logical address [145096704+64k  ..145096704+2x64k) -> devid2, [83034112    ..83034112+64k)
                parity:                            -> devid3, [63111168    ..63111168+64k)
* second 128kb
logical address [145096704+2x64k..145096704+3x64k) -> devid2, [83034112+64k..83034112+2x64k)
logical address [145096704+3x64k..145096704+4x64k) -> devid3, [63111168+64k..63111168+2x64k)
                parity:                            -> devid1, [63111168+64k..63111168+2x64k)

And so on...

(NB: 145096704+2x64k == 145227776)

The fs-tree, maps the file content [0..131072) [size=128k] to the logical address [145227776..145227776+131072) [size=128k]

So the file content is stored starting from the disk devid2, at 83034112+64k=83099648 (first 64k). The second 64k is placed in disk devid3 at 63111168+64k=63176704; the parity is stored at disk1, 63111168+64k = 63176704

BR
G.Baroncelli

Quoted 4 lines

Cheers.
Lakshmipathi.G

Signature · 2 lines

gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

Lakshmipathi.G

author

2017-02-16 15:15 UTC #4 lore raw

Quoted 18 lines · Goffredo Baroncelli

The chunk-tree maps the logical address [145096704...145096704+134217728) [size=128MB] to the physical ones

	devid3 : [63111168..63111168+67108864) [size=64MB]
	devid1 : [63111168..63111168+67108864) [size=64MB]
	devid2 : [83034112..83034112+67108864) [size=64MB]

So because the logical address is divided in pieces of 64k, interleaved by the parity, we know that:
* first 128kb

logical address [145096704      ..145096704+64k)   -> devid1, [63111168    ..63111168+64k)
logical address [145096704+64k  ..145096704+2x64k) -> devid2, [83034112    ..83034112+64k)
                parity:                            -> devid3, [63111168    ..63111168+64k)
* second 128kb
logical address [145096704+2x64k..145096704+3x64k) -> devid2, [83034112+64k..83034112+2x64k)
logical address [145096704+3x64k..145096704+4x64k) -> devid3, [63111168+64k..63111168+2x64k)
                parity:                            -> devid1, [63111168+64k..63111168+2x64k)

And so on...

(NB: 145096704+2x64k == 145227776)

Quoted 8 lines

The fs-tree, maps the file content [0..131072) [size=128k] to the logical address [145227776..145227776+131072) [size=128k]
So the file content is stored starting from the disk devid2, at 83034112+64k=83099648 (first 64k). The second 64k is placed in disk devid3 at 63111168+64k=63176704; the parity is stored at disk1, 63111168+64k = 63176704
BR
G.Baroncelli

Thanks for the detailed example with exact numbers. Now understood the address mapping better. With this as a reference, I think it should be possible to access parity/data-stripes more sensible manner instead using expensive "cat /device/ | hexdump | grep" combination. thanks.

Cheers.
Lakshmipathi.G

Goffredo Baroncelli

2018-04-17 19:20 UTC #5 lore raw

In reply to Goffredo Baroncelli

Quoted 34 lines · Goffredo Baroncelli

Quoted 16 lines · Lakshmipathi.G
Hi.
Came across this thread https://www.mail-archive.com/[email protected]/msg55161.html
Exploring possibility of adding test-scripts around these area using dump-tree & corrupt-block.But unable to figure-out how to get parity of file or find its location. dump-tree output gave,
    item 5 key (FIRST_CHUNK_TREE CHUNK_ITEM 145096704) itemoff 15557 itemsize 144
        length 134217728 owner 2 stripe_len 65536 type DATA|RAID5
        io_align 65536 io_width 65536 sector_size 4096
        num_stripes 3 sub_stripes 0
            stripe 0 devid 3 offset 63111168                 # Is this parity?Seems empty?
            dev_uuid f62df114-186c-4e48-8152-9ed15aa078b4
            stripe 1 devid 2 offset 63111168                 # Contains file data-stripe-1
            dev_uuid c0aeaab0-e57e-4f7a-9356-db1878876d9f
            stripe 2 devid 1 offset 83034112                 # Contains file data-stripe-2
            dev_uuid 637b3666-9d8f-4ec4-9969-53b0b933b9b1
Quoted 1 line
thanks.
IIRC, the parity is spread across the disk stripes of the chunk.
So first you have to find the logical-offset [LO] where the the file begins. Then you have to map this offset to the chunk which holds the data. The chunk has the following info:
- chunk start [CS], chunk length [CL]
- for each stripe:
where the stripe starts
If you subtract the chunk-start from the logical-offset [ CO == LO-CS], you will find the offset where the data belongs in the chunk.
As stated above, the PARITY is spread across the chunk stripes. So (supposing that the stripe size is 64K, the raid level is 5, the disks are three),
- the first 64k of stripe 0, is data [0..64K)
- the first 64k of stripe 1, is data [64..128K)
- the first 64k of stripe 2 is parity,

Quoted 8 lines

- the 2nd 64k of stripe 0 is parity,
- the 2nd 64k of stripe 1, is data [128..196K)
- the 2nd 64k of stripe 2, is data [192..256K)
- the 3rd 64k of stripe 0, is data [256..320K)
- the 3rd 64k of stripe 1 is parity,
- the 3rd 64k of stripe 2, is data [320..384K)
and so on,

I was wrong !
- the 3rd 64k of stripe 0, is data [320..384K)
- the 3rd 64k of stripe 1 is parity,
- the 3rd 64k of stripe 2, is data [256..320K)

Basically stripe 0 and 2 were swapped. The idea is that after parity there is stripe 1, then stripe 2, and so on ....

D    D    D
I    I    I
S    S    S
K    K    K
1    2    3

0    1    P     
P    2    3     
5    P    4     
6    7    P

Where
P = parity
0...7 are the slices of data

So 'P' parity move from left to right starting from the last disk; the data are in the increasing address from left to right *starting* from parity in a circular buffer.

I am trying to implement raid5/6 in grub, so I went deep in the raid5 layout

BR
G.Baroncelli

Quoted 21 lines

To find the data, You have to compare the CO to the data [...) range.
If you look to an my old patch (unfinished :-( ), you can find some example to dump the different stripe
[BTRFS-PROGS][PATCH][V2] Add two new commands: 'btrfs insp physical-find' and 'btrfs insp physical-dump'
Quoted 7 lines
Cheers.
Lakshmipathi.G
--
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

Signature · 2 lines

gpg @keyserver.linux.it: Goffredo Baroncelli <kreijackATinwind.it>
Key fingerprint BBF5 1610 0B64 DAC6 5F7D  17B2 0EDA 9B37 8B82 E0B5

A message that is not in the archive (sent off-list or not yet received): [email protected]

Lakshmipathi.G

author

2017-02-14 20:07 UTC #7 lore raw

Quoted 17 lines · Qu Wenruo

Please note the following things when calculating RAID5/6 data and P/Q location:
1) Basic layout
The chunk stripe only shows the *first* full stripe layout. And it always follows the sequence of "Data0, Data1, ... Data N, Parity"
And one full stripe is consistent of N * 64K (fixed yet).
2) Device rotation
RAID5/6 do device rotation.
So the *second* full stripe will have the following layout:
"Data 1, Data2, ... Data N, Parity, Data 0"

Quoted 7 lines

You can refer to my offline-scrub patchset to see how it assemble the RAID5/6 mapping, which I believe it is easier than current btrfs_map_block() implementation.
[PATCH v2 19/19] btrfs-progs: fsck: Introduce offline scrub function
Thanks,
Qu

Sorry for the delay in response, I was offline. Thanks for the details. I think now I have better idea about (1)Basic layout and (2)Device rotation. Will look into offline-scrub patches to explore more about exact mapping and on-disk layouts. I'm trying to understand layout for simple Raid-5 with 3-drives with 128KB file-size. Will try to understand Raid-6 little later. thanks.

Cheers.
Lakshmipathi.G