{"thread":{"id":"10755","subject":"[PATCH 04/11] Allow pooled nodes to be recycled back onto a free list","startedAt":"2007-11-09T11:06:19Z","lastAt":"2007-11-09T22:27:39Z","messageCount":2,"participants":["Shawn O. Pearce","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":11},"messages":[{"id":"59024","messageId":"20071109110619.GD19368@spearce.org","threadId":"10755","inReplyTo":null,"subject":"[PATCH 04/11] Allow pooled nodes to be recycled back onto a free list","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-11-09T11:06:19Z","receivedAt":"2007-11-09T11:06:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"In some cases and for some node types a caller may have used one of\nour allocated nodes for some temporary usage and then wants to return\nit back to the available free list.  We now define a function that\nwill thread the object onto the front of a free list, which will be\nused only after the current block has been exhausted.\n\nWe hold off on looking at the free list until we are sure the current\nblock is empty.  This saves about 1000 tests of the (usually empty)\nfree list per block.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n alloc.c |   23 +++++++++++++++++++++--\n 1 files changed, 21 insertions(+), 2 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex aa429ec..5737a73 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -26,6 +26,7 @@ struct node_block\n struct node_pool\n {\n \tstruct node_block *block_list;\n+\tvoid *free_list;\n \tchar *base;\n \tsize_t nr;\n };\n@@ -38,15 +39,22 @@ struct node_pool\n \n static void report(const char* name, struct node_pool *p, size_t sz)\n {\n-\tunsigned int count = 0;\n+\tunsigned int count = 0, free = 0;\n \tstruct node_block *b;\n+\tvoid **f;\n \n \tfor (b = p->block_list; b; b = b->next)\n \t\tcount += BLOCKING;\n+\tfor (f = p->free_list; f; f = *f)\n+\t\tfree++;\n+\tfree += p->nr;\n \tcount -= p->nr;\n \n \tsz = (count * sz) >> 10;\n-\tfprintf(stderr, \"%10s: %8u (\" SZ_FMT \" kB)\\n\", name, count, sz);\n+\tfprintf(stderr, \"%10s: %8u (\" SZ_FMT \" kB)\", name, count, sz);\n+\tif (free)\n+\t\tfprintf(stderr, \", %8u on free list\", free);\n+\tfputc('\\n', stderr);\n }\n \n #undef SZ_FMT\n@@ -59,6 +67,12 @@ void *alloc_##name##_node(void)\t\t\t\t\t\\\n \t\t\t\t\t\t\t\t\\\n \tif (!name##_pool.nr) {\t\t\t\t\t\\\n \t\tstruct node_block *b;\t\t\t\t\\\n+\t\tif (name##_pool.free_list) {\t\t\t\\\n+\t\t\tret = name##_pool.free_list;\t\t\\\n+\t\t\tname##_pool.free_list = *((void**)ret);\t\\\n+\t\t\tmemset(ret, 0, sizeof(t));\t\t\\\n+\t\t\treturn ret;\t\t\t\t\\\n+\t\t}\t\t\t\t\t\t\\\n \t\tb = xmalloc(sizeof(*b) + BLOCKING * sizeof(t));\t\\\n \t\tb->next = name##_pool.block_list;\t\t\\\n \t\tname##_pool.block_list = b;\t\t\t\\\n@@ -71,6 +85,11 @@ void *alloc_##name##_node(void)\t\t\t\t\t\\\n \tmemset(ret, 0, sizeof(t));\t\t\t\t\\\n \treturn ret;\t\t\t\t\t\t\\\n }\t\t\t\t\t\t\t\t\\\n+void free_##name##_node(void *n)\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\t*((void**)n) = name##_pool.free_list;\t\t\t\\\n+\tname##_pool.free_list = n;\t\t\t\t\\\n+}\t\t\t\t\t\t\t\t\\\n static void report_##name(void)\t\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\\\n \treport(#name, &name##_pool, sizeof(t));\t\t\t\\\n-- \n1.5.3.5.1622.g41d10\n"},{"id":"59130","messageId":"7v1wazrr50.fsf@gitster.siamese.dyndns.org","threadId":"10755","inReplyTo":"20071109110619.GD19368@spearce.org","subject":"Re: [PATCH 04/11] Allow pooled nodes to be recycled back onto a free list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-09T22:27:39Z","receivedAt":"2007-11-09T22:27:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> In some cases and for some node types a caller may have used one of\n> our allocated nodes for some temporary usage and then wants to return\n> it back to the available free list.  We now define a function that\n> will thread the object onto the front of a free list, which will be\n> used only after the current block has been exhausted.\n>\n> We hold off on looking at the free list until we are sure the current\n> block is empty.  This saves about 1000 tests of the (usually empty)\n> free list per block.\n>\n> Signed-off-by: Shawn O. Pearce <spearce@spearce.org>\n\n> +void free_##name##_node(void *n)\t\t\t\t\\\n> +{\t\t\t\t\t\t\t\t\\\n> +\t*((void**)n) = name##_pool.free_list;\t\t\t\\\n> +\tname##_pool.free_list = n;\t\t\t\t\\\n> +}\t\t\t\t\t\t\t\t\\\n>  static void report_##name(void)\t\t\t\t\t\\\n>  {\t\t\t\t\t\t\t\t\\\n>  \treport(#name, &name##_pool, sizeof(t));\t\t\t\\\n\nI wonder how well this will interact with object scrubbing.  A\nfreed node is still in the array in the block bucket and the\nscrubber walks the array without skipping any freed node, but\nthe threading pointer already scribbled on the first\nsizeof(void**) bytes on the object memory.  Worse, the caller\nmay say \"Hey, I am freeing this node, so I'll bzero() it before\nreturning it to the pool\", without realizing that the scrubber\nmay still act on that freed node buffer.\n\nThe rules for a \"class designer\" on freeing a temporary node\nwith this implementation as I understand it is:\n\n - do assume free_all will call scrubber on freed nodes;\n\n - do not have anything your scrubber needs to access near the\n   beginning of the nodes managed by alloc.c API;\n\n - do not clobber anything scrubber needs to access when freeing\n   a node.\n\nFor struct object and its descendant classes, I think this is a\nnon issue -- the first bytes in the structure are the flags and\nsha1[] and the current implementation of the scrubbers would not\nlook at these fields.\n\nBut it does look like a risk in the future.\n"}]}