source: trunk/src/kash/shheap.c

Last change on this file was 3477, checked in by bird, 5 years ago

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