GPLization banner introduced to *.[hc] files
[sip-router] / mem / vq_malloc.c
1 /* $Id$
2  *
3  * Copyright (C) 2001-2003 Fhg Fokus
4  *
5  * This file is part of ser, a free SIP server.
6  *
7  * ser is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version
11  *
12  * For a license to use the ser software under conditions
13  * other than those described here, or to purchase support for this
14  * software, please contact iptel.org by e-mail at the following addresses:
15  *    info@iptel.org
16  *
17  * ser is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License 
23  * along with this program; if not, write to the Free Software 
24  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
25  * History: 
26  * merged from Andrei's qmalloc and many fragments from Regents 
27  * University of California NetBSD malloc used; see
28  * http://www.ajk.tele.fi/libc/stdlib/malloc.c.html#malloc for more
29  * details including redistribution policy; this policy asks for
30  * displaying the copyright:
31  * Copyright (c) 1983 Regents of the University of California.
32  * All rights reserved.
33  *
34  *
35  * About:
36  * aggressive, wasteful and very quick malloc library built for
37  * servers that continuously alocate and release chunks of only
38  * few sizes:
39  * - free lists are organized by size (which eliminates long list traversal 
40  *   thru short free chunks if a long one is asked)
41  * - quite a few sizes are supported --> this results in more waste
42  *    (unused place in a chunk) however memory can be well reused after
43  *    freeing
44  * - the last bucket holds unlikely, huge, variable length chunks;
45  *   they are maintained as stack growing from the opposite direction
46  *   of our heap; coalesing is enabled; stack-like first-fit used to
47  *   find free fragments
48  *
49  * TODO: possibly, some delayed coalescation wouldn't hurt; also, further
50  * optimization will certainly speed-up the entire process a lot; using
51  * knowledge of application as well as trying to make pipeline happy
52  * (from which I am sadly far away now)
53  * provides optimization space; trying to use other memory allocators
54  * to compare would be a great thing to do too;
55  *
56  * also, comparing to other memory allocaters (like Horde) would not
57  * be a bad idea: those folks have been doing that for ages and specifically
58  * Horde has been heavily optimized for multi-processor machines
59  *
60  * References:
61  *   - list of malloc implementations: http://www.cs.colorado.edu/~zorn/Malloc.html
62  *   - a white-paper: http://g.oswego.edu/dl/html/malloc.html
63  *   - Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles: 
64        ``Dynamic Storage Allocation: A Survey and Critical Review'' in International 
65        Workshop on Memory Management, September 1995, 
66        ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
67  *   - ptmalloc: http://www.malloc.de/en/
68  *   - GNU C-lib malloc: http://www.gnu.org/manual/glibc-2.0.6/html_chapter/libc_3.html
69  *   - delorie malocs: http://www.delorie.com/djgpp/malloc/
70  *
71  */
72
73
74 #ifdef VQ_MALLOC
75
76 #include <stdlib.h>
77
78 #include "../config.h"
79 #include "../globals.h"
80 #include "vq_malloc.h"
81 #include "../dprint.h"
82 #include "../globals.h"
83
84 #define BIG_BUCKET(_qm) ((_qm)->max_small_bucket+1)
85 #define IS_BIGBUCKET(_qm, _bucket) ((_bucket)==BIG_BUCKET(_qm)) 
86
87 #ifdef DBG_QM_MALLOC
88 #define ASSERT(a)       \
89         my_assert(a, __LINE__, __FILE__, __FUNCTION__ )
90 #else
91 #define ASSERT(a)
92 #endif
93
94 #ifdef DBG_QM_MALLOC
95 #       define MORE_CORE(_q,_b,_s) (more_core( (_q), (_b), (_s), file, func, line ))
96 #else
97 #       define MORE_CORE(_q,_b,_s) (more_core( (_q), (_b), (_s) ))
98 #endif
99
100
101
102 /* dimensioning buckets: define the step function constants for size2bucket */
103 int s2b_step[] = {8, 16, 32, 64, 128, 256, 512, 1024, 1536, 2048, 2560, MAX_FIXED_BLOCK, EO_STEP };
104
105 void my_assert( int assertation, int line, char *file, char *function )
106 {
107         if (assertation) return;
108
109         LOG(L_CRIT,"CRIT: assertation failed in %s (%s:%d)\n",
110                 function, file, line);
111         abort();
112 }
113
114 #ifdef DBG_QM_MALLOC
115 void vqm_debug_frag(struct vqm_block* qm, struct vqm_frag* f)
116 {
117
118
119         if (f->check!=ST_CHECK_PATTERN){
120                 LOG(L_CRIT, "BUG: vqm_*: fragm. %p beginning overwritten(%x)!\n",
121                                 f, f->check);
122                 vqm_status(qm);
123                 abort();
124         };
125         if (memcmp(f->end_check, END_CHECK_PATTERN, END_CHECK_PATTERN_LEN)!=0) {
126                 LOG(L_CRIT, "BUG: vqm_*: fragm. %p end overwritten(%.*s)!\n",
127                                 f, END_CHECK_PATTERN_LEN, f->end_check );
128                 vqm_status(qm);
129                 abort();
130         }
131 }
132 #endif
133
134
135 /* takes  demanded size without overhead as input, returns bucket number
136    and changed the demanded size to size really used including all
137    possible overhead
138  */
139 unsigned char size2bucket( struct vqm_block* qm, int *size  )
140 {
141         unsigned char b;        
142         unsigned int real_size;
143         unsigned int exceeds;
144
145         real_size = *size+ VQM_OVERHEAD;
146
147 #ifdef DBG_QM_MALLOC
148         real_size+=END_CHECK_PATTERN_LEN;
149 #endif
150         real_size+=((exceeds = (real_size % 8 )) ? 8 - exceeds : 0);
151         ASSERT( !(real_size%8) );
152         /* "small" chunk sizes <=1k translated using a table */
153         if ( real_size < MAX_FIXED_BLOCK ) {
154                 b = qm->s2b[ real_size ];
155                 *size = qm->s2s[ real_size ];
156         /* there might be various allocations slightly 1>1k, I still
157            don't want to be too agressive and increase useless 
158            allocations in small steps
159         */      
160         } else {
161                 b = BIG_BUCKET(qm); 
162                 *size = MAX_FIXED_BLOCK + 
163                         (real_size-MAX_FIXED_BLOCK+BLOCK_STEP) 
164                         / BLOCK_STEP * BLOCK_STEP;
165         }
166         /*size must be a multiple of 8*/
167         ASSERT( !(*size%8) );
168         return b;
169 }
170
171
172 /* init malloc and return a qm_block */
173 struct vqm_block* vqm_malloc_init(char* address, unsigned int size)
174 {
175         char* start;
176         struct vqm_block* qm;
177         unsigned int init_overhead;
178         unsigned char b;        /* bucket iterator */
179         unsigned int s;         /* size iterator */
180         char *end;
181         
182         /* make address and size multiple of 8*/
183         start=(char*)( ((unsigned int)address%8)?((unsigned int)address+8)/8*8:
184                         (unsigned int)address);
185         if (size<start-address) return 0;
186         size-=(start-address);
187         if (size <8) return 0;
188         size=(size%8)?(size-8)/8*8:size;
189
190         init_overhead=sizeof(struct vqm_block);
191         if (size < init_overhead)
192         {
193                 /* not enough mem to create our control structures !!!*/
194                 return 0;
195         }
196         end = start + size;
197         qm=(struct vqm_block*)start;
198         memset(qm, 0, sizeof(struct vqm_block));
199         size-=init_overhead;
200
201         /* definition of the size2bucket table */
202         for (s=0, b=0; s<MAX_FIXED_BLOCK ; s++) {
203                 while (s>s2b_step[b]) b++;
204                 if (b>MAX_BUCKET) {
205                         LOG(L_CRIT, "CRIT: vqm_malloc_init: attempt to install too many buckets,"
206                                 "s2b_step > MAX_BUCKET\n");
207                         return 0;
208                 }
209                 qm->s2b[s] = b;
210                 qm->s2s[s] = s2b_step[b];
211         }
212         qm->max_small_bucket = b;
213
214         /* from where we will draw memory */
215         qm->core = (char *) ( start + sizeof( struct vqm_block ) );
216         qm->free_core = size;
217         /* remember for bound checking */
218         qm->init_core = qm->core;
219         qm->core_end = end;
220         /* allocate big chunks from end */
221         qm->big_chunks = end;
222         
223         return qm;
224 }
225
226
227
228 struct vqm_frag *more_core(     struct vqm_block* qm, 
229                                 unsigned char bucket, unsigned int size
230 #ifdef DBG_QM_MALLOC
231                                 , char *file, char *func, unsigned int line
232 #endif
233                          ) 
234 {
235         struct vqm_frag *new_chunk;
236         struct vqm_frag_end *end;
237
238         if (qm->free_core<size) return 0;
239
240         /* update core */
241         if (IS_BIGBUCKET(qm, bucket)) {
242                 qm->big_chunks-=size;
243                 new_chunk = (struct vqm_frag *) qm->big_chunks ;        
244         } else {
245                 new_chunk = (struct vqm_frag *) qm->core;       
246                 qm->core+=size;
247         }
248         qm->free_core-=size;
249
250         /* initialize the new fragment */
251         new_chunk->u.inuse.bucket = bucket;
252         new_chunk->size = size;
253
254         end=FRAG_END( new_chunk );
255         end->size=size;
256
257         return new_chunk;
258 }
259
260 static inline void vqm_detach_free( struct vqm_block* qm, struct vqm_frag* frag)
261 {
262
263         struct vqm_frag *prev, *next;
264
265         prev=FRAG_END(frag)->prv_free; 
266         next=frag->u.nxt_free;
267
268         if (prev) prev->u.nxt_free=next; 
269         else qm->next_free[BIG_BUCKET(qm)]=next;
270
271         if (next) FRAG_END(next)->prv_free=prev; 
272          
273 }
274
275
276 #ifdef DBG_QM_MALLOC
277 void* vqm_malloc(struct vqm_block* qm, unsigned int size, 
278         char* file, char* func, unsigned int line)
279 #else
280 void* vqm_malloc(struct vqm_block* qm, unsigned int size)
281 #endif
282 {
283         struct vqm_frag *new_chunk, *f;
284         unsigned char bucket;
285         
286 #ifdef DBG_QM_MALLOC
287         unsigned int demanded_size;
288         DBG("vqm_malloc(%p, %d) called from %s: %s(%d)\n", qm, size, file,
289          func, line);
290         demanded_size = size;
291 #endif
292         new_chunk=0;
293         /* what's the bucket? what's the total size incl. overhead? */
294         bucket = size2bucket( qm, &size );
295
296         if (IS_BIGBUCKET(qm, bucket)) { /* the kilo-bucket uses first-fit */
297 #ifdef DBG_QM_MALLOC
298                 DBG("vqm_malloc: processing a big fragment\n");
299 #endif
300                 for (f=qm->next_free[bucket] ; f; f=f->u.nxt_free ) 
301                         if (f->size>=size) { /* first-fit */
302                                 new_chunk=f;
303                                 VQM_DEBUG_FRAG(qm, f);
304                                 vqm_detach_free(qm,f);
305                                 break;
306                         }
307         } else if (  (new_chunk=qm->next_free[ bucket ]) ) { /*fixed size bucket*/
308                         VQM_DEBUG_FRAG(qm, new_chunk);
309                         /*detach it from the head of bucket's free list*/
310                         qm->next_free[ bucket ] = new_chunk->u.nxt_free;
311         }
312
313         if (!new_chunk) { /* no chunk can be reused; slice one from the core */
314                 new_chunk=MORE_CORE( qm, bucket, size );
315                 if (!new_chunk) {
316 #ifdef DBG_QM_MALLOC
317                         LOG(L_DBG, "vqm_malloc(%p, %d) called from %s: %s(%d)\n", 
318                                 qm, size, file, func, line);
319 #else
320                         LOG(L_DBG, "vqm_malloc(%p, %d) called from %s: %s(%d)\n", 
321                                 qm, size);
322 #endif
323                         return 0;
324                 }
325         }
326         new_chunk->u.inuse.magic = FR_USED;
327         new_chunk->u.inuse.bucket=bucket;
328 #ifdef DBG_QM_MALLOC
329         new_chunk->file=file;
330         new_chunk->func=func;
331         new_chunk->line=line;
332         new_chunk->demanded_size=demanded_size;
333         qm->usage[ bucket ]++;
334         DBG("vqm_malloc( %p, %d ) returns address %p in bucket %d, real-size %d \n",
335                 qm, demanded_size, (char*)new_chunk+sizeof(struct vqm_frag), 
336                 bucket, size );
337
338         new_chunk->end_check=(char*)new_chunk+sizeof(struct vqm_frag)+demanded_size;
339         memcpy(  new_chunk->end_check, END_CHECK_PATTERN, END_CHECK_PATTERN_LEN );
340         new_chunk->check=ST_CHECK_PATTERN;
341 #endif
342         return (char*)new_chunk+sizeof(struct vqm_frag);
343 }
344
345 #ifdef DBG_QM_MALLOC
346 void vqm_free(struct vqm_block* qm, void* p, char* file, char* func, 
347                                 unsigned int line)
348 #else
349 void vqm_free(struct vqm_block* qm, void* p)
350 #endif
351 {
352         struct vqm_frag *f, *next, *prev, *first_big;
353         unsigned char b;
354
355 #ifdef DBG_QM_MALLOC
356         DBG("vqm_free(%p, %p), called from %s: %s(%d)\n", 
357                 qm, p, file, func, line);
358         if (p>(void *)qm->core_end || p<(void*)qm->init_core){
359                 LOG(L_CRIT, "BUG: vqm_free: bad pointer %p (out of memory block!) - "
360                                 "aborting\n", p);
361                 abort();
362         }
363 #endif
364         if (p==0) {
365                 DBG("WARNING:vqm_free: free(0) called\n");
366                 return;
367         }
368         f=(struct  vqm_frag*) ((char*)p-sizeof(struct vqm_frag));
369         b=f->u.inuse.bucket;
370 #ifdef DBG_QM_MALLOC
371         VQM_DEBUG_FRAG(qm, f);
372         if ( ! FRAG_ISUSED(f) ) {
373                 LOG(L_CRIT, "BUG: vqm_free: freeing already freed pointer,"
374                                 " first freed: %s: %s(%d) - aborting\n",
375                                 f->file, f->func, f->line);
376                 abort();
377         }
378         if ( b>MAX_BUCKET ) {
379                 LOG(L_CRIT, "BUG: vqm_free: fragment with too high bucket nr: "
380                                 "%d, allocated: %s: %s(%d) - aborting\n",
381                                 b, f->file, f->func, f->line); 
382                 abort();
383         }
384         DBG("vqm_free: freeing %d bucket block alloc'ed from %s: %s(%d)\n", 
385                 f->u.inuse.bucket, f->file, f->func, f->line);
386         f->file=file; f->func=func; f->line=line;
387         qm->usage[ f->u.inuse.bucket ]--;
388 #endif
389         if (IS_BIGBUCKET(qm,b)) {
390                 next=FRAG_NEXT(f);
391                 if  ((char *)next +sizeof( struct vqm_frag) < qm->core_end) {
392                         VQM_DEBUG_FRAG(qm, next);
393                         if (! FRAG_ISUSED(next)) { /* coalescate with next fragment */
394                                 DBG("vqm_free: coalescated with next\n");
395                                 vqm_detach_free(qm, next);
396                                 f->size+=next->size;
397                                 FRAG_END(f)->size=f->size;
398                         }
399                 }
400                 first_big = qm->next_free[b];
401                 if (first_big &&  f>first_big) {
402                         prev=FRAG_PREV(f);
403                         VQM_DEBUG_FRAG(qm, prev);
404                         if (!FRAG_ISUSED(prev)) { /* coalescate with prev fragment */
405                                 DBG("vqm_free: coalescated with prev\n");
406                                 vqm_detach_free(qm, prev );
407                                 prev->size+=f->size;
408                                 f=prev;
409                                 FRAG_END(f)->size=f->size;
410                         }
411                 }
412                 if ((char *)f==qm->big_chunks) { /* release unused core */
413                         DBG("vqm_free: big chunk released\n");
414                         qm->free_core+=f->size;
415                         qm->big_chunks+=f->size;
416                         return;
417                 }               
418                 first_big = qm->next_free[b];
419                 /* fix reverse link (used only for BIG_BUCKET */
420                 if (first_big) FRAG_END(first_big)->prv_free=f;
421                 FRAG_END(f)->prv_free=0;
422         } else first_big = qm->next_free[b];
423         f->u.nxt_free = first_big; /* also clobbers magic */
424         qm->next_free[b] = f;
425 }
426
427 void dump_frag( struct vqm_frag* f, int i )
428 {
429         LOG(memlog, "    %3d. address=%p  real size=%d bucket=%d\n", i, 
430                 (char*)f+sizeof(struct vqm_frag), f->size, f->u.inuse.bucket);
431 #ifdef DBG_QM_MALLOC
432         LOG(memlog, "            demanded size=%d\n", f->demanded_size );
433         LOG(memlog, "            alloc'd from %s: %s(%d)\n",
434                 f->file, f->func, f->line);
435         LOG(memlog, "        start check=%x, end check= %.*s\n",
436                         f->check, END_CHECK_PATTERN_LEN, f->end_check );
437 #endif
438 }
439
440 void vqm_status(struct vqm_block* qm)
441 {
442         struct vqm_frag* f;
443         unsigned int i,on_list;
444
445         LOG(memlog, "vqm_status (%p):\n", qm);
446         if (!qm) return;
447         LOG(memlog, " heap size= %d, available: %d\n", 
448                 qm->core_end-qm->init_core, qm->free_core );
449         
450         LOG(memlog, "dumping unfreed fragments:\n");
451         for (f=(struct vqm_frag*)qm->init_core, i=0;(char*)f<(char*)qm->core;
452                 f=FRAG_NEXT(f) ,i++) if ( FRAG_ISUSED(f) ) dump_frag(f, i);
453
454         LOG(memlog, "dumping unfreed big fragments:\n");
455     for (f=(struct vqm_frag*)qm->big_chunks,i=0;(char*)f<(char*)qm->core_end;
456                 f=FRAG_NEXT(f) ,i++) if ( FRAG_ISUSED(f) ) dump_frag( f, i );
457
458 #ifdef DBG_QM_MALLOC
459         DBG("dumping bucket statistics:\n");
460         for (i=0; i<=BIG_BUCKET(qm); i++) {
461                 for(on_list=0, f=qm->next_free[i]; f; f=f->u.nxt_free ) on_list++;
462                 LOG(L_DBG, "    %3d. bucket: in use: %ld, on free list: %d\n", 
463                         i, qm->usage[i], on_list );
464         }
465 #endif
466         LOG(memlog, "-----------------------------\n");
467 }
468
469
470
471 #endif