Prex Home / Browse Source - Prex Version: 0.9.0

root/sys/mem/kmem.c

DEFINITIONS

1. block_find
2. kmem_alloc
3. kmem_free
4. kmem_map
5. kmem_init

   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  */
  30 /*
  31  * kmem.c - kernel memory allocator
  32  */
  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  */
  55 #include <kernel.h>
  56 #include <page.h>
  57 #include <sched.h>
  58 #include <vm.h>
  59 #include <kmem.h>
  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 {
u_short          magic;         /* magic number */
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 };
  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 {
u_short          magic;         /* magic number */
u_short          nallocs;       /* number of allocated blocks */
  85         struct block_hdr first_blk;     /* first block in this page */
  86 };
  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)
  93 /* number of free block list */
  94 #define NR_BLOCK_LIST   (PAGE_SIZE / ALIGN_SIZE)
  96 #define BLOCK_MAGIC     0xdead
  97 #define PAGE_MAGIC      0xbeef
  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)
 103 #define MIN_BLOCK_SIZE  (BLKHDR_SIZE + 16)
 104 #define MAX_BLOCK_SIZE  (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
 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))
 110 /* macro to get the index of free block list. */
 111 #define BLKNDX(b)       ((u_int)((b)->size) >> 4)
 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];
 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 *
block_find(size_t size)
 151 {
 152         int i;
list_t n;
 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;
n = list_first(&free_blocks[i]);
 163         return list_entry(n, struct block_hdr, link);
 164 }
 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 *
kmem_alloc(size_t size)
 176 {
 177         struct block_hdr *blk, *newblk;
 178         struct page_hdr *pg;
paddr_t pa;
 180         void *p;
ASSERT(size != 0);
sched_lock();           /* Lock scheduler */
 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          */
size = ALLOC_SIZE(size + BLKHDR_SIZE);
 192         if (size > MAX_ALLOC_SIZE)
panic("kmem_alloc: too large allocation");
blk = block_find(size);
 196         if (blk) {
 197                 /*
 198                  * Block found.
 199                  */
list_remove(&blk->link); /* Remove from free list */
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) {
sched_unlock();
 208                         return NULL;
 209                 }
pg = ptokv(pa);
pg->nallocs = 0;
pg->magic = PAGE_MAGIC;
 214                 /*
 215                  * Setup first block.
 216                  */
blk = &pg->first_blk;
blk->magic = BLOCK_MAGIC;
blk->size = MAX_BLOCK_SIZE;
blk->pg_next = NULL;
 221         }
 223         /*
 224          * Sanity check
 225          */
 226         if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
panic("kmem_alloc: overrun");
 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                  */
newblk = (struct block_hdr *)((vaddr_t)blk + size);
newblk->magic = BLOCK_MAGIC;
newblk->size = (u_short)(blk->size - size);
list_insert(&free_blocks[BLKNDX(newblk)], &newblk->link);
 241                 /*
 242                  * Update page list.
 243                  */
newblk->pg_next = blk->pg_next;
blk->pg_next = newblk;
blk->size = (u_short)size;
 247         }
 248         /*
 249          * Increment allocation count of this page.
 250          */
pg->nallocs++;
p = (void *)((vaddr_t)blk + BLKHDR_SIZE);
sched_unlock();
 255         return p;
 256 }
 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
kmem_free(void *ptr)
 270 {
 271         struct block_hdr *blk;
 272         struct page_hdr *pg;
ASSERT(ptr != NULL);
 276         /* Lock scheduler */
sched_lock();
 279         /* Get the block header */
blk = (struct block_hdr *)((vaddr_t)ptr - BLKHDR_SIZE);
 281         if (blk->magic != BLOCK_MAGIC)
panic("kmem_free: invalid address");
 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          */
list_insert(&free_blocks[BLKNDX(blk)], &blk->link);
 291         /*
 292          * Decrement allocation count of this page.
 293          */
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) {
list_remove(&blk->link); /* Remove from free list */
 302                 }
pg->magic = 0;
page_free(kvtop(pg), PAGE_SIZE);
 305         }
sched_unlock();
 307 }
 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 *
kmem_map(void *addr, size_t size)
 315 {
paddr_t pa;
pa = vm_translate((vaddr_t)addr, size);
 319         if (pa == 0)
 320                 return NULL;
 321         return ptokv(pa);
 322 }
 324 void
kmem_init(void)
 326 {
 327         int i;
 329         for (i = 0; i < NR_BLOCK_LIST; i++)
list_init(&free_blocks[i]);
 331 }