d6c2aec77cf89cf320cac341508f11c48d95a9db
[sip-router] / mem / f_malloc.c
1 /* $Id$
2  *
3  */
4
5 #if !defined(q_malloc) && !(defined VQ_MALLOC) 
6
7 #include <string.h>
8
9 #include "f_malloc.h"
10 #include "../dprint.h"
11 #include "../globals.h"
12
13
14 /*useful macros*/
15
16 #define FRAG_NEXT(f) \
17         ((struct fm_frag*)((char*)(f)+sizeof(struct fm_frag)+(f)->size ))
18
19 #define FRAG_OVERHEAD   (sizeof(struct fm_frag))
20
21
22 /* ROUNDTO= 2^k so the following works */
23 #define ROUNDTO_MASK    (~((unsigned long)ROUNDTO-1))
24 #define ROUNDUP(s)              (((s)+(ROUNDTO-1))&ROUNDTO_MASK)
25 #define ROUNDDOWN(s)    ((s)&ROUNDTO_MASK)
26
27 /*
28  #define ROUNDUP(s)             (((s)%ROUNDTO)?((s)+ROUNDTO)/ROUNDTO*ROUNDTO:(s))
29  #define ROUNDDOWN(s)   (((s)%ROUNDTO)?((s)-ROUNDTO)/ROUNDTO*ROUNDTO:(s))
30 */
31
32
33
34         /* finds the hash value for s, s=ROUNDTO multiple*/
35 #define GET_HASH(s)   ( ((s)<F_MALLOC_OPTIMIZE)?(s)/ROUNDTO: \
36                                                 F_MALLOC_OPTIMIZE/ROUNDTO+big_hash_idx((s))- \
37                                                         F_MALLOC_OPTIMIZE_FACTOR+1 )
38
39 #define UN_HASH(h)      ( ((h)<(F_MALLOC_OPTIMIZE/ROUNDTO))?(h)*ROUNDTO: \
40                                                 1<<((h)-F_MALLOC_OPTIMIZE/ROUNDTO+\
41                                                         F_MALLOC_OPTIMIZE_FACTOR-1)\
42                                         )
43
44
45 /* computes hash number for big buckets*/
46 inline static int big_hash_idx(int s)
47 {
48         int idx;
49         /* s is rounded => s = k*2^n (ROUNDTO=2^n) 
50          * index= i such that 2^i > s >= 2^(i-1)
51          *
52          * => index = number of the first non null bit in s*/
53         for (idx=31; !(s&0x80000000) ; s<<=1, idx--);
54         return idx;
55 }
56
57
58 #ifdef DBG_F_MALLOC
59 #define ST_CHECK_PATTERN   0xf0f0f0f0
60 #define END_CHECK_PATTERN1 0xc0c0c0c0
61 #define END_CHECK_PATTERN2 0xabcdefed
62 #endif
63
64
65
66 static inline void fm_insert_free(struct fm_block* qm, struct fm_frag* frag)
67 {
68         struct fm_frag** f;
69         int hash;
70         
71         hash=GET_HASH(frag->size);
72         f=&(qm->free_hash[hash]);
73         if (frag->size > F_MALLOC_OPTIMIZE){
74                 for(; *f; f=&((*f)->u.nxt_free)){
75                         if (frag->size <= (*f)->size) break;
76                 }
77         }
78         
79         /*insert it here*/
80         frag->u.nxt_free=*f;
81         *f=frag;
82 }
83
84
85
86 /* init malloc and return a qm_block*/
87 struct fm_block* fm_malloc_init(char* address, unsigned int size)
88 {
89         char* start;
90         char* end;
91         struct fm_block* qm;
92         unsigned int init_overhead;
93         
94         /* make address and size multiple of 8*/
95         start=(char*)ROUNDUP((unsigned int) address);
96         if (size<start-address) return 0;
97         size-=(start-address);
98         if (size <(MIN_FRAG_SIZE+FRAG_OVERHEAD)) return 0;
99         size=ROUNDDOWN(size);
100
101         init_overhead=(ROUNDUP(sizeof(struct fm_block))+sizeof(struct fm_frag));
102         
103         
104         if (size < init_overhead)
105         {
106                 /* not enough mem to create our control structures !!!*/
107                 return 0;
108         }
109         end=start+size;
110         qm=(struct fm_block*)start;
111         memset(qm, 0, sizeof(struct fm_block));
112         size-=init_overhead;
113         qm->size=size;
114 #ifdef DBG_F_MALLOC
115         qm->real_used=init_overhead;
116         qm->max_real_used=qm->real_used;
117 #endif
118         
119         qm->first_frag=(struct fm_frag*)(start+ROUNDUP(sizeof(struct fm_block)));
120         qm->last_frag=(struct fm_frag*)(end-sizeof(struct fm_frag));
121         /* init initial fragment*/
122         qm->first_frag->size=size;
123         qm->last_frag->size=0;
124         
125 #ifdef DBG_F_MALLOC
126         qm->first_frag->check=ST_CHECK_PATTERN;
127         qm->last_frag->check=END_CHECK_PATTERN1;
128 #endif
129         
130         /* link initial fragment into the free list*/
131         
132         fm_insert_free(qm, qm->first_frag);
133         
134         
135         return qm;
136 }
137
138
139
140 #ifdef DBG_F_MALLOC
141 void* fm_malloc(struct fm_block* qm, unsigned int size, char* file, char* func,
142                                         unsigned int line)
143 #else
144 void* fm_malloc(struct fm_block* qm, unsigned int size)
145 #endif
146 {
147         struct fm_frag** f;
148         struct fm_frag* frag;
149         struct fm_frag* n;
150         unsigned int rest;
151         int hash;
152         
153 #ifdef DBG_F_MALLOC
154         DBG("fm_malloc(%x, %d) called from %s: %s(%d)\n", qm, size, file, func,
155                         line);
156 #endif
157         /*size must be a multiple of 8*/
158         size=ROUNDUP(size);
159 /*      if (size>(qm->size-qm->real_used)) return 0; */
160
161         
162         /*search for a suitable free frag*/
163
164         for(hash=GET_HASH(size);hash<F_HASH_SIZE;hash++){
165                 f=&(qm->free_hash[hash]);
166                 for(;(*f); f=&((*f)->u.nxt_free))
167                         if ((*f)->size>=size) goto found;
168                 /* try in a bigger bucket */
169         }
170         /* not found, bad! */
171         return 0;
172
173 found:
174         /* we found it!*/
175         /* detach it from the free list*/
176         frag=*f;
177         *f=frag->u.nxt_free;
178         
179         /*see if we'll use full frag, or we'll split it in 2*/
180         rest=frag->size-size;
181         if (rest>(FRAG_OVERHEAD+MIN_FRAG_SIZE)){
182                 frag->size=size;
183                 /*split the fragment*/
184                 n=FRAG_NEXT(frag);
185                 n->size=rest-FRAG_OVERHEAD;
186 #ifdef DBG_F_MALLOC
187                 qm->real_used+=FRAG_OVERHEAD;
188                 /* frag created by malloc, mark it*/
189                 n->file=file;
190                 n->func="frag. from qm_malloc";
191                 n->line=line;
192                 n->check=ST_CHECK_PATTERN;
193 #endif
194                 /* reinsert n in free list*/
195                 fm_insert_free(qm, n);
196         }else{
197                 /* we cannot split this fragment any more => alloc all of it*/
198         }
199 #ifdef DBG_F_MALLOC
200         qm->real_used+=frag->size;
201         qm->used+=frag->size;
202
203         if (qm->max_real_used<qm->real_used)
204                 qm->max_real_used=qm->real_used;
205
206         frag->file=file;
207         frag->func=func;
208         frag->line=line;
209         frag->check=ST_CHECK_PATTERN;
210         DBG("fm_malloc(%x, %d) returns address %x \n", qm, size,
211                 (char*)frag+sizeof(struct fm_frag));
212 #endif
213         return (char*)frag+sizeof(struct fm_frag);
214 }
215
216
217
218 #ifdef DBG_F_MALLOC
219 void fm_free(struct fm_block* qm, void* p, char* file, char* func, 
220                                 unsigned int line)
221 #else
222 void fm_free(struct fm_block* qm, void* p)
223 #endif
224 {
225         struct fm_frag* f;
226         unsigned int size;
227
228 #ifdef DBG_F_MALLOC
229         DBG("fm_free(%x, %x), called from %s: %s(%d)\n", qm, p, file, func, line);
230         if (p>(void*)qm->last_frag || p<(void*)qm->first_frag){
231                 LOG(L_CRIT, "BUG: fm_free: bad pointer %x (out of memory block!) - "
232                                 "aborting\n", p);
233                 abort();
234         }
235 #endif
236         if (p==0) {
237                 LOG(L_WARN, "WARNING:fm_free: free(0) called\n");
238                 return;
239         }
240         f=(struct fm_frag*) ((char*)p-sizeof(struct fm_frag));
241 #ifdef DBG_F_MALLOC
242         DBG("fm_free: freeing block alloc'ed from %s: %s(%d)\n", f->file, f->func,
243                         f->line);
244 #endif
245         size=f->size;
246
247 #ifdef DBG_F_MALLOC
248         qm->used-=size;
249         qm->real_used-=size;
250         f->file=file;
251         f->func=func;
252         f->line=line;
253 #endif
254         fm_insert_free(qm, f);
255 }
256
257
258
259 void fm_status(struct fm_block* qm)
260 {
261         struct fm_frag* f;
262         int i,j;
263         int h;
264         int size;
265
266         LOG(memlog, "fm_status (%p):\n", qm);
267         if (!qm) return;
268
269         LOG(memlog, " heap size= %d\n", qm->size);
270 #ifdef DBG_F_MALLOC
271         LOG(memlog, " used= %d, used+overhead=%d, free=%d\n",
272                         qm->used, qm->real_used, qm->size-qm->real_used);
273         LOG(memlog, " max used (+overhead)= %d\n", qm->max_real_used);
274 #endif
275         /*
276         LOG(memlog, "dumping all fragments:\n");
277         for (f=qm->first_frag, i=0;((char*)f<(char*)qm->last_frag) && (i<10);
278                         f=FRAG_NEXT(f), i++){
279                 LOG(memlog, "    %3d. %c  address=%x  size=%d\n", i, 
280                                 (f->u.reserved)?'a':'N',
281                                 (char*)f+sizeof(struct fm_frag), f->size);
282 #ifdef DBG_F_MALLOC
283                 LOG(memlog, "            %s from %s: %s(%d)\n",
284                                 (f->u.is_free)?"freed":"alloc'd", f->file, f->func, f->line);
285 #endif
286         }
287 */
288         LOG(memlog, "dumping free list:\n");
289         for(h=0,i=0,size=0;h<F_HASH_SIZE;h++){
290                 
291                 for (f=qm->free_hash[h],j=0; f; size+=f->size,f=f->u.nxt_free,i++,j++);
292                 if (j) LOG(memlog, "hash = %3d fragments no.: %5d,\n\t\t"
293                                                         " bucket size: %9d - %9d (first %9d)\n",
294                                                         h, j, UN_HASH(h),
295                                                         ((h<F_MALLOC_OPTIMIZE/ROUNDTO)?1:2)*UN_HASH(h),
296                                                         qm->free_hash[h]->size
297                                 );
298                 /*
299                 {
300                         LOG(memlog, "   %5d.[%3d:%3d] %c  address=%x  size=%d(%x)\n",
301                                         i, h, j,
302                                         (f->u.reserved)?'a':'N',
303                                         (char*)f+sizeof(struct fm_frag), f->size, f->size);
304 #ifdef DBG_F_MALLOC
305                         DBG("            %s from %s: %s(%d)\n", 
306                                 (f->u.reserved)?"freed":"alloc'd", f->file, f->func, f->line);
307 #endif
308                 }
309         */
310         }
311         LOG(memlog, "TOTAL: %6d free fragments = %6d free bytes\n", i, size);
312         LOG(memlog, "-----------------------------\n");
313 }
314
315
316
317
318 #endif