netdev - Re: [net-next 01/15] net/mlx5: DR, Add buddy allocator utilities

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: <20200926.151540.1383303857229218158.davem@davemloft.net>
Date:   Sat, 26 Sep 2020 15:15:40 -0700 (PDT)
From:   David Miller <davem@...emloft.net>
To:     saeed@...nel.org
Cc:     kuba@...nel.org, netdev@...r.kernel.org, kliteyn@...dia.com,
        erezsh@...dia.com, mbloch@...dia.com, saeedm@...dia.com
Subject: Re: [net-next 01/15] net/mlx5: DR, Add buddy allocator utilities

From: saeed@...nel.org
Date: Fri, 25 Sep 2020 12:37:55 -0700

> From: Yevgeny Kliteynik <kliteyn@...dia.com>
> 
> Add implementation of SW Steering variation of buddy allocator.
> 
> The buddy system for ICM memory uses 2 main data structures:
>   - Bitmap per order, that keeps the current state of allocated
>     blocks for this order
>   - Indicator for the number of available blocks per each order
> 
> In addition, there is one more hierarchy of searching in the bitmaps
> in order to accelerate the search of the next free block which done
> via find-first function:
> The buddy system spends lots of its time in searching the next free
> space using function find_first_bit, which scans a big array of long
> values in order to find the first bit. We added one more array of
> longs, where each bit indicates a long value in the original array,
> that way there is a need for much less searches for the next free area.
> 
> For example, for the following bits array of 128 bits where all
> bits are zero except for the last bit  :  0000........00001
> the corresponding bits-per-long array is:  0001
> 
> The search will be done over the bits-per-long array first, and after
> the first bit is found, we will use it as a start pointer in the
> bigger array (bits array).
> 
> Signed-off-by: Erez Shitrit <erezsh@...dia.com>
> Signed-off-by: Yevgeny Kliteynik <kliteyn@...dia.com>
> Reviewed-by: Mark Bloch <mbloch@...dia.com>
> Signed-off-by: Saeed Mahameed <saeedm@...dia.com>

Instead of a bits-per-long array, it seems so much simpler and more
cache friendly to maintain instead just a "lowest set bit" value.

In the initial state it is zero for all values, remember this is just
a hint.

When you allocate, if num_free is non-zero of course, you start the
bit scan from the "lowest set bit" value.  When the set bit is found,
update the "lowest set bit" cache to the set bit plus one (or zero if
the new value exceeds the bitmap size).

Then on free you update "lowest set bit" to the bit being set if it is
smaller than the current "lowest set bit" value for that order.

No double scanning of bitmap arrays, just a single bitmap search with
a variable start point.