linux-kernel - Re: [PATCH V2] tipc: Use bsearch library 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]

Message-ID: <1505553970.16316.1.camel@perches.com>
Date:   Sat, 16 Sep 2017 02:26:10 -0700
From:   Joe Perches <joe@...ches.com>
To:     Ying Xue <ying.xue@...driver.com>, Thomas Meyer <thomas@...3r.de>,
        jon.maloy@...csson.com, netdev@...r.kernel.org,
        tipc-discussion@...ts.sourceforge.net,
        linux-kernel@...r.kernel.org, davem@...emloft.net
Subject: Re: [PATCH V2] tipc: Use bsearch library function

On Sat, 2017-09-16 at 17:02 +0800, Ying Xue wrote:
> On 09/16/2017 03:50 PM, Thomas Meyer wrote:
> > Use common library function rather than explicitly coding
> > some variant of it yourself.
> > 
> > Signed-off-by: Thomas Meyer <thomas@...3r.de>
> 
> Acked-by: Ying Xue <ying.xue@...driver.com>

Are you sure you want to do this?

Note the comment above nameseq_find_subseq

 * Very time-critical, so binary searches through sub-sequence array.

What impact does this change have on performance?

> > diff --git a/net/tipc/name_table.c b/net/tipc/name_table.c
> > index bd0aac87b41a..eeb4d7a13de2 100644
> > --- a/net/tipc/name_table.c
> > +++ b/net/tipc/name_table.c
> > @@ -44,6 +44,7 @@
> >  #include "addr.h"
> >  #include "node.h"
> >  #include <net/genetlink.h>
> > +#include <linux/bsearch.h>
> >  
> >  #define TIPC_NAMETBL_SIZE 1024		/* must be a power of 2 */
> >  
> > @@ -168,6 +169,18 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea
> >  	return nseq;
> >  }
> >  
> > +static int nameseq_find_subseq_cmp(const void *key, const void *elt)
> > +{
> > +	struct sub_seq *sseq = (struct sub_seq *)elt;
> > +	u32 instance = *(u32 *)key;
> > +
> > +	if (instance < sseq->lower)
> > +		return -1;
> > +	else if (instance > sseq->upper)
> > +		return 1;
> > +	return 0;
> > +}
> > +
> >  /**
> >   * nameseq_find_subseq - find sub-sequence (if any) matching a name instance
> >   *
> > @@ -176,21 +189,8 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea
> >  static struct sub_seq *nameseq_find_subseq(struct name_seq *nseq,
> >  					   u32 instance)
> >  {
> > -	struct sub_seq *sseqs = nseq->sseqs;
> > -	int low = 0;
> > -	int high = nseq->first_free - 1;
> > -	int mid;
> > -
> > -	while (low <= high) {
> > -		mid = (low + high) / 2;
> > -		if (instance < sseqs[mid].lower)
> > -			high = mid - 1;
> > -		else if (instance > sseqs[mid].upper)
> > -			low = mid + 1;
> > -		else
> > -			return &sseqs[mid];
> > -	}
> > -	return NULL;
> > +	return bsearch(&instance, nseq->sseqs, nseq->first_free,
> > +		       sizeof(struct sub_seq), nameseq_find_subseq_cmp);
> >  }
> >  
> >  /**
> >