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

Last change on this file since 2562 was 2416, checked in by bird, 15 years ago

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