Message-ID: <DM6PR12MB423444C484839CF7FB7AA6B3C0350@DM6PR12MB4234.namprd12.prod.outlook.com>
Date:   Mon, 28 Sep 2020 19:58:59 +0000
From:   Yevgeny Kliteynik <kliteyn@...dia.com>
To:     David Miller <davem@...emloft.net>,
        "saeed@...nel.org" <saeed@...nel.org>
CC:     "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

> From: David Miller <davem@...emloft.net>
> Sent: Sunday, September 27, 2020 01:16
> To: saeed@...nel.org
> Cc: kuba@...nel.org; netdev@...r.kernel.org; Yevgeny Kliteynik
> <kliteyn@...dia.com>; 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
> 
> External email: Use caution opening links or attachments
> 
> 
> 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).

This will work when you allocate everything and freeing "in order".
In our vase the system is more dynamic - we allocate, and then some chunks
are freed all over, creating free spots in the bit array in a rather random manner.
By replacing the bits-per-long array with a single counter we loose this ability
to jump faster to the free spot.
It is still an improvement to start from a certain place and not from the beginning,
but bits-per-long array saves more time.
Also, in terms of memory, it's not a big hit - it's bit per 32 chunks (or byte per 256 chunks).

-- YK

> 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