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