linux-kernel - Re: [PATCH 4/6] lib: rework bitmap

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] [day] [month] [year] [list]

Message-ID: <20190501003750.GA28987@yury-thinkpad>
Date:   Tue, 30 Apr 2019 17:37:50 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc:     Andrew Morton <akpm@...ux-foundation.org>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Dmitry Torokhov <dmitry.torokhov@...il.com>,
        "David S . Miller" <davem@...emloft.net>,
        Stephen Rothwell <sfr@...b.auug.org.au>,
        Amritha Nambiar <amritha.nambiar@...el.com>,
        Willem de Bruijn <willemb@...gle.com>,
        Kees Cook <keescook@...omium.org>,
        Matthew Wilcox <willy@...radead.org>,
        "Tobin C . Harding" <tobin@...nel.org>,
        Will Deacon <will.deacon@....com>,
        Miklos Szeredi <mszeredi@...hat.com>,
        Vineet Gupta <vineet.gupta1@...opsys.com>,
        Chris Wilson <chris@...is-wilson.co.uk>,
        Arnaldo Carvalho de Melo <acme@...hat.com>,
        Yury Norov <ynorov@...vell.com>, linux-kernel@...r.kernel.org,
        Jens Axboe <axboe@...nel.dk>,
        Steffen Klassert <steffen.klassert@...unet.com>
Subject: Re: [PATCH 4/6] lib: rework bitmap_parse()

On Sun, Apr 28, 2019 at 07:57:45PM +0300, Andy Shevchenko wrote:
> On Sat, Apr 27, 2019 at 08:29:34PM -0700, Yury Norov wrote:
> > bitmap_parse() is ineffective and full of opaque variables and opencoded
> > parts. It leads to hard understanding of it. This rework includes:
> >  - remove bitmap_shift_left() call from the cycle. Now it makes the
> >    complexity of the algorithm as O(nbits^2). In the suggested approach
> >    the input string is parsed in reverse direction, so no shifts needed;
> >  - relax requirement on a single comma and no white spaces between chunks.
> >    It is considered useful in scripting, and it aligns with
> >    bitmap_parselist();
> >  - split bitmap_parse() to small readable helpers;
> >  - make an explicit calculation of the end of input line at the
> >    beginning, so users of the bitmap_parse() won't bother doing this.
> 
> > +static inline bool in_str(const char *start, const char *ptr)
> > +{
> > +	return start <= ptr;
> > +}
> > +
> 
> I don't see how it's better than explicit use. Moreover, explicit use shows the
> exact condition in-line. Even by used characters it's longer.

I did 2 mistakes with a condition ('<' instead of '<=') during the
development, after that I decided to introduce it. I would prefer
keep it.
 
> > +static const char *bitmap_get_hex32_rev(const char *start,
> > +					const char *end, u32 *num)
> 
> In kernel few functions to work with hex u32 named foo_x32(). I would rather
> use that. Besides, we spell "reverse" in full.

OK

> > +{
> > +	u32 ret = 0;
> > +	int c, i;
> > +
> > +	if (hex_to_bin(*end) < 0)
> > +		return ERR_PTR(-EINVAL);
> > +
> > +	for (i = 0; i < 32; i += 4) {
> > +		c = hex_to_bin(*end--);
> > +		if (c < 0)
> 
> Perhaps we may need similar patch for hex_to_bin() as in the commit
> 9888a588ea96 ("lib/hexdump.c: return -EINVAL in case of error in hex2bin()")
> 
> > +			return ERR_PTR(-EINVAL);
> 
> > +
> > +		ret |= c << i;
> > +
> > +		if (!in_str(start, end) || __end_of_region(*end))
> > +			goto out;
> > +	}
> > +
> > +	if (hex_to_bin(*end) >= 0)
> > +		return ERR_PTR(-EOVERFLOW);
> > +out:
> > +	*num = ret;
> > +	return end;
> > +}
> 
> -- 
> With Best Regards,
> Andy Shevchenko
>