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
9typedef long Align;
10
11union header {
12 struct {
13 union header *ptr;
14 uint size;
15 } s;
16 Align x;
17};
18
19typedef union header Header;
20
21static Header base;
22static Header *freep;
23
24void
25free(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
46static Header*
47morecore(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
63void*
64malloc(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