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]

Date:   Tue, 6 Oct 2020 16:02:24 +0300
From:   Yevgeny Kliteynik <kliteyn@...dia.com>
To:     David Miller <davem@...emloft.net>
CC:     "saeed@...nel.org" <saeed@...nel.org>,
        "kuba@...nel.org" <kuba@...nel.org>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        "Erez Shitrit" <erezsh@...dia.com>, Mark Bloch <mbloch@...dia.com>,
        Saeed Mahameed <saeedm@...dia.com>
Subject: Re: [net-next 01/15] net/mlx5: DR, Add buddy allocator utilities

On 29-Sep-20 23:44, Yevgeny Kliteynik wrote:>
 > On 29-Sep-20 00:41, David Miller wrote:
 >>
 >> From: Yevgeny Kliteynik <kliteyn@...dia.com>
 >> Date: Mon, 28 Sep 2020 19:58:59 +0000
 >>
 >>> By replacing the bits-per-long array with a single counter we loose
 >>> this ability to jump faster to the free spot.
 >>
 >> I don't understand why this is true, because upon the free we will
 >> update the hint and that's where the next bit search will start.
 >>
 >> Have you even tried my suggestion?
 >
 > I did, but I couldn't make it work for some use cases that
 > I expect to be fairly common. Perhaps I misunderstood something.
 > Let's look at the following use case (I'll make it 'extreme' to
 > better illustrate the problem):

Following up on this mail.
In addition to the case I've described, I'd like to clarify why
the 'lowest set bit' hint doesn't work here.

Buddy allocator allocates blocks of different sizes, so when it
scans the bits array, the allocator looks for free *area* of at
least the required size.
Can't store this info in a 'lowest set bit' counter.

Furthermore, when buddy allocator scans for such areas, it
takes into consideration blocks alignment as required by HW,
which can't be stored in an external counter.

The code here implements standard buddy allocator with a small
optimization of an additional level to speed up the search.
Do you see something wrong with this additional level?

-- YK


 > A buddy is all allocated by mostly small chunks.
 > This means that the bit array of size n will look something like this:
 >
 > idx  | 0 | 1 | ...                                     |n-2|n-1|
 >      |---|---|-----------------------------------------|---|---|
 > array| 0 | 0 | ....... all zeroes - all full .......   | 0 | 0 |
 >      |---|---|-----------------------------------------|---|---|
 >
 > Then chunk that was allocated at index n-1 is freed, which means
 > that 'lowest set bit' is set to n-1.
 > Array will look like this:
 >
 > idx  | 0 | 1 | ...                                     |n-2|n-1|
 >      |---|---|-----------------------------------------|---|---|
 > array| 0 | 0 | ....... all zeroes - all full .......   | 0 | 1 |
 >      |---|---|-----------------------------------------|---|---|
 >
 >
 > Then chunk that was allocated at index 0 is freed, which means
 > that 'lowest set bit' is set to 0.
 > Array will look like this:
 >
 > idx  | 0 | 1 | ...                                     |n-2|n-1|
 >      |---|---|-----------------------------------------|---|---|
 > array| 1 | 0 | ....... all zeroes - all full .......   | 0 | 1 |
 >      |---|---|-----------------------------------------|---|---|
 >
 > Then a new allocation request comes in.
 > The 'lowest set bit' is 0, which allows us to find the spot.
 >
 > The 'lowest set bit' is now set to 1.
 > Array will look like this:
 >
 > idx  | 0 | 1 | ...                                     |n-2|n-1|
 >      |---|---|-----------------------------------------|---|---|
 > array| 0 | 0 | ....... all zeroes - all full .......   | 0 | 1 |
 >      |---|---|-----------------------------------------|---|---|
 >
 > Then another allocation request comes in.
 > The 'lowest set bit' is 1, which means that we now need
 > to scan the whole array.
 >
 > Is there a way to make 'lowest set bit' hint to work for
 > the use cases similar to what I've described?
 >
 > -- YK
 >