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: <df068816-7269-4275-a673-d9ed5c050365@efficios.com>
Date: Tue, 20 Aug 2024 22:45:17 +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-20 19:19, Mathieu Desnoyers wrote:
> On 2024-08-19 21:19, Yury Norov wrote:
[...]
>>> +/**
>>> + * 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.

Actually, now that I come to think of it in terms of logic gates:

~A & ~B == ~(A | B)

So this "notandnot" is simply a "NOR" gate.

I therefore intend to name it "find_next_nor_bit" if that's OK with
you.

Thanks,

Mathieu

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