mem/q_malloc.c
6fa79282
 /* $Id$
  *
7dd0b342
  *
  * Copyright (C) 2001-2003 Fhg Fokus
  *
  * This file is part of ser, a free SIP server.
  *
  * ser is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
  * (at your option) any later version
  *
  * For a license to use the ser software under conditions
  * other than those described here, or to purchase support for this
  * software, please contact iptel.org by e-mail at the following addresses:
  *    info@iptel.org
  *
  * ser is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License 
  * along with this program; if not, write to the Free Software 
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
6fa79282
  */
 
7dd0b342
 
b2dec9c6
 #if !defined(q_malloc) && !(defined VQ_MALLOC) && !(defined F_MALLOC)
6fa79282
 #define q_malloc
 
f48312e2
 #include <stdlib.h>
 #include <string.h>
 
6fa79282
 #include "q_malloc.h"
dda9dab1
 #include "../dprint.h"
843b2927
 #include "../globals.h"
6fa79282
 
 
dda9dab1
 /*useful macros*/
6fa79282
 #define FRAG_END(f)  \
dda9dab1
 	((struct qm_frag_end*)((char*)(f)+sizeof(struct qm_frag)+ \
 	   (f)->size))
6fa79282
 
 #define FRAG_NEXT(f) \
dda9dab1
 	((struct qm_frag*)((char*)(f)+sizeof(struct qm_frag)+(f)->size+ \
 	   sizeof(struct qm_frag_end)))
6fa79282
 			
 #define FRAG_PREV(f) \
dda9dab1
 	( (struct qm_frag*) ( ((char*)(f)-sizeof(struct qm_frag_end))- \
 	((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))->size- \
 	   sizeof(struct qm_frag) ) )
6fa79282
 
2c65bd8b
 #define PREV_FRAG_END(f) \
dda9dab1
 	((struct qm_frag_end*)((char*)(f)-sizeof(struct qm_frag_end)))
2c65bd8b
 
eca7f442
 
 #define FRAG_OVERHEAD	(sizeof(struct qm_frag)+sizeof(struct qm_frag_end))
 
 
7b5c6965
 #define ROUNDTO_MASK	(~((unsigned long)ROUNDTO-1))
 #define ROUNDUP(s)		(((s)+(ROUNDTO-1))&ROUNDTO_MASK)
 #define ROUNDDOWN(s)	((s)&ROUNDTO_MASK)
 
 /*
eca7f442
 #define ROUNDUP(s)		(((s)%ROUNDTO)?((s)+ROUNDTO)/ROUNDTO*ROUNDTO:(s))
 #define ROUNDDOWN(s)	(((s)%ROUNDTO)?((s)-ROUNDTO)/ROUNDTO*ROUNDTO:(s))
7b5c6965
 */
eca7f442
 
 
 
 	/* finds the hash value for s, s=ROUNDTO multiple*/
 #define GET_HASH(s)   ( ((s)<QM_MALLOC_OPTIMIZE)?(s)/ROUNDTO: \
 						QM_MALLOC_OPTIMIZE/ROUNDTO+big_hash_idx((s))- \
 							QM_MALLOC_OPTIMIZE_FACTOR+1 )
 
 
 /* computes hash number for big buckets*/
 inline static int big_hash_idx(int s)
 {
 	int idx;
 	/* s is rounded => s = k*2^n (ROUNDTO=2^n) 
 	 * index= i such that 2^i > s >= 2^(i-1)
 	 *
 	 * => index = number of the first non null bit in s*/
 	for (idx=31; !(s&0x80000000) ; s<<=1, idx--);
 	return idx;
 }
 
 
2c65bd8b
 #ifdef DBG_QM_MALLOC
 #define ST_CHECK_PATTERN   0xf0f0f0f0
 #define END_CHECK_PATTERN1 0xc0c0c0c0
 #define END_CHECK_PATTERN2 0xabcdefed
6fa79282
 
 
2c65bd8b
 static  void qm_debug_frag(struct qm_block* qm, struct qm_frag* f)
 {
 	if (f->check!=ST_CHECK_PATTERN){
f48312e2
 		LOG(L_CRIT, "BUG: qm_*: fragm. %p beginning overwritten(%x)!\n",
2c65bd8b
 				f, f->check);
 		qm_status(qm);
 		abort();
 	};
 	if ((FRAG_END(f)->check1!=END_CHECK_PATTERN1)||
 		(FRAG_END(f)->check2!=END_CHECK_PATTERN2)){
f48312e2
 		LOG(L_CRIT, "BUG: qm_*: fragm. %p end overwritten(%x, %x)!\n",
2c65bd8b
 				f, FRAG_END(f)->check1, FRAG_END(f)->check2);
 		qm_status(qm);
 		abort();
 	}
 	if ((f>qm->first_frag)&&
 			((PREV_FRAG_END(f)->check1!=END_CHECK_PATTERN1) ||
 				(PREV_FRAG_END(f)->check2!=END_CHECK_PATTERN2) ) ){
f48312e2
 		LOG(L_CRIT, "BUG: qm_*: prev. fragm. tail overwritten(%x, %x)[%p]!\n",
2c65bd8b
 				PREV_FRAG_END(f)->check1, PREV_FRAG_END(f)->check2, f);
 		qm_status(qm);
 		abort();
 	}
 }
 #endif
 
6fa79282
 
 
eca7f442
 static inline void qm_insert_free(struct qm_block* qm, struct qm_frag* frag)
 {
 	struct qm_frag* f;
 	struct qm_frag* prev;
 	int hash;
 	
 	hash=GET_HASH(frag->size);
 	for(f=qm->free_hash[hash].head.u.nxt_free; f!=&(qm->free_hash[hash].head);
 			f=f->u.nxt_free){
 		if (frag->size <= f->size) break;
 	}
 	/*insert it here*/
 	prev=FRAG_END(f)->prev_free;
 	prev->u.nxt_free=frag;
 	FRAG_END(frag)->prev_free=prev;
 	frag->u.nxt_free=f;
 	FRAG_END(f)->prev_free=frag;
 }
 
 
 
6fa79282
 /* init malloc and return a qm_block*/
 struct qm_block* qm_malloc_init(char* address, unsigned int size)
 {
 	char* start;
 	char* end;
 	struct qm_block* qm;
 	unsigned int init_overhead;
eca7f442
 	int h;
6fa79282
 	
 	/* make address and size multiple of 8*/
eca7f442
 	start=(char*)ROUNDUP((unsigned int) address);
f48312e2
 	DBG("qm_malloc_init: QM_OPTIMIZE=%d, /ROUNDTO=%d\n",
eca7f442
 			QM_MALLOC_OPTIMIZE, QM_MALLOC_OPTIMIZE/ROUNDTO);
f48312e2
 	DBG("qm_malloc_init: QM_HASH_SIZE=%d, qm_block size=%d\n",
eca7f442
 			QM_HASH_SIZE, sizeof(struct qm_block));
f48312e2
 	DBG("qm_malloc_init(%p, %d), start=%p\n", address, size, start);
6fa79282
 	if (size<start-address) return 0;
 	size-=(start-address);
eca7f442
 	if (size <(MIN_FRAG_SIZE+FRAG_OVERHEAD)) return 0;
 	size=ROUNDDOWN(size);
6fa79282
 	
b2dec9c6
 	init_overhead=ROUNDUP(sizeof(struct qm_block))+sizeof(struct qm_frag)+
6fa79282
 		sizeof(struct qm_frag_end);
f48312e2
 	DBG("qm_malloc_init: size= %d, init_overhead=%d\n", size, init_overhead);
eca7f442
 	
6fa79282
 	if (size < init_overhead)
 	{
 		/* not enough mem to create our control structures !!!*/
 		return 0;
 	}
 	end=start+size;
 	qm=(struct qm_block*)start;
 	memset(qm, 0, sizeof(struct qm_block));
02690ea6
 	size-=init_overhead;
 	qm->size=size;
6fa79282
 	qm->real_used=init_overhead;
02690ea6
 	qm->max_real_used=qm->real_used;
6fa79282
 	
b2dec9c6
 	qm->first_frag=(struct qm_frag*)(start+ROUNDUP(sizeof(struct qm_block)));
6fa79282
 	qm->last_frag_end=(struct qm_frag_end*)(end-sizeof(struct qm_frag_end));
 	/* init initial fragment*/
 	qm->first_frag->size=size;
 	qm->last_frag_end->size=size;
eca7f442
 	
2c65bd8b
 #ifdef DBG_QM_MALLOC
 	qm->first_frag->check=ST_CHECK_PATTERN;
 	qm->last_frag_end->check1=END_CHECK_PATTERN1;
 	qm->last_frag_end->check2=END_CHECK_PATTERN2;
 #endif
eca7f442
 	/* init free_hash* */
 	for (h=0; h<QM_HASH_SIZE;h++){
 		qm->free_hash[h].head.u.nxt_free=&(qm->free_hash[h].head);
 		qm->free_hash[h].tail.prev_free=&(qm->free_hash[h].head);
 		qm->free_hash[h].head.size=0;
 		qm->free_hash[h].tail.size=0;
 	}
 	
 	/* link initial fragment into the free list*/
 	
 	qm_insert_free(qm, qm->first_frag);
 	
 	/*qm->first_frag->u.nxt_free=&(qm->free_lst);
 	  qm->last_frag_end->prev_free=&(qm->free_lst);
 	*/
6fa79282
 	
 	
 	return qm;
 }
 
 
 
 static inline void qm_detach_free(struct qm_block* qm, struct qm_frag* frag)
 {
 	struct qm_frag *prev;
 	struct qm_frag *next;
 	
 	prev=FRAG_END(frag)->prev_free;
 	next=frag->u.nxt_free;
 	prev->u.nxt_free=next;
 	FRAG_END(next)->prev_free=prev;
 	
 }
 
 
 
eca7f442
 static inline struct qm_frag* qm_find_free(struct qm_block* qm, 
 										unsigned int size)
 {
 	int hash;
 	struct qm_frag* f;
 
 	for (hash=GET_HASH(size); hash<QM_HASH_SIZE; hash++){
 		for (f=qm->free_hash[hash].head.u.nxt_free; 
 					f!=&(qm->free_hash[hash].head); f=f->u.nxt_free){
 			if (f->size>=size) return f;
 		}
 	/*try in a bigger bucket*/
 	}
 	/* not found */
 	return 0;
 }
 
 
 
b4d048d4
 #ifdef DBG_QM_MALLOC
 void* qm_malloc(struct qm_block* qm, unsigned int size, char* file, char* func,
 					unsigned int line)
 #else
6fa79282
 void* qm_malloc(struct qm_block* qm, unsigned int size)
b4d048d4
 #endif
6fa79282
 {
 	struct qm_frag* f;
 	struct qm_frag_end* end;
 	struct qm_frag* n;
 	unsigned int rest;
 	
b4d048d4
 #ifdef DBG_QM_MALLOC
dda9dab1
 	unsigned int list_cntr;
 
 	list_cntr = 0;
f48312e2
 	DBG("qm_malloc(%p, %d) called from %s: %s(%d)\n", qm, size, file, func,
b4d048d4
 			line);
 #endif
6fa79282
 	/*size must be a multiple of 8*/
eca7f442
 	size=ROUNDUP(size);
6fa79282
 	if (size>(qm->size-qm->real_used)) return 0;
eca7f442
 
b2dec9c6
 	/*search for a suitable free frag*/
eca7f442
 	if ((f=qm_find_free(qm, size))!=0){
 		/* we found it!*/
 		/*detach it from the free list*/
2c65bd8b
 #ifdef DBG_QM_MALLOC
 			qm_debug_frag(qm, f);
 #endif
eca7f442
 		qm_detach_free(qm, f);
 		/*mark it as "busy"*/
 		f->u.is_free=0;
 		
 		/*see if we'll use full frag, or we'll split it in 2*/
 		rest=f->size-size;
 		if (rest>(FRAG_OVERHEAD+MIN_FRAG_SIZE)){
 			f->size=size;
 			/*split the fragment*/
 			end=FRAG_END(f);
 			end->size=size;
 			n=(struct qm_frag*)((char*)end+sizeof(struct qm_frag_end));
 			n->size=rest-FRAG_OVERHEAD;
 			FRAG_END(n)->size=n->size;
 			qm->real_used+=FRAG_OVERHEAD;
b4d048d4
 #ifdef DBG_QM_MALLOC
eca7f442
 			end->check1=END_CHECK_PATTERN1;
 			end->check2=END_CHECK_PATTERN2;
 			/* frag created by malloc, mark it*/
 			n->file=file;
 			n->func="frag. from qm_malloc";
 			n->line=line;
 			n->check=ST_CHECK_PATTERN;
 /*			FRAG_END(n)->check1=END_CHECK_PATTERN1;
 			FRAG_END(n)->check2=END_CHECK_PATTERN2; */
b4d048d4
 #endif
eca7f442
 			/* reinsert n in free list*/
 			qm_insert_free(qm, n);
 		}else{
 			/* we cannot split this fragment any more => alloc all of it*/
 		}
 		qm->real_used+=f->size;
 		qm->used+=f->size;
 		if (qm->max_real_used<qm->real_used)
 			qm->max_real_used=qm->real_used;
b4d048d4
 #ifdef DBG_QM_MALLOC
eca7f442
 		f->file=file;
 		f->func=func;
 		f->line=line;
 		f->check=ST_CHECK_PATTERN;
2c65bd8b
 		/*  FRAG_END(f)->check1=END_CHECK_PATTERN1;
 			FRAG_END(f)->check2=END_CHECK_PATTERN2;*/
f48312e2
 		DBG("qm_malloc(%p, %d) returns address %p on %d -th hit\n", qm, size,
dda9dab1
 			(char*)f+sizeof(struct qm_frag), list_cntr );
b4d048d4
 #endif
eca7f442
 		return (char*)f+sizeof(struct qm_frag);
6fa79282
 	}
 	return 0;
 }
 
 
 
b4d048d4
 #ifdef DBG_QM_MALLOC
 void qm_free(struct qm_block* qm, void* p, char* file, char* func, 
 				unsigned int line)
 #else
6fa79282
 void qm_free(struct qm_block* qm, void* p)
b4d048d4
 #endif
6fa79282
 {
 	struct qm_frag* f;
 	struct qm_frag* prev;
 	struct qm_frag* next;
 	unsigned int size;
 
b4d048d4
 #ifdef DBG_QM_MALLOC
f48312e2
 	DBG("qm_free(%p, %p), called from %s: %s(%d)\n", qm, p, file, func, line);
b4d048d4
 	if (p>(void*)qm->last_frag_end || p<(void*)qm->first_frag){
f48312e2
 		LOG(L_CRIT, "BUG: qm_free: bad pointer %p (out of memory block!) - "
b4d048d4
 				"aborting\n", p);
 		abort();
 	}
 #endif
6fa79282
 	if (p==0) {
eca7f442
 		LOG(L_WARN, "WARNING:qm_free: free(0) called\n");
6fa79282
 		return;
 	}
 	prev=next=0;
 	f=(struct qm_frag*) ((char*)p-sizeof(struct qm_frag));
b4d048d4
 #ifdef DBG_QM_MALLOC
2c65bd8b
 	qm_debug_frag(qm, f);
b4d048d4
 	if (f->u.is_free){
3faad3f2
 		LOG(L_CRIT, "BUG: qm_free: freeing already freed pointer,"
 				" first free: %s: %s(%d) - aborting\n",
 				f->file, f->func, f->line);
b4d048d4
 		abort();
 	}
 	DBG("qm_free: freeing block alloc'ed from %s: %s(%d)\n", f->file, f->func,
 			f->line);
 #endif
6fa79282
 	size=f->size;
 	qm->used-=size;
 	qm->real_used-=size;
2c65bd8b
 #ifdef DBG_QM_MALLOC
 	qm_debug_frag(qm, f);
 #endif
eca7f442
 
 #ifdef QM_JOIN_FREE
 	/* join packets if possible*/
b2dec9c6
 	next=FRAG_NEXT(f);
6fa79282
 	if (((char*)next < (char*)qm->last_frag_end) &&( next->u.is_free)){
 		/* join */
 		qm_detach_free(qm, next);
eca7f442
 		size+=next->size+FRAG_OVERHEAD;
 		qm->real_used-=FRAG_OVERHEAD;
6fa79282
 	}
 	
 	if (f > qm->first_frag){
 		prev=FRAG_PREV(f);
 		/*	(struct qm_frag*)((char*)f - (struct qm_frag_end*)((char*)f-
 								sizeof(struct qm_frag_end))->size);*/
2c65bd8b
 #ifdef DBG_QM_MALLOC
 		qm_debug_frag(qm, f);
 #endif
6fa79282
 		if (prev->u.is_free){
 			/*join*/
 			qm_detach_free(qm, prev);
eca7f442
 			size+=prev->size+FRAG_OVERHEAD;
 			qm->real_used-=FRAG_OVERHEAD;
6fa79282
 			f=prev;
 		}
 	}
02690ea6
 	f->size=size;
6fa79282
 	FRAG_END(f)->size=f->size;
eca7f442
 #endif /* QM_JOIN_FREE*/
b4d048d4
 #ifdef DBG_QM_MALLOC
 	f->file=file;
 	f->func=func;
 	f->line=line;
 #endif
6fa79282
 	qm_insert_free(qm, f);
 }
 
 
 
 void qm_status(struct qm_block* qm)
 {
 	struct qm_frag* f;
eca7f442
 	int i,j;
 	int h;
6fa79282
 
843b2927
 	LOG(memlog, "qm_status (%p):\n", qm);
dda9dab1
 	if (!qm) return;
 
843b2927
 	LOG(memlog, " heap size= %d\n", qm->size);
 	LOG(memlog, " used= %d, used+overhead=%d, free=%d\n",
6fa79282
 			qm->used, qm->real_used, qm->size-qm->real_used);
843b2927
 	LOG(memlog, " max used (+overhead)= %d\n", qm->max_real_used);
6fa79282
 	
843b2927
 	LOG(memlog, "dumping all allocked. fragments:\n");
6fa79282
 	for (f=qm->first_frag, i=0;(char*)f<(char*)qm->last_frag_end;f=FRAG_NEXT(f)
b4d048d4
 			,i++){
b2dec9c6
 		if (! f->u.is_free){
843b2927
 			LOG(memlog, "    %3d. %c  address=%p  size=%d\n", i, 
9dfa5dc4
 				(f->u.is_free)?'a':'N',
6fa79282
 				(char*)f+sizeof(struct qm_frag), f->size);
b4d048d4
 #ifdef DBG_QM_MALLOC
843b2927
 			LOG(memlog, "            %s from %s: %s(%d)\n",
b4d048d4
 				(f->u.is_free)?"freed":"alloc'd", f->file, f->func, f->line);
843b2927
 			LOG(memlog, "        start check=%x, end check= %x, %x\n",
2c65bd8b
 				f->check, FRAG_END(f)->check1, FRAG_END(f)->check2);
b4d048d4
 #endif
b2dec9c6
 		}
b4d048d4
 	}
843b2927
 	LOG(memlog, "dumping free list stats :\n");
eca7f442
 	for(h=0,i=0;h<QM_HASH_SIZE;h++){
 		
 		for (f=qm->free_hash[h].head.u.nxt_free,j=0; 
b2dec9c6
 				f!=&(qm->free_hash[h].head); f=f->u.nxt_free, i++, j++);
843b2927
 			if (j) LOG(memlog, "hash= %3d. fragments no.: %5d\n", h, j);
b4d048d4
 	}
843b2927
 	LOG(memlog, "-----------------------------\n");
6fa79282
 }
 
 
 
 
 #endif