commit 2f4b50a01e322ba30cdf2fb15d62abc12800e773
parent 59165d9e6a8a1c8aa7b65d0b50976cd71cd7c788
Author: Quentin Rameau <quinq@fifth.space>
Date: Fri, 3 Mar 2017 18:24:41 +0100
[libc] add malloc, calloc, realloc, free
Diffstat:
9 files changed, 250 insertions(+), 1 deletion(-)
diff --git a/libc/include/bits/amd64-sysv/arch/stdlib.h b/libc/include/bits/amd64-sysv/arch/stdlib.h
@@ -12,3 +12,5 @@ typedef unsigned long size_t;
typedef int wchar_t;
#define _WCHAR_T
#endif
+
+#define _ALIGNTYPE long double
diff --git a/libc/include/bits/i386-sysv/arch/stdlib.h b/libc/include/bits/i386-sysv/arch/stdlib.h
@@ -12,3 +12,5 @@ typedef unsigned long size_t;
typedef int wchar_t;
#define _WCHAR_T
#endif
+
+#define _ALIGNTYPE long double
diff --git a/libc/include/bits/qbe/arch/stdlib.h b/libc/include/bits/qbe/arch/stdlib.h
@@ -12,3 +12,5 @@ typedef unsigned long size_t;
typedef int wchar_t;
#define _WCHAR_T
#endif
+
+#define _ALIGNTYPE long double
diff --git a/libc/include/bits/z80/arch/stdlib.h b/libc/include/bits/z80/arch/stdlib.h
@@ -12,3 +12,5 @@ typedef unsigned size_t;
typedef long wchar_t;
#define _WCHAR_T
#endif
+
+#define _ALIGNTYPE int
diff --git a/libc/src/Makefile b/libc/src/Makefile
@@ -11,7 +11,8 @@ LIBCOBJ = assert.o strcpy.o strcmp.o strlen.o strchr.o \
isgraph.o islower.o isprint.o ispunct.o isspace.o isupper.o \
isxdigit.o toupper.o tolower.o ctype.o setlocale.o \
localeconv.o atoi.o atexit.o exit.o \
- printf.o fprintf.o vfprintf.o
+ printf.o fprintf.o vfprintf.o \
+ realloc.o calloc.o malloc.o
all: libc.a
diff --git a/libc/src/calloc.c b/libc/src/calloc.c
@@ -0,0 +1,19 @@
+/* See LICENSE file for copyright and license details. */
+
+#include <stdlib.h>
+#include <string.h>
+
+void *
+calloc(size_t nmemb, size_t size)
+{
+ size_t nbytes;
+ void *mem;
+
+ if (!nmemb || !size || nmemb > (size_t)-1/size)
+ return NULL;
+
+ nbytes = nmemb * size;
+ if ((mem = malloc(nbytes)) == NULL)
+ return NULL;
+ return memset(mem, 0, nbytes);
+}
diff --git a/libc/src/malloc.c b/libc/src/malloc.c
@@ -0,0 +1,134 @@
+/* See LICENSE file for copyright and license details. */
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+#include "malloc.h"
+
+extern void *_sbrk(intptr_t increment);
+
+static Header base = { .h.next = &base };
+static Header *freep = &base;
+
+/*
+ * Run over the free list looking for the nearest previous
+ * block. There are two possible results: end of the list
+ * or an intermediary block.
+ */
+void *
+_prevchunk(Header *hp)
+{
+ Header *p;
+
+ for (p = freep; ;p = p->h.next) {
+ /* hp between p and p->h.next? */
+ if (p < hp && hp < p->h.next)
+ break;
+ /* p before hp and hp at the end of list? */
+ if (p->h.next <= p && (hp < p->h.next || hp > p))
+ break;
+ }
+ return p;
+}
+
+/*
+ * Get the previous block and try to merge
+ * with next and previous blocks
+ */
+void
+free(void *mem)
+{
+ Header *hp, *prev;
+
+ if (!mem)
+ return;
+
+ hp = (Header *) mem - 1;
+ prev = _prevchunk(hp);
+
+ /* join to next */
+ if (hp + hp->h.size == prev->h.next) {
+ hp->h.size += prev->h.next->h.size;
+ hp->h.next = prev->h.next->h.next;
+ } else {
+ hp->h.next = prev->h.next;
+ }
+
+ /* join to previous */
+ if (prev + prev->h.size == hp) {
+ prev->h.size += hp->h.size;
+ prev->h.next = hp->h.next;
+ } else {
+ prev->h.next = hp;
+ }
+
+ freep = prev;
+}
+
+static Header *
+morecore(size_t nunits)
+{
+ char *rawmem;
+ Header *hp;
+
+ if (nunits < NALLOC)
+ nunits = NALLOC;
+
+ rawmem = _sbrk(nunits * sizeof(Header));
+ if (rawmem == (void *)-1)
+ return NULL;
+
+ hp = (Header*)rawmem;
+ hp->h.size = nunits;
+
+ /* integrate new memory into the list */
+ free(hp + 1);
+
+ return freep;
+}
+
+/*
+ * Run over the list of free blocks trying to find a block
+ * big enough for nbytes. If the block fit perfectly with
+ * the required size then we only have to unlink
+ * the block. Otherwise we have to split the block and
+ * return the right part. If we run over the full list
+ * without a fit then we have to require more memory
+ *
+ * ______________________________________
+ * ___________./______________________________________\_____
+ * ...| in | | | in | |.....| in | | | |....
+ * ...| use | | | use | |.....| use | | | |....
+ * ___|______|___|.____|_____|._|_____|______|._|.___|.|____
+ * \__/ \_________/ \_____________/ \/ \__/
+ */
+void *
+malloc(size_t nbytes)
+{
+ Header *cur, *prev;
+ size_t nunits;
+
+ /* 1 unit for header plus enough units to fit nbytes */
+ nunits = (nbytes+sizeof(Header)-1) / sizeof(Header) + 1;
+
+ for (prev = freep; ; prev = cur) {
+ cur = prev->h.next;
+ if (cur->h.size >= nunits) {
+ if (cur->h.size == nunits) {
+ prev->h.next = cur->h.next;
+ } else {
+ cur->h.size -= nunits;
+ cur += cur->h.size;
+ cur->h.size = nunits;
+ }
+ freep = prev;
+ return cur + 1;
+ }
+
+ if (cur == freep) {
+ if ((cur = morecore(nunits)) == NULL)
+ return NULL;
+ }
+ }
+}
diff --git a/libc/src/malloc.h b/libc/src/malloc.h
@@ -0,0 +1,18 @@
+/* See LICENSE file for copyright and license details. */
+
+#include <stdlib.h>
+
+/* minimum amount of required units */
+#define NALLOC 10000
+
+typedef union header Header;
+union header {
+ struct hdr {
+ Header *next;
+ size_t size;
+ } h;
+ /* most restrictive type fixes the union size for alignment */
+ _ALIGNTYPE most;
+};
+
+extern void *_prevchunk(Header *hp);
diff --git a/libc/src/realloc.c b/libc/src/realloc.c
@@ -0,0 +1,69 @@
+/* See LICENSE file for copyright and license details. */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "malloc.h"
+
+void *
+realloc(void *ptr, size_t nbytes)
+{
+ Header *oh, *prev, *next, *new;
+ size_t nunits, avail, onbytes, n;
+
+ if (!nbytes)
+ return NULL;
+
+ if (!ptr)
+ return malloc(nbytes);
+
+ nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
+ oh = (Header*)ptr - 1;
+
+ if (oh->h.size == nunits)
+ return ptr;
+
+ new = oh + nunits;
+
+ if (nunits < oh->h.size - 1) {
+ new->h.size = oh->h.size - nunits;
+ oh->h.size = nunits;
+ free(new + 1);
+ return oh;
+ }
+
+ prev = _prevchunk(oh);
+
+ if (oh + oh->h.size == prev->h.next) {
+ /*
+ * if there is free space adjacent
+ * to the current memory
+ */
+ next = prev->h.next;
+ avail = oh->h.size + next->h.size;
+
+ if (avail == nunits) {
+ oh->h.size = nunits;
+ prev->h.next = next->h.next;
+ return oh;
+ }
+
+ if (avail > nunits) {
+ oh->h.size = nunits;
+ prev->h.next = new;
+ new->h.next = next;
+ new->h.size = avail - nunits;
+ return oh;
+ }
+ }
+
+ onbytes = (oh->h.size - 1) * sizeof(Header);
+ if ((new = malloc(nbytes)) == NULL)
+ return NULL;
+
+ n = (onbytes > nbytes) ? nbytes : onbytes;
+ memcpy(new, ptr, n);
+ free(ptr);
+
+ return new;
+}
