update copyright notices
[mono.git] / mono / metadata / mempool.c
1 /*
2  * mempool.c: efficient memory allocation
3  *
4  * MonoMemPool is for fast allocation of memory. We free
5  * all memory when the pool is destroyed.
6  *
7  * Author:
8  *   Dietmar Maurer (dietmar@ximian.com)
9  *
10  * Copyright 2001-2003 Ximian, Inc (http://www.ximian.com)
11  * Copyright 2004-2009 Novell, Inc (http://www.novell.com)
12  */
13
14 #include <config.h>
15 #include <glib.h>
16 #include <string.h>
17
18 #include "mempool.h"
19 #include "mempool-internals.h"
20
21 #if USE_MALLOC_FOR_MEMPOOLS
22 #define MALLOC_ALLOCATION
23 #endif
24
25 /*
26  * MonoMemPool is for fast allocation of memory. We free
27  * all memory when the pool is destroyed.
28  */
29
30 #define MEM_ALIGN 8
31
32 #define MONO_MEMPOOL_PAGESIZE 8192
33 #define MONO_MEMPOOL_MINSIZE 512
34
35 #ifndef G_LIKELY
36 #define G_LIKELY(a) (a)
37 #define G_UNLIKELY(a) (a)
38 #endif
39
40 #ifdef MALLOC_ALLOCATION
41 typedef struct _Chunk {
42         struct _Chunk *next;
43         guint32 size;
44 } Chunk;
45
46 struct _MonoMemPool {
47         Chunk *chunks;
48         guint32 allocated;
49 };
50 #else
51 struct _MonoMemPool {
52         MonoMemPool *next;
53         gint rest;
54         guint8 *pos, *end;
55         guint32 size;
56         union {
57                 double pad; /* to assure proper alignment */
58                 guint32 allocated;
59         } d;
60 };
61 #endif
62
63 /**
64  * mono_mempool_new:
65  *
66  * Returns: a new memory pool.
67  */
68 MonoMemPool *
69 mono_mempool_new (void)
70 {
71         return mono_mempool_new_size (MONO_MEMPOOL_PAGESIZE);
72 }
73
74 MonoMemPool *
75 mono_mempool_new_size (int initial_size)
76 {
77 #ifdef MALLOC_ALLOCATION
78         return g_new0 (MonoMemPool, 1);
79 #else
80         MonoMemPool *pool;
81         if (initial_size < MONO_MEMPOOL_MINSIZE)
82                 initial_size = MONO_MEMPOOL_MINSIZE;
83         pool = g_malloc (initial_size);
84
85         pool->next = NULL;
86         pool->pos = (guint8*)pool + sizeof (MonoMemPool);
87         pool->end = pool->pos + initial_size - sizeof (MonoMemPool);
88         pool->d.allocated = pool->size = initial_size;
89         return pool;
90 #endif
91 }
92
93 /**
94  * mono_mempool_destroy:
95  * @pool: the memory pool to destroy
96  *
97  * Free all memory associated with this pool.
98  */
99 void
100 mono_mempool_destroy (MonoMemPool *pool)
101 {
102 #ifdef MALLOC_ALLOCATION
103         mono_mempool_empty (pool);
104
105         g_free (pool);
106 #else
107         MonoMemPool *p, *n;
108
109         p = pool;
110         while (p) {
111                 n = p->next;
112                 g_free (p);
113                 p = n;
114         }
115 #endif
116 }
117
118 /**
119  * mono_mempool_invalidate:
120  * @pool: the memory pool to invalidate
121  *
122  * Fill the memory associated with this pool to 0x2a (42). Useful for debugging.
123  */
124 void
125 mono_mempool_invalidate (MonoMemPool *pool)
126 {
127 #ifdef MALLOC_ALLOCATION
128         g_assert_not_reached ();
129 #else
130         MonoMemPool *p, *n;
131
132         p = pool;
133         while (p) {
134                 n = p->next;
135                 memset (p, 42, p->size);
136                 p = n;
137         }
138 #endif
139 }
140
141 void
142 mono_mempool_empty (MonoMemPool *pool)
143 {
144 #ifdef MALLOC_ALLOCATION
145         Chunk *p, *n;
146
147         p = pool->chunks;
148         pool->chunks = NULL;
149         while (p) {
150                 n = p->next;
151                 g_free (p);
152                 p = n;
153         }
154
155         pool->allocated = 0;
156 #else
157         pool->pos = (guint8*)pool + sizeof (MonoMemPool);
158         pool->end = pool->pos + pool->size - sizeof (MonoMemPool);
159 #endif
160 }
161
162 /**
163  * mono_mempool_stats:
164  * @pool: the momory pool we need stats for
165  *
166  * Print a few stats about the mempool
167  */
168 void
169 mono_mempool_stats (MonoMemPool *pool)
170 {
171 #ifdef MALLOC_ALLOCATION
172         g_assert_not_reached ();
173 #else
174         MonoMemPool *p;
175         int count = 0;
176         guint32 still_free = 0;
177
178         p = pool;
179         while (p) {
180                 still_free += p->end - p->pos;
181                 p = p->next;
182                 count++;
183         }
184         if (pool) {
185                 g_print ("Mempool %p stats:\n", pool);
186                 g_print ("Total mem allocated: %d\n", pool->d.allocated);
187                 g_print ("Num chunks: %d\n", count);
188                 g_print ("Free memory: %d\n", still_free);
189         }
190 #endif
191 }
192
193 #ifndef MALLOC_ALLOCATION
194 #ifdef TRACE_ALLOCATIONS
195 #include <execinfo.h>
196 #include "metadata/appdomain.h"
197 #include "metadata/metadata-internals.h"
198
199 static CRITICAL_SECTION mempool_tracing_lock;
200 #define BACKTRACE_DEPTH 7
201 static void
202 mono_backtrace (int size)
203 {
204         void *array[BACKTRACE_DEPTH];
205         char **names;
206         int i, symbols;
207         static gboolean inited;
208
209         if (!inited) {
210             InitializeCriticalSection (&mempool_tracing_lock);
211             inited = TRUE;
212         }
213
214         EnterCriticalSection (&mempool_tracing_lock);
215         g_print ("Allocating %d bytes\n", size);
216         symbols = backtrace (array, BACKTRACE_DEPTH);
217         names = backtrace_symbols (array, symbols);
218         for (i = 1; i < symbols; ++i) {
219                 g_print ("\t%s\n", names [i]);
220         }
221         free (names);
222         LeaveCriticalSection (&mempool_tracing_lock);
223 }
224
225 #endif
226
227 static int
228 get_next_size (MonoMemPool *pool, int size)
229 {
230         int target = pool->next? pool->next->size: pool->size;
231         size += sizeof (MonoMemPool);
232         /* increase the size */
233         target += target / 2;
234         while (target < size) {
235                 target += target / 2;
236         }
237         if (target > MONO_MEMPOOL_PAGESIZE)
238                 target = MONO_MEMPOOL_PAGESIZE;
239         /* we are called with size smaller than 4096 */
240         g_assert (size <= MONO_MEMPOOL_PAGESIZE);
241         return target;
242 }
243 #endif
244
245 /**
246  * mono_mempool_alloc:
247  * @pool: the momory pool to use
248  * @size: size of the momory block
249  *
250  * Allocates a new block of memory in @pool.
251  *
252  * Returns: the address of a newly allocated memory block.
253  */
254 gpointer
255 mono_mempool_alloc (MonoMemPool *pool, guint size)
256 {
257         gpointer rval;
258         
259         size = (size + MEM_ALIGN - 1) & ~(MEM_ALIGN - 1);
260
261 #ifdef MALLOC_ALLOCATION
262         {
263                 Chunk *c = g_malloc (sizeof (Chunk) + size);
264
265                 c->next = pool->chunks;
266                 pool->chunks = c;
267                 c->size = size;
268
269                 pool->allocated += size;
270
271                 rval = ((guint8*)c) + sizeof (Chunk);
272         }
273 #else
274         rval = pool->pos;
275         pool->pos = (guint8*)rval + size;
276
277 #ifdef TRACE_ALLOCATIONS
278         if (pool == mono_get_corlib ()->mempool) {
279                 mono_backtrace (size);
280         }
281 #endif
282         if (G_UNLIKELY (pool->pos >= pool->end)) {
283                 pool->pos -= size;
284                 if (size >= 4096) {
285                         MonoMemPool *np = g_malloc (sizeof (MonoMemPool) + size);
286                         np->next = pool->next;
287                         pool->next = np;
288                         np->pos = (guint8*)np + sizeof (MonoMemPool);
289                         np->size = sizeof (MonoMemPool) + size;
290                         np->end = np->pos + np->size - sizeof (MonoMemPool);
291                         pool->d.allocated += sizeof (MonoMemPool) + size;
292                         return (guint8*)np + sizeof (MonoMemPool);
293                 } else {
294                         int new_size = get_next_size (pool, size);
295                         MonoMemPool *np = g_malloc (new_size);
296                         np->next = pool->next;
297                         pool->next = np;
298                         pool->pos = (guint8*)np + sizeof (MonoMemPool);
299                         np->pos = (guint8*)np + sizeof (MonoMemPool);
300                         np->size = new_size;
301                         np->end = np->pos;
302                         pool->end = pool->pos + new_size - sizeof (MonoMemPool);
303                         pool->d.allocated += new_size;
304
305                         rval = pool->pos;
306                         pool->pos += size;
307                 }
308         }
309
310         return rval;
311 #endif
312 }
313
314 /**
315  * mono_mempool_alloc0:
316  *
317  * same as mono_mempool_alloc, but fills memory with zero.
318  */
319 gpointer
320 mono_mempool_alloc0 (MonoMemPool *pool, guint size)
321 {
322         gpointer rval;
323
324 #ifdef MALLOC_ALLOCATION
325         rval = mono_mempool_alloc (pool, size);
326 #else
327         size = (size + MEM_ALIGN - 1) & ~(MEM_ALIGN - 1);
328
329         rval = pool->pos;
330         pool->pos = (guint8*)rval + size;
331
332         if (G_UNLIKELY (pool->pos >= pool->end)) {
333                 rval = mono_mempool_alloc (pool, size);
334         }
335 #ifdef TRACE_ALLOCATIONS
336         else if (pool == mono_get_corlib ()->mempool) {
337                 mono_backtrace (size);
338         }
339 #endif
340 #endif
341
342         memset (rval, 0, size);
343         return rval;
344 }
345
346 /**
347  * mono_mempool_contains_addr:
348  *
349  *  Determines whenever ADDR is inside the memory used by the mempool.
350  */
351 gboolean
352 mono_mempool_contains_addr (MonoMemPool *pool,
353                                                         gpointer addr)
354 {
355 #ifdef MALLOC_ALLOCATION
356         Chunk *c;
357
358         c = pool->chunks;
359         while (c) {
360                 guint8 *p = ((guint8*)c) + sizeof (Chunk);
361
362                 if (addr >= (gpointer)p && addr < (gpointer)(p + c->size))
363                         return TRUE;
364
365                 c = c->next;
366         }
367 #else
368         MonoMemPool *p;
369
370         p = pool;
371         while (p) {
372                 if (addr > (gpointer)p && addr <= (gpointer)((guint8*)p + p->size))
373                         return TRUE;
374                 p = p->next;
375         }
376 #endif
377
378         return FALSE;
379 }
380
381 /**
382  * mono_mempool_strdup:
383  *
384  * Same as strdup, but allocates memory from the mempool.
385  * Returns: a pointer to the newly allocated string data inside the mempool.
386  */
387 char*
388 mono_mempool_strdup (MonoMemPool *pool,
389                                          const char *s)
390 {
391         int l;
392         char *res;
393
394         if (s == NULL)
395                 return NULL;
396
397         l = strlen (s);
398         res = mono_mempool_alloc (pool, l + 1);
399         memcpy (res, s, l + 1);
400
401         return res;
402 }
403
404 /**
405  * mono_mempool_get_allocated:
406  *
407  * Return the amount of memory allocated for this mempool.
408  */
409 guint32
410 mono_mempool_get_allocated (MonoMemPool *pool)
411 {
412 #ifdef MALLOC_ALLOCATION
413         return pool->allocated;
414 #else
415         return pool->d.allocated;
416 #endif
417 }
418
419 GList*
420 g_list_prepend_mempool (MonoMemPool *mp, GList *list, gpointer data)
421 {
422         GList *new_list;
423         
424         new_list = mono_mempool_alloc (mp, sizeof (GList));
425         new_list->data = data;
426         new_list->prev = list ? list->prev : NULL;
427     new_list->next = list;
428
429     if (new_list->prev)
430             new_list->prev->next = new_list;
431     if (list)
432             list->prev = new_list;
433
434         return new_list;
435 }
436
437 GSList*
438 g_slist_prepend_mempool (MonoMemPool *mp, GSList *list, gpointer  data)
439 {
440         GSList *new_list;
441         
442         new_list = mono_mempool_alloc (mp, sizeof (GSList));
443         new_list->data = data;
444         new_list->next = list;
445
446         return new_list;
447 }
448
449 GSList*
450 g_slist_append_mempool (MonoMemPool *mp, GSList *list, gpointer data)
451 {
452         GSList *new_list;
453         GSList *last;
454
455         new_list = mono_mempool_alloc (mp, sizeof (GSList));
456         new_list->data = data;
457         new_list->next = NULL;
458
459         if (list) {
460                 last = list;
461                 while (last->next)
462                         last = last->next;
463                 last->next = new_list;
464
465                 return list;
466         } else
467                 return new_list;
468 }