summaryrefslogtreecommitdiffstats
path: root/src/kmk/alloccache.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/kmk/alloccache.c259
1 files changed, 259 insertions, 0 deletions
diff --git a/src/kmk/alloccache.c b/src/kmk/alloccache.c
new file mode 100644
index 0000000..54c28d5
--- /dev/null
+++ b/src/kmk/alloccache.c
@@ -0,0 +1,259 @@
+/* $Id: alloccache.c 3141 2018-03-14 21:58:32Z bird $ */
+/** @file
+ * alloccache - Fixed sized allocation cache.
+ *
+ * The rational for using an allocation cache, is that it is way faster
+ * than malloc+free on most systems. It may be more efficient as well,
+ * depending on the way the heap implementes small allocations. Also,
+ * with the incdep.c code being threaded, all heaps (except for MSC)
+ * ran into severe lock contention issues since both the main thread
+ * and the incdep worker thread was allocating a crazy amount of tiny
+ * allocations (struct dep, struct nameseq, ++).
+ *
+ * Darwin also showed a significant amount of time spent just executing
+ * free(), which is kind of silly. The alloccache helps a bit here too.
+ */
+
+/*
+ * Copyright (c) 2008-2010 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
+ *
+ * This file is part of kBuild.
+ *
+ * kBuild is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * kBuild is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with kBuild. If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+/*******************************************************************************
+* Header Files *
+*******************************************************************************/
+#include "makeint.h"
+#include "filedef.h"
+#include "dep.h"
+#include "debug.h"
+#include <assert.h>
+
+
+#ifdef CONFIG_WITH_ALLOC_CACHES
+
+/* Free am item.
+ This was not inlined because of aliasing issues arrising with GCC.
+ It is also in a separate file for this reason (it used to be in misc.c
+ but since free_dep_chain() was using it there, we ran the risk of it
+ being inlined and gcc screwing up). */
+void
+alloccache_free (struct alloccache *cache, void *item)
+{
+#ifndef CONFIG_WITH_ALLOCCACHE_DEBUG
+ struct alloccache_free_ent *f = (struct alloccache_free_ent *)item;
+# if 0 /*ndef NDEBUG*/
+ struct alloccache_free_ent *c;
+ unsigned int i = 0;
+ for (c = cache->free_head; c != NULL; c = c->next, i++)
+ MY_ASSERT_MSG (c != f && i < 0x10000000,
+ ("i=%u total_count=%u\n", i, cache->total_count));
+# endif
+
+ f->next = cache->free_head;
+ cache->free_head = f;
+ MAKE_STATS(cache->free_count++;);
+#else /* CONFIG_WITH_ALLOCCACHE_DEBUG */
+
+ struct alloccache **ppcache = (struct alloccache **)item - 1;
+ MY_ASSERT_MSG (*ppcache == cache, ("*ppcache=%p cache=%p item=%p\n", *ppcache, cache, item));
+ *ppcache = NULL;
+ free(ppcache);
+#endif /* CONFIG_WITH_ALLOCCACHE_DEBUG */
+}
+
+/* Default allocator. */
+static void *
+alloccache_default_grow_alloc(void *ignore, unsigned int size)
+{
+ return xmalloc (size);
+}
+
+/* Worker for growing the cache. */
+struct alloccache_free_ent *
+alloccache_alloc_grow (struct alloccache *cache)
+{
+#ifndef CONFIG_WITH_ALLOCCACHE_DEBUG
+ void *item;
+ unsigned int items = (64*1024 - 32) / cache->size;
+ cache->free_start = cache->grow_alloc (cache->grow_arg, items * cache->size);
+ cache->free_end = cache->free_start + items * cache->size;
+ cache->total_count+= items;
+
+# ifndef NDEBUG /* skip the first item so the heap can detect free(). */
+ cache->total_count--;
+ cache->free_start += cache->size;
+# endif
+
+ item = cache->free_start;
+ cache->free_start += cache->size;
+ /* caller counts */
+ return (struct alloccache_free_ent *)item;
+#else /* CONFIG_WITH_ALLOCCACHE_DEBUG */
+
+ /* Prefix the allocation with a cache pointer so alloccahce_free can better
+ catch incorrect calls. */
+ struct alloccache **ppcache = (struct alloccache **)xmalloc(sizeof(*ppcache) + cache->size);
+ *ppcache = cache;
+ return (struct alloccache_free_ent *)(ppcache + 1);
+#endif /* CONFIG_WITH_ALLOCCACHE_DEBUG */
+}
+
+/* List of alloc caches, for printing. */
+static struct alloccache *alloccache_head = NULL;
+
+/* Initializes an alloc cache */
+void
+alloccache_init (struct alloccache *cache, unsigned int size, const char *name,
+ void *(*grow_alloc)(void *grow_arg, unsigned int size), void *grow_arg)
+{
+ unsigned act_size;
+
+ /* ensure OK alignment and min sizeof (struct alloccache_free_ent). */
+ if (size <= sizeof (struct alloccache_free_ent))
+ act_size = sizeof (struct alloccache_free_ent);
+ else if (size <= 32)
+ {
+ act_size = 4;
+ while (act_size < size)
+ act_size <<= 1;
+ }
+ else
+ act_size = (size + 31U) & ~(size_t)31;
+
+ /* align the structure. */
+ cache->free_start = NULL;
+ cache->free_end = NULL;
+ cache->free_head = NULL;
+ cache->size = act_size;
+ cache->total_count = 0;
+ cache->alloc_count = 0;
+ cache->free_count = 0;
+ cache->name = name;
+ cache->grow_arg = grow_arg;
+ cache->grow_alloc = grow_alloc ? grow_alloc : alloccache_default_grow_alloc;
+
+ /* link it. */
+ cache->next = alloccache_head;
+ alloccache_head = cache;
+}
+
+/* Terminate an alloc cache, free all the memory it contains. */
+void
+alloccache_term (struct alloccache *cache,
+ void (*term_free)(void *term_arg, void *ptr, unsigned int size), void *term_arg)
+{
+ /*cache->size = 0;*/
+ (void)cache;
+ (void)term_free;
+ (void)term_arg;
+ /* FIXME: Implement memory segment tracking and cleanup. */
+}
+
+/* Joins to caches, unlinking the 2nd one. */
+void
+alloccache_join (struct alloccache *cache, struct alloccache *eat)
+{
+ assert (cache->size == eat->size);
+
+#if 0 /* probably a waste of time */ /* FIXME: Optimize joining, avoid all list walking. */
+ /* add the free list... */
+ if (eat->free_head)
+ {
+ unsigned int eat_in_use = eat->alloc_count - eat->free_count;
+ unsigned int dst_in_use = cache->alloc_count - cache->free_count;
+ if (!cache->free_head)
+ cache->free_head = eat->free_head;
+ else if (eat->total_count - eat_in_use < cache->total_count - dst_ins_use)
+ {
+ struct alloccache_free_ent *last = eat->free_head;
+ while (last->next)
+ last = last->next;
+ last->next = cache->free_head;
+ cache->free_head = eat->free_head;
+ }
+ else
+ {
+ struct alloccache_free_ent *last = cache->free_head;
+ while (last->next)
+ last = last->next;
+ last->next = eat->free_head;
+ }
+ }
+
+ /* ... and the free space. */
+ while (eat->free_start != eat->free_end)
+ {
+ struct alloccache_free_ent *f = (struct alloccache_free_ent *)eat->free_start;
+ eat->free_start += eat->size;
+ f->next = cache->free_head;
+ cache->free_head = f;
+ }
+
+ /* and statistics */
+ cache->alloc_count += eat->alloc_count;
+ cache->free_count += eat->free_count;
+#else
+ /* and statistics */
+ cache->alloc_count += eat->alloc_count;
+ cache->free_count += eat->free_count;
+#endif
+ cache->total_count += eat->total_count;
+
+ /* unlink and disable the eat cache */
+ if (alloccache_head == eat)
+ alloccache_head = eat->next;
+ else
+ {
+ struct alloccache *cur = alloccache_head;
+ while (cur->next != eat)
+ cur = cur->next;
+ assert (cur && cur->next == eat);
+ cur->next = eat->next;
+ }
+
+ eat->size = 0;
+ eat->free_end = eat->free_start = NULL;
+ eat->free_head = NULL;
+}
+
+/* Print one alloc cache. */
+void
+alloccache_print (struct alloccache *cache)
+{
+ printf (_("\n# Alloc Cache: %s\n"
+ "# Items: size = %-3u total = %-6u"),
+ cache->name, cache->size, cache->total_count);
+ MAKE_STATS(printf (_(" in-use = %-6lu"),
+ cache->alloc_count - cache->free_count););
+ MAKE_STATS(printf (_("\n# alloc calls = %-7lu free calls = %-7lu"),
+ cache->alloc_count, cache->free_count););
+ printf ("\n");
+}
+
+/* Print all alloc caches. */
+void
+alloccache_print_all (void)
+{
+ struct alloccache *cur;
+ puts ("");
+ for (cur = alloccache_head; cur; cur = cur->next)
+ alloccache_print (cur);
+}
+
+#endif /* CONFIG_WITH_ALLOC_CACHES */
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-26 17:00:54 +0000