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: <d53133e1-ca35-40cd-3856-f8592fd4895e@nvidia.com>
Date:   Tue, 29 Sep 2020 23:44:50 +0300
From:   Yevgeny Kliteynik <kliteyn@...dia.com>
To:     David Miller <davem@...emloft.net>
CC:     <saeed@...nel.org>, <kuba@...nel.org>, <netdev@...r.kernel.org>,
        <erezsh@...dia.com>, <mbloch@...dia.com>, <saeedm@...dia.com>
Subject: Re: [net-next 01/15] net/mlx5: DR, Add buddy allocator utilities

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):

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