commit ee643349eedf014d5275bd38a4c7ffcf5719e148
parent 9a4612256c7e1642b4fcf860c81704aea4b5b00c
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date: Wed, 13 Sep 2017 16:19:29 +0100
[lib] Add generic arena allocator
At this moment we are using a specific arena allocator in cc2 for nodes,
but there are other places in the code where an arena allocator can be
used, so it is a good idea to have a generic implementation.
Diffstat:
4 files changed, 126 insertions(+), 3 deletions(-)
diff --git a/cc2/target/qbe/code.c b/cc2/target/qbe/code.c
@@ -13,7 +13,7 @@ static char sccsid[] = "@(#) ./cc2/arch/qbe/code.c";
static void binary(void), unary(void), store(void), jmp(void), ret(void),
branch(void), call(void), ecall(void), param(void),
- alloc(void), form2local(void), ldir(void), vastart(void),
+ asalloc(void), form2local(void), ldir(void), vastart(void),
vaarg(void);
static struct opdata {
@@ -146,7 +146,7 @@ static struct opdata {
[ASCALLEX] = {.fun = ecall, .txt = ", ...)"},
[ASPAR] = {.fun = param, .txt = "%s %s, "},
[ASPARE] = {.fun = param, .txt = "%s %s"},
- [ASALLOC] = {.fun = alloc},
+ [ASALLOC] = {.fun = asalloc},
[ASFORM] = {.fun = form2local},
[ASVSTAR] = {.fun = vastart},
@@ -516,7 +516,7 @@ vaarg(void)
}
static void
-alloc(void)
+asalloc(void)
{
Symbol *sym = pc->to.u.sym;
Type *tp = &sym->type;
diff --git a/inc/scc.h b/inc/scc.h
@@ -19,6 +19,20 @@ struct items {
unsigned n;
};
+typedef struct alloc Alloc;
+
+struct arena;
+union hdr;
+
+struct alloc {
+ size_t size;
+ size_t nmemb;
+ size_t padding;
+ struct arena *arena;
+ union hdr *freep;
+};
+
+
extern void die(const char *fmt, ...);
extern void dbg(const char *fmt, ...);
extern void newitem(struct items *items, char *item);
@@ -26,3 +40,7 @@ extern void *xmalloc(size_t size);
extern void *xcalloc(size_t nmemb, size_t size);
extern char *xstrdup(const char *s);
extern void *xrealloc(void *buff, register size_t size);
+extern Alloc *alloc(size_t size, size_t nmemb);
+extern void dealloc(Alloc *allocp);
+extern void *new(Alloc *allocp);
+extern void delete(Alloc *allocp, void *p);
diff --git a/lib/scc/alloc.c b/lib/scc/alloc.c
@@ -0,0 +1,104 @@
+static char sccsid[] = "@(#) ./lib/alloc.c";
+#include <stdlib.h>
+#include "../../inc/scc.h"
+
+/*
+ * This is the most pedantic piece of code that I have written
+ * in my life. The next union is used to enforce the aligmnet
+ * of the address returned by new(). A union has the aligment
+ * of the field with the biggest aligment. This union has all
+ * the types that we use in scc, and we round all the address
+ * to the aligment of this struct, so we can be sure that any
+ * pointer using that address will be safe. The field ap is
+ * in the union to be sure that struct pointers are included
+ * in the list, although they will have the same aligment or
+ * smaller than void *, but I wanted to be pedantic.
+ */
+union hdr {
+ union hdr *next;
+ struct arena *ap;
+ char c;
+ unsigned char uc;
+ int i;
+ short s;
+ long l;
+ long long ll;
+ float f;
+ double d;
+ long double ld;
+ void *vp;
+};
+
+struct arena {
+ struct arena *next;
+ union hdr *array;
+};
+
+static void
+newarena(Alloc *allocp)
+{
+ struct arena *ap;
+ union hdr *bp, *lim;
+ size_t unit, n = allocp->nmemb;
+
+ unit = (allocp->size-1) / sizeof(union hdr) + 1;
+ ap = xmalloc(sizeof(struct arena));
+ ap->array = xmalloc(unit * sizeof(union hdr) * n);
+
+ bp = ap->array;
+ for (lim = &bp[unit * (n-1)]; bp < lim; bp += unit)
+ bp->next = bp + unit;
+ bp->next = NULL;
+
+ ap->next = allocp->arena;
+ allocp->arena = ap;
+ allocp->freep = ap->array;
+}
+
+Alloc *
+alloc(size_t size, size_t nmemb)
+{
+ Alloc *allocp = xmalloc(sizeof(*allocp));
+
+ allocp->size = size;
+ allocp->nmemb = nmemb;
+ allocp->arena = NULL;
+ allocp->freep = NULL;
+
+ return allocp;
+}
+
+void
+dealloc(Alloc *allocp)
+{
+ struct arena *ap, *next;
+
+ for (ap = allocp->arena; ap; ap = next) {
+ next = ap->next;
+ free(ap->array);
+ free(ap);
+ }
+ free(allocp);
+}
+
+void *
+new(Alloc *allocp)
+{
+ union hdr *bp;
+
+ if (!allocp->freep)
+ newarena(allocp);
+ bp = allocp->freep;
+ allocp->freep = bp->next;
+
+ return bp;
+}
+
+void
+delete(Alloc *allocp, void *p)
+{
+ union hdr *bp = p;
+
+ bp->next = allocp->freep;
+ allocp->freep = bp;
+}
diff --git a/lib/scc/libdep.mk b/lib/scc/libdep.mk
@@ -5,3 +5,4 @@ LIB-OBJ = $(LIBDIR)/debug.o \
$(LIBDIR)/xmalloc.o \
$(LIBDIR)/xrealloc.o \
$(LIBDIR)/xstrdup.o \
+ $(LIBDIR)/alloc.o \
