Tree fragmentation and prefetching
While looking into the performance of scrub I noticed that a significant amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to improve on it.
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.
a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324s
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7s
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, filled 28%. It is created with the current git tree + the round robin patch and filled with
fs_mark -D 512 -t 16 -n 4096 -F -S0
The 'normal' read is done by enumerating the leaves by btrfs_next_leaf() with path->reada=2. Both trees are being enumerated one after the other. The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This will probably add some overhead. It also does not check the crcs.
While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, deletion of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(struct btrfs_root *root,
struct btrfs_key *start, struct btrfs_key *end, struct btrfs_reada_ctx *reada);
void btrfs_readahead_wait(struct btrfs_reada_ctx *reada);
to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.
--
Arne
Quoted 8 lines · Arne Jansen
While looking into the performance of scrub I noticed that a significant amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to improve on it.
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.
Quoted 6 lines
a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140sreading both trees: 324s
sorry, the number is wrong, it should be 384s (just the sum of both ./. rounding errors).
Quoted 58 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7sThe test setup consists of a 7 Seagate ES.2 1TB disks filesystem, filled 28%. It is created with the current git tree + the round robin patch and filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by
btrfs_next_leaf()with path->reada=2. Both trees are being enumerated one after the other. The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This will probably add some overhead. It also does not check the crcs.While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, deletion of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
structbtrfs_key*start, structbtrfs_key*end, structbtrfs_reada_ctx*reada);
voidbtrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.--
Arne--
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
Quoted 1 line · Arne Jansen
While looking into the performance of scrub I noticed that a signific=
ant
Quoted 2 lines
amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to impr=
ove
Quoted 2 lines
on it.
The main idea is to load the tree (or parts of it) top-down, order th=
e
Quoted 8 lines
needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=3D2
=C2=A0 reading extent tree: 242s
=C2=A0 reading csum tree: 140s
=C2=A0 reading both trees: 324s
Quoted 4 lines
b) prefetch prototype
=C2=A0 reading extent tree: 23.5s
=C2=A0 reading csum tree: 20.4s
=C2=A0 reading both trees: 25.7s
10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Regards,
Andrey
Quoted 2 lines
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, fil=
led
Quoted 1 line
28%. It is created with the current git tree + the round robin patch =
and
Quoted 5 lines
filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by btrfs_next_lea=
f()
Quoted 1 line
with path->reada=3D2. Both trees are being enumerated one after the o=
ther.
Quoted 2 lines
The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This wil=
l
Quoted 5 lines
probably add some overhead. It also does not check the crcs.
While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, delet=
ion
Quoted 7 lines
of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_key *start,
Quoted 1 line
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_key *end,
Quoted 1 line
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_reada_ctx *reada);
Quoted 6 lines
void
btrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Quoted 6 lines
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
For the implementation I'd need an interface which I haven't been abl=
e
Quoted 2 lines
to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need wou=
ld
Quoted 1 line
be an interface that gives me a callback on each completion or a wait=
ing
Quoted 11 lines
function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.--
Arne--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs=
" in
Quoted 2 lines
the body of a message to [email protected]
More majordomo info at =C2=A0http://vger.kernel.org/majordomo-info.ht=
ml
Quoted 1 line
--
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
Quoted 19 lines · Andrey Kuzmin
Quoted 13 lines · Arne Jansen
While looking into the performance of scrub I noticed that a significant amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to improve on it.
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324sQuoted 4 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7s
Quoted 4 lines
10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Yes. Leaves and the intermediate nodes tend to be quite scattered around the disk with respect to their logical order. Reading them in logical (ascending/descending) order require lots of seeks.
Quoted 62 lines
Regards,
AndreyQuoted 45 lines
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, filled 28%. It is created with the current git tree + the round robin patch and filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by
btrfs_next_leaf()with path->reada=2. Both trees are being enumerated one after the other. The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This will probably add some overhead. It also does not check the crcs.While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, deletion of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
structbtrfs_key*start, structbtrfs_key*end, structbtrfs_reada_ctx*reada);
voidbtrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.Quoted 9 lines
--
Arne--
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--
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
Quoted 3 lines · Arne Jansen
Quoted 2 lines · Andrey Kuzmin
On Wed, Mar 23, 2011 at 4:06 PM, Arne Jansen<[email protected]> =C2=A0=
Quoted 2 lines · wrote:
Quoted 2 lines
Quoted 2 lines
While looking into the performance of scrub I noticed that a signif=
icant
Quoted 1 line
Quoted 1 line
Quoted 1 line
amount of time is being used for loading the extent tree and the cs=
um
Quoted 1 line
Quoted 1 line
Quoted 1 line
tree. While this is no surprise I did some prototyping on how to im=
prove
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
on it.
The main idea is to load the tree (or parts of it) top-down, order =
the
Quoted 18 lines
Quoted 13 lines
Quoted 8 lines
needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=3D2
=C2=A0 reading extent tree: 242s
=C2=A0 reading csum tree: 140s
=C2=A0 reading both trees: 324sQuoted 4 lines
b) prefetch prototype
=C2=A0 reading extent tree: 23.5s
=C2=A0 reading csum tree: 20.4s
=C2=A0 reading both trees: 25.7sQuoted 4 lines
10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Quoted 4 lines
Yes. Leaves and the intermediate nodes tend to be quite scattered around the disk with respect to their logical order. Reading them in logical (ascending/descending) order require lots of seeks.
And the patch actually does on-the-fly defragmentation, right? Why loose it then :)?
Regards,
Andrey
Quoted 7 lines
Quoted 7 lines
Regards,
AndreyQuoted 2 lines
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, f=
illed
Quoted 1 line
Quoted 1 line
Quoted 1 line
28%. It is created with the current git tree + the round robin patc=
h and
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by btrfs_next_l=
eaf()
Quoted 1 line
Quoted 1 line
Quoted 1 line
with path->reada=3D2. Both trees are being enumerated one after the=
other.
Quoted 1 line
Quoted 1 line
Quoted 1 line
The prototype currently just uses raw bios, does not make use of th=
e
Quoted 1 line
Quoted 1 line
Quoted 1 line
page cache and does not enter the read pages into the cache. This w=
ill
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
probably add some overhead. It also does not check the crcs.
While it is very promising to implement it for scrub, I think a mor=
e
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, del=
etion
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_key *start,
Quoted 1 line
Quoted 1 line
Quoted 1 line
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_key *end,
Quoted 1 line
Quoted 1 line
Quoted 1 line
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0struct btrfs_reada_ctx *reada);
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
void
btrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fix=
ed
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
start/end range.
For the implementation I'd need an interface which I haven't been a=
ble
Quoted 1 line
Quoted 1 line
Quoted 1 line
to find yet. Currently I can trigger the read of several pages / tr=
ee
Quoted 1 line
Quoted 1 line
Quoted 1 line
blocks and wait for the completion of each of them. What I'd need w=
ould
Quoted 1 line
Quoted 1 line
Quoted 1 line
be an interface that gives me a callback on each completion or a wa=
iting
Quoted 1 line
Quoted 1 line
Quoted 1 line
function that wakes up on each completion with the information whic=
h
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
pages just completed.
One way to achieve this would be to add a hook, but I gladly take a=
ny
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
implementation hints.
--
Arne--
To unsubscribe from this list: send the line "unsubscribe linux-btr=
fs" in
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
the body of a message to [email protected]
More majordomo info at =C2=A0http://vger.kernel.org/majordomo-info.=
html
Quoted 3 lines
Quoted 3 lines
Quoted 1 line
--
To unsubscribe from this list: send the line "unsubscribe linux-btrf=
s" in
Quoted 2 lines
Quoted 2 lines
the body of a message to [email protected]
More majordomo info at =C2=A0http://vger.kernel.org/majordomo-info.h=
tml
Quoted 2 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
Quoted 25 lines · Arne Jansen
Quoted 19 lines · Andrey Kuzmin
Quoted 13 lines · Arne Jansen
While looking into the performance of scrub I noticed that a significant amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to improve on it.
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324sQuoted 4 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7sQuoted 4 lines
10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Quoted 4 lines
Yes. Leaves and the intermediate nodes tend to be quite scattered around the disk with respect to their logical order. Reading them in logical (ascending/descending) order require lots of seeks.
I'm also dealing with tree fragmentation problem, I try to store the leaves which have the same parent closely.
Regards
Miao
Quoted 69 lines
Quoted 63 lines
Regards,
AndreyQuoted 54 lines
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, filled 28%. It is created with the current git tree + the round robin patch and filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by
btrfs_next_leaf()with path->reada=2. Both trees are being enumerated one after the other. The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This will probably add some overhead. It also does not check the crcs.While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, deletion of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
structbtrfs_key*start, structbtrfs_key*end, structbtrfs_reada_ctx*reada);
voidbtrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.Signature · 7 lines
Arne -- 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.htmlSignature · 3 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.htmlSignature · 3 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
Quoted 22 lines · Miao Xie
Quoted 21 lines · Arne Jansen
Quoted 19 lines · Andrey Kuzmin
Quoted 9 lines · Arne Jansen
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324sQuoted 4 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7s10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Quoted 7 lines
Quoted 4 lines
Yes. Leaves and the intermediate nodes tend to be quite scattered around the disk with respect to their logical order. Reading them in logical (ascending/descending) order require lots of seeks.
I'm also dealing with tree fragmentation problem, I try to store the leaves which have the same parent closely.
That's good to hear. Do you have already anything I can repeat the test with?
-Arne
Quoted 4 lines
Regards
Miao
Quoted 28 lines · Arne Jansen
Quoted 27 lines · Miao Xie
Quoted 25 lines · Arne Jansen
Quoted 15 lines · Andrey Kuzmin
Quoted 9 lines · Arne Jansen
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324sQuoted 4 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7sQuoted 4 lines
10x speed-up looks indeed impressive. Just for me to be sure, did I get you right in that you attribute this effect specifically to enumerating tree leaves in key address vs. disk addresses when these two are not aligned?
Yes. Leaves and the intermediate nodes tend to be quite scattered around the disk with respect to their logical order. Reading them in logical (ascending/descending) order require lots of seeks.
Quoted 5 lines
Quoted 2 lines
I'm also dealing with tree fragmentation problem, I try to store the leaves which have the same parent closely.
That's good to hear. Do you have already anything I can repeat the test with?
It is still under developing.;)
Thanks
Miao
Quoted 11 lines
-Arne
Quoted 4 lines
Regards
Miao--
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
Excerpts from Arne Jansen's message of 2011-03-23 09:06:02 -0400:
Quoted 13 lines
While looking into the performance of scrub I noticed that a significant amount of time is being used for loading the extent tree and the csum tree. While this is no surprise I did some prototyping on how to improve on it.
The main idea is to load the tree (or parts of it) top-down, order the needed blocks and distribute it over all disks.
To keep you interested, some results first.a) by tree enumeration with reada=2
reading extent tree: 242s
reading csum tree: 140s
reading both trees: 324s
Quoted 4 lines
b) prefetch prototype
reading extent tree: 23.5s
reading csum tree: 20.4s
reading both trees: 25.7s
Very nice, btrfsck does something similar.
Quoted 36 lines
The test setup consists of a 7 Seagate ES.2 1TB disks filesystem, filled 28%. It is created with the current git tree + the round robin patch and filled with
fs_mark-D 512 -t 16 -n 4096 -F -S0The 'normal' read is done by enumerating the leaves by
btrfs_next_leaf()with path->reada=2. Both trees are being enumerated one after the other. The prototype currently just uses raw bios, does not make use of the page cache and does not enter the read pages into the cache. This will probably add some overhead. It also does not check the crcs.While it is very promising to implement it for scrub, I think a more general interface which can be used for every enumeration would be beneficial. Use cases that come to mind are rebalance, reflink, deletion of large files, listing of large directories etc..
I'd imagine an interface along the lines of
int
btrfs_readahead_init(struct btrfs_reada_ctx *reada); int btrfs_readahead_add(structbtrfs_root*root,
structbtrfs_key*start, structbtrfs_key*end, structbtrfs_reada_ctx*reada);
voidbtrfs_readahead_wait(struct btrfs_reada_ctx *reada);to trigger the readahead of parts of a tree. Multiple readahead requests can be given before waiting. This would enable the very beneficial folding seen above for 'reading both trees'.
Also it would be possible to add a cascading readahead, where the content of leaves would trigger readaheads in other trees, maybe by giving a callback for the decisions what to read instead of the fixed start/end range.
Quoted 8 lines
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.
We have the bio endio call backs for this, I think that's the only thing you can use.
-chris
Quoted 11 lines · Chris Mason
Excerpts from Arne Jansen's message of 2011-03-23 09:06:02 -0400:
Quoted 9 lines
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.
Quoted 3 lines
We have the bio endio call backs for this, I think that's the only thing you can use.
ok, so I'll add a new extent state bit EXTENT_READAHEAD and test for it in btree_readpage_end_io_hook.
Excerpts from Arne Jansen's message of 2011-03-25 16:14:35 -0400:
Quoted 12 lines · Chris Mason
Quoted 11 lines
Excerpts from Arne Jansen's message of 2011-03-23 09:06:02 -0400:
Quoted 9 lines
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.
Quoted 6 lines
Quoted 3 lines
We have the bio endio call backs for this, I think that's the only thing you can use.
ok, so I'll add a new extent state bit
EXTENT_READAHEADand test for it inbtree_readpage_end_io_hook.
It's also common to use a chain of endio handlers. If you're allocating any state for the RA, you just save the original endio handler in your new struct, and then use your own endio handler that does the readahead smarts.
-chris
Quoted 17 lines · Chris Mason
Excerpts from Arne Jansen's message of 2011-03-25 16:14:35 -0400:
Quoted 16 lines · Chris Mason
Quoted 14 lines
Excerpts from Arne Jansen's message of 2011-03-23 09:06:02 -0400:
Quoted 9 lines
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.We have the bio endio call backs for this, I think that's the only thing you can use.
Quoted 8 lines
Quoted 2 lines
ok, so I'll add a new extent state bit
EXTENT_READAHEADand test for it inbtree_readpage_end_io_hook.It's also common to use a chain of endio handlers. If you're allocating any state for the RA, you just save the original endio handler in your new struct, and then use your own endio handler that does the readahead smarts.
Do you mean replacing the bio end_io handler or the readpage_end_io_hook? As I want the pages to end up in the page cache, I'd like to use as much of the existing infrastructure as possible. To intercept the bio deep down in the chain would mean to duplicate some code on the way down and on the way up again.
-Arne
Excerpts from Arne Jansen's message of 2011-03-25 16:53:24 -0400:
Quoted 27 lines · Chris Mason
Quoted 17 lines
Excerpts from Arne Jansen's message of 2011-03-25 16:14:35 -0400:
Quoted 16 lines · Chris Mason
Quoted 14 lines
Excerpts from Arne Jansen's message of 2011-03-23 09:06:02 -0400:
Quoted 9 lines
For the implementation I'd need an interface which I haven't been able to find yet. Currently I can trigger the read of several pages / tree blocks and wait for the completion of each of them. What I'd need would be an interface that gives me a callback on each completion or a waiting function that wakes up on each completion with the information which pages just completed.
One way to achieve this would be to add a hook, but I gladly take any implementation hints.We have the bio endio call backs for this, I think that's the only thing you can use.
Quoted 8 lines
Quoted 2 lines
ok, so I'll add a new extent state bit
EXTENT_READAHEADand test for it inbtree_readpage_end_io_hook.It's also common to use a chain of endio handlers. If you're allocating any state for the RA, you just save the original endio handler in your new struct, and then use your own endio handler that does the readahead smarts.
Quoted 5 lines
Do you mean replacing the bio
end_iohandler or thereadpage_end_io_hook? As I want the pages to end up in the page cache, I'd like to use as much of the existing infrastructure as possible. To intercept the bio deep down in the chain would mean to duplicate some code on the way down and on the way up again.
The end_io handler, see how we chain them around for the crc helper threads.
-chris