|
0
|
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
|
|
|
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*
|
|
|
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*
|
|
|
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 }
|
