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  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]
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.

Powered by blists - more mailing lists