1 /* $Id: alloccache.c 2633 2012-09-08 23:18:59Z bird $ */
2 /** @file
3  * alloccache - Fixed sized allocation cache.
4  *
5  * The rational for using an allocation cache, is that it is way faster
6  * than malloc+free on most systems.  It may be more efficient as well,
7  * depending on the way the heap implementes small allocations.  Also,
8  * with the incdep.c code being threaded, all heaps (except for MSC)
9  * ran into severe lock contention issues since both the main thread
10  * and the incdep worker thread was allocating a crazy amount of tiny
11  * allocations (struct dep, struct nameseq, ++).
12  *
13  * Darwin also showed a significant amount of time spent just executing
14  * free(), which is kind of silly.  The alloccache helps a bit here too.
15  */
16 
17 /*
18  * Copyright (c) 2008-2010 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
19  *
20  * This file is part of kBuild.
21  *
22  * kBuild is free software; you can redistribute it and/or modify
23  * it under the terms of the GNU General Public License as published by
24  * the Free Software Foundation; either version 3 of the License, or
25  * (at your option) any later version.
26  *
27  * kBuild is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
30  * GNU General Public License for more details.
31  *
32  * You should have received a copy of the GNU General Public License
33  * along with kBuild.  If not, see <http://www.gnu.org/licenses/>
34  *
35  */
36 
37 /*******************************************************************************
38 *   Header Files                                                               *
39 *******************************************************************************/
40 #include "make.h"
41 #include "dep.h"
42 #include "debug.h"
43 #include <assert.h>
44 
45 
46 #ifdef CONFIG_WITH_ALLOC_CACHES
47 
48 /* Free am item.
49    This was not inlined because of aliasing issues arrising with GCC.
50    It is also in a separate file for this reason (it used to be in misc.c
51    but since free_dep_chain() was using it there, we ran the risk of it
52    being inlined and gcc screwing up).  */
53 void
alloccache_free(struct alloccache * cache,void * item)54 alloccache_free (struct alloccache *cache, void *item)
55 {
56 #ifndef CONFIG_WITH_ALLOCCACHE_DEBUG
57   struct alloccache_free_ent *f = (struct alloccache_free_ent *)item;
58 # if 0 /*ndef NDEBUG*/
59   struct alloccache_free_ent *c;
60   unsigned int i = 0;
61   for (c = cache->free_head; c != NULL; c = c->next, i++)
62     MY_ASSERT_MSG (c != f && i < 0x10000000,
63                    ("i=%u total_count=%u\n", i, cache->total_count));
64 # endif
65 
66   f->next = cache->free_head;
67   cache->free_head = f;
68   MAKE_STATS(cache->free_count++;);
69 #else
70   free(item);
71 #endif
72 }
73 
74 /* Default allocator. */
75 static void *
alloccache_default_grow_alloc(void * ignore,unsigned int size)76 alloccache_default_grow_alloc(void *ignore, unsigned int size)
77 {
78   return xmalloc (size);
79 }
80 
81 /* Worker for growing the cache. */
82 struct alloccache_free_ent *
alloccache_alloc_grow(struct alloccache * cache)83 alloccache_alloc_grow (struct alloccache *cache)
84 {
85 #ifndef CONFIG_WITH_ALLOCCACHE_DEBUG
86   void *item;
87   unsigned int items = (64*1024 - 32) / cache->size;
88   cache->free_start  = cache->grow_alloc (cache->grow_arg, items * cache->size);
89   cache->free_end    = cache->free_start + items * cache->size;
90   cache->total_count+= items;
91 
92 # ifndef NDEBUG /* skip the first item so the heap can detect free(). */
93   cache->total_count--;
94   cache->free_start += cache->size;
95 # endif
96 
97   item = cache->free_start;
98   cache->free_start += cache->size;
99   /* caller counts */
100   return (struct alloccache_free_ent *)item;
101 #else
102   return (struct alloccache_free_ent *)xmalloc(cache->size);
103 #endif
104 }
105 
106 /* List of alloc caches, for printing. */
107 static struct alloccache *alloccache_head = NULL;
108 
109 /* Initializes an alloc cache */
110 void
alloccache_init(struct alloccache * cache,unsigned int size,const char * name,void * (* grow_alloc)(void * grow_arg,unsigned int size),void * grow_arg)111 alloccache_init (struct alloccache *cache, unsigned int size, const char *name,
112                  void *(*grow_alloc)(void *grow_arg, unsigned int size), void *grow_arg)
113 {
114   unsigned act_size;
115 
116   /* ensure OK alignment and min sizeof (struct alloccache_free_ent). */
117   if (size <= sizeof (struct alloccache_free_ent))
118     act_size = sizeof (struct alloccache_free_ent);
119   else if (size <= 32)
120     {
121       act_size = 4;
122       while (act_size < size)
123         act_size <<= 1;
124     }
125   else
126     act_size = (size + 31U) & ~(size_t)31;
127 
128   /* align the structure. */
129   cache->free_start  = NULL;
130   cache->free_end    = NULL;
131   cache->free_head   = NULL;
132   cache->size        = act_size;
133   cache->total_count = 0;
134   cache->alloc_count = 0;
135   cache->free_count  = 0;
136   cache->name        = name;
137   cache->grow_arg    = grow_arg;
138   cache->grow_alloc  = grow_alloc ? grow_alloc : alloccache_default_grow_alloc;
139 
140   /* link it. */
141   cache->next        = alloccache_head;
142   alloccache_head    = cache;
143 }
144 
145 /* Terminate an alloc cache, free all the memory it contains. */
146 void
alloccache_term(struct alloccache * cache,void (* term_free)(void * term_arg,void * ptr,unsigned int size),void * term_arg)147 alloccache_term (struct alloccache *cache,
148                  void (*term_free)(void *term_arg, void *ptr, unsigned int size), void *term_arg)
149 {
150     /*cache->size = 0;*/
151     (void)cache;
152     (void)term_free;
153     (void)term_arg;
154     /* FIXME: Implement memory segment tracking and cleanup. */
155 }
156 
157 /* Joins to caches, unlinking the 2nd one. */
158 void
alloccache_join(struct alloccache * cache,struct alloccache * eat)159 alloccache_join (struct alloccache *cache, struct alloccache *eat)
160 {
161   assert (cache->size == eat->size);
162 
163 #if 0 /* probably a waste of time */ /* FIXME: Optimize joining, avoid all list walking. */
164   /* add the free list... */
165   if (eat->free_head)
166     {
167      unsigned int eat_in_use = eat->alloc_count - eat->free_count;
168      unsigned int dst_in_use = cache->alloc_count - cache->free_count;
169      if (!cache->free_head)
170        cache->free_head = eat->free_head;
171      else if (eat->total_count - eat_in_use < cache->total_count - dst_ins_use)
172        {
173          struct alloccache_free_ent *last = eat->free_head;
174          while (last->next)
175            last = last->next;
176          last->next = cache->free_head;
177          cache->free_head = eat->free_head;
178        }
179      else
180        {
181          struct alloccache_free_ent *last = cache->free_head;
182          while (last->next)
183            last = last->next;
184          last->next = eat->free_head;
185        }
186     }
187 
188   /* ... and the free space. */
189   while (eat->free_start != eat->free_end)
190     {
191       struct alloccache_free_ent *f = (struct alloccache_free_ent *)eat->free_start;
192       eat->free_start += eat->size;
193       f->next = cache->free_head;
194       cache->free_head = f;
195     }
196 
197   /* and statistics */
198   cache->alloc_count += eat->alloc_count;
199   cache->free_count  += eat->free_count;
200 #else
201   /* and statistics */
202   cache->alloc_count += eat->alloc_count;
203   cache->free_count  += eat->free_count;
204 #endif
205   cache->total_count += eat->total_count;
206 
207   /* unlink and disable the eat cache */
208   if (alloccache_head == eat)
209     alloccache_head = eat->next;
210   else
211     {
212       struct alloccache *cur = alloccache_head;
213       while (cur->next != eat)
214         cur = cur->next;
215       assert (cur && cur->next == eat);
216       cur->next = eat->next;
217     }
218 
219   eat->size = 0;
220   eat->free_end = eat->free_start = NULL;
221   eat->free_head = NULL;
222 }
223 
224 /* Print one alloc cache. */
225 void
alloccache_print(struct alloccache * cache)226 alloccache_print (struct alloccache *cache)
227 {
228   printf (_("\n# Alloc Cache: %s\n"
229               "#  Items: size = %-3u  total = %-6u"),
230           cache->name, cache->size, cache->total_count);
231   MAKE_STATS(printf (_("  in-use = %-6lu"),
232                      cache->alloc_count - cache->free_count););
233   MAKE_STATS(printf (_("\n#         alloc calls = %-7lu  free calls = %-7lu"),
234                      cache->alloc_count, cache->free_count););
235   printf ("\n");
236 }
237 
238 /* Print all alloc caches. */
239 void
alloccache_print_all(void)240 alloccache_print_all (void)
241 {
242   struct alloccache *cur;
243   puts ("");
244   for (cur = alloccache_head; cur; cur = cur->next)
245     alloccache_print (cur);
246 }
247 
248 #endif /* CONFIG_WITH_ALLOC_CACHES */
249 
250