scoutos / prex-0.9.0 / sys / mem / kmem.c @ 03e9c04a
History | View | Annotate | Download (9.24 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 |
* kmem.c - kernel memory allocator
|
32 |
*/
|
33 |
|
34 |
/*
|
35 |
* This is a memory allocator optimized for the low foot print
|
36 |
* kernel. It works on top of the underlying page allocator, and
|
37 |
* manages more smaller memory than page size. It will divide one page
|
38 |
* into two or more blocks, and each page is linked as a kernel page.
|
39 |
*
|
40 |
* There are following 3 linked lists to manage used/free blocks.
|
41 |
* 1) All pages allocated for the kernel memory are linked.
|
42 |
* 2) All blocks divided in the same page are linked.
|
43 |
* 3) All free blocks of the same size are linked.
|
44 |
*
|
45 |
* Currently, it can not handle the memory size exceeding one page.
|
46 |
* Instead, a driver can use page_alloc() to allocate larger memory.
|
47 |
*
|
48 |
* The kmem functions are used by not only the kernel core but also by
|
49 |
* the buggy drivers. If such kernel code illegally writes data in
|
50 |
* exceeding the allocated area, the system will crash easily. In
|
51 |
* order to detect the memory over run, each free block has a magic
|
52 |
* ID.
|
53 |
*/
|
54 |
|
55 |
#include <kernel.h> |
56 |
#include <page.h> |
57 |
#include <sched.h> |
58 |
#include <vm.h> |
59 |
#include <kmem.h> |
60 |
|
61 |
/*
|
62 |
* Block header
|
63 |
*
|
64 |
* All free blocks that have same size are linked each other.
|
65 |
* In addition, all free blocks within same page are also linked.
|
66 |
*/
|
67 |
struct block_hdr {
|
68 |
u_short magic; /* magic number */
|
69 |
u_short size; /* size of this block */
|
70 |
struct list link; /* link to the free list */ |
71 |
struct block_hdr *pg_next; /* next block in same page */ |
72 |
}; |
73 |
|
74 |
/*
|
75 |
* Page header
|
76 |
*
|
77 |
* The page header is placed at the top of each page. This
|
78 |
* header is used in order to free the page when there are no
|
79 |
* used block left in the page. If 'nallocs' value becomes zero,
|
80 |
* that page can be removed from kernel page.
|
81 |
*/
|
82 |
struct page_hdr {
|
83 |
u_short magic; /* magic number */
|
84 |
u_short nallocs; /* number of allocated blocks */
|
85 |
struct block_hdr first_blk; /* first block in this page */ |
86 |
}; |
87 |
|
88 |
#define ALIGN_SIZE 16 |
89 |
#define ALIGN_MASK (ALIGN_SIZE - 1) |
90 |
#define ALLOC_SIZE(n) (size_t) \
|
91 |
(((vaddr_t)(n) + ALIGN_MASK) & (vaddr_t)~ALIGN_MASK) |
92 |
|
93 |
/* number of free block list */
|
94 |
#define NR_BLOCK_LIST (PAGE_SIZE / ALIGN_SIZE)
|
95 |
|
96 |
#define BLOCK_MAGIC 0xdead |
97 |
#define PAGE_MAGIC 0xbeef |
98 |
|
99 |
#define BLKHDR_SIZE (sizeof(struct block_hdr)) |
100 |
#define PGHDR_SIZE (sizeof(struct page_hdr)) |
101 |
#define MAX_ALLOC_SIZE (size_t)(PAGE_SIZE - PGHDR_SIZE)
|
102 |
|
103 |
#define MIN_BLOCK_SIZE (BLKHDR_SIZE + 16) |
104 |
#define MAX_BLOCK_SIZE (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
|
105 |
|
106 |
/* macro to point the page header from specific address. */
|
107 |
#define PAGETOP(n) (struct page_hdr *) \ |
108 |
((vaddr_t)(n) & (vaddr_t)~(PAGE_SIZE - 1))
|
109 |
|
110 |
/* macro to get the index of free block list. */
|
111 |
#define BLKNDX(b) ((u_int)((b)->size) >> 4) |
112 |
|
113 |
/**
|
114 |
* Array of the head block of free block list.
|
115 |
*
|
116 |
* The index of array is decided by the size of each block.
|
117 |
* All block has the size of the multiple of 16.
|
118 |
*
|
119 |
* ie. free_blocks[0] = list for 16 byte block
|
120 |
* free_blocks[1] = list for 32 byte block
|
121 |
* free_blocks[2] = list for 48 byte block
|
122 |
* .
|
123 |
* .
|
124 |
* free_blocks[255] = list for 4096 byte block
|
125 |
*
|
126 |
* Generally, only one list is used to search the free block with
|
127 |
* a first fit algorithm. Basically, this allocator also uses a
|
128 |
* first fit method. However it uses multiple lists corresponding
|
129 |
* to each block size. A search is started from the list of the
|
130 |
* requested size. So, it is not necessary to search smaller
|
131 |
* block's list wastefully.
|
132 |
*
|
133 |
* Most of kernel memory allocator is using 2^n as block size.
|
134 |
* But, these implementation will throw away much memory that
|
135 |
* the block size is not fit. This is not suitable for the
|
136 |
* embedded system with low foot print.
|
137 |
*/
|
138 |
static struct list free_blocks[NR_BLOCK_LIST]; |
139 |
|
140 |
/*
|
141 |
* Find the free block for the specified size.
|
142 |
* Returns pointer to free block, or NULL on failure.
|
143 |
*
|
144 |
* First, it searches from the list of same size. If it does not
|
145 |
* exists, then it will search the list of larger one.
|
146 |
* It will use the block of smallest size that satisfies the
|
147 |
* specified size.
|
148 |
*/
|
149 |
static struct block_hdr * |
150 |
block_find(size_t size) |
151 |
{ |
152 |
int i;
|
153 |
list_t n; |
154 |
|
155 |
for (i = (int)((u_int)size >> 4); i < NR_BLOCK_LIST; i++) { |
156 |
if (!list_empty(&free_blocks[i]))
|
157 |
break;
|
158 |
} |
159 |
if (i >= NR_BLOCK_LIST)
|
160 |
return NULL; |
161 |
|
162 |
n = list_first(&free_blocks[i]); |
163 |
return list_entry(n, struct block_hdr, link); |
164 |
} |
165 |
|
166 |
/*
|
167 |
* Allocate memory block for kernel
|
168 |
*
|
169 |
* This function does not fill the allocated block by 0 for performance.
|
170 |
* kmem_alloc() returns NULL on failure.
|
171 |
*
|
172 |
* => must not be called from interrupt context.
|
173 |
*/
|
174 |
void *
|
175 |
kmem_alloc(size_t size) |
176 |
{ |
177 |
struct block_hdr *blk, *newblk;
|
178 |
struct page_hdr *pg;
|
179 |
paddr_t pa; |
180 |
void *p;
|
181 |
|
182 |
ASSERT(size != 0);
|
183 |
|
184 |
sched_lock(); /* Lock scheduler */
|
185 |
|
186 |
/*
|
187 |
* First, the free block of enough size is searched
|
188 |
* from the page already used. If it does not exist,
|
189 |
* new page is allocated for free block.
|
190 |
*/
|
191 |
size = ALLOC_SIZE(size + BLKHDR_SIZE); |
192 |
if (size > MAX_ALLOC_SIZE)
|
193 |
panic("kmem_alloc: too large allocation");
|
194 |
|
195 |
blk = block_find(size); |
196 |
if (blk) {
|
197 |
/*
|
198 |
* Block found.
|
199 |
*/
|
200 |
list_remove(&blk->link); /* Remove from free list */
|
201 |
pg = PAGETOP(blk); /* Get the page address */
|
202 |
} else {
|
203 |
/*
|
204 |
* No block found. Allocate new page.
|
205 |
*/
|
206 |
if ((pa = page_alloc(PAGE_SIZE)) == 0) { |
207 |
sched_unlock(); |
208 |
return NULL; |
209 |
} |
210 |
pg = ptokv(pa); |
211 |
pg->nallocs = 0;
|
212 |
pg->magic = PAGE_MAGIC; |
213 |
|
214 |
/*
|
215 |
* Setup first block.
|
216 |
*/
|
217 |
blk = &pg->first_blk; |
218 |
blk->magic = BLOCK_MAGIC; |
219 |
blk->size = MAX_BLOCK_SIZE; |
220 |
blk->pg_next = NULL;
|
221 |
} |
222 |
|
223 |
/*
|
224 |
* Sanity check
|
225 |
*/
|
226 |
if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
|
227 |
panic("kmem_alloc: overrun");
|
228 |
|
229 |
/*
|
230 |
* If the found block is large enough, split it.
|
231 |
*/
|
232 |
if (blk->size - size >= MIN_BLOCK_SIZE) {
|
233 |
/*
|
234 |
* Make new block.
|
235 |
*/
|
236 |
newblk = (struct block_hdr *)((vaddr_t)blk + size);
|
237 |
newblk->magic = BLOCK_MAGIC; |
238 |
newblk->size = (u_short)(blk->size - size); |
239 |
list_insert(&free_blocks[BLKNDX(newblk)], &newblk->link); |
240 |
|
241 |
/*
|
242 |
* Update page list.
|
243 |
*/
|
244 |
newblk->pg_next = blk->pg_next; |
245 |
blk->pg_next = newblk; |
246 |
blk->size = (u_short)size; |
247 |
} |
248 |
/*
|
249 |
* Increment allocation count of this page.
|
250 |
*/
|
251 |
pg->nallocs++; |
252 |
p = (void *)((vaddr_t)blk + BLKHDR_SIZE);
|
253 |
|
254 |
sched_unlock(); |
255 |
return p;
|
256 |
} |
257 |
|
258 |
/*
|
259 |
* Free allocated memory block.
|
260 |
*
|
261 |
* Some kernel does not release the free page for the kernel memory
|
262 |
* because it is needed to allocate immediately later. For example,
|
263 |
* it is efficient here if the free page is just linked to the list
|
264 |
* of the biggest size. However, consider the case where a driver
|
265 |
* requires many small memories temporarily. After these pages are
|
266 |
* freed, they can not be reused for an application.
|
267 |
*/
|
268 |
void
|
269 |
kmem_free(void *ptr)
|
270 |
{ |
271 |
struct block_hdr *blk;
|
272 |
struct page_hdr *pg;
|
273 |
|
274 |
ASSERT(ptr != NULL);
|
275 |
|
276 |
/* Lock scheduler */
|
277 |
sched_lock(); |
278 |
|
279 |
/* Get the block header */
|
280 |
blk = (struct block_hdr *)((vaddr_t)ptr - BLKHDR_SIZE);
|
281 |
if (blk->magic != BLOCK_MAGIC)
|
282 |
panic("kmem_free: invalid address");
|
283 |
|
284 |
/*
|
285 |
* Return the block to free list. Since kernel code will
|
286 |
* request fixed size of memory block, we don't merge the
|
287 |
* blocks to use it as cache.
|
288 |
*/
|
289 |
list_insert(&free_blocks[BLKNDX(blk)], &blk->link); |
290 |
|
291 |
/*
|
292 |
* Decrement allocation count of this page.
|
293 |
*/
|
294 |
pg = PAGETOP(blk); |
295 |
if (--pg->nallocs == 0) { |
296 |
/*
|
297 |
* No allocated block in this page.
|
298 |
* Remove all blocks and deallocate this page.
|
299 |
*/
|
300 |
for (blk = &pg->first_blk; blk != NULL; blk = blk->pg_next) { |
301 |
list_remove(&blk->link); /* Remove from free list */
|
302 |
} |
303 |
pg->magic = 0;
|
304 |
page_free(kvtop(pg), PAGE_SIZE); |
305 |
} |
306 |
sched_unlock(); |
307 |
} |
308 |
|
309 |
/*
|
310 |
* Map specified virtual address to the kernel address
|
311 |
* Returns kernel address on success, or NULL if no mapped memory.
|
312 |
*/
|
313 |
void *
|
314 |
kmem_map(void *addr, size_t size)
|
315 |
{ |
316 |
paddr_t pa; |
317 |
|
318 |
pa = vm_translate((vaddr_t)addr, size); |
319 |
if (pa == 0) |
320 |
return NULL; |
321 |
return ptokv(pa);
|
322 |
} |
323 |
|
324 |
void
|
325 |
kmem_init(void)
|
326 |
{ |
327 |
int i;
|
328 |
|
329 |
for (i = 0; i < NR_BLOCK_LIST; i++) |
330 |
list_init(&free_blocks[i]); |
331 |
} |