1 |
root |
1.1 |
/* |
2 |
|
|
* malloc/free by O.Dreesen |
3 |
|
|
* |
4 |
|
|
* first TRY: |
5 |
|
|
* lists w/magics |
6 |
|
|
* and now the second TRY |
7 |
|
|
* let the kernel map all the stuff (if there is something to do) |
8 |
|
|
*/ |
9 |
|
|
|
10 |
|
|
#define _GNU_SOURCE 1 |
11 |
|
|
|
12 |
|
|
#include <unistd.h> |
13 |
|
|
#include <sys/mman.h> |
14 |
|
|
#include <errno.h> |
15 |
|
|
|
16 |
|
|
#include <sys/types.h> |
17 |
|
|
#include <stddef.h> |
18 |
|
|
#include <stdlib.h> |
19 |
|
|
#include <string.h> |
20 |
|
|
|
21 |
|
|
#include <limits.h> |
22 |
|
|
//#include <sys/shm.h> /* for PAGE_SIZE */ |
23 |
|
|
|
24 |
|
|
#ifndef PAGE_SIZE |
25 |
|
|
#define PAGE_SIZE sysconf (_SC_PAGESIZE) |
26 |
|
|
#endif |
27 |
|
|
|
28 |
|
|
#ifndef MREMAP_MAYMOVE |
29 |
|
|
#define MREMAP_MAYMOVE 1 |
30 |
|
|
#endif |
31 |
|
|
|
32 |
|
|
/* -- HELPER CODE --------------------------------------------------------- */ |
33 |
|
|
|
34 |
|
|
#ifndef MAP_FAILED |
35 |
|
|
#define MAP_FAILED ((void*)-1) |
36 |
|
|
#endif |
37 |
|
|
|
38 |
|
|
#ifndef NULL |
39 |
|
|
#define NULL ((void*)0) |
40 |
|
|
#endif |
41 |
|
|
|
42 |
|
|
typedef struct { |
43 |
|
|
void* next; |
44 |
|
|
size_t size; |
45 |
|
|
} __alloc_t; |
46 |
|
|
|
47 |
|
|
#define BLOCK_START(b) (((void*)(b))-sizeof(__alloc_t)) |
48 |
|
|
#define BLOCK_RET(b) (((void*)(b))+sizeof(__alloc_t)) |
49 |
|
|
|
50 |
|
|
#define MEM_BLOCK_SIZE PAGE_SIZE |
51 |
|
|
#define PAGE_ALIGN(s) (((s)+MEM_BLOCK_SIZE-1)&(unsigned long)(~(MEM_BLOCK_SIZE-1))) |
52 |
|
|
|
53 |
|
|
/* a simple mmap :) */ |
54 |
|
|
#if defined(__i386__) |
55 |
|
|
#define REGPARM(x) __attribute__((regparm(x))) |
56 |
|
|
#else |
57 |
|
|
#define REGPARM(x) |
58 |
|
|
#endif |
59 |
|
|
|
60 |
|
|
static void REGPARM(1) *do_mmap(size_t size) { |
61 |
|
|
return mmap(0, size, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, (size_t)0); |
62 |
|
|
} |
63 |
|
|
|
64 |
|
|
/* -- SMALL MEM ----------------------------------------------------------- */ |
65 |
|
|
|
66 |
|
|
static __alloc_t* __small_mem[8]; |
67 |
|
|
|
68 |
|
|
#define __SMALL_NR(i) (MEM_BLOCK_SIZE/(i)) |
69 |
|
|
|
70 |
|
|
#define __MIN_SMALL_SIZE __SMALL_NR(256) /* 16 / 32 */ |
71 |
|
|
#define __MAX_SMALL_SIZE __SMALL_NR(2) /* 2048 / 4096 */ |
72 |
|
|
|
73 |
|
|
#define GET_SIZE(s) (__MIN_SMALL_SIZE<<get_index((s))) |
74 |
|
|
|
75 |
|
|
#define FIRST_SMALL(p) (((unsigned long)(p))&(~(MEM_BLOCK_SIZE-1))) |
76 |
|
|
|
77 |
|
|
static inline int __ind_shift() { return (MEM_BLOCK_SIZE==4096)?4:5; } |
78 |
|
|
|
79 |
|
|
static size_t REGPARM(1) get_index(size_t _size) { |
80 |
|
|
register size_t idx=0; |
81 |
|
|
// if (_size) { /* we already check this in the callers */ |
82 |
|
|
register size_t size=((_size-1)&(MEM_BLOCK_SIZE-1))>>__ind_shift(); |
83 |
|
|
while(size) { size>>=1; ++idx; } |
84 |
|
|
// } |
85 |
|
|
return idx; |
86 |
|
|
} |
87 |
|
|
|
88 |
|
|
/* small mem */ |
89 |
|
|
static void __small_free(void*_ptr,size_t _size) REGPARM(2); |
90 |
|
|
|
91 |
|
|
static void REGPARM(2) __small_free(void*_ptr,size_t _size) { |
92 |
|
|
__alloc_t* ptr=BLOCK_START(_ptr); |
93 |
|
|
size_t size=_size; |
94 |
|
|
size_t idx=get_index(size); |
95 |
|
|
|
96 |
|
|
#ifdef WANT_FREE_OVERWRITE |
97 |
|
|
memset(ptr,0x55,size); /* allways zero out small mem */ |
98 |
|
|
#else |
99 |
|
|
#if 0 |
100 |
|
|
memset(ptr,0,size); /* allways zero out small mem */ |
101 |
|
|
#endif |
102 |
|
|
#endif |
103 |
|
|
|
104 |
|
|
ptr->next=__small_mem[idx]; |
105 |
|
|
__small_mem[idx]=ptr; |
106 |
|
|
} |
107 |
|
|
|
108 |
|
|
static void* REGPARM(1) __small_malloc(size_t _size) { |
109 |
|
|
__alloc_t *ptr; |
110 |
|
|
size_t size=_size; |
111 |
|
|
size_t idx; |
112 |
|
|
|
113 |
|
|
idx=get_index(size); |
114 |
|
|
ptr=__small_mem[idx]; |
115 |
|
|
|
116 |
|
|
if (ptr==0) { /* no free blocks ? */ |
117 |
|
|
register int i,nr; |
118 |
|
|
ptr=do_mmap(MEM_BLOCK_SIZE); |
119 |
|
|
if (ptr==MAP_FAILED) return MAP_FAILED; |
120 |
|
|
|
121 |
|
|
__small_mem[idx]=ptr; |
122 |
|
|
|
123 |
|
|
nr=__SMALL_NR(size)-1; |
124 |
|
|
for (i=0;i<nr;i++) { |
125 |
|
|
ptr->next=(((void*)ptr)+size); |
126 |
|
|
ptr=ptr->next; |
127 |
|
|
} |
128 |
|
|
ptr->next=0; |
129 |
|
|
|
130 |
|
|
ptr=__small_mem[idx]; |
131 |
|
|
} |
132 |
|
|
|
133 |
|
|
/* get a free block */ |
134 |
|
|
__small_mem[idx]=ptr->next; |
135 |
|
|
ptr->next=0; |
136 |
|
|
|
137 |
|
|
return ptr; |
138 |
|
|
} |
139 |
|
|
|
140 |
|
|
/* -- PUBLIC FUNCTIONS ---------------------------------------------------- */ |
141 |
|
|
|
142 |
|
|
void free(void *ptr) { |
143 |
|
|
register size_t size; |
144 |
|
|
if (ptr) { |
145 |
|
|
size=((__alloc_t*)BLOCK_START(ptr))->size; |
146 |
|
|
if (size) { |
147 |
|
|
if (size<=__MAX_SMALL_SIZE) |
148 |
|
|
__small_free(ptr,size); |
149 |
|
|
else |
150 |
|
|
munmap(BLOCK_START(ptr),size); |
151 |
|
|
} |
152 |
|
|
} |
153 |
|
|
} |
154 |
|
|
|
155 |
|
|
void* malloc(size_t size) { |
156 |
|
|
__alloc_t* ptr; |
157 |
|
|
size_t need; |
158 |
|
|
if (!size) goto err_out; |
159 |
|
|
size+=sizeof(__alloc_t); |
160 |
|
|
if (size<sizeof(__alloc_t)) goto err_out; |
161 |
|
|
if (size<=__MAX_SMALL_SIZE) { |
162 |
|
|
need=GET_SIZE(size); |
163 |
|
|
ptr=__small_malloc(need); |
164 |
|
|
} |
165 |
|
|
else { |
166 |
|
|
need=PAGE_ALIGN(size); |
167 |
|
|
if (!need) ptr=MAP_FAILED; else ptr=do_mmap(need); |
168 |
|
|
} |
169 |
|
|
if (ptr==MAP_FAILED) goto err_out; |
170 |
|
|
ptr->size=need; |
171 |
|
|
return BLOCK_RET(ptr); |
172 |
|
|
err_out: |
173 |
|
|
//(*__errno_location())=ENOMEM; |
174 |
|
|
return 0; |
175 |
|
|
} |
176 |
|
|
|
177 |
|
|
void* calloc(size_t nmemb, size_t _size) { |
178 |
|
|
register size_t size=_size*nmemb; |
179 |
|
|
if (nmemb && size/nmemb!=_size) { |
180 |
|
|
//(*__errno_location())=ENOMEM; |
181 |
|
|
return 0; |
182 |
|
|
} |
183 |
|
|
#ifdef WANT_FREE_OVERWRITE |
184 |
|
|
if (size<__MAX_SMALL_SIZE) { |
185 |
|
|
void* x=malloc(size); |
186 |
|
|
memset(x,0,size); |
187 |
|
|
return x; |
188 |
|
|
} else |
189 |
|
|
#endif |
190 |
|
|
return malloc(size); |
191 |
|
|
} |
192 |
|
|
|
193 |
|
|
void* realloc(void* ptr, size_t _size) { |
194 |
|
|
register size_t size=_size; |
195 |
|
|
if (ptr) { |
196 |
|
|
if (size) { |
197 |
|
|
__alloc_t* tmp=BLOCK_START(ptr); |
198 |
|
|
size+=sizeof(__alloc_t); |
199 |
|
|
if (size<sizeof(__alloc_t)) goto retzero; |
200 |
|
|
size=(size<=__MAX_SMALL_SIZE)?GET_SIZE(size):PAGE_ALIGN(size); |
201 |
|
|
if (tmp->size!=size) { |
202 |
|
|
if ((tmp->size<=__MAX_SMALL_SIZE)) { |
203 |
|
|
void *new=malloc(_size); |
204 |
|
|
if (new) { |
205 |
|
|
register __alloc_t* foo=BLOCK_START(new); |
206 |
|
|
size=foo->size; |
207 |
|
|
if (size>tmp->size) size=tmp->size; |
208 |
|
|
if (size) memcpy(new,ptr,size-sizeof(__alloc_t)); |
209 |
|
|
free(ptr); |
210 |
|
|
} |
211 |
|
|
ptr=new; |
212 |
|
|
} |
213 |
|
|
else { |
214 |
|
|
register __alloc_t* foo; |
215 |
|
|
size=PAGE_ALIGN(size); |
216 |
|
|
foo=mremap(tmp,tmp->size,size,MREMAP_MAYMOVE); |
217 |
|
|
if (foo==MAP_FAILED) { |
218 |
|
|
retzero: |
219 |
|
|
//(*__errno_location())=ENOMEM; |
220 |
|
|
ptr=0; |
221 |
|
|
} |
222 |
|
|
else { |
223 |
|
|
foo->size=size; |
224 |
|
|
ptr=BLOCK_RET(foo); |
225 |
|
|
} |
226 |
|
|
} |
227 |
|
|
} |
228 |
|
|
} |
229 |
|
|
else { /* size==0 */ |
230 |
|
|
free(ptr); |
231 |
|
|
ptr = NULL; |
232 |
|
|
} |
233 |
|
|
} |
234 |
|
|
else { /* ptr==0 */ |
235 |
|
|
if (size) { |
236 |
|
|
ptr=malloc(size); |
237 |
|
|
} |
238 |
|
|
} |
239 |
|
|
return ptr; |
240 |
|
|
} |
241 |
|
|
|