GPLization banner introduced to *.[hc] files
[sip-router] / mem / q_malloc.c
1 /* $Id$
2  *
3  *
4  * Copyright (C) 2001-2003 Fhg Fokus
5  *
6  * This file is part of ser, a free SIP server.
7  *
8  * ser is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version
12  *
13  * For a license to use the ser software under conditions
14  * other than those described here, or to purchase support for this
15  * software, please contact iptel.org by e-mail at the following addresses:
16  *    info@iptel.org
17  *
18  * ser is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License 
24  * along with this program; if not, write to the Free Software 
25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
26  */
27
28
29 #if !defined(q_malloc) && !(defined VQ_MALLOC) && !(defined F_MALLOC)
30 #define q_malloc
31
32 #include <stdlib.h>
33 #include <string.h>
34
35 #include "q_malloc.h"
36 #include "../dprint.h"
37 #include "../globals.h"
38
39
40 /*useful macros*/
41 #define FRAG_END(f)  \
42         ((struct qm_frag_end*)((char*)(f)+sizeof(struct qm_frag)+ \
43            (f)->size))
44
45 #define FRAG_NEXT(f) \
46         ((struct qm_frag*)((char*)(f)+sizeof(struct qm_frag)+(f)->size+ \
47            sizeof(struct qm_frag_end)))
48                         
49 #define FRAG_PREV(f) \
50         ( (struct qm_frag*) ( ((char*)(f)-sizeof(struct qm_frag_end))- \
51         ((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))->size- \
52            sizeof(struct qm_frag) ) )
53
54 #define PREV_FRAG_END(f) \
55         ((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))
56
57
58 #define FRAG_OVERHEAD   (sizeof(struct qm_frag)+sizeof(struct qm_frag_end))
59
60
61 #define ROUNDTO_MASK    (~((unsigned long)ROUNDTO-1))
62 #define ROUNDUP(s)              (((s)+(ROUNDTO-1))&ROUNDTO_MASK)
63 #define ROUNDDOWN(s)    ((s)&ROUNDTO_MASK)
64
65 /*
66 #define ROUNDUP(s)              (((s)%ROUNDTO)?((s)+ROUNDTO)/ROUNDTO*ROUNDTO:(s))
67 #define ROUNDDOWN(s)    (((s)%ROUNDTO)?((s)-ROUNDTO)/ROUNDTO*ROUNDTO:(s))
68 */
69
70
71
72         /* finds the hash value for s, s=ROUNDTO multiple*/
73 #define GET_HASH(s)   ( ((s)<QM_MALLOC_OPTIMIZE)?(s)/ROUNDTO: \
74                                                 QM_MALLOC_OPTIMIZE/ROUNDTO+big_hash_idx((s))- \
75                                                         QM_MALLOC_OPTIMIZE_FACTOR+1 )
76
77
78 /* computes hash number for big buckets*/
79 inline static int big_hash_idx(int s)
80 {
81         int idx;
82         /* s is rounded => s = k*2^n (ROUNDTO=2^n) 
83          * index= i such that 2^i > s >= 2^(i-1)
84          *
85          * => index = number of the first non null bit in s*/
86         for (idx=31; !(s&0x80000000) ; s<<=1, idx--);
87         return idx;
88 }
89
90
91 #ifdef DBG_QM_MALLOC
92 #define ST_CHECK_PATTERN   0xf0f0f0f0
93 #define END_CHECK_PATTERN1 0xc0c0c0c0
94 #define END_CHECK_PATTERN2 0xabcdefed
95
96
97 static  void qm_debug_frag(struct qm_block* qm, struct qm_frag* f)
98 {
99         if (f->check!=ST_CHECK_PATTERN){
100                 LOG(L_CRIT, "BUG: qm_*: fragm. %p beginning overwritten(%x)!\n",
101                                 f, f->check);
102                 qm_status(qm);
103                 abort();
104         };
105         if ((FRAG_END(f)->check1!=END_CHECK_PATTERN1)||
106                 (FRAG_END(f)->check2!=END_CHECK_PATTERN2)){
107                 LOG(L_CRIT, "BUG: qm_*: fragm. %p end overwritten(%x, %x)!\n",
108                                 f, FRAG_END(f)->check1, FRAG_END(f)->check2);
109                 qm_status(qm);
110                 abort();
111         }
112         if ((f>qm->first_frag)&&
113                         ((PREV_FRAG_END(f)->check1!=END_CHECK_PATTERN1) ||
114                                 (PREV_FRAG_END(f)->check2!=END_CHECK_PATTERN2) ) ){
115                 LOG(L_CRIT, "BUG: qm_*: prev. fragm. tail overwritten(%x, %x)[%p]!\n",
116                                 PREV_FRAG_END(f)->check1, PREV_FRAG_END(f)->check2, f);
117                 qm_status(qm);
118                 abort();
119         }
120 }
121 #endif
122
123
124
125 static inline void qm_insert_free(struct qm_block* qm, struct qm_frag* frag)
126 {
127         struct qm_frag* f;
128         struct qm_frag* prev;
129         int hash;
130         
131         hash=GET_HASH(frag->size);
132         for(f=qm->free_hash[hash].head.u.nxt_free; f!=&(qm->free_hash[hash].head);
133                         f=f->u.nxt_free){
134                 if (frag->size <= f->size) break;
135         }
136         /*insert it here*/
137         prev=FRAG_END(f)->prev_free;
138         prev->u.nxt_free=frag;
139         FRAG_END(frag)->prev_free=prev;
140         frag->u.nxt_free=f;
141         FRAG_END(f)->prev_free=frag;
142 }
143
144
145
146 /* init malloc and return a qm_block*/
147 struct qm_block* qm_malloc_init(char* address, unsigned int size)
148 {
149         char* start;
150         char* end;
151         struct qm_block* qm;
152         unsigned int init_overhead;
153         int h;
154         
155         /* make address and size multiple of 8*/
156         start=(char*)ROUNDUP((unsigned int) address);
157         DBG("qm_malloc_init: QM_OPTIMIZE=%d, /ROUNDTO=%d\n",
158                         QM_MALLOC_OPTIMIZE, QM_MALLOC_OPTIMIZE/ROUNDTO);
159         DBG("qm_malloc_init: QM_HASH_SIZE=%d, qm_block size=%d\n",
160                         QM_HASH_SIZE, sizeof(struct qm_block));
161         DBG("qm_malloc_init(%p, %d), start=%p\n", address, size, start);
162         if (size<start-address) return 0;
163         size-=(start-address);
164         if (size <(MIN_FRAG_SIZE+FRAG_OVERHEAD)) return 0;
165         size=ROUNDDOWN(size);
166         
167         init_overhead=ROUNDUP(sizeof(struct qm_block))+sizeof(struct qm_frag)+
168                 sizeof(struct qm_frag_end);
169         DBG("qm_malloc_init: size= %d, init_overhead=%d\n", size, init_overhead);
170         
171         if (size < init_overhead)
172         {
173                 /* not enough mem to create our control structures !!!*/
174                 return 0;
175         }
176         end=start+size;
177         qm=(struct qm_block*)start;
178         memset(qm, 0, sizeof(struct qm_block));
179         size-=init_overhead;
180         qm->size=size;
181         qm->real_used=init_overhead;
182         qm->max_real_used=qm->real_used;
183         
184         qm->first_frag=(struct qm_frag*)(start+ROUNDUP(sizeof(struct qm_block)));
185         qm->last_frag_end=(struct qm_frag_end*)(end-sizeof(struct qm_frag_end));
186         /* init initial fragment*/
187         qm->first_frag->size=size;
188         qm->last_frag_end->size=size;
189         
190 #ifdef DBG_QM_MALLOC
191         qm->first_frag->check=ST_CHECK_PATTERN;
192         qm->last_frag_end->check1=END_CHECK_PATTERN1;
193         qm->last_frag_end->check2=END_CHECK_PATTERN2;
194 #endif
195         /* init free_hash* */
196         for (h=0; h<QM_HASH_SIZE;h++){
197                 qm->free_hash[h].head.u.nxt_free=&(qm->free_hash[h].head);
198                 qm->free_hash[h].tail.prev_free=&(qm->free_hash[h].head);
199                 qm->free_hash[h].head.size=0;
200                 qm->free_hash[h].tail.size=0;
201         }
202         
203         /* link initial fragment into the free list*/
204         
205         qm_insert_free(qm, qm->first_frag);
206         
207         /*qm->first_frag->u.nxt_free=&(qm->free_lst);
208           qm->last_frag_end->prev_free=&(qm->free_lst);
209         */
210         
211         
212         return qm;
213 }
214
215
216
217 static inline void qm_detach_free(struct qm_block* qm, struct qm_frag* frag)
218 {
219         struct qm_frag *prev;
220         struct qm_frag *next;
221         
222         prev=FRAG_END(frag)->prev_free;
223         next=frag->u.nxt_free;
224         prev->u.nxt_free=next;
225         FRAG_END(next)->prev_free=prev;
226         
227 }
228
229
230
231 static inline struct qm_frag* qm_find_free(struct qm_block* qm, 
232                                                                                 unsigned int size)
233 {
234         int hash;
235         struct qm_frag* f;
236
237         for (hash=GET_HASH(size); hash<QM_HASH_SIZE; hash++){
238                 for (f=qm->free_hash[hash].head.u.nxt_free; 
239                                         f!=&(qm->free_hash[hash].head); f=f->u.nxt_free){
240                         if (f->size>=size) return f;
241                 }
242         /*try in a bigger bucket*/
243         }
244         /* not found */
245         return 0;
246 }
247
248
249
250 #ifdef DBG_QM_MALLOC
251 void* qm_malloc(struct qm_block* qm, unsigned int size, char* file, char* func,
252                                         unsigned int line)
253 #else
254 void* qm_malloc(struct qm_block* qm, unsigned int size)
255 #endif
256 {
257         struct qm_frag* f;
258         struct qm_frag_end* end;
259         struct qm_frag* n;
260         unsigned int rest;
261         
262 #ifdef DBG_QM_MALLOC
263         unsigned int list_cntr;
264
265         list_cntr = 0;
266         DBG("qm_malloc(%p, %d) called from %s: %s(%d)\n", qm, size, file, func,
267                         line);
268 #endif
269         /*size must be a multiple of 8*/
270         size=ROUNDUP(size);
271         if (size>(qm->size-qm->real_used)) return 0;
272
273         /*search for a suitable free frag*/
274         if ((f=qm_find_free(qm, size))!=0){
275                 /* we found it!*/
276                 /*detach it from the free list*/
277 #ifdef DBG_QM_MALLOC
278                         qm_debug_frag(qm, f);
279 #endif
280                 qm_detach_free(qm, f);
281                 /*mark it as "busy"*/
282                 f->u.is_free=0;
283                 
284                 /*see if we'll use full frag, or we'll split it in 2*/
285                 rest=f->size-size;
286                 if (rest>(FRAG_OVERHEAD+MIN_FRAG_SIZE)){
287                         f->size=size;
288                         /*split the fragment*/
289                         end=FRAG_END(f);
290                         end->size=size;
291                         n=(struct qm_frag*)((char*)end+sizeof(struct qm_frag_end));
292                         n->size=rest-FRAG_OVERHEAD;
293                         FRAG_END(n)->size=n->size;
294                         qm->real_used+=FRAG_OVERHEAD;
295 #ifdef DBG_QM_MALLOC
296                         end->check1=END_CHECK_PATTERN1;
297                         end->check2=END_CHECK_PATTERN2;
298                         /* frag created by malloc, mark it*/
299                         n->file=file;
300                         n->func="frag. from qm_malloc";
301                         n->line=line;
302                         n->check=ST_CHECK_PATTERN;
303 /*                      FRAG_END(n)->check1=END_CHECK_PATTERN1;
304                         FRAG_END(n)->check2=END_CHECK_PATTERN2; */
305 #endif
306                         /* reinsert n in free list*/
307                         qm_insert_free(qm, n);
308                 }else{
309                         /* we cannot split this fragment any more => alloc all of it*/
310                 }
311                 qm->real_used+=f->size;
312                 qm->used+=f->size;
313                 if (qm->max_real_used<qm->real_used)
314                         qm->max_real_used=qm->real_used;
315 #ifdef DBG_QM_MALLOC
316                 f->file=file;
317                 f->func=func;
318                 f->line=line;
319                 f->check=ST_CHECK_PATTERN;
320                 /*  FRAG_END(f)->check1=END_CHECK_PATTERN1;
321                         FRAG_END(f)->check2=END_CHECK_PATTERN2;*/
322                 DBG("qm_malloc(%p, %d) returns address %p on %d -th hit\n", qm, size,
323                         (char*)f+sizeof(struct qm_frag), list_cntr );
324 #endif
325                 return (char*)f+sizeof(struct qm_frag);
326         }
327         return 0;
328 }
329
330
331
332 #ifdef DBG_QM_MALLOC
333 void qm_free(struct qm_block* qm, void* p, char* file, char* func, 
334                                 unsigned int line)
335 #else
336 void qm_free(struct qm_block* qm, void* p)
337 #endif
338 {
339         struct qm_frag* f;
340         struct qm_frag* prev;
341         struct qm_frag* next;
342         unsigned int size;
343
344 #ifdef DBG_QM_MALLOC
345         DBG("qm_free(%p, %p), called from %s: %s(%d)\n", qm, p, file, func, line);
346         if (p>(void*)qm->last_frag_end || p<(void*)qm->first_frag){
347                 LOG(L_CRIT, "BUG: qm_free: bad pointer %p (out of memory block!) - "
348                                 "aborting\n", p);
349                 abort();
350         }
351 #endif
352         if (p==0) {
353                 LOG(L_WARN, "WARNING:qm_free: free(0) called\n");
354                 return;
355         }
356         prev=next=0;
357         f=(struct qm_frag*) ((char*)p-sizeof(struct qm_frag));
358 #ifdef DBG_QM_MALLOC
359         qm_debug_frag(qm, f);
360         if (f->u.is_free){
361                 LOG(L_CRIT, "BUG: qm_free: freeing already freed pointer,"
362                                 " first free: %s: %s(%d) - aborting\n",
363                                 f->file, f->func, f->line);
364                 abort();
365         }
366         DBG("qm_free: freeing block alloc'ed from %s: %s(%d)\n", f->file, f->func,
367                         f->line);
368 #endif
369         size=f->size;
370         qm->used-=size;
371         qm->real_used-=size;
372 #ifdef DBG_QM_MALLOC
373         qm_debug_frag(qm, f);
374 #endif
375
376 #ifdef QM_JOIN_FREE
377         /* join packets if possible*/
378         next=FRAG_NEXT(f);
379         if (((char*)next < (char*)qm->last_frag_end) &&( next->u.is_free)){
380                 /* join */
381                 qm_detach_free(qm, next);
382                 size+=next->size+FRAG_OVERHEAD;
383                 qm->real_used-=FRAG_OVERHEAD;
384         }
385         
386         if (f > qm->first_frag){
387                 prev=FRAG_PREV(f);
388                 /*      (struct qm_frag*)((char*)f - (struct qm_frag_end*)((char*)f-
389                                                                 sizeof(struct qm_frag_end))->size);*/
390 #ifdef DBG_QM_MALLOC
391                 qm_debug_frag(qm, f);
392 #endif
393                 if (prev->u.is_free){
394                         /*join*/
395                         qm_detach_free(qm, prev);
396                         size+=prev->size+FRAG_OVERHEAD;
397                         qm->real_used-=FRAG_OVERHEAD;
398                         f=prev;
399                 }
400         }
401         f->size=size;
402         FRAG_END(f)->size=f->size;
403 #endif /* QM_JOIN_FREE*/
404 #ifdef DBG_QM_MALLOC
405         f->file=file;
406         f->func=func;
407         f->line=line;
408 #endif
409         qm_insert_free(qm, f);
410 }
411
412
413
414 void qm_status(struct qm_block* qm)
415 {
416         struct qm_frag* f;
417         int i,j;
418         int h;
419
420         LOG(memlog, "qm_status (%p):\n", qm);
421         if (!qm) return;
422
423         LOG(memlog, " heap size= %d\n", qm->size);
424         LOG(memlog, " used= %d, used+overhead=%d, free=%d\n",
425                         qm->used, qm->real_used, qm->size-qm->real_used);
426         LOG(memlog, " max used (+overhead)= %d\n", qm->max_real_used);
427         
428         LOG(memlog, "dumping all allocked. fragments:\n");
429         for (f=qm->first_frag, i=0;(char*)f<(char*)qm->last_frag_end;f=FRAG_NEXT(f)
430                         ,i++){
431                 if (! f->u.is_free){
432                         LOG(memlog, "    %3d. %c  address=%p  size=%d\n", i, 
433                                 (f->u.is_free)?'a':'N',
434                                 (char*)f+sizeof(struct qm_frag), f->size);
435 #ifdef DBG_QM_MALLOC
436                         LOG(memlog, "            %s from %s: %s(%d)\n",
437                                 (f->u.is_free)?"freed":"alloc'd", f->file, f->func, f->line);
438                         LOG(memlog, "        start check=%x, end check= %x, %x\n",
439                                 f->check, FRAG_END(f)->check1, FRAG_END(f)->check2);
440 #endif
441                 }
442         }
443         LOG(memlog, "dumping free list stats :\n");
444         for(h=0,i=0;h<QM_HASH_SIZE;h++){
445                 
446                 for (f=qm->free_hash[h].head.u.nxt_free,j=0; 
447                                 f!=&(qm->free_hash[h].head); f=f->u.nxt_free, i++, j++);
448                         if (j) LOG(memlog, "hash= %3d. fragments no.: %5d\n", h, j);
449         }
450         LOG(memlog, "-----------------------------\n");
451 }
452
453
454
455
456 #endif