[PATCH 0/3] Extract memory pool logic into reusable component

[PATCH 0/3] Extract memory pool logic into reusable component

[jameson.miller81]

From: Jameson Miller <jamill@microsoft.com>

This patch series extracts the memory pool implementation, currently
used by fast-import, into a generalized component. This memory pool
can then be generally used by any component that needs a pool of
memory.

This patch is in preparation for a change to speed up the loading of
indexes with a large number of cache entries by reducing the number of
malloc() calls. For a rough example of how this component will be used
in this capacity, please see [1].

[1] https://github.com/jamill/git/compare/block_allocation_base...jamill:block_allocation

Jameson Miller (3):
  fast-import: rename mem_pool to fi_mem_pool
  Introduce a reusable memory pool type
  fast-import: use built-in mem pool

 Makefile      |   1 +
 fast-import.c |  50 ++++------------------
 mem-pool.c    | 130 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    |  48 ++++++++++++++++++++++
 4 files changed, 186 insertions(+), 43 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

-- 
2.14.3

[PATCH 1/3] fast-import: rename mem_pool to fi_mem_pool

[jameson.miller81]

From: Jameson Miller <jamill@microsoft.com>

Rename the mem_pool variables and structs in fast-import.c that will
conflict with an upcoming global mem_pool type.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 58ef360da4..4e68acc156 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -209,8 +209,8 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mem_pool {
-	struct mem_pool *next_pool;
+struct fi_mem_pool {
+	struct fi_mem_pool *next_pool;
 	char *next_free;
 	char *end;
 	uintmax_t space[FLEX_ARRAY]; /* more */
@@ -304,9 +304,9 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
+static size_t fi_mem_pool_alloc = 2*1024*1024 - sizeof(struct fi_mem_pool);
 static size_t total_allocd;
-static struct mem_pool *mem_pool;
+static struct fi_mem_pool *mem_pool;
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -636,7 +636,7 @@ static unsigned int hc_str(const char *s, size_t len)
 
 static void *pool_alloc(size_t len)
 {
-	struct mem_pool *p;
+	struct fi_mem_pool *p;
 	void *r;
 
 	/* round up to a 'uintmax_t' alignment */
@@ -648,15 +648,15 @@ static void *pool_alloc(size_t len)
 			break;
 
 	if (!p) {
-		if (len >= (mem_pool_alloc/2)) {
+		if (len >= (fi_mem_pool_alloc/2)) {
 			total_allocd += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mem_pool), mem_pool_alloc));
+		total_allocd += sizeof(struct fi_mem_pool) + fi_mem_pool_alloc;
+		p = xmalloc(st_add(sizeof(struct fi_mem_pool), fi_mem_pool_alloc));
 		p->next_pool = mem_pool;
 		p->next_free = (char *) p->space;
-		p->end = p->next_free + mem_pool_alloc;
+		p->end = p->next_free + fi_mem_pool_alloc;
 		mem_pool = p;
 	}
 
-- 
2.14.3

[PATCH 2/3] Introduce a reusable memory pool type

[jameson.miller81]

From: Jameson Miller <jamill@microsoft.com>

Extract the existing memory pool logic used by fast-import into a
generalized component. This memory pool component can then be used by
other components that need this functionality.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 Makefile   |   1 +
 mem-pool.c | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h |  48 +++++++++++++++++++++++
 3 files changed, 179 insertions(+)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

diff --git a/Makefile b/Makefile
index a1d8775adb..1e142b1dd9 100644
--- a/Makefile
+++ b/Makefile
@@ -832,6 +832,7 @@ LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailinfo.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += mem-pool.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
diff --git a/mem-pool.c b/mem-pool.c
new file mode 100644
index 0000000000..3028bc3c67
--- /dev/null
+++ b/mem-pool.c
@@ -0,0 +1,130 @@
+/*
+ * Memory Pool implementation logic.
+ */
+
+#include "cache.h"
+#include "mem-pool.h"
+
+#define MIN_ALLOC_GROWTH_SIZE 1024 * 1024
+
+struct mp_block {
+	struct mp_block *next_block;
+	char *next_free;
+	char *end;
+	uintmax_t space[FLEX_ARRAY];
+};
+
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p;
+
+	/* Round up to a 'uintmax_t' alignment */
+	if (block_alloc & (sizeof(uintmax_t) - 1))
+		block_alloc += sizeof(uintmax_t) - (block_alloc & (sizeof(uintmax_t) - 1));
+
+	mem_pool->pool_alloc += block_alloc;
+
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+void mem_pool_init(struct mem_pool **mem_pool, size_t block_alloc, size_t initial_size)
+{
+	if (!(*mem_pool))
+	{
+		if (block_alloc < MIN_ALLOC_GROWTH_SIZE)
+			block_alloc = MIN_ALLOC_GROWTH_SIZE;
+
+		*mem_pool = xmalloc(sizeof(struct mem_pool));
+		(*mem_pool)->pool_alloc = 0;
+		(*mem_pool)->mp_block = 0;
+		(*mem_pool)->block_alloc = block_alloc;
+
+		if (initial_size > 0)
+			mem_pool_alloc_block((*mem_pool), initial_size);
+	}
+}
+
+void mem_pool_discard(struct mem_pool *mem_pool)
+{
+	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);
+	}
+
+	free(mem_pool);
+}
+
+void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
+{
+	struct mp_block *p;
+	void *r;
+
+	/* Round up to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
+	p = mem_pool->mp_block;
+
+	if (p &&
+	   (p->end - p->next_free < len)) {
+		for (p = p->next_block; p; p = p->next_block)
+			if (p->end - p->next_free >= len)
+				break;
+	}
+
+	if (!p) {
+		if (len >= ((mem_pool->block_alloc - sizeof(struct mp_block)) / 2)) {
+			p = mem_pool_alloc_block(mem_pool, len);
+		}
+		else
+			p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
+	}
+
+	r = p->next_free;
+	p->next_free += len;
+	return r;
+}
+
+void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
+{
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
+	memset(r, 0, len);
+	return r;
+}
+
+int mem_pool_contains(struct mem_pool *mem_pool, void *mem)
+{
+	struct mp_block *p;
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if ((mem >= ((void *)p->space)) &&
+		    (mem < ((void *)p->end)))
+			return 1;
+
+	return 0;
+}
+
+void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src)
+{
+	struct mp_block **tail = &dst->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;
+
+	dst->pool_alloc += src->pool_alloc;
+	src->pool_alloc = 0;
+	src->mp_block = NULL;
+}
diff --git a/mem-pool.h b/mem-pool.h
new file mode 100644
index 0000000000..902ef8caf2
--- /dev/null
+++ b/mem-pool.h
@@ -0,0 +1,48 @@
+#ifndef MEM_POOL_H
+#define MEM_POOL_H
+
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/* The size of new blocks to grow the pool by. */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
+/*
+ * Initialize mem_pool with specified parameters for initial size and
+ * how much to grow when a larger memory block is required.
+ */
+void mem_pool_init(struct mem_pool **mem_pool, size_t alloc_growth_size, size_t initial_size);
+
+/*
+ * Move the memory associated with the 'src' pool to the 'dst' pool. The 'src'
+ * pool will be empty and not contain any memory. It still needs to be free'd
+ * with a call to `mem_pool_discard`.
+ */
+void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src);
+
+/*
+ * Discard a memory pool and free all the memory it is responsible for.
+ */
+void mem_pool_discard(struct mem_pool *mem_pool);
+
+/*
+ * Alloc memory from the mem_pool.
+ */
+void *mem_pool_alloc(struct mem_pool *pool, size_t len);
+
+/*
+ * Allocate and zero memory from the memory pool.
+ */
+void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
+
+/*
+ * Check if a memory pointed at by 'mem' is part of the range of
+ * memory managed by the specified mem_pool.
+ */
+int mem_pool_contains(struct mem_pool *mem_pool, void *mem);
+
+#endif
-- 
2.14.3

[PATCH 3/3] fast-import: use built-in mem pool

[jameson.miller81]

From: Jameson Miller <jamill@microsoft.com>

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 50 +++++++-------------------------------------------
 1 file changed, 7 insertions(+), 43 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 4e68acc156..126f2da118 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -168,6 +168,7 @@ Format of STDIN stream:
 #include "dir.h"
 #include "run-command.h"
 #include "packfile.h"
+#include "mem-pool.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -209,13 +210,6 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct fi_mem_pool {
-	struct fi_mem_pool *next_pool;
-	char *next_free;
-	char *end;
-	uintmax_t space[FLEX_ARRAY]; /* more */
-};
-
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -304,9 +298,7 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t fi_mem_pool_alloc = 2*1024*1024 - sizeof(struct fi_mem_pool);
-static size_t total_allocd;
-static struct fi_mem_pool *mem_pool;
+static struct mem_pool mem_pool =  {0, 2 * 1024 * 1024, 0 };
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -324,6 +316,7 @@ static off_t pack_size;
 /* Table of objects we've written. */
 static unsigned int object_entry_alloc = 5000;
 static struct object_entry_pool *blocks;
+static size_t total_allocd = 0;
 static struct object_entry *object_table[1 << 16];
 static struct mark_set *marks;
 static const char *export_marks_file;
@@ -636,41 +629,12 @@ static unsigned int hc_str(const char *s, size_t len)
 
 static void *pool_alloc(size_t len)
 {
-	struct fi_mem_pool *p;
-	void *r;
-
-	/* round up to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
-
-	for (p = mem_pool; p; p = p->next_pool)
-		if ((p->end - p->next_free >= len))
-			break;
-
-	if (!p) {
-		if (len >= (fi_mem_pool_alloc/2)) {
-			total_allocd += len;
-			return xmalloc(len);
-		}
-		total_allocd += sizeof(struct fi_mem_pool) + fi_mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct fi_mem_pool), fi_mem_pool_alloc));
-		p->next_pool = mem_pool;
-		p->next_free = (char *) p->space;
-		p->end = p->next_free + fi_mem_pool_alloc;
-		mem_pool = p;
-	}
-
-	r = p->next_free;
-	p->next_free += len;
-	return r;
+	return mem_pool_alloc(&mem_pool, len);
 }
 
 static void *pool_calloc(size_t count, size_t size)
 {
-	size_t len = count * size;
-	void *r = pool_alloc(len);
-	memset(r, 0, len);
-	return r;
+	return mem_pool_calloc(&mem_pool, count, size);
 }
 
 static char *pool_strdup(const char *s)
@@ -3541,8 +3505,8 @@ int cmd_main(int argc, const char **argv)
 		fprintf(stderr, "Total branches:  %10lu (%10lu loads     )\n", branch_count, branch_load_count);
 		fprintf(stderr, "      marks:     %10" PRIuMAX " (%10" PRIuMAX " unique    )\n", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);
 		fprintf(stderr, "      atoms:     %10u\n", atom_cnt);
-		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);
-		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)(total_allocd/1024));
+		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + mem_pool.pool_alloc + alloc_count*sizeof(struct object_entry))/1024);
+		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)((total_allocd + mem_pool.pool_alloc) /1024));
 		fprintf(stderr, "     objects:    %10" PRIuMAX " KiB\n", (alloc_count*sizeof(struct object_entry))/1024);
 		fprintf(stderr, "---------------------------------------------------------------------\n");
 		pack_report();
-- 
2.14.3

Re: [PATCH 0/3] Extract memory pool logic into reusable component

[Junio C Hamano]

jameson.miller81@gmail.com writes:

> This patch series extracts the memory pool implementation, currently
> used by fast-import, into a generalized component. This memory pool
> can then be generally used by any component that needs a pool of
> memory.

The way this series is organized is quite reviewer hostile.  

Step #2 that adds bunch of new code without introducing any caller
nor adjusting existing code means the readers will have no idea how
the new code relates to the existing code in fast-import.c (e.g. "Is
it just a rename of some type, structure fields, function names
etc., and moving the lines without no other change?"  "Is the new
code more capable than fast-import's one and does step #3 just makes
the existing fast-import callers use just a subset of the feature?").

Either case, if I were doing this (by the way, I am not in
particular an expert in this area), I probably would make existing
memtool implementation more generic (e.g. renaming, feature
generalization, etc.) and adjust existing callers while the code is
still in its original place in one step, and then in a separate step
move the resulting reusable bits to a new file wilt a new header.

[PATCH v2 0/3] Extract memory pool logic into reusable component

[Jameson Miller]

Changes from v1:
  - Rework the structure of commits to be more reviewer friendly.

This patch series extracts the memory pool implementation, currently
used by fast-import, into a generalized component. This memory pool
can then be generally used by any component that needs a pool of
memory.

This patch is in preparation for a change to speed up the loading of
indexes with a large number of cache entries by reducing the number of
malloc() calls. For a rough example of how this component will be used
in this capacity, please see [1].

The last commit in this series includes changes to fill out the
mem_pool type into a more complete implementation. These functions are
not used in this change, but we will be used in an upcoming patch
series. I can remove this commit if it is desired.

[1] https://github.com/jamill/git/compare/block_allocation_base...jamill:block_allocation

Jameson Miller (5):
  fast-import: rename mem_pool type to mp_block
  fast-import: introduce mem_pool type
  fast-import: update pool_* functions to work on local pool
  Move the reusable parts of memory pool into its own file
  Expand implementation of mem-pool type

 Makefile      |   1 +
 fast-import.c |  74 +++++----------------------
 mem-pool.c    | 161 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    |  58 +++++++++++++++++++++
 4 files changed, 234 insertions(+), 60 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

-- 
2.14.3

[PATCH v2 1/5] fast-import: rename mem_pool type to mp_block

[Jameson Miller]

This is part of a patch series to extract the memory pool logic in
fast-import into a more generalized version. The existing mem_pool type
maps more closely to a "block of memory" (mp_block) in the more
generalized memory pool. This commit renames the mem_pool to mp_block to
reduce churn in future patches.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 58ef360da4..6c3215d7c3 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -209,8 +209,8 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mem_pool {
-	struct mem_pool *next_pool;
+struct mp_block {
+	struct mp_block *next_block;
 	char *next_free;
 	char *end;
 	uintmax_t space[FLEX_ARRAY]; /* more */
@@ -304,9 +304,9 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
+static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
 static size_t total_allocd;
-static struct mem_pool *mem_pool;
+static struct mp_block *mp_block_head;
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -636,14 +636,14 @@ static unsigned int hc_str(const char *s, size_t len)
 
 static void *pool_alloc(size_t len)
 {
-	struct mem_pool *p;
+	struct mp_block *p;
 	void *r;
 
 	/* round up to a 'uintmax_t' alignment */
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mem_pool; p; p = p->next_pool)
+	for (p = mp_block_head; p; p = p->next_block)
 		if ((p->end - p->next_free >= len))
 			break;
 
@@ -652,12 +652,12 @@ static void *pool_alloc(size_t len)
 			total_allocd += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mem_pool), mem_pool_alloc));
-		p->next_pool = mem_pool;
+		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
+		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
+		p->next_block = mp_block_head;
 		p->next_free = (char *) p->space;
 		p->end = p->next_free + mem_pool_alloc;
-		mem_pool = p;
+		mp_block_head = p;
 	}
 
 	r = p->next_free;
-- 
2.14.3

Re: [PATCH v2 1/5] fast-import: rename mem_pool type to mp_block

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> This is part of a patch series to extract the memory pool logic in
> fast-import into a more generalized version. The existing mem_pool type
> maps more closely to a "block of memory" (mp_block) in the more
> generalized memory pool.

Sounds good.

[PATCH v2 2/5] fast-import: introduce mem_pool type

[Jameson Miller]

Introduce the mem_pool type and wrap the existing mp_block in this new
type. The new mem_pool type will allow for the memory pool logic to be
reused outside of fast-import. This type will be moved into its own file
in a future commit.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 108 +++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 89 insertions(+), 19 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 6c3215d7c3..1262d9e6be 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -216,6 +216,19 @@ struct mp_block {
 	uintmax_t space[FLEX_ARRAY]; /* more */
 };
 
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -304,9 +317,7 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
-static size_t total_allocd;
-static struct mp_block *mp_block_head;
+static struct mem_pool fi_mem_pool =  {0, 2*1024*1024 - sizeof(struct mp_block), 0 };
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -324,6 +335,7 @@ static off_t pack_size;
 /* Table of objects we've written. */
 static unsigned int object_entry_alloc = 5000;
 static struct object_entry_pool *blocks;
+static size_t total_allocd = 0;
 static struct object_entry *object_table[1 << 16];
 static struct mark_set *marks;
 static const char *export_marks_file;
@@ -634,6 +646,60 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
+static struct mp_block *pool_alloc_block()
+{
+	struct mp_block *p;
+
+	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + fi_mem_pool.block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), fi_mem_pool.block_alloc));
+	p->next_block = fi_mem_pool.mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + fi_mem_pool.block_alloc;
+	fi_mem_pool.mp_block = p;
+
+	return p;
+}
+
+/*
+ * Allocates a block of memory with a specific size and
+ * appends it to the memory pool's list of blocks.
+ *
+ * This function is used to allocate blocks with sizes
+ * different than the default "block_alloc" size for the mem_pool.
+ *
+ * There are two use cases:
+ *  1) The initial block allocation for a memory pool.
+ *
+ *  2) large" blocks of a specific size, where the entire memory block
+ *     is going to be used. This means the block will not have any
+ *     available memory for future allocations. The block is placed at
+ *     the end of the list so that it will be the last block searched
+ *     for available space.
+ */
+static struct mp_block *pool_alloc_block_with_size(size_t block_alloc)
+{
+	struct mp_block *p, *block;
+
+	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+
+	block = fi_mem_pool.mp_block;
+	if (block) {
+		while (block->next_block)
+			block = block->next_block;
+
+		block->next_block = p;
+	} else {
+		fi_mem_pool.mp_block = p;
+	}
+
+	p->next_block = NULL;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+
+	return p;
+}
+
 static void *pool_alloc(size_t len)
 {
 	struct mp_block *p;
@@ -643,21 +709,25 @@ static void *pool_alloc(size_t len)
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mp_block_head; p; p = p->next_block)
-		if ((p->end - p->next_free >= len))
-			break;
+	p = fi_mem_pool.mp_block;
+
+	/*
+	 * In performance profiling, there was a minor perf benefit to
+	 * check for available memory in the head block via the if
+	 * statement, and only going through the loop when needed.
+	 */
+	if (p &&
+	   (p->end - p->next_free < len)) {
+		for (p = p->next_block; p; p = p->next_block)
+			if (p->end - p->next_free >= len)
+				break;
+	}
 
 	if (!p) {
-		if (len >= (mem_pool_alloc/2)) {
-			total_allocd += len;
-			return xmalloc(len);
-		}
-		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
-		p->next_block = mp_block_head;
-		p->next_free = (char *) p->space;
-		p->end = p->next_free + mem_pool_alloc;
-		mp_block_head = p;
+		if (len >= (fi_mem_pool.block_alloc / 2))
+			p = pool_alloc_block_with_size(len);
+		else
+			p = pool_alloc_block();
 	}
 
 	r = p->next_free;
@@ -667,7 +737,7 @@ static void *pool_alloc(size_t len)
 
 static void *pool_calloc(size_t count, size_t size)
 {
-	size_t len = count * size;
+	size_t len = st_mult(count, size);
 	void *r = pool_alloc(len);
 	memset(r, 0, len);
 	return r;
@@ -3541,8 +3611,8 @@ int cmd_main(int argc, const char **argv)
 		fprintf(stderr, "Total branches:  %10lu (%10lu loads     )\n", branch_count, branch_load_count);
 		fprintf(stderr, "      marks:     %10" PRIuMAX " (%10" PRIuMAX " unique    )\n", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);
 		fprintf(stderr, "      atoms:     %10u\n", atom_cnt);
-		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);
-		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)(total_allocd/1024));
+		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + fi_mem_pool.pool_alloc + alloc_count*sizeof(struct object_entry))/1024);
+		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)((total_allocd + fi_mem_pool.pool_alloc) /1024));
 		fprintf(stderr, "     objects:    %10" PRIuMAX " KiB\n", (alloc_count*sizeof(struct object_entry))/1024);
 		fprintf(stderr, "---------------------------------------------------------------------\n");
 		pack_report();
-- 
2.14.3

Re: [PATCH v2 2/5] fast-import: introduce mem_pool type

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> Introduce the mem_pool type and wrap the existing mp_block in this new
> type. The new mem_pool type will allow for the memory pool logic to be
> reused outside of fast-import. This type will be moved into its own file
> in a future commit.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>
> ---
>  fast-import.c | 108 +++++++++++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 89 insertions(+), 19 deletions(-)
>
> diff --git a/fast-import.c b/fast-import.c
> index 6c3215d7c3..1262d9e6be 100644
> --- a/fast-import.c
> +++ b/fast-import.c
> @@ -216,6 +216,19 @@ struct mp_block {
>  	uintmax_t space[FLEX_ARRAY]; /* more */
>  };
>  
> +struct mem_pool {
> +	struct mp_block *mp_block;
> +
> +	/*
> +	 * The amount of available memory to grow the pool by.
> +	 * This size does not include the overhead for the mp_block.
> +	 */
> +	size_t block_alloc;
> +
> +	/* The total amount of memory allocated by the pool. */
> +	size_t pool_alloc;
> +};

OK, so the existing fast-import one knows that it only needs a
single instance, but by introducing this structure, we made it
possible to have more than one instance of it, and more importantly,
all the necessary pieces of info to manage it are available to those
who have a pointer to this instance.

>  struct atom_str {
>  	struct atom_str *next_atom;
>  	unsigned short str_len;
> @@ -304,9 +317,7 @@ static int global_argc;
>  static const char **global_argv;
>  
>  /* Memory pools */
> -static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
> -static size_t total_allocd;
> -static struct mp_block *mp_block_head;
> +static struct mem_pool fi_mem_pool =  {0, 2*1024*1024 - sizeof(struct mp_block), 0 };

And this struct instance represents the <list of blocks, block_alloc
and pool_alloc> for fast-import's use, which used to be separate
global variables that are file-scope static here.

Good.

>  /* Atom management */
>  static unsigned int atom_table_sz = 4451;
> @@ -324,6 +335,7 @@ static off_t pack_size;
>  /* Table of objects we've written. */
>  static unsigned int object_entry_alloc = 5000;
>  static struct object_entry_pool *blocks;
> +static size_t total_allocd = 0;

This one is now used as a total across all the mempool instances and
is kept outside the struct, which is OK.

Do not initialize a var in BSS with an explicit "= 0".

> @@ -634,6 +646,60 @@ static unsigned int hc_str(const char *s, size_t len)
>  	return r;
>  }
>  
> +static struct mp_block *pool_alloc_block()

Should spell this as:

	static struct mp_block *pool_alloc_block(void)

But it is somewhat curious; if we are moving to make this reusable,
shouldn't this be accepting "struct mem_pool *pool" from the caller
and using pool->pool_alloc, pool->block_alloc, etc. instead of
always using the global instance, which fi_mem_pool is?

> +{
> +	struct mp_block *p;
> +
> +	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + fi_mem_pool.block_alloc;

This addition, just like the addition on the next line, potentially
overflows and wraps-around, so it is probably a candidate for
st_add(), but IIUC, pool_alloc is only for usage stats, so it may
not be too bad an offence.  In any case, the above is done as close
to the original and is good for a refactoring patch.

> +	p = xmalloc(st_add(sizeof(struct mp_block), fi_mem_pool.block_alloc));
> +	p->next_block = fi_mem_pool.mp_block;
> +	p->next_free = (char *)p->space;
> +	p->end = p->next_free + fi_mem_pool.block_alloc;
> +	fi_mem_pool.mp_block = p;
> +
> +	return p;
> +}

So this is one half of the original pool_alloc(), that allocated a
new block and queued it to the pool when a not-too-large allocation
is requested (the other half that dealt with large allocations
bypassed the pool mechanism altogether).

> +/*
> + * Allocates a block of memory with a specific size and
> + * appends it to the memory pool's list of blocks.
> + *
> + * This function is used to allocate blocks with sizes
> + * different than the default "block_alloc" size for the mem_pool.
> + *
> + * There are two use cases:
> + *  1) The initial block allocation for a memory pool.
> + *
> + *  2) large" blocks of a specific size, where the entire memory block
> + *     is going to be used. This means the block will not have any
> + *     available memory for future allocations. The block is placed at
> + *     the end of the list so that it will be the last block searched
> + *     for available space.

If we know the block won't have any leftover space, what's the point
of "searching for available space" in it in the first place, even if
you make it the last?

> + */
> +static struct mp_block *pool_alloc_block_with_size(size_t block_alloc)
> +{

Same comment on passing a "pool" instance as parameter applies to
this function.

> +	struct mp_block *p, *block;
> +
> +	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + block_alloc;
> +	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
> +
> +	block = fi_mem_pool.mp_block;
> +	if (block) {
> +		while (block->next_block)
> +			block = block->next_block;
> +
> +		block->next_block = p;

If there were a need to append to the end (and also a need to
iterate from the beginning), keep an extra pointer in the "pool"
instance to make it an O(1) operation.  Or perhaps this list can be
managed with list.h?

It is unclear why this and pool_alloc_block() need to exist as
separate functions.  80% of the code are shared between them.

> +	} else {
> +		fi_mem_pool.mp_block = p;
> +	}
> +
> +	p->next_block = NULL;
> +	p->next_free = (char *)p->space;
> +	p->end = p->next_free + block_alloc;
> +
> +	return p;
> +}
> +
>  static void *pool_alloc(size_t len)
>  {
>  	struct mp_block *p;
> @@ -643,21 +709,25 @@ static void *pool_alloc(size_t len)
>  	if (len & (sizeof(uintmax_t) - 1))
>  		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
>  
> -	for (p = mp_block_head; p; p = p->next_block)
> -		if ((p->end - p->next_free >= len))
> -			break;
> +	p = fi_mem_pool.mp_block;
> +
> +	/*
> +	 * In performance profiling, there was a minor perf benefit to
> +	 * check for available memory in the head block via the if
> +	 * statement, and only going through the loop when needed.
> +	 */

Don't mix premature optimization in a refactoring patch, please.

> +	if (p &&
> +	   (p->end - p->next_free < len)) {
> +		for (p = p->next_block; p; p = p->next_block)
> +			if (p->end - p->next_free >= len)
> +				break;
> +	}
>  
>  	if (!p) {
> -		if (len >= (mem_pool_alloc/2)) {
> -			total_allocd += len;
> -			return xmalloc(len);
> -		}
> -		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
> -		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
> -		p->next_block = mp_block_head;
> -		p->next_free = (char *) p->space;
> -		p->end = p->next_free + mem_pool_alloc;
> -		mp_block_head = p;
> +		if (len >= (fi_mem_pool.block_alloc / 2))
> +			p = pool_alloc_block_with_size(len);
> +		else
> +			p = pool_alloc_block();

So we used to fulfill large request directly from xmalloc() but now
we create a new block, which is large enough to fulfill the request
but otherwise unusable for helping later requests, and queue that to
the mem_pool structure.

It _might_ be a justifiable change in behaviour, but is entirely
unexpected from a refactoring patch that wants to "wrap the existing
mp_block in this new type", especially without justifying why in the
proposed log message.

[PATCH v2 3/5] fast-import: update pool_* functions to work on local pool

[Jameson Miller]

Update memory pool functions to work on a passed in mem_pool instead of
the global mem_pool type. This is in preparation for making the memory
pool logic reusable.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 52 ++++++++++++++++++++++++++--------------------------
 1 file changed, 26 insertions(+), 26 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 1262d9e6be..519e1cbd7f 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -646,16 +646,16 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static struct mp_block *pool_alloc_block()
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool)
 {
 	struct mp_block *p;
 
-	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + fi_mem_pool.block_alloc;
-	p = xmalloc(st_add(sizeof(struct mp_block), fi_mem_pool.block_alloc));
-	p->next_block = fi_mem_pool.mp_block;
+	mem_pool->pool_alloc += sizeof(struct mp_block) + mem_pool->block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), mem_pool->block_alloc));
+	p->next_block = mem_pool->mp_block;
 	p->next_free = (char *)p->space;
-	p->end = p->next_free + fi_mem_pool.block_alloc;
-	fi_mem_pool.mp_block = p;
+	p->end = p->next_free + mem_pool->block_alloc;
+	mem_pool->mp_block = p;
 
 	return p;
 }
@@ -676,21 +676,21 @@ static struct mp_block *pool_alloc_block()
  *     the end of the list so that it will be the last block searched
  *     for available space.
  */
-static struct mp_block *pool_alloc_block_with_size(size_t block_alloc)
+static struct mp_block *mem_pool_alloc_block_with_size(struct mem_pool *mem_pool, size_t block_alloc)
 {
 	struct mp_block *p, *block;
 
-	fi_mem_pool.pool_alloc += sizeof(struct mp_block) + block_alloc;
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
 	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
 
-	block = fi_mem_pool.mp_block;
+	block = mem_pool->mp_block;
 	if (block) {
 		while (block->next_block)
 			block = block->next_block;
 
 		block->next_block = p;
 	} else {
-		fi_mem_pool.mp_block = p;
+		mem_pool->mp_block = p;
 	}
 
 	p->next_block = NULL;
@@ -700,7 +700,7 @@ static struct mp_block *pool_alloc_block_with_size(size_t block_alloc)
 	return p;
 }
 
-static void *pool_alloc(size_t len)
+static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
 {
 	struct mp_block *p;
 	void *r;
@@ -709,7 +709,7 @@ static void *pool_alloc(size_t len)
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	p = fi_mem_pool.mp_block;
+	p = mem_pool->mp_block;
 
 	/*
 	 * In performance profiling, there was a minor perf benefit to
@@ -724,10 +724,10 @@ static void *pool_alloc(size_t len)
 	}
 
 	if (!p) {
-		if (len >= (fi_mem_pool.block_alloc / 2))
-			p = pool_alloc_block_with_size(len);
+		if (len >= (mem_pool->block_alloc / 2))
+			p = mem_pool_alloc_block_with_size(mem_pool, len);
 		else
-			p = pool_alloc_block();
+			p = mem_pool_alloc_block(mem_pool);
 	}
 
 	r = p->next_free;
@@ -735,10 +735,10 @@ static void *pool_alloc(size_t len)
 	return r;
 }
 
-static void *pool_calloc(size_t count, size_t size)
+static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
 {
 	size_t len = st_mult(count, size);
-	void *r = pool_alloc(len);
+	void *r = mem_pool_alloc(mem_pool, len);
 	memset(r, 0, len);
 	return r;
 }
@@ -746,7 +746,7 @@ static void *pool_calloc(size_t count, size_t size)
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
-	char *r = pool_alloc(len);
+	char *r = mem_pool_alloc(&fi_mem_pool, len);
 	memcpy(r, s, len);
 	return r;
 }
@@ -755,7 +755,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 {
 	struct mark_set *s = marks;
 	while ((idnum >> s->shift) >= 1024) {
-		s = pool_calloc(1, sizeof(struct mark_set));
+		s = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 		s->shift = marks->shift + 10;
 		s->data.sets[0] = marks;
 		marks = s;
@@ -764,7 +764,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 		uintmax_t i = idnum >> s->shift;
 		idnum -= i << s->shift;
 		if (!s->data.sets[i]) {
-			s->data.sets[i] = pool_calloc(1, sizeof(struct mark_set));
+			s->data.sets[i] = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 			s->data.sets[i]->shift = s->shift - 10;
 		}
 		s = s->data.sets[i];
@@ -802,7 +802,7 @@ static struct atom_str *to_atom(const char *s, unsigned short len)
 		if (c->str_len == len && !strncmp(s, c->str_dat, len))
 			return c;
 
-	c = pool_alloc(sizeof(struct atom_str) + len + 1);
+	c = mem_pool_alloc(&fi_mem_pool, sizeof(struct atom_str) + len + 1);
 	c->str_len = len;
 	memcpy(c->str_dat, s, len);
 	c->str_dat[len] = 0;
@@ -833,7 +833,7 @@ static struct branch *new_branch(const char *name)
 	if (check_refname_format(name, REFNAME_ALLOW_ONELEVEL))
 		die("Branch name doesn't conform to GIT standards: %s", name);
 
-	b = pool_calloc(1, sizeof(struct branch));
+	b = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct branch));
 	b->name = pool_strdup(name);
 	b->table_next_branch = branch_table[hc];
 	b->branch_tree.versions[0].mode = S_IFDIR;
@@ -869,7 +869,7 @@ static struct tree_content *new_tree_content(unsigned int cnt)
 			avail_tree_table[hc] = f->next_avail;
 	} else {
 		cnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;
-		f = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);
+		f = mem_pool_alloc(&fi_mem_pool, sizeof(*t) + sizeof(t->entries[0]) * cnt);
 		f->entry_capacity = cnt;
 	}
 
@@ -2932,7 +2932,7 @@ static void parse_new_tag(const char *arg)
 	enum object_type type;
 	const char *v;
 
-	t = pool_alloc(sizeof(struct tag));
+	t = mem_pool_alloc(&fi_mem_pool, sizeof(struct tag));
 	memset(t, 0, sizeof(struct tag));
 	t->name = pool_strdup(arg);
 	if (last_tag)
@@ -3531,12 +3531,12 @@ int cmd_main(int argc, const char **argv)
 	atom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));
 	branch_table = xcalloc(branch_table_sz, sizeof(struct branch*));
 	avail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));
-	marks = pool_calloc(1, sizeof(struct mark_set));
+	marks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 
 	global_argc = argc;
 	global_argv = argv;
 
-	rc_free = pool_alloc(cmd_save * sizeof(*rc_free));
+	rc_free = mem_pool_alloc(&fi_mem_pool, cmd_save * sizeof(*rc_free));
 	for (i = 0; i < (cmd_save - 1); i++)
 		rc_free[i].next = &rc_free[i + 1];
 	rc_free[cmd_save - 1].next = NULL;
-- 
2.14.3

Re: [PATCH v2 3/5] fast-import: update pool_* functions to work on local pool

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> Update memory pool functions to work on a passed in mem_pool instead of
> the global mem_pool type. This is in preparation for making the memory
> pool logic reusable.

This should be part of 2/5; the same comments to 2/5 I just sent out
would still apply to a patch that is a combined result between 2/5
and 3/5.

Also, if mem_pool_alloc_block() etc. are the desired final names,
using them from the beginning would make the result easier to read
through (both during review and later "log -p").

Thanks.  This round, especially 2/5 (with anticipation of 3/5
already in reader's head), was easier to grok than the previous.

[PATCH v2 4/5] Move the reusable parts of memory pool into its own file

[Jameson Miller]

This moves the reusable parts of the memory pool logic used by
fast-import.c into its own file for use by other components.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 Makefile      |   1 +
 fast-import.c | 118 +---------------------------------------------------------
 mem-pool.c    | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    |  34 +++++++++++++++++
 4 files changed, 139 insertions(+), 117 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

diff --git a/Makefile b/Makefile
index a1d8775adb..1e142b1dd9 100644
--- a/Makefile
+++ b/Makefile
@@ -832,6 +832,7 @@ LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailinfo.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += mem-pool.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
diff --git a/fast-import.c b/fast-import.c
index 519e1cbd7f..36ac5760d6 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -168,6 +168,7 @@ Format of STDIN stream:
 #include "dir.h"
 #include "run-command.h"
 #include "packfile.h"
+#include "mem-pool.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -209,26 +210,6 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mp_block {
-	struct mp_block *next_block;
-	char *next_free;
-	char *end;
-	uintmax_t space[FLEX_ARRAY]; /* more */
-};
-
-struct mem_pool {
-	struct mp_block *mp_block;
-
-	/*
-	 * The amount of available memory to grow the pool by.
-	 * This size does not include the overhead for the mp_block.
-	 */
-	size_t block_alloc;
-
-	/* The total amount of memory allocated by the pool. */
-	size_t pool_alloc;
-};
-
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -646,103 +627,6 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool)
-{
-	struct mp_block *p;
-
-	mem_pool->pool_alloc += sizeof(struct mp_block) + mem_pool->block_alloc;
-	p = xmalloc(st_add(sizeof(struct mp_block), mem_pool->block_alloc));
-	p->next_block = mem_pool->mp_block;
-	p->next_free = (char *)p->space;
-	p->end = p->next_free + mem_pool->block_alloc;
-	mem_pool->mp_block = p;
-
-	return p;
-}
-
-/*
- * Allocates a block of memory with a specific size and
- * appends it to the memory pool's list of blocks.
- *
- * This function is used to allocate blocks with sizes
- * different than the default "block_alloc" size for the mem_pool.
- *
- * There are two use cases:
- *  1) The initial block allocation for a memory pool.
- *
- *  2) large" blocks of a specific size, where the entire memory block
- *     is going to be used. This means the block will not have any
- *     available memory for future allocations. The block is placed at
- *     the end of the list so that it will be the last block searched
- *     for available space.
- */
-static struct mp_block *mem_pool_alloc_block_with_size(struct mem_pool *mem_pool, size_t block_alloc)
-{
-	struct mp_block *p, *block;
-
-	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
-	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
-
-	block = mem_pool->mp_block;
-	if (block) {
-		while (block->next_block)
-			block = block->next_block;
-
-		block->next_block = p;
-	} else {
-		mem_pool->mp_block = p;
-	}
-
-	p->next_block = NULL;
-	p->next_free = (char *)p->space;
-	p->end = p->next_free + block_alloc;
-
-	return p;
-}
-
-static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
-{
-	struct mp_block *p;
-	void *r;
-
-	/* round up to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
-
-	p = mem_pool->mp_block;
-
-	/*
-	 * In performance profiling, there was a minor perf benefit to
-	 * check for available memory in the head block via the if
-	 * statement, and only going through the loop when needed.
-	 */
-	if (p &&
-	   (p->end - p->next_free < len)) {
-		for (p = p->next_block; p; p = p->next_block)
-			if (p->end - p->next_free >= len)
-				break;
-	}
-
-	if (!p) {
-		if (len >= (mem_pool->block_alloc / 2))
-			p = mem_pool_alloc_block_with_size(mem_pool, len);
-		else
-			p = mem_pool_alloc_block(mem_pool);
-	}
-
-	r = p->next_free;
-	p->next_free += len;
-	return r;
-}
-
-static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
-{
-	size_t len = st_mult(count, size);
-	void *r = mem_pool_alloc(mem_pool, len);
-	memset(r, 0, len);
-	return r;
-}
-
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
diff --git a/mem-pool.c b/mem-pool.c
new file mode 100644
index 0000000000..992e354e12
--- /dev/null
+++ b/mem-pool.c
@@ -0,0 +1,103 @@
+/*
+ * Memory Pool implementation logic.
+ */
+
+#include "cache.h"
+#include "mem-pool.h"
+
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool)
+{
+	struct mp_block *p;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + mem_pool->block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), mem_pool->block_alloc));
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + mem_pool->block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+/*
+ * Allocates a block of memory with a specific size and
+ * appends it to the memory pool's list of blocks.
+ *
+ * This function is used to allocate blocks with sizes
+ * different than the default "block_alloc" size for the mem_pool.
+ *
+ * There are two use cases:
+ *  1) The initial block allocation for a memory pool.
+ *
+ *  2) large" blocks of a specific size, where the entire memory block
+ *     is going to be used. This means the block will not have any
+ *     available memory for future allocations. The block is placed at
+ *     the end of the list so that it will be the last block searched
+ *     for available space.
+ */
+static struct mp_block *mem_pool_alloc_block_with_size(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p, *block;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+
+	block = mem_pool->mp_block;
+	if (block) {
+		while (block->next_block)
+			block = block->next_block;
+
+		block->next_block = p;
+	} else {
+		mem_pool->mp_block = p;
+	}
+
+	p->next_block = NULL;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+
+	return p;
+}
+
+void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
+{
+	struct mp_block *p;
+	void *r;
+
+	/* round up to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
+	p = mem_pool->mp_block;
+
+	/*
+	 * In performance profiling, there was a minor perf benefit to
+	 * check for available memory in the head block via the if
+	 * statement, and only going through the loop when needed.
+	 */
+	if (p &&
+	   (p->end - p->next_free < len)) {
+		for (p = p->next_block; p; p = p->next_block)
+			if (p->end - p->next_free >= len)
+				break;
+	}
+
+	if (!p) {
+		if (len >= (mem_pool->block_alloc / 2))
+			p = mem_pool_alloc_block_with_size(mem_pool, len);
+		else
+			p = mem_pool_alloc_block(mem_pool);
+	}
+
+	r = p->next_free;
+	p->next_free += len;
+	return r;
+}
+
+void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
+{
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
+	memset(r, 0, len);
+	return r;
+}
diff --git a/mem-pool.h b/mem-pool.h
new file mode 100644
index 0000000000..829ad58ecf
--- /dev/null
+++ b/mem-pool.h
@@ -0,0 +1,34 @@
+#ifndef MEM_POOL_H
+#define MEM_POOL_H
+
+struct mp_block {
+	struct mp_block *next_block;
+	char *next_free;
+	char *end;
+	uintmax_t space[FLEX_ARRAY]; /* more */
+};
+
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
+/*
+ * Alloc memory from the mem_pool.
+ */
+void *mem_pool_alloc(struct mem_pool *pool, size_t len);
+
+/*
+ * Allocate and zero memory from the memory pool.
+ */
+void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
+
+#endif
-- 
2.14.3

Re: [PATCH v2 4/5] Move the reusable parts of memory pool into its own file

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> This moves the reusable parts of the memory pool logic used by
> fast-import.c into its own file for use by other components.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>
> ---
>  Makefile      |   1 +
>  fast-import.c | 118 +---------------------------------------------------------
>  mem-pool.c    | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  mem-pool.h    |  34 +++++++++++++++++
>  4 files changed, 139 insertions(+), 117 deletions(-)
>  create mode 100644 mem-pool.c
>  create mode 100644 mem-pool.h

This step looks totally uncontroversial, provided that the result
after [1-3/5] is in a reasonable shape ;-)

Hint for other reviewers.  This

    $ git blame -s -b -C HEAD^..HEAD mem-pool.c

can be used to see that most of the lines in this new file are
imported verbatim from fast-import.c at the receiving end.

[PATCH v2 5/5] Expand implementation of mem-pool type

[Jameson Miller]

This commit adds functionality to the mem-pool type that can be
generally useful. This functionality will be used in a future commit.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 mem-pool.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h | 24 ++++++++++++++++++++++++
 2 files changed, 82 insertions(+)

diff --git a/mem-pool.c b/mem-pool.c
index 992e354e12..7d21a7e035 100644
--- a/mem-pool.c
+++ b/mem-pool.c
@@ -5,6 +5,8 @@
 #include "cache.h"
 #include "mem-pool.h"
 
+#define MIN_ALLOC_GROWTH_SIZE 1024 * 1024
+
 static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool)
 {
 	struct mp_block *p;
@@ -59,6 +61,36 @@ static struct mp_block *mem_pool_alloc_block_with_size(struct mem_pool *mem_pool
 	return p;
 }
 
+void mem_pool_init(struct mem_pool **mem_pool, size_t block_alloc, size_t initial_size)
+{
+	if (!(*mem_pool))
+	{
+		if (block_alloc < (MIN_ALLOC_GROWTH_SIZE - sizeof(struct mp_block)))
+			block_alloc = (MIN_ALLOC_GROWTH_SIZE - sizeof(struct mp_block));
+
+		*mem_pool = xmalloc(sizeof(struct mem_pool));
+		(*mem_pool)->pool_alloc = 0;
+		(*mem_pool)->mp_block = 0;
+		(*mem_pool)->block_alloc = block_alloc;
+
+		if (initial_size > 0)
+			mem_pool_alloc_block_with_size(*mem_pool, initial_size);
+	}
+}
+
+void mem_pool_discard(struct mem_pool *mem_pool)
+{
+	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);
+	}
+
+	free(mem_pool);
+}
+
 void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
 {
 	struct mp_block *p;
@@ -101,3 +133,29 @@ 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)
+{
+	struct mp_block *p;
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if ((mem >= ((void *)p->space)) &&
+		    (mem < ((void *)p->end)))
+			return 1;
+
+	return 0;
+}
+
+void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src)
+{
+	struct mp_block **tail = &dst->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;
+
+	dst->pool_alloc += src->pool_alloc;
+	src->pool_alloc = 0;
+	src->mp_block = NULL;
+}
diff --git a/mem-pool.h b/mem-pool.h
index 829ad58ecf..d9e7f21541 100644
--- a/mem-pool.h
+++ b/mem-pool.h
@@ -21,6 +21,17 @@ struct mem_pool {
 	size_t pool_alloc;
 };
 
+/*
+ * Initialize mem_pool with specified parameters for initial size and
+ * how much to grow when a larger memory block is required.
+ */
+void mem_pool_init(struct mem_pool **mem_pool, size_t alloc_growth_size, size_t initial_size);
+
+/*
+ * Discard a memory pool and free all the memory it is responsible for.
+ */
+void mem_pool_discard(struct mem_pool *mem_pool);
+
 /*
  * Alloc memory from the mem_pool.
  */
@@ -31,4 +42,17 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len);
  */
 void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
 
+/*
+ * Move the memory associated with the 'src' pool to the 'dst' pool. The 'src'
+ * pool will be empty and not contain any memory. It still needs to be free'd
+ * with a call to `mem_pool_discard`.
+ */
+void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src);
+
+/*
+ * Check if a memory pointed at by 'mem' is part of the range of
+ * memory managed by the specified mem_pool.
+ */
+int mem_pool_contains(struct mem_pool *mem_pool, void *mem);
+
 #endif
-- 
2.14.3

Re: [PATCH v2 5/5] Expand implementation of mem-pool type

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> +void mem_pool_discard(struct mem_pool *mem_pool)
> +{
> +	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);
> +	}
> +
> +	free(mem_pool);
> +}

This can be used as a (half-)valid justification to the unadvertised
behaviour change made in [2/5] where a large allocation is still
given its own block and connected to a pool (as opposed to bypassing
the pool subsystem altogether).  If an instance of pool does not
keep track of all the pieces of memory mem_pool_alloc() hands out,
mem_pool_discard() cannot be used to reclaim all of the resources.

It however still does not justify how pool_alloc_block_with_size()
appends the new block at the end of the "next" list, which is
scanned for unused spaces when a new request comes in.  "We need to
keep track of them so that disard() can release" would justify a
pointer in the pool struct that chains together allocation blocks,
each of which hosts the memory for a single large allocation request
without extra room to carve out memory for subsequent small
requests.  That pointer does not have to be the usual "mp_block"
pointer.

> diff --git a/mem-pool.h b/mem-pool.h
> index 829ad58ecf..d9e7f21541 100644
> --- a/mem-pool.h
> +++ b/mem-pool.h
> @@ -21,6 +21,17 @@ struct mem_pool {
>  	size_t pool_alloc;
>  };
>  
> +/*
> + * Initialize mem_pool with specified parameters for initial size and
> + * how much to grow when a larger memory block is required.
> + */
> +void mem_pool_init(struct mem_pool **mem_pool, size_t alloc_growth_size, size_t initial_size);
> +
> +/*
> + * Discard a memory pool and free all the memory it is responsible for.
> + */
> +void mem_pool_discard(struct mem_pool *mem_pool);
> +
>  /*
>   * Alloc memory from the mem_pool.
>   */
> @@ -31,4 +42,17 @@ void *mem_pool_alloc(struct mem_pool *pool, size_t len);
>   */
>  void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
>  
> +/*
> + * Move the memory associated with the 'src' pool to the 'dst' pool. The 'src'
> + * pool will be empty and not contain any memory. It still needs to be free'd
> + * with a call to `mem_pool_discard`.
> + */
> +void mem_pool_combine(struct mem_pool *dst, struct mem_pool *src);
> +
> +/*
> + * Check if a memory pointed at by 'mem' is part of the range of
> + * memory managed by the specified mem_pool.
> + */
> +int mem_pool_contains(struct mem_pool *mem_pool, void *mem);
> +
>  #endif

When adding a new "API", we prefer to see its usage demonstrated
with its first user, either in the same patch or in later steps in
the same series.  That would make it easier to evaluate its worth
fairly.

Thanks.

[PATCH v3 0/3] Extract memory pool logic into reusable component

[Jameson Miller]

Changes from v2:

  - Code Review Reactions
  
  - Lifetime management functions for mem_pool will be included in
    future patch series

This patch series extracts the memory pool implementation, currently
used by fast-import, into a generalized component. This memory pool
can then be generally used by any component that needs a pool of
memory.

This patch is in preparation for a change to speed up the loading of
indexes with a large number of cache entries by reducing the number of
malloc() calls. For a rough example of how this component will be used
in this capacity, please see [1].

[1] https://github.com/jamill/git/compare/block_allocation_base...jamill:block_allocation

Jameson Miller (3):
  fast-import: rename mem_pool type to mp_block
  fast-import: introduce mem_pool type
  Move reusable parts of memory pool into its own file

 Makefile      |  1 +
 fast-import.c | 74 +++++++++++------------------------------------------------
 mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    | 34 +++++++++++++++++++++++++++
 4 files changed, 104 insertions(+), 60 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

-- 
2.14.3

[PATCH v3 1/3] fast-import: rename mem_pool type to mp_block

[Jameson Miller]

This is part of a patch series to extract the memory pool logic in
fast-import into a more generalized version. The existing mem_pool type
maps more closely to a "block of memory" (mp_block) in the more
generalized memory pool. This commit renames the mem_pool to mp_block to
reduce churn in future patches.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 58ef360da4..6c3215d7c3 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -209,8 +209,8 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mem_pool {
-	struct mem_pool *next_pool;
+struct mp_block {
+	struct mp_block *next_block;
 	char *next_free;
 	char *end;
 	uintmax_t space[FLEX_ARRAY]; /* more */
@@ -304,9 +304,9 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
+static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
 static size_t total_allocd;
-static struct mem_pool *mem_pool;
+static struct mp_block *mp_block_head;
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -636,14 +636,14 @@ static unsigned int hc_str(const char *s, size_t len)
 
 static void *pool_alloc(size_t len)
 {
-	struct mem_pool *p;
+	struct mp_block *p;
 	void *r;
 
 	/* round up to a 'uintmax_t' alignment */
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mem_pool; p; p = p->next_pool)
+	for (p = mp_block_head; p; p = p->next_block)
 		if ((p->end - p->next_free >= len))
 			break;
 
@@ -652,12 +652,12 @@ static void *pool_alloc(size_t len)
 			total_allocd += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mem_pool), mem_pool_alloc));
-		p->next_pool = mem_pool;
+		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
+		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
+		p->next_block = mp_block_head;
 		p->next_free = (char *) p->space;
 		p->end = p->next_free + mem_pool_alloc;
-		mem_pool = p;
+		mp_block_head = p;
 	}
 
 	r = p->next_free;
-- 
2.14.3

[PATCH v3 2/3] fast-import: introduce mem_pool type

[Jameson Miller]

Introduce the mem_pool type which encapsulates all the information
necessary to manage a pool of memory.This change moves the existing
variables in fast-import used to support the global memory pool to use
this structure.

These changes allow for the multiple instances of a memory pool to
exist and be reused outside of fast-import. In a future commit the
mem_pool type will be moved to its own file.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 80 +++++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 51 insertions(+), 29 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 6c3215d7c3..e85512191c 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -216,6 +216,19 @@ struct mp_block {
 	uintmax_t space[FLEX_ARRAY]; /* more */
 };
 
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -304,9 +317,7 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
-static size_t total_allocd;
-static struct mp_block *mp_block_head;
+static struct mem_pool fi_mem_pool =  {0, 2*1024*1024 - sizeof(struct mp_block), 0 };
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -324,6 +335,7 @@ static off_t pack_size;
 /* Table of objects we've written. */
 static unsigned int object_entry_alloc = 5000;
 static struct object_entry_pool *blocks;
+static size_t total_allocd;
 static struct object_entry *object_table[1 << 16];
 static struct mark_set *marks;
 static const char *export_marks_file;
@@ -634,7 +646,21 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static void *pool_alloc(size_t len)
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
 {
 	struct mp_block *p;
 	void *r;
@@ -643,21 +669,17 @@ static void *pool_alloc(size_t len)
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mp_block_head; p; p = p->next_block)
-		if ((p->end - p->next_free >= len))
-			break;
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if (p->end - p->next_free >= len)
+	       		break;
 
 	if (!p) {
-		if (len >= (mem_pool_alloc/2)) {
-			total_allocd += len;
+		if (len >= (mem_pool->block_alloc / 2)) {
+			mem_pool->pool_alloc += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
-		p->next_block = mp_block_head;
-		p->next_free = (char *) p->space;
-		p->end = p->next_free + mem_pool_alloc;
-		mp_block_head = p;
+
+		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
 	}
 
 	r = p->next_free;
@@ -665,10 +687,10 @@ static void *pool_alloc(size_t len)
 	return r;
 }
 
-static void *pool_calloc(size_t count, size_t size)
+static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
 {
-	size_t len = count * size;
-	void *r = pool_alloc(len);
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
 	memset(r, 0, len);
 	return r;
 }
@@ -676,7 +698,7 @@ static void *pool_calloc(size_t count, size_t size)
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
-	char *r = pool_alloc(len);
+	char *r = mem_pool_alloc(&fi_mem_pool, len);
 	memcpy(r, s, len);
 	return r;
 }
@@ -685,7 +707,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 {
 	struct mark_set *s = marks;
 	while ((idnum >> s->shift) >= 1024) {
-		s = pool_calloc(1, sizeof(struct mark_set));
+		s = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 		s->shift = marks->shift + 10;
 		s->data.sets[0] = marks;
 		marks = s;
@@ -694,7 +716,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 		uintmax_t i = idnum >> s->shift;
 		idnum -= i << s->shift;
 		if (!s->data.sets[i]) {
-			s->data.sets[i] = pool_calloc(1, sizeof(struct mark_set));
+			s->data.sets[i] = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 			s->data.sets[i]->shift = s->shift - 10;
 		}
 		s = s->data.sets[i];
@@ -732,7 +754,7 @@ static struct atom_str *to_atom(const char *s, unsigned short len)
 		if (c->str_len == len && !strncmp(s, c->str_dat, len))
 			return c;
 
-	c = pool_alloc(sizeof(struct atom_str) + len + 1);
+	c = mem_pool_alloc(&fi_mem_pool, sizeof(struct atom_str) + len + 1);
 	c->str_len = len;
 	memcpy(c->str_dat, s, len);
 	c->str_dat[len] = 0;
@@ -763,7 +785,7 @@ static struct branch *new_branch(const char *name)
 	if (check_refname_format(name, REFNAME_ALLOW_ONELEVEL))
 		die("Branch name doesn't conform to GIT standards: %s", name);
 
-	b = pool_calloc(1, sizeof(struct branch));
+	b = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct branch));
 	b->name = pool_strdup(name);
 	b->table_next_branch = branch_table[hc];
 	b->branch_tree.versions[0].mode = S_IFDIR;
@@ -799,7 +821,7 @@ static struct tree_content *new_tree_content(unsigned int cnt)
 			avail_tree_table[hc] = f->next_avail;
 	} else {
 		cnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;
-		f = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);
+		f = mem_pool_alloc(&fi_mem_pool, sizeof(*t) + sizeof(t->entries[0]) * cnt);
 		f->entry_capacity = cnt;
 	}
 
@@ -2862,7 +2884,7 @@ static void parse_new_tag(const char *arg)
 	enum object_type type;
 	const char *v;
 
-	t = pool_alloc(sizeof(struct tag));
+	t = mem_pool_alloc(&fi_mem_pool, sizeof(struct tag));
 	memset(t, 0, sizeof(struct tag));
 	t->name = pool_strdup(arg);
 	if (last_tag)
@@ -3461,12 +3483,12 @@ int cmd_main(int argc, const char **argv)
 	atom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));
 	branch_table = xcalloc(branch_table_sz, sizeof(struct branch*));
 	avail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));
-	marks = pool_calloc(1, sizeof(struct mark_set));
+	marks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 
 	global_argc = argc;
 	global_argv = argv;
 
-	rc_free = pool_alloc(cmd_save * sizeof(*rc_free));
+	rc_free = mem_pool_alloc(&fi_mem_pool, cmd_save * sizeof(*rc_free));
 	for (i = 0; i < (cmd_save - 1); i++)
 		rc_free[i].next = &rc_free[i + 1];
 	rc_free[cmd_save - 1].next = NULL;
@@ -3541,8 +3563,8 @@ int cmd_main(int argc, const char **argv)
 		fprintf(stderr, "Total branches:  %10lu (%10lu loads     )\n", branch_count, branch_load_count);
 		fprintf(stderr, "      marks:     %10" PRIuMAX " (%10" PRIuMAX " unique    )\n", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);
 		fprintf(stderr, "      atoms:     %10u\n", atom_cnt);
-		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);
-		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)(total_allocd/1024));
+		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + fi_mem_pool.pool_alloc + alloc_count*sizeof(struct object_entry))/1024);
+		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)((total_allocd + fi_mem_pool.pool_alloc) /1024));
 		fprintf(stderr, "     objects:    %10" PRIuMAX " KiB\n", (alloc_count*sizeof(struct object_entry))/1024);
 		fprintf(stderr, "---------------------------------------------------------------------\n");
 		pack_report();
-- 
2.14.3

Re: [PATCH v3 2/3] fast-import: introduce mem_pool type

[Eric Sunshine]

On Mon, Mar 26, 2018 at 1:03 PM, Jameson Miller <jamill@microsoft.com> wrote:
> Introduce the mem_pool type which encapsulates all the information
> necessary to manage a pool of memory.This change moves the existing

s/memory\.This/memory. This/

> variables in fast-import used to support the global memory pool to use
> this structure.
>
> These changes allow for the multiple instances of a memory pool to
> exist and be reused outside of fast-import. In a future commit the
> mem_pool type will be moved to its own file.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>

Re: [PATCH v3 2/3] fast-import: introduce mem_pool type

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> Introduce the mem_pool type which encapsulates all the information
> necessary to manage a pool of memory.This change moves the existing
> variables in fast-import used to support the global memory pool to use
> this structure.
>
> These changes allow for the multiple instances of a memory pool to
> exist and be reused outside of fast-import. In a future commit the
> mem_pool type will be moved to its own file.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>
> ---
>  fast-import.c | 80 +++++++++++++++++++++++++++++++++++++----------------------
>  1 file changed, 51 insertions(+), 29 deletions(-)

Thanks, this got much easier to read and reason about.

> @@ -304,9 +317,7 @@ static int global_argc;
>  static const char **global_argv;
>  
>  /* Memory pools */
> -static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
> -static size_t total_allocd;
> -static struct mp_block *mp_block_head;
> +static struct mem_pool fi_mem_pool =  {0, 2*1024*1024 - sizeof(struct mp_block), 0 };
>  
>  /* Atom management */
>  static unsigned int atom_table_sz = 4451;
> @@ -324,6 +335,7 @@ static off_t pack_size;
>  /* Table of objects we've written. */
>  static unsigned int object_entry_alloc = 5000;
>  static struct object_entry_pool *blocks;
> +static size_t total_allocd;

So the design decision made at this step is that pool_alloc field
keeps track of the per-pool allocation, while total_allocd is a sum
across instances of pools.  That sounds appropriate for stats.

> @@ -634,7 +646,21 @@ static unsigned int hc_str(const char *s, size_t len)
>  	return r;
>  }
>  
> -static void *pool_alloc(size_t len)
> +static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
> +{
> +	struct mp_block *p;
> +
> +	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
> +	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
> +	p->next_block = mem_pool->mp_block;
> +	p->next_free = (char *)p->space;
> +	p->end = p->next_free + block_alloc;
> +	mem_pool->mp_block = p;

This, compared to what used to happen in mem_pool_alloc()'s original
code, ignores total_allocd.  I cannot tell if that is an intentional
change or a mistake.

> +
> +	return p;
> +}
> +
> +static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
>  {
>  	struct mp_block *p;
>  	void *r;
> @@ -643,21 +669,17 @@ static void *pool_alloc(size_t len)
>  	if (len & (sizeof(uintmax_t) - 1))
>  		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
>  
> -	for (p = mp_block_head; p; p = p->next_block)
> -		if ((p->end - p->next_free >= len))
> -			break;
> +	for (p = mem_pool->mp_block; p; p = p->next_block)
> +		if (p->end - p->next_free >= len)
> +	       		break;
>  
>  	if (!p) {
> -		if (len >= (mem_pool_alloc/2)) {
> -			total_allocd += len;
> +		if (len >= (mem_pool->block_alloc / 2)) {
> +			mem_pool->pool_alloc += len;
>  			return xmalloc(len);

It is unfair to account this piece of memory to the mem_pool, as we
ended up not carving it out from here.  Did you mean to increment
total_allocd by len instead, perhaps?

And I do agree with the idea in the previous round to make these
oversized pieces of memory allocated here to be freeable via the
mem_pool instance (I only found it questionable to use the main
"here are the list of blocks that we could carve small pieces out"
list), and anticipate that a later step in the series would change
this part to do so.  With that anticipation, I very much appreciate
that this step did not mix that and stayed as close to the original
(except for the possible mis-accounting).  It makes it very clear
what is going on in each separate step in the series.

>  		}
> -		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;

This is what I noticed got lost in the pool-alloc-block helper above.

> -		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
> -		p->next_block = mp_block_head;
> -		p->next_free = (char *) p->space;
> -		p->end = p->next_free + mem_pool_alloc;
> -		mp_block_head = p;
> +
> +		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
>  	}
>  
>  	r = p->next_free;
> @@ -665,10 +687,10 @@ static void *pool_alloc(size_t len)
>  	return r;
>  }
>  
> -static void *pool_calloc(size_t count, size_t size)
> +static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
>  {
> -	size_t len = count * size;
> -	void *r = pool_alloc(len);
> +	size_t len = st_mult(count, size);

Nice ;-)

> +	void *r = mem_pool_alloc(mem_pool, len);
>  	memset(r, 0, len);
>  	return r;
>  }

[PATCH v3 3/3] Move reusable parts of memory pool into its own file

[Jameson Miller]

This moves the reusable parts of the memory pool logic used by
fast-import.c into its own file for use by other components.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 Makefile      |  1 +
 fast-import.c | 70 +----------------------------------------------------------
 mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    | 34 +++++++++++++++++++++++++++++
 4 files changed, 91 insertions(+), 69 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

diff --git a/Makefile b/Makefile
index a1d8775adb..1e142b1dd9 100644
--- a/Makefile
+++ b/Makefile
@@ -832,6 +832,7 @@ LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailinfo.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += mem-pool.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
diff --git a/fast-import.c b/fast-import.c
index e85512191c..12c0058c06 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -168,6 +168,7 @@ Format of STDIN stream:
 #include "dir.h"
 #include "run-command.h"
 #include "packfile.h"
+#include "mem-pool.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -209,26 +210,6 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mp_block {
-	struct mp_block *next_block;
-	char *next_free;
-	char *end;
-	uintmax_t space[FLEX_ARRAY]; /* more */
-};
-
-struct mem_pool {
-	struct mp_block *mp_block;
-
-	/*
-	 * The amount of available memory to grow the pool by.
-	 * This size does not include the overhead for the mp_block.
-	 */
-	size_t block_alloc;
-
-	/* The total amount of memory allocated by the pool. */
-	size_t pool_alloc;
-};
-
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -646,55 +627,6 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
-{
-	struct mp_block *p;
-
-	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
-	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
-	p->next_block = mem_pool->mp_block;
-	p->next_free = (char *)p->space;
-	p->end = p->next_free + block_alloc;
-	mem_pool->mp_block = p;
-
-	return p;
-}
-
-static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
-{
-	struct mp_block *p;
-	void *r;
-
-	/* round up to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
-
-	for (p = mem_pool->mp_block; p; p = p->next_block)
-		if (p->end - p->next_free >= len)
-	       		break;
-
-	if (!p) {
-		if (len >= (mem_pool->block_alloc / 2)) {
-			mem_pool->pool_alloc += len;
-			return xmalloc(len);
-		}
-
-		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
-	}
-
-	r = p->next_free;
-	p->next_free += len;
-	return r;
-}
-
-static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
-{
-	size_t len = st_mult(count, size);
-	void *r = mem_pool_alloc(mem_pool, len);
-	memset(r, 0, len);
-	return r;
-}
-
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
diff --git a/mem-pool.c b/mem-pool.c
new file mode 100644
index 0000000000..389d7af447
--- /dev/null
+++ b/mem-pool.c
@@ -0,0 +1,55 @@
+/*
+ * Memory Pool implementation logic.
+ */
+
+#include "cache.h"
+#include "mem-pool.h"
+
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
+{
+	struct mp_block *p;
+	void *r;
+
+	/* round up to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if (p->end - p->next_free >= len)
+			break;
+
+	if (!p) {
+		if (len >= (mem_pool->block_alloc / 2)) {
+			mem_pool->pool_alloc += len;
+			return xmalloc(len);
+		}
+
+		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
+	}
+
+	r = p->next_free;
+	p->next_free += len;
+	return r;
+}
+
+void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
+{
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
+	memset(r, 0, len);
+	return r;
+}
diff --git a/mem-pool.h b/mem-pool.h
new file mode 100644
index 0000000000..829ad58ecf
--- /dev/null
+++ b/mem-pool.h
@@ -0,0 +1,34 @@
+#ifndef MEM_POOL_H
+#define MEM_POOL_H
+
+struct mp_block {
+	struct mp_block *next_block;
+	char *next_free;
+	char *end;
+	uintmax_t space[FLEX_ARRAY]; /* more */
+};
+
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
+/*
+ * Alloc memory from the mem_pool.
+ */
+void *mem_pool_alloc(struct mem_pool *pool, size_t len);
+
+/*
+ * Allocate and zero memory from the memory pool.
+ */
+void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
+
+#endif
-- 
2.14.3

Re: [PATCH v3 3/3] Move reusable parts of memory pool into its own file

[Junio C Hamano]

Jameson Miller <jamill@microsoft.com> writes:

> This moves the reusable parts of the memory pool logic used by
> fast-import.c into its own file for use by other components.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>
> ---
>  Makefile      |  1 +
>  fast-import.c | 70 +----------------------------------------------------------
>  mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++++
>  mem-pool.h    | 34 +++++++++++++++++++++++++++++
>  4 files changed, 91 insertions(+), 69 deletions(-)
>  create mode 100644 mem-pool.c
>  create mode 100644 mem-pool.h

OK.  This is indeed straight-forward line movements and nothing else,
other than obviously a few static helpers are now extern.

I said I'd anticipate that the allocation that bypasses the pool
subsystem would want to become traceable by the pool subsystem,
which would allow us to free() the pieces of memory allocated
directly with xmalloc() in mem_pool_alloc() instead of leaking.  I
am OK if the structure of this series is to make that change after
these three steps we see here.  When that happens, it will start to
make sense to bill the "this is too big so do not attempt to carve
it out from block, and do not overallocate and make the remainder
available for later requests" to the pool instance mem_pool_alloc()
is working on, as that piece of memory is also known to a specific
pool instance.

After I wrote review for 2/3, I found out that you changed the
meaning of total_allocd (which should probably be described in its
log message).  Unlike the original that counted "total", it now is
used only for memory that is allocated directly by fast-import.c and
does not account for memory obtained by calling mem-pool.

The output routine is changed in 2/3 to add fi_mem_pool's pool_alloc
to it, so billing oversized allocation that does *not* belong to any
specific pool to _some_ pool and ignoring total_allocd would cancel
things out.  It still feels a bit fishy, but I think it is OK.

So all in all, I think we are in no worse shape than the original
(we call it "bug-to-bug compatible" ;-)), and successfully extracted
a reusable piece in a separate file in a clean way so that we can
refine and extend it further.  Nicely done.

Will queue; the proposed log for step 2/3 may want to be a bit
polished, though.

Thanks.

Re: [PATCH v3 3/3] Move reusable parts of memory pool into its own file

[Jameson Miller]

Thank you for the thorough and detailed review - I very much appreciate it.

> I
> am OK if the structure of this series is to make that change after
> these three steps we see here. 

I will add (back) the accounting of large memory blocks in a future patch
series, taking into account your existing feedback. As this patch series did not have
any consumers that "discarded" a memory pool, I decided to wait until I had 
a consumer that used this functionality.

> Will queue; the proposed log for step 2/3 may want to be a bit
> polished, though.

I am away the rest of this week and next week, but will update this patch
series when I get back (Week of April 9th).

Thank you
Jameson

________________________________________
From: Junio C Hamano <jch2355@gmail.com> on behalf of Junio C Hamano <gitster@pobox.com>
Sent: Tuesday, March 27, 2018 12:43 PM
To: Jameson Miller
Cc: git@vger.kernel.org; peff@peff.net
Subject: Re: [PATCH v3 3/3] Move reusable parts of memory pool into its own file 
 
Jameson Miller <jamill@microsoft.com> writes:

> This moves the reusable parts of the memory pool logic used by
> fast-import.c into its own file for use by other components.
>
> Signed-off-by: Jameson Miller <jamill@microsoft.com>
> ---
>  Makefile      |  1 +
>  fast-import.c | 70 +----------------------------------------------------------
>  mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++++
>  mem-pool.h    | 34 +++++++++++++++++++++++++++++
>  4 files changed, 91 insertions(+), 69 deletions(-)
>  create mode 100644 mem-pool.c
>  create mode 100644 mem-pool.h

OK.  This is indeed straight-forward line movements and nothing else,
other than obviously a few static helpers are now extern.

I said I'd anticipate that the allocation that bypasses the pool
subsystem would want to become traceable by the pool subsystem,
which would allow us to free() the pieces of memory allocated
directly with xmalloc() in mem_pool_alloc() instead of leaking.  I
am OK if the structure of this series is to make that change after
these three steps we see here.  When that happens, it will start to
make sense to bill the "this is too big so do not attempt to carve
it out from block, and do not overallocate and make the remainder
available for later requests" to the pool instance mem_pool_alloc()
is working on, as that piece of memory is also known to a specific
pool instance.

After I wrote review for 2/3, I found out that you changed the
meaning of total_allocd (which should probably be described in its
log message).  Unlike the original that counted "total", it now is
used only for memory that is allocated directly by fast-import.c and
does not account for memory obtained by calling mem-pool.

The output routine is changed in 2/3 to add fi_mem_pool's pool_alloc
to it, so billing oversized allocation that does *not* belong to any
specific pool to _some_ pool and ignoring total_allocd would cancel
things out.  It still feels a bit fishy, but I think it is OK.

So all in all, I think we are in no worse shape than the original
(we call it "bug-to-bug compatible" ;-)), and successfully extracted
a reusable piece in a separate file in a clean way so that we can
refine and extend it further.  Nicely done.

Will queue; the proposed log for step 2/3 may want to be a bit
polished, though.

Thanks.

[PATCH v4 0/3] Extract memory pool logic into reusable component

[Jameson Miller]

Thank you everyone for taking the time review and provide feedback on
this patch series.

Changes from v3:

  - Based patch off of new commit, to resolve merge conflict.

  - Updated log message in 2/3 based on feedback.

  - Squashed patch from Ramsay Jones into 2/3 to fix warning from
    sparse.

  - Updated variable names in 2/3 to reflect updated usage of
    variable.

Jameson Miller (3):
  fast-import: rename mem_pool type to mp_block
  fast-import: introduce mem_pool type
  Move reusable parts of memory pool into its own file

 Makefile      |  1 +
 fast-import.c | 77 +++++++++++++----------------------------------------------
 mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    | 34 ++++++++++++++++++++++++++
 4 files changed, 106 insertions(+), 61 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

-- 
2.14.3

RE: [PATCH v4 0/3] Extract memory pool logic into reusable component

[Jameson Miller]

I think this version (V4) should reflect the latest round of feedback. Please let me know if there are any other questions or outstanding work to finish here.

I have submitted a patch series to have a second component use this memory pool [1].

Thank you

[1] https://public-inbox.org/git/20180417163400.3875-2-jamill@microsoft.com/

-----Original Message-----
From: Jameson Miller 
Sent: Wednesday, April 11, 2018 2:38 PM
To: git@vger.kernel.org
Cc: gitster@pobox.com; peff@peff.net; sunshine@sunshineco.com; ramsay@ramsayjones.plus.com; Jameson Miller <jamill@microsoft.com>
Subject: [PATCH v4 0/3] Extract memory pool logic into reusable component

Thank you everyone for taking the time review and provide feedback on this patch series.

Changes from v3:

  - Based patch off of new commit, to resolve merge conflict.

  - Updated log message in 2/3 based on feedback.

  - Squashed patch from Ramsay Jones into 2/3 to fix warning from
    sparse.

  - Updated variable names in 2/3 to reflect updated usage of
    variable.

Jameson Miller (3):
  fast-import: rename mem_pool type to mp_block
  fast-import: introduce mem_pool type
  Move reusable parts of memory pool into its own file

 Makefile      |  1 +
 fast-import.c | 77 +++++++++++++----------------------------------------------
 mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    | 34 ++++++++++++++++++++++++++
 4 files changed, 106 insertions(+), 61 deletions(-)  create mode 100644 mem-pool.c  create mode 100644 mem-pool.h

--
2.14.3

[PATCH v4 1/3] fast-import: rename mem_pool type to mp_block

[Jameson Miller]

This is part of a patch series to extract the memory pool logic in
fast-import into a more generalized version. The existing mem_pool type
maps more closely to a "block of memory" (mp_block) in the more
generalized memory pool. This commit renames the mem_pool to mp_block to
reduce churn in future patches.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 99f8f56e8c..38af0a294b 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -211,8 +211,8 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mem_pool {
-	struct mem_pool *next_pool;
+struct mp_block {
+	struct mp_block *next_block;
 	char *next_free;
 	char *end;
 	uintmax_t space[FLEX_ARRAY]; /* more */
@@ -306,9 +306,9 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
+static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
 static size_t total_allocd;
-static struct mem_pool *mem_pool;
+static struct mp_block *mp_block_head;
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -638,14 +638,14 @@ static unsigned int hc_str(const char *s, size_t len)
 
 static void *pool_alloc(size_t len)
 {
-	struct mem_pool *p;
+	struct mp_block *p;
 	void *r;
 
 	/* round up to a 'uintmax_t' alignment */
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mem_pool; p; p = p->next_pool)
+	for (p = mp_block_head; p; p = p->next_block)
 		if ((p->end - p->next_free >= len))
 			break;
 
@@ -654,12 +654,12 @@ static void *pool_alloc(size_t len)
 			total_allocd += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mem_pool), mem_pool_alloc));
-		p->next_pool = mem_pool;
+		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
+		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
+		p->next_block = mp_block_head;
 		p->next_free = (char *) p->space;
 		p->end = p->next_free + mem_pool_alloc;
-		mem_pool = p;
+		mp_block_head = p;
 	}
 
 	r = p->next_free;
-- 
2.14.3

[PATCH v4 2/3] fast-import: introduce mem_pool type

[Jameson Miller]

Introduce the mem_pool type which encapsulates all the information necessary to
manage a pool of memory. This change moves the existing variables in
fast-import used to support the global memory pool to use this structure. It
also renames variables that are no longer used by memory pools to reflect their
more scoped usage.

These changes allow for the multiple instances of a memory pool to
exist and be reused outside of fast-import. In a future commit the
mem_pool type will be moved to its own file.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 fast-import.c | 81 ++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 52 insertions(+), 29 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 38af0a294b..48d4797ab5 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -218,6 +218,19 @@ struct mp_block {
 	uintmax_t space[FLEX_ARRAY]; /* more */
 };
 
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -306,9 +319,8 @@ static int global_argc;
 static const char **global_argv;
 
 /* Memory pools */
-static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mp_block);
-static size_t total_allocd;
-static struct mp_block *mp_block_head;
+static struct mem_pool fi_mem_pool =  {NULL, 2*1024*1024 -
+				       sizeof(struct mp_block), 0 };
 
 /* Atom management */
 static unsigned int atom_table_sz = 4451;
@@ -343,6 +355,7 @@ static unsigned int tree_entry_alloc = 1000;
 static void *avail_tree_entry;
 static unsigned int avail_tree_table_sz = 100;
 static struct avail_tree_content **avail_tree_table;
+static size_t tree_entry_allocd;
 static struct strbuf old_tree = STRBUF_INIT;
 static struct strbuf new_tree = STRBUF_INIT;
 
@@ -636,7 +649,21 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static void *pool_alloc(size_t len)
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
 {
 	struct mp_block *p;
 	void *r;
@@ -645,21 +672,17 @@ static void *pool_alloc(size_t len)
 	if (len & (sizeof(uintmax_t) - 1))
 		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 
-	for (p = mp_block_head; p; p = p->next_block)
-		if ((p->end - p->next_free >= len))
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if (p->end - p->next_free >= len)
 			break;
 
 	if (!p) {
-		if (len >= (mem_pool_alloc/2)) {
-			total_allocd += len;
+		if (len >= (mem_pool->block_alloc / 2)) {
+			mem_pool->pool_alloc += len;
 			return xmalloc(len);
 		}
-		total_allocd += sizeof(struct mp_block) + mem_pool_alloc;
-		p = xmalloc(st_add(sizeof(struct mp_block), mem_pool_alloc));
-		p->next_block = mp_block_head;
-		p->next_free = (char *) p->space;
-		p->end = p->next_free + mem_pool_alloc;
-		mp_block_head = p;
+
+		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
 	}
 
 	r = p->next_free;
@@ -667,10 +690,10 @@ static void *pool_alloc(size_t len)
 	return r;
 }
 
-static void *pool_calloc(size_t count, size_t size)
+static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
 {
-	size_t len = count * size;
-	void *r = pool_alloc(len);
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
 	memset(r, 0, len);
 	return r;
 }
@@ -678,7 +701,7 @@ static void *pool_calloc(size_t count, size_t size)
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
-	char *r = pool_alloc(len);
+	char *r = mem_pool_alloc(&fi_mem_pool, len);
 	memcpy(r, s, len);
 	return r;
 }
@@ -687,7 +710,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 {
 	struct mark_set *s = marks;
 	while ((idnum >> s->shift) >= 1024) {
-		s = pool_calloc(1, sizeof(struct mark_set));
+		s = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 		s->shift = marks->shift + 10;
 		s->data.sets[0] = marks;
 		marks = s;
@@ -696,7 +719,7 @@ static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 		uintmax_t i = idnum >> s->shift;
 		idnum -= i << s->shift;
 		if (!s->data.sets[i]) {
-			s->data.sets[i] = pool_calloc(1, sizeof(struct mark_set));
+			s->data.sets[i] = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 			s->data.sets[i]->shift = s->shift - 10;
 		}
 		s = s->data.sets[i];
@@ -734,7 +757,7 @@ static struct atom_str *to_atom(const char *s, unsigned short len)
 		if (c->str_len == len && !strncmp(s, c->str_dat, len))
 			return c;
 
-	c = pool_alloc(sizeof(struct atom_str) + len + 1);
+	c = mem_pool_alloc(&fi_mem_pool, sizeof(struct atom_str) + len + 1);
 	c->str_len = len;
 	memcpy(c->str_dat, s, len);
 	c->str_dat[len] = 0;
@@ -765,7 +788,7 @@ static struct branch *new_branch(const char *name)
 	if (check_refname_format(name, REFNAME_ALLOW_ONELEVEL))
 		die("Branch name doesn't conform to GIT standards: %s", name);
 
-	b = pool_calloc(1, sizeof(struct branch));
+	b = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct branch));
 	b->name = pool_strdup(name);
 	b->table_next_branch = branch_table[hc];
 	b->branch_tree.versions[0].mode = S_IFDIR;
@@ -801,7 +824,7 @@ static struct tree_content *new_tree_content(unsigned int cnt)
 			avail_tree_table[hc] = f->next_avail;
 	} else {
 		cnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;
-		f = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);
+		f = mem_pool_alloc(&fi_mem_pool, sizeof(*t) + sizeof(t->entries[0]) * cnt);
 		f->entry_capacity = cnt;
 	}
 
@@ -846,7 +869,7 @@ static struct tree_entry *new_tree_entry(void)
 
 	if (!avail_tree_entry) {
 		unsigned int n = tree_entry_alloc;
-		total_allocd += n * sizeof(struct tree_entry);
+		tree_entry_allocd += n * sizeof(struct tree_entry);
 		ALLOC_ARRAY(e, n);
 		avail_tree_entry = e;
 		while (n-- > 1) {
@@ -2867,7 +2890,7 @@ static void parse_new_tag(const char *arg)
 	enum object_type type;
 	const char *v;
 
-	t = pool_alloc(sizeof(struct tag));
+	t = mem_pool_alloc(&fi_mem_pool, sizeof(struct tag));
 	memset(t, 0, sizeof(struct tag));
 	t->name = pool_strdup(arg);
 	if (last_tag)
@@ -3466,12 +3489,12 @@ int cmd_main(int argc, const char **argv)
 	atom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));
 	branch_table = xcalloc(branch_table_sz, sizeof(struct branch*));
 	avail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));
-	marks = pool_calloc(1, sizeof(struct mark_set));
+	marks = mem_pool_calloc(&fi_mem_pool, 1, sizeof(struct mark_set));
 
 	global_argc = argc;
 	global_argv = argv;
 
-	rc_free = pool_alloc(cmd_save * sizeof(*rc_free));
+	rc_free = mem_pool_alloc(&fi_mem_pool, cmd_save * sizeof(*rc_free));
 	for (i = 0; i < (cmd_save - 1); i++)
 		rc_free[i].next = &rc_free[i + 1];
 	rc_free[cmd_save - 1].next = NULL;
@@ -3545,8 +3568,8 @@ int cmd_main(int argc, const char **argv)
 		fprintf(stderr, "Total branches:  %10lu (%10lu loads     )\n", branch_count, branch_load_count);
 		fprintf(stderr, "      marks:     %10" PRIuMAX " (%10" PRIuMAX " unique    )\n", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);
 		fprintf(stderr, "      atoms:     %10u\n", atom_cnt);
-		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);
-		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)(total_allocd/1024));
+		fprintf(stderr, "Memory total:    %10" PRIuMAX " KiB\n", (tree_entry_allocd + fi_mem_pool.pool_alloc + alloc_count*sizeof(struct object_entry))/1024);
+		fprintf(stderr, "       pools:    %10lu KiB\n", (unsigned long)((tree_entry_allocd + fi_mem_pool.pool_alloc) /1024));
 		fprintf(stderr, "     objects:    %10" PRIuMAX " KiB\n", (alloc_count*sizeof(struct object_entry))/1024);
 		fprintf(stderr, "---------------------------------------------------------------------\n");
 		pack_report();
-- 
2.14.3

[PATCH v4 3/3] Move reusable parts of memory pool into its own file

[Jameson Miller]

This moves the reusable parts of the memory pool logic used by
fast-import.c into its own file for use by other components.

Signed-off-by: Jameson Miller <jamill@microsoft.com>
---
 Makefile      |  1 +
 fast-import.c | 70 +----------------------------------------------------------
 mem-pool.c    | 55 ++++++++++++++++++++++++++++++++++++++++++++++
 mem-pool.h    | 34 +++++++++++++++++++++++++++++
 4 files changed, 91 insertions(+), 69 deletions(-)
 create mode 100644 mem-pool.c
 create mode 100644 mem-pool.h

diff --git a/Makefile b/Makefile
index f181687250..5aa4f8064f 100644
--- a/Makefile
+++ b/Makefile
@@ -844,6 +844,7 @@ LIB_OBJS += log-tree.o
 LIB_OBJS += mailinfo.o
 LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
+LIB_OBJS += mem-pool.o
 LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
diff --git a/fast-import.c b/fast-import.c
index 48d4797ab5..05d1079d23 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -170,6 +170,7 @@ Format of STDIN stream:
 #include "run-command.h"
 #include "packfile.h"
 #include "object-store.h"
+#include "mem-pool.h"
 
 #define PACK_ID_BITS 16
 #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@ -211,26 +212,6 @@ struct last_object {
 	unsigned no_swap : 1;
 };
 
-struct mp_block {
-	struct mp_block *next_block;
-	char *next_free;
-	char *end;
-	uintmax_t space[FLEX_ARRAY]; /* more */
-};
-
-struct mem_pool {
-	struct mp_block *mp_block;
-
-	/*
-	 * The amount of available memory to grow the pool by.
-	 * This size does not include the overhead for the mp_block.
-	 */
-	size_t block_alloc;
-
-	/* The total amount of memory allocated by the pool. */
-	size_t pool_alloc;
-};
-
 struct atom_str {
 	struct atom_str *next_atom;
 	unsigned short str_len;
@@ -649,55 +630,6 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
-{
-	struct mp_block *p;
-
-	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
-	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
-	p->next_block = mem_pool->mp_block;
-	p->next_free = (char *)p->space;
-	p->end = p->next_free + block_alloc;
-	mem_pool->mp_block = p;
-
-	return p;
-}
-
-static void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
-{
-	struct mp_block *p;
-	void *r;
-
-	/* round up to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
-
-	for (p = mem_pool->mp_block; p; p = p->next_block)
-		if (p->end - p->next_free >= len)
-			break;
-
-	if (!p) {
-		if (len >= (mem_pool->block_alloc / 2)) {
-			mem_pool->pool_alloc += len;
-			return xmalloc(len);
-		}
-
-		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
-	}
-
-	r = p->next_free;
-	p->next_free += len;
-	return r;
-}
-
-static void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
-{
-	size_t len = st_mult(count, size);
-	void *r = mem_pool_alloc(mem_pool, len);
-	memset(r, 0, len);
-	return r;
-}
-
 static char *pool_strdup(const char *s)
 {
 	size_t len = strlen(s) + 1;
diff --git a/mem-pool.c b/mem-pool.c
new file mode 100644
index 0000000000..389d7af447
--- /dev/null
+++ b/mem-pool.c
@@ -0,0 +1,55 @@
+/*
+ * Memory Pool implementation logic.
+ */
+
+#include "cache.h"
+#include "mem-pool.h"
+
+static struct mp_block *mem_pool_alloc_block(struct mem_pool *mem_pool, size_t block_alloc)
+{
+	struct mp_block *p;
+
+	mem_pool->pool_alloc += sizeof(struct mp_block) + block_alloc;
+	p = xmalloc(st_add(sizeof(struct mp_block), block_alloc));
+	p->next_block = mem_pool->mp_block;
+	p->next_free = (char *)p->space;
+	p->end = p->next_free + block_alloc;
+	mem_pool->mp_block = p;
+
+	return p;
+}
+
+void *mem_pool_alloc(struct mem_pool *mem_pool, size_t len)
+{
+	struct mp_block *p;
+	void *r;
+
+	/* round up to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
+	for (p = mem_pool->mp_block; p; p = p->next_block)
+		if (p->end - p->next_free >= len)
+			break;
+
+	if (!p) {
+		if (len >= (mem_pool->block_alloc / 2)) {
+			mem_pool->pool_alloc += len;
+			return xmalloc(len);
+		}
+
+		p = mem_pool_alloc_block(mem_pool, mem_pool->block_alloc);
+	}
+
+	r = p->next_free;
+	p->next_free += len;
+	return r;
+}
+
+void *mem_pool_calloc(struct mem_pool *mem_pool, size_t count, size_t size)
+{
+	size_t len = st_mult(count, size);
+	void *r = mem_pool_alloc(mem_pool, len);
+	memset(r, 0, len);
+	return r;
+}
diff --git a/mem-pool.h b/mem-pool.h
new file mode 100644
index 0000000000..829ad58ecf
--- /dev/null
+++ b/mem-pool.h
@@ -0,0 +1,34 @@
+#ifndef MEM_POOL_H
+#define MEM_POOL_H
+
+struct mp_block {
+	struct mp_block *next_block;
+	char *next_free;
+	char *end;
+	uintmax_t space[FLEX_ARRAY]; /* more */
+};
+
+struct mem_pool {
+	struct mp_block *mp_block;
+
+	/*
+	 * The amount of available memory to grow the pool by.
+	 * This size does not include the overhead for the mp_block.
+	 */
+	size_t block_alloc;
+
+	/* The total amount of memory allocated by the pool. */
+	size_t pool_alloc;
+};
+
+/*
+ * Alloc memory from the mem_pool.
+ */
+void *mem_pool_alloc(struct mem_pool *pool, size_t len);
+
+/*
+ * Allocate and zero memory from the memory pool.
+ */
+void *mem_pool_calloc(struct mem_pool *pool, size_t count, size_t size);
+
+#endif
-- 
2.14.3