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

Last change on this file since 2364 was 2308, checked in by bird, 17 years ago

kash: Fixed wrong assumption in sh_free.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 15.2 KB
Line 
1/* $Id: shheap.c 2308 2009-03-01 10:01:02Z 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# if K_OS == K_OS_WINDOWS
140/**
141 * Copies the heap into the child process.
142 *
143 * @returns 0 on success, -1 and errno on failure.
144 * @param hChild Handle to the child process.
145 */
146int shheap_fork_copy_to_child(void *hChild)
147{
148 shmemchunk *chunk;
149 shmtxtmp tmp;
150 int err = 0;
151
152 shmtx_enter(&g_sh_heap_mtx, &tmp);
153
154 for (chunk = g_sh_heap; chunk; chunk = chunk->next)
155 {
156 void *chld_chnk;
157
158 chld_chnk = (shmemchunk *)VirtualAllocEx(hChild, chunk, chunk->size,
159 MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
160 if (chld_chnk != chunk)
161 {
162 err = GetLastError();
163 fprintf(stderr, "shfork: VirtualAllocEx(,%p,%p,) -> %d\n", chunk, chunk->size, err);
164 break;
165 }
166
167 if (!WriteProcessMemory(hChild, chunk, chunk, chunk->size, NULL /* pNumberOfBytesWritten */))
168 {
169 err = GetLastError();
170 fprintf(stderr, "shfork: WriteProcessMemory(,%p,,%p,) -> %d\n", chunk, chunk->size, err);
171 break;
172 }
173 }
174
175 shmtx_leave(&g_sh_heap_mtx, &tmp);
176
177 if (!err)
178 return 0;
179 errno = EINVAL;
180 return -1;
181}
182# endif
183
184
185/**
186 * Checks a heap chunk.
187 * @param chunk The chunk to check.
188 */
189static void shheap_check_chunk(shmemchunk *chunk)
190{
191 size_t free_count;
192 struct shmemhdr *mem;
193 struct shmemhdr *prev;
194
195 SHHEAP_ASSERT(chunk->magic == SHMEMCHUNK_MAGIC);
196 SHHEAP_ASSERT(chunk->head);
197 SHHEAP_ASSERT(chunk->size == SHHEAP_CHUNK_ALIGN(chunk->size));
198
199 free_count = 0;
200 prev = NULL;
201 for (mem = chunk->head; mem; mem = mem->next)
202 {
203 size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
204 SHHEAP_ASSERT(mem->size == size);
205 SHHEAP_ASSERT(mem->prev == prev);
206 if (mem->magic == SHMEMHDR_MAGIC_FREE)
207 free_count++;
208 else
209 SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_USED);
210 prev = mem;
211 }
212
213 prev = NULL;
214 for (mem = chunk->free_head; mem; mem = mem->next2)
215 {
216 size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
217 SHHEAP_ASSERT(mem->size == size);
218 SHHEAP_ASSERT(mem->prev2 == prev);
219 SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_FREE);
220 free_count--;
221 prev = mem;
222 }
223 SHHEAP_ASSERT(free_count == 0);
224}
225
226/**
227 * Checks the heap.
228 */
229static void shheap_check(void)
230{
231 shmemchunk *chunk;
232 for (chunk = g_sh_heap; chunk; chunk = chunk->next)
233 shheap_check_chunk(chunk);
234}
235
236/**
237 * Grows the heap with another chunk carving out a block
238 *
239 * @returns Pointer to a used entry of size @a size1. NULL
240 * if we're out of memory
241 * @param size1 The size of the block to be returned (aligned).
242 */
243static shmemhdr *shheap_grow(size_t size1)
244{
245 shmemchunk *chunk;
246 shmemhdr *used;
247 shmemhdr *avail;
248 size_t chunk_size;
249
250 /* Calc the chunk size and allocate it. */
251 chunk_size = SHHEAP_ALIGN(size1) + SHHEAP_ALIGN(sizeof(*chunk)) + SHHEAP_ALIGN(sizeof(*used)) * 10;
252 if (chunk_size < SHHEAP_MIN_CHUNK)
253 chunk_size = SHHEAP_MIN_CHUNK;
254 else
255 chunk_size = SHHEAP_CHUNK_ALIGN(chunk_size);
256
257# if K_OS == K_OS_WINDOWS
258 chunk = (shmemchunk *)VirtualAlloc(NULL, chunk_size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
259# else
260 chunk = NULL;
261# endif
262
263 if (!chunk)
264 return NULL;
265
266 used = (shmemhdr *)((char *)chunk + SHHEAP_ALIGN(sizeof(*chunk)));
267 avail = (shmemhdr *)((char *)(used + 1) + size1);
268
269 used->magic = SHMEMHDR_MAGIC_USED;
270 used->size = size1;
271 used->next = avail;
272 used->prev = NULL;
273 used->next2 = SHHEAP_POISON_NULL(0x41);
274 used->prev2 = SHHEAP_POISON_NULL(0x41);
275 used->psh = NULL;
276 used->chunk = chunk;
277
278 avail->magic = SHMEMHDR_MAGIC_FREE;
279 avail->size = (char *)chunk + chunk_size - (char *)(avail + 1);
280 avail->next = NULL;
281 avail->prev = used;
282 avail->next2 = NULL;
283 avail->prev2 = NULL;
284 avail->psh = NULL;
285 avail->chunk = chunk;
286
287 chunk->head = used;
288 chunk->free_head = avail;
289 chunk->size = chunk_size;
290 chunk->magic = SHMEMCHUNK_MAGIC;
291 chunk->prev = NULL;
292 chunk->next = g_sh_heap;
293 if (g_sh_heap)
294 g_sh_heap->prev = chunk;
295 g_sh_heap = chunk;
296 chunk->padding0 = 0;
297 chunk->padding1 = 0;
298
299 SHHEAP_CHECK_2();
300 return used;
301}
302
303/***
304 * Splits a big memory block into two smaller, one with the
305 * size @a size1.
306 *
307 * The one with the given size is removed from the free list
308 * while the other one remains there.
309 *
310 * @returns The @a size1 sized block, NULL on failure.
311 * @param big The block that is too big.
312 * @param size1 The size of the block to be returned (aligned).
313 */
314static shmemhdr *shheap_split(shmemhdr *big, size_t size1)
315{
316 shmemhdr *split;
317 SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(*big)) == sizeof(*big));
318 SHHEAP_ASSERT(big->magic == SHMEMHDR_MAGIC_FREE);
319 SHHEAP_ASSERT(!big->next2 || big->next2->magic == SHMEMHDR_MAGIC_FREE);
320 SHHEAP_ASSERT(!big->prev2 || big->prev2->magic == SHMEMHDR_MAGIC_FREE);
321
322 split = (shmemhdr *)((uint8_t *)(big + 1) + size1);
323 split->magic = SHMEMHDR_MAGIC_FREE;
324 split->size = big->size - size1 - sizeof(*split);
325 split->next = big->next;
326 split->prev = big;
327 split->next2 = big->next2;
328 split->prev2 = big->prev2;
329 split->psh = SHHEAP_POISON_NULL(0x54);
330 split->chunk = big->chunk;
331
332 if (big->next2)
333 big->next2->prev2 = split;
334 if (big->prev2)
335 big->prev2->next2 = split;
336 else
337 big->chunk->free_head = split;
338
339 big->magic = SHMEMHDR_MAGIC_USED;
340 big->next2 = big->prev2 = SHHEAP_POISON_NULL(0x41);
341
342 if (big->next)
343 big->next->prev = split;
344 big->next = split;
345 big->size = size1;
346
347 SHHEAP_CHECK_2();
348 return big;
349}
350
351/***
352 * Unlinks a free memory block.
353 * @param mem The block to unlink.
354 */
355static void shheap_unlink_free(shmemhdr *mem)
356{
357 if (mem->next2)
358 mem->next2->prev2 = mem->prev2;
359 if (mem->prev2)
360 mem->prev2->next2 = mem->next2;
361 else
362 mem->chunk->free_head = mem->next2;
363 mem->magic = SHMEMHDR_MAGIC_USED;
364 mem->next2 = mem->prev2 = SHHEAP_POISON_NULL(0x42);
365}
366
367#endif /* SHHEAP_IN_USE */
368
369
370/** free() */
371void sh_free(shinstance *psh, void *ptr)
372{
373#ifdef SHHEAP_IN_USE
374 shmemhdr *mem = (shmemhdr *)ptr - 1;
375 shmemhdr *right;
376 shmemhdr *left;
377 shmtxtmp tmp;
378
379 if (mem->magic != SHMEMHDR_MAGIC_USED)
380 {
381 SHHEAP_ASSERT(0);
382 return;
383 }
384
385 shmtx_enter(&g_sh_heap_mtx, &tmp);
386 SHHEAP_CHECK();
387
388 /* join right. */
389 right = mem->next;
390 if ( right
391 && right->magic == SHMEMHDR_MAGIC_FREE)
392 {
393 mem->next = right->next;
394 if (right->next)
395 right->next->prev = mem;
396
397 mem->next2 = right->next2;
398 if (right->next2)
399 right->next2->prev2 = mem;
400 mem->prev2 = right->prev2;
401 if (right->prev2)
402 mem->prev2->next2 = mem;
403 else
404 mem->chunk->free_head = mem;
405
406 mem->size += sizeof(*right) + right->size;
407 mem->magic = SHMEMHDR_MAGIC_FREE;
408 right->magic = ~SHMEMHDR_MAGIC_FREE;
409 mem->psh = SHHEAP_POISON_NULL(0x50);
410 SHHEAP_CHECK_2();
411 }
412
413 /* join left */
414 left = mem->prev;
415 if ( left
416 && left->magic == SHMEMHDR_MAGIC_FREE)
417 {
418 left->next = mem->next;
419 if (mem->next)
420 mem->next->prev = left;
421
422 if (mem->magic == SHMEMHDR_MAGIC_FREE)
423 {
424 if (mem->next2)
425 mem->next2->prev2 = mem->prev2;
426 if (mem->prev2)
427 mem->prev2->next2 = mem->next2;
428 else
429 mem->chunk->free_head = mem->next2;
430 }
431
432 left->size += sizeof(*mem) + mem->size;
433 mem->magic = ~SHMEMHDR_MAGIC_USED;
434 left->psh = SHHEAP_POISON_NULL(0x51);
435 }
436
437 /* insert as free if necessary */
438 else if (mem->magic == SHMEMHDR_MAGIC_USED)
439 {
440 mem->prev2 = NULL;
441 mem->next2 = mem->chunk->free_head;
442 if (mem->chunk->free_head)
443 mem->chunk->free_head->prev2 = mem;
444 mem->chunk->free_head = mem;
445 mem->magic = SHMEMHDR_MAGIC_FREE;
446 mem->psh = SHHEAP_POISON_NULL(0x52);
447 }
448
449 SHHEAP_CHECK();
450 shmtx_leave(&g_sh_heap_mtx, &tmp);
451#else
452 if (ptr)
453 free(ptr);
454 (void)psh;
455#endif
456}
457
458/** malloc() */
459void *sh_malloc(shinstance *psh, size_t size)
460{
461#ifdef SHHEAP_IN_USE
462 shmemchunk *chunk;
463 shmemhdr *mem;
464 shmtxtmp tmp;
465
466 size = SHHEAP_ALIGN(size);
467 SHHEAP_ASSERT(size);
468 if (!size)
469 size = SHHEAP_ALIGN(1);
470
471 shmtx_enter(&g_sh_heap_mtx, &tmp);
472 SHHEAP_CHECK();
473
474
475 /* Search for fitting block */
476 mem = NULL;
477 chunk = g_sh_heap;
478 while (chunk)
479 {
480 mem = chunk->free_head;
481 while (mem && mem->size < size)
482 mem = mem->next2;
483 if (mem)
484 break;
485 chunk = chunk->next;
486 }
487 if (mem)
488 {
489 /* split it, or just unlink it? */
490 if (mem->size - size > sizeof(*mem) * 2)
491 mem = shheap_split(mem, size);
492 else
493 shheap_unlink_free(mem);
494 }
495 else
496 {
497 /* no block found, try grow the heap. */
498 mem = shheap_grow(size);
499 if (!mem)
500 {
501 shmtx_leave(&g_sh_heap_mtx, &tmp);
502 return NULL;
503 }
504 }
505
506 SHHEAP_CHECK();
507 shmtx_leave(&g_sh_heap_mtx, &tmp);
508
509 mem->psh = SHHEAP_POISON_PSH(psh, 0x53);
510
511 return mem + 1;
512
513#else
514 (void)psh;
515 return malloc(size);
516#endif
517}
518
519/** calloc() */
520void *sh_calloc(shinstance *psh, size_t num, size_t item_size)
521{
522#ifdef SHHEAP_IN_USE
523 size_t size = num * item_size;
524 void *pv = sh_malloc(psh, size);
525 if (pv)
526 pv = memset(pv, '\0', size);
527 return pv;
528#else
529 (void)psh;
530 return calloc(num, item_size);
531#endif
532}
533
534/** realloc() */
535void *sh_realloc(shinstance *psh, void *old, size_t new_size)
536{
537#ifdef SHHEAP_IN_USE
538 void *pv;
539 if (new_size)
540 {
541 if (old)
542 {
543 shmemhdr *hdr = (shmemhdr *)old - 1;
544 if (hdr->size < new_size)
545 {
546 pv = sh_malloc(psh, new_size);
547 if (pv)
548 {
549 memcpy(pv, old, hdr->size);
550 sh_free(psh, old);
551 }
552 }
553 else
554 pv = old;
555 }
556 else
557 pv = sh_malloc(psh, new_size);
558 }
559 else
560 {
561 sh_free(psh, old);
562 pv = NULL;
563 }
564 return pv;
565#else
566 return realloc(old, new_size);
567#endif
568}
569
570/** strdup() */
571char *sh_strdup(shinstance *psh, const char *string)
572{
573 size_t len = strlen(string);
574 char *ret = sh_malloc(psh, len + 1);
575 if (ret)
576 memcpy(ret, string, len + 1);
577 return ret;
578}
579
580
Note: See TracBrowser for help on using the repository browser.