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

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

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