1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
// Physical memory allocator, intended to allocate
// memory for user processes. Allocates in 4096-byte "pages".
// Free list is kept sorted and combines adjacent pages into
// long runs, to make it easier to allocate big segments.
// One reason the page size is 4k is that the x86 segment size
// granularity is 4k.
#include "param.h"
#include "types.h"
#include "defs.h"
#include "param.h"
#include "mmu.h"
#include "proc.h"
#include "spinlock.h"
struct spinlock kalloc_lock;
struct run {
struct run *next;
int len; // bytes
};
struct run *freelist;
// Initialize free list of physical pages.
// This code cheats by just considering one megabyte of
// pages after _end. Real systems would determine the
// amount of memory available in the system and use it all.
void
kinit(void)
{
extern int end;
uint mem;
char *start;
initlock(&kalloc_lock, "kalloc");
start = (char*) &end;
start = (char*) (((uint)start + PAGE) & ~(PAGE-1));
mem = 256; // assume computer has 256 pages of RAM
cprintf("mem = %d\n", mem * PAGE);
kfree(start, mem * PAGE);
}
// Free the len bytes of memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(len). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(char *v, int len)
{
struct run *r, *rend, **rp, *p, *pend;
if(len <= 0 || len % PAGE)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(v, 1, len);
acquire(&kalloc_lock);
p = (struct run*)v;
pend = (struct run*)(v + len);
for(rp=&freelist; (r=*rp) != 0 && r <= pend; rp=&r->next){
rend = (struct run*)((char*)r + r->len);
if(r <= p && p < rend)
panic("freeing free page");
if(pend == r){ // p next to r: replace r with p
p->len = len + r->len;
p->next = r->next;
*rp = p;
goto out;
}
if(rend == p){ // r next to p: replace p with r
r->len += len;
if(r->next && r->next == pend){ // r now next to r->next?
r->len += r->next->len;
r->next = r->next->next;
}
goto out;
}
}
// Insert p before r in list.
p->len = len;
p->next = r;
*rp = p;
out:
release(&kalloc_lock);
}
// Allocate n bytes of physical memory.
// Returns a kernel-segment pointer.
// Returns 0 if the memory cannot be allocated.
char*
kalloc(int n)
{
char *p;
struct run *r, **rr;
if(n % PAGE || n <= 0)
panic("kalloc");
acquire(&kalloc_lock);
rr = &freelist;
while(*rr){
r = *rr;
if(r->len == n){
*rr = r->next;
release(&kalloc_lock);
return (char*) r;
}
if(r->len > n){
r->len -= n;
p = (char*)r + r->len;
release(&kalloc_lock);
return p;
}
rr = &(*rr)->next;
}
release(&kalloc_lock);
cprintf("kalloc: out of memory\n");
return 0;
}
|
