source: trunk/src/kash/shheap.c@ 2291

Last change on this file since 2291 was 2291, checked in by bird, 16 years ago

hash: cooked our own heap on windows (for forking).
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 14.0 KB
Line 
1/* $Id: shheap.c 2291 2009-02-28 01:06:16Z bird $ */
2/** @file
3 * The shell memory heap methods.
4 */
5
6/*
7 * Copyright (c) 2009 knut st. osmundsen <bird-kBuild-spamix@anduin.net>
8 *
9 *
10 * This file is part of kBuild.
11 *
12 * kBuild is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
16 *
17 * kBuild is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with kBuild; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 */
27
28/*******************************************************************************
29* Header Files *
30*******************************************************************************/
31#include <string.h>
32#include <stdlib.h>
33#include <assert.h>
34#include "shinstance.h"
35
36#if K_OS == K_OS_WINDOWS
37# define SHHEAP_IN_USE
38#endif
39
40#ifdef SHHEAP_IN_USE
41# if K_OS == K_OS_WINDOWS
42# include <Windows.h>
43# else
44# include <unistd.h>
45# endif
46#endif
47
48
49/*******************************************************************************
50* Structures and Typedefs *
51*******************************************************************************/
52#ifdef SHHEAP_IN_USE
53/**
54 * heap memory block header.
55 */
56typedef struct shmemhdr
57{
58 size_t magic; /**< Magic value */
59 size_t size; /**< The block size */
60 struct shmemhdr *next; /**< Forward pointer. */
61 struct shmemhdr *prev; /**< Backward pointer. */
62 struct shmemhdr *next2; /**< Free/Shell list forward. */
63 struct shmemhdr *prev2; /**< Free/Shell list backward. */
64 struct shinstance *psh; /**< The shell who allocated it. */
65 struct shmemchunk *chunk; /**< The chunk who owns this. */
66} shmemhdr;
67
68/** Free block magic (shmemhdr::magic) */
69#define SHMEMHDR_MAGIC_FREE 0xbeeff00d
70/** Used block magic (shmemhdr::magic) */
71#define SHMEMHDR_MAGIC_USED 0xfeedface
72
73typedef struct shmemchunk
74{
75 struct shmemhdr *head; /**< Head of the block list. */
76 struct shmemhdr *free_head; /**< Head of the free list. */
77 struct shmemchunk *next; /**< The next block. */
78 struct shmemchunk *prev; /**< The previous block. */
79 size_t size; /**< Chunk size. */
80 size_t magic; /**< Magic value. */
81 size_t padding0;
82 size_t padding1;
83} shmemchunk;
84
85/** shmemchunk::magic */
86#define SHMEMCHUNK_MAGIC 0x12345678
87
88#endif /* K_OS_WINDOWS */
89
90
91/*******************************************************************************
92* Defined Constants And Macros *
93*******************************************************************************/
94#define SHHEAP_ALIGN(sz) (((sz) + 31) & ~(size_t)31)
95#define SHHEAP_CHUNK_ALIGN(sz) (((sz) + 0xffff) & ~(size_t)0xffff)
96#define SHHEAP_MIN_CHUNK 0x10000 //(1024*1024)
97#ifdef NDEBUG
98# define SHHEAP_CHECK() do { } while (0)
99# define SHHEAP_CHECK_2() do { } while (0)
100# define SHHEAP_ASSERT(expr) do { } while (0)
101# define SHHEAP_POISON_PSH(p,v) (p)
102# define SHHEAP_POISON_NULL(v) NULL
103#else
104# define SHHEAP_CHECK() shheap_check()
105# define SHHEAP_CHECK_2() shheap_check()
106# define SHHEAP_ASSERT(expr) assert(expr)
107# define SHHEAP_POISON_PSH(p,v) ((shinstance *)(v))
108# define SHHEAP_POISON_NULL(v) ((void *)(v))
109#endif
110
111
112/*******************************************************************************
113* Global Variables *
114*******************************************************************************/
115#ifdef SHHEAP_IN_USE
116/** The heap lock. */
117static shmtx g_sh_heap_mtx;
118/** The heap.
119 * This is a list of chunks. */
120static shmemchunk *g_sh_heap;
121#endif
122
123
124int shheap_init(void)
125{
126 int rc;
127#ifdef SHHEAP_IN_USE
128 SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(shmemhdr)) == sizeof(shmemhdr));
129 rc = shmtx_init(&g_sh_heap_mtx);
130#else
131 rc = 0;
132#endif
133 return rc;
134}
135
136#ifdef SHHEAP_IN_USE
137
138/**
139 * Checks a heap chunk.
140 * @param chunk The chunk to check.
141 */
142static void shheap_check_chunk(shmemchunk *chunk)
143{
144 size_t free_count;
145 struct shmemhdr *mem;
146 struct shmemhdr *prev;
147
148 SHHEAP_ASSERT(chunk->magic == SHMEMCHUNK_MAGIC);
149 SHHEAP_ASSERT(chunk->head);
150 SHHEAP_ASSERT(chunk->size == SHHEAP_CHUNK_ALIGN(chunk->size));
151
152 free_count = 0;
153 prev = NULL;
154 for (mem = chunk->head; mem; mem = mem->next)
155 {
156 size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
157 SHHEAP_ASSERT(mem->size == size);
158 SHHEAP_ASSERT(mem->prev == prev);
159 if (mem->magic == SHMEMHDR_MAGIC_FREE)
160 free_count++;
161 else
162 SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_USED);
163 prev = mem;
164 }
165
166 prev = NULL;
167 for (mem = chunk->free_head; mem; mem = mem->next2)
168 {
169 size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
170 SHHEAP_ASSERT(mem->size == size);
171 SHHEAP_ASSERT(mem->prev2 == prev);
172 SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_FREE);
173 free_count--;
174 prev = mem;
175 }
176 SHHEAP_ASSERT(free_count == 0);
177}
178
179/**
180 * Checks the heap.
181 */
182static void shheap_check(void)
183{
184 shmemchunk *chunk;
185 for (chunk = g_sh_heap; chunk; chunk = chunk->next)
186 shheap_check_chunk(chunk);
187}
188
189/**
190 * Grows the heap with another chunk carving out a block
191 *
192 * @returns Pointer to a used entry of size @a size1. NULL
193 * if we're out of memory
194 * @param size1 The size of the block to be returned (aligned).
195 */
196static shmemhdr *shheap_grow(size_t size1)
197{
198 shmemchunk *chunk;
199 shmemhdr *used;
200 shmemhdr *avail;
201 size_t chunk_size;
202
203 /* Calc the chunk size and allocate it. */
204 chunk_size = SHHEAP_ALIGN(size1) + SHHEAP_ALIGN(sizeof(*chunk)) + SHHEAP_ALIGN(sizeof(*used)) * 10;
205 if (chunk_size < SHHEAP_MIN_CHUNK)
206 chunk_size = SHHEAP_MIN_CHUNK;
207 else
208 chunk_size = SHHEAP_CHUNK_ALIGN(chunk_size);
209
210# if K_OS == K_OS_WINDOWS
211 chunk = (shmemchunk *)VirtualAlloc(NULL, chunk_size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
212# else
213 chunk = NULL;
214# endif
215
216 if (!chunk)
217 return NULL;
218
219 used = (shmemhdr *)((char *)chunk + SHHEAP_ALIGN(sizeof(*chunk)));
220 avail = (shmemhdr *)((char *)(used + 1) + size1);
221
222 used->magic = SHMEMHDR_MAGIC_USED;
223 used->size = size1;
224 used->next = avail;
225 used->prev = NULL;
226 used->next2 = SHHEAP_POISON_NULL(0x41);
227 used->prev2 = SHHEAP_POISON_NULL(0x41);
228 used->psh = NULL;
229 used->chunk = chunk;
230
231 avail->magic = SHMEMHDR_MAGIC_FREE;
232 avail->size = (char *)chunk + chunk_size - (char *)(avail + 1);
233 avail->next = NULL;
234 avail->prev = used;
235 avail->next2 = NULL;
236 avail->prev2 = NULL;
237 avail->psh = NULL;
238 avail->chunk = chunk;
239
240 chunk->head = used;
241 chunk->free_head = avail;
242 chunk->size = chunk_size;
243 chunk->magic = SHMEMCHUNK_MAGIC;
244 chunk->prev = NULL;
245 chunk->next = g_sh_heap;
246 if (g_sh_heap)
247 g_sh_heap->prev = chunk;
248 g_sh_heap = chunk;
249 chunk->padding0 = 0;
250 chunk->padding1 = 0;
251
252 SHHEAP_CHECK_2();
253 return used;
254}
255
256/***
257 * Splits a big memory block into two smaller, one with the
258 * size @a size1.
259 *
260 * The one with the given size is removed from the free list
261 * while the other one remains there.
262 *
263 * @returns The @a size1 sized block, NULL on failure.
264 * @param big The block that is too big.
265 * @param size1 The size of the block to be returned (aligned).
266 */
267static shmemhdr *shheap_split(shmemhdr *big, size_t size1)
268{
269 shmemhdr *split;
270 SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(*big)) == sizeof(*big));
271 SHHEAP_ASSERT(big->magic == SHMEMHDR_MAGIC_FREE);
272 SHHEAP_ASSERT(!big->next2 || big->next2->magic == SHMEMHDR_MAGIC_FREE);
273 SHHEAP_ASSERT(!big->prev2 || big->prev2->magic == SHMEMHDR_MAGIC_FREE);
274
275 split = (shmemhdr *)((uint8_t *)(big + 1) + size1);
276 split->magic = SHMEMHDR_MAGIC_FREE;
277 split->size = big->size - size1 - sizeof(*split);
278 split->next = big->next;
279 split->prev = big;
280 split->next2 = big->next2;
281 split->prev2 = big->prev2;
282 split->psh = SHHEAP_POISON_NULL(0x54);
283 split->chunk = big->chunk;
284
285 if (big->next2)
286 big->next2->prev2 = split;
287 if (big->prev2)
288 big->prev2->next2 = split;
289 else
290 big->chunk->free_head = split;
291
292 big->magic = SHMEMHDR_MAGIC_USED;
293 big->next2 = big->prev2 = SHHEAP_POISON_NULL(0x41);
294
295 if (big->next)
296 big->next->prev = split;
297 big->next = split;
298 big->size = size1;
299
300 SHHEAP_CHECK_2();
301 return big;
302}
303
304/***
305 * Unlinks a free memory block.
306 * @param mem The block to unlink.
307 */
308static void shheap_unlink_free(shmemhdr *mem)
309{
310 if (mem->next2)
311 mem->next2->prev2 = mem->prev2;
312 if (mem->prev2)
313 mem->prev2->next2 = mem->next2;
314 else
315 mem->chunk->free_head = mem->next2;
316 mem->magic = SHMEMHDR_MAGIC_USED;
317 mem->next2 = mem->prev2 = SHHEAP_POISON_NULL(0x42);
318}
319
320#endif /* SHHEAP_IN_USE */
321
322
323/** free() */
324void sh_free(shinstance *psh, void *ptr)
325{
326#ifdef SHHEAP_IN_USE
327 shmemhdr *mem = (shmemhdr *)ptr - 1;
328 shmemhdr *right;
329 shmemhdr *left;
330 shmtxtmp tmp;
331
332 if (mem->magic != SHMEMHDR_MAGIC_USED)
333 {
334 SHHEAP_ASSERT(0);
335 return;
336 }
337
338 shmtx_enter(&g_sh_heap_mtx, &tmp);
339 SHHEAP_CHECK();
340
341 /* join right. */
342 right = mem->next;
343 if ( right
344 && right->magic == SHMEMHDR_MAGIC_FREE)
345 {
346 mem->next = right->next;
347 if (right->next)
348 right->next->prev = mem;
349
350 mem->next2 = right->next2;
351 if (right->next2)
352 right->next2->prev2 = mem;
353 mem->prev2 = right->prev2;
354 if (right->prev2)
355 mem->prev2->next2 = mem;
356 else
357 mem->chunk->free_head = mem;
358
359 mem->size += sizeof(*right) + right->size;
360 mem->magic = SHMEMHDR_MAGIC_FREE;
361 right->magic = ~SHMEMHDR_MAGIC_FREE;
362 mem->psh = SHHEAP_POISON_NULL(0x50);
363 SHHEAP_CHECK_2();
364 }
365
366 /* join left */
367 left = mem->prev;
368 if ( left
369 && left->magic == SHMEMHDR_MAGIC_FREE)
370 {
371 left->next = mem->next;
372 if (mem->next)
373 mem->next->prev = left;
374
375 if (mem->magic == SHMEMHDR_MAGIC_FREE)
376 {
377 SHHEAP_ASSERT(left->next2 == mem);
378 SHHEAP_ASSERT(mem->prev2 == left);
379 left->next2 = mem->next2;
380 if (mem->next2)
381 mem->next2->prev2 = left;
382 }
383
384 left->size += sizeof(*mem) + mem->size;
385 mem->magic = ~SHMEMHDR_MAGIC_USED;
386 left->psh = SHHEAP_POISON_NULL(0x51);
387 }
388
389 /* insert as free if necessary */
390 else if (mem->magic == SHMEMHDR_MAGIC_USED)
391 {
392 mem->prev2 = NULL;
393 mem->next2 = mem->chunk->free_head;
394 if (mem->chunk->free_head)
395 mem->chunk->free_head->prev2 = mem;
396 mem->chunk->free_head = mem;
397 mem->magic = SHMEMHDR_MAGIC_FREE;
398 mem->psh = SHHEAP_POISON_NULL(0x52);
399 }
400
401 SHHEAP_CHECK();
402 shmtx_leave(&g_sh_heap_mtx, &tmp);
403#else
404 if (ptr)
405 free(ptr);
406 (void)psh;
407#endif
408}
409
410/** malloc() */
411void *sh_malloc(shinstance *psh, size_t size)
412{
413#ifdef SHHEAP_IN_USE
414 shmemchunk *chunk;
415 shmemhdr *mem;
416 shmtxtmp tmp;
417
418 size = SHHEAP_ALIGN(size);
419 SHHEAP_ASSERT(size);
420 if (!size)
421 size = SHHEAP_ALIGN(1);
422
423 shmtx_enter(&g_sh_heap_mtx, &tmp);
424 SHHEAP_CHECK();
425
426
427 /* Search for fitting block */
428 mem = NULL;
429 chunk = g_sh_heap;
430 while (chunk)
431 {
432 mem = chunk->free_head;
433 while (mem && mem->size < size)
434 mem = mem->next2;
435 if (mem)
436 break;
437 chunk = chunk->next;
438 }
439 if (mem)
440 {
441 /* split it, or just unlink it? */
442 if (mem->size - size > sizeof(*mem) * 2)
443 mem = shheap_split(mem, size);
444 else
445 shheap_unlink_free(mem);
446 }
447 else
448 {
449 /* no block found, try grow the heap. */
450 mem = shheap_grow(size);
451 if (!mem)
452 {
453 shmtx_leave(&g_sh_heap_mtx, &tmp);
454 return NULL;
455 }
456 }
457
458 SHHEAP_CHECK();
459 shmtx_leave(&g_sh_heap_mtx, &tmp);
460
461 mem->psh = SHHEAP_POISON_PSH(psh, 0x53);
462
463 return mem + 1;
464
465#else
466 (void)psh;
467 return malloc(size);
468#endif
469}
470
471/** calloc() */
472void *sh_calloc(shinstance *psh, size_t num, size_t item_size)
473{
474#ifdef SHHEAP_IN_USE
475 size_t size = num * item_size;
476 void *pv = sh_malloc(psh, size);
477 if (pv)
478 pv = memset(pv, '\0', size);
479 return pv;
480#else
481 (void)psh;
482 return calloc(num, item_size);
483#endif
484}
485
486/** realloc() */
487void *sh_realloc(shinstance *psh, void *old, size_t new_size)
488{
489#ifdef SHHEAP_IN_USE
490 void *pv;
491 if (new_size)
492 {
493 if (old)
494 {
495 shmemhdr *hdr = (shmemhdr *)old - 1;
496 if (hdr->size < new_size)
497 {
498 void *pv = sh_malloc(psh, new_size);
499 if (pv)
500 {
501 memcpy(pv, old, hdr->size);
502 sh_free(psh, old);
503 }
504 }
505 else
506 pv = old;
507 }
508 else
509 pv = sh_malloc(psh, new_size);
510 }
511 else
512 {
513 sh_free(psh, old);
514 pv = NULL;
515 }
516 return pv;
517#else
518 return realloc(old, new_size);
519#endif
520}
521
522/** strdup() */
523char *sh_strdup(shinstance *psh, const char *string)
524{
525 size_t len = strlen(string);
526 char *ret = sh_malloc(psh, len + 1);
527 if (ret)
528 memcpy(ret, string, len + 1);
529 return ret;
530}
531
532
Note: See TracBrowser for help on using the repository browser.