summaryrefslogtreecommitdiff
path: root/user/umalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'user/umalloc.c')
-rw-r--r--user/umalloc.c90
1 files changed, 90 insertions, 0 deletions
diff --git a/user/umalloc.c b/user/umalloc.c
new file mode 100644
index 0000000..2092a32
--- /dev/null
+++ b/user/umalloc.c
@@ -0,0 +1,90 @@
+#include "kernel/types.h"
+#include "kernel/stat.h"
+#include "user/user.h"
+#include "kernel/param.h"
+
+// Memory allocator by Kernighan and Ritchie,
+// The C programming Language, 2nd ed. Section 8.7.
+
+typedef long Align;
+
+union header {
+ struct {
+ union header *ptr;
+ uint size;
+ } s;
+ Align x;
+};
+
+typedef union header Header;
+
+static Header base;
+static Header *freep;
+
+void
+free(void *ap)
+{
+ Header *bp, *p;
+
+ bp = (Header*)ap - 1;
+ for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
+ if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
+ break;
+ if(bp + bp->s.size == p->s.ptr){
+ bp->s.size += p->s.ptr->s.size;
+ bp->s.ptr = p->s.ptr->s.ptr;
+ } else
+ bp->s.ptr = p->s.ptr;
+ if(p + p->s.size == bp){
+ p->s.size += bp->s.size;
+ p->s.ptr = bp->s.ptr;
+ } else
+ p->s.ptr = bp;
+ freep = p;
+}
+
+static Header*
+morecore(uint nu)
+{
+ char *p;
+ Header *hp;
+
+ if(nu < 4096)
+ nu = 4096;
+ p = sbrk(nu * sizeof(Header));
+ if(p == (char*)-1)
+ return 0;
+ hp = (Header*)p;
+ hp->s.size = nu;
+ free((void*)(hp + 1));
+ return freep;
+}
+
+void*
+malloc(uint nbytes)
+{
+ Header *p, *prevp;
+ uint nunits;
+
+ nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
+ if((prevp = freep) == 0){
+ base.s.ptr = freep = prevp = &base;
+ base.s.size = 0;
+ }
+ for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
+ if(p->s.size >= nunits){
+ if(p->s.size == nunits)
+ prevp->s.ptr = p->s.ptr;
+ else {
+ p->s.size -= nunits;
+ p += p->s.size;
+ p->s.size = nunits;
+ }
+ freep = prevp;
+ return (void*)(p + 1);
+ }
+ if(p == freep)
+ if((p = morecore(nunits)) == 0)
+ return 0;
+ }
+}