48cd8b154f297a2b9148a0c315fe0c71b02ba3c5
[sip-router] / mem / f_malloc.c
1 /* $Id$
2  *
3  *
4  * Copyright (C) 2001-2003 FhG Fokus
5  *
6  * This file is part of sip-router, a free SIP server.
7  *
8  * Permission to use, copy, modify, and distribute this software for any
9  * purpose with or without fee is hereby granted, provided that the above
10  * copyright notice and this permission notice appear in all copies.
11  *
12  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19  */
20 /*
21  * History:
22  * --------
23  *              created by andrei
24  *  2003-07-06  added fm_realloc (andrei)
25  *  2004-07-19  fragments book keeping code and support for 64 bits
26  *               memory blocks (64 bits machine & size >=2^32) 
27  *              GET_HASH s/</<=/ (avoids waste of 1 hash cell)   (andrei)
28  *  2004-11-10  support for > 4Gb mem., switched to long (andrei)
29  *  2005-03-02  added fm_info() (andrei)
30  *  2005-12-12  fixed realloc shrink real_used accounting (andrei)
31  *              fixed initial size (andrei)
32  *  2006-02-03  fixed realloc out of mem. free bug (andrei)
33  *  2006-04-07  s/DBG/MDBG (andrei)
34  *  2007-02-23  added fm_available() (andrei)
35  *  2007-06-23  added hash bitmap (andrei)
36  *  2009-09-28  added fm_sums() (patch from Dragos Vingarzan)
37  *  2010-03-11  fix big fragments bug (smaller fragment was wrongly
38  *               returned sometimes) (andrei)
39  *  2010-03-12  fix real_used stats for realloc: a realloc that shrank an
40  *               allocation accounted twice fro the frag. overhead (andrei)
41  *  2010-09-30  fixed search for big fragments using the hash bitmap
42  *               (only the first bucket was tried) (andrei)
43  */
44
45
46 #if !defined(q_malloc)  && (defined F_MALLOC)
47
48 #include <string.h>
49 #include <stdlib.h>
50
51 #include "f_malloc.h"
52 #include "../dprint.h"
53 #include "../globals.h"
54 #include "../compiler_opt.h"
55 #include "memdbg.h"
56 #include "../bit_scan.h"
57 #include "../cfg/cfg.h" /* memlog */
58 #ifdef MALLOC_STATS
59 #include "../events.h"
60 #endif
61
62
63 /*useful macros*/
64
65 #define FRAG_NEXT(f) \
66         ((struct fm_frag*)((char*)(f)+sizeof(struct fm_frag)+(f)->size ))
67
68 #define FRAG_OVERHEAD   (sizeof(struct fm_frag))
69 #define INIT_OVERHEAD   \
70         (ROUNDUP(sizeof(struct fm_block))+sizeof(struct fm_frag))
71
72
73
74 /* ROUNDTO= 2^k so the following works */
75 #define ROUNDTO_MASK    (~((unsigned long)ROUNDTO-1))
76 #define ROUNDUP(s)              (((s)+(ROUNDTO-1))&ROUNDTO_MASK)
77 #define ROUNDDOWN(s)    ((s)&ROUNDTO_MASK)
78
79 /*
80  #define ROUNDUP(s)             (((s)%ROUNDTO)?((s)+ROUNDTO)/ROUNDTO*ROUNDTO:(s))
81  #define ROUNDDOWN(s)   (((s)%ROUNDTO)?((s)-ROUNDTO)/ROUNDTO*ROUNDTO:(s))
82 */
83
84
85
86         /* finds the hash value for s, s=ROUNDTO multiple*/
87 #define GET_HASH(s)   ( ((unsigned long)(s)<=F_MALLOC_OPTIMIZE)?\
88                                                         (unsigned long)(s)/ROUNDTO: \
89                                                         F_MALLOC_OPTIMIZE/ROUNDTO+big_hash_idx((s))- \
90                                                                 F_MALLOC_OPTIMIZE_FACTOR+1 )
91
92 #define UN_HASH(h)      ( ((unsigned long)(h)<=(F_MALLOC_OPTIMIZE/ROUNDTO))?\
93                                                 (unsigned long)(h)*ROUNDTO: \
94                                                 1UL<<((unsigned long)(h)-F_MALLOC_OPTIMIZE/ROUNDTO+\
95                                                         F_MALLOC_OPTIMIZE_FACTOR-1)\
96                                         )
97
98 #ifdef F_MALLOC_HASH_BITMAP
99
100 #define fm_bmp_set(qm, b) \
101         do{ \
102                 (qm)->free_bitmap[(b)/FM_HASH_BMP_BITS] |= \
103                                                                                         1UL<<((b)%FM_HASH_BMP_BITS); \
104         }while(0)
105
106 #define fm_bmp_reset(qm, b) \
107         do{ \
108                 (qm)->free_bitmap[(b)/FM_HASH_BMP_BITS] &= \
109                                                                                         ~(1UL<<((b)%FM_HASH_BMP_BITS)); \
110         }while(0)
111
112 /* returns 0 if not set, !=0 if set */
113 #define fm_bmp_is_set(qm, b) \
114         ((qm)->free_bitmap[(b)/FM_HASH_BMP_BITS] & (1UL<<((b)%FM_HASH_BMP_BITS)))
115
116 inline static int fm_bmp_first_set(struct fm_block* qm, int start)
117 {
118         int bmp_idx;
119         int bit;
120         int r;
121         fm_hash_bitmap_t test_val;
122         fm_hash_bitmap_t v;
123         
124         bmp_idx=start/FM_HASH_BMP_BITS;
125         bit=start%FM_HASH_BMP_BITS;
126         test_val=1UL <<((unsigned long)bit);
127         if (qm->free_bitmap[bmp_idx] & test_val)
128                 return start;
129         else if (qm->free_bitmap[bmp_idx] & ~(test_val-1)){
130 #if 0
131                 test_val<<=1;
132                 for (r=bit+1; r<FM_HASH_BMP_BITS; r++, test_val<<=1){
133                         if (qm->free_bitmap[bmp_idx] & test_val)
134                                 return (start-bit+r);
135                 }
136 #endif
137                 v=qm->free_bitmap[bmp_idx]>>(bit+1);
138                 return start+1+bit_scan_forward((unsigned long)v);
139         }
140         for (r=bmp_idx+1;r<FM_HASH_BMP_SIZE; r++){
141                 if (qm->free_bitmap[r]){
142                         /* find first set bit */
143                         return r*FM_HASH_BMP_BITS+
144                                                 bit_scan_forward((unsigned long)qm->free_bitmap[r]);
145                 }
146         }
147         /* not found, nothing free */
148         return -1;
149 }
150 #endif /* F_MALLOC_HASH_BITMAP */
151
152
153
154 /* mark/test used/unused frags */
155 #define FRAG_MARK_USED(f)
156 #define FRAG_CLEAR_USED(f)
157 #define FRAG_WAS_USED(f)   (1)
158
159 /* other frag related defines:
160  * MEM_COALESCE_FRAGS 
161  * MEM_FRAG_AVOIDANCE
162  */
163 #define MEM_FRAG_AVOIDANCE
164
165
166 /* computes hash number for big buckets*/
167 #if 0
168 inline static unsigned long big_hash_idx(unsigned long s)
169 {
170         unsigned long idx;
171         /* s is rounded => s = k*2^n (ROUNDTO=2^n) 
172          * index= i such that 2^(i+1) > s >= 2^i
173          *
174          * => index = number of the first non null bit in s*/
175         idx=sizeof(long)*8-1;
176         for (; !(s&(1UL<<(sizeof(long)*8-1))) ; s<<=1, idx--);
177         return idx;
178 }
179 #else
180 #define big_hash_idx(s) ((unsigned long)bit_scan_reverse((unsigned long)(s)))
181 #endif
182
183
184 #ifdef DBG_F_MALLOC
185 #define ST_CHECK_PATTERN   0xf0f0f0f0
186 #define END_CHECK_PATTERN1 0xc0c0c0c0
187 #define END_CHECK_PATTERN2 0xabcdefed
188 #endif
189
190
191
192 static inline void fm_insert_free(struct fm_block* qm, struct fm_frag* frag)
193 {
194         struct fm_frag** f;
195         int hash;
196         
197         hash=GET_HASH(frag->size);
198         f=&(qm->free_hash[hash].first);
199         if (frag->size > F_MALLOC_OPTIMIZE){ /* because of '<=' in GET_HASH,
200                                                                                         (different from 0.8.1[24] on
201                                                                                          purpose --andrei ) */
202                 for(; *f; f=&((*f)->u.nxt_free)){
203                         if (frag->size <= (*f)->size) break;
204                 }
205         }
206         
207         /*insert it here*/
208         frag->u.nxt_free=*f;
209         *f=frag;
210         qm->free_hash[hash].no++;
211 #ifdef F_MALLOC_HASH_BITMAP
212         fm_bmp_set(qm, hash);
213 #endif /* F_MALLOC_HASH_BITMAP */
214 }
215
216
217
218  /* size should be already rounded-up */
219 static inline
220 #ifdef DBG_F_MALLOC 
221 void fm_split_frag(struct fm_block* qm, struct fm_frag* frag,
222                                         unsigned long size,
223                                         const char* file, const char* func, unsigned int line)
224 #else
225 void fm_split_frag(struct fm_block* qm, struct fm_frag* frag,
226                                         unsigned long size)
227 #endif
228 {
229         unsigned long rest;
230         struct fm_frag* n;
231         
232         rest=frag->size-size;
233 #ifdef MEM_FRAG_AVOIDANCE
234         if ((rest> (FRAG_OVERHEAD+F_MALLOC_OPTIMIZE))||
235                 (rest>=(FRAG_OVERHEAD+size))){ /* the residue fragm. is big enough*/
236 #else
237         if (rest>(FRAG_OVERHEAD+MIN_FRAG_SIZE)){
238 #endif
239                 frag->size=size;
240                 /*split the fragment*/
241                 n=FRAG_NEXT(frag);
242                 n->size=rest-FRAG_OVERHEAD;
243                 FRAG_CLEAR_USED(n); /* never used */
244 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
245                 qm->real_used+=FRAG_OVERHEAD;
246 #ifdef MALLOC_STATS
247                 sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
248 #endif
249 #endif
250 #ifdef DBG_F_MALLOC
251                 /* frag created by malloc, mark it*/
252                 n->file=file;
253                 n->func="frag. from fm_malloc";
254                 n->line=line;
255                 n->check=ST_CHECK_PATTERN;
256 #endif
257                 /* reinsert n in free list*/
258                 fm_insert_free(qm, n);
259         }else{
260                 /* we cannot split this fragment any more => alloc all of it*/
261         }
262 }
263
264
265
266 /* init malloc and return a fm_block*/
267 struct fm_block* fm_malloc_init(char* address, unsigned long size)
268 {
269         char* start;
270         char* end;
271         struct fm_block* qm;
272         unsigned long init_overhead;
273         
274         /* make address and size multiple of 8*/
275         start=(char*)ROUNDUP((unsigned long) address);
276         DBG("fm_malloc_init: F_OPTIMIZE=%lu, /ROUNDTO=%lu\n",
277                         F_MALLOC_OPTIMIZE, F_MALLOC_OPTIMIZE/ROUNDTO);
278         DBG("fm_malloc_init: F_HASH_SIZE=%lu, fm_block size=%lu\n",
279                         F_HASH_SIZE, (long)sizeof(struct fm_block));
280         DBG("fm_malloc_init(%p, %lu), start=%p\n", address, size, start);
281
282         if (size<start-address) return 0;
283         size-=(start-address);
284         if (size <(MIN_FRAG_SIZE+FRAG_OVERHEAD)) return 0;
285         size=ROUNDDOWN(size);
286
287         init_overhead=INIT_OVERHEAD;
288         
289         
290         if (size < init_overhead)
291         {
292                 /* not enough mem to create our control structures !!!*/
293                 return 0;
294         }
295         end=start+size;
296         qm=(struct fm_block*)start;
297         memset(qm, 0, sizeof(struct fm_block));
298         qm->size=size;
299 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
300         qm->real_used=init_overhead;
301         qm->max_real_used=qm->real_used;
302 #endif
303         size-=init_overhead;
304         
305         qm->first_frag=(struct fm_frag*)(start+ROUNDUP(sizeof(struct fm_block)));
306         qm->last_frag=(struct fm_frag*)(end-sizeof(struct fm_frag));
307         /* init initial fragment*/
308         qm->first_frag->size=size;
309         qm->last_frag->size=0;
310         
311 #ifdef DBG_F_MALLOC
312         qm->first_frag->check=ST_CHECK_PATTERN;
313         qm->last_frag->check=END_CHECK_PATTERN1;
314 #endif
315         
316         /* link initial fragment into the free list*/
317         
318         fm_insert_free(qm, qm->first_frag);
319         
320         
321         return qm;
322 }
323
324
325
326 #ifdef DBG_F_MALLOC
327 void* fm_malloc(struct fm_block* qm, unsigned long size,
328                                         const char* file, const char* func, unsigned int line)
329 #else
330 void* fm_malloc(struct fm_block* qm, unsigned long size)
331 #endif
332 {
333         struct fm_frag** f;
334         struct fm_frag* frag;
335         int hash;
336         
337 #ifdef DBG_F_MALLOC
338         MDBG("fm_malloc(%p, %lu) called from %s: %s(%d)\n", qm, size, file, func,
339                         line);
340 #endif
341         /*size must be a multiple of 8*/
342         size=ROUNDUP(size);
343 /*      if (size>(qm->size-qm->real_used)) return 0; */
344
345         
346         /*search for a suitable free frag*/
347
348 #ifdef F_MALLOC_HASH_BITMAP
349         hash=fm_bmp_first_set(qm, GET_HASH(size));
350         if (likely(hash>=0)){
351                 if (likely(hash<=F_MALLOC_OPTIMIZE/ROUNDTO)) { /* return first match */
352                         f=&(qm->free_hash[hash].first);
353                         goto found;
354                 }
355                 /* if we are here we are searching for a "big" fragment
356                    between F_MALLOC_OPTIMIZE/ROUNDTO+1
357                    and F_MALLOC_OPTIMIZE/ROUNDTO + (32|64) - F_MALLOC_OPTIMIZE_FACTOR
358                    => 18 hash buckets on 32 bits and 50 buckets on 64 bits
359                    The free hash bitmap is used to jump directly to non-empty
360                    hash buckets.
361                 */
362                 do {
363                         for(f=&(qm->free_hash[hash].first);(*f); f=&((*f)->u.nxt_free))
364                                 if ((*f)->size>=size) goto found;
365                         hash++; /* try in next hash cell */
366                 }while((hash < F_HASH_SIZE) &&
367                                 ((hash=fm_bmp_first_set(qm, hash)) >= 0));
368         }
369 #else /* F_MALLOC_HASH_BITMAP */
370         for(hash=GET_HASH(size);hash<F_HASH_SIZE;hash++){
371                 f=&(qm->free_hash[hash].first);
372 #if 0
373                 if (likely(hash<=F_MALLOC_OPTIMIZE/ROUNDTO)) /* return first match */
374                                 goto found; 
375 #endif
376                 for(;(*f); f=&((*f)->u.nxt_free))
377                         if ((*f)->size>=size) goto found;
378                 /* try in a bigger bucket */
379         }
380 #endif /* F_MALLOC_HASH_BITMAP */
381         /* not found, bad! */
382         return 0;
383
384 found:
385         /* we found it!*/
386         /* detach it from the free list*/
387         frag=*f;
388         *f=frag->u.nxt_free;
389         frag->u.nxt_free=0; /* mark it as 'taken' */
390         qm->free_hash[hash].no--;
391 #ifdef F_MALLOC_HASH_BITMAP
392         if (qm->free_hash[hash].no==0)
393                 fm_bmp_reset(qm, hash);
394 #endif /* F_MALLOC_HASH_BITMAP */
395         
396         /*see if we'll use full frag, or we'll split it in 2*/
397         
398 #ifdef DBG_F_MALLOC
399         fm_split_frag(qm, frag, size, file, func, line);
400
401         frag->file=file;
402         frag->func=func;
403         frag->line=line;
404         frag->check=ST_CHECK_PATTERN;
405         MDBG("fm_malloc(%p, %lu) returns address %p \n", qm, size,
406                 (char*)frag+sizeof(struct fm_frag));
407 #else
408         fm_split_frag(qm, frag, size);
409 #endif
410 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
411         qm->real_used+=frag->size;
412         qm->used+=frag->size;
413         if (qm->max_real_used<qm->real_used)
414                 qm->max_real_used=qm->real_used;
415 #ifdef MALLOC_STATS
416         sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
417         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
418 #endif
419 #endif
420         FRAG_MARK_USED(frag); /* mark it as used */
421         return (char*)frag+sizeof(struct fm_frag);
422 }
423
424
425
426 #ifdef DBG_F_MALLOC
427 void fm_free(struct fm_block* qm, void* p, const char* file, const char* func, 
428                                 unsigned int line)
429 #else
430 void fm_free(struct fm_block* qm, void* p)
431 #endif
432 {
433         struct fm_frag* f;
434         unsigned long size;
435
436 #ifdef DBG_F_MALLOC
437         MDBG("fm_free(%p, %p), called from %s: %s(%d)\n", qm, p, file, func, line);
438         if (p>(void*)qm->last_frag || p<(void*)qm->first_frag){
439                 LOG(L_CRIT, "BUG: fm_free: bad pointer %p (out of memory block!) - "
440                                 "aborting\n", p);
441                 abort();
442         }
443 #endif
444         if (p==0) {
445                 LOG(L_WARN, "WARNING:fm_free: free(0) called\n");
446                 return;
447         }
448         f=(struct fm_frag*) ((char*)p-sizeof(struct fm_frag));
449 #ifdef DBG_F_MALLOC
450         MDBG("fm_free: freeing block alloc'ed from %s: %s(%ld)\n",
451                         f->file, f->func, f->line);
452 #endif
453         size=f->size;
454 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
455         qm->used-=size;
456         qm->real_used-=size;
457 #ifdef MALLOC_STATS
458         sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
459         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
460 #endif
461 #endif
462 #ifdef DBG_F_MALLOC
463         f->file=file;
464         f->func=func;
465         f->line=line;
466 #endif
467         fm_insert_free(qm, f);
468 }
469
470
471 #ifdef DBG_F_MALLOC
472 void* fm_realloc(struct fm_block* qm, void* p, unsigned long size,
473                                         const char* file, const char* func, unsigned int line)
474 #else
475 void* fm_realloc(struct fm_block* qm, void* p, unsigned long size)
476 #endif
477 {
478         struct fm_frag *f;
479         struct fm_frag **pf;
480         unsigned long diff;
481         unsigned long orig_size;
482         struct fm_frag *n;
483         void *ptr;
484         int hash;
485         
486 #ifdef DBG_F_MALLOC
487         MDBG("fm_realloc(%p, %p, %lu) called from %s: %s(%d)\n", qm, p, size,
488                         file, func, line);
489         if ((p)&&(p>(void*)qm->last_frag || p<(void*)qm->first_frag)){
490                 LOG(L_CRIT, "BUG: fm_free: bad pointer %p (out of memory block!) - "
491                                 "aborting\n", p);
492                 abort();
493         }
494 #endif
495         if (size==0) {
496                 if (p)
497 #ifdef DBG_F_MALLOC
498                         fm_free(qm, p, file, func, line);
499 #else
500                         fm_free(qm, p);
501 #endif
502                 return 0;
503         }
504         if (p==0)
505 #ifdef DBG_F_MALLOC
506                 return fm_malloc(qm, size, file, func, line);
507 #else
508                 return fm_malloc(qm, size);
509 #endif
510         f=(struct fm_frag*) ((char*)p-sizeof(struct fm_frag));
511 #ifdef DBG_F_MALLOC
512         MDBG("fm_realloc: realloc'ing frag %p alloc'ed from %s: %s(%ld)\n",
513                         f, f->file, f->func, f->line);
514 #endif
515         size=ROUNDUP(size);
516         orig_size=f->size;
517         if (f->size > size){
518                 /* shrink */
519 #ifdef DBG_F_MALLOC
520                 MDBG("fm_realloc: shrinking from %lu to %lu\n", f->size, size);
521                 fm_split_frag(qm, f, size, file, "frag. from fm_realloc", line);
522 #else
523                 fm_split_frag(qm, f, size);
524 #endif
525 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
526                 /* fm_split frag already adds FRAG_OVERHEAD for the newly created
527                    free frag, so here we only need orig_size-f->size for real used */
528                 qm->real_used-=(orig_size-f->size);
529                 qm->used-=(orig_size-f->size);
530 #ifdef MALLOC_STATS
531                 sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
532                 sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
533 #endif
534 #endif
535         }else if (f->size<size){
536                 /* grow */
537 #ifdef DBG_F_MALLOC
538                 MDBG("fm_realloc: growing from %lu to %lu\n", f->size, size);
539 #endif
540                 diff=size-f->size;
541                 n=FRAG_NEXT(f);
542                 if (((char*)n < (char*)qm->last_frag) && 
543                                 (n->u.nxt_free)&&((n->size+FRAG_OVERHEAD)>=diff)){
544                         /* join  */
545                         /* detach n from the free list */
546                         hash=GET_HASH(n->size);
547                         pf=&(qm->free_hash[hash].first);
548                         /* find it */
549                         for(;(*pf)&&(*pf!=n); pf=&((*pf)->u.nxt_free)); /*FIXME slow */
550                         if (*pf==0){
551                                 /* not found, bad! */
552                                 LOG(L_CRIT, "BUG: fm_realloc: could not find %p in free "
553                                                 "list (hash=%ld)\n", n, GET_HASH(n->size));
554                                 abort();
555                         }
556                         /* detach */
557                         *pf=n->u.nxt_free;
558                         qm->free_hash[hash].no--;
559 #ifdef F_MALLOC_HASH_BITMAP
560                         if (qm->free_hash[hash].no==0)
561                                 fm_bmp_reset(qm, hash);
562 #endif /* F_MALLOC_HASH_BITMAP */
563                         /* join */
564                         f->size+=n->size+FRAG_OVERHEAD;
565                 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
566                         qm->real_used-=FRAG_OVERHEAD;
567 #ifdef MALLOC_STATS
568                         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
569 #endif
570                 #endif
571                         /* split it if necessary */
572                         if (f->size > size){
573                 #ifdef DBG_F_MALLOC
574                                 fm_split_frag(qm, f, size, file, "fragm. from fm_realloc",
575                                                 line);
576                 #else
577                                 fm_split_frag(qm, f, size);
578                 #endif
579                         }
580                 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
581                         qm->real_used+=(f->size-orig_size);
582                         qm->used+=(f->size-orig_size);
583 #ifdef MALLOC_STATS
584                         sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
585                         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
586 #endif
587                 #endif
588                 }else{
589                         /* could not join => realloc */
590         #ifdef DBG_F_MALLOC
591                         ptr=fm_malloc(qm, size, file, func, line);
592         #else
593                         ptr=fm_malloc(qm, size);
594         #endif
595                         if (ptr){
596                                 /* copy, need by libssl */
597                                 memcpy(ptr, p, orig_size);
598         #ifdef DBG_F_MALLOC
599                                 fm_free(qm, p, file, func, line);
600         #else
601                                 fm_free(qm, p);
602         #endif
603                         }
604                         p=ptr;
605                 }
606         }else{
607                 /* do nothing */
608 #ifdef DBG_F_MALLOC
609                 MDBG("fm_realloc: doing nothing, same size: %lu - %lu\n", 
610                                 f->size, size);
611 #endif
612         }
613 #ifdef DBG_F_MALLOC
614         MDBG("fm_realloc: returning %p\n", p);
615 #endif
616         return p;
617 }
618
619
620
621 void fm_status(struct fm_block* qm)
622 {
623         struct fm_frag* f;
624         int i,j;
625         int h;
626         int unused;
627         unsigned long size;
628         int memlog;
629
630         memlog=cfg_get(core, core_cfg, memlog);
631         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ", "fm_status (%p):\n", qm);
632         if (!qm) return;
633
634         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ", " heap size= %ld\n",
635                         qm->size);
636 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
637         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
638                         " used= %lu, used+overhead=%lu, free=%lu\n",
639                         qm->used, qm->real_used, qm->size-qm->real_used);
640         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
641                         " max used (+overhead)= %lu\n", qm->max_real_used);
642 #endif
643         /*
644         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ", "dumping all fragments:\n");
645         for (f=qm->first_frag, i=0;((char*)f<(char*)qm->last_frag) && (i<10);
646                         f=FRAG_NEXT(f), i++){
647                 LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
648                                 "    %3d. %c  address=%x  size=%d\n", i,
649                                 (f->u.reserved)?'a':'N',
650                                 (char*)f+sizeof(struct fm_frag), f->size);
651 #ifdef DBG_F_MALLOC
652                 LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
653                                 "            %s from %s: %s(%d)\n",
654                                 (f->u.is_free)?"freed":"alloc'd", f->file, f->func, f->line);
655 #endif
656         }
657 */
658         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ", "dumping free list:\n");
659         for(h=0,i=0,size=0;h<F_HASH_SIZE;h++){
660                 unused=0;
661                 for (f=qm->free_hash[h].first,j=0; f;
662                                 size+=f->size,f=f->u.nxt_free,i++,j++){
663                         if (!FRAG_WAS_USED(f)){
664                                 unused++;
665 #ifdef DBG_F_MALLOC
666                                 LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
667                                                         "unused fragm.: hash = %3d, fragment %p,"
668                                                         " address %p size %lu, created from %s: %s(%ld)\n",
669                                                     h, f, (char*)f+sizeof(struct fm_frag), f->size,
670                                                         f->file, f->func, f->line);
671 #endif
672                         };
673                 }
674                 if (j) LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
675                                                         "hash = %3d fragments no.: %5d, unused: %5d\n\t\t"
676                                                         " bucket size: %9lu - %9lu (first %9lu)\n",
677                                                         h, j, unused, UN_HASH(h),
678                                                 ((h<=F_MALLOC_OPTIMIZE/ROUNDTO)?1:2)* UN_HASH(h),
679                                                         qm->free_hash[h].first->size
680                                 );
681                 if (j!=qm->free_hash[h].no){
682                         LOG(L_CRIT, "BUG: fm_status: different free frag. count: %d!=%ld"
683                                         " for hash %3d\n", j, qm->free_hash[h].no, h);
684                 }
685                 /*
686                 {
687                         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
688                                         "   %5d.[%3d:%3d] %c  address=%x  size=%d(%x)\n",
689                                         i, h, j,
690                                         (f->u.reserved)?'a':'N',
691                                         (char*)f+sizeof(struct fm_frag), f->size, f->size);
692 #ifdef DBG_F_MALLOC
693                         DBG("            %s from %s: %s(%d)\n", 
694                                 (f->u.reserved)?"freed":"alloc'd", f->file, f->func, f->line);
695 #endif
696                 }
697         */
698         }
699         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
700                         "TOTAL: %6d free fragments = %6lu free bytes\n", i, size);
701         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
702                         "-----------------------------\n");
703 }
704
705
706
707 /* fills a malloc info structure with info about the block
708  * if a parameter is not supported, it will be filled with 0 */
709 void fm_info(struct fm_block* qm, struct mem_info* info)
710 {
711         int r;
712         long total_frags;
713 #if !defined(DBG_F_MALLOC) && !defined(MALLOC_STATS)
714         struct fm_frag* f;
715 #endif
716         
717         memset(info,0, sizeof(*info));
718         total_frags=0;
719         info->total_size=qm->size;
720         info->min_frag=MIN_FRAG_SIZE;
721 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
722         info->free=qm->size-qm->real_used;
723         info->used=qm->used;
724         info->real_used=qm->real_used;
725         info->max_used=qm->max_real_used;
726         for(r=0;r<F_HASH_SIZE; r++){
727                 total_frags+=qm->free_hash[r].no;
728         }
729 #else
730         /* we'll have to compute it all */
731         for (r=0; r<=F_MALLOC_OPTIMIZE/ROUNDTO; r++){
732                 info->free+=qm->free_hash[r].no*UN_HASH(r);
733                 total_frags+=qm->free_hash[r].no;
734         }
735         for(;r<F_HASH_SIZE; r++){
736                 total_frags+=qm->free_hash[r].no;
737                 for(f=qm->free_hash[r].first;f;f=f->u.nxt_free){
738                         info->free+=f->size;
739                 }
740         }
741         info->real_used=info->total_size-info->free;
742         info->used=0; /* we don't really now */
743         info->used=info->real_used-total_frags*FRAG_OVERHEAD-INIT_OVERHEAD-
744                                         FRAG_OVERHEAD;
745         info->max_used=0; /* we don't really now */
746 #endif
747         info->total_frags=total_frags;
748 }
749
750
751
752 /* returns how much free memory is available
753  * on error (not compiled with bookkeeping code) returns (unsigned long)(-1) */
754 unsigned long fm_available(struct fm_block* qm)
755 {
756
757 #if defined(DBG_F_MALLOC) || defined(MALLOC_STATS)
758         return qm->size-qm->real_used;
759 #else
760         /* we don't know how much free memory we have and it's to expensive
761          * to compute it */
762         return ((unsigned long)-1);
763 #endif
764 }
765
766
767 #ifdef DBG_F_MALLOC
768
769 typedef struct _mem_counter{
770         const char *file;
771         const char *func;
772         unsigned long line;
773         
774         unsigned long size;
775         int count;
776         
777         struct _mem_counter *next;
778 } mem_counter;
779
780 static mem_counter* get_mem_counter(mem_counter **root,struct fm_frag* f)
781 {
782         mem_counter *x;
783         
784         if (!*root) goto make_new;
785         for(x=*root;x;x=x->next)
786                 if (x->file == f->file && x->func == f->func && x->line == f->line)
787                         return x;
788 make_new:       
789         x = malloc(sizeof(mem_counter));
790         x->file = f->file;
791         x->func = f->func;
792         x->line = f->line;
793         x->count = 0;
794         x->size = 0;
795         x->next = *root;
796         *root = x;
797         return x;
798 }
799
800
801
802 void fm_sums(struct fm_block* qm)
803 {
804         struct fm_frag* f;
805         struct fm_frag* free_frag;
806         int i, hash;
807         int memlog;
808         mem_counter *root,*x;
809         
810         root=0;
811         if (!qm) return;
812
813         memlog=cfg_get(core, core_cfg, memlog);
814         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
815                         "summarizing all alloc'ed. fragments:\n");
816         
817         for (f=qm->first_frag, i=0; (char*)f<(char*)qm->last_frag;
818                         f=FRAG_NEXT(f), i++){
819                 if (f->u.nxt_free==0){
820                         /* it might be in-use or the last free fragm. in a free list 
821                            => search the free frags of the same size for a possible
822                            match --andrei*/
823                         hash=GET_HASH(f->size);
824                         for(free_frag=qm->free_hash[hash].first;
825                                         free_frag && (free_frag!=f);
826                                         free_frag=free_frag->u.nxt_free);
827                         if (free_frag==0){ /* not found among the free frag */
828                                 x = get_mem_counter(&root,f);
829                                 x->count++;
830                                 x->size+=f->size;
831                         }
832                 }
833         }
834         x = root;
835         while(x){
836                 LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
837                                 " count=%6d size=%10lu bytes from %s: %s(%ld)\n",
838                         x->count,x->size,
839                         x->file, x->func, x->line
840                         );
841                 root = x->next;
842                 free(x);
843                 x = root;
844         }
845         LOG_(DEFAULT_FACILITY, memlog, "fm_status: ",
846                         "-----------------------------\n");
847 }
848 #endif /* DBG_F_MALLOC */
849
850
851
852 #endif