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 |
|