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