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