xref: /xv6-public/umalloc.c (revision 1a81e38b) 
1 #include "types.h"
2 #include "stat.h"
3 #include "user.h"
4 #include "param.h"
5 
6 // Memory allocator by Kernighan and Ritchie,
7 // The C programming Language, 2nd ed.  Section 8.7.
8 
9 typedef long Align;
10 
11 union header {
12   struct {
13     union header *ptr;
14     uint size;
15   } s;
16   Align x;
17 };
18 
19 typedef union header Header;
20 
21 static Header base;
22 static Header *freep;
23 
24 void
free(void * ap)25 free(void *ap)
26 {
27   Header *bp, *p;
28 
29   bp = (Header*)ap - 1;
30   for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
31     if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
32       break;
33   if(bp + bp->s.size == p->s.ptr){
34     bp->s.size += p->s.ptr->s.size;
35     bp->s.ptr = p->s.ptr->s.ptr;
36   } else
37     bp->s.ptr = p->s.ptr;
38   if(p + p->s.size == bp){
39     p->s.size += bp->s.size;
40     p->s.ptr = bp->s.ptr;
41   } else
42     p->s.ptr = bp;
43   freep = p;
44 }
45 
46 static Header*
morecore(uint nu)47 morecore(uint nu)
48 {
49   char *p;
50   Header *hp;
51 
52   if(nu < 4096)
53     nu = 4096;
54   p = sbrk(nu * sizeof(Header));
55   if(p == (char*)-1)
56     return 0;
57   hp = (Header*)p;
58   hp->s.size = nu;
59   free((void*)(hp + 1));
60   return freep;
61 }
62 
63 void*
malloc(uint nbytes)64 malloc(uint nbytes)
65 {
66   Header *p, *prevp;
67   uint nunits;
68 
69   nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
70   if((prevp = freep) == 0){
71     base.s.ptr = freep = prevp = &base;
72     base.s.size = 0;
73   }
74   for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
75     if(p->s.size >= nunits){
76       if(p->s.size == nunits)
77         prevp->s.ptr = p->s.ptr;
78       else {
79         p->s.size -= nunits;
80         p += p->s.size;
81         p->s.size = nunits;
82       }
83       freep = prevp;
84       return (void*)(p + 1);
85     }
86     if(p == freep)
87       if((p = morecore(nunits)) == 0)
88         return 0;
89   }
90 }
91