File: [local] / prex-old / sys / mem / kmem.c (download)
Revision 1.1.1.1 (vendor branch), Tue Jun 3 09:38:46 2008 UTC (16 years, 3 months ago) by nbrk
Branch: MAIN, KOHSUKE
CVS Tags: PREX_0_7_BASE, HEAD Branch point for: PREX_0_8_BASE
Changes since 1.1: +0 -0 lines
Yeah, this is an initial import of Prex, portable real-time microkernel
operating system. I wanna hack it for non-profit but fun, so let it in.
|
/*-
* Copyright (c) 2005-2006, Kohsuke Ohtani
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the author nor the names of any co-contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/*
* kmem.c - kernel memory allocator
*/
/*
* This is a memory allocator optimized for the low foot print kernel.
* It works on top of the underlying page allocator, and manages more
* smaller memory than page size. It will divide one page into two or
* more blocks, and each page is linked as a kernel page.
*
* There are following 3 linked lists to manage used/free blocks.
* 1) All pages allocated for the kernel memory are linked.
* 2) All blocks divided in the same page are linked.
* 3) All free blocks of the same size are linked.
*
* Currently, it can not handle the memory size exceeding one page.
* Instead, a driver can use page_alloc() to allocate larger memory.
*
* The kmem functions are used by not only the kernel core but also
* by the buggy drivers. If such kernel code illegally writes data in
* exceeding the allocated area, the system will crash easily. In order
* to detect the memory over run, each free block has a magic ID.
*/
#include <kernel.h>
#include <page.h>
#include <sched.h>
#include <vm.h>
/*
* Block header
*
* All free blocks that have same size are linked each other.
* In addition, all free blocks within same page are also linked.
*/
struct block_hdr {
u_short magic; /* magic number */
u_short size; /* size of this block */
struct list link; /* link to the free list */
struct block_hdr *pg_next; /* next block in same page */
};
/*
* Page header
*
* The page header is placed at the top of each page. This header is
* used in order to free the page when there are no used block left in
* the page. If nr_alloc value becomes zero, that page can be removed
* from kernel page.
*/
struct page_hdr {
u_short magic; /* magic number */
u_short nallocs; /* number of allocated blocks */
struct block_hdr first_blk; /* first block in this page */
};
#define ALIGN_SIZE 16
#define ALIGN_MASK (ALIGN_SIZE - 1)
#define ALLOC_ALIGN(n) (((n) + ALIGN_MASK) & ~ALIGN_MASK)
#define BLOCK_MAGIC 0xdead
#define PAGE_MAGIC 0xbeef
#define BLKHDR_SIZE (sizeof(struct block_hdr))
#define PGHDR_SIZE (sizeof(struct page_hdr))
#define MAX_ALLOC_SIZE (PAGE_SIZE - PGHDR_SIZE)
#define MIN_BLOCK_SIZE (BLKHDR_SIZE + 16)
#define MAX_BLOCK_SIZE (u_short)(PAGE_SIZE - (PGHDR_SIZE - BLKHDR_SIZE))
/* macro to point the page header from specific address */
#define PAGE_TOP(n) (struct page_hdr *) \
((u_long)(n) & ~(PAGE_SIZE - 1))
/* index of free block list */
#define BLKIDX(b) ((int)((b)->size) >> 4)
/* number of free block list */
#define NR_BLOCK_LIST (PAGE_SIZE / ALIGN_SIZE)
/**
* Array of the head block of free block list.
*
* The index of array is decided by the size of each block.
* All block has the size of the multiple of 16.
*
* ie. free_blocks[0] = list for 16 byte block
* free_blocks[1] = list for 32 byte block
* free_blocks[2] = list for 48 byte block
* .
* .
* free_blocks[255] = list for 4096 byte block
*
* Generally, only one list is used to search the free block with
* a first fit algorithm. Basically, this allocator also uses a first
* fit method. However it uses multiple lists corresponding to each
* block size.
* A search is started from the list of the requested size. So, it is
* not necessary to search smaller block's list wastefully.
*
* Most of kernel memory allocator is using 2^n as block size. But,
* these implementation will throw away much memory that the block
* size is not fit. This is not suitable for the embedded system with
* low foot print.
*/
static struct list free_blocks[NR_BLOCK_LIST];
static int kmem_bytes; /* number of bytes currently allocated */
#ifdef DEBUG
/*
* profiling data
*/
static int nr_pages; /* number of pages currently used */
static int nr_blocks[NR_BLOCK_LIST]; /* number of blocks currently used */
#endif /* DEBUG */
/*
* Find the free block for the specified size.
* Returns pointer to free block, or NULL on failure.
*
* First, it searches from the list of same size. If it does not
* exists, then it will search the list of larger one.
* It will use the block of smallest size that satisfies the
* specified size.
*/
static struct block_hdr *
block_find(size_t size)
{
int i;
list_t n;
for (i = (int)size >> 4; i < NR_BLOCK_LIST; i++) {
if (!list_empty(&free_blocks[i]))
break;
}
if (i >= NR_BLOCK_LIST)
return NULL;
n = list_first(&free_blocks[i]);
return list_entry(n, struct block_hdr, link);
}
/*
* Allocate memory block for kernel
*
* This function does not fill the allocated block by 0 for performance.
* kmem_alloc() returns NULL on failure.
*/
void *
kmem_alloc(size_t size)
{
struct block_hdr *blk, *new_blk;
struct page_hdr *pg;
void *p;
ASSERT(irq_level == 0);
sched_lock(); /* Lock scheduler */
/*
* First, the free block of enough size is searched
* from the page already used. If it does not exist,
* new page is allocated for free block.
*/
size = ALLOC_ALIGN(size + BLKHDR_SIZE);
ASSERT(size && size <= MAX_ALLOC_SIZE);
blk = block_find(size);
if (blk) {
/* Block found */
list_remove(&blk->link); /* Remove from free list */
pg = PAGE_TOP(blk); /* Get the page address */
} else {
/* No block found. Allocate new page */
if ((pg = page_alloc(PAGE_SIZE)) == NULL) {
sched_unlock();
return NULL;
}
pg = phys_to_virt(pg);
pg->nallocs = 0;
pg->magic = PAGE_MAGIC;
/* Setup first block */
blk = &(pg->first_blk);
blk->magic = BLOCK_MAGIC;
blk->size = MAX_BLOCK_SIZE;
blk->pg_next = NULL;
#ifdef DEBUG
nr_pages++;
#endif
}
/* Sanity check */
if (pg->magic != PAGE_MAGIC || blk->magic != BLOCK_MAGIC)
panic("kmem overrun: addr=%x", blk);
/*
* If the found block is large enough, split it.
*/
if (blk->size - size >= MIN_BLOCK_SIZE) {
/* Make new block */
new_blk = (struct block_hdr *)((u_long)blk + size);
new_blk->magic = BLOCK_MAGIC;
new_blk->size = (u_short)(blk->size - size);
list_insert(&free_blocks[BLKIDX(new_blk)], &new_blk->link);
/* Update page list */
new_blk->pg_next = blk->pg_next;
blk->pg_next = new_blk;
blk->size = (u_short)size;
}
/* Increment allocation count of this page */
pg->nallocs++;
kmem_bytes += blk->size;
#ifdef DEBUG
nr_blocks[BLKIDX(blk)]++;
#endif
p = (void *)((u_long)blk + BLKHDR_SIZE);
sched_unlock();
return p;
}
/*
* Free allocated memory block.
*
* Some kernel does not release the free page for the kernel memory
* because it is needed to allocate immediately later. For example,
* it is efficient here if the free page is just linked to the list
* of the biggest size. However, consider the case where a driver
* requires many small memories temporarily. After these pages are
* freed, they can not be reused for an application.
*/
void
kmem_free(void *ptr)
{
struct block_hdr *blk;
struct page_hdr *pg;
ASSERT(irq_level == 0);
ASSERT(ptr);
/* Lock scheduler */
sched_lock();
/* Get the block header */
blk = (struct block_hdr *)((u_long)ptr - BLKHDR_SIZE);
if (blk->magic != BLOCK_MAGIC)
panic("kmem_free");
kmem_bytes -= blk->size;
#ifdef DEBUG
nr_blocks[BLKIDX(blk)]--;
#endif
/*
* Return the block to free list.
* Since kernel code will request fixed size of memory block,
* we don't merge the blocks to use it as cache.
*/
list_insert(&free_blocks[BLKIDX(blk)], &blk->link);
/* Decrement allocation count of this page */
pg = PAGE_TOP(blk);
if (--pg->nallocs <= 0) {
/*
* No allocated block in this page.
* Remove all blocks and deallocate this page.
*/
for (blk = &(pg->first_blk); blk != NULL; blk = blk->pg_next) {
list_remove(&blk->link); /* Remove from free list */
#ifdef DEBUG
nr_blocks[BLKIDX(blk)]--;
#endif
}
pg->magic = 0;
page_free(virt_to_phys(pg), PAGE_SIZE);
#ifdef DEBUG
nr_pages--;
#endif
}
sched_unlock();
}
/*
* Map specified virtual address to the kernel address
* Returns kernel address on success, or NULL if no mapped memory.
*/
void *
kmem_map(void *addr, size_t size)
{
void *phys;
phys = vm_translate(addr, size);
if (phys == NULL)
return NULL;
return phys_to_virt(phys);
}
void
kmem_info(size_t *size)
{
*size = (size_t)kmem_bytes;
}
#if defined(DEBUG) && defined(CONFIG_KDUMP)
void
kmem_dump(void)
{
list_t head, n;
int i, cnt;
struct block_hdr *blk;
printk("\nKernel memory dump:\n");
printk(" allocated blocks:\n");
printk(" block size count\n");
printk(" ---------- --------\n");
for (i = 0; i < NR_BLOCK_LIST; i++) {
if (nr_blocks[i])
printk(" %4d %8d\n", i << 4, nr_blocks[i]);
}
printk("\n free blocks:\n");
printk(" block size count\n");
printk(" ---------- --------\n");
for (i = 0; i < NR_BLOCK_LIST; i++) {
cnt = 0;
head = &free_blocks[i];
for (n = list_first(head); n != head; n = list_next(n)) {
cnt++;
blk = list_entry(n, struct block_hdr, link);
}
if (cnt > 0)
printk(" %4d %8d\n", i << 4, cnt);
}
printk(" Total: page=%d (%dKbyte) alloc=%dbyte unused=%dbyte\n",
nr_pages, nr_pages * 4, kmem_bytes,
nr_pages * PAGE_SIZE - kmem_bytes);
}
#endif
void
kmem_init(void)
{
int i;
for (i = 0; i < NR_BLOCK_LIST; i++)
list_init(&free_blocks[i]);
}