Annotation of prex-old/sys/mem/kmem.c, Revision 1.1.1.1
1.1 nbrk 1: /*-
2: * Copyright (c) 2005-2006, 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 kernel.
36: * It works on top of the underlying page allocator, and manages more
37: * smaller memory than page size. It will divide one page into two or
38: * 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
49: * by the buggy drivers. If such kernel code illegally writes data in
50: * exceeding the allocated area, the system will crash easily. In order
51: * to detect the memory over run, each free block has a magic ID.
52: */
53:
54: #include <kernel.h>
55: #include <page.h>
56: #include <sched.h>
57: #include <vm.h>
58:
59: /*
60: * Block header
61: *
62: * All free blocks that have same size are linked each other.
63: * In addition, all free blocks within same page are also linked.
64: */
65: struct block_hdr {
66: u_short magic; /* magic number */
67: u_short size; /* size of this block */
68: struct list link; /* link to the free list */
69: struct block_hdr *pg_next; /* next block in same page */
70: };
71:
72: /*
73: * Page header
74: *
75: * The page header is placed at the top of each page. This header is
76: * used in order to free the page when there are no used block left in
77: * the page. If nr_alloc value becomes zero, that page can be removed
78: * from kernel page.
79: */
80: struct page_hdr {
81: u_short magic; /* magic number */
82: u_short nallocs; /* number of allocated blocks */
83: struct block_hdr first_blk; /* first block in this page */
84: };
85:
86: #define ALIGN_SIZE 16
87: #define ALIGN_MASK (ALIGN_SIZE - 1)
88: #define ALLOC_ALIGN(n) (((n) + ALIGN_MASK) & ~ALIGN_MASK)
89:
90: #define BLOCK_MAGIC 0xdead
91: #define PAGE_MAGIC 0xbeef
92:
93: #define BLKHDR_SIZE (sizeof(struct block_hdr))
94: #define PGHDR_SIZE (sizeof(struct page_hdr))
95: #define MAX_ALLOC_SIZE (PAGE_SIZE - PGHDR_SIZE)
96:
97: #define MIN_BLOCK_SIZE (BLKHDR_SIZE + 16)
98: #define MAX_BLOCK_SIZE (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
99:
100: /* macro to point the page header from specific address */
101: #define PAGE_TOP(n) (struct page_hdr *) \
102: ((u_long)(n) & ~(PAGE_SIZE - 1))
103:
104: /* index of free block list */
105: #define BLKIDX(b) ((int)((b)->size) >> 4)
106:
107: /* number of free block list */
108: #define NR_BLOCK_LIST (PAGE_SIZE / ALIGN_SIZE)
109:
110: /**
111: * Array of the head block of free block list.
112: *
113: * The index of array is decided by the size of each block.
114: * All block has the size of the multiple of 16.
115: *
116: * ie. free_blocks[0] = list for 16 byte block
117: * free_blocks[1] = list for 32 byte block
118: * free_blocks[2] = list for 48 byte block
119: * .
120: * .
121: * free_blocks[255] = list for 4096 byte block
122: *
123: * Generally, only one list is used to search the free block with
124: * a first fit algorithm. Basically, this allocator also uses a first
125: * fit method. However it uses multiple lists corresponding to each
126: * block size.
127: * A search is started from the list of the requested size. So, it is
128: * not necessary to search smaller block's list wastefully.
129: *
130: * Most of kernel memory allocator is using 2^n as block size. But,
131: * these implementation will throw away much memory that the block
132: * size is not fit. This is not suitable for the embedded system with
133: * low foot print.
134: */
135: static struct list free_blocks[NR_BLOCK_LIST];
136:
137: static int kmem_bytes; /* number of bytes currently allocated */
138:
139: #ifdef DEBUG
140: /*
141: * profiling data
142: */
143: static int nr_pages; /* number of pages currently used */
144: static int nr_blocks[NR_BLOCK_LIST]; /* number of blocks currently used */
145:
146: #endif /* DEBUG */
147:
148: /*
149: * Find the free block for the specified size.
150: * Returns pointer to free block, or NULL on failure.
151: *
152: * First, it searches from the list of same size. If it does not
153: * exists, then it will search the list of larger one.
154: * It will use the block of smallest size that satisfies the
155: * specified size.
156: */
157: static struct block_hdr *
158: block_find(size_t size)
159: {
160: int i;
161: list_t n;
162:
163: for (i = (int)size >> 4; i < NR_BLOCK_LIST; i++) {
164: if (!list_empty(&free_blocks[i]))
165: break;
166: }
167: if (i >= NR_BLOCK_LIST)
168: return NULL;
169:
170: n = list_first(&free_blocks[i]);
171: return list_entry(n, struct block_hdr, link);
172: }
173:
174: /*
175: * Allocate memory block for kernel
176: *
177: * This function does not fill the allocated block by 0 for performance.
178: * kmem_alloc() returns NULL on failure.
179: */
180: void *
181: kmem_alloc(size_t size)
182: {
183: struct block_hdr *blk, *new_blk;
184: struct page_hdr *pg;
185: void *p;
186:
187: ASSERT(irq_level == 0);
188:
189: sched_lock(); /* Lock scheduler */
190: /*
191: * First, the free block of enough size is searched
192: * from the page already used. If it does not exist,
193: * new page is allocated for free block.
194: */
195: size = ALLOC_ALIGN(size + BLKHDR_SIZE);
196:
197: ASSERT(size && size <= MAX_ALLOC_SIZE);
198:
199: blk = block_find(size);
200: if (blk) {
201: /* Block found */
202: list_remove(&blk->link); /* Remove from free list */
203: pg = PAGE_TOP(blk); /* Get the page address */
204: } else {
205: /* No block found. Allocate new page */
206: if ((pg = page_alloc(PAGE_SIZE)) == NULL) {
207: sched_unlock();
208: return NULL;
209: }
210: pg = phys_to_virt(pg);
211: pg->nallocs = 0;
212: pg->magic = PAGE_MAGIC;
213:
214: /* Setup first block */
215: blk = &(pg->first_blk);
216: blk->magic = BLOCK_MAGIC;
217: blk->size = MAX_BLOCK_SIZE;
218: blk->pg_next = NULL;
219: #ifdef DEBUG
220: nr_pages++;
221: #endif
222: }
223: /* Sanity check */
224: if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
225: panic("kmem overrun: addr=%x", blk);
226: /*
227: * If the found block is large enough, split it.
228: */
229: if (blk->size - size >= MIN_BLOCK_SIZE) {
230: /* Make new block */
231: new_blk = (struct block_hdr *)((u_long)blk + size);
232: new_blk->magic = BLOCK_MAGIC;
233: new_blk->size = (u_short)(blk->size - size);
234: list_insert(&free_blocks[BLKIDX(new_blk)], &new_blk->link);
235:
236: /* Update page list */
237: new_blk->pg_next = blk->pg_next;
238: blk->pg_next = new_blk;
239:
240: blk->size = (u_short)size;
241: }
242: /* Increment allocation count of this page */
243: pg->nallocs++;
244: kmem_bytes += blk->size;
245: #ifdef DEBUG
246: nr_blocks[BLKIDX(blk)]++;
247: #endif
248: p = (void *)((u_long)blk + BLKHDR_SIZE);
249: sched_unlock();
250: return p;
251: }
252:
253: /*
254: * Free allocated memory block.
255: *
256: * Some kernel does not release the free page for the kernel memory
257: * because it is needed to allocate immediately later. For example,
258: * it is efficient here if the free page is just linked to the list
259: * of the biggest size. However, consider the case where a driver
260: * requires many small memories temporarily. After these pages are
261: * freed, they can not be reused for an application.
262: */
263: void
264: kmem_free(void *ptr)
265: {
266: struct block_hdr *blk;
267: struct page_hdr *pg;
268:
269: ASSERT(irq_level == 0);
270: ASSERT(ptr);
271:
272: /* Lock scheduler */
273: sched_lock();
274:
275: /* Get the block header */
276: blk = (struct block_hdr *)((u_long)ptr - BLKHDR_SIZE);
277: if (blk->magic != BLOCK_MAGIC)
278: panic("kmem_free");
279:
280: kmem_bytes -= blk->size;
281:
282: #ifdef DEBUG
283: nr_blocks[BLKIDX(blk)]--;
284: #endif
285: /*
286: * Return the block to free list.
287: * Since kernel code will request fixed size of memory block,
288: * we don't merge the blocks to use it as cache.
289: */
290: list_insert(&free_blocks[BLKIDX(blk)], &blk->link);
291:
292: /* Decrement allocation count of this page */
293: pg = PAGE_TOP(blk);
294: if (--pg->nallocs <= 0) {
295: /*
296: * No allocated block in this page.
297: * Remove all blocks and deallocate this page.
298: */
299: for (blk = &(pg->first_blk); blk != NULL; blk = blk->pg_next) {
300: list_remove(&blk->link); /* Remove from free list */
301: #ifdef DEBUG
302: nr_blocks[BLKIDX(blk)]--;
303: #endif
304: }
305: pg->magic = 0;
306: page_free(virt_to_phys(pg), PAGE_SIZE);
307: #ifdef DEBUG
308: nr_pages--;
309: #endif
310: }
311: sched_unlock();
312: }
313:
314: /*
315: * Map specified virtual address to the kernel address
316: * Returns kernel address on success, or NULL if no mapped memory.
317: */
318: void *
319: kmem_map(void *addr, size_t size)
320: {
321: void *phys;
322:
323: phys = vm_translate(addr, size);
324: if (phys == NULL)
325: return NULL;
326: return phys_to_virt(phys);
327: }
328:
329: void
330: kmem_info(size_t *size)
331: {
332:
333: *size = (size_t)kmem_bytes;
334: }
335:
336: #if defined(DEBUG) && defined(CONFIG_KDUMP)
337: void
338: kmem_dump(void)
339: {
340: list_t head, n;
341: int i, cnt;
342: struct block_hdr *blk;
343:
344: printk("\nKernel memory dump:\n");
345:
346: printk(" allocated blocks:\n");
347: printk(" block size count\n");
348: printk(" ---------- --------\n");
349:
350: for (i = 0; i < NR_BLOCK_LIST; i++) {
351: if (nr_blocks[i])
352: printk(" %4d %8d\n", i << 4, nr_blocks[i]);
353: }
354: printk("\n free blocks:\n");
355: printk(" block size count\n");
356: printk(" ---------- --------\n");
357:
358: for (i = 0; i < NR_BLOCK_LIST; i++) {
359: cnt = 0;
360: head = &free_blocks[i];
361: for (n = list_first(head); n != head; n = list_next(n)) {
362: cnt++;
363:
364: blk = list_entry(n, struct block_hdr, link);
365: }
366: if (cnt > 0)
367: printk(" %4d %8d\n", i << 4, cnt);
368: }
369: printk(" Total: page=%d (%dKbyte) alloc=%dbyte unused=%dbyte\n",
370: nr_pages, nr_pages * 4, kmem_bytes,
371: nr_pages * PAGE_SIZE - kmem_bytes);
372: }
373: #endif
374:
375: void
376: kmem_init(void)
377: {
378: int i;
379:
380: for (i = 0; i < NR_BLOCK_LIST; i++)
381: list_init(&free_blocks[i]);
382: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to kmem.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex-old / sys / mem