linux-kernel - Re: [PATCH v2] lib/btree.c: optimise the code by previously getpos function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 11 May 2017 14:00:01 +0300
From:   Andy Shevchenko <andy.shevchenko@...il.com>
To:     Leno Hou <lenohou@...il.com>
Cc:     "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Christoph Hellwig <hch@...radead.org>
Subject: Re: [PATCH v2] lib/btree.c: optimise the code by previously getpos function

On Thu, May 11, 2017 at 12:42 PM, Leno Hou <lenohou@...il.com> wrote:
> This patch optimized the code by previously getpos function call.
> Therefore, It's takes the convenience to understand logic of code.
>
> v2:
>   - getpos() returns errorno if not found the key
>
> v1:
>   - cleanup code by using getpos()

FWIW:
Reviewed-by: Andy Shevchenko <andy.shevchenko@...il.com>

>
> Signed-off-by: Leno Hou <lenohou@...il.com>
> ---
>  lib/btree.c | 50 +++++++++++++++++++++-----------------------------
>  1 file changed, 21 insertions(+), 29 deletions(-)
>
> diff --git a/lib/btree.c b/lib/btree.c
> index f93a945..8604773 100644
> --- a/lib/btree.c
> +++ b/lib/btree.c
> @@ -238,6 +238,18 @@ static int keyzero(struct btree_geo *geo, unsigned long *key)
>         return 1;
>  }
>
> +static int getpos(struct btree_geo *geo, unsigned long *node,
> +               unsigned long *key)
> +{
> +       unsigned int i;
> +
> +       for (i = 0; i < geo->no_pairs; i++) {
> +               if (keycmp(geo, node, i, key) <= 0)
> +                       return i;
> +       }
> +       return -ENOENT;
> +}
> +
>  void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
>                 unsigned long *key)
>  {
> @@ -248,10 +260,8 @@ void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
>                 return NULL;
>
>         for ( ; height > 1; height--) {
> -               for (i = 0; i < geo->no_pairs; i++)
> -                       if (keycmp(geo, node, i, key) <= 0)
> -                               break;
> -               if (i == geo->no_pairs)
> +               i = getpos(geo, node, key);
> +               if (i < 0)
>                         return NULL;
>                 node = bval(geo, node, i);
>                 if (!node)
> @@ -278,10 +288,8 @@ int btree_update(struct btree_head *head, struct btree_geo *geo,
>                 return -ENOENT;
>
>         for ( ; height > 1; height--) {
> -               for (i = 0; i < geo->no_pairs; i++)
> -                       if (keycmp(geo, node, i, key) <= 0)
> -                               break;
> -               if (i == geo->no_pairs)
> +               i = getpos(geo, node, key);
> +               if (i < 0)
>                         return -ENOENT;
>                 node = bval(geo, node, i);
>                 if (!node)
> @@ -326,10 +334,8 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
>
>         node = head->node;
>         for (height = head->height ; height > 1; height--) {
> -               for (i = 0; i < geo->no_pairs; i++)
> -                       if (keycmp(geo, node, i, key) <= 0)
> -                               break;
> -               if (i == geo->no_pairs)
> +               i = getpos(geo, node, key);
> +               if (i < 0)
>                         goto miss;
>                 oldnode = node;
>                 node = bval(geo, node, i);
> @@ -360,18 +366,6 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
>  }
>  EXPORT_SYMBOL_GPL(btree_get_prev);
>
> -static int getpos(struct btree_geo *geo, unsigned long *node,
> -               unsigned long *key)
> -{
> -       int i;
> -
> -       for (i = 0; i < geo->no_pairs; i++) {
> -               if (keycmp(geo, node, i, key) <= 0)
> -                       break;
> -       }
> -       return i;
> -}
> -
>  static int getfill(struct btree_geo *geo, unsigned long *node, int start)
>  {
>         int i;
> @@ -392,11 +386,9 @@ static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
>         int i, height;
>
>         for (height = head->height; height > level; height--) {
> -               for (i = 0; i < geo->no_pairs; i++)
> -                       if (keycmp(geo, node, i, key) <= 0)
> -                               break;
> +               i = getpos(geo, node, key);
>
> -               if ((i == geo->no_pairs) || !bval(geo, node, i)) {
> +               if ((i < 0) || !bval(geo, node, i)) {
>                         /* right-most key is too large, update it */
>                         /* FIXME: If the right-most key on higher levels is
>                          * always zero, this wouldn't be necessary. */
> @@ -466,7 +458,7 @@ static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
>         /* two identical keys are not allowed */
>         BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
>
> -       if (fill == geo->no_pairs) {
> +       if (fill < 0) {
>                 /* need to split node */
>                 unsigned long *new;
>
> --
> 2.7.4
>



-- 
With Best Regards,
Andy Shevchenko