linux-kernel - Re: [RFC PATCH 1/5] lib: Implement find_{first,next,nth}_notandnot_bit, find_first_andnot

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: <1207b505-0842-40cc-a581-44e595f67601@efficios.com>
Date: Tue, 20 Aug 2024 19:19:43 +0200
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: Yury Norov <yury.norov@...il.com>
Cc: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>,
 linux-kernel@...r.kernel.org, Valentin Schneider <vschneid@...hat.com>,
 Mel Gorman <mgorman@...e.de>, Steven Rostedt <rostedt@...dmis.org>,
 Vincent Guittot <vincent.guittot@...aro.org>,
 Dietmar Eggemann <dietmar.eggemann@....com>, Ben Segall
 <bsegall@...gle.com>, Rasmus Villemoes <linux@...musvillemoes.dk>,
 Shuah Khan <skhan@...uxfoundation.org>
Subject: Re: [RFC PATCH 1/5] lib: Implement
 find_{first,next,nth}_notandnot_bit, find_first_andnot_bit

On 2024-08-19 21:19, Yury Norov wrote:
[...[> Can you split rewording of existing comments out to a separate patch
> please?

Will do.

> 
>>    */
>>   static inline
>>   unsigned long find_next_andnot_bit(const unsigned long *addr1,
>> @@ -131,6 +138,36 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,
>>   }
>>   #endif
>>   
>> +#ifndef find_next_notandnot_bit
> 
> Don't protect new functions. This is only for those having arch
> implementation, and it's only armv7 now.

OK

> 
>> +/**
>> + * find_next_notandnot_bit - find the next bit cleared in both *addr1 and *addr2
>> + * @addr1: The first address to base the search on
>> + * @addr2: The second address to base the search on
>> + * @size: The bitmap size in bits
>> + * @offset: The bitnumber to start searching at
>> + *
>> + * Returns the bit number for the next bit cleared in both *addr1 and *addr2.
>> + * If no such bits are found, returns @size.
>> + */
>> +static inline
>> +unsigned long find_next_notandnot_bit(const unsigned long *addr1,
>> +		const unsigned long *addr2, unsigned long size,
>> +		unsigned long offset)
>> +{
>> +	if (small_const_nbits(size)) {
>> +		unsigned long val;
>> +
>> +		if (unlikely(offset >= size))
>> +			return size;
>> +
>> +		val = (~*addr1) & (~*addr2) & GENMASK(size - 1, offset);
>> +		return val ? __ffs(val) : size;
>> +	}
>> +
>> +	return _find_next_notandnot_bit(addr1, addr2, size, offset);
>> +}
>> +#endif
>> +
> 
> It's not said explicitly, but some naming conventions exist around bitmap
> searching.
> 
> If you're looking for a clear (unset) bit in a mask, you'd use a 'zero'
> modifier. We have only 2 such functions now: find_{first,next}_zero_bit,
> both taking one bitmap. I think it's time to extend this rule for
> many bitmaps and write down the naming rules.
> 
> With the following, the find_next_notandnot_bit() should be named
> like; find_next_zero_and_bit(). It's not perfect, but still sounds
> better to me than 'notandnot' thing.
> 
> If we search for a set bit in bitmap, we use find_first or find_next
> prefixes:
>   - find_first_bit;
>   - find_next_bit.
> 
> If we'd like to pass an additional bitmap to AND, OR or XOR with the
> 1st bitmap, we provide as corresponding logical operation as
> suffix(es):
>   - find_first_and_bit(b1, b2) : b1 & b2;
>   - find _next_and_or_bit(b1, b2, b3) : b1 & b2 | b3.
> 
> If additional bitmap must be inverted, we provide a 'not' after the
> corresponding logical operation:
>   - find_first_andnot_bit(b1, b2) : b1 & ~b2;
>   - find _next_and_ornot_bit(b1, b2, b3) : b1 & b2 | ~b3.
> 
> If all bitmaps have to be inverted, or in other words, we are looking
> for an unset bit in a bitmap or a combination of bitmaps, we provide
> a 'zero' prefix in the function name:
>   - find_next_zero_bit;
>   - find_next_zero_and_bit;
>   - find_next_zero_and_or_bit;
> 
> Functions having 'zero' prefix should not negate bitmaps (should not
> have 'not' in names) because of commutative property. For example,
> find_next_zero_andnot_bit(), which is ~b1 & ~(~b2) is redundant
> because it's the same as find_next_andnot_bit() : b2 & ~b1.
> 
> Iterators over unset bits in bitmap(s) (those based on 'zero' search
> functions) should have a 'clear' prefix in the name:
>   - for_each_clear_bit;
>   - for_each_clear_bit_from;
> 
> I should probably put the above on top of the file...

I'll do this for the next round. Yes, it would be good to add
those explanations on top of the file.

Thanks for the review !

Mathieu

> 
> Thanks,
> Yury

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com