mem: initial doxygen documentation for MM, small whitespace changes
[sip-router] / mem / q_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-04-14  more debugging added in DBG_QM_MALLOC mode (andrei)
24  *  2003-06-29  added qm_realloc (andrei)
25  *  2004-07-19  fragments book keeping code and support for 64 bits
26  *               memory blocks (64 bits machine & size>=2^32) (andrei)
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 qm_info() (andrei)
30  *  2005-12-12  fixed realloc shrink real_used & used accounting;
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  *  2009-09-28  added fm_sums() (patch from Dragos Vingarzan)
36  */
37
38 /**
39  * \file
40  * \brief Simple & fast malloc library
41  * \ingroup mem
42  */
43
44
45 #if !defined(q_malloc) && !(defined F_MALLOC)
46 #define q_malloc
47
48 #include <stdlib.h>
49 #include <string.h>
50
51 #include "q_malloc.h"
52 #include "../dprint.h"
53 #include "../globals.h"
54 #include "memdbg.h"
55 #include "../cfg/cfg.h" /* memlog */
56 #ifdef MALLOC_STATS
57 #include "../events.h"
58 #endif
59
60
61 /*useful macros*/
62 #define FRAG_END(f)  \
63         ((struct qm_frag_end*)((char*)(f)+sizeof(struct qm_frag)+ \
64            (f)->size))
65
66 #define FRAG_NEXT(f) \
67         ((struct qm_frag*)((char*)(f)+sizeof(struct qm_frag)+(f)->size+ \
68            sizeof(struct qm_frag_end)))
69                         
70 #define FRAG_PREV(f) \
71         ( (struct qm_frag*) ( ((char*)(f)-sizeof(struct qm_frag_end))- \
72         ((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))->size- \
73            sizeof(struct qm_frag) ) )
74
75 #define PREV_FRAG_END(f) \
76         ((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))
77
78
79 #define FRAG_OVERHEAD   (sizeof(struct qm_frag)+sizeof(struct qm_frag_end))
80
81
82 #define ROUNDTO_MASK    (~((unsigned long)ROUNDTO-1))
83 #define ROUNDUP(s)              (((s)+(ROUNDTO-1))&ROUNDTO_MASK)
84 #define ROUNDDOWN(s)    ((s)&ROUNDTO_MASK)
85
86 /*
87 #define ROUNDUP(s)              (((s)%ROUNDTO)?((s)+ROUNDTO)/ROUNDTO*ROUNDTO:(s))
88 #define ROUNDDOWN(s)    (((s)%ROUNDTO)?((s)-ROUNDTO)/ROUNDTO*ROUNDTO:(s))
89 */
90
91
92
93         /* finds the hash value for s, s=ROUNDTO multiple*/
94 #define GET_HASH(s)   ( ((unsigned long)(s)<=QM_MALLOC_OPTIMIZE)?\
95                                                         (unsigned long)(s)/ROUNDTO: \
96                                                         QM_MALLOC_OPTIMIZE/ROUNDTO+big_hash_idx((s))- \
97                                                                 QM_MALLOC_OPTIMIZE_FACTOR+1 )
98
99 #define UN_HASH(h)      ( ((unsigned long)(h)<=(QM_MALLOC_OPTIMIZE/ROUNDTO))?\
100                                                         (unsigned long)(h)*ROUNDTO: \
101                                                         1UL<<((h)-QM_MALLOC_OPTIMIZE/ROUNDTO+\
102                                                                 QM_MALLOC_OPTIMIZE_FACTOR-1)\
103                                         )
104
105
106 /* mark/test used/unused frags */
107 #define FRAG_MARK_USED(f)
108 #define FRAG_CLEAR_USED(f)
109 #define FRAG_WAS_USED(f)   (1)
110
111 /* other frag related defines:
112  * MEM_COALESCE_FRAGS 
113  * MEM_FRAG_AVOIDANCE
114  */
115
116 #define MEM_FRAG_AVOIDANCE
117
118
119 /* computes hash number for big buckets*/
120 inline static unsigned long big_hash_idx(unsigned long s)
121 {
122         int idx;
123         /* s is rounded => s = k*2^n (ROUNDTO=2^n) 
124          * index= i such that 2^i > s >= 2^(i-1)
125          *
126          * => index = number of the first non null bit in s*/
127         idx=sizeof(long)*8-1;
128         for (; !(s&(1UL<<(sizeof(long)*8-1))) ; s<<=1, idx--);
129         return idx;
130 }
131
132
133 #ifdef DBG_QM_MALLOC
134 #define ST_CHECK_PATTERN   0xf0f0f0f0
135 #define END_CHECK_PATTERN1 0xc0c0c0c0
136 #define END_CHECK_PATTERN2 0xabcdefed
137
138
139 static  void qm_debug_frag(struct qm_block* qm, struct qm_frag* f)
140 {
141         if (f->check!=ST_CHECK_PATTERN){
142                 LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p) "
143                                 "beginning overwritten(%lx)!\n",
144                                 f, (char*)f+sizeof(struct qm_frag),
145                                 f->check);
146                 qm_status(qm);
147                 abort();
148         };
149         if ((FRAG_END(f)->check1!=END_CHECK_PATTERN1)||
150                 (FRAG_END(f)->check2!=END_CHECK_PATTERN2)){
151                 LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p)"
152                                         " end overwritten(%lx, %lx)!\n",
153                                 f, (char*)f+sizeof(struct qm_frag), 
154                                 FRAG_END(f)->check1, FRAG_END(f)->check2);
155                 qm_status(qm);
156                 abort();
157         }
158         if ((f>qm->first_frag)&&
159                         ((PREV_FRAG_END(f)->check1!=END_CHECK_PATTERN1) ||
160                                 (PREV_FRAG_END(f)->check2!=END_CHECK_PATTERN2) ) ){
161                 LOG(L_CRIT, "BUG: qm_*: prev. fragm. tail overwritten(%lx, %lx)[%p:%p]!"
162                                         "\n",
163                                 PREV_FRAG_END(f)->check1, PREV_FRAG_END(f)->check2, f,
164                                 (char*)f+sizeof(struct qm_frag));
165                 qm_status(qm);
166                 abort();
167         }
168 }
169 #endif
170
171
172
173 static inline void qm_insert_free(struct qm_block* qm, struct qm_frag* frag)
174 {
175         struct qm_frag* f;
176         struct qm_frag* prev;
177         int hash;
178         
179         hash=GET_HASH(frag->size);
180         for(f=qm->free_hash[hash].head.u.nxt_free; f!=&(qm->free_hash[hash].head);
181                         f=f->u.nxt_free){
182                 if (frag->size <= f->size) break;
183         }
184         /*insert it here*/
185         prev=FRAG_END(f)->prev_free;
186         prev->u.nxt_free=frag;
187         FRAG_END(frag)->prev_free=prev;
188         frag->u.nxt_free=f;
189         FRAG_END(f)->prev_free=frag;
190         qm->free_hash[hash].no++;
191 }
192
193
194
195 /* init malloc and return a qm_block*/
196 struct qm_block* qm_malloc_init(char* address, unsigned long size)
197 {
198         char* start;
199         char* end;
200         struct qm_block* qm;
201         unsigned long init_overhead;
202         int h;
203         
204         /* make address and size multiple of 8*/
205         start=(char*)ROUNDUP((unsigned long) address);
206         DBG("qm_malloc_init: QM_OPTIMIZE=%lu, /ROUNDTO=%lu\n",
207                         QM_MALLOC_OPTIMIZE, QM_MALLOC_OPTIMIZE/ROUNDTO);
208         DBG("qm_malloc_init: QM_HASH_SIZE=%lu, qm_block size=%lu\n",
209                         QM_HASH_SIZE, (long)sizeof(struct qm_block));
210         DBG("qm_malloc_init(%p, %lu), start=%p\n", address, size, start);
211         if (size<start-address) return 0;
212         size-=(start-address);
213         if (size <(MIN_FRAG_SIZE+FRAG_OVERHEAD)) return 0;
214         size=ROUNDDOWN(size);
215         
216         init_overhead=ROUNDUP(sizeof(struct qm_block))+sizeof(struct qm_frag)+
217                 sizeof(struct qm_frag_end);
218         DBG("qm_malloc_init: size= %lu, init_overhead=%lu\n", size, init_overhead);
219         
220         if (size < init_overhead)
221         {
222                 /* not enough mem to create our control structures !!!*/
223                 return 0;
224         }
225         end=start+size;
226         qm=(struct qm_block*)start;
227         memset(qm, 0, sizeof(struct qm_block));
228         qm->size=size;
229         qm->real_used=init_overhead;
230         qm->max_real_used=qm->real_used;
231         size-=init_overhead;
232         
233         qm->first_frag=(struct qm_frag*)(start+ROUNDUP(sizeof(struct qm_block)));
234         qm->last_frag_end=(struct qm_frag_end*)(end-sizeof(struct qm_frag_end));
235         /* init initial fragment*/
236         qm->first_frag->size=size;
237         qm->last_frag_end->size=size;
238         
239 #ifdef DBG_QM_MALLOC
240         qm->first_frag->check=ST_CHECK_PATTERN;
241         qm->last_frag_end->check1=END_CHECK_PATTERN1;
242         qm->last_frag_end->check2=END_CHECK_PATTERN2;
243 #endif
244         /* init free_hash* */
245         for (h=0; h<QM_HASH_SIZE;h++){
246                 qm->free_hash[h].head.u.nxt_free=&(qm->free_hash[h].head);
247                 qm->free_hash[h].tail.prev_free=&(qm->free_hash[h].head);
248                 qm->free_hash[h].head.size=0;
249                 qm->free_hash[h].tail.size=0;
250         }
251         
252         /* link initial fragment into the free list*/
253         
254         qm_insert_free(qm, qm->first_frag);
255         
256         /*qm->first_frag->u.nxt_free=&(qm->free_lst);
257           qm->last_frag_end->prev_free=&(qm->free_lst);
258         */
259         
260         
261         return qm;
262 }
263
264
265
266 static inline void qm_detach_free(struct qm_block* qm, struct qm_frag* frag)
267 {
268         struct qm_frag *prev;
269         struct qm_frag *next;
270         
271         prev=FRAG_END(frag)->prev_free;
272         next=frag->u.nxt_free;
273         prev->u.nxt_free=next;
274         FRAG_END(next)->prev_free=prev;
275         
276 }
277
278
279
280 #ifdef DBG_QM_MALLOC
281 static inline struct qm_frag* qm_find_free(struct qm_block* qm, 
282                                                                                         unsigned long size,
283                                                                                         int *h,
284                                                                                         unsigned int *count)
285 #else
286 static inline struct qm_frag* qm_find_free(struct qm_block* qm, 
287                                                                                         unsigned long size,
288                                                                                         int* h)
289 #endif
290 {
291         int hash;
292         struct qm_frag* f;
293
294         for (hash=GET_HASH(size); hash<QM_HASH_SIZE; hash++){
295                 for (f=qm->free_hash[hash].head.u.nxt_free; 
296                                         f!=&(qm->free_hash[hash].head); f=f->u.nxt_free){
297 #ifdef DBG_QM_MALLOC
298                         *count+=1; /* *count++ generates a warning with gcc 2.9* -Wall */
299 #endif
300                         if (f->size>=size){ *h=hash; return f; }
301                 }
302         /*try in a bigger bucket*/
303         }
304         /* not found */
305         return 0;
306 }
307
308
309 /* returns 0 on success, -1 on error;
310  * new_size < size & rounded-up already!*/
311 static inline
312 #ifdef DBG_QM_MALLOC
313 int split_frag(struct qm_block* qm, struct qm_frag* f, unsigned long new_size,
314                                 const char* file, const char* func, unsigned int line)
315 #else
316 int split_frag(struct qm_block* qm, struct qm_frag* f, unsigned long new_size)
317 #endif
318 {
319         unsigned long rest;
320         struct qm_frag* n;
321         struct qm_frag_end* end;
322         
323         rest=f->size-new_size;
324 #ifdef MEM_FRAG_AVOIDANCE
325         if ((rest> (FRAG_OVERHEAD+QM_MALLOC_OPTIMIZE))||
326                 (rest>=(FRAG_OVERHEAD+new_size))){/* the residue fragm. is big enough*/
327 #else
328         if (rest>(FRAG_OVERHEAD+MIN_FRAG_SIZE)){
329 #endif
330                 f->size=new_size;
331                 /*split the fragment*/
332                 end=FRAG_END(f);
333                 end->size=new_size;
334                 n=(struct qm_frag*)((char*)end+sizeof(struct qm_frag_end));
335                 n->size=rest-FRAG_OVERHEAD;
336                 FRAG_END(n)->size=n->size;
337                 FRAG_CLEAR_USED(n); /* never used */
338                 qm->real_used+=FRAG_OVERHEAD;
339 #ifdef DBG_QM_MALLOC
340                 end->check1=END_CHECK_PATTERN1;
341                 end->check2=END_CHECK_PATTERN2;
342                 /* frag created by malloc, mark it*/
343                 n->file=file;
344                 n->func=func;
345                 n->line=line;
346                 n->check=ST_CHECK_PATTERN;
347 #endif
348                 /* reinsert n in free list*/
349                 qm_insert_free(qm, n);
350                 return 0;
351         }else{
352                         /* we cannot split this fragment any more */
353                 return -1;
354         }
355 }
356
357
358
359 #ifdef DBG_QM_MALLOC
360 void* qm_malloc(struct qm_block* qm, unsigned long size,
361                                         const char* file, const char* func, unsigned int line)
362 #else
363 void* qm_malloc(struct qm_block* qm, unsigned long size)
364 #endif
365 {
366         struct qm_frag* f;
367         int hash;
368         
369 #ifdef DBG_QM_MALLOC
370         unsigned int list_cntr;
371
372         list_cntr = 0;
373         MDBG("qm_malloc(%p, %lu) called from %s: %s(%d)\n", qm, size, file, func,
374                         line);
375 #endif
376         /*size must be a multiple of 8*/
377         size=ROUNDUP(size);
378         if (size>(qm->size-qm->real_used)) return 0;
379
380         /*search for a suitable free frag*/
381 #ifdef DBG_QM_MALLOC
382         if ((f=qm_find_free(qm, size, &hash, &list_cntr))!=0){
383 #else
384         if ((f=qm_find_free(qm, size, &hash))!=0){
385 #endif
386                 /* we found it!*/
387                 /*detach it from the free list*/
388 #ifdef DBG_QM_MALLOC
389                         qm_debug_frag(qm, f);
390 #endif
391                 qm_detach_free(qm, f);
392                 /*mark it as "busy"*/
393                 f->u.is_free=0;
394                 qm->free_hash[hash].no--;
395                 /* we ignore split return */
396 #ifdef DBG_QM_MALLOC
397                 split_frag(qm, f, size, file, "fragm. from qm_malloc", line);
398 #else
399                 split_frag(qm, f, size);
400 #endif
401                 qm->real_used+=f->size;
402                 qm->used+=f->size;
403                 if (qm->max_real_used<qm->real_used)
404                         qm->max_real_used=qm->real_used;
405 #ifdef MALLOC_STATS
406                 sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
407                 sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
408 #endif
409 #ifdef DBG_QM_MALLOC
410                 f->file=file;
411                 f->func=func;
412                 f->line=line;
413                 f->check=ST_CHECK_PATTERN;
414                 /*  FRAG_END(f)->check1=END_CHECK_PATTERN1;
415                         FRAG_END(f)->check2=END_CHECK_PATTERN2;*/
416                 MDBG("qm_malloc(%p, %lu) returns address %p frag. %p (size=%lu) on %d"
417                                 " -th hit\n",
418                          qm, size, (char*)f+sizeof(struct qm_frag), f, f->size, list_cntr );
419 #endif
420                 return (char*)f+sizeof(struct qm_frag);
421         }
422         return 0;
423 }
424
425
426
427 #ifdef DBG_QM_MALLOC
428 void qm_free(struct qm_block* qm, void* p, const char* file, const char* func, 
429                                 unsigned int line)
430 #else
431 void qm_free(struct qm_block* qm, void* p)
432 #endif
433 {
434         struct qm_frag* f;
435         unsigned long size;
436 #ifdef QM_JOIN_FREE
437         struct qm_frag* next;
438         struct qm_frag* prev;
439 #endif /* QM_JOIN_FREE*/
440
441 #ifdef DBG_QM_MALLOC
442         MDBG("qm_free(%p, %p), called from %s: %s(%d)\n", qm, p, file, func, line);
443         if (p>(void*)qm->last_frag_end || p<(void*)qm->first_frag){
444                 LOG(L_CRIT, "BUG: qm_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:qm_free: free(0) called\n");
451                 return;
452         }
453 #ifdef QM_JOIN_FREE
454         next=prev=0;
455 #endif /* QM_JOIN_FREE*/
456         f=(struct qm_frag*) ((char*)p-sizeof(struct qm_frag));
457 #ifdef DBG_QM_MALLOC
458         qm_debug_frag(qm, f);
459         if (f->u.is_free){
460                 LOG(L_CRIT, "BUG: qm_free: freeing already freed pointer,"
461                                 " first free: %s: %s(%ld) - aborting\n",
462                                 f->file, f->func, f->line);
463                 abort();
464         }
465         MDBG("qm_free: freeing frag. %p alloc'ed from %s: %s(%ld)\n",
466                         f, f->file, f->func, f->line);
467 #endif
468         size=f->size;
469         qm->used-=size;
470         qm->real_used-=size;
471 #ifdef MALLOC_STATS
472         sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
473         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
474 #endif
475
476 #ifdef QM_JOIN_FREE
477         /* mark this fragment as used (might fall into the middle of joined frags)
478           to give us an extra change of detecting a double free call (if the joined
479           fragment has not yet been reused) */
480         f->u.nxt_free=(void*)0x1L; /* bogus value, just to mark it as free */
481         /* join packets if possible*/
482         next=FRAG_NEXT(f);
483         if (((char*)next < (char*)qm->last_frag_end) &&( next->u.is_free)){
484                 /* join */
485 #ifdef DBG_QM_MALLOC
486                 qm_debug_frag(qm, next);
487 #endif
488                 qm_detach_free(qm, next);
489                 size+=next->size+FRAG_OVERHEAD;
490                 qm->real_used-=FRAG_OVERHEAD;
491                 qm->free_hash[GET_HASH(next->size)].no--; /* FIXME slow */
492         }
493         
494         if (f > qm->first_frag){
495                 prev=FRAG_PREV(f);
496                 /*      (struct qm_frag*)((char*)f - (struct qm_frag_end*)((char*)f-
497                                                                 sizeof(struct qm_frag_end))->size);*/
498 #ifdef DBG_QM_MALLOC
499                 qm_debug_frag(qm, prev);
500 #endif
501                 if (prev->u.is_free){
502                         /*join*/
503                         qm_detach_free(qm, prev);
504                         size+=prev->size+FRAG_OVERHEAD;
505                         qm->real_used-=FRAG_OVERHEAD;
506                         qm->free_hash[GET_HASH(prev->size)].no--; /* FIXME slow */
507                         f=prev;
508                 }
509         }
510         f->size=size;
511         FRAG_END(f)->size=f->size;
512 #endif /* QM_JOIN_FREE*/
513 #ifdef DBG_QM_MALLOC
514         f->file=file;
515         f->func=func;
516         f->line=line;
517 #endif
518         qm_insert_free(qm, f);
519 }
520
521
522
523 #ifdef DBG_QM_MALLOC
524 void* qm_realloc(struct qm_block* qm, void* p, unsigned long size,
525                                         const char* file, const char* func, unsigned int line)
526 #else
527 void* qm_realloc(struct qm_block* qm, void* p, unsigned long size)
528 #endif
529 {
530         struct qm_frag* f;
531         unsigned long diff;
532         unsigned long orig_size;
533         struct qm_frag* n;
534         void* ptr;
535         
536         
537 #ifdef DBG_QM_MALLOC
538         MDBG("qm_realloc(%p, %p, %lu) called from %s: %s(%d)\n", qm, p, size,
539                         file, func, line);
540         if ((p)&&(p>(void*)qm->last_frag_end || p<(void*)qm->first_frag)){
541                 LOG(L_CRIT, "BUG: qm_free: bad pointer %p (out of memory block!) - "
542                                 "aborting\n", p);
543                 abort();
544         }
545 #endif
546         
547         if (size==0) {
548                 if (p)
549 #ifdef DBG_QM_MALLOC
550                         qm_free(qm, p, file, func, line);
551 #else
552                         qm_free(qm, p);
553 #endif
554                 return 0;
555         }
556         if (p==0)
557 #ifdef DBG_QM_MALLOC
558                 return qm_malloc(qm, size, file, func, line);
559 #else
560                 return qm_malloc(qm, size);
561 #endif
562         f=(struct qm_frag*) ((char*)p-sizeof(struct qm_frag));
563 #ifdef DBG_QM_MALLOC
564         qm_debug_frag(qm, f);
565         MDBG("qm_realloc: realloc'ing frag %p alloc'ed from %s: %s(%ld)\n",
566                         f, f->file, f->func, f->line);
567         if (f->u.is_free){
568                 LOG(L_CRIT, "BUG:qm_realloc: trying to realloc an already freed "
569                                 "pointer %p , fragment %p -- aborting\n", p, f);
570                 abort();
571         }
572 #endif
573         /* find first acceptable size */
574         size=ROUNDUP(size);
575         if (f->size > size){
576                 orig_size=f->size;
577                 /* shrink */
578 #ifdef DBG_QM_MALLOC
579                 MDBG("qm_realloc: shrinking from %lu to %lu\n", f->size, size);
580                 if(split_frag(qm, f, size, file, "fragm. from qm_realloc", line)!=0){
581                 MDBG("qm_realloc : shrinked successful\n");
582 #else
583                 if(split_frag(qm, f, size)!=0){
584 #endif
585                         /* update used sizes: freed the splited frag */
586                         /* split frag already adds FRAG_OVERHEAD for the newly created
587                            free frag, so here we only need orig_size-f->size for real used
588                          */
589                         qm->real_used-=(orig_size-f->size);
590                         qm->used-=(orig_size-f->size);
591 #ifdef MALLOC_STATS
592                         sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
593                         sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
594 #endif
595                 }
596                 
597         }else if (f->size < size){
598                 /* grow */
599 #ifdef DBG_QM_MALLOC
600                 MDBG("qm_realloc: growing from %lu to %lu\n", f->size, size);
601 #endif
602                         orig_size=f->size;
603                         diff=size-f->size;
604                         n=FRAG_NEXT(f);
605                         if (((char*)n < (char*)qm->last_frag_end) && 
606                                         (n->u.is_free)&&((n->size+FRAG_OVERHEAD)>=diff)){
607                                 /* join  */
608                                 qm_detach_free(qm, n);
609                                 qm->free_hash[GET_HASH(n->size)].no--; /*FIXME: slow*/
610                                 f->size+=n->size+FRAG_OVERHEAD;
611                                 qm->real_used-=FRAG_OVERHEAD;
612                                 FRAG_END(f)->size=f->size;
613                                 /* end checks should be ok */
614                                 /* split it if necessary */
615                                 if (f->size > size ){
616         #ifdef DBG_QM_MALLOC
617                                         split_frag(qm, f, size, file, "fragm. from qm_realloc",
618                                                                                 line);
619         #else
620                                         split_frag(qm, f, size);
621         #endif
622                                 }
623                                 qm->real_used+=(f->size-orig_size);
624                                 qm->used+=(f->size-orig_size);
625 #ifdef MALLOC_STATS
626                                 sr_event_exec(SREV_PKG_SET_USED, (void*)qm->used);
627                                 sr_event_exec(SREV_PKG_SET_REAL_USED, (void*)qm->real_used);
628 #endif
629                         }else{
630                                 /* could not join => realloc */
631         #ifdef DBG_QM_MALLOC
632                                 ptr=qm_malloc(qm, size, file, func, line);
633         #else
634                                 ptr=qm_malloc(qm, size);
635         #endif
636                                 if (ptr){
637                                         /* copy, need by libssl */
638                                         memcpy(ptr, p, orig_size);
639         #ifdef DBG_QM_MALLOC
640                                         qm_free(qm, p, file, func, line);
641         #else
642                                         qm_free(qm, p);
643         #endif
644                                 }
645                                 p=ptr;
646                         }
647         }else{
648                 /* do nothing */
649 #ifdef DBG_QM_MALLOC
650                 MDBG("qm_realloc: doing nothing, same size: %lu - %lu\n",
651                                 f->size, size);
652 #endif
653         }
654 #ifdef DBG_QM_MALLOC
655         MDBG("qm_realloc: returning %p\n", p);
656 #endif
657         return p;
658 }
659
660
661 void qm_check(struct qm_block* qm)
662 {
663         struct qm_frag* f;
664         long fcount = 0;
665         int memlog;
666         
667         memlog=cfg_get(core, core_cfg, memlog);
668         LOG(memlog, "DEBUG: qm_check()\n");
669         f = qm->first_frag;
670         while ((char*)f < (char*)qm->last_frag_end) {
671                 fcount++;
672                 /* check struct qm_frag */
673 #ifdef DBG_QM_MALLOC
674                 if (f->check!=ST_CHECK_PATTERN){
675                         LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p) "
676                                         "beginning overwritten(%lx)!\n",
677                                         f, (char*)f + sizeof(struct qm_frag),
678                                         f->check);
679                         qm_status(qm);
680                         abort();
681                 };
682 #endif
683                 if (f + sizeof(struct qm_frag) + f->size + sizeof(struct qm_frag_end) > qm->first_frag + qm->size) {
684                         LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p) "
685                                 "bad size: %lu (frag end: %p > end of block: %p)\n",
686                                 f, (char*)f + sizeof(struct qm_frag) + sizeof(struct qm_frag_end), f->size,
687                                 f + sizeof(struct qm_frag) + f->size, qm->first_frag + qm->size);
688                         qm_status(qm);
689                         abort();
690                 }
691                 /* check struct qm_frag_end */
692                 if (FRAG_END(f)->size != f->size) {
693                         LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p) "
694                                 "size in qm_frag and qm_frag_end does not match: frag->size=%lu, frag_end->size=%lu)\n",
695                                 f, (char*)f + sizeof(struct qm_frag),
696                                 f->size, FRAG_END(f)->size);
697                         qm_status(qm);
698                         abort();
699                 }
700 #ifdef DBG_QM_MALLOC
701                 if ((FRAG_END(f)->check1 != END_CHECK_PATTERN1) ||
702                         (FRAG_END(f)->check2 != END_CHECK_PATTERN2)) {
703                         LOG(L_CRIT, "BUG: qm_*: fragm. %p (address %p)"
704                                                 " end overwritten(%lx, %lx)!\n",
705                                         f, (char*)f + sizeof(struct qm_frag), 
706                                         FRAG_END(f)->check1, FRAG_END(f)->check2);
707                         qm_status(qm);
708                         abort();
709                 }
710 #endif
711                 f = FRAG_NEXT(f);
712         }
713
714         LOG(memlog, "DEBUG: qm_check: %lu fragments OK\n", fcount);
715 }
716
717 void qm_status(struct qm_block* qm)
718 {
719         struct qm_frag* f;
720         int i,j;
721         int h;
722         int unused;
723         int memlog;
724
725
726         memlog=cfg_get(core, core_cfg, memlog);
727         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ", "(%p):\n", qm);
728         if (!qm) return;
729
730         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ", "heap size= %lu\n",
731                         qm->size);
732         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
733                         "used= %lu, used+overhead=%lu, free=%lu\n",
734                         qm->used, qm->real_used, qm->size-qm->real_used);
735         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
736                         "max used (+overhead)= %lu\n", qm->max_real_used);
737         
738         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
739                         "dumping all alloc'ed. fragments:\n");
740         for (f=qm->first_frag, i=0;(char*)f<(char*)qm->last_frag_end;f=FRAG_NEXT(f)
741                         ,i++){
742                 if (! f->u.is_free){
743                         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
744                                         "   %3d. %c  address=%p frag=%p size=%lu used=%d\n",
745                                 i,
746                                 (f->u.is_free)?'a':'N',
747                                 (char*)f+sizeof(struct qm_frag), f, f->size, FRAG_WAS_USED(f));
748 #ifdef DBG_QM_MALLOC
749                         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
750                                         "          %s from %s: %s(%ld)\n",
751                                 (f->u.is_free)?"freed":"alloc'd", f->file, f->func, f->line);
752                         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
753                                         "         start check=%lx, end check= %lx, %lx\n",
754                                 f->check, FRAG_END(f)->check1, FRAG_END(f)->check2);
755 #endif
756                 }
757         }
758         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
759                         "dumping free list stats :\n");
760         for(h=0,i=0;h<QM_HASH_SIZE;h++){
761                 unused=0;
762                 for (f=qm->free_hash[h].head.u.nxt_free,j=0; 
763                                 f!=&(qm->free_hash[h].head); f=f->u.nxt_free, i++, j++){
764                                 if (!FRAG_WAS_USED(f)){
765                                         unused++;
766 #ifdef DBG_QM_MALLOC
767                                         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
768                                                 "unused fragm.: hash = %3d, fragment %p,"
769                                                 " address %p size %lu, created from %s: %s(%lu)\n",
770                                             h, f, (char*)f+sizeof(struct qm_frag), f->size,
771                                                 f->file, f->func, f->line);
772 #endif
773                                 }
774                 }
775
776                 if (j) LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
777                                 "hash= %3d. fragments no.: %5d, unused: %5d\n"
778                                         "\t\t bucket size: %9lu - %9ld (first %9lu)\n",
779                                         h, j, unused, UN_HASH(h),
780                                         ((h<=QM_MALLOC_OPTIMIZE/ROUNDTO)?1:2)*UN_HASH(h),
781                                         qm->free_hash[h].head.u.nxt_free->size
782                                 );
783                 if (j!=qm->free_hash[h].no){
784                         LOG(L_CRIT, "BUG: qm_status: different free frag. count: %d!=%lu"
785                                 " for hash %3d\n", j, qm->free_hash[h].no, h);
786                 }
787
788         }
789         LOG_(DEFAULT_FACILITY, memlog, "qm_status: ",
790                         "-----------------------------\n");
791 }
792
793
794 /* fills a malloc info structure with info about the block
795  * if a parameter is not supported, it will be filled with 0 */
796 void qm_info(struct qm_block* qm, struct mem_info* info)
797 {
798         int r;
799         long total_frags;
800         
801         total_frags=0;
802         memset(info,0, sizeof(*info));
803         info->total_size=qm->size;
804         info->min_frag=MIN_FRAG_SIZE;
805         info->free=qm->size-qm->real_used;
806         info->used=qm->used;
807         info->real_used=qm->real_used;
808         info->max_used=qm->max_real_used;
809         for(r=0;r<QM_HASH_SIZE; r++){
810                 total_frags+=qm->free_hash[r].no;
811         }
812         info->total_frags=total_frags;
813 }
814
815
816 /* returns how much free memory is available
817  * it never returns an error (unlike fm_available) */
818 unsigned long qm_available(struct qm_block* qm)
819 {
820         return qm->size-qm->real_used;
821 }
822
823
824
825 #ifdef DBG_QM_MALLOC
826
827 typedef struct _mem_counter{
828         const char *file;
829         const char *func;
830         unsigned long line;
831         
832         unsigned long size;
833         int count;
834         
835         struct _mem_counter *next;
836 } mem_counter;
837
838 static mem_counter* get_mem_counter(mem_counter **root, struct qm_frag* f)
839 {
840         mem_counter *x;
841         if (!*root) goto make_new;
842         for(x=*root;x;x=x->next)
843                 if (x->file == f->file && x->func == f->func && x->line == f->line)
844                         return x;
845 make_new:       
846         x = malloc(sizeof(mem_counter));
847         x->file = f->file;
848         x->func = f->func;
849         x->line = f->line;
850         x->count = 0;
851         x->size = 0;
852         x->next = *root;
853         *root = x;
854         return x;
855 }
856
857
858
859 void qm_sums(struct qm_block* qm)
860 {
861         struct qm_frag* f;
862         int i;
863         mem_counter *root, *x;
864         int memlog;
865         
866         root=0;
867         if (!qm) return;
868         
869         memlog=cfg_get(core, core_cfg, memlog);
870         LOG_(DEFAULT_FACILITY, memlog, "qm_sums: ",
871                         "summarizing all alloc'ed. fragments:\n");
872         
873         for (f=qm->first_frag, i=0;(char*)f<(char*)qm->last_frag_end;
874                         f=FRAG_NEXT(f),i++){
875                 if (! f->u.is_free){
876                         x = get_mem_counter(&root,f);
877                         x->count++;
878                         x->size+=f->size;
879                 }
880         }
881         x = root;
882         while(x){
883                 LOG_(DEFAULT_FACILITY, memlog, "qm_sums: ",
884                                 " count=%6d size=%10lu bytes from %s: %s(%ld)\n",
885                         x->count,x->size,
886                         x->file, x->func, x->line
887                         );
888                 root = x->next;
889                 free(x);
890                 x = root;
891         }
892         LOG_(DEFAULT_FACILITY, memlog, "qm_sums: ",
893                         "-----------------------------\n");
894 }
895 #endif /* DBG_QM_MALLOC */
896
897
898 #endif