RE: [PATCH v2 3/5] mem-pool: fill out functionality

[Jameson Miller <jamill@microsoft.com>]

Thank you for taking a look - I think these are good questions. Please let me know if you have further questions.

> -----Original Message-----
> From: Stefan Beller <sbeller@google.com>
> Sent: Monday, April 30, 2018 5:42 PM
> To: Jameson Miller <jamill@microsoft.com>
> Cc: git@vger.kernel.org; gitster@pobox.com; pclouds@gmail.com;
> jonathantanmy@google.com
> Subject: Re: [PATCH v2 3/5] mem-pool: fill out functionality
> 
> On Mon, Apr 30, 2018 at 8:31 AM, Jameson Miller <jamill@microsoft.com>
> wrote:
> > Adds the following functionality to memory pools:
> >
> >  - Lifecycle management functions (init, discard)
> >
> >  - Test whether a memory location is part of the managed pool
> >
> >  - Function to combine 2 pools
> >
> > This also adds logic to track all memory allocations made by a memory
> > pool.
> >
> > These functions will be used in a future commit in this commit series.
> >
> > Signed-off-by: Jameson Miller <jamill@microsoft.com>
> > ---
> >  mem-pool.c | 114
> > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
> >  mem-pool.h |  32 +++++++++++++++++
> 
> > diff --git a/mem-pool.h b/mem-pool.h
> > index 829ad58ecf..34df4fa709 100644
> > --- a/mem-pool.h
> > +++ b/mem-pool.h
> > @@ -19,8 +19,27 @@ struct mem_pool {
> >
> >         /* The total amount of memory allocated by the pool. */
> >         size_t pool_alloc;
> > +
> > +       /*
> > +        * Array of pointers to "custom size" memory allocations.
> > +        * This is used for "large" memory allocations.
> > +        * The *_end variables are used to track the range of memory
> > +        * allocated.
> > +        */
> > +       void **custom, **custom_end;
> > +       int nr, nr_end, alloc, alloc_end;
> >  };
> 
> What is the design goal of this mem pool?
> What is it really good at, which patterns of use should we avoid?
> 

This memory pool is designed to provide many small (small
compared to the memory pool block size) chunks of memory from a
larger block of allocated memory. This reduces the overhead of
performing many small memory allocations from the heap. In the
ideal case, we know the total amount of memory required, and the
pool can make a single allocation to satisfy that requirement,
and hand it out in chunks to consumers.

We should avoid making many large memory requests (large compared
to the memory pool block size), as these requests will be
fulfilled from individual memory allocations (i.e. the "custom"
allocations). While there is not a correctness issue here, it
will not perform as well when requests are fulfilled from the
internal memory blocks.

> It looks like internally the mem-pool can either use mp_blocks that are stored as
> a linked list, or it can have custom allocations stored in an array.
> 
> Is the linked list or the custom part sorted by some key?
> Does it need to be sorted?
> 
> I am currently looking at alloc.c, which is really good for allocating memory for
> equally sized parts, i.e. it is very efficient at providing memory for fixed sized
> structs. And on top of that it is not tracking any memory as it relies on program
> termination for cleanup.

The linked list is ordered in the order the blocks were allocated
in. The last allocated block will be the head of the linked
list. This means that most memory requests should be fulfilled by
the head block, reducing the need to iterate through the list to
find available memory.

The custom memory blocks are in their own list because they will
never contain any free memory. There is no need to include these
allocations in the list of blocks that could potentially have
free memory.

I expect this code would be efficient at allocating many equal
sized parts, as long as those parts are comparitively small
compared to the block size. In this case, you would never
allocate "custom" blocks, and the overwhelming majority of
allocations would come from the head block. If you know the total
amount of memory you will need, then you can size the memory pool
so all allocations come from the head block.

> 
> This memory pool seems to be optimized for allocations of varying sizes, some
> of them huge (to be stored in the custom
> part) and most of them rather small as they go into the mp_blocks?

I would say this memory pool is optimized for allocations of
varying sizes (although it should be pretty efficient when the
allocations are of the same size), but can handle the edge case
when there happens to be a need for a "huge allocation".
> 
> Thanks,
> Stefan