Prex Home / Browse Source - Prex Version: 0.9.0

root/sys/mem/page.c

DEFINITIONS

1. page_alloc
2. page_free
3. page_reserve
4. page_info
5. page_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  * page.c - physical page allocator
  32  */
  34 /*
  35  * Simple list-based page allocator:
  36  *
  37  * When the remaining page is exhausted, what should we do ?
  38  * If the system can stop with panic() here, the error check of
  39  * many portions in kernel is not necessary, and kernel code can
  40  * become more simple. But, in general, even if a page is
  41  * exhausted, a kernel can not be stopped but it should return an
  42  * error and continue processing.  If the memory becomes short
  43  * during boot time, kernel and drivers can use panic() in that
  44  * case.
  45  */
  47 #include <kernel.h>
  48 #include <page.h>
  49 #include <sched.h>
  50 #include <hal.h>
  52 /*
  53  * The page structure is put on the head of the first page of
  54  * each free block.
  55  */
  56 struct page {
  57         struct page     *next;
  58         struct page     *prev;
vsize_t         size;           /* number of bytes of this block */
  60 };
  62 static struct page      page_head;      /* first free block */
  63 static psize_t          total_size;     /* size of memory in the system */
  64 static psize_t          used_size;      /* current used size */
  65 static psize_t          bootdisk_size;  /* size of the boot disk */
  67 /*
  68  * page_alloc - allocate continuous pages of the specified size.
  69  *
  70  * This routine returns the physical address of a new free page
  71  * block, or returns NULL on failure. The requested size is
  72  * automatically round up to the page boundary.  The allocated
  73  * memory is _not_ filled with 0.
  74  */
paddr_t
page_alloc(psize_t psize)
  77 {
  78         struct page *blk, *tmp;
vsize_t size;
ASSERT(psize != 0);
sched_lock();
  85         /*
  86          * Find the free block that has enough size.
  87          */
size = round_page(psize);
blk = &page_head;
  90         do {
blk = blk->next;
  92                 if (blk == &page_head) {
sched_unlock();
DPRINTF(("page_alloc: out of memory\n"));
  95                         return 0;       /* Not found. */
  96                 }
  97         } while (blk->size < size);
  99         /*
 100          * If found block size is exactly same with requested,
 101          * just remove it from a free list. Otherwise, the
 102          * found block is divided into two and first half is
 103          * used for allocation.
 104          */
 105         if (blk->size == size) {
blk->prev->next = blk->next;
blk->next->prev = blk->prev;
 108         } else {
tmp = (struct page *)((vaddr_t)blk + size);
tmp->size = blk->size - size;
tmp->prev = blk->prev;
tmp->next = blk->next;
blk->prev->next = tmp;
blk->next->prev = tmp;
 115         }
used_size += (psize_t)size;
sched_unlock();
 118         return kvtop(blk);
 119 }
 121 /*
 122  * Free page block.
 123  *
 124  * This allocator does not maintain the size of allocated page
 125  * block. The caller must provide the size information of the
 126  * block.
 127  */
 128 void
page_free(paddr_t paddr, psize_t psize)
 130 {
 131         struct page *blk, *prev;
vsize_t size;
ASSERT(psize != 0);
sched_lock();
size = round_page(psize);
blk = ptokv(paddr);
 141         /*
 142          * Find the target position in list.
 143          */
 144         for (prev = &page_head; prev->next < blk; prev = prev->next) {
 145                 if (prev->next == &page_head)
 146                         break;
 147         }
 149         /*
 150          * Insert new block into list.
 151          */
blk->size = size;
blk->prev = prev;
blk->next = prev->next;
prev->next->prev = blk;
prev->next = blk;
 158         /*
 159          * If the adjoining block is free, it combines and
 160          * is made on block.
 161          */
 162         if (blk->next != &page_head &&
 163             ((vaddr_t)blk + blk->size) == (vaddr_t)blk->next) {
blk->size += blk->next->size;
blk->next = blk->next->next;
blk->next->prev = blk;
 167         }
 168         if (blk->prev != &page_head &&
 169             (vaddr_t)blk->prev + blk->prev->size == (vaddr_t)blk) {
blk->prev->size += blk->size;
blk->prev->next = blk->next;
blk->next->prev = blk->prev;
 173         }
used_size -= (psize_t)size;
sched_unlock();
 176 }
 178 /*
 179  * The function to reserve pages in specific address.
 180  */
 181 int
page_reserve(paddr_t paddr, psize_t psize)
 183 {
 184         struct page *blk, *tmp;
vaddr_t start, end;
vsize_t size;
 188         if (psize == 0)
 189                 return 0;
start = trunc_page((vaddr_t)ptokv(paddr));
end = round_page((vaddr_t)ptokv(paddr + psize));
size = end - start;
 195         /*
 196          * Find the block which includes specified block.
 197          */
blk = page_head.next;
 199         for (;;) {
 200                 if (blk == &page_head)
 201                         return ENOMEM;
 203                 if ((vaddr_t)blk <= start
 204                     && end <= (vaddr_t)blk + blk->size)
 205                         break;
blk = blk->next;
 207         }
 208         if ((vaddr_t)blk == start && blk->size == size) {
 209                 /*
 210                  * Unlink the block from free list.
 211                  */
blk->prev->next = blk->next;
blk->next->prev = blk->prev;
 214         } else {
 215                 /*
 216                  * Split this block.
 217                  */
 218                 if ((vaddr_t)blk + blk->size != end) {
tmp = (struct page *)end;
tmp->size = (vaddr_t)blk + blk->size - end;
tmp->next = blk->next;
tmp->prev = blk;
blk->size -= tmp->size;
blk->next->prev = tmp;
blk->next = tmp;
 227                 }
 228                 if ((vaddr_t)blk == start) {
blk->prev->next = blk->next;
blk->next->prev = blk->prev;
 231                 } else
blk->size = start - (vaddr_t)blk;
 233         }
used_size += (psize_t)size;
 235         return 0;
 236 }
 238 void
page_info(struct meminfo *info)
 240 {
info->total = total_size;
info->free = total_size - used_size;
info->bootdisk = bootdisk_size;
 246 #ifndef CONFIG_ROMBOOT
 247         /*
 248          * The boot disk is placed at RAM.
 249          */
info->free -= bootdisk_size;
 251 #endif
 252 }
 254 /*
 255  * Initialize page allocator.
 256  * page_init() must be called prior to other memory manager's
 257  * initializations.
 258  */
 259 void
page_init(void)
 261 {
 262         struct physmem *ram;
 263         struct bootinfo *bi;
 264         int i;
machine_bootinfo(&bi);
total_size = 0;
bootdisk_size = 0;
page_head.next = page_head.prev = &page_head;
 272         /*
 273          * First, create a free list from the boot information.
 274          */
 275         for (i = 0; i < bi->nr_rams; i++) {
ram = &bi->ram[i];
 277                 if (ram->type == MT_USABLE) {
page_free(ram->base, ram->size);
total_size += ram->size;
 280                 }
 281         }
 282         /*
 283          * Then, reserve un-usable memory.
 284          */
 285         for (i = 0; i < bi->nr_rams; i++) {
ram = &bi->ram[i];
 287                 switch (ram->type) {
 288                 case MT_BOOTDISK:
bootdisk_size += ram->size;
 290                         /* FALLTHROUGH */
 291                 case MT_MEMHOLE:
total_size -= ram->size;
 293                         /* FALLTHROUGH */
 294                 case MT_RESERVED:
 295                         if (page_reserve(ram->base, ram->size))
panic("page_init");
 297                         break;
 298                 }
 299         }
used_size = 0;
DPRINTF(("Memory size=%ld\n", total_size));
 302 }