LXR linux-bk/mm/bootmem.c

   1/*
   2 *  linux/mm/bootmem.c
   3 *
   4 *  Copyright (C) 1999 Ingo Molnar
   5 *  Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999
   6 *
   7 *  simple boot-time physical memory area allocator and
   8 *  free memory collector. It's used to deal with reserved
   9 *  system memory and memory holes as well.
  10 */
  11
  12#include <linux/mm.h>
  13#include <linux/kernel_stat.h>
  14#include <linux/swap.h>
  15#include <linux/interrupt.h>
  16#include <linux/init.h>
  17#include <linux/bootmem.h>
  18#include <linux/mmzone.h>
  19#include <asm/dma.h>
  20#include <asm/io.h>
  21
  22/*
  23 * Access to this subsystem has to be serialized externally. (this is
  24 * true for the boot process anyway)
  25 */
  26unsigned long max_low_pfn;
  27unsigned long min_low_pfn;
  28unsigned long max_pfn;
  29
  30/* return the number of _pages_ that will be allocated for the boot bitmap */
  31unsigned long __init bootmem_bootmap_pages (unsigned long pages)
  32{
  33        unsigned long mapsize;
  34
  35        mapsize = (pages+7)/8;
  36        mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
  37        mapsize >>= PAGE_SHIFT;
  38
  39        return mapsize;
  40}
  41
  42/*
  43 * Called once to set up the allocator itself.
  44 */
  45static unsigned long __init init_bootmem_core (pg_data_t *pgdat,
  46        unsigned long mapstart, unsigned long start, unsigned long end)
  47{
  48        bootmem_data_t *bdata = pgdat->bdata;
  49        unsigned long mapsize = ((end - start)+7)/8;
  50
  51        pgdat->pgdat_next = pgdat_list;
  52        pgdat_list = pgdat;
  53
  54        mapsize = (mapsize + (sizeof(long) - 1UL)) & ~(sizeof(long) - 1UL);
  55        bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT);
  56        bdata->node_boot_start = (start << PAGE_SHIFT);
  57        bdata->node_low_pfn = end;
  58
  59        /*
  60         * Initially all pages are reserved - setup_arch() has to
  61         * register free RAM areas explicitly.
  62         */
  63        memset(bdata->node_bootmem_map, 0xff, mapsize);
  64
  65        return mapsize;
  66}
  67
  68/*
  69 * Marks a particular physical memory range as unallocatable. Usable RAM
  70 * might be used for boot-time allocations - or it might get added
  71 * to the free page pool later on.
  72 */
  73static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size)
  74{
  75        unsigned long i;
  76        /*
  77         * round up, partially reserved pages are considered
  78         * fully reserved.
  79         */
  80        unsigned long sidx = (addr - bdata->node_boot_start)/PAGE_SIZE;
  81        unsigned long eidx = (addr + size - bdata->node_boot_start + 
  82                                                        PAGE_SIZE-1)/PAGE_SIZE;
  83        unsigned long end = (addr + size + PAGE_SIZE-1)/PAGE_SIZE;
  84
  85        if (!size) BUG();
  86
  87        if (sidx < 0)
  88                BUG();
  89        if (eidx < 0)
  90                BUG();
  91        if (sidx >= eidx)
  92                BUG();
  93        if ((addr >> PAGE_SHIFT) >= bdata->node_low_pfn)
  94                BUG();
  95        if (end > bdata->node_low_pfn)
  96                BUG();
  97        for (i = sidx; i < eidx; i++)
  98                if (test_and_set_bit(i, bdata->node_bootmem_map))
  99                        printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
 100}
 101
 102static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size)
 103{
 104        unsigned long i;
 105        unsigned long start;
 106        /*
 107         * round down end of usable mem, partially free pages are
 108         * considered reserved.
 109         */
 110        unsigned long sidx;
 111        unsigned long eidx = (addr + size - bdata->node_boot_start)/PAGE_SIZE;
 112        unsigned long end = (addr + size)/PAGE_SIZE;
 113
 114        if (!size) BUG();
 115        if (end > bdata->node_low_pfn)
 116                BUG();
 117
 118        /*
 119         * Round up the beginning of the address.
 120         */
 121        start = (addr + PAGE_SIZE-1) / PAGE_SIZE;
 122        sidx = start - (bdata->node_boot_start/PAGE_SIZE);
 123
 124        for (i = sidx; i < eidx; i++) {
 125                if (!test_and_clear_bit(i, bdata->node_bootmem_map))
 126                        BUG();
 127        }
 128}
 129
 130/*
 131 * We 'merge' subsequent allocations to save space. We might 'lose'
 132 * some fraction of a page if allocations cannot be satisfied due to
 133 * size constraints on boxes where there is physical RAM space
 134 * fragmentation - in these cases * (mostly large memory boxes) this
 135 * is not a problem.
 136 *
 137 * On low memory boxes we get it right in 100% of the cases.
 138 */
 139
 140/*
 141 * alignment has to be a power of 2 value.
 142 */
 143static void * __init __alloc_bootmem_core (bootmem_data_t *bdata, 
 144        unsigned long size, unsigned long align, unsigned long goal)
 145{
 146        unsigned long i, start = 0;
 147        void *ret;
 148        unsigned long offset, remaining_size;
 149        unsigned long areasize, preferred, incr;
 150        unsigned long eidx = bdata->node_low_pfn - (bdata->node_boot_start >>
 151                                                        PAGE_SHIFT);
 152
 153        if (!size) BUG();
 154
 155        if (align & (align-1))
 156                BUG();
 157
 158        offset = 0;
 159        if (align &&
 160            (bdata->node_boot_start & (align - 1UL)) != 0)
 161                offset = (align - (bdata->node_boot_start & (align - 1UL)));
 162        offset >>= PAGE_SHIFT;
 163
 164        /*
 165         * We try to allocate bootmem pages above 'goal'
 166         * first, then we try to allocate lower pages.
 167         */
 168        if (goal && (goal >= bdata->node_boot_start) && 
 169                        ((goal >> PAGE_SHIFT) < bdata->node_low_pfn)) {
 170                preferred = goal - bdata->node_boot_start;
 171        } else
 172                preferred = 0;
 173
 174        preferred = ((preferred + align - 1) & ~(align - 1)) >> PAGE_SHIFT;
 175        preferred += offset;
 176        areasize = (size+PAGE_SIZE-1)/PAGE_SIZE;
 177        incr = align >> PAGE_SHIFT ? : 1;
 178
 179restart_scan:
 180        for (i = preferred; i < eidx; i += incr) {
 181                unsigned long j;
 182                if (test_bit(i, bdata->node_bootmem_map))
 183                        continue;
 184                for (j = i + 1; j < i + areasize; ++j) {
 185                        if (j >= eidx)
 186                                goto fail_block;
 187                        if (test_bit (j, bdata->node_bootmem_map))
 188                                goto fail_block;
 189                }
 190                start = i;
 191                goto found;
 192        fail_block:;
 193        }
 194        if (preferred) {
 195                preferred = offset;
 196                goto restart_scan;
 197        }
 198        return NULL;
 199found:
 200        if (start >= eidx)
 201                BUG();
 202
 203        /*
 204         * Is the next page of the previous allocation-end the start
 205         * of this allocation's buffer? If yes then we can 'merge'
 206         * the previous partial page with this allocation.
 207         */
 208        if (align <= PAGE_SIZE
 209            && bdata->last_offset && bdata->last_pos+1 == start) {
 210                offset = (bdata->last_offset+align-1) & ~(align-1);
 211                if (offset > PAGE_SIZE)
 212                        BUG();
 213                remaining_size = PAGE_SIZE-offset;
 214                if (size < remaining_size) {
 215                        areasize = 0;
 216                        // last_pos unchanged
 217                        bdata->last_offset = offset+size;
 218                        ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
 219                                                bdata->node_boot_start);
 220                } else {
 221                        remaining_size = size - remaining_size;
 222                        areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE;
 223                        ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
 224                                                bdata->node_boot_start);
 225                        bdata->last_pos = start+areasize-1;
 226                        bdata->last_offset = remaining_size;
 227                }
 228                bdata->last_offset &= ~PAGE_MASK;
 229        } else {
 230                bdata->last_pos = start + areasize - 1;
 231                bdata->last_offset = size & ~PAGE_MASK;
 232                ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
 233        }
 234        /*
 235         * Reserve the area now:
 236         */
 237        for (i = start; i < start+areasize; i++)
 238                if (test_and_set_bit(i, bdata->node_bootmem_map))
 239                        BUG();
 240        memset(ret, 0, size);
 241        return ret;
 242}
 243
 244static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat)
 245{
 246        struct page *page = pgdat->node_mem_map;
 247        bootmem_data_t *bdata = pgdat->bdata;
 248        unsigned long i, count, total = 0;
 249        unsigned long idx;
 250        unsigned long *map; 
 251
 252        if (!bdata->node_bootmem_map) BUG();
 253
 254        count = 0;
 255        idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 256        map = bdata->node_bootmem_map;
 257        for (i = 0; i < idx; ) {
 258                unsigned long v = ~map[i / BITS_PER_LONG];
 259                if (v) { 
 260                        unsigned long m;
 261                        for (m = 1; m && i < idx; m<<=1, page++, i++) { 
 262                                if (v & m) {
 263                        count++;
 264                        ClearPageReserved(page);
 265                        set_page_count(page, 1);
 266                        __free_page(page);
 267                }
 268        }
 269                } else {
 270                        i+=BITS_PER_LONG;
 271                        page+=BITS_PER_LONG; 
 272                }       
 273        }       
 274        total += count;
 275
 276        /*
 277         * Now free the allocator bitmap itself, it's not
 278         * needed anymore:
 279         */
 280        page = virt_to_page(bdata->node_bootmem_map);
 281        count = 0;
 282        for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) {
 283                count++;
 284                ClearPageReserved(page);
 285                set_page_count(page, 1);
 286                __free_page(page);
 287        }
 288        total += count;
 289        bdata->node_bootmem_map = NULL;
 290
 291        return total;
 292}
 293
 294unsigned long __init init_bootmem_node (pg_data_t *pgdat, unsigned long freepfn, unsigned long startpfn, unsigned long endpfn)
 295{
 296        return(init_bootmem_core(pgdat, freepfn, startpfn, endpfn));
 297}
 298
 299void __init reserve_bootmem_node (pg_data_t *pgdat, unsigned long physaddr, unsigned long size)
 300{
 301        reserve_bootmem_core(pgdat->bdata, physaddr, size);
 302}
 303
 304void __init free_bootmem_node (pg_data_t *pgdat, unsigned long physaddr, unsigned long size)
 305{
 306        return(free_bootmem_core(pgdat->bdata, physaddr, size));
 307}
 308
 309unsigned long __init free_all_bootmem_node (pg_data_t *pgdat)
 310{
 311        return(free_all_bootmem_core(pgdat));
 312}
 313
 314unsigned long __init init_bootmem (unsigned long start, unsigned long pages)
 315{
 316        max_low_pfn = pages;
 317        min_low_pfn = start;
 318        return(init_bootmem_core(&contig_page_data, start, 0, pages));
 319}
 320
 321#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
 322void __init reserve_bootmem (unsigned long addr, unsigned long size)
 323{
 324        reserve_bootmem_core(contig_page_data.bdata, addr, size);
 325}
 326#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
 327
 328void __init free_bootmem (unsigned long addr, unsigned long size)
 329{
 330        return(free_bootmem_core(contig_page_data.bdata, addr, size));
 331}
 332
 333unsigned long __init free_all_bootmem (void)
 334{
 335        return(free_all_bootmem_core(&contig_page_data));
 336}
 337
 338void * __init __alloc_bootmem (unsigned long size, unsigned long align, unsigned long goal)
 339{
 340        pg_data_t *pgdat = pgdat_list;
 341        void *ptr;
 342
 343        for_each_pgdat(pgdat)
 344                if ((ptr = __alloc_bootmem_core(pgdat->bdata, size,
 345                                                align, goal)))
 346                        return(ptr);
 347
 348        /*
 349         * Whoops, we cannot satisfy the allocation request.
 350         */
 351        printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
 352        panic("Out of memory");
 353        return NULL;
 354}
 355
 356void * __init __alloc_bootmem_node (pg_data_t *pgdat, unsigned long size, unsigned long align, unsigned long goal)
 357{
 358        void *ptr;
 359
 360        ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal);
 361        if (ptr)
 362                return (ptr);
 363
 364        /*
 365         * Whoops, we cannot satisfy the allocation request.
 366         */
 367        printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
 368        panic("Out of memory");
 369        return NULL;
 370}
 371
 372