scripts

commit 57cede2e1a4902f3833af79d1330160686c215dd
parent e7299d91751363b8eefe9256f7f5ec86797a4ec9
Author: sin <sin@2f30.org>
Date:   Thu,  1 Aug 2013 15:04:00 +0100

Only free `oldp' if it is non-NULL

Diffstat:
M
random/alloc.c
 | 
2
+-
A
random/rballoc.c
 | 
243
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 244 insertions(+), 1 deletion(-)
diff --git a/random/alloc.c b/random/alloc.c
@@ -92,7 +92,7 @@ realloc(void *oldp, size_t nbytes)
 	size_t n;
 	long i;
 
-	if (!nbytes) {
+	if (!nbytes && oldp) {
 		free(oldp);
 		return NULL;
 	}
diff --git a/random/rballoc.c b/random/rballoc.c
@@ -0,0 +1,243 @@
+#include <sys/mman.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include "tree.h"
+
+enum { PAGESIZE = 4096 };
+
+struct node {
+	void *buf;
+	size_t siz;
+	RB_ENTRY(node) entry;
+};
+
+RB_HEAD(free_tree, node) ft = RB_INITIALIZER(&ft);
+RB_HEAD(alloc_tree, node) at = RB_INITIALIZER(&at);
+
+static int ft_cmp(struct node *a, struct node *b);
+RB_PROTOTYPE(free_tree, node, entry, ft_cmp);
+
+static int at_cmp(struct node *a, struct node *b);
+RB_PROTOTYPE(alloc_tree, node, entry, at_cmp);
+
+RB_GENERATE(free_tree, node, entry, ft_cmp);
+/* These are ordered by `siz' */
+static int
+ft_cmp(struct node *a, struct node *b)
+{
+	if (a->siz < b->siz)
+		return -1;
+	if (a->siz > b->siz)
+		return 1;
+	return 0;
+}
+
+RB_GENERATE(alloc_tree, node, entry, at_cmp);
+/* These are ordered by address */
+static int
+at_cmp(struct node *a, struct node *b)
+{
+	if (a->buf < b->buf)
+		return -1;
+	if (a->buf > b->buf)
+		return 1;
+	return 0;
+}
+
+static void
+dump_alloc_tree(void)
+{
+	struct node *n;
+
+	RB_FOREACH(n, alloc_tree, &at)
+		fprintf(stderr, "%s: buf: %p, size: %zu\n",
+			__func__, n->buf, n->siz);
+}
+
+static void
+dump_free_tree(void)
+{
+	struct node *n;
+
+	RB_FOREACH(n, free_tree, &ft)
+		fprintf(stderr, "%s: buf: %p, size: %zu\n",
+			__func__, n->buf, n->siz);
+}
+
+static void *
+alloc_object(size_t siz)
+{
+	void *p;
+
+	p = mmap(0, siz, PROT_READ | PROT_WRITE,
+		 MAP_PRIVATE | MAP_ANON, -1, 0);
+	if (p == MAP_FAILED)
+		return NULL;
+	return p;
+}
+
+static void
+free_object(void *p, size_t siz)
+{
+	munmap(p, siz);
+}
+
+static void *
+mmap_pages(size_t siz)
+{
+	void *addr;
+
+	if (siz % PAGESIZE)
+		siz = (siz + PAGESIZE) & ~(PAGESIZE - 1);
+
+	addr = mmap(0, siz, PROT_READ | PROT_WRITE,
+		    MAP_PRIVATE | MAP_ANON, -1, 0);
+	if (addr == MAP_FAILED)
+		return NULL;
+	return addr;
+}
+
+void *
+malloc(size_t siz)
+{
+	struct node n, *an, *res;
+	void *p;
+
+	if (!siz)
+		return NULL;
+	/* Lookup in the free tree for a block greater
+	 * than or equal to `siz' bytes */
+	n.siz = siz;
+	res = RB_NFIND(free_tree, &ft, &n);
+	if (!res) {
+		/* No available free block, create a new block
+		 * and add it to the alloc tree */
+		an = alloc_object(sizeof(*an));
+		if (!an)
+			return NULL;
+		p = mmap_pages(siz);
+		if (!p) {
+			free_object(an, sizeof(*an));
+			return NULL;
+		}
+		an->buf = p;
+		an->siz = siz;
+		RB_INSERT(alloc_tree, &at, an);
+		return an->buf;
+	}
+	an = RB_REMOVE(free_tree, &ft, res);
+	RB_INSERT(alloc_tree, &at, an);
+	return an->buf;
+}
+
+void *
+realloc(void *oldp, size_t siz)
+{
+	struct node n, *res;
+	void *p;
+
+	if (!oldp)
+		return malloc(siz);
+
+	if (!siz && oldp) {
+		free(oldp);
+		return NULL;
+	}
+
+	n.buf = oldp;
+	/* Search the alloc tree for an allocation starting
+	 * at address `oldp' */
+	res = RB_FIND(alloc_tree, &at, &n);
+	if (res) {
+		p = malloc(siz);
+		if (!p)
+			return NULL;
+		memcpy(p, res->buf, siz < res->siz ? siz : res->siz);
+		free(res->buf);
+		return p;
+	}
+	return NULL;
+}
+
+void *
+calloc(size_t nmemb, size_t siz)
+{
+	void *p;
+
+	p = malloc(nmemb * siz);
+	if (!p)
+		return NULL;
+	memset(p, 0, nmemb * siz);
+	return p;
+}
+
+void
+free(void *p)
+{
+	struct node n, *fn, *res;
+
+	if (!p)
+		return;
+	n.buf = p;
+	res = RB_FIND(alloc_tree, &at, &n);
+	/* Lookup this allocation in the alloc tree.
+	 * If it is located, remove it from the alloc tree
+	 * and insert it in the free tree. */
+	if (res) {
+		fn = RB_REMOVE(alloc_tree, &at, res);
+		RB_INSERT(free_tree, &ft, fn);
+	}
+}
+
+void
+cfree(void *p)
+{
+	free(p);
+}
+
+int
+posix_memalign(void **memptr, size_t align, size_t size)
+{
+	void *mem;
+
+	if (((align - 1) & align))
+		return EINVAL;
+	if (align < sizeof(void *))
+		return EINVAL;
+
+	if (PAGESIZE % align) {
+		fprintf(stderr, "%s: %zu alignment not supported!\n",
+			__func__, align);
+		abort();
+	}
+
+	mem = malloc(size);
+	if (!mem)
+		return ENOMEM;
+
+	*memptr = mem;
+	return 0;
+}
+
+size_t
+malloc_usable_size(void *p)
+{
+	struct node n, *res;
+
+	if (!p)
+		return 0;
+	n.buf = p;
+	res = RB_FIND(alloc_tree, &at, &n);
+	if (res)
+		return res->siz;
+	return 0;
+}
+
+size_t
+malloc_size(void *p)
+{
+	return malloc_usable_size(p);
+}