scoutos / prex-0.9.0 / sys / mem / page.c @ 03e9c04a
History | View | Annotate | Download (7.22 KB)
1 |
/*-
|
---|---|
2 |
* Copyright (c) 2005-2009, Kohsuke Ohtani
|
3 |
* All rights reserved.
|
4 |
*
|
5 |
* Redistribution and use in source and binary forms, with or without
|
6 |
* modification, are permitted provided that the following conditions
|
7 |
* are met:
|
8 |
* 1. Redistributions of source code must retain the above copyright
|
9 |
* notice, this list of conditions and the following disclaimer.
|
10 |
* 2. Redistributions in binary form must reproduce the above copyright
|
11 |
* notice, this list of conditions and the following disclaimer in the
|
12 |
* documentation and/or other materials provided with the distribution.
|
13 |
* 3. Neither the name of the author nor the names of any co-contributors
|
14 |
* may be used to endorse or promote products derived from this software
|
15 |
* without specific prior written permission.
|
16 |
*
|
17 |
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
|
18 |
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
19 |
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
20 |
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
|
21 |
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
22 |
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
23 |
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
24 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
25 |
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
26 |
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
27 |
* SUCH DAMAGE.
|
28 |
*/
|
29 |
|
30 |
/*
|
31 |
* page.c - physical page allocator
|
32 |
*/
|
33 |
|
34 |
/*
|
35 |
* Simple list-based page allocator:
|
36 |
*
|
37 |
* When the remaining page is exhausted, what should we do ?
|
38 |
* If the system can stop with panic() here, the error check of
|
39 |
* many portions in kernel is not necessary, and kernel code can
|
40 |
* become more simple. But, in general, even if a page is
|
41 |
* exhausted, a kernel can not be stopped but it should return an
|
42 |
* error and continue processing. If the memory becomes short
|
43 |
* during boot time, kernel and drivers can use panic() in that
|
44 |
* case.
|
45 |
*/
|
46 |
|
47 |
#include <kernel.h> |
48 |
#include <page.h> |
49 |
#include <sched.h> |
50 |
#include <hal.h> |
51 |
|
52 |
/*
|
53 |
* The page structure is put on the head of the first page of
|
54 |
* each free block.
|
55 |
*/
|
56 |
struct page {
|
57 |
struct page *next;
|
58 |
struct page *prev;
|
59 |
vsize_t size; /* number of bytes of this block */
|
60 |
}; |
61 |
|
62 |
static struct page page_head; /* first free block */ |
63 |
static psize_t total_size; /* size of memory in the system */ |
64 |
static psize_t used_size; /* current used size */ |
65 |
static psize_t bootdisk_size; /* size of the boot disk */ |
66 |
|
67 |
/*
|
68 |
* page_alloc - allocate continuous pages of the specified size.
|
69 |
*
|
70 |
* This routine returns the physical address of a new free page
|
71 |
* block, or returns NULL on failure. The requested size is
|
72 |
* automatically round up to the page boundary. The allocated
|
73 |
* memory is _not_ filled with 0.
|
74 |
*/
|
75 |
paddr_t |
76 |
page_alloc(psize_t psize) |
77 |
{ |
78 |
struct page *blk, *tmp;
|
79 |
vsize_t size; |
80 |
|
81 |
ASSERT(psize != 0);
|
82 |
|
83 |
sched_lock(); |
84 |
|
85 |
/*
|
86 |
* Find the free block that has enough size.
|
87 |
*/
|
88 |
size = round_page(psize); |
89 |
blk = &page_head; |
90 |
do {
|
91 |
blk = blk->next; |
92 |
if (blk == &page_head) {
|
93 |
sched_unlock(); |
94 |
DPRINTF(("page_alloc: out of memory\n"));
|
95 |
return 0; /* Not found. */ |
96 |
} |
97 |
} while (blk->size < size);
|
98 |
|
99 |
/*
|
100 |
* If found block size is exactly same with requested,
|
101 |
* just remove it from a free list. Otherwise, the
|
102 |
* found block is divided into two and first half is
|
103 |
* used for allocation.
|
104 |
*/
|
105 |
if (blk->size == size) {
|
106 |
blk->prev->next = blk->next; |
107 |
blk->next->prev = blk->prev; |
108 |
} else {
|
109 |
tmp = (struct page *)((vaddr_t)blk + size);
|
110 |
tmp->size = blk->size - size; |
111 |
tmp->prev = blk->prev; |
112 |
tmp->next = blk->next; |
113 |
blk->prev->next = tmp; |
114 |
blk->next->prev = tmp; |
115 |
} |
116 |
used_size += (psize_t)size; |
117 |
sched_unlock(); |
118 |
return kvtop(blk);
|
119 |
} |
120 |
|
121 |
/*
|
122 |
* Free page block.
|
123 |
*
|
124 |
* This allocator does not maintain the size of allocated page
|
125 |
* block. The caller must provide the size information of the
|
126 |
* block.
|
127 |
*/
|
128 |
void
|
129 |
page_free(paddr_t paddr, psize_t psize) |
130 |
{ |
131 |
struct page *blk, *prev;
|
132 |
vsize_t size; |
133 |
|
134 |
ASSERT(psize != 0);
|
135 |
|
136 |
sched_lock(); |
137 |
|
138 |
size = round_page(psize); |
139 |
blk = ptokv(paddr); |
140 |
|
141 |
/*
|
142 |
* Find the target position in list.
|
143 |
*/
|
144 |
for (prev = &page_head; prev->next < blk; prev = prev->next) {
|
145 |
if (prev->next == &page_head)
|
146 |
break;
|
147 |
} |
148 |
|
149 |
/*
|
150 |
* Insert new block into list.
|
151 |
*/
|
152 |
blk->size = size; |
153 |
blk->prev = prev; |
154 |
blk->next = prev->next; |
155 |
prev->next->prev = blk; |
156 |
prev->next = blk; |
157 |
|
158 |
/*
|
159 |
* If the adjoining block is free, it combines and
|
160 |
* is made on block.
|
161 |
*/
|
162 |
if (blk->next != &page_head &&
|
163 |
((vaddr_t)blk + blk->size) == (vaddr_t)blk->next) { |
164 |
blk->size += blk->next->size; |
165 |
blk->next = blk->next->next; |
166 |
blk->next->prev = blk; |
167 |
} |
168 |
if (blk->prev != &page_head &&
|
169 |
(vaddr_t)blk->prev + blk->prev->size == (vaddr_t)blk) { |
170 |
blk->prev->size += blk->size; |
171 |
blk->prev->next = blk->next; |
172 |
blk->next->prev = blk->prev; |
173 |
} |
174 |
used_size -= (psize_t)size; |
175 |
sched_unlock(); |
176 |
} |
177 |
|
178 |
/*
|
179 |
* The function to reserve pages in specific address.
|
180 |
*/
|
181 |
int
|
182 |
page_reserve(paddr_t paddr, psize_t psize) |
183 |
{ |
184 |
struct page *blk, *tmp;
|
185 |
vaddr_t start, end; |
186 |
vsize_t size; |
187 |
|
188 |
if (psize == 0) |
189 |
return 0; |
190 |
|
191 |
start = trunc_page((vaddr_t)ptokv(paddr)); |
192 |
end = round_page((vaddr_t)ptokv(paddr + psize)); |
193 |
size = end - start; |
194 |
|
195 |
/*
|
196 |
* Find the block which includes specified block.
|
197 |
*/
|
198 |
blk = page_head.next; |
199 |
for (;;) {
|
200 |
if (blk == &page_head)
|
201 |
return ENOMEM;
|
202 |
|
203 |
if ((vaddr_t)blk <= start
|
204 |
&& end <= (vaddr_t)blk + blk->size) |
205 |
break;
|
206 |
blk = blk->next; |
207 |
} |
208 |
if ((vaddr_t)blk == start && blk->size == size) {
|
209 |
/*
|
210 |
* Unlink the block from free list.
|
211 |
*/
|
212 |
blk->prev->next = blk->next; |
213 |
blk->next->prev = blk->prev; |
214 |
} else {
|
215 |
/*
|
216 |
* Split this block.
|
217 |
*/
|
218 |
if ((vaddr_t)blk + blk->size != end) {
|
219 |
tmp = (struct page *)end;
|
220 |
tmp->size = (vaddr_t)blk + blk->size - end; |
221 |
tmp->next = blk->next; |
222 |
tmp->prev = blk; |
223 |
|
224 |
blk->size -= tmp->size; |
225 |
blk->next->prev = tmp; |
226 |
blk->next = tmp; |
227 |
} |
228 |
if ((vaddr_t)blk == start) {
|
229 |
blk->prev->next = blk->next; |
230 |
blk->next->prev = blk->prev; |
231 |
} else
|
232 |
blk->size = start - (vaddr_t)blk; |
233 |
} |
234 |
used_size += (psize_t)size; |
235 |
return 0; |
236 |
} |
237 |
|
238 |
void
|
239 |
page_info(struct meminfo *info)
|
240 |
{ |
241 |
|
242 |
info->total = total_size; |
243 |
info->free = total_size - used_size; |
244 |
info->bootdisk = bootdisk_size; |
245 |
|
246 |
#ifndef CONFIG_ROMBOOT
|
247 |
/*
|
248 |
* The boot disk is placed at RAM.
|
249 |
*/
|
250 |
info->free -= bootdisk_size; |
251 |
#endif
|
252 |
} |
253 |
|
254 |
/*
|
255 |
* Initialize page allocator.
|
256 |
* page_init() must be called prior to other memory manager's
|
257 |
* initializations.
|
258 |
*/
|
259 |
void
|
260 |
page_init(void)
|
261 |
{ |
262 |
struct physmem *ram;
|
263 |
struct bootinfo *bi;
|
264 |
int i;
|
265 |
|
266 |
machine_bootinfo(&bi); |
267 |
|
268 |
total_size = 0;
|
269 |
bootdisk_size = 0;
|
270 |
page_head.next = page_head.prev = &page_head; |
271 |
|
272 |
/*
|
273 |
* First, create a free list from the boot information.
|
274 |
*/
|
275 |
for (i = 0; i < bi->nr_rams; i++) { |
276 |
ram = &bi->ram[i]; |
277 |
if (ram->type == MT_USABLE) {
|
278 |
page_free(ram->base, ram->size); |
279 |
total_size += ram->size; |
280 |
} |
281 |
} |
282 |
/*
|
283 |
* Then, reserve un-usable memory.
|
284 |
*/
|
285 |
for (i = 0; i < bi->nr_rams; i++) { |
286 |
ram = &bi->ram[i]; |
287 |
switch (ram->type) {
|
288 |
case MT_BOOTDISK:
|
289 |
bootdisk_size += ram->size; |
290 |
/* FALLTHROUGH */
|
291 |
case MT_MEMHOLE:
|
292 |
total_size -= ram->size; |
293 |
/* FALLTHROUGH */
|
294 |
case MT_RESERVED:
|
295 |
if (page_reserve(ram->base, ram->size))
|
296 |
panic("page_init");
|
297 |
break;
|
298 |
} |
299 |
} |
300 |
used_size = 0;
|
301 |
DPRINTF(("Memory size=%ld\n", total_size));
|
302 |
} |