mm/memblock.c

   1 /*
   2  * Procedures for maintaining information about logical memory blocks.
   3  *
   4  * Peter Bergner, IBM Corp.     June 2001.
   5  * Copyright (C) 2001 Peter Bergner.
   6  *
   7  *      This program is free software; you can redistribute it and/or
   8  *      modify it under the terms of the GNU General Public License
   9  *      as published by the Free Software Foundation; either version
  10  *      2 of the License, or (at your option) any later version.
  11  */
  12
  13 #include <linux/kernel.h>
  14 #include <linux/init.h>
  15 #include <linux/bitops.h>
  16 #include <linux/poison.h>
  17 #include <linux/memblock.h>
  18
  19 struct memblock memblock;
  20
  21 static int memblock_debug;
  22 static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS + 1];
  23 static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS + 1];
  24
  25 static int __init early_memblock(char *p)
  26 {
  27         if (p && strstr(p, "debug"))
  28                 memblock_debug = 1;
  29         return 0;
  30 }
  31 early_param("memblock", early_memblock);
  32
  33 static void memblock_dump(struct memblock_type *region, char *name)
  34 {
  35         unsigned long long base, size;
  36         int i;
  37
  38         pr_info(" %s.cnt  = 0x%lx\n", name, region->cnt);
  39
  40         for (i = 0; i < region->cnt; i++) {
  41                 base = region->regions[i].base;
  42                 size = region->regions[i].size;
  43
  44                 pr_info(" %s[0x%x]\t0x%016llx - 0x%016llx, 0x%llx bytes\n",
  45                     name, i, base, base + size - 1, size);
  46         }
  47 }
  48
  49 void memblock_dump_all(void)
  50 {
  51         if (!memblock_debug)
  52                 return;
  53
  54         pr_info("MEMBLOCK configuration:\n");
  55         pr_info(" memory size = 0x%llx\n", (unsigned long long)memblock.memory_size);
  56
  57         memblock_dump(&memblock.memory, "memory");
  58         memblock_dump(&memblock.reserved, "reserved");
  59 }
  60
  61 static unsigned long memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
  62                                        phys_addr_t base2, phys_addr_t size2)
  63 {
  64         return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
  65 }
  66
  67 static long memblock_addrs_adjacent(phys_addr_t base1, phys_addr_t size1,
  68                                phys_addr_t base2, phys_addr_t size2)
  69 {
  70         if (base2 == base1 + size1)
  71                 return 1;
  72         else if (base1 == base2 + size2)
  73                 return -1;
  74
  75         return 0;
  76 }
  77
  78 static long memblock_regions_adjacent(struct memblock_type *type,
  79                                  unsigned long r1, unsigned long r2)
  80 {
  81         phys_addr_t base1 = type->regions[r1].base;
  82         phys_addr_t size1 = type->regions[r1].size;
  83         phys_addr_t base2 = type->regions[r2].base;
  84         phys_addr_t size2 = type->regions[r2].size;
  85
  86         return memblock_addrs_adjacent(base1, size1, base2, size2);
  87 }
  88
  89 static void memblock_remove_region(struct memblock_type *type, unsigned long r)
  90 {
  91         unsigned long i;
  92
  93         for (i = r; i < type->cnt - 1; i++) {
  94                 type->regions[i].base = type->regions[i + 1].base;
  95                 type->regions[i].size = type->regions[i + 1].size;
  96         }
  97         type->cnt--;
  98 }
  99
 100 /* Assumption: base addr of region 1 < base addr of region 2 */
 101 static void memblock_coalesce_regions(struct memblock_type *type,
 102                 unsigned long r1, unsigned long r2)
 103 {
 104         type->regions[r1].size += type->regions[r2].size;
 105         memblock_remove_region(type, r2);
 106 }
 107
 108 void __init memblock_init(void)
 109 {
 110         /* Hookup the initial arrays */
 111         memblock.memory.regions = memblock_memory_init_regions;
 112         memblock.memory.max             = INIT_MEMBLOCK_REGIONS;
 113         memblock.reserved.regions       = memblock_reserved_init_regions;
 114         memblock.reserved.max   = INIT_MEMBLOCK_REGIONS;
 115
 116         /* Write a marker in the unused last array entry */
 117         memblock.memory.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
 118         memblock.reserved.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
 119
 120         /* Create a dummy zero size MEMBLOCK which will get coalesced away later.
 121          * This simplifies the memblock_add() code below...
 122          */
 123         memblock.memory.regions[0].base = 0;
 124         memblock.memory.regions[0].size = 0;
 125         memblock.memory.cnt = 1;
 126
 127         /* Ditto. */
 128         memblock.reserved.regions[0].base = 0;
 129         memblock.reserved.regions[0].size = 0;
 130         memblock.reserved.cnt = 1;
 131
 132         memblock.current_limit = MEMBLOCK_ALLOC_ANYWHERE;
 133 }
 134
 135 void __init memblock_analyze(void)
 136 {
 137         int i;
 138
 139         /* Check marker in the unused last array entry */
 140         WARN_ON(memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS].base
 141                 != (phys_addr_t)RED_INACTIVE);
 142         WARN_ON(memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS].base
 143                 != (phys_addr_t)RED_INACTIVE);
 144
 145         memblock.memory_size = 0;
 146
 147         for (i = 0; i < memblock.memory.cnt; i++)
 148                 memblock.memory_size += memblock.memory.regions[i].size;
 149 }
 150
 151 static long memblock_add_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
 152 {
 153         unsigned long coalesced = 0;
 154         long adjacent, i;
 155
 156         if ((type->cnt == 1) && (type->regions[0].size == 0)) {
 157                 type->regions[0].base = base;
 158                 type->regions[0].size = size;
 159                 return 0;
 160         }
 161
 162         /* First try and coalesce this MEMBLOCK with another. */
 163         for (i = 0; i < type->cnt; i++) {
 164                 phys_addr_t rgnbase = type->regions[i].base;
 165                 phys_addr_t rgnsize = type->regions[i].size;
 166
 167                 if ((rgnbase == base) && (rgnsize == size))
 168                         /* Already have this region, so we're done */
 169                         return 0;
 170
 171                 adjacent = memblock_addrs_adjacent(base, size, rgnbase, rgnsize);
 172                 if (adjacent > 0) {
 173                         type->regions[i].base -= size;
 174                         type->regions[i].size += size;
 175                         coalesced++;
 176                         break;
 177                 } else if (adjacent < 0) {
 178                         type->regions[i].size += size;
 179                         coalesced++;
 180                         break;
 181                 }
 182         }
 183
 184         if ((i < type->cnt - 1) && memblock_regions_adjacent(type, i, i+1)) {
 185                 memblock_coalesce_regions(type, i, i+1);
 186                 coalesced++;
 187         }
 188
 189         if (coalesced)
 190                 return coalesced;
 191         if (type->cnt >= type->max)
 192                 return -1;
 193
 194         /* Couldn't coalesce the MEMBLOCK, so add it to the sorted table. */
 195         for (i = type->cnt - 1; i >= 0; i--) {
 196                 if (base < type->regions[i].base) {
 197                         type->regions[i+1].base = type->regions[i].base;
 198                         type->regions[i+1].size = type->regions[i].size;
 199                 } else {
 200                         type->regions[i+1].base = base;
 201                         type->regions[i+1].size = size;
 202                         break;
 203                 }
 204         }
 205
 206         if (base < type->regions[0].base) {
 207                 type->regions[0].base = base;
 208                 type->regions[0].size = size;
 209         }
 210         type->cnt++;
 211
 212         return 0;
 213 }
 214
 215 long memblock_add(phys_addr_t base, phys_addr_t size)
 216 {
 217         return memblock_add_region(&memblock.memory, base, size);
 218
 219 }
 220
 221 static long __memblock_remove(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
 222 {
 223         phys_addr_t rgnbegin, rgnend;
 224         phys_addr_t end = base + size;
 225         int i;
 226
 227         rgnbegin = rgnend = 0; /* supress gcc warnings */
 228
 229         /* Find the region where (base, size) belongs to */
 230         for (i=0; i < type->cnt; i++) {
 231                 rgnbegin = type->regions[i].base;
 232                 rgnend = rgnbegin + type->regions[i].size;
 233
 234                 if ((rgnbegin <= base) && (end <= rgnend))
 235                         break;
 236         }
 237
 238         /* Didn't find the region */
 239         if (i == type->cnt)
 240                 return -1;
 241
 242         /* Check to see if we are removing entire region */
 243         if ((rgnbegin == base) && (rgnend == end)) {
 244                 memblock_remove_region(type, i);
 245                 return 0;
 246         }
 247
 248         /* Check to see if region is matching at the front */
 249         if (rgnbegin == base) {
 250                 type->regions[i].base = end;
 251                 type->regions[i].size -= size;
 252                 return 0;
 253         }
 254
 255         /* Check to see if the region is matching at the end */
 256         if (rgnend == end) {
 257                 type->regions[i].size -= size;
 258                 return 0;
 259         }
 260
 261         /*
 262          * We need to split the entry -  adjust the current one to the
 263          * beginging of the hole and add the region after hole.
 264          */
 265         type->regions[i].size = base - type->regions[i].base;
 266         return memblock_add_region(type, end, rgnend - end);
 267 }
 268
 269 long memblock_remove(phys_addr_t base, phys_addr_t size)
 270 {
 271         return __memblock_remove(&memblock.memory, base, size);
 272 }
 273
 274 long __init memblock_free(phys_addr_t base, phys_addr_t size)
 275 {
 276         return __memblock_remove(&memblock.reserved, base, size);
 277 }
 278
 279 long __init memblock_reserve(phys_addr_t base, phys_addr_t size)
 280 {
 281         struct memblock_type *_rgn = &memblock.reserved;
 282
 283         BUG_ON(0 == size);
 284
 285         return memblock_add_region(_rgn, base, size);
 286 }
 287
 288 long memblock_overlaps_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
 289 {
 290         unsigned long i;
 291
 292         for (i = 0; i < type->cnt; i++) {
 293                 phys_addr_t rgnbase = type->regions[i].base;
 294                 phys_addr_t rgnsize = type->regions[i].size;
 295                 if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
 296                         break;
 297         }
 298
 299         return (i < type->cnt) ? i : -1;
 300 }
 301
 302 static phys_addr_t memblock_align_down(phys_addr_t addr, phys_addr_t size)
 303 {
 304         return addr & ~(size - 1);
 305 }
 306
 307 static phys_addr_t memblock_align_up(phys_addr_t addr, phys_addr_t size)
 308 {
 309         return (addr + (size - 1)) & ~(size - 1);
 310 }
 311
 312 static phys_addr_t __init memblock_find_region(phys_addr_t start, phys_addr_t end,
 313                                           phys_addr_t size, phys_addr_t align)
 314 {
 315         phys_addr_t base, res_base;
 316         long j;
 317
 318         base = memblock_align_down((end - size), align);
 319         while (start <= base) {
 320                 j = memblock_overlaps_region(&memblock.reserved, base, size);
 321                 if (j < 0)
 322                         return base;
 323                 res_base = memblock.reserved.regions[j].base;
 324                 if (res_base < size)
 325                         break;
 326                 base = memblock_align_down(res_base - size, align);
 327         }
 328
 329         return ~(phys_addr_t)0;
 330 }
 331
 332 phys_addr_t __weak __init memblock_nid_range(phys_addr_t start, phys_addr_t end, int *nid)
 333 {
 334         *nid = 0;
 335
 336         return end;
 337 }
 338
 339 static phys_addr_t __init memblock_alloc_nid_region(struct memblock_region *mp,
 340                                                phys_addr_t size,
 341                                                phys_addr_t align, int nid)
 342 {
 343         phys_addr_t start, end;
 344
 345         start = mp->base;
 346         end = start + mp->size;
 347
 348         start = memblock_align_up(start, align);
 349         while (start < end) {
 350                 phys_addr_t this_end;
 351                 int this_nid;
 352
 353                 this_end = memblock_nid_range(start, end, &this_nid);
 354                 if (this_nid == nid) {
 355                         phys_addr_t ret = memblock_find_region(start, this_end, size, align);
 356                         if (ret != ~(phys_addr_t)0 &&
 357                             memblock_add_region(&memblock.reserved, ret, size) >= 0)
 358                                 return ret;
 359                 }
 360                 start = this_end;
 361         }
 362
 363         return ~(phys_addr_t)0;
 364 }
 365
 366 phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
 367 {
 368         struct memblock_type *mem = &memblock.memory;
 369         int i;
 370
 371         BUG_ON(0 == size);
 372
 373         /* We do a bottom-up search for a region with the right
 374          * nid since that's easier considering how memblock_nid_range()
 375          * works
 376          */
 377         size = memblock_align_up(size, align);
 378
 379         for (i = 0; i < mem->cnt; i++) {
 380                 phys_addr_t ret = memblock_alloc_nid_region(&mem->regions[i],
 381                                                size, align, nid);
 382                 if (ret != ~(phys_addr_t)0)
 383                         return ret;
 384         }
 385
 386         return memblock_alloc(size, align);
 387 }
 388
 389 phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
 390 {
 391         return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
 392 }
 393
 394 phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
 395 {
 396         phys_addr_t alloc;
 397
 398         alloc = __memblock_alloc_base(size, align, max_addr);
 399
 400         if (alloc == 0)
 401                 panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
 402                       (unsigned long long) size, (unsigned long long) max_addr);
 403
 404         return alloc;
 405 }
 406
 407 phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
 408 {
 409         long i;
 410         phys_addr_t base = 0;
 411         phys_addr_t res_base;
 412
 413         BUG_ON(0 == size);
 414
 415         size = memblock_align_up(size, align);
 416
 417         /* Pump up max_addr */
 418         if (max_addr == MEMBLOCK_ALLOC_ACCESSIBLE)
 419                 max_addr = memblock.current_limit;
 420
 421         /* We do a top-down search, this tends to limit memory
 422          * fragmentation by keeping early boot allocs near the
 423          * top of memory
 424          */
 425         for (i = memblock.memory.cnt - 1; i >= 0; i--) {
 426                 phys_addr_t memblockbase = memblock.memory.regions[i].base;
 427                 phys_addr_t memblocksize = memblock.memory.regions[i].size;
 428
 429                 if (memblocksize < size)
 430                         continue;
 431                 base = min(memblockbase + memblocksize, max_addr);
 432                 res_base = memblock_find_region(memblockbase, base, size, align);
 433                 if (res_base != ~(phys_addr_t)0 &&
 434                     memblock_add_region(&memblock.reserved, res_base, size) >= 0)
 435                         return res_base;
 436         }
 437         return 0;
 438 }
 439
 440 /* You must call memblock_analyze() before this. */
 441 phys_addr_t __init memblock_phys_mem_size(void)
 442 {
 443         return memblock.memory_size;
 444 }
 445
 446 phys_addr_t memblock_end_of_DRAM(void)
 447 {
 448         int idx = memblock.memory.cnt - 1;
 449
 450         return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
 451 }
 452
 453 /* You must call memblock_analyze() after this. */
 454 void __init memblock_enforce_memory_limit(phys_addr_t memory_limit)
 455 {
 456         unsigned long i;
 457         phys_addr_t limit;
 458         struct memblock_region *p;
 459
 460         if (!memory_limit)
 461                 return;
 462
 463         /* Truncate the memblock regions to satisfy the memory limit. */
 464         limit = memory_limit;
 465         for (i = 0; i < memblock.memory.cnt; i++) {
 466                 if (limit > memblock.memory.regions[i].size) {
 467                         limit -= memblock.memory.regions[i].size;
 468                         continue;
 469                 }
 470
 471                 memblock.memory.regions[i].size = limit;
 472                 memblock.memory.cnt = i + 1;
 473                 break;
 474         }
 475
 476         memory_limit = memblock_end_of_DRAM();
 477
 478         /* And truncate any reserves above the limit also. */
 479         for (i = 0; i < memblock.reserved.cnt; i++) {
 480                 p = &memblock.reserved.regions[i];
 481
 482                 if (p->base > memory_limit)
 483                         p->size = 0;
 484                 else if ((p->base + p->size) > memory_limit)
 485                         p->size = memory_limit - p->base;
 486
 487                 if (p->size == 0) {
 488                         memblock_remove_region(&memblock.reserved, i);
 489                         i--;
 490                 }
 491         }
 492 }
 493
 494 static int memblock_search(struct memblock_type *type, phys_addr_t addr)
 495 {
 496         unsigned int left = 0, right = type->cnt;
 497
 498         do {
 499                 unsigned int mid = (right + left) / 2;
 500
 501                 if (addr < type->regions[mid].base)
 502                         right = mid;
 503                 else if (addr >= (type->regions[mid].base +
 504                                   type->regions[mid].size))
 505                         left = mid + 1;
 506                 else
 507                         return mid;
 508         } while (left < right);
 509         return -1;
 510 }
 511
 512 int __init memblock_is_reserved(phys_addr_t addr)
 513 {
 514         return memblock_search(&memblock.reserved, addr) != -1;
 515 }
 516
 517 int memblock_is_memory(phys_addr_t addr)
 518 {
 519         return memblock_search(&memblock.memory, addr) != -1;
 520 }
 521
 522 int memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
 523 {
 524         int idx = memblock_search(&memblock.reserved, base);
 525
 526         if (idx == -1)
 527                 return 0;
 528         return memblock.reserved.regions[idx].base <= base &&
 529                 (memblock.reserved.regions[idx].base +
 530                  memblock.reserved.regions[idx].size) >= (base + size);
 531 }
 532
 533 int memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
 534 {
 535         return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
 536 }
 537
 538
 539 void __init memblock_set_current_limit(phys_addr_t limit)
 540 {
 541         memblock.current_limit = limit;
 542 }
 543