- malloc replacements
[sip-router] / q_malloc.c
1 /* $Id$
2  *
3  */
4
5 #define q_malloc
6 #ifdef q_malloc
7
8 #include "q_malloc.h"
9 #include "dprint.h"
10
11
12 /*usefull macros*/
13 #define FRAG_END(f)  \
14                         ((struct qm_frag_end*)((char*)f+sizeof(struct qm_frag)+f->size))
15
16 #define FRAG_NEXT(f) \
17                         ((struct qm_frag*)((char*)f+sizeof(struct qm_frag)+f->size+ \
18                                                            sizeof(struct qm_frag_end)))
19                         
20 #define FRAG_PREV(f) \
21                 ( (struct qm_frag*) ( ((char*)f-sizeof(struct qm_frag_end))- \
22                 ((struct qm_frag_end*)((char*)f-sizeof(struct qm_frag_end)))->size- \
23                         sizeof(struct qm_frag) ) )
24
25
26
27
28
29 /* init malloc and return a qm_block*/
30 struct qm_block* qm_malloc_init(char* address, unsigned int size)
31 {
32         char* start;
33         char* end;
34         struct qm_block* qm;
35         unsigned int init_overhead;
36         unsigned int init_size;
37         
38         init_size=size;
39         /* make address and size multiple of 8*/
40         start=(char*)( ((unsigned int)address%8)?((unsigned int)address+8)/8*8:
41                         (unsigned int)address);
42         if (size<start-address) return 0;
43         size-=(start-address);
44         if (size <8) return 0;
45         size=(size%8)?(size-8)/8*8:size;
46         
47         init_overhead=sizeof(struct qm_block)+sizeof(struct qm_frag)+
48                 sizeof(struct qm_frag_end);
49         if (size < init_overhead)
50         {
51                 /* not enough mem to create our control structures !!!*/
52                 return 0;
53         }
54         end=start+size;
55         qm=(struct qm_block*)start;
56         memset(qm, 0, sizeof(struct qm_block));
57         qm->init_size=init_size;
58         qm->size=size-init_overhead;
59         qm->real_used=init_overhead;
60         
61         qm->first_frag=(struct qm_frag*)(start+sizeof(struct qm_block));
62         qm->last_frag_end=(struct qm_frag_end*)(end-sizeof(struct qm_frag_end));
63         /* init initial fragment*/
64         qm->first_frag->size=size;
65         qm->first_frag->u.nxt_free=&(qm->free_lst);
66         qm->last_frag_end->size=size;
67         qm->last_frag_end->prev_free=&(qm->free_lst);
68         /* init free_lst* */
69         qm->free_lst.u.nxt_free=qm->first_frag;
70         qm->free_lst_end.prev_free=qm->first_frag;
71         qm->free_lst.size=0;
72         qm->free_lst_end.size=0;
73         
74         
75         return qm;
76 }
77
78
79 static inline void qm_insert_free(struct qm_block* qm, struct qm_frag* frag)
80 {
81         struct qm_frag* f;
82         struct qm_frag* prev;
83
84         for(f=qm->free_lst.u.nxt_free; f!=&(qm->free_lst); f=f->u.nxt_free){
85                 if (frag->size < f->size) break;
86         }
87         /*insert it here*/
88         prev=FRAG_END(f)->prev_free;
89         prev->u.nxt_free=frag;
90         FRAG_END(frag)->prev_free=prev;
91         frag->u.nxt_free=f;
92         FRAG_END(f)->prev_free=frag;
93 }
94
95
96
97 static inline void qm_detach_free(struct qm_block* qm, struct qm_frag* frag)
98 {
99         struct qm_frag *prev;
100         struct qm_frag *next;
101         
102         struct qm_frag_end *end;
103
104         prev=FRAG_END(frag)->prev_free;
105         next=frag->u.nxt_free;
106         prev->u.nxt_free=next;
107         FRAG_END(next)->prev_free=prev;
108         
109 }
110
111
112
113 void* qm_malloc(struct qm_block* qm, unsigned int size)
114 {
115         struct qm_frag* f;
116         struct qm_frag_end* end;
117         struct qm_frag* n;
118         unsigned int rest;
119         unsigned int overhead;
120         
121         /*size must be a multiple of 8*/
122         size=(size%8)?(size+8)/8*8:size;
123         if (size>(qm->size-qm->real_used)) return 0;
124         if (qm->free_lst.u.nxt_free==&(qm->free_lst)) return 0;
125         /*search for a suitable free frag*/
126         for (f=qm->free_lst.u.nxt_free; f!=&(qm->free_lst); f=f->u.nxt_free){
127                 if (f->size>=size){
128                         /* we found it!*/
129                         /*detach it from the free list*/
130                         qm_detach_free(qm, f);
131                         /*mark it as "busy"*/
132                         f->u.is_free=0;
133                         
134                         /*see if we'll use full frag, or we'll split it in 2*/
135                         rest=f->size-size;
136                         overhead=sizeof(struct qm_frag)+sizeof(struct qm_frag_end);
137                         if (rest>overhead){
138                                 f->size=size;
139                                 /*split the fragment*/
140                                 end=FRAG_END(f);
141                                 end->size=size;
142                                 n=(struct qm_frag*)((char*)end+sizeof(struct qm_frag_end));
143                                 n->size=rest-overhead;
144                                 FRAG_END(n)->size=n->size;
145                                 qm->real_used+=overhead;
146                                 /* reinsert n in free list*/
147                                 qm_insert_free(qm, n);
148                         }else{
149                                 /* we cannot split this fragment any more => alloc all of it*/
150                         }
151                         qm->real_used+=f->size;
152                         qm->used+=f->size;
153                         return (char*)f+sizeof(struct qm_frag);
154                 }
155         }
156         return 0;
157 }
158
159
160
161 void qm_free(struct qm_block* qm, void* p)
162 {
163         struct qm_frag* f;
164         struct qm_frag* prev;
165         struct qm_frag* next;
166         struct qm_frag_end *end;
167         unsigned int overhead;
168         unsigned int size;
169
170         if (p==0) {
171                 DBG("WARNING:qm_free: free(0) called\n");
172                 return;
173         }
174         prev=next=0;
175         f=(struct qm_frag*) ((char*)p-sizeof(struct qm_frag));
176         overhead=sizeof(struct qm_frag)+sizeof(struct qm_frag_end);
177         next=FRAG_NEXT(f);
178         size=f->size;
179         qm->used-=size;
180         qm->real_used-=size;
181         if (((char*)next < (char*)qm->last_frag_end) &&( next->u.is_free)){
182                 /* join */
183                 qm_detach_free(qm, next);
184                 size+=next->size+overhead;
185                 qm->real_used-=overhead;
186         }
187         
188         if (f > qm->first_frag){
189                 prev=FRAG_PREV(f);
190                 /*      (struct qm_frag*)((char*)f - (struct qm_frag_end*)((char*)f-
191                                                                 sizeof(struct qm_frag_end))->size);*/
192                 if (prev->u.is_free){
193                         /*join*/
194                         qm_detach_free(qm, prev);
195                         size+=prev->size+overhead;
196                         qm->real_used-=overhead;
197                         f=prev;
198                 }
199         }
200         FRAG_END(f)->size=f->size;
201         qm_insert_free(qm, f);
202 }
203
204
205
206 void qm_status(struct qm_block* qm)
207 {
208         struct qm_frag* f;
209         int i;
210
211         DBG("qm_status (%x):\n", qm);
212         DBG(" init_size= %d", qm->init_size);
213         DBG(" heap size= %d", qm->size);
214         DBG(" used= %d, used+overhead=%d, free=%d\n",
215                         qm->used, qm->real_used, qm->size-qm->real_used);
216         
217         DBG("dumping all fragments:\n");
218         for (f=qm->first_frag, i=0;(char*)f<(char*)qm->last_frag_end;f=FRAG_NEXT(f)
219                         ,i++)
220                 DBG("    %3d. %c  address=%x  size=%d\n", i, (f->u.is_free)?'a':'N',
221                                 (char*)f+sizeof(struct qm_frag), f->size);
222         DBG("dumping free list:\n");
223         for (f=qm->free_lst.u.nxt_free; f!=&(qm->free_lst); f=f->u.nxt_free)
224                 DBG("    %3d. %c  address=%x  size=%d\n", i, (f->u.is_free)?'a':'N',
225                                 (char*)f+sizeof(struct qm_frag), f->size);
226         DBG("-----------------------------\n");
227 }
228
229
230
231
232 #endif