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