Annotation of prex/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
! 36: * kernel. It works on top of the underlying page allocator, and
! 37: * manages more smaller memory than page size. It will divide one
! 38: * page into two or more blocks, and each page is linked as a
! 39: * kernel page.
! 40: *
! 41: * There are following 3 linked lists to manage used/free blocks.
! 42: * 1) All pages allocated for the kernel memory are linked.
! 43: * 2) All blocks divided in the same page are linked.
! 44: * 3) All free blocks of the same size are linked.
! 45: *
! 46: * Currently, it can not handle the memory size exceeding one page.
! 47: * Instead, a driver can use page_alloc() to allocate larger memory.
! 48: *
! 49: * The kmem functions are used by not only the kernel core but
! 50: * also by the buggy drivers. If such kernel code illegally
! 51: * writes data in exceeding the allocated area, the system will
! 52: * crash easily. In order to detect the memory over run, each
! 53: * free block has a magic ID.
! 54: */
! 55:
! 56: #include <kernel.h>
! 57: #include <page.h>
! 58: #include <sched.h>
! 59: #include <vm.h>
! 60: #include <kmem.h>
! 61:
! 62: /*
! 63: * Block header
! 64: *
! 65: * All free blocks that have same size are linked each other.
! 66: * In addition, all free blocks within same page are also linked.
! 67: */
! 68: struct block_hdr {
! 69: u_short magic; /* magic number */
! 70: u_short size; /* size of this block */
! 71: struct list link; /* link to the free list */
! 72: struct block_hdr *pg_next; /* next block in same page */
! 73: };
! 74:
! 75: /*
! 76: * Page header
! 77: *
! 78: * The page header is placed at the top of each page. This
! 79: * header is used in order to free the page when there are no
! 80: * used block left in the page. If nr_alloc value becomes zero,
! 81: * that page can be removed from kernel page.
! 82: */
! 83: struct page_hdr {
! 84: u_short magic; /* magic number */
! 85: u_short nallocs; /* number of allocated blocks */
! 86: struct block_hdr first_blk; /* first block in this page */
! 87: };
! 88:
! 89: #define ALIGN_SIZE 16
! 90: #define ALIGN_MASK (ALIGN_SIZE - 1)
! 91: #define ALLOC_ALIGN(n) (((vaddr_t)(n) + ALIGN_MASK) & (vaddr_t)~ALIGN_MASK)
! 92:
! 93: #define BLOCK_MAGIC 0xdead
! 94: #define PAGE_MAGIC 0xbeef
! 95:
! 96: #define BLKHDR_SIZE (sizeof(struct block_hdr))
! 97: #define PGHDR_SIZE (sizeof(struct page_hdr))
! 98: #define MAX_ALLOC_SIZE (size_t)(PAGE_SIZE - PGHDR_SIZE)
! 99:
! 100: #define MIN_BLOCK_SIZE (BLKHDR_SIZE + 16)
! 101: #define MAX_BLOCK_SIZE (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
! 102:
! 103: /* macro to point the page header from specific address */
! 104: #define PAGE_TOP(n) (struct page_hdr *) \
! 105: ((vaddr_t)(n) & (vaddr_t)~(PAGE_SIZE - 1))
! 106:
! 107: /* index of free block list */
! 108: #define BLKIDX(b) ((u_int)((b)->size) >> 4)
! 109:
! 110: /* number of free block list */
! 111: #define NR_BLOCK_LIST (PAGE_SIZE / ALIGN_SIZE)
! 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: void *
! 173: kmem_alloc(size_t size)
! 174: {
! 175: struct block_hdr *blk, *newblk;
! 176: struct page_hdr *pg;
! 177: void *p;
! 178:
! 179: ASSERT(irq_level == 0);
! 180:
! 181: sched_lock(); /* Lock scheduler */
! 182: /*
! 183: * First, the free block of enough size is searched
! 184: * from the page already used. If it does not exist,
! 185: * new page is allocated for free block.
! 186: */
! 187: size = ALLOC_ALIGN(size + BLKHDR_SIZE);
! 188:
! 189: ASSERT(size && size <= MAX_ALLOC_SIZE);
! 190:
! 191: blk = block_find(size);
! 192: if (blk) {
! 193: /* Block found */
! 194: list_remove(&blk->link); /* Remove from free list */
! 195: pg = PAGE_TOP(blk); /* Get the page address */
! 196: } else {
! 197: /* No block found. Allocate new page */
! 198: if ((pg = page_alloc(PAGE_SIZE)) == NULL) {
! 199: sched_unlock();
! 200: return NULL;
! 201: }
! 202: pg = phys_to_virt(pg);
! 203: pg->nallocs = 0;
! 204: pg->magic = PAGE_MAGIC;
! 205:
! 206: /* Setup first block */
! 207: blk = &(pg->first_blk);
! 208: blk->magic = BLOCK_MAGIC;
! 209: blk->size = MAX_BLOCK_SIZE;
! 210: blk->pg_next = NULL;
! 211: }
! 212: /* Sanity check */
! 213: if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
! 214: panic("kmem_alloc: overrun");
! 215: /*
! 216: * If the found block is large enough, split it.
! 217: */
! 218: if (blk->size - size >= MIN_BLOCK_SIZE) {
! 219: /* Make new block */
! 220: newblk = (struct block_hdr *)((char *)blk + size);
! 221: newblk->magic = BLOCK_MAGIC;
! 222: newblk->size = (u_short)(blk->size - size);
! 223: list_insert(&free_blocks[BLKIDX(newblk)], &newblk->link);
! 224:
! 225: /* Update page list */
! 226: newblk->pg_next = blk->pg_next;
! 227: blk->pg_next = newblk;
! 228:
! 229: blk->size = (u_short)size;
! 230: }
! 231: /* Increment allocation count of this page */
! 232: pg->nallocs++;
! 233: p = (char *)blk + BLKHDR_SIZE;
! 234: sched_unlock();
! 235: return p;
! 236: }
! 237:
! 238: /*
! 239: * Free allocated memory block.
! 240: *
! 241: * Some kernel does not release the free page for the kernel memory
! 242: * because it is needed to allocate immediately later. For example,
! 243: * it is efficient here if the free page is just linked to the list
! 244: * of the biggest size. However, consider the case where a driver
! 245: * requires many small memories temporarily. After these pages are
! 246: * freed, they can not be reused for an application.
! 247: */
! 248: void
! 249: kmem_free(void *ptr)
! 250: {
! 251: struct block_hdr *blk;
! 252: struct page_hdr *pg;
! 253:
! 254: ASSERT(irq_level == 0);
! 255: ASSERT(ptr);
! 256:
! 257: /* Lock scheduler */
! 258: sched_lock();
! 259:
! 260: /* Get the block header */
! 261: blk = (struct block_hdr *)((char *)ptr - BLKHDR_SIZE);
! 262: if (blk->magic != BLOCK_MAGIC)
! 263: panic("kmem_free: invalid address");
! 264:
! 265: /*
! 266: * Return the block to free list. Since kernel code will
! 267: * request fixed size of memory block, we don't merge the
! 268: * blocks to use it as cache.
! 269: */
! 270: list_insert(&free_blocks[BLKIDX(blk)], &blk->link);
! 271:
! 272: /* Decrement allocation count of this page */
! 273: pg = PAGE_TOP(blk);
! 274: if (--pg->nallocs <= 0) {
! 275: /*
! 276: * No allocated block in this page.
! 277: * Remove all blocks and deallocate this page.
! 278: */
! 279: for (blk = &(pg->first_blk); blk != NULL; blk = blk->pg_next) {
! 280: list_remove(&blk->link); /* Remove from free list */
! 281: }
! 282: pg->magic = 0;
! 283: page_free(virt_to_phys(pg), PAGE_SIZE);
! 284: }
! 285: sched_unlock();
! 286: }
! 287:
! 288: /*
! 289: * Map specified virtual address to the kernel address
! 290: * Returns kernel address on success, or NULL if no mapped memory.
! 291: */
! 292: void *
! 293: kmem_map(void *addr, size_t size)
! 294: {
! 295: void *phys;
! 296:
! 297: phys = vm_translate(addr, size);
! 298: if (phys == NULL)
! 299: return NULL;
! 300: return phys_to_virt(phys);
! 301: }
! 302:
! 303: void
! 304: kmem_init(void)
! 305: {
! 306: int i;
! 307:
! 308: for (i = 0; i < NR_BLOCK_LIST; i++)
! 309: list_init(&free_blocks[i]);
! 310: }
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 / sys / mem