]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | * Example memory allocator with pool allocation for small sizes and | |
3 | * fallback into malloc/realloc/free for larger sizes or when the pools | |
4 | * are exhausted. | |
5 | * | |
6 | * Useful to reduce memory churn or work around a platform allocator | |
7 | * that doesn't handle a lot of small allocations efficiently. | |
8 | */ | |
9 | ||
10 | #include "duktape.h" | |
11 | #include <stdio.h> | |
12 | #include <stdlib.h> | |
13 | #include <string.h> | |
14 | #include <stdint.h> | |
15 | ||
16 | /* Define to enable some debug printfs. */ | |
17 | /* #define DUK_ALLOC_HYBRID_DEBUG */ | |
18 | ||
19 | typedef struct { | |
20 | size_t size; | |
21 | int count; | |
22 | } pool_size_spec; | |
23 | ||
24 | static pool_size_spec pool_sizes[] = { | |
25 | { 32, 1024 }, | |
26 | { 48, 2048 }, | |
27 | { 64, 2048 }, | |
28 | { 128, 2048 }, | |
29 | { 256, 512 }, | |
30 | { 1024, 64 }, | |
31 | { 2048, 32 } | |
32 | }; | |
33 | ||
34 | #define NUM_POOLS (sizeof(pool_sizes) / sizeof(pool_size_spec)) | |
35 | ||
36 | /* This must fit into the smallest pool entry. */ | |
37 | struct pool_free_entry; | |
38 | typedef struct pool_free_entry pool_free_entry; | |
39 | struct pool_free_entry { | |
40 | pool_free_entry *next; | |
41 | }; | |
42 | ||
43 | typedef struct { | |
44 | pool_free_entry *free; | |
45 | char *alloc_start; | |
46 | char *alloc_end; | |
47 | size_t size; | |
48 | int count; | |
49 | } pool_header; | |
50 | ||
51 | typedef struct { | |
52 | pool_header headers[NUM_POOLS]; | |
53 | size_t pool_max_size; | |
54 | char *alloc_start; | |
55 | char *alloc_end; | |
56 | } pool_state; | |
57 | ||
58 | #define ADDR_IN_STATE_ALLOC(st,p) \ | |
59 | ((char *) (p) >= (st)->alloc_start && (char *) (p) < (st)->alloc_end) | |
60 | #define ADDR_IN_HEADER_ALLOC(hdr,p) \ | |
61 | ((char *) (p) >= (hdr)->alloc_start && (char *) (p) < (hdr)->alloc_end) | |
62 | ||
63 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
64 | static void dump_pool_state(pool_state *st) { | |
65 | pool_free_entry *free; | |
66 | int free_len; | |
67 | int i; | |
68 | ||
69 | printf("=== Pool state: st=%p\n", (void *) st); | |
70 | for (i = 0; i < (int) NUM_POOLS; i++) { | |
71 | pool_header *hdr = st->headers + i; | |
72 | ||
73 | for (free = hdr->free, free_len = 0; free != NULL; free = free->next) { | |
74 | free_len++; | |
75 | } | |
76 | ||
77 | printf("[%d]: size %ld, count %ld, used %ld, free list len %ld\n", | |
78 | i, (long) hdr->size, (long) hdr->count, | |
79 | (long) (hdr->count - free_len), | |
80 | (long) free_len); | |
81 | } | |
82 | } | |
83 | #else | |
84 | static void dump_pool_state(pool_state *st) { | |
85 | (void) st; | |
86 | } | |
87 | #endif | |
88 | ||
89 | void *duk_alloc_hybrid_init(void) { | |
90 | pool_state *st; | |
91 | size_t total_size, max_size; | |
92 | int i, j; | |
93 | char *p; | |
94 | ||
95 | st = (pool_state *) malloc(sizeof(pool_state)); | |
96 | if (!st) { | |
97 | return NULL; | |
98 | } | |
99 | memset((void *) st, 0, sizeof(pool_state)); | |
100 | st->alloc_start = NULL; | |
101 | st->alloc_end = NULL; | |
102 | ||
103 | for (i = 0, total_size = 0, max_size = 0; i < (int) NUM_POOLS; i++) { | |
104 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
105 | printf("Pool %d: size %ld, count %ld\n", i, (long) pool_sizes[i].size, (long) pool_sizes[i].count); | |
106 | #endif | |
107 | total_size += pool_sizes[i].size * pool_sizes[i].count; | |
108 | if (pool_sizes[i].size > max_size) { | |
109 | max_size = pool_sizes[i].size; | |
110 | } | |
111 | } | |
112 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
113 | printf("Total size %ld, max pool size %ld\n", (long) total_size, (long) max_size); | |
114 | #endif | |
115 | ||
116 | st->alloc_start = (char *) malloc(total_size); | |
117 | if (!st->alloc_start) { | |
118 | free(st); | |
119 | return NULL; | |
120 | } | |
121 | st->alloc_end = st->alloc_start + total_size; | |
122 | st->pool_max_size = max_size; | |
123 | memset((void *) st->alloc_start, 0, total_size); | |
124 | ||
125 | for (i = 0, p = st->alloc_start; i < (int) NUM_POOLS; i++) { | |
126 | pool_header *hdr = st->headers + i; | |
127 | ||
128 | hdr->alloc_start = p; | |
129 | hdr->alloc_end = p + pool_sizes[i].size * pool_sizes[i].count; | |
130 | hdr->free = (pool_free_entry *) (void *) p; | |
131 | hdr->size = pool_sizes[i].size; | |
132 | hdr->count = pool_sizes[i].count; | |
133 | ||
134 | for (j = 0; j < pool_sizes[i].count; j++) { | |
135 | pool_free_entry *ent = (pool_free_entry *) (void *) p; | |
136 | if (j == pool_sizes[i].count - 1) { | |
137 | ent->next = (pool_free_entry *) NULL; | |
138 | } else { | |
139 | ent->next = (pool_free_entry *) (void *) (p + pool_sizes[i].size); | |
140 | } | |
141 | p += pool_sizes[i].size; | |
142 | } | |
143 | } | |
144 | ||
145 | dump_pool_state(st); | |
146 | ||
147 | /* Use 'st' as udata. */ | |
148 | return (void *) st; | |
149 | } | |
150 | ||
151 | void *duk_alloc_hybrid(void *udata, duk_size_t size) { | |
152 | pool_state *st = (pool_state *) udata; | |
153 | int i; | |
154 | void *new_ptr; | |
155 | ||
156 | #if 0 | |
157 | dump_pool_state(st); | |
158 | #endif | |
159 | ||
160 | if (size == 0) { | |
161 | return NULL; | |
162 | } | |
163 | if (size > st->pool_max_size) { | |
164 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
165 | printf("alloc fallback: %ld\n", (long) size); | |
166 | #endif | |
167 | return malloc(size); | |
168 | } | |
169 | ||
170 | for (i = 0; i < (int) NUM_POOLS; i++) { | |
171 | pool_header *hdr = st->headers + i; | |
172 | if (hdr->size < size) { | |
173 | continue; | |
174 | } | |
175 | ||
176 | if (hdr->free) { | |
177 | #if 0 | |
178 | printf("alloc from pool: %ld -> pool size %ld\n", (long) size, (long) hdr->size); | |
179 | #endif | |
180 | new_ptr = (void *) hdr->free; | |
181 | hdr->free = hdr->free->next; | |
182 | return new_ptr; | |
183 | } else { | |
184 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
185 | printf("alloc out of pool entries: %ld -> pool size %ld\n", (long) size, (long) hdr->size); | |
186 | #endif | |
187 | break; | |
188 | } | |
189 | } | |
190 | ||
191 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
192 | printf("alloc fallback (out of pool): %ld\n", (long) size); | |
193 | #endif | |
194 | return malloc(size); | |
195 | } | |
196 | ||
197 | void *duk_realloc_hybrid(void *udata, void *ptr, duk_size_t size) { | |
198 | pool_state *st = (pool_state *) udata; | |
199 | void *new_ptr; | |
200 | int i; | |
201 | ||
202 | #if 0 | |
203 | dump_pool_state(st); | |
204 | #endif | |
205 | ||
206 | if (ADDR_IN_STATE_ALLOC(st, ptr)) { | |
207 | /* 'ptr' cannot be NULL. */ | |
208 | for (i = 0; i < (int) NUM_POOLS; i++) { | |
209 | pool_header *hdr = st->headers + i; | |
210 | if (ADDR_IN_HEADER_ALLOC(hdr, ptr)) { | |
211 | if (size <= hdr->size) { | |
212 | /* Still fits, no shrink support. */ | |
213 | #if 0 | |
214 | printf("realloc original from pool: still fits, size %ld, pool size %ld\n", | |
215 | (long) size, (long) hdr->size); | |
216 | #endif | |
217 | return ptr; | |
218 | } | |
219 | ||
220 | new_ptr = duk_alloc_hybrid(udata, size); | |
221 | if (!new_ptr) { | |
222 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
223 | printf("realloc original from pool: needed larger size, failed to alloc\n"); | |
224 | #endif | |
225 | return NULL; | |
226 | } | |
227 | memcpy(new_ptr, ptr, hdr->size); | |
228 | ||
229 | ((pool_free_entry *) ptr)->next = hdr->free; | |
230 | hdr->free = (pool_free_entry *) ptr; | |
231 | #if 0 | |
232 | printf("realloc original from pool: size %ld, pool size %ld\n", (long) size, (long) hdr->size); | |
233 | #endif | |
234 | return new_ptr; | |
235 | } | |
236 | } | |
237 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
238 | printf("NEVER HERE\n"); | |
239 | #endif | |
240 | return NULL; | |
241 | } else if (ptr != NULL) { | |
242 | if (size == 0) { | |
243 | free(ptr); | |
244 | return NULL; | |
245 | } else { | |
246 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
247 | printf("realloc fallback: size %ld\n", (long) size); | |
248 | #endif | |
249 | return realloc(ptr, size); | |
250 | } | |
251 | } else { | |
252 | #if 0 | |
253 | printf("realloc NULL ptr, call alloc: %ld\n", (long) size); | |
254 | #endif | |
255 | return duk_alloc_hybrid(udata, size); | |
256 | } | |
257 | } | |
258 | ||
259 | void duk_free_hybrid(void *udata, void *ptr) { | |
260 | pool_state *st = (pool_state *) udata; | |
261 | int i; | |
262 | ||
263 | #if 0 | |
264 | dump_pool_state(st); | |
265 | #endif | |
266 | ||
267 | if (!ADDR_IN_STATE_ALLOC(st, ptr)) { | |
268 | if (ptr == NULL) { | |
269 | return; | |
270 | } | |
271 | #if 0 | |
272 | printf("free out of pool: %p\n", (void *) ptr); | |
273 | #endif | |
274 | free(ptr); | |
275 | return; | |
276 | } | |
277 | ||
278 | for (i = 0; i < (int) NUM_POOLS; i++) { | |
279 | pool_header *hdr = st->headers + i; | |
280 | if (ADDR_IN_HEADER_ALLOC(hdr, ptr)) { | |
281 | ((pool_free_entry *) ptr)->next = hdr->free; | |
282 | hdr->free = (pool_free_entry *) ptr; | |
283 | #if 0 | |
284 | printf("free from pool: %p\n", ptr); | |
285 | #endif | |
286 | return; | |
287 | } | |
288 | } | |
289 | ||
290 | #ifdef DUK_ALLOC_HYBRID_DEBUG | |
291 | printf("NEVER HERE\n"); | |
292 | #endif | |
293 | } |