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

[Duy Nguyen]

Another I noticed in the jm/mem-pool series is this loop in mem_pool_alloc()

for (p = mem_pool->mp_block; p; p = p->next_block)
if (p->end - p->next_free >= len)
break;

You always go from the start (mp_block) but at some point those first
blocks are filled up and we don't really need to walk from the start
anymore. If we allow the mem-pool user to set a "minimum alloc" limit,
then we can determine if the remaining space in a block is not useful
for any future allocation, we can just skip it and start looking for
an available from a new pointer, avail_block or something.

I'm writing this with alloc.c in mind because we have a lot more
blocks to allocate there. Unlike read-cache, you can't really estimate
how many mp_blocks you're going to need. This linked list could become
long. And because alloc.c does fixed size allocation, we use up one
block after another and will never find free space in previous blocks.

On Mon, Apr 30, 2018 at 5:31 PM, Jameson Miller  wrote:
> diff --git a/mem-pool.c b/mem-pool.c
> index 389d7af447..a495885c4b 100644
> --- a/mem-pool.c
> +++ b/mem-pool.c
> @@ -5,6 +5,8 @@
>  #include "cache.h"
>  #include "mem-pool.h"
>
> +#define BLOCK_GROWTH_SIZE 1024*1024 - sizeof(struct mp_block);

#define BLOCK_GROWTH_SIZE (1024*1024 - sizeof(struct mp_block))

(wrapped in brackets and no trailing semicolon)

> +
>  static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, 
> size_t block_alloc)
>  {
> struct mp_block *p;
> @@ -19,6 +21,60 @@ static struct mp_block *mem_pool_alloc_block(struct 
> mem_pool *mem_pool, size_t b
> return p;
>  }
>
> +static void *mem_pool_alloc_custom(struct mem_pool *mem_pool, size_t 
> block_alloc)
> +{
> +   char *p;

An empty line between variable declaration and function body would be nice.

> +   ALLOC_GROW(mem_pool->custom, mem_pool->nr + 1, mem_pool->alloc);
> +   ALLOC_GROW(mem_pool->custom_end, mem_pool->nr_end + 1, 
> mem_pool->alloc_end);
> +

If you put both custom and custom_end in a struct, then you can grow
just one array (of the new struct) and have fewer support variables
like nr_end and alloc_end

The only downside that I can see is the potential padding between
struct increasing memory consumption here. but since you don't care
about reallocation cost (i.e. large memory allocations should be
rare), it probably  does not matter either.

But wait, can we just reuse struct mp_block for this? You allocate a
new mp_block (for just one allocation) as usual, then you can can
maintain a linked list of custom alloc in "struct mp_block
*mp_custom_block" or something. This way we can walk both bulk and
custom allocation the same way.

> +   p = xmalloc(block_alloc);
> +   mem_pool->custom[mem_pool->nr++] = p;
> +   mem_pool->custom_end[mem_pool->nr_end++] = p + block_alloc;
> +
> +   mem_pool->pool_alloc += block_alloc;
> +
> +   return mem_pool->custom[mem_pool->nr];
> +}
> +
> +void mem_pool_init(struct mem_pool **mem_pool, size_t initial_size)
> +{
> +   if (!(*mem_pool))

I think (!*mem_pool) should be enough, although you could avoid the
operator precedence headache by doing

if (*mem_pool)
return;

> +   {
> +   *mem_pool = xmalloc(sizeof(struct mem_pool));

I think we tend to do *mem_pool = xmalloc(sizeof(**mem_pool));

> +   (*mem_pool)->pool_alloc = 0;

Eghh.. perhaps just declare

struct mem_pool *pool;

then allocate a new memory to this, initialize everything and only do

*mem_pool = pool;

at the end? It's much less of this (*mem_pool)->

> +   (*mem_pool)->mp_block = NULL;

Just memset() it once (or use xcallo) and only initialize
non-zero/null fields afterwards.

> +   (*mem_pool)->block_alloc = BLOCK_GROWTH_SIZE;
> +   (*mem_pool)->custom = NULL;
> +   (*mem_pool)->nr = 0;
> +   (*mem_pool)->alloc = 0;
> +   (*mem_pool)->custom_end = NULL;
> +   (*mem_pool)->nr_end = 0;
> +   (*mem_pool)->alloc_end = 0;
> +
> +   if (initial_size > 0)
> +   mem_pool_alloc_block(*mem_pool, initial_size);
> +   }
> +}
> +
> +void mem_pool_discard(struct mem_pool *mem_pool)
> +{
> +   int i;
> +   struct mp_block *block, *block_to_free;
> +   for (block = mem_pool->mp_block; block;)
> +   {
> +   block_to_free = block;
> +   block = block->next_block;
> +   free(block_to_free);
> +   }
> +
> +   for (i = 0; i < mem_pool->nr; i++)
> +   free(mem_pool->custom[i]);
> +
> +   free(mem_pool->custom);
> +   free(mem_pool->custom_end);
> +   free(mem_pool);
> +}
> +
>  void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
>  {
> struct mp_block *p;
> @@ -33,10 +89,8 @@ void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
> break;
>
> if (!p) {
> -

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

[Jameson Miller]

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 <sbel...@google.com>
> Sent: Monday, April 30, 2018 5:42 PM
> To: Jameson Miller <jam...@microsoft.com>
> Cc: git@vger.kernel.org; gits...@pobox.com; pclo...@gmail.com;
> jonathanta...@google.com
> Subject: Re: [PATCH v2 3/5] mem-pool: fill out functionality
> 
> On Mon, Apr 30, 2018 at 8:31 AM, Jameson Miller <jam...@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 <jam...@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

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

[Stefan Beller]

On Mon, Apr 30, 2018 at 8:31 AM, Jameson Miller  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 
> ---
>  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?

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.

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?

Thanks,
Stefan

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

[Jameson Miller]

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 
---
 mem-pool.c | 114 ++---
 mem-pool.h |  32 +
 2 files changed, 142 insertions(+), 4 deletions(-)

diff --git a/mem-pool.c b/mem-pool.c
index 389d7af447..a495885c4b 100644
--- a/mem-pool.c
+++ b/mem-pool.c
@@ -5,6 +5,8 @@
 #include "cache.h"
 #include "mem-pool.h"
 
+#define BLOCK_GROWTH_SIZE 1024*1024 - sizeof(struct mp_block);
+
 static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t 
block_alloc)
 {
struct mp_block *p;
@@ -19,6 +21,60 @@ static struct mp_block *mem_pool_alloc_block(struct mem_pool 
*mem_pool, size_t b
return p;
 }
 
+static void *mem_pool_alloc_custom(struct mem_pool *mem_pool, size_t 
block_alloc)
+{
+   char *p;
+   ALLOC_GROW(mem_pool->custom, mem_pool->nr + 1, mem_pool->alloc);
+   ALLOC_GROW(mem_pool->custom_end, mem_pool->nr_end + 1, 
mem_pool->alloc_end);
+
+   p = xmalloc(block_alloc);
+   mem_pool->custom[mem_pool->nr++] = p;
+   mem_pool->custom_end[mem_pool->nr_end++] = p + block_alloc;
+
+   mem_pool->pool_alloc += block_alloc;
+
+   return mem_pool->custom[mem_pool->nr];
+}
+
+void mem_pool_init(struct mem_pool **mem_pool, size_t initial_size)
+{
+   if (!(*mem_pool))
+   {
+   *mem_pool = xmalloc(sizeof(struct mem_pool));
+   (*mem_pool)->pool_alloc = 0;
+   (*mem_pool)->mp_block = NULL;
+   (*mem_pool)->block_alloc = BLOCK_GROWTH_SIZE;
+   (*mem_pool)->custom = NULL;
+   (*mem_pool)->nr = 0;
+   (*mem_pool)->alloc = 0;
+   (*mem_pool)->custom_end = NULL;
+   (*mem_pool)->nr_end = 0;
+   (*mem_pool)->alloc_end = 0;
+
+   if (initial_size > 0)
+   mem_pool_alloc_block(*mem_pool, initial_size);
+   }
+}
+
+void mem_pool_discard(struct mem_pool *mem_pool)
+{
+   int i;
+   struct mp_block *block, *block_to_free;
+   for (block = mem_pool->mp_block; block;)
+   {
+   block_to_free = block;
+   block = block->next_block;
+   free(block_to_free);
+   }
+
+   for (i = 0; i < mem_pool->nr; i++)
+   free(mem_pool->custom[i]);
+
+   free(mem_pool->custom);
+   free(mem_pool->custom_end);
+   free(mem_pool);
+}
+
 void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
 {
struct mp_block *p;
@@ -33,10 +89,8 @@ void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
break;
 
if (!p) {
-   if (len >= (mem_pool->block_alloc / 2)) {
-   mem_pool->pool_alloc += len;
-   return xmalloc(len);
-   }
+   if (len >= (mem_pool->block_alloc / 2))
+   return mem_pool_alloc_custom(mem_pool, len);
 
p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
}
@@ -53,3 +107,55 @@ void *mem_pool_calloc(struct mem_pool *mem_pool, size_t 
count, size_t size)
memset(r, 0, len);
return r;
 }
+
+int mem_pool_contains(struct mem_pool *mem_pool, void *mem)
+{
+   int i;
+   struct mp_block *p;
+
+   /* Check if memory is allocated in a block */
+   for (p = mem_pool->mp_block; p; p = p->next_block)
+   if ((mem >= ((void *)p->space)) &&
+   (mem < ((void *)p->end)))
+   return 1;
+
+   /* Check if memory is allocated in custom block */
+   for (i = 0; i < mem_pool->nr; i++)
+   if ((mem >= mem_pool->custom[i]) &&
+   (mem < mem_pool->custom_end[i]))
+   return 1;
+
+   return 0;
+}
+
+void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src)
+{
+   int i;
+   struct mp_block **tail = >mp_block;
+
+   /* Find pointer of dst's last block (if any) */
+   while (*tail)
+   tail = &(*tail)->next_block;
+
+   /* Append the blocks from src to dst */
+   *tail = src->mp_block;
+
+   /* Combine custom allocations */
+   ALLOC_GROW(dst->custom, dst->nr + src->nr, dst->alloc);
+   ALLOC_GROW(dst->custom_end, dst->nr_end + src->nr_end, dst->alloc_end);
+
+   for (i = 0; i < src->nr; i++) {
+   dst->custom[dst->nr++] = src->custom[i];
+   dst->custom_end[dst->nr_end++] = src->custom_end[i];
+   }
+
+   dst->pool_alloc += src->pool_alloc;
+   src->pool_alloc = 0;
+   src->mp_block = NULL;
+   src->custom = NULL;
+   src->nr = 0;
+