| Message ID | 1367801267-15659-1-git-send-email-bapper@gmail.com |
|---|---|
| State | New, archived |
| Headers | show |
On Mon, May 6, 2013 at 2:47 AM, Brian Pomerantz <bapper@gmail.com> wrote: > After some profiling of the attach process, it was found that > a considerable amount of time was spent spinning through the list of > used PEBs in ubi_attach_fastmap(). This patch converts the list into > a RB tree saving considerable time when the volumes fill up. > > Signed-off-by: Brian Pomerantz <bapper@gmail.com> Nice! Looks good so far, but this week I'm on the road. As soon as I the have time to test it, I'll ack your patch. Do you have some numbers? I'm interested in how much faster the rbtree is compared to list in this case... -- Thanks, //richard
On May 6, 2013, at 6:45 AM, richard -rw- weinberger <richard.weinberger@gmail.com> wrote: > On Mon, May 6, 2013 at 2:47 AM, Brian Pomerantz <bapper@gmail.com> wrote: >> After some profiling of the attach process, it was found that >> a considerable amount of time was spent spinning through the list of >> used PEBs in ubi_attach_fastmap(). This patch converts the list into >> a RB tree saving considerable time when the volumes fill up. >> >> Signed-off-by: Brian Pomerantz <bapper@gmail.com> > > Nice! > Looks good so far, but this week I'm on the road. > As soon as I the have time to test it, I'll ack your patch. > > Do you have some numbers? > I'm interested in how much faster the rbtree is compared to list in this case... > Using a Samsung 1GB NAND with 3958 PEBs and only 510 left available (nearly full), without the patch I get around a 300ms attach time and with the patch it is around 50ms attach time. I made the same change in u-boot, our kernel image is stored in UBI along with a backup image, and saw the same speedup. So I shaved off 500ms from my boot time with the two changes. The attach time should be much more constant using the tree, not getting much longer as the volumes fill up. There wasn't a noticeable difference in how long it took to fill the tree verses appending to a list, so with empty volumes there shouldn't be much overhead. --Brian
On Mon, May 6, 2013 at 5:04 PM, Brian Pomerantz <bapper@gmail.com> wrote: > > On May 6, 2013, at 6:45 AM, richard -rw- weinberger <richard.weinberger@gmail.com> wrote: > >> On Mon, May 6, 2013 at 2:47 AM, Brian Pomerantz <bapper@gmail.com> wrote: >>> After some profiling of the attach process, it was found that >>> a considerable amount of time was spent spinning through the list of >>> used PEBs in ubi_attach_fastmap(). This patch converts the list into >>> a RB tree saving considerable time when the volumes fill up. >>> >>> Signed-off-by: Brian Pomerantz <bapper@gmail.com> >> >> Nice! >> Looks good so far, but this week I'm on the road. >> As soon as I the have time to test it, I'll ack your patch. >> >> Do you have some numbers? >> I'm interested in how much faster the rbtree is compared to list in this case... >> > > Using a Samsung 1GB NAND with 3958 PEBs and only 510 left available (nearly full), without the patch I get around a 300ms attach time and with the patch it is around 50ms attach time. I made the same change in u-boot, our kernel image is stored in UBI along with a backup image, and saw the same speedup. So I shaved off 500ms from my boot time with the two changes. The attach time should be much more constant using the tree, not getting much longer as the volumes fill up. There wasn't a noticeable difference in how long it took to fill the tree verses appending to a list, so with empty volumes there shouldn't be much overhead. Sounds good. :) Did you port fastmap to u-boot? Thanks, //richard
On May 6, 2013, at 8:17 AM, richard -rw- weinberger <richard.weinberger@gmail.com> wrote: > On Mon, May 6, 2013 at 5:04 PM, Brian Pomerantz <bapper@gmail.com> wrote: >> >> On May 6, 2013, at 6:45 AM, richard -rw- weinberger <richard.weinberger@gmail.com> wrote: >> >> Using a Samsung 1GB NAND with 3958 PEBs and only 510 left available (nearly full), without the patch I get around a 300ms attach time and with the patch it is around 50ms attach time. I made the same change in u-boot, our kernel image is stored in UBI along with a backup image, and saw the same speedup. So I shaved off 500ms from my boot time with the two changes. The attach time should be much more constant using the tree, not getting much longer as the volumes fill up. There wasn't a noticeable difference in how long it took to fill the tree verses appending to a list, so with empty volumes there shouldn't be much overhead. > > Sounds good. :) > Did you port fastmap to u-boot? > I didn't, though if it's not upstream then perhaps one of my colleagues did. From what I can tell, it's nearly identical code to what is in the kernel. --Brian
Hi Brian, Nice! Few tiny comments. On Sun, 5 May 2013 17:47:47 -0700 Brian Pomerantz <bapper@gmail.com> wrote: > +/** > + * add_aeb - create and add a attach erase block to a given rb tree root. s/add_aeb/add_aeb_rb/ > + * @ai: UBI attach info object > + * @root: the target rb tree > + * @pnum: PEB number of the new attach erase block > + * @ec: erease counter of the new LEB > + * @scrub: scrub this PEB after attaching > + * > + * Returns 0 on success, < 0 indicates an internal error. > + */ > +static int add_aeb_rb(struct ubi_attach_info *ai, struct rb_root *root, > + int pnum, int ec, int scrub) > +{ > + struct ubi_ainf_peb *aeb; > + struct ubi_ainf_peb *tmp_aeb; > + struct rb_node **p = &root->rb_node, *parent = NULL; > + > + aeb = kmem_cache_alloc(ai->aeb_slab_cache, GFP_KERNEL); > + if (!aeb) > + return -ENOMEM; > + > + aeb->pnum = pnum; > + aeb->ec = ec; > + aeb->lnum = -1; > + aeb->scrub = scrub; > + aeb->copy_flag = aeb->sqnum = 0; > + > + ai->ec_sum += aeb->ec; > + ai->ec_count++; > + > + if (ai->max_ec < aeb->ec) > + ai->max_ec = aeb->ec; > + > + if (ai->min_ec > aeb->ec) > + ai->min_ec = aeb->ec; Up until here, the code is identical to 'add_aeb'. Suggest unify the above 'aeb' construction code. > /** > - * assign_aeb_to_av - assigns a SEB to a given ainf_volume and removes it > - * from it's original list. > + * assign_aeb_to_av - assigns a SEB to a given ainf_volume Maybe comment that 'aeb' should be already unlinked from any prior aeb->u.list or aeb->u.rb? > @@ -726,10 +803,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, > continue; > > aeb = NULL; > - list_for_each_entry(tmp_aeb, &used, u.list) { > - if (tmp_aeb->pnum == pnum) > - aeb = tmp_aeb; > - } > + aeb = find_aeb_in_rb(&used, pnum); The above 'aeb = NULL' is now redundant. From ubi.h, struct ubi_ainf_peb documentation: * @u.rb: link in the per-volume RB-tree of &struct ubi_ainf_peb objects * @u.list: link in one of the eraseblock lists Maybe we should amend the documentation, now that u.rb serves other purposes than the per-volume RB-tree link? Regards, Shmulik
On 05/06/2013 05:27 PM, Brian Pomerantz wrote: >> Did you port fastmap to u-boot? >> > > I didn't, though if it's not upstream then perhaps one of my colleagues > did. From what I can tell, it's nearly identical code to what is in the > kernel. Yes, the UBI code in U-Boot is a slightly modified version of the Linux UBI code. But pretty old (from 2008). And mainline U-Boot UBI currently has no fastmap support. Brian, could you please let me know which U-Boot version you are using? It would be great to see this fastmap support merged back into mainline. Thanks, Stefan
diff --git a/drivers/mtd/ubi/fastmap.c b/drivers/mtd/ubi/fastmap.c index 0648c69..15180c9 100644 --- a/drivers/mtd/ubi/fastmap.c +++ b/drivers/mtd/ubi/fastmap.c @@ -103,6 +103,85 @@ static int add_aeb(struct ubi_attach_info *ai, struct list_head *list, } /** + * find_aeb_in_rb - find an eraseblock in the given rb tree + * @pnum: PEB number of the erase block to find + * @root: tree to search in + * + * Returns struct ubi_ainf_peb of the found erase block on success, NULL if it + * was not found + */ +static struct ubi_ainf_peb *find_aeb_in_rb(struct rb_root *root, + int pnum) +{ + struct ubi_ainf_peb *tmp_aeb; + struct rb_node *node = root->rb_node; + + while (node) { + tmp_aeb = rb_entry(node, struct ubi_ainf_peb, u.rb); + if (pnum < tmp_aeb->pnum) + node = node->rb_left; + else if (pnum > tmp_aeb->pnum) + node = node->rb_right; + else + return tmp_aeb; + } + + return NULL; +} + +/** + * add_aeb - create and add a attach erase block to a given rb tree root. + * @ai: UBI attach info object + * @root: the target rb tree + * @pnum: PEB number of the new attach erase block + * @ec: erease counter of the new LEB + * @scrub: scrub this PEB after attaching + * + * Returns 0 on success, < 0 indicates an internal error. + */ +static int add_aeb_rb(struct ubi_attach_info *ai, struct rb_root *root, + int pnum, int ec, int scrub) +{ + struct ubi_ainf_peb *aeb; + struct ubi_ainf_peb *tmp_aeb; + struct rb_node **p = &root->rb_node, *parent = NULL; + + aeb = kmem_cache_alloc(ai->aeb_slab_cache, GFP_KERNEL); + if (!aeb) + return -ENOMEM; + + aeb->pnum = pnum; + aeb->ec = ec; + aeb->lnum = -1; + aeb->scrub = scrub; + aeb->copy_flag = aeb->sqnum = 0; + + ai->ec_sum += aeb->ec; + ai->ec_count++; + + if (ai->max_ec < aeb->ec) + ai->max_ec = aeb->ec; + + if (ai->min_ec > aeb->ec) + ai->min_ec = aeb->ec; + + while (*p) { + parent = *p; + + tmp_aeb = rb_entry(parent, struct ubi_ainf_peb, u.rb); + if (aeb->pnum < tmp_aeb->pnum) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + + rb_link_node(&aeb->u.rb, parent, p); + rb_insert_color(&aeb->u.rb, root); + + return 0; +} + +/** * add_vol - create and add a new volume to ubi_attach_info. * @ai: ubi_attach_info object * @vol_id: VID of the new volume @@ -154,8 +233,7 @@ out: } /** - * assign_aeb_to_av - assigns a SEB to a given ainf_volume and removes it - * from it's original list. + * assign_aeb_to_av - assigns a SEB to a given ainf_volume * @ai: ubi_attach_info object * @aeb: the to be assigned SEB * @av: target scan volume @@ -183,7 +261,6 @@ static void assign_aeb_to_av(struct ubi_attach_info *ai, break; } - list_del(&aeb->u.list); av->leb_count++; rb_link_node(&aeb->u.rb, parent, p); @@ -534,7 +611,8 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, struct ubi_attach_info *ai, struct ubi_fastmap_layout *fm) { - struct list_head used, eba_orphans, free; + struct list_head eba_orphans, free; + struct rb_root used = RB_ROOT; struct ubi_ainf_volume *av; struct ubi_ainf_peb *aeb, *tmp_aeb, *_tmp_aeb; struct ubi_ec_hdr *ech; @@ -549,7 +627,6 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, unsigned long long max_sqnum = 0; void *fm_raw = ubi->fm_buf; - INIT_LIST_HEAD(&used); INIT_LIST_HEAD(&free); INIT_LIST_HEAD(&eba_orphans); INIT_LIST_HEAD(&ai->corr); @@ -650,7 +727,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, if (fm_pos >= fm_size) goto fail_bad; - add_aeb(ai, &used, be32_to_cpu(fmec->pnum), + add_aeb_rb(ai, &used, be32_to_cpu(fmec->pnum), be32_to_cpu(fmec->ec), 0); } @@ -661,7 +738,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, if (fm_pos >= fm_size) goto fail_bad; - add_aeb(ai, &used, be32_to_cpu(fmec->pnum), + add_aeb_rb(ai, &used, be32_to_cpu(fmec->pnum), be32_to_cpu(fmec->ec), 1); } @@ -726,10 +803,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, continue; aeb = NULL; - list_for_each_entry(tmp_aeb, &used, u.list) { - if (tmp_aeb->pnum == pnum) - aeb = tmp_aeb; - } + aeb = find_aeb_in_rb(&used, pnum); /* This can happen if a PEB is already in an EBA known * by this fastmap but the PEB itself is not in the used @@ -760,6 +834,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, if (av->highest_lnum <= aeb->lnum) av->highest_lnum = aeb->lnum; + rb_erase(&aeb->u.rb, &used); assign_aeb_to_av(ai, aeb, av); dbg_bld("inserting PEB:%i (LEB %i) to vol %i", @@ -795,6 +870,7 @@ static int ubi_attach_fastmap(struct ubi_device *ubi, tmp_aeb->scrub = 1; tmp_aeb->ec = be64_to_cpu(ech->ec); + list_del(&tmp_aeb->u.list); assign_aeb_to_av(ai, tmp_aeb, av); }
After some profiling of the attach process, it was found that a considerable amount of time was spent spinning through the list of used PEBs in ubi_attach_fastmap(). This patch converts the list into a RB tree saving considerable time when the volumes fill up. Signed-off-by: Brian Pomerantz <bapper@gmail.com> --- drivers/mtd/ubi/fastmap.c | 98 +++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 87 insertions(+), 11 deletions(-)