linux/mm/memblock.c
<<
>>
Prefs
   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/slab.h>
  15#include <linux/init.h>
  16#include <linux/bitops.h>
  17#include <linux/poison.h>
  18#include <linux/pfn.h>
  19#include <linux/debugfs.h>
  20#include <linux/seq_file.h>
  21#include <linux/memblock.h>
  22
  23static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblock;
  24static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblock;
  25
  26struct memblock memblock __initdata_memblock = {
  27        .memory.regions         = memblock_memory_init_regions,
  28        .memory.cnt             = 1,    /* empty dummy entry */
  29        .memory.max             = INIT_MEMBLOCK_REGIONS,
  30
  31        .reserved.regions       = memblock_reserved_init_regions,
  32        .reserved.cnt           = 1,    /* empty dummy entry */
  33        .reserved.max           = INIT_MEMBLOCK_REGIONS,
  34
  35        .current_limit          = MEMBLOCK_ALLOC_ANYWHERE,
  36};
  37
  38int memblock_debug __initdata_memblock;
  39static int memblock_can_resize __initdata_memblock;
  40static int memblock_memory_in_slab __initdata_memblock = 0;
  41static int memblock_reserved_in_slab __initdata_memblock = 0;
  42
  43/* inline so we don't get a warning when pr_debug is compiled out */
  44static __init_memblock const char *
  45memblock_type_name(struct memblock_type *type)
  46{
  47        if (type == &memblock.memory)
  48                return "memory";
  49        else if (type == &memblock.reserved)
  50                return "reserved";
  51        else
  52                return "unknown";
  53}
  54
  55/* adjust *@size so that (@base + *@size) doesn't overflow, return new size */
  56static inline phys_addr_t memblock_cap_size(phys_addr_t base, phys_addr_t *size)
  57{
  58        return *size = min(*size, (phys_addr_t)ULLONG_MAX - base);
  59}
  60
  61/*
  62 * Address comparison utilities
  63 */
  64static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
  65                                       phys_addr_t base2, phys_addr_t size2)
  66{
  67        return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
  68}
  69
  70static long __init_memblock memblock_overlaps_region(struct memblock_type *type,
  71                                        phys_addr_t base, phys_addr_t size)
  72{
  73        unsigned long i;
  74
  75        for (i = 0; i < type->cnt; i++) {
  76                phys_addr_t rgnbase = type->regions[i].base;
  77                phys_addr_t rgnsize = type->regions[i].size;
  78                if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
  79                        break;
  80        }
  81
  82        return (i < type->cnt) ? i : -1;
  83}
  84
  85/**
  86 * memblock_find_in_range_node - find free area in given range and node
  87 * @start: start of candidate range
  88 * @end: end of candidate range, can be %MEMBLOCK_ALLOC_{ANYWHERE|ACCESSIBLE}
  89 * @size: size of free area to find
  90 * @align: alignment of free area to find
  91 * @nid: nid of the free area to find, %MAX_NUMNODES for any node
  92 *
  93 * Find @size free area aligned to @align in the specified range and node.
  94 *
  95 * RETURNS:
  96 * Found address on success, %0 on failure.
  97 */
  98phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t start,
  99                                        phys_addr_t end, phys_addr_t size,
 100                                        phys_addr_t align, int nid)
 101{
 102        phys_addr_t this_start, this_end, cand;
 103        u64 i;
 104
 105        /* pump up @end */
 106        if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
 107                end = memblock.current_limit;
 108
 109        /* avoid allocating the first page */
 110        start = max_t(phys_addr_t, start, PAGE_SIZE);
 111        end = max(start, end);
 112
 113        for_each_free_mem_range_reverse(i, nid, &this_start, &this_end, NULL) {
 114                this_start = clamp(this_start, start, end);
 115                this_end = clamp(this_end, start, end);
 116
 117                if (this_end < size)
 118                        continue;
 119
 120                cand = round_down(this_end - size, align);
 121                if (cand >= this_start)
 122                        return cand;
 123        }
 124        return 0;
 125}
 126
 127/**
 128 * memblock_find_in_range - find free area in given range
 129 * @start: start of candidate range
 130 * @end: end of candidate range, can be %MEMBLOCK_ALLOC_{ANYWHERE|ACCESSIBLE}
 131 * @size: size of free area to find
 132 * @align: alignment of free area to find
 133 *
 134 * Find @size free area aligned to @align in the specified range.
 135 *
 136 * RETURNS:
 137 * Found address on success, %0 on failure.
 138 */
 139phys_addr_t __init_memblock memblock_find_in_range(phys_addr_t start,
 140                                        phys_addr_t end, phys_addr_t size,
 141                                        phys_addr_t align)
 142{
 143        return memblock_find_in_range_node(start, end, size, align,
 144                                           MAX_NUMNODES);
 145}
 146
 147static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
 148{
 149        type->total_size -= type->regions[r].size;
 150        memmove(&type->regions[r], &type->regions[r + 1],
 151                (type->cnt - (r + 1)) * sizeof(type->regions[r]));
 152        type->cnt--;
 153
 154        /* Special case for empty arrays */
 155        if (type->cnt == 0) {
 156                WARN_ON(type->total_size != 0);
 157                type->cnt = 1;
 158                type->regions[0].base = 0;
 159                type->regions[0].size = 0;
 160                memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
 161        }
 162}
 163
 164phys_addr_t __init_memblock get_allocated_memblock_reserved_regions_info(
 165                                        phys_addr_t *addr)
 166{
 167        if (memblock.reserved.regions == memblock_reserved_init_regions)
 168                return 0;
 169
 170        *addr = __pa(memblock.reserved.regions);
 171
 172        return PAGE_ALIGN(sizeof(struct memblock_region) *
 173                          memblock.reserved.max);
 174}
 175
 176/**
 177 * memblock_double_array - double the size of the memblock regions array
 178 * @type: memblock type of the regions array being doubled
 179 * @new_area_start: starting address of memory range to avoid overlap with
 180 * @new_area_size: size of memory range to avoid overlap with
 181 *
 182 * Double the size of the @type regions array. If memblock is being used to
 183 * allocate memory for a new reserved regions array and there is a previously
 184 * allocated memory range [@new_area_start,@new_area_start+@new_area_size]
 185 * waiting to be reserved, ensure the memory used by the new array does
 186 * not overlap.
 187 *
 188 * RETURNS:
 189 * 0 on success, -1 on failure.
 190 */
 191static int __init_memblock memblock_double_array(struct memblock_type *type,
 192                                                phys_addr_t new_area_start,
 193                                                phys_addr_t new_area_size)
 194{
 195        struct memblock_region *new_array, *old_array;
 196        phys_addr_t old_alloc_size, new_alloc_size;
 197        phys_addr_t old_size, new_size, addr;
 198        int use_slab = slab_is_available();
 199        int *in_slab;
 200
 201        /* We don't allow resizing until we know about the reserved regions
 202         * of memory that aren't suitable for allocation
 203         */
 204        if (!memblock_can_resize)
 205                return -1;
 206
 207        /* Calculate new doubled size */
 208        old_size = type->max * sizeof(struct memblock_region);
 209        new_size = old_size << 1;
 210        /*
 211         * We need to allocated new one align to PAGE_SIZE,
 212         *   so we can free them completely later.
 213         */
 214        old_alloc_size = PAGE_ALIGN(old_size);
 215        new_alloc_size = PAGE_ALIGN(new_size);
 216
 217        /* Retrieve the slab flag */
 218        if (type == &memblock.memory)
 219                in_slab = &memblock_memory_in_slab;
 220        else
 221                in_slab = &memblock_reserved_in_slab;
 222
 223        /* Try to find some space for it.
 224         *
 225         * WARNING: We assume that either slab_is_available() and we use it or
 226         * we use MEMBLOCK for allocations. That means that this is unsafe to
 227         * use when bootmem is currently active (unless bootmem itself is
 228         * implemented on top of MEMBLOCK which isn't the case yet)
 229         *
 230         * This should however not be an issue for now, as we currently only
 231         * call into MEMBLOCK while it's still active, or much later when slab
 232         * is active for memory hotplug operations
 233         */
 234        if (use_slab) {
 235                new_array = kmalloc(new_size, GFP_KERNEL);
 236                addr = new_array ? __pa(new_array) : 0;
 237        } else {
 238                /* only exclude range when trying to double reserved.regions */
 239                if (type != &memblock.reserved)
 240                        new_area_start = new_area_size = 0;
 241
 242                addr = memblock_find_in_range(new_area_start + new_area_size,
 243                                                memblock.current_limit,
 244                                                new_alloc_size, PAGE_SIZE);
 245                if (!addr && new_area_size)
 246                        addr = memblock_find_in_range(0,
 247                                min(new_area_start, memblock.current_limit),
 248                                new_alloc_size, PAGE_SIZE);
 249
 250                new_array = addr ? __va(addr) : NULL;
 251        }
 252        if (!addr) {
 253                pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
 254                       memblock_type_name(type), type->max, type->max * 2);
 255                return -1;
 256        }
 257
 258        memblock_dbg("memblock: %s is doubled to %ld at [%#010llx-%#010llx]",
 259                        memblock_type_name(type), type->max * 2, (u64)addr,
 260                        (u64)addr + new_size - 1);
 261
 262        /*
 263         * Found space, we now need to move the array over before we add the
 264         * reserved region since it may be our reserved array itself that is
 265         * full.
 266         */
 267        memcpy(new_array, type->regions, old_size);
 268        memset(new_array + type->max, 0, old_size);
 269        old_array = type->regions;
 270        type->regions = new_array;
 271        type->max <<= 1;
 272
 273        /* Free old array. We needn't free it if the array is the static one */
 274        if (*in_slab)
 275                kfree(old_array);
 276        else if (old_array != memblock_memory_init_regions &&
 277                 old_array != memblock_reserved_init_regions)
 278                memblock_free(__pa(old_array), old_alloc_size);
 279
 280        /*
 281         * Reserve the new array if that comes from the memblock.  Otherwise, we
 282         * needn't do it
 283         */
 284        if (!use_slab)
 285                BUG_ON(memblock_reserve(addr, new_alloc_size));
 286
 287        /* Update slab flag */
 288        *in_slab = use_slab;
 289
 290        return 0;
 291}
 292
 293/**
 294 * memblock_merge_regions - merge neighboring compatible regions
 295 * @type: memblock type to scan
 296 *
 297 * Scan @type and merge neighboring compatible regions.
 298 */
 299static void __init_memblock memblock_merge_regions(struct memblock_type *type)
 300{
 301        int i = 0;
 302
 303        /* cnt never goes below 1 */
 304        while (i < type->cnt - 1) {
 305                struct memblock_region *this = &type->regions[i];
 306                struct memblock_region *next = &type->regions[i + 1];
 307
 308                if (this->base + this->size != next->base ||
 309                    memblock_get_region_node(this) !=
 310                    memblock_get_region_node(next)) {
 311                        BUG_ON(this->base + this->size > next->base);
 312                        i++;
 313                        continue;
 314                }
 315
 316                this->size += next->size;
 317                memmove(next, next + 1, (type->cnt - (i + 1)) * sizeof(*next));
 318                type->cnt--;
 319        }
 320}
 321
 322/**
 323 * memblock_insert_region - insert new memblock region
 324 * @type: memblock type to insert into
 325 * @idx: index for the insertion point
 326 * @base: base address of the new region
 327 * @size: size of the new region
 328 *
 329 * Insert new memblock region [@base,@base+@size) into @type at @idx.
 330 * @type must already have extra room to accomodate the new region.
 331 */
 332static void __init_memblock memblock_insert_region(struct memblock_type *type,
 333                                                   int idx, phys_addr_t base,
 334                                                   phys_addr_t size, int nid)
 335{
 336        struct memblock_region *rgn = &type->regions[idx];
 337
 338        BUG_ON(type->cnt >= type->max);
 339        memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
 340        rgn->base = base;
 341        rgn->size = size;
 342        memblock_set_region_node(rgn, nid);
 343        type->cnt++;
 344        type->total_size += size;
 345}
 346
 347/**
 348 * memblock_add_region - add new memblock region
 349 * @type: memblock type to add new region into
 350 * @base: base address of the new region
 351 * @size: size of the new region
 352 * @nid: nid of the new region
 353 *
 354 * Add new memblock region [@base,@base+@size) into @type.  The new region
 355 * is allowed to overlap with existing ones - overlaps don't affect already
 356 * existing regions.  @type is guaranteed to be minimal (all neighbouring
 357 * compatible regions are merged) after the addition.
 358 *
 359 * RETURNS:
 360 * 0 on success, -errno on failure.
 361 */
 362static int __init_memblock memblock_add_region(struct memblock_type *type,
 363                                phys_addr_t base, phys_addr_t size, int nid)
 364{
 365        bool insert = false;
 366        phys_addr_t obase = base;
 367        phys_addr_t end = base + memblock_cap_size(base, &size);
 368        int i, nr_new;
 369
 370        if (!size)
 371                return 0;
 372
 373        /* special case for empty array */
 374        if (type->regions[0].size == 0) {
 375                WARN_ON(type->cnt != 1 || type->total_size);
 376                type->regions[0].base = base;
 377                type->regions[0].size = size;
 378                memblock_set_region_node(&type->regions[0], nid);
 379                type->total_size = size;
 380                return 0;
 381        }
 382repeat:
 383        /*
 384         * The following is executed twice.  Once with %false @insert and
 385         * then with %true.  The first counts the number of regions needed
 386         * to accomodate the new area.  The second actually inserts them.
 387         */
 388        base = obase;
 389        nr_new = 0;
 390
 391        for (i = 0; i < type->cnt; i++) {
 392                struct memblock_region *rgn = &type->regions[i];
 393                phys_addr_t rbase = rgn->base;
 394                phys_addr_t rend = rbase + rgn->size;
 395
 396                if (rbase >= end)
 397                        break;
 398                if (rend <= base)
 399                        continue;
 400                /*
 401                 * @rgn overlaps.  If it separates the lower part of new
 402                 * area, insert that portion.
 403                 */
 404                if (rbase > base) {
 405                        nr_new++;
 406                        if (insert)
 407                                memblock_insert_region(type, i++, base,
 408                                                       rbase - base, nid);
 409                }
 410                /* area below @rend is dealt with, forget about it */
 411                base = min(rend, end);
 412        }
 413
 414        /* insert the remaining portion */
 415        if (base < end) {
 416                nr_new++;
 417                if (insert)
 418                        memblock_insert_region(type, i, base, end - base, nid);
 419        }
 420
 421        /*
 422         * If this was the first round, resize array and repeat for actual
 423         * insertions; otherwise, merge and return.
 424         */
 425        if (!insert) {
 426                while (type->cnt + nr_new > type->max)
 427                        if (memblock_double_array(type, obase, size) < 0)
 428                                return -ENOMEM;
 429                insert = true;
 430                goto repeat;
 431        } else {
 432                memblock_merge_regions(type);
 433                return 0;
 434        }
 435}
 436
 437int __init_memblock memblock_add_node(phys_addr_t base, phys_addr_t size,
 438                                       int nid)
 439{
 440        return memblock_add_region(&memblock.memory, base, size, nid);
 441}
 442
 443int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
 444{
 445        return memblock_add_region(&memblock.memory, base, size, MAX_NUMNODES);
 446}
 447
 448/**
 449 * memblock_isolate_range - isolate given range into disjoint memblocks
 450 * @type: memblock type to isolate range for
 451 * @base: base of range to isolate
 452 * @size: size of range to isolate
 453 * @start_rgn: out parameter for the start of isolated region
 454 * @end_rgn: out parameter for the end of isolated region
 455 *
 456 * Walk @type and ensure that regions don't cross the boundaries defined by
 457 * [@base,@base+@size).  Crossing regions are split at the boundaries,
 458 * which may create at most two more regions.  The index of the first
 459 * region inside the range is returned in *@start_rgn and end in *@end_rgn.
 460 *
 461 * RETURNS:
 462 * 0 on success, -errno on failure.
 463 */
 464static int __init_memblock memblock_isolate_range(struct memblock_type *type,
 465                                        phys_addr_t base, phys_addr_t size,
 466                                        int *start_rgn, int *end_rgn)
 467{
 468        phys_addr_t end = base + memblock_cap_size(base, &size);
 469        int i;
 470
 471        *start_rgn = *end_rgn = 0;
 472
 473        if (!size)
 474                return 0;
 475
 476        /* we'll create at most two more regions */
 477        while (type->cnt + 2 > type->max)
 478                if (memblock_double_array(type, base, size) < 0)
 479                        return -ENOMEM;
 480
 481        for (i = 0; i < type->cnt; i++) {
 482                struct memblock_region *rgn = &type->regions[i];
 483                phys_addr_t rbase = rgn->base;
 484                phys_addr_t rend = rbase + rgn->size;
 485
 486                if (rbase >= end)
 487                        break;
 488                if (rend <= base)
 489                        continue;
 490
 491                if (rbase < base) {
 492                        /*
 493                         * @rgn intersects from below.  Split and continue
 494                         * to process the next region - the new top half.
 495                         */
 496                        rgn->base = base;
 497                        rgn->size -= base - rbase;
 498                        type->total_size -= base - rbase;
 499                        memblock_insert_region(type, i, rbase, base - rbase,
 500                                               memblock_get_region_node(rgn));
 501                } else if (rend > end) {
 502                        /*
 503                         * @rgn intersects from above.  Split and redo the
 504                         * current region - the new bottom half.
 505                         */
 506                        rgn->base = end;
 507                        rgn->size -= end - rbase;
 508                        type->total_size -= end - rbase;
 509                        memblock_insert_region(type, i--, rbase, end - rbase,
 510                                               memblock_get_region_node(rgn));
 511                } else {
 512                        /* @rgn is fully contained, record it */
 513                        if (!*end_rgn)
 514                                *start_rgn = i;
 515                        *end_rgn = i + 1;
 516                }
 517        }
 518
 519        return 0;
 520}
 521
 522static int __init_memblock __memblock_remove(struct memblock_type *type,
 523                                             phys_addr_t base, phys_addr_t size)
 524{
 525        int start_rgn, end_rgn;
 526        int i, ret;
 527
 528        ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
 529        if (ret)
 530                return ret;
 531
 532        for (i = end_rgn - 1; i >= start_rgn; i--)
 533                memblock_remove_region(type, i);
 534        return 0;
 535}
 536
 537int __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
 538{
 539        return __memblock_remove(&memblock.memory, base, size);
 540}
 541
 542int __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
 543{
 544        memblock_dbg("   memblock_free: [%#016llx-%#016llx] %pF\n",
 545                     (unsigned long long)base,
 546                     (unsigned long long)base + size,
 547                     (void *)_RET_IP_);
 548
 549        return __memblock_remove(&memblock.reserved, base, size);
 550}
 551
 552int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
 553{
 554        struct memblock_type *_rgn = &memblock.reserved;
 555
 556        memblock_dbg("memblock_reserve: [%#016llx-%#016llx] %pF\n",
 557                     (unsigned long long)base,
 558                     (unsigned long long)base + size,
 559                     (void *)_RET_IP_);
 560
 561        return memblock_add_region(_rgn, base, size, MAX_NUMNODES);
 562}
 563
 564/**
 565 * __next_free_mem_range - next function for for_each_free_mem_range()
 566 * @idx: pointer to u64 loop variable
 567 * @nid: nid: node selector, %MAX_NUMNODES for all nodes
 568 * @out_start: ptr to phys_addr_t for start address of the range, can be %NULL
 569 * @out_end: ptr to phys_addr_t for end address of the range, can be %NULL
 570 * @out_nid: ptr to int for nid of the range, can be %NULL
 571 *
 572 * Find the first free area from *@idx which matches @nid, fill the out
 573 * parameters, and update *@idx for the next iteration.  The lower 32bit of
 574 * *@idx contains index into memory region and the upper 32bit indexes the
 575 * areas before each reserved region.  For example, if reserved regions
 576 * look like the following,
 577 *
 578 *      0:[0-16), 1:[32-48), 2:[128-130)
 579 *
 580 * The upper 32bit indexes the following regions.
 581 *
 582 *      0:[0-0), 1:[16-32), 2:[48-128), 3:[130-MAX)
 583 *
 584 * As both region arrays are sorted, the function advances the two indices
 585 * in lockstep and returns each intersection.
 586 */
 587void __init_memblock __next_free_mem_range(u64 *idx, int nid,
 588                                           phys_addr_t *out_start,
 589                                           phys_addr_t *out_end, int *out_nid)
 590{
 591        struct memblock_type *mem = &memblock.memory;
 592        struct memblock_type *rsv = &memblock.reserved;
 593        int mi = *idx & 0xffffffff;
 594        int ri = *idx >> 32;
 595
 596        for ( ; mi < mem->cnt; mi++) {
 597                struct memblock_region *m = &mem->regions[mi];
 598                phys_addr_t m_start = m->base;
 599                phys_addr_t m_end = m->base + m->size;
 600
 601                /* only memory regions are associated with nodes, check it */
 602                if (nid != MAX_NUMNODES && nid != memblock_get_region_node(m))
 603                        continue;
 604
 605                /* scan areas before each reservation for intersection */
 606                for ( ; ri < rsv->cnt + 1; ri++) {
 607                        struct memblock_region *r = &rsv->regions[ri];
 608                        phys_addr_t r_start = ri ? r[-1].base + r[-1].size : 0;
 609                        phys_addr_t r_end = ri < rsv->cnt ? r->base : ULLONG_MAX;
 610
 611                        /* if ri advanced past mi, break out to advance mi */
 612                        if (r_start >= m_end)
 613                                break;
 614                        /* if the two regions intersect, we're done */
 615                        if (m_start < r_end) {
 616                                if (out_start)
 617                                        *out_start = max(m_start, r_start);
 618                                if (out_end)
 619                                        *out_end = min(m_end, r_end);
 620                                if (out_nid)
 621                                        *out_nid = memblock_get_region_node(m);
 622                                /*
 623                                 * The region which ends first is advanced
 624                                 * for the next iteration.
 625                                 */
 626                                if (m_end <= r_end)
 627                                        mi++;
 628                                else
 629                                        ri++;
 630                                *idx = (u32)mi | (u64)ri << 32;
 631                                return;
 632                        }
 633                }
 634        }
 635
 636        /* signal end of iteration */
 637        *idx = ULLONG_MAX;
 638}
 639
 640/**
 641 * __next_free_mem_range_rev - next function for for_each_free_mem_range_reverse()
 642 * @idx: pointer to u64 loop variable
 643 * @nid: nid: node selector, %MAX_NUMNODES for all nodes
 644 * @out_start: ptr to phys_addr_t for start address of the range, can be %NULL
 645 * @out_end: ptr to phys_addr_t for end address of the range, can be %NULL
 646 * @out_nid: ptr to int for nid of the range, can be %NULL
 647 *
 648 * Reverse of __next_free_mem_range().
 649 */
 650void __init_memblock __next_free_mem_range_rev(u64 *idx, int nid,
 651                                           phys_addr_t *out_start,
 652                                           phys_addr_t *out_end, int *out_nid)
 653{
 654        struct memblock_type *mem = &memblock.memory;
 655        struct memblock_type *rsv = &memblock.reserved;
 656        int mi = *idx & 0xffffffff;
 657        int ri = *idx >> 32;
 658
 659        if (*idx == (u64)ULLONG_MAX) {
 660                mi = mem->cnt - 1;
 661                ri = rsv->cnt;
 662        }
 663
 664        for ( ; mi >= 0; mi--) {
 665                struct memblock_region *m = &mem->regions[mi];
 666                phys_addr_t m_start = m->base;
 667                phys_addr_t m_end = m->base + m->size;
 668
 669                /* only memory regions are associated with nodes, check it */
 670                if (nid != MAX_NUMNODES && nid != memblock_get_region_node(m))
 671                        continue;
 672
 673                /* scan areas before each reservation for intersection */
 674                for ( ; ri >= 0; ri--) {
 675                        struct memblock_region *r = &rsv->regions[ri];
 676                        phys_addr_t r_start = ri ? r[-1].base + r[-1].size : 0;
 677                        phys_addr_t r_end = ri < rsv->cnt ? r->base : ULLONG_MAX;
 678
 679                        /* if ri advanced past mi, break out to advance mi */
 680                        if (r_end <= m_start)
 681                                break;
 682                        /* if the two regions intersect, we're done */
 683                        if (m_end > r_start) {
 684                                if (out_start)
 685                                        *out_start = max(m_start, r_start);
 686                                if (out_end)
 687                                        *out_end = min(m_end, r_end);
 688                                if (out_nid)
 689                                        *out_nid = memblock_get_region_node(m);
 690
 691                                if (m_start >= r_start)
 692                                        mi--;
 693                                else
 694                                        ri--;
 695                                *idx = (u32)mi | (u64)ri << 32;
 696                                return;
 697                        }
 698                }
 699        }
 700
 701        *idx = ULLONG_MAX;
 702}
 703
 704#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
 705/*
 706 * Common iterator interface used to define for_each_mem_range().
 707 */
 708void __init_memblock __next_mem_pfn_range(int *idx, int nid,
 709                                unsigned long *out_start_pfn,
 710                                unsigned long *out_end_pfn, int *out_nid)
 711{
 712        struct memblock_type *type = &memblock.memory;
 713        struct memblock_region *r;
 714
 715        while (++*idx < type->cnt) {
 716                r = &type->regions[*idx];
 717
 718                if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
 719                        continue;
 720                if (nid == MAX_NUMNODES || nid == r->nid)
 721                        break;
 722        }
 723        if (*idx >= type->cnt) {
 724                *idx = -1;
 725                return;
 726        }
 727
 728        if (out_start_pfn)
 729                *out_start_pfn = PFN_UP(r->base);
 730        if (out_end_pfn)
 731                *out_end_pfn = PFN_DOWN(r->base + r->size);
 732        if (out_nid)
 733                *out_nid = r->nid;
 734}
 735
 736/**
 737 * memblock_set_node - set node ID on memblock regions
 738 * @base: base of area to set node ID for
 739 * @size: size of area to set node ID for
 740 * @nid: node ID to set
 741 *
 742 * Set the nid of memblock memory regions in [@base,@base+@size) to @nid.
 743 * Regions which cross the area boundaries are split as necessary.
 744 *
 745 * RETURNS:
 746 * 0 on success, -errno on failure.
 747 */
 748int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size,
 749                                      int nid)
 750{
 751        struct memblock_type *type = &memblock.memory;
 752        int start_rgn, end_rgn;
 753        int i, ret;
 754
 755        ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
 756        if (ret)
 757                return ret;
 758
 759        for (i = start_rgn; i < end_rgn; i++)
 760                memblock_set_region_node(&type->regions[i], nid);
 761
 762        memblock_merge_regions(type);
 763        return 0;
 764}
 765#endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */
 766
 767static phys_addr_t __init memblock_alloc_base_nid(phys_addr_t size,
 768                                        phys_addr_t align, phys_addr_t max_addr,
 769                                        int nid)
 770{
 771        phys_addr_t found;
 772
 773        /* align @size to avoid excessive fragmentation on reserved array */
 774        size = round_up(size, align);
 775
 776        found = memblock_find_in_range_node(0, max_addr, size, align, nid);
 777        if (found && !memblock_reserve(found, size))
 778                return found;
 779
 780        return 0;
 781}
 782
 783phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
 784{
 785        return memblock_alloc_base_nid(size, align, MEMBLOCK_ALLOC_ACCESSIBLE, nid);
 786}
 787
 788phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
 789{
 790        return memblock_alloc_base_nid(size, align, max_addr, MAX_NUMNODES);
 791}
 792
 793phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
 794{
 795        phys_addr_t alloc;
 796
 797        alloc = __memblock_alloc_base(size, align, max_addr);
 798
 799        if (alloc == 0)
 800                panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
 801                      (unsigned long long) size, (unsigned long long) max_addr);
 802
 803        return alloc;
 804}
 805
 806phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
 807{
 808        return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
 809}
 810
 811phys_addr_t __init memblock_alloc_try_nid(phys_addr_t size, phys_addr_t align, int nid)
 812{
 813        phys_addr_t res = memblock_alloc_nid(size, align, nid);
 814
 815        if (res)
 816                return res;
 817        return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
 818}
 819
 820
 821/*
 822 * Remaining API functions
 823 */
 824
 825phys_addr_t __init memblock_phys_mem_size(void)
 826{
 827        return memblock.memory.total_size;
 828}
 829
 830/* lowest address */
 831phys_addr_t __init_memblock memblock_start_of_DRAM(void)
 832{
 833        return memblock.memory.regions[0].base;
 834}
 835
 836phys_addr_t __init_memblock memblock_end_of_DRAM(void)
 837{
 838        int idx = memblock.memory.cnt - 1;
 839
 840        return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
 841}
 842
 843void __init memblock_enforce_memory_limit(phys_addr_t limit)
 844{
 845        unsigned long i;
 846        phys_addr_t max_addr = (phys_addr_t)ULLONG_MAX;
 847
 848        if (!limit)
 849                return;
 850
 851        /* find out max address */
 852        for (i = 0; i < memblock.memory.cnt; i++) {
 853                struct memblock_region *r = &memblock.memory.regions[i];
 854
 855                if (limit <= r->size) {
 856                        max_addr = r->base + limit;
 857                        break;
 858                }
 859                limit -= r->size;
 860        }
 861
 862        /* truncate both memory and reserved regions */
 863        __memblock_remove(&memblock.memory, max_addr, (phys_addr_t)ULLONG_MAX);
 864        __memblock_remove(&memblock.reserved, max_addr, (phys_addr_t)ULLONG_MAX);
 865}
 866
 867static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
 868{
 869        unsigned int left = 0, right = type->cnt;
 870
 871        do {
 872                unsigned int mid = (right + left) / 2;
 873
 874                if (addr < type->regions[mid].base)
 875                        right = mid;
 876                else if (addr >= (type->regions[mid].base +
 877                                  type->regions[mid].size))
 878                        left = mid + 1;
 879                else
 880                        return mid;
 881        } while (left < right);
 882        return -1;
 883}
 884
 885int __init memblock_is_reserved(phys_addr_t addr)
 886{
 887        return memblock_search(&memblock.reserved, addr) != -1;
 888}
 889
 890int __init_memblock memblock_is_memory(phys_addr_t addr)
 891{
 892        return memblock_search(&memblock.memory, addr) != -1;
 893}
 894
 895/**
 896 * memblock_is_region_memory - check if a region is a subset of memory
 897 * @base: base of region to check
 898 * @size: size of region to check
 899 *
 900 * Check if the region [@base, @base+@size) is a subset of a memory block.
 901 *
 902 * RETURNS:
 903 * 0 if false, non-zero if true
 904 */
 905int __init_memblock memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
 906{
 907        int idx = memblock_search(&memblock.memory, base);
 908        phys_addr_t end = base + memblock_cap_size(base, &size);
 909
 910        if (idx == -1)
 911                return 0;
 912        return memblock.memory.regions[idx].base <= base &&
 913                (memblock.memory.regions[idx].base +
 914                 memblock.memory.regions[idx].size) >= end;
 915}
 916
 917/**
 918 * memblock_is_region_reserved - check if a region intersects reserved memory
 919 * @base: base of region to check
 920 * @size: size of region to check
 921 *
 922 * Check if the region [@base, @base+@size) intersects a reserved memory block.
 923 *
 924 * RETURNS:
 925 * 0 if false, non-zero if true
 926 */
 927int __init_memblock memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
 928{
 929        memblock_cap_size(base, &size);
 930        return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
 931}
 932
 933void __init_memblock memblock_trim_memory(phys_addr_t align)
 934{
 935        int i;
 936        phys_addr_t start, end, orig_start, orig_end;
 937        struct memblock_type *mem = &memblock.memory;
 938
 939        for (i = 0; i < mem->cnt; i++) {
 940                orig_start = mem->regions[i].base;
 941                orig_end = mem->regions[i].base + mem->regions[i].size;
 942                start = round_up(orig_start, align);
 943                end = round_down(orig_end, align);
 944
 945                if (start == orig_start && end == orig_end)
 946                        continue;
 947
 948                if (start < end) {
 949                        mem->regions[i].base = start;
 950                        mem->regions[i].size = end - start;
 951                } else {
 952                        memblock_remove_region(mem, i);
 953                        i--;
 954                }
 955        }
 956}
 957
 958void __init_memblock memblock_set_current_limit(phys_addr_t limit)
 959{
 960        memblock.current_limit = limit;
 961}
 962
 963static void __init_memblock memblock_dump(struct memblock_type *type, char *name)
 964{
 965        unsigned long long base, size;
 966        int i;
 967
 968        pr_info(" %s.cnt  = 0x%lx\n", name, type->cnt);
 969
 970        for (i = 0; i < type->cnt; i++) {
 971                struct memblock_region *rgn = &type->regions[i];
 972                char nid_buf[32] = "";
 973
 974                base = rgn->base;
 975                size = rgn->size;
 976#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
 977                if (memblock_get_region_node(rgn) != MAX_NUMNODES)
 978                        snprintf(nid_buf, sizeof(nid_buf), " on node %d",
 979                                 memblock_get_region_node(rgn));
 980#endif
 981                pr_info(" %s[%#x]\t[%#016llx-%#016llx], %#llx bytes%s\n",
 982                        name, i, base, base + size - 1, size, nid_buf);
 983        }
 984}
 985
 986void __init_memblock __memblock_dump_all(void)
 987{
 988        pr_info("MEMBLOCK configuration:\n");
 989        pr_info(" memory size = %#llx reserved size = %#llx\n",
 990                (unsigned long long)memblock.memory.total_size,
 991                (unsigned long long)memblock.reserved.total_size);
 992
 993        memblock_dump(&memblock.memory, "memory");
 994        memblock_dump(&memblock.reserved, "reserved");
 995}
 996
 997void __init memblock_allow_resize(void)
 998{
 999        memblock_can_resize = 1;
1000}
1001
1002static int __init early_memblock(char *p)
1003{
1004        if (p && strstr(p, "debug"))
1005                memblock_debug = 1;
1006        return 0;
1007}
1008early_param("memblock", early_memblock);
1009
1010#if defined(CONFIG_DEBUG_FS) && !defined(CONFIG_ARCH_DISCARD_MEMBLOCK)
1011
1012static int memblock_debug_show(struct seq_file *m, void *private)
1013{
1014        struct memblock_type *type = m->private;
1015        struct memblock_region *reg;
1016        int i;
1017
1018        for (i = 0; i < type->cnt; i++) {
1019                reg = &type->regions[i];
1020                seq_printf(m, "%4d: ", i);
1021                if (sizeof(phys_addr_t) == 4)
1022                        seq_printf(m, "0x%08lx..0x%08lx\n",
1023                                   (unsigned long)reg->base,
1024                                   (unsigned long)(reg->base + reg->size - 1));
1025                else
1026                        seq_printf(m, "0x%016llx..0x%016llx\n",
1027                                   (unsigned long long)reg->base,
1028                                   (unsigned long long)(reg->base + reg->size - 1));
1029
1030        }
1031        return 0;
1032}
1033
1034static int memblock_debug_open(struct inode *inode, struct file *file)
1035{
1036        return single_open(file, memblock_debug_show, inode->i_private);
1037}
1038
1039static const struct file_operations memblock_debug_fops = {
1040        .open = memblock_debug_open,
1041        .read = seq_read,
1042        .llseek = seq_lseek,
1043        .release = single_release,
1044};
1045
1046static int __init memblock_init_debugfs(void)
1047{
1048        struct dentry *root = debugfs_create_dir("memblock", NULL);
1049        if (!root)
1050                return -ENXIO;
1051        debugfs_create_file("memory", S_IRUGO, root, &memblock.memory, &memblock_debug_fops);
1052        debugfs_create_file("reserved", S_IRUGO, root, &memblock.reserved, &memblock_debug_fops);
1053
1054        return 0;
1055}
1056__initcall(memblock_init_debugfs);
1057
1058#endif /* CONFIG_DEBUG_FS */
1059
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.