summaryrefslogtreecommitdiffstats
path: root/src/kash/shheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/kash/shheap.c')
-rw-r--r--src/kash/shheap.c596
1 files changed, 596 insertions, 0 deletions
diff --git a/src/kash/shheap.c b/src/kash/shheap.c
new file mode 100644
index 0000000..cc481fb
--- /dev/null
+++ b/src/kash/shheap.c
@@ -0,0 +1,596 @@
+/* $Id: shheap.c 3477 2020-09-17 21:52:16Z bird $ */
+/** @file
+ * The shell memory heap methods.
+ */
+
+/*
+ * Copyright (c) 2009-2010 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
+ *
+ *
+ * This file is part of kBuild.
+ *
+ * kBuild is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * kBuild is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with kBuild; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ */
+
+/*******************************************************************************
+* Header Files *
+*******************************************************************************/
+#include "shheap.h"
+#include <string.h>
+#include <stdlib.h>
+#include "shinstance.h"
+
+#if K_OS == K_OS_WINDOWS && defined(SH_FORKED_MODE)
+# define SHHEAP_IN_USE
+#endif
+
+#ifdef SHHEAP_IN_USE
+# if K_OS == K_OS_WINDOWS
+# include <Windows.h>
+# else
+# include <unistd.h>
+# endif
+#endif
+
+
+/*******************************************************************************
+* Structures and Typedefs *
+*******************************************************************************/
+#ifdef SHHEAP_IN_USE
+/**
+ * heap memory block header.
+ */
+typedef struct shmemhdr
+{
+ size_t magic; /**< Magic value */
+ size_t size; /**< The block size */
+ struct shmemhdr *next; /**< Forward pointer. */
+ struct shmemhdr *prev; /**< Backward pointer. */
+ struct shmemhdr *next2; /**< Free/Shell list forward. */
+ struct shmemhdr *prev2; /**< Free/Shell list backward. */
+ struct shinstance *psh; /**< The shell who allocated it. */
+ struct shmemchunk *chunk; /**< The chunk who owns this. */
+} shmemhdr;
+
+/** Free block magic (shmemhdr::magic) */
+#define SHMEMHDR_MAGIC_FREE 0xbeeff00d
+/** Used block magic (shmemhdr::magic) */
+#define SHMEMHDR_MAGIC_USED 0xfeedface
+
+typedef struct shmemchunk
+{
+ struct shmemhdr *head; /**< Head of the block list. */
+ struct shmemhdr *free_head; /**< Head of the free list. */
+ struct shmemchunk *next; /**< The next block. */
+ struct shmemchunk *prev; /**< The previous block. */
+ size_t size; /**< Chunk size. */
+ size_t magic; /**< Magic value. */
+ size_t padding0;
+ size_t padding1;
+} shmemchunk;
+
+/** shmemchunk::magic */
+#define SHMEMCHUNK_MAGIC 0x12345678
+
+#endif /* K_OS_WINDOWS */
+
+
+/*******************************************************************************
+* Defined Constants And Macros *
+*******************************************************************************/
+#define SHHEAP_ALIGN(sz) (((sz) + 31) & ~(size_t)31)
+#define SHHEAP_CHUNK_ALIGN(sz) (((sz) + 0xffff) & ~(size_t)0xffff)
+#define SHHEAP_MIN_CHUNK 0x80000 //(1024*1024)
+#ifdef NDEBUG
+# define SHHEAP_CHECK() do { } while (0)
+# define SHHEAP_CHECK_2() do { } while (0)
+# define SHHEAP_ASSERT(expr) do { } while (0)
+# define SHHEAP_POISON_PSH(p,v) (p)
+# define SHHEAP_POISON_NULL(v) NULL
+#else
+# define SHHEAP_CHECK() shheap_check()
+# define SHHEAP_CHECK_2() shheap_check()
+# define SHHEAP_ASSERT(expr) kHlpAssert(expr)
+# define SHHEAP_POISON_PSH(p,v) ((shinstance *)(v))
+# define SHHEAP_POISON_NULL(v) ((void *)(v))
+#endif
+
+
+/*******************************************************************************
+* Global Variables *
+*******************************************************************************/
+#ifdef SHHEAP_IN_USE
+/** The heap lock. */
+static shmtx g_sh_heap_mtx;
+/** The heap.
+ * This is a list of chunks. */
+static shmemchunk *g_sh_heap;
+#endif
+
+
+int shheap_init(void *phead)
+{
+ int rc;
+#ifdef SHHEAP_IN_USE
+ SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(shmemhdr)) == sizeof(shmemhdr));
+ rc = shmtx_init(&g_sh_heap_mtx);
+ g_sh_heap = (shmemchunk *)phead; /* non-zero on fork() */
+#else
+ rc = 0;
+#endif
+ return rc;
+}
+
+#ifdef SHHEAP_IN_USE
+
+# if K_OS == K_OS_WINDOWS
+
+/**
+ * Get the head so the child can pass it to shheap_init() after fork().
+ *
+ * @returns g_sh_heap.
+ */
+void *shheap_get_head(void)
+{
+ return g_sh_heap;
+}
+
+/**
+ * Copies the heap into the child process.
+ *
+ * @returns 0 on success, -1 and errno on failure.
+ * @param hChild Handle to the child process.
+ */
+int shheap_fork_copy_to_child(void *hChild)
+{
+ shmemchunk *chunk;
+ shmtxtmp tmp;
+ int err = 0;
+
+ shmtx_enter(&g_sh_heap_mtx, &tmp);
+
+ for (chunk = g_sh_heap; chunk; chunk = chunk->next)
+ {
+ void *chld_chnk;
+
+ chld_chnk = (shmemchunk *)VirtualAllocEx(hChild, chunk, chunk->size,
+ MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
+ if (chld_chnk != chunk)
+ {
+ err = GetLastError();
+ fprintf(stderr, "shfork: VirtualAllocEx(,%p,%p,) -> %p/%d\n", chunk, chunk->size, chld_chnk, err);
+ break;
+ }
+
+ if (!WriteProcessMemory(hChild, chunk, chunk, chunk->size, NULL /* pNumberOfBytesWritten */))
+ {
+ err = GetLastError();
+ fprintf(stderr, "shfork: WriteProcessMemory(,%p,,%p,) -> %d\n", chunk, chunk->size, err);
+ break;
+ }
+ }
+
+ shmtx_leave(&g_sh_heap_mtx, &tmp);
+
+ if (!err)
+ return 0;
+ errno = EINVAL;
+ return -1;
+}
+
+# endif /* K_OS == K_OS_WINDOWS */
+
+/**
+ * Checks a heap chunk.
+ * @param chunk The chunk to check.
+ */
+static void shheap_check_chunk(shmemchunk *chunk)
+{
+ size_t free_count;
+ struct shmemhdr *mem;
+ struct shmemhdr *prev;
+
+ SHHEAP_ASSERT(chunk->magic == SHMEMCHUNK_MAGIC);
+ SHHEAP_ASSERT(chunk->head);
+ SHHEAP_ASSERT(chunk->size == SHHEAP_CHUNK_ALIGN(chunk->size));
+
+ free_count = 0;
+ prev = NULL;
+ for (mem = chunk->head; mem; mem = mem->next)
+ {
+ size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
+ SHHEAP_ASSERT(mem->size == size);
+ SHHEAP_ASSERT(mem->prev == prev);
+ if (mem->magic == SHMEMHDR_MAGIC_FREE)
+ free_count++;
+ else
+ SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_USED);
+ prev = mem;
+ }
+
+ prev = NULL;
+ for (mem = chunk->free_head; mem; mem = mem->next2)
+ {
+ size_t size = (mem->next ? (char *)mem->next : (char *)chunk + chunk->size) - (char *)(mem + 1);
+ SHHEAP_ASSERT(mem->size == size);
+ SHHEAP_ASSERT(mem->prev2 == prev);
+ SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_FREE);
+ free_count--;
+ prev = mem;
+ }
+ SHHEAP_ASSERT(free_count == 0);
+}
+
+/**
+ * Checks the heap.
+ */
+static void shheap_check(void)
+{
+ shmemchunk *chunk;
+ for (chunk = g_sh_heap; chunk; chunk = chunk->next)
+ shheap_check_chunk(chunk);
+}
+
+/**
+ * Grows the heap with another chunk carving out a block
+ *
+ * @returns Pointer to a used entry of size @a size1. NULL
+ * if we're out of memory
+ * @param size1 The size of the block to be returned (aligned).
+ */
+static shmemhdr *shheap_grow(size_t size1)
+{
+ shmemchunk *chunk;
+ shmemhdr *used;
+ shmemhdr *avail;
+ size_t chunk_size;
+
+ /* Calc the chunk size and allocate it. */
+ chunk_size = SHHEAP_ALIGN(size1) + SHHEAP_ALIGN(sizeof(*chunk)) + SHHEAP_ALIGN(sizeof(*used)) * 10;
+ if (chunk_size < SHHEAP_MIN_CHUNK)
+ chunk_size = SHHEAP_MIN_CHUNK;
+ else
+ chunk_size = SHHEAP_CHUNK_ALIGN(chunk_size);
+
+# if K_OS == K_OS_WINDOWS
+ chunk = (shmemchunk *)VirtualAlloc(NULL, chunk_size, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
+# else
+ chunk = NULL;
+# endif
+
+ if (!chunk)
+ return NULL;
+
+ used = (shmemhdr *)((char *)chunk + SHHEAP_ALIGN(sizeof(*chunk)));
+ avail = (shmemhdr *)((char *)(used + 1) + size1);
+
+ used->magic = SHMEMHDR_MAGIC_USED;
+ used->size = size1;
+ used->next = avail;
+ used->prev = NULL;
+ used->next2 = SHHEAP_POISON_NULL(0x41);
+ used->prev2 = SHHEAP_POISON_NULL(0x41);
+ used->psh = NULL;
+ used->chunk = chunk;
+
+ avail->magic = SHMEMHDR_MAGIC_FREE;
+ avail->size = (char *)chunk + chunk_size - (char *)(avail + 1);
+ avail->next = NULL;
+ avail->prev = used;
+ avail->next2 = NULL;
+ avail->prev2 = NULL;
+ avail->psh = NULL;
+ avail->chunk = chunk;
+
+ chunk->head = used;
+ chunk->free_head = avail;
+ chunk->size = chunk_size;
+ chunk->magic = SHMEMCHUNK_MAGIC;
+ chunk->prev = NULL;
+ chunk->next = g_sh_heap;
+ if (g_sh_heap)
+ g_sh_heap->prev = chunk;
+ g_sh_heap = chunk;
+ chunk->padding0 = 0;
+ chunk->padding1 = 0;
+
+ SHHEAP_CHECK_2();
+ return used;
+}
+
+/***
+ * Splits a big memory block into two smaller, one with the
+ * size @a size1.
+ *
+ * The one with the given size is removed from the free list
+ * while the other one remains there.
+ *
+ * @returns The @a size1 sized block, NULL on failure.
+ * @param big The block that is too big.
+ * @param size1 The size of the block to be returned (aligned).
+ */
+static shmemhdr *shheap_split(shmemhdr *big, size_t size1)
+{
+ shmemhdr *split;
+ SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(*big)) == sizeof(*big));
+ SHHEAP_ASSERT(big->magic == SHMEMHDR_MAGIC_FREE);
+ SHHEAP_ASSERT(!big->next2 || big->next2->magic == SHMEMHDR_MAGIC_FREE);
+ SHHEAP_ASSERT(!big->prev2 || big->prev2->magic == SHMEMHDR_MAGIC_FREE);
+
+ split = (shmemhdr *)((uint8_t *)(big + 1) + size1);
+ split->magic = SHMEMHDR_MAGIC_FREE;
+ split->size = big->size - size1 - sizeof(*split);
+ split->next = big->next;
+ split->prev = big;
+ split->next2 = big->next2;
+ split->prev2 = big->prev2;
+ split->psh = SHHEAP_POISON_NULL(0x54);
+ split->chunk = big->chunk;
+
+ if (big->next2)
+ big->next2->prev2 = split;
+ if (big->prev2)
+ big->prev2->next2 = split;
+ else
+ big->chunk->free_head = split;
+
+ big->magic = SHMEMHDR_MAGIC_USED;
+ big->next2 = big->prev2 = SHHEAP_POISON_NULL(0x41);
+
+ if (big->next)
+ big->next->prev = split;
+ big->next = split;
+ big->size = size1;
+
+ SHHEAP_CHECK_2();
+ return big;
+}
+
+/***
+ * Unlinks a free memory block.
+ * @param mem The block to unlink.
+ */
+static void shheap_unlink_free(shmemhdr *mem)
+{
+ if (mem->next2)
+ mem->next2->prev2 = mem->prev2;
+ if (mem->prev2)
+ mem->prev2->next2 = mem->next2;
+ else
+ mem->chunk->free_head = mem->next2;
+ mem->magic = SHMEMHDR_MAGIC_USED;
+ mem->next2 = mem->prev2 = SHHEAP_POISON_NULL(0x42);
+}
+
+#endif /* SHHEAP_IN_USE */
+
+
+/** free() */
+void sh_free(shinstance *psh, void *ptr)
+{
+#ifdef SHHEAP_IN_USE
+ shmemhdr *mem;
+ shmemhdr *right;
+ shmemhdr *left;
+ shmtxtmp tmp;
+
+ if (ptr)
+ mem = (shmemhdr *)ptr - 1;
+ else
+ return;
+
+ if (mem->magic != SHMEMHDR_MAGIC_USED)
+ {
+ SHHEAP_ASSERT(0);
+ return;
+ }
+
+ shmtx_enter(&g_sh_heap_mtx, &tmp);
+ SHHEAP_CHECK();
+
+ /* join right. */
+ right = mem->next;
+ if ( right
+ && right->magic == SHMEMHDR_MAGIC_FREE)
+ {
+ mem->next = right->next;
+ if (right->next)
+ right->next->prev = mem;
+
+ mem->next2 = right->next2;
+ if (right->next2)
+ right->next2->prev2 = mem;
+ mem->prev2 = right->prev2;
+ if (right->prev2)
+ mem->prev2->next2 = mem;
+ else
+ mem->chunk->free_head = mem;
+
+ mem->size += sizeof(*right) + right->size;
+ mem->magic = SHMEMHDR_MAGIC_FREE;
+ right->magic = ~SHMEMHDR_MAGIC_FREE;
+ mem->psh = SHHEAP_POISON_NULL(0x50);
+ SHHEAP_CHECK_2();
+ }
+
+ /* join left */
+ left = mem->prev;
+ if ( left
+ && left->magic == SHMEMHDR_MAGIC_FREE)
+ {
+ left->next = mem->next;
+ if (mem->next)
+ mem->next->prev = left;
+
+ if (mem->magic == SHMEMHDR_MAGIC_FREE)
+ {
+ if (mem->next2)
+ mem->next2->prev2 = mem->prev2;
+ if (mem->prev2)
+ mem->prev2->next2 = mem->next2;
+ else
+ mem->chunk->free_head = mem->next2;
+ }
+
+ left->size += sizeof(*mem) + mem->size;
+ mem->magic = ~SHMEMHDR_MAGIC_USED;
+ left->psh = SHHEAP_POISON_NULL(0x51);
+ }
+
+ /* insert as free if necessary */
+ else if (mem->magic == SHMEMHDR_MAGIC_USED)
+ {
+ mem->prev2 = NULL;
+ mem->next2 = mem->chunk->free_head;
+ if (mem->chunk->free_head)
+ mem->chunk->free_head->prev2 = mem;
+ mem->chunk->free_head = mem;
+ mem->magic = SHMEMHDR_MAGIC_FREE;
+ mem->psh = SHHEAP_POISON_NULL(0x52);
+ }
+
+ SHHEAP_CHECK();
+ shmtx_leave(&g_sh_heap_mtx, &tmp);
+#else
+ if (ptr)
+ free(ptr);
+ (void)psh;
+#endif
+}
+
+/** malloc() */
+void *sh_malloc(shinstance *psh, size_t size)
+{
+#ifdef SHHEAP_IN_USE
+ shmemchunk *chunk;
+ shmemhdr *mem;
+ shmtxtmp tmp;
+
+ size = SHHEAP_ALIGN(size);
+ SHHEAP_ASSERT(size);
+ if (!size)
+ size = SHHEAP_ALIGN(1);
+
+ shmtx_enter(&g_sh_heap_mtx, &tmp);
+ SHHEAP_CHECK();
+
+
+ /* Search for fitting block */
+ mem = NULL;
+ chunk = g_sh_heap;
+ while (chunk)
+ {
+ mem = chunk->free_head;
+ while (mem && mem->size < size)
+ mem = mem->next2;
+ if (mem)
+ break;
+ chunk = chunk->next;
+ }
+ if (mem)
+ {
+ /* split it, or just unlink it? */
+ if (mem->size - size > sizeof(*mem) * 2)
+ mem = shheap_split(mem, size);
+ else
+ shheap_unlink_free(mem);
+ }
+ else
+ {
+ /* no block found, try grow the heap. */
+ mem = shheap_grow(size);
+ if (!mem)
+ {
+ shmtx_leave(&g_sh_heap_mtx, &tmp);
+ return NULL;
+ }
+ }
+
+ SHHEAP_CHECK();
+ shmtx_leave(&g_sh_heap_mtx, &tmp);
+
+ mem->psh = SHHEAP_POISON_PSH(psh, 0x53);
+
+ return mem + 1;
+
+#else
+ (void)psh;
+ return malloc(size);
+#endif
+}
+
+/** calloc() */
+void *sh_calloc(shinstance *psh, size_t num, size_t item_size)
+{
+#ifdef SHHEAP_IN_USE
+ size_t size = num * item_size;
+ void *pv = sh_malloc(psh, size);
+ if (pv)
+ pv = memset(pv, '\0', size);
+ return pv;
+#else
+ (void)psh;
+ return calloc(num, item_size);
+#endif
+}
+
+/** realloc() */
+void *sh_realloc(shinstance *psh, void *old, size_t new_size)
+{
+#ifdef SHHEAP_IN_USE
+ void *pv;
+ if (new_size)
+ {
+ if (old)
+ {
+ shmemhdr *hdr = (shmemhdr *)old - 1;
+ if (hdr->size < new_size)
+ {
+ pv = sh_malloc(psh, new_size);
+ if (pv)
+ {
+ memcpy(pv, old, hdr->size);
+ sh_free(psh, old);
+ }
+ }
+ else
+ pv = old;
+ }
+ else
+ pv = sh_malloc(psh, new_size);
+ }
+ else
+ {
+ sh_free(psh, old);
+ pv = NULL;
+ }
+ return pv;
+#else
+ return realloc(old, new_size);
+#endif
+}
+
+/** strdup() */
+char *sh_strdup(shinstance *psh, const char *string)
+{
+ size_t len = strlen(string);
+ char *ret = sh_malloc(psh, len + 1);
+ if (ret)
+ memcpy(ret, string, len + 1);
+ return ret;
+}
+
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-18 00:56:09 +0000