kitten/mm/bootmem.c

   1 /*
   2  *  lwk/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 <lwk/init.h>
  13 #include <lwk/pfn.h>
  14 #include <lwk/bootmem.h>
  15 #include <lwk/params.h>
  16 #include <lwk/log2.h>
  17 #include <lwk/pmem.h>
  18 #include <lwk/kmem.h>
  19 #include <lwk/bitops.h>
  20 #include <arch/io.h>
  21
  22 /**
  23  * Set to true once bootmem allocator has been destroyed.
  24  */
  25 static bool bootmem_destoyed = false;
  26
  27 /**
  28  * Access to this subsystem has to be serialized externally.
  29  * (this is true for the boot process anyway)
  30  */
  31
  32
  33 /**
  34  * Amount of system memory to reserve for use by the kernel. The first
  35  * kmem_size bytes of system memory [0, kmem_size) will be added to the
  36  * kernel memory pool. The remainder of system memory is left untouched by
  37  * the kernel and is available for use by applications.
  38  */
  39 static unsigned long kmem_size = (1024 * 1024 * 8);  /* default is first 8 MB */
  40 param(kmem_size, ulong);
  41
  42
  43 /**
  44  *
  45  */
  46 static bootmem_data_t __initdata bootmem_data;
  47
  48 /**
  49  * List of bootmem_data structures, each describing a section of
  50  * physical memory.
  51  */
  52 static LIST_HEAD(bdata_list);
  53
  54 /**
  55  * Returns the number of _pages_ that will be allocated for the boot bitmap.
  56  */
  57 unsigned long __init
  58 bootmem_bootmap_pages(unsigned long pages)
  59 {
  60         unsigned long mapsize;
  61
  62         mapsize = (pages+7)/8;
  63         mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK;
  64         mapsize >>= PAGE_SHIFT;
  65
  66         return mapsize;
  67 }
  68
  69 /**
  70  * Links a newly created bootmem_data structure to the bdata_list.
  71  */
  72 static void __init
  73 link_bootmem(bootmem_data_t *bdata)
  74 {
  75         bootmem_data_t *ent;
  76         if (list_empty(&bdata_list)) {
  77                 list_add(&bdata->list, &bdata_list);
  78                 return;
  79         }
  80         /* insert in order */
  81         list_for_each_entry(ent, &bdata_list, list) {
  82                 if (bdata->node_boot_start < ent->node_boot_start) {
  83                         list_add_tail(&bdata->list, &ent->list);
  84                         return;
  85                 }
  86         }
  87         list_add_tail(&bdata->list, &bdata_list);
  88         return;
  89 }
  90
  91 /**
  92  * Called once to set up the allocator itself.
  93  */
  94 static unsigned long __init
  95 init_bootmem_core(
  96         bootmem_data_t  *bdata,
  97         unsigned long   mapstart,
  98         unsigned long   start,
  99         unsigned long   end
 100 )
 101 {
 102         unsigned long mapsize = ((end - start)+7)/8;
 103
 104         mapsize = ALIGN(mapsize, sizeof(long));
 105         bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT);
 106         bdata->node_boot_start = (start << PAGE_SHIFT);
 107         bdata->node_low_pfn = end;
 108         link_bootmem(bdata);
 109
 110         /*
 111          * Initially all pages are reserved - setup_arch() has to
 112          * register free RAM areas explicitly.
 113          */
 114         memset(bdata->node_bootmem_map, 0xff, mapsize);
 115
 116         return mapsize;
 117 }
 118
 119 /**
 120  * Marks a particular physical memory range as unallocatable. Usable RAM
 121  * might be used for boot-time allocations - or it might get added
 122  * to the free page pool later on.
 123  */
 124 static void __init
 125 reserve_bootmem_core(
 126         bootmem_data_t  *bdata,
 127         unsigned long   addr,
 128         unsigned long   size
 129 )
 130 {
 131         unsigned long sidx, eidx;
 132         unsigned long i;
 133
 134         /*
 135          * round up, partially reserved pages are considered
 136          * fully reserved.
 137          */
 138         BUG_ON(!size);
 139         BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
 140         BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);
 141
 142         sidx = PFN_DOWN(addr - bdata->node_boot_start);
 143         eidx = PFN_UP(addr + size - bdata->node_boot_start);
 144
 145         for (i = sidx; i < eidx; i++) {
 146                 if (test_and_set_bit(i, bdata->node_bootmem_map)) {
 147 #ifdef CONFIG_DEBUG_BOOTMEM
 148                         printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
 149 #endif
 150                 }
 151         }
 152 }
 153
 154 /**
 155  * Frees a section of bootmemory.
 156  */
 157 static void __init
 158 free_bootmem_core(
 159         bootmem_data_t  *bdata,
 160         unsigned long   addr,
 161         unsigned long   size
 162 )
 163 {
 164         unsigned long i;
 165         unsigned long start;
 166         /*
 167          * round down end of usable mem, partially free pages are
 168          * considered reserved.
 169          */
 170         unsigned long sidx;
 171         unsigned long eidx = (addr + size - bdata->node_boot_start)/PAGE_SIZE;
 172         unsigned long end = (addr + size)/PAGE_SIZE;
 173
 174         BUG_ON(!size);
 175         BUG_ON(end > bdata->node_low_pfn);
 176
 177         if (addr < bdata->last_success)
 178                 bdata->last_success = addr;
 179
 180         /*
 181          * Round up the beginning of the address.
 182          */
 183         start = (addr + PAGE_SIZE-1) / PAGE_SIZE;
 184         sidx = start - (bdata->node_boot_start/PAGE_SIZE);
 185
 186         for (i = sidx; i < eidx; i++) {
 187                 if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
 188                         BUG();
 189         }
 190 }
 191
 192 /**
 193  * We 'merge' subsequent allocations to save space. We might 'lose'
 194  * some fraction of a page if allocations cannot be satisfied due to
 195  * size constraints on boxes where there is physical RAM space
 196  * fragmentation - in these cases (mostly large memory boxes) this
 197  * is not a problem.
 198  *
 199  * On low memory boxes we get it right in 100% of the cases.
 200  *
 201  * alignment has to be a power of 2 value.
 202  *
 203  * NOTE:  This function is _not_ reentrant.
 204  */
 205 void * __init
 206 __alloc_bootmem_core(
 207         struct bootmem_data     *bdata,
 208         unsigned long           size,
 209         unsigned long           align,
 210         unsigned long           goal,
 211         unsigned long           limit
 212 )
 213 {
 214         unsigned long offset, remaining_size, areasize, preferred;
 215         unsigned long i, start = 0, incr, eidx, end_pfn = bdata->node_low_pfn;
 216         void *ret;
 217
 218         if (bootmem_destoyed)
 219                 panic("The bootmem allocator has been destroyed.");
 220
 221         if(!size) {
 222                 printk("__alloc_bootmem_core(): zero-sized request\n");
 223                 BUG();
 224         }
 225         BUG_ON(align & (align-1));
 226
 227         if (limit && bdata->node_boot_start >= limit)
 228                 return NULL;
 229
 230         limit >>=PAGE_SHIFT;
 231         if (limit && end_pfn > limit)
 232                 end_pfn = limit;
 233
 234         eidx = end_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 235         offset = 0;
 236         if (align &&
 237             (bdata->node_boot_start & (align - 1UL)) != 0)
 238                 offset = (align - (bdata->node_boot_start & (align - 1UL)));
 239         offset >>= PAGE_SHIFT;
 240
 241         /*
 242          * We try to allocate bootmem pages above 'goal'
 243          * first, then we try to allocate lower pages.
 244          */
 245         if (goal && (goal >= bdata->node_boot_start) &&
 246             ((goal >> PAGE_SHIFT) < end_pfn)) {
 247                 preferred = goal - bdata->node_boot_start;
 248
 249                 if (bdata->last_success >= preferred)
 250                         if (!limit || (limit && limit > bdata->last_success))
 251                                 preferred = bdata->last_success;
 252         } else
 253                 preferred = 0;
 254
 255         preferred = ALIGN(preferred, align) >> PAGE_SHIFT;
 256         preferred += offset;
 257         areasize = (size+PAGE_SIZE-1)/PAGE_SIZE;
 258         incr = align >> PAGE_SHIFT ? : 1;
 259
 260 restart_scan:
 261         for (i = preferred; i < eidx; i += incr) {
 262                 unsigned long j;
 263                 i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);
 264                 i = ALIGN(i, incr);
 265                 if (i >= eidx)
 266                         break;
 267                 if (test_bit(i, bdata->node_bootmem_map))
 268                         continue;
 269                 for (j = i + 1; j < i + areasize; ++j) {
 270                         if (j >= eidx)
 271                                 goto fail_block;
 272                         if (test_bit (j, bdata->node_bootmem_map))
 273                                 goto fail_block;
 274                 }
 275                 start = i;
 276                 goto found;
 277         fail_block:
 278                 i = ALIGN(j, incr);
 279         }
 280
 281         if (preferred > offset) {
 282                 preferred = offset;
 283                 goto restart_scan;
 284         }
 285         return NULL;
 286
 287 found:
 288         bdata->last_success = start << PAGE_SHIFT;
 289         BUG_ON(start >= eidx);
 290
 291         /*
 292          * Is the next page of the previous allocation-end the start
 293          * of this allocation's buffer? If yes then we can 'merge'
 294          * the previous partial page with this allocation.
 295          */
 296         if (align < PAGE_SIZE &&
 297             bdata->last_offset && bdata->last_pos+1 == start) {
 298                 offset = ALIGN(bdata->last_offset, align);
 299                 BUG_ON(offset > PAGE_SIZE);
 300                 remaining_size = PAGE_SIZE-offset;
 301                 if (size < remaining_size) {
 302                         areasize = 0;
 303                         /* last_pos unchanged */
 304                         bdata->last_offset = offset+size;
 305                         ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
 306                                                 bdata->node_boot_start);
 307                 } else {
 308                         remaining_size = size - remaining_size;
 309                         areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE;
 310                         ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset +
 311                                                 bdata->node_boot_start);
 312                         bdata->last_pos = start+areasize-1;
 313                         bdata->last_offset = remaining_size;
 314                 }
 315                 bdata->last_offset &= ~PAGE_MASK;
 316         } else {
 317                 bdata->last_pos = start + areasize - 1;
 318                 bdata->last_offset = size & ~PAGE_MASK;
 319                 ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
 320         }
 321
 322         /*
 323          * Reserve the area now:
 324          */
 325         for (i = start; i < start+areasize; i++)
 326                 if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
 327                         BUG();
 328         memset(ret, 0, size);
 329         return ret;
 330 }
 331
 332 static void __init
 333 free_all_bootmem_core(struct bootmem_data *bdata)
 334 {
 335         unsigned long pfn;
 336         unsigned long vaddr;
 337         unsigned long i, m, count;
 338         unsigned long bootmem_total=0, kmem_total=0, umem_total=0;
 339         unsigned long kmem_max_idx, max_idx;
 340         unsigned long *map;
 341         struct pmem_region rgn;
 342
 343         BUG_ON(!bdata->node_bootmem_map);
 344
 345         kmem_max_idx = (kmem_size >> PAGE_SHIFT) - (bdata->node_boot_start >> PAGE_SHIFT);
 346         max_idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 347         BUG_ON(kmem_max_idx > max_idx);
 348
 349         /* Create the initial kernel managed memory pool (kmem) */
 350         count = 0;
 351         pfn = bdata->node_boot_start >> PAGE_SHIFT;  /* first extant page of node */
 352         map = bdata->node_bootmem_map;
 353         for (i = 0; i < kmem_max_idx; ) {
 354                 unsigned long v = ~map[i / BITS_PER_LONG];
 355
 356                 if (v) {
 357                         vaddr = (unsigned long) __va(pfn << PAGE_SHIFT);
 358                         for (m = 1; m && i < kmem_max_idx; m<<=1, vaddr+=PAGE_SIZE, i++) {
 359                                 if (v & m) {
 360                                         count++;
 361                                         kmem_add_memory(vaddr, PAGE_SIZE);
 362                                 }
 363                         }
 364                 } else {
 365                         i+=BITS_PER_LONG;
 366                 }
 367                 pfn += BITS_PER_LONG;
 368         }
 369         BUG_ON(count == 0);
 370
 371         /*
 372          * At this point, kmem_alloc() will work. The physical memory tracking
 373          * code relies on kmem_alloc(), so it cannot be initialized until now.
 374          *
 375          * Tell the physical memory tracking subsystem about the kernel-managed
 376          * pool and the remaining memory that will be managed by user-space.
 377          */
 378         pfn = bdata->node_boot_start >> PAGE_SHIFT;  /* first extant page of node */
 379         map = bdata->node_bootmem_map;
 380         pmem_region_unset_all(&rgn);
 381         rgn.type_is_set = true;
 382         rgn.allocated_is_set = true;
 383         rgn.lgroup_is_set = true;
 384         for (i = 0; i < max_idx; ) {
 385                 unsigned long v = ~map[i / BITS_PER_LONG];
 386                 unsigned long paddr = (unsigned long) pfn << PAGE_SHIFT;
 387
 388                 for (m = 1; m && i < max_idx; m<<=1, paddr+=PAGE_SIZE, i++) {
 389                         rgn.start = paddr;
 390                         rgn.end   = paddr + PAGE_SIZE;
 391
 392                         if (v & m) {
 393                                 if (i < kmem_max_idx) {
 394                                         rgn.type = PMEM_TYPE_KMEM;
 395                                         rgn.allocated = true;
 396                                         rgn.lgroup = 0;
 397                                         ++kmem_total;
 398                                 } else {
 399                                         rgn.type = PMEM_TYPE_UMEM;
 400                                         rgn.allocated = false;
 401                                         rgn.lgroup = 0;
 402                                         ++umem_total;
 403                                 }
 404                         } else {
 405                                 rgn.type = PMEM_TYPE_BOOTMEM;
 406                                 rgn.allocated = true;
 407                                 rgn.lgroup = 0;
 408                                 ++bootmem_total;
 409                         }
 410
 411                         if (pmem_add(&rgn))
 412                                 BUG();
 413                 }
 414
 415                 pfn += BITS_PER_LONG;
 416         }
 417
 418         /*
 419          * Now free the allocator bitmap itself, it's not
 420          * needed anymore:
 421          */
 422         vaddr = (unsigned long)bdata->node_bootmem_map;
 423         count = 0;
 424         pmem_region_unset_all(&rgn);
 425         rgn.type_is_set = true;
 426         rgn.allocated_is_set = true;
 427         rgn.lgroup_is_set = true;
 428         for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,vaddr+=PAGE_SIZE) {
 429                 count++;
 430
 431                 rgn.start = __pa(vaddr);
 432                 rgn.end   = rgn.start + PAGE_SIZE;
 433
 434                 if (i < kmem_max_idx) {
 435                         kmem_add_memory(vaddr, PAGE_SIZE);
 436                         rgn.type = PMEM_TYPE_KMEM;
 437                         rgn.allocated = true;
 438                         rgn.lgroup = 0;
 439                 } else {
 440                         rgn.type = PMEM_TYPE_UMEM;
 441                         rgn.allocated = false;
 442                         rgn.lgroup = 0;
 443                 }
 444
 445                 pmem_add(&rgn);
 446         }
 447         BUG_ON(count == 0);
 448
 449         /* Mark the bootmem allocator as dead */
 450         bdata->node_bootmem_map = NULL;
 451
 452         printk(KERN_DEBUG
 453                "The boot-strap bootmem allocator has been destroyed:\n");
 454         printk(KERN_DEBUG
 455                "  %lu bytes released to the kernel-managed memory pool (kmem)\n",
 456                kmem_total << PAGE_SHIFT);
 457         printk(KERN_DEBUG
 458                "  %lu bytes released to the user-managed memory pool (umem)\n",
 459                umem_total << PAGE_SHIFT);
 460 }
 461
 462 /**
 463  * Initialize boot memory allocator.
 464  */
 465 unsigned long __init
 466 init_bootmem(unsigned long start, unsigned long pages)
 467 {
 468         return init_bootmem_core(&bootmem_data, start, 0, pages);
 469 }
 470
 471 /**
 472  * Reserve a portion of the boot memory.
 473  * This prevents the reserved memory from being allocated.
 474  */
 475 void __init
 476 reserve_bootmem(unsigned long addr, unsigned long size)
 477 {
 478         reserve_bootmem_core(&bootmem_data, addr, size);
 479 }
 480
 481 /**
 482  * Return a portion of boot memory to the free pool.
 483  * Note that the region freed is the set of pages covering
 484  * the byte range [addr, addr+size).
 485  */
 486 void __init
 487 free_bootmem(unsigned long addr, unsigned long size)
 488 {
 489         free_bootmem_core(&bootmem_data, addr, size);
 490 }
 491
 492 void __init
 493 free_all_bootmem(void)
 494 {
 495         free_all_bootmem_core(&bootmem_data);
 496         bootmem_destoyed = true;
 497 }
 498
 499 static void * __init
 500 __alloc_bootmem_nopanic(unsigned long size, unsigned long align, unsigned long goal)
 501 {
 502         bootmem_data_t *bdata;
 503         void *ptr;
 504
 505         list_for_each_entry(bdata, &bdata_list, list)
 506                 if ((ptr = __alloc_bootmem_core(bdata, size, align, goal, 0)))
 507                         return(ptr);
 508         return NULL;
 509 }
 510
 511 /**
 512  * Allocate a chunk of memory from the boot memory allocator.
 513  *
 514  *     size  = number of bytes requested
 515  *     align = required alignment
 516  *     goal  = hint specifying address to start search.
 517  */
 518 void * __init
 519 __alloc_bootmem(unsigned long size, unsigned long align, unsigned long goal)
 520 {
 521         void *mem = __alloc_bootmem_nopanic(size,align,goal);
 522         if (mem)
 523                 return mem;
 524         /*
 525          * Whoops, we cannot satisfy the allocation request.
 526          */
 527         printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
 528         panic("Out of memory");
 529         return NULL;
 530 }
 531
 532 /**
 533  * Allocates a block of memory of the specified size.
 534  */
 535 void * __init
 536 alloc_bootmem(unsigned long size)
 537 {
 538         return __alloc_bootmem(size, SMP_CACHE_BYTES, 0);
 539 }
 540
 541 /**
 542  * Allocates a block of memory of the specified size and alignment.
 543  */
 544 void * __init
 545 alloc_bootmem_aligned(unsigned long size, unsigned long align)
 546 {
 547         return __alloc_bootmem(size, align, 0);
 548 }
 549
 550 /**
 551  * Initializes the kernel memory subsystem.
 552  */
 553 void __init
 554 mem_subsys_init(void)
 555 {
 556         /* We like powers of two */
 557         if (!is_power_of_2(kmem_size)) {
 558                 printk(KERN_WARNING "kmem_size must be a power of two.");
 559                 kmem_size = roundup_pow_of_two(kmem_size);
 560         }
 561
 562         printk(KERN_DEBUG
 563                "First %lu bytes of system memory reserved for the kernel.\n",
 564                kmem_size);
 565
 566         /* Initialize the kernel memory pool */
 567         kmem_create_zone(PAGE_OFFSET, kmem_size);
 568         free_all_bootmem();
 569         arch_memsys_init(kmem_size);
 570 }
 571