memblock.c 26.7 KB
Newer Older
Yinghai Lu's avatar
Yinghai Lu committed
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
 * Procedures for maintaining information about logical memory blocks.
 *
 * Peter Bergner, IBM Corp.	June 2001.
 * Copyright (C) 2001 Peter Bergner.
 *
 *      This program is free software; you can redistribute it and/or
 *      modify it under the terms of the GNU General Public License
 *      as published by the Free Software Foundation; either version
 *      2 of the License, or (at your option) any later version.
 */

#include <linux/kernel.h>
14
#include <linux/slab.h>
Yinghai Lu's avatar
Yinghai Lu committed
15 16
#include <linux/init.h>
#include <linux/bitops.h>
17
#include <linux/poison.h>
18
#include <linux/pfn.h>
19 20
#include <linux/debugfs.h>
#include <linux/seq_file.h>
Yinghai Lu's avatar
Yinghai Lu committed
21 22
#include <linux/memblock.h>

Tejun Heo's avatar
Tejun Heo committed
23 24 25 26 27 28 29 30 31 32 33 34 35 36
static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblock;
static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS] __initdata_memblock;

struct memblock memblock __initdata_memblock = {
	.memory.regions		= memblock_memory_init_regions,
	.memory.cnt		= 1,	/* empty dummy entry */
	.memory.max		= INIT_MEMBLOCK_REGIONS,

	.reserved.regions	= memblock_reserved_init_regions,
	.reserved.cnt		= 1,	/* empty dummy entry */
	.reserved.max		= INIT_MEMBLOCK_REGIONS,

	.current_limit		= MEMBLOCK_ALLOC_ANYWHERE,
};
Yinghai Lu's avatar
Yinghai Lu committed
37

38
int memblock_debug __initdata_memblock;
39
static int memblock_can_resize __initdata_memblock;
Yinghai Lu's avatar
Yinghai Lu committed
40

41 42 43 44 45 46 47 48 49 50 51
/* inline so we don't get a warning when pr_debug is compiled out */
static inline const char *memblock_type_name(struct memblock_type *type)
{
	if (type == &memblock.memory)
		return "memory";
	else if (type == &memblock.reserved)
		return "reserved";
	else
		return "unknown";
}

52 53 54 55 56 57
/* adjust *@size so that (@base + *@size) doesn't overflow, return new size */
static inline phys_addr_t memblock_cap_size(phys_addr_t base, phys_addr_t *size)
{
	return *size = min(*size, (phys_addr_t)ULLONG_MAX - base);
}

58 59 60
/*
 * Address comparison utilities
 */
61
static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
62
				       phys_addr_t base2, phys_addr_t size2)
Yinghai Lu's avatar
Yinghai Lu committed
63 64 65 66
{
	return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
}

67 68
static long __init_memblock memblock_overlaps_region(struct memblock_type *type,
					phys_addr_t base, phys_addr_t size)
69 70 71 72 73 74 75 76 77 78 79 80 81
{
	unsigned long i;

	for (i = 0; i < type->cnt; i++) {
		phys_addr_t rgnbase = type->regions[i].base;
		phys_addr_t rgnsize = type->regions[i].size;
		if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
			break;
	}

	return (i < type->cnt) ? i : -1;
}

82 83 84 85 86 87 88 89 90 91 92 93
/**
 * memblock_find_in_range_node - find free area in given range and node
 * @start: start of candidate range
 * @end: end of candidate range, can be %MEMBLOCK_ALLOC_{ANYWHERE|ACCESSIBLE}
 * @size: size of free area to find
 * @align: alignment of free area to find
 * @nid: nid of the free area to find, %MAX_NUMNODES for any node
 *
 * Find @size free area aligned to @align in the specified range and node.
 *
 * RETURNS:
 * Found address on success, %0 on failure.
94
 */
95 96 97
phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t start,
					phys_addr_t end, phys_addr_t size,
					phys_addr_t align, int nid)
98
{
99 100
	phys_addr_t this_start, this_end, cand;
	u64 i;
101

102 103 104
	/* pump up @end */
	if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
		end = memblock.current_limit;
105

106 107
	/* avoid allocating the first page */
	start = max_t(phys_addr_t, start, PAGE_SIZE);
108
	end = max(start, end);
109

110 111 112
	for_each_free_mem_range_reverse(i, nid, &this_start, &this_end, NULL) {
		this_start = clamp(this_start, start, end);
		this_end = clamp(this_end, start, end);
113

114 115 116
		if (this_end < size)
			continue;

117 118 119 120
		cand = round_down(this_end - size, align);
		if (cand >= this_start)
			return cand;
	}
Tejun Heo's avatar
Tejun Heo committed
121
	return 0;
122 123
}

124 125 126 127 128 129 130 131 132 133 134
/**
 * memblock_find_in_range - find free area in given range
 * @start: start of candidate range
 * @end: end of candidate range, can be %MEMBLOCK_ALLOC_{ANYWHERE|ACCESSIBLE}
 * @size: size of free area to find
 * @align: alignment of free area to find
 *
 * Find @size free area aligned to @align in the specified range.
 *
 * RETURNS:
 * Found address on success, %0 on failure.
135
 */
136 137 138
phys_addr_t __init_memblock memblock_find_in_range(phys_addr_t start,
					phys_addr_t end, phys_addr_t size,
					phys_addr_t align)
139
{
140 141
	return memblock_find_in_range_node(start, end, size, align,
					   MAX_NUMNODES);
142 143
}

144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
/*
 * Free memblock.reserved.regions
 */
int __init_memblock memblock_free_reserved_regions(void)
{
	if (memblock.reserved.regions == memblock_reserved_init_regions)
		return 0;

	return memblock_free(__pa(memblock.reserved.regions),
		 sizeof(struct memblock_region) * memblock.reserved.max);
}

/*
 * Reserve memblock.reserved.regions
 */
int __init_memblock memblock_reserve_reserved_regions(void)
{
	if (memblock.reserved.regions == memblock_reserved_init_regions)
		return 0;

	return memblock_reserve(__pa(memblock.reserved.regions),
		 sizeof(struct memblock_region) * memblock.reserved.max);
}

168
static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
Yinghai Lu's avatar
Yinghai Lu committed
169
{
170
	type->total_size -= type->regions[r].size;
171 172
	memmove(&type->regions[r], &type->regions[r + 1],
		(type->cnt - (r + 1)) * sizeof(type->regions[r]));
173
	type->cnt--;
Yinghai Lu's avatar
Yinghai Lu committed
174

175 176
	/* Special case for empty arrays */
	if (type->cnt == 0) {
177
		WARN_ON(type->total_size != 0);
178 179 180
		type->cnt = 1;
		type->regions[0].base = 0;
		type->regions[0].size = 0;
181
		memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
182
	}
Yinghai Lu's avatar
Yinghai Lu committed
183 184
}

185
static int __init_memblock memblock_double_array(struct memblock_type *type)
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
{
	struct memblock_region *new_array, *old_array;
	phys_addr_t old_size, new_size, addr;
	int use_slab = slab_is_available();

	/* We don't allow resizing until we know about the reserved regions
	 * of memory that aren't suitable for allocation
	 */
	if (!memblock_can_resize)
		return -1;

	/* Calculate new doubled size */
	old_size = type->max * sizeof(struct memblock_region);
	new_size = old_size << 1;

	/* Try to find some space for it.
	 *
	 * WARNING: We assume that either slab_is_available() and we use it or
	 * we use MEMBLOCK for allocations. That means that this is unsafe to use
	 * when bootmem is currently active (unless bootmem itself is implemented
	 * on top of MEMBLOCK which isn't the case yet)
	 *
	 * This should however not be an issue for now, as we currently only
	 * call into MEMBLOCK while it's still active, or much later when slab is
	 * active for memory hotplug operations
	 */
	if (use_slab) {
		new_array = kmalloc(new_size, GFP_KERNEL);
Tejun Heo's avatar
Tejun Heo committed
214
		addr = new_array ? __pa(new_array) : 0;
215
	} else
216
		addr = memblock_find_in_range(0, MEMBLOCK_ALLOC_ACCESSIBLE, new_size, sizeof(phys_addr_t));
Tejun Heo's avatar
Tejun Heo committed
217
	if (!addr) {
218 219 220 221 222 223
		pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
		       memblock_type_name(type), type->max, type->max * 2);
		return -1;
	}
	new_array = __va(addr);

224 225 226
	memblock_dbg("memblock: %s array is doubled to %ld at [%#010llx-%#010llx]",
		 memblock_type_name(type), type->max * 2, (u64)addr, (u64)addr + new_size - 1);

227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
	/* Found space, we now need to move the array over before
	 * we add the reserved region since it may be our reserved
	 * array itself that is full.
	 */
	memcpy(new_array, type->regions, old_size);
	memset(new_array + type->max, 0, old_size);
	old_array = type->regions;
	type->regions = new_array;
	type->max <<= 1;

	/* If we use SLAB that's it, we are done */
	if (use_slab)
		return 0;

	/* Add the new reserved region now. Should not fail ! */
242
	BUG_ON(memblock_reserve(addr, new_size));
243 244 245 246 247 248 249 250 251 252 253 254 255

	/* If the array wasn't our static init one, then free it. We only do
	 * that before SLAB is available as later on, we don't know whether
	 * to use kfree or free_bootmem_pages(). Shouldn't be a big deal
	 * anyways
	 */
	if (old_array != memblock_memory_init_regions &&
	    old_array != memblock_reserved_init_regions)
		memblock_free(__pa(old_array), old_size);

	return 0;
}

256 257 258 259 260 261 262
/**
 * memblock_merge_regions - merge neighboring compatible regions
 * @type: memblock type to scan
 *
 * Scan @type and merge neighboring compatible regions.
 */
static void __init_memblock memblock_merge_regions(struct memblock_type *type)
Yinghai Lu's avatar
Yinghai Lu committed
263
{
264
	int i = 0;
Yinghai Lu's avatar
Yinghai Lu committed
265

266 267 268 269
	/* cnt never goes below 1 */
	while (i < type->cnt - 1) {
		struct memblock_region *this = &type->regions[i];
		struct memblock_region *next = &type->regions[i + 1];
Yinghai Lu's avatar
Yinghai Lu committed
270

271 272 273
		if (this->base + this->size != next->base ||
		    memblock_get_region_node(this) !=
		    memblock_get_region_node(next)) {
274 275 276
			BUG_ON(this->base + this->size > next->base);
			i++;
			continue;
277 278
		}

279 280 281
		this->size += next->size;
		memmove(next, next + 1, (type->cnt - (i + 1)) * sizeof(*next));
		type->cnt--;
Yinghai Lu's avatar
Yinghai Lu committed
282
	}
283
}
Yinghai Lu's avatar
Yinghai Lu committed
284

285 286 287 288 289 290 291 292 293 294 295 296
/**
 * memblock_insert_region - insert new memblock region
 * @type: memblock type to insert into
 * @idx: index for the insertion point
 * @base: base address of the new region
 * @size: size of the new region
 *
 * Insert new memblock region [@base,@base+@size) into @type at @idx.
 * @type must already have extra room to accomodate the new region.
 */
static void __init_memblock memblock_insert_region(struct memblock_type *type,
						   int idx, phys_addr_t base,
297
						   phys_addr_t size, int nid)
298 299 300 301 302 303 304
{
	struct memblock_region *rgn = &type->regions[idx];

	BUG_ON(type->cnt >= type->max);
	memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
	rgn->base = base;
	rgn->size = size;
305
	memblock_set_region_node(rgn, nid);
306
	type->cnt++;
307
	type->total_size += size;
308 309 310 311 312 313 314
}

/**
 * memblock_add_region - add new memblock region
 * @type: memblock type to add new region into
 * @base: base address of the new region
 * @size: size of the new region
315
 * @nid: nid of the new region
316 317 318 319 320 321 322 323 324
 *
 * Add new memblock region [@base,@base+@size) into @type.  The new region
 * is allowed to overlap with existing ones - overlaps don't affect already
 * existing regions.  @type is guaranteed to be minimal (all neighbouring
 * compatible regions are merged) after the addition.
 *
 * RETURNS:
 * 0 on success, -errno on failure.
 */
325
static int __init_memblock memblock_add_region(struct memblock_type *type,
326
				phys_addr_t base, phys_addr_t size, int nid)
327 328
{
	bool insert = false;
329 330
	phys_addr_t obase = base;
	phys_addr_t end = base + memblock_cap_size(base, &size);
331 332
	int i, nr_new;

333 334 335
	if (!size)
		return 0;

336 337
	/* special case for empty array */
	if (type->regions[0].size == 0) {
338
		WARN_ON(type->cnt != 1 || type->total_size);
339 340
		type->regions[0].base = base;
		type->regions[0].size = size;
341
		memblock_set_region_node(&type->regions[0], nid);
342
		type->total_size = size;
343
		return 0;
Yinghai Lu's avatar
Yinghai Lu committed
344
	}
345 346 347 348 349
repeat:
	/*
	 * The following is executed twice.  Once with %false @insert and
	 * then with %true.  The first counts the number of regions needed
	 * to accomodate the new area.  The second actually inserts them.
350
	 */
351 352
	base = obase;
	nr_new = 0;
Yinghai Lu's avatar
Yinghai Lu committed
353

354 355 356 357 358 359
	for (i = 0; i < type->cnt; i++) {
		struct memblock_region *rgn = &type->regions[i];
		phys_addr_t rbase = rgn->base;
		phys_addr_t rend = rbase + rgn->size;

		if (rbase >= end)
Yinghai Lu's avatar
Yinghai Lu committed
360
			break;
361 362 363 364 365 366 367 368 369 370
		if (rend <= base)
			continue;
		/*
		 * @rgn overlaps.  If it separates the lower part of new
		 * area, insert that portion.
		 */
		if (rbase > base) {
			nr_new++;
			if (insert)
				memblock_insert_region(type, i++, base,
371
						       rbase - base, nid);
Yinghai Lu's avatar
Yinghai Lu committed
372
		}
373 374
		/* area below @rend is dealt with, forget about it */
		base = min(rend, end);
Yinghai Lu's avatar
Yinghai Lu committed
375
	}
376 377 378 379 380

	/* insert the remaining portion */
	if (base < end) {
		nr_new++;
		if (insert)
381
			memblock_insert_region(type, i, base, end - base, nid);
Yinghai Lu's avatar
Yinghai Lu committed
382 383
	}

384 385 386
	/*
	 * If this was the first round, resize array and repeat for actual
	 * insertions; otherwise, merge and return.
387
	 */
388 389 390 391 392 393 394 395 396
	if (!insert) {
		while (type->cnt + nr_new > type->max)
			if (memblock_double_array(type) < 0)
				return -ENOMEM;
		insert = true;
		goto repeat;
	} else {
		memblock_merge_regions(type);
		return 0;
397
	}
Yinghai Lu's avatar
Yinghai Lu committed
398 399
}

400 401 402 403 404 405
int __init_memblock memblock_add_node(phys_addr_t base, phys_addr_t size,
				       int nid)
{
	return memblock_add_region(&memblock.memory, base, size, nid);
}

406
int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
407
{
408
	return memblock_add_region(&memblock.memory, base, size, MAX_NUMNODES);
Yinghai Lu's avatar
Yinghai Lu committed
409 410
}

411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430
/**
 * memblock_isolate_range - isolate given range into disjoint memblocks
 * @type: memblock type to isolate range for
 * @base: base of range to isolate
 * @size: size of range to isolate
 * @start_rgn: out parameter for the start of isolated region
 * @end_rgn: out parameter for the end of isolated region
 *
 * Walk @type and ensure that regions don't cross the boundaries defined by
 * [@base,@base+@size).  Crossing regions are split at the boundaries,
 * which may create at most two more regions.  The index of the first
 * region inside the range is returned in *@start_rgn and end in *@end_rgn.
 *
 * RETURNS:
 * 0 on success, -errno on failure.
 */
static int __init_memblock memblock_isolate_range(struct memblock_type *type,
					phys_addr_t base, phys_addr_t size,
					int *start_rgn, int *end_rgn)
{
431
	phys_addr_t end = base + memblock_cap_size(base, &size);
432 433 434 435
	int i;

	*start_rgn = *end_rgn = 0;

436 437 438
	if (!size)
		return 0;

439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459
	/* we'll create at most two more regions */
	while (type->cnt + 2 > type->max)
		if (memblock_double_array(type) < 0)
			return -ENOMEM;

	for (i = 0; i < type->cnt; i++) {
		struct memblock_region *rgn = &type->regions[i];
		phys_addr_t rbase = rgn->base;
		phys_addr_t rend = rbase + rgn->size;

		if (rbase >= end)
			break;
		if (rend <= base)
			continue;

		if (rbase < base) {
			/*
			 * @rgn intersects from below.  Split and continue
			 * to process the next region - the new top half.
			 */
			rgn->base = base;
460 461
			rgn->size -= base - rbase;
			type->total_size -= base - rbase;
462
			memblock_insert_region(type, i, rbase, base - rbase,
463
					       memblock_get_region_node(rgn));
464 465 466 467 468 469
		} else if (rend > end) {
			/*
			 * @rgn intersects from above.  Split and redo the
			 * current region - the new bottom half.
			 */
			rgn->base = end;
470 471
			rgn->size -= end - rbase;
			type->total_size -= end - rbase;
472
			memblock_insert_region(type, i--, rbase, end - rbase,
473
					       memblock_get_region_node(rgn));
474 475 476 477 478 479 480 481 482 483 484
		} else {
			/* @rgn is fully contained, record it */
			if (!*end_rgn)
				*start_rgn = i;
			*end_rgn = i + 1;
		}
	}

	return 0;
}

485 486
static int __init_memblock __memblock_remove(struct memblock_type *type,
					     phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
487
{
488 489
	int start_rgn, end_rgn;
	int i, ret;
Yinghai Lu's avatar
Yinghai Lu committed
490

491 492 493
	ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
	if (ret)
		return ret;
Yinghai Lu's avatar
Yinghai Lu committed
494

495 496
	for (i = end_rgn - 1; i >= start_rgn; i--)
		memblock_remove_region(type, i);
497
	return 0;
Yinghai Lu's avatar
Yinghai Lu committed
498 499
}

500
int __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
501 502 503 504
{
	return __memblock_remove(&memblock.memory, base, size);
}

505
int __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
506
{
507
	memblock_dbg("   memblock_free: [%#016llx-%#016llx] %pF\n",
508 509 510
		     (unsigned long long)base,
		     (unsigned long long)base + size,
		     (void *)_RET_IP_);
511

Yinghai Lu's avatar
Yinghai Lu committed
512 513 514
	return __memblock_remove(&memblock.reserved, base, size);
}

515
int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
516
{
517
	struct memblock_type *_rgn = &memblock.reserved;
Yinghai Lu's avatar
Yinghai Lu committed
518

519
	memblock_dbg("memblock_reserve: [%#016llx-%#016llx] %pF\n",
520 521 522
		     (unsigned long long)base,
		     (unsigned long long)base + size,
		     (void *)_RET_IP_);
Yinghai Lu's avatar
Yinghai Lu committed
523

524
	return memblock_add_region(_rgn, base, size, MAX_NUMNODES);
Yinghai Lu's avatar
Yinghai Lu committed
525 526
}

527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
/**
 * __next_free_mem_range - next function for for_each_free_mem_range()
 * @idx: pointer to u64 loop variable
 * @nid: nid: node selector, %MAX_NUMNODES for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 *
 * Find the first free area from *@idx which matches @nid, fill the out
 * parameters, and update *@idx for the next iteration.  The lower 32bit of
 * *@idx contains index into memory region and the upper 32bit indexes the
 * areas before each reserved region.  For example, if reserved regions
 * look like the following,
 *
 *	0:[0-16), 1:[32-48), 2:[128-130)
 *
 * The upper 32bit indexes the following regions.
 *
 *	0:[0-0), 1:[16-32), 2:[48-128), 3:[130-MAX)
 *
 * As both region arrays are sorted, the function advances the two indices
 * in lockstep and returns each intersection.
 */
void __init_memblock __next_free_mem_range(u64 *idx, int nid,
					   phys_addr_t *out_start,
					   phys_addr_t *out_end, int *out_nid)
{
	struct memblock_type *mem = &memblock.memory;
	struct memblock_type *rsv = &memblock.reserved;
	int mi = *idx & 0xffffffff;
	int ri = *idx >> 32;

	for ( ; mi < mem->cnt; mi++) {
		struct memblock_region *m = &mem->regions[mi];
		phys_addr_t m_start = m->base;
		phys_addr_t m_end = m->base + m->size;

		/* only memory regions are associated with nodes, check it */
		if (nid != MAX_NUMNODES && nid != memblock_get_region_node(m))
			continue;

		/* scan areas before each reservation for intersection */
		for ( ; ri < rsv->cnt + 1; ri++) {
			struct memblock_region *r = &rsv->regions[ri];
			phys_addr_t r_start = ri ? r[-1].base + r[-1].size : 0;
			phys_addr_t r_end = ri < rsv->cnt ? r->base : ULLONG_MAX;

			/* if ri advanced past mi, break out to advance mi */
			if (r_start >= m_end)
				break;
			/* if the two regions intersect, we're done */
			if (m_start < r_end) {
				if (out_start)
					*out_start = max(m_start, r_start);
				if (out_end)
					*out_end = min(m_end, r_end);
				if (out_nid)
					*out_nid = memblock_get_region_node(m);
				/*
				 * The region which ends first is advanced
				 * for the next iteration.
				 */
				if (m_end <= r_end)
					mi++;
				else
					ri++;
				*idx = (u32)mi | (u64)ri << 32;
				return;
			}
		}
	}

	/* signal end of iteration */
	*idx = ULLONG_MAX;
}

603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666
/**
 * __next_free_mem_range_rev - next function for for_each_free_mem_range_reverse()
 * @idx: pointer to u64 loop variable
 * @nid: nid: node selector, %MAX_NUMNODES for all nodes
 * @p_start: ptr to phys_addr_t for start address of the range, can be %NULL
 * @p_end: ptr to phys_addr_t for end address of the range, can be %NULL
 * @p_nid: ptr to int for nid of the range, can be %NULL
 *
 * Reverse of __next_free_mem_range().
 */
void __init_memblock __next_free_mem_range_rev(u64 *idx, int nid,
					   phys_addr_t *out_start,
					   phys_addr_t *out_end, int *out_nid)
{
	struct memblock_type *mem = &memblock.memory;
	struct memblock_type *rsv = &memblock.reserved;
	int mi = *idx & 0xffffffff;
	int ri = *idx >> 32;

	if (*idx == (u64)ULLONG_MAX) {
		mi = mem->cnt - 1;
		ri = rsv->cnt;
	}

	for ( ; mi >= 0; mi--) {
		struct memblock_region *m = &mem->regions[mi];
		phys_addr_t m_start = m->base;
		phys_addr_t m_end = m->base + m->size;

		/* only memory regions are associated with nodes, check it */
		if (nid != MAX_NUMNODES && nid != memblock_get_region_node(m))
			continue;

		/* scan areas before each reservation for intersection */
		for ( ; ri >= 0; ri--) {
			struct memblock_region *r = &rsv->regions[ri];
			phys_addr_t r_start = ri ? r[-1].base + r[-1].size : 0;
			phys_addr_t r_end = ri < rsv->cnt ? r->base : ULLONG_MAX;

			/* if ri advanced past mi, break out to advance mi */
			if (r_end <= m_start)
				break;
			/* if the two regions intersect, we're done */
			if (m_end > r_start) {
				if (out_start)
					*out_start = max(m_start, r_start);
				if (out_end)
					*out_end = min(m_end, r_end);
				if (out_nid)
					*out_nid = memblock_get_region_node(m);

				if (m_start >= r_start)
					mi--;
				else
					ri--;
				*idx = (u32)mi | (u64)ri << 32;
				return;
			}
		}
	}

	*idx = ULLONG_MAX;
}

667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
/*
 * Common iterator interface used to define for_each_mem_range().
 */
void __init_memblock __next_mem_pfn_range(int *idx, int nid,
				unsigned long *out_start_pfn,
				unsigned long *out_end_pfn, int *out_nid)
{
	struct memblock_type *type = &memblock.memory;
	struct memblock_region *r;

	while (++*idx < type->cnt) {
		r = &type->regions[*idx];

		if (PFN_UP(r->base) >= PFN_DOWN(r->base + r->size))
			continue;
		if (nid == MAX_NUMNODES || nid == r->nid)
			break;
	}
	if (*idx >= type->cnt) {
		*idx = -1;
		return;
	}

	if (out_start_pfn)
		*out_start_pfn = PFN_UP(r->base);
	if (out_end_pfn)
		*out_end_pfn = PFN_DOWN(r->base + r->size);
	if (out_nid)
		*out_nid = r->nid;
}

/**
 * memblock_set_node - set node ID on memblock regions
 * @base: base of area to set node ID for
 * @size: size of area to set node ID for
 * @nid: node ID to set
 *
 * Set the nid of memblock memory regions in [@base,@base+@size) to @nid.
 * Regions which cross the area boundaries are split as necessary.
 *
 * RETURNS:
 * 0 on success, -errno on failure.
 */
int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size,
				      int nid)
{
	struct memblock_type *type = &memblock.memory;
715 716
	int start_rgn, end_rgn;
	int i, ret;
717

718 719 720
	ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
	if (ret)
		return ret;
721

722 723
	for (i = start_rgn; i < end_rgn; i++)
		type->regions[i].nid = nid;
724 725 726 727 728 729

	memblock_merge_regions(type);
	return 0;
}
#endif /* CONFIG_HAVE_MEMBLOCK_NODE_MAP */

730 731 732
static phys_addr_t __init memblock_alloc_base_nid(phys_addr_t size,
					phys_addr_t align, phys_addr_t max_addr,
					int nid)
Yinghai Lu's avatar
Yinghai Lu committed
733
{
734
	phys_addr_t found;
Yinghai Lu's avatar
Yinghai Lu committed
735

736 737 738
	/* align @size to avoid excessive fragmentation on reserved array */
	size = round_up(size, align);

739
	found = memblock_find_in_range_node(0, max_addr, size, align, nid);
740
	if (found && !memblock_reserve(found, size))
741
		return found;
Yinghai Lu's avatar
Yinghai Lu committed
742

743
	return 0;
Yinghai Lu's avatar
Yinghai Lu committed
744 745
}

746 747 748 749 750 751 752 753 754 755
phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
{
	return memblock_alloc_base_nid(size, align, MEMBLOCK_ALLOC_ACCESSIBLE, nid);
}

phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
{
	return memblock_alloc_base_nid(size, align, max_addr, MAX_NUMNODES);
}

756
phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
Yinghai Lu's avatar
Yinghai Lu committed
757
{
758 759 760 761 762 763 764 765 766
	phys_addr_t alloc;

	alloc = __memblock_alloc_base(size, align, max_addr);

	if (alloc == 0)
		panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
		      (unsigned long long) size, (unsigned long long) max_addr);

	return alloc;
Yinghai Lu's avatar
Yinghai Lu committed
767 768
}

769
phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
Yinghai Lu's avatar
Yinghai Lu committed
770
{
771 772
	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
}
Yinghai Lu's avatar
Yinghai Lu committed
773

774 775 776 777 778 779
phys_addr_t __init memblock_alloc_try_nid(phys_addr_t size, phys_addr_t align, int nid)
{
	phys_addr_t res = memblock_alloc_nid(size, align, nid);

	if (res)
		return res;
780
	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
Yinghai Lu's avatar
Yinghai Lu committed
781 782
}

783 784 785 786 787

/*
 * Remaining API functions
 */

788
phys_addr_t __init memblock_phys_mem_size(void)
Yinghai Lu's avatar
Yinghai Lu committed
789
{
790
	return memblock.memory.total_size;
Yinghai Lu's avatar
Yinghai Lu committed
791 792
}

793 794 795 796 797 798
/* lowest address */
phys_addr_t __init_memblock memblock_start_of_DRAM(void)
{
	return memblock.memory.regions[0].base;
}

799
phys_addr_t __init_memblock memblock_end_of_DRAM(void)
Yinghai Lu's avatar
Yinghai Lu committed
800 801 802
{
	int idx = memblock.memory.cnt - 1;

803
	return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
Yinghai Lu's avatar
Yinghai Lu committed
804 805
}

806
void __init memblock_enforce_memory_limit(phys_addr_t limit)
Yinghai Lu's avatar
Yinghai Lu committed
807 808
{
	unsigned long i;
809
	phys_addr_t max_addr = (phys_addr_t)ULLONG_MAX;
Yinghai Lu's avatar
Yinghai Lu committed
810

811
	if (!limit)
Yinghai Lu's avatar
Yinghai Lu committed
812 813
		return;

814
	/* find out max address */
Yinghai Lu's avatar
Yinghai Lu committed
815
	for (i = 0; i < memblock.memory.cnt; i++) {
816
		struct memblock_region *r = &memblock.memory.regions[i];
Yinghai Lu's avatar
Yinghai Lu committed
817

818 819 820
		if (limit <= r->size) {
			max_addr = r->base + limit;
			break;
Yinghai Lu's avatar
Yinghai Lu committed
821
		}
822
		limit -= r->size;
Yinghai Lu's avatar
Yinghai Lu committed
823
	}
824 825 826 827

	/* truncate both memory and reserved regions */
	__memblock_remove(&memblock.memory, max_addr, (phys_addr_t)ULLONG_MAX);
	__memblock_remove(&memblock.reserved, max_addr, (phys_addr_t)ULLONG_MAX);
Yinghai Lu's avatar
Yinghai Lu committed
828 829
}

830
static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847
{
	unsigned int left = 0, right = type->cnt;

	do {
		unsigned int mid = (right + left) / 2;

		if (addr < type->regions[mid].base)
			right = mid;
		else if (addr >= (type->regions[mid].base +
				  type->regions[mid].size))
			left = mid + 1;
		else
			return mid;
	} while (left < right);
	return -1;
}

848
int __init memblock_is_reserved(phys_addr_t addr)
Yinghai Lu's avatar
Yinghai Lu committed
849
{
850 851
	return memblock_search(&memblock.reserved, addr) != -1;
}
Yinghai Lu's avatar
Yinghai Lu committed
852

853
int __init_memblock memblock_is_memory(phys_addr_t addr)
854 855 856 857
{
	return memblock_search(&memblock.memory, addr) != -1;
}

858
int __init_memblock memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
859
{
860
	int idx = memblock_search(&memblock.memory, base);
861
	phys_addr_t end = base + memblock_cap_size(base, &size);
862 863 864

	if (idx == -1)
		return 0;
865 866
	return memblock.memory.regions[idx].base <= base &&
		(memblock.memory.regions[idx].base +
867
		 memblock.memory.regions[idx].size) >= end;
Yinghai Lu's avatar
Yinghai Lu committed
868 869
}

870
int __init_memblock memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
Yinghai Lu's avatar
Yinghai Lu committed
871
{
872
	memblock_cap_size(base, &size);
873
	return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
Yinghai Lu's avatar
Yinghai Lu committed
874 875
}

876

877
void __init_memblock memblock_set_current_limit(phys_addr_t limit)
878 879 880 881
{
	memblock.current_limit = limit;
}

882
static void __init_memblock memblock_dump(struct memblock_type *type, char *name)
883 884 885 886
{
	unsigned long long base, size;
	int i;

887
	pr_info(" %s.cnt  = 0x%lx\n", name, type->cnt);
888

889 890 891 892 893 894 895 896 897 898 899 900 901
	for (i = 0; i < type->cnt; i++) {
		struct memblock_region *rgn = &type->regions[i];
		char nid_buf[32] = "";

		base = rgn->base;
		size = rgn->size;
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
		if (memblock_get_region_node(rgn) != MAX_NUMNODES)
			snprintf(nid_buf, sizeof(nid_buf), " on node %d",
				 memblock_get_region_node(rgn));
#endif
		pr_info(" %s[%#x]\t[%#016llx-%#016llx], %#llx bytes%s\n",
			name, i, base, base + size - 1, size, nid_buf);
902 903 904
	}
}

905
void __init_memblock __memblock_dump_all(void)
906 907
{
	pr_info("MEMBLOCK configuration:\n");
908 909 910
	pr_info(" memory size = %#llx reserved size = %#llx\n",
		(unsigned long long)memblock.memory.total_size,
		(unsigned long long)memblock.reserved.total_size);
911 912 913 914 915

	memblock_dump(&memblock.memory, "memory");
	memblock_dump(&memblock.reserved, "reserved");
}

916
void __init memblock_allow_resize(void)
917
{
918
	memblock_can_resize = 1;
919 920 921 922 923 924 925 926 927 928
}

static int __init early_memblock(char *p)
{
	if (p && strstr(p, "debug"))
		memblock_debug = 1;
	return 0;
}
early_param("memblock", early_memblock);

929
#if defined(CONFIG_DEBUG_FS) && !defined(CONFIG_ARCH_DISCARD_MEMBLOCK)
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977

static int memblock_debug_show(struct seq_file *m, void *private)
{
	struct memblock_type *type = m->private;
	struct memblock_region *reg;
	int i;

	for (i = 0; i < type->cnt; i++) {
		reg = &type->regions[i];
		seq_printf(m, "%4d: ", i);
		if (sizeof(phys_addr_t) == 4)
			seq_printf(m, "0x%08lx..0x%08lx\n",
				   (unsigned long)reg->base,
				   (unsigned long)(reg->base + reg->size - 1));
		else
			seq_printf(m, "0x%016llx..0x%016llx\n",
				   (unsigned long long)reg->base,
				   (unsigned long long)(reg->base + reg->size - 1));

	}
	return 0;
}

static int memblock_debug_open(struct inode *inode, struct file *file)
{
	return single_open(file, memblock_debug_show, inode->i_private);
}

static const struct file_operations memblock_debug_fops = {
	.open = memblock_debug_open,
	.read = seq_read,
	.llseek = seq_lseek,
	.release = single_release,
};

static int __init memblock_init_debugfs(void)
{
	struct dentry *root = debugfs_create_dir("memblock", NULL);
	if (!root)
		return -ENXIO;
	debugfs_create_file("memory", S_IRUGO, root, &memblock.memory, &memblock_debug_fops);
	debugfs_create_file("reserved", S_IRUGO, root, &memblock.reserved, &memblock_debug_fops);

	return 0;
}
__initcall(memblock_init_debugfs);

#endif /* CONFIG_DEBUG_FS */