scoutos / prex-0.9.0 / sys / mem / kmem.c @ 03e9c04a
History | View | Annotate | Download (9.24 KB)
1 | 03e9c04a | Brad Neuman | /*-
|
---|---|---|---|
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 | } |