memblock.c revision 3a9c2c81eb2024c136cc534df534f93682d516d0
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 25static int __init early_memblock(char *p) 26{ 27 if (p && strstr(p, "debug")) 28 memblock_debug = 1; 29 return 0; 30} 31early_param("memblock", early_memblock); 32 33static 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 49void 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 61static 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 67static 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 78static 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 89static 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 */ 101static 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 108void __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 135void __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 151static 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 215long memblock_add(phys_addr_t base, phys_addr_t size) 216{ 217 return memblock_add_region(&memblock.memory, base, size); 218 219} 220 221static 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 269long memblock_remove(phys_addr_t base, phys_addr_t size) 270{ 271 return __memblock_remove(&memblock.memory, base, size); 272} 273 274long __init memblock_free(phys_addr_t base, phys_addr_t size) 275{ 276 return __memblock_remove(&memblock.reserved, base, size); 277} 278 279long __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 288long 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 302static phys_addr_t memblock_align_down(phys_addr_t addr, phys_addr_t size) 303{ 304 return addr & ~(size - 1); 305} 306 307static phys_addr_t memblock_align_up(phys_addr_t addr, phys_addr_t size) 308{ 309 return (addr + (size - 1)) & ~(size - 1); 310} 311 312static 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 332phys_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 339static 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 366phys_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 389phys_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 394phys_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 407phys_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. */ 441phys_addr_t __init memblock_phys_mem_size(void) 442{ 443 return memblock.memory_size; 444} 445 446phys_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. */ 454void __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 494static 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 512int __init memblock_is_reserved(phys_addr_t addr) 513{ 514 return memblock_search(&memblock.reserved, addr) != -1; 515} 516 517int memblock_is_memory(phys_addr_t addr) 518{ 519 return memblock_search(&memblock.memory, addr) != -1; 520} 521 522int 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 533int 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 539void __init memblock_set_current_limit(phys_addr_t limit) 540{ 541 memblock.current_limit = limit; 542} 543 544