Annotation of prex-old/sys/mem/kmem.c, Revision 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