memblock.c 26.4 KB
Newer Older
Y
Yinghai Lu 已提交
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>
Y
Yinghai Lu 已提交
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>
Y
Yinghai Lu 已提交
21 22
#include <linux/memblock.h>

T
Tejun Heo 已提交
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,
};
Y
Yinghai Lu 已提交
37

38
int memblock_debug __initdata_memblock;
39
static int memblock_can_resize __initdata_memblock;
Y
Yinghai Lu 已提交
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)
Y
Yinghai Lu 已提交
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 82 83 84 85 86
{
	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;
}

/*
 * Find, allocate, deallocate or reserve unreserved regions. All allocations
 * are top-down.
 */

87
static phys_addr_t __init_memblock memblock_find_region(phys_addr_t start, phys_addr_t end,
88 89 90 91 92
					  phys_addr_t size, phys_addr_t align)
{
	phys_addr_t base, res_base;
	long j;

93 94
	/* In case, huge size is requested */
	if (end < size)
T
Tejun Heo 已提交
95
		return 0;
96

97
	base = round_down(end - size, align);
98

99 100 101 102 103 104
	/* Prevent allocations returning 0 as it's also used to
	 * indicate an allocation failure
	 */
	if (start == 0)
		start = PAGE_SIZE;

105 106 107 108 109 110 111
	while (start <= base) {
		j = memblock_overlaps_region(&memblock.reserved, base, size);
		if (j < 0)
			return base;
		res_base = memblock.reserved.regions[j].base;
		if (res_base < size)
			break;
112
		base = round_down(res_base - size, align);
113 114
	}

T
Tejun Heo 已提交
115
	return 0;
116 117
}

118 119 120 121 122
/*
 * Find a free area with specified alignment in a specific range.
 */
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)
123 124 125 126 127 128
{
	long i;

	BUG_ON(0 == size);

	/* Pump up max_addr */
129 130
	if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
		end = memblock.current_limit;
131 132 133 134 135 136 137 138

	/* We do a top-down search, this tends to limit memory
	 * fragmentation by keeping early boot allocs near the
	 * top of memory
	 */
	for (i = memblock.memory.cnt - 1; i >= 0; i--) {
		phys_addr_t memblockbase = memblock.memory.regions[i].base;
		phys_addr_t memblocksize = memblock.memory.regions[i].size;
139
		phys_addr_t bottom, top, found;
140 141 142

		if (memblocksize < size)
			continue;
143 144 145 146 147 148 149
		if ((memblockbase + memblocksize) <= start)
			break;
		bottom = max(memblockbase, start);
		top = min(memblockbase + memblocksize, end);
		if (bottom >= top)
			continue;
		found = memblock_find_region(bottom, top, size, align);
T
Tejun Heo 已提交
150
		if (found)
151
			return found;
152
	}
T
Tejun Heo 已提交
153
	return 0;
154 155
}

156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
/*
 * 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);
}

180
static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
Y
Yinghai Lu 已提交
181
{
182
	type->total_size -= type->regions[r].size;
T
Tejun Heo 已提交
183 184
	memmove(&type->regions[r], &type->regions[r + 1],
		(type->cnt - (r + 1)) * sizeof(type->regions[r]));
185
	type->cnt--;
Y
Yinghai Lu 已提交
186

187 188
	/* Special case for empty arrays */
	if (type->cnt == 0) {
189
		WARN_ON(type->total_size != 0);
190 191 192
		type->cnt = 1;
		type->regions[0].base = 0;
		type->regions[0].size = 0;
T
Tejun Heo 已提交
193
		memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
194
	}
Y
Yinghai Lu 已提交
195 196
}

197
static int __init_memblock memblock_double_array(struct memblock_type *type)
198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
{
	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);
T
Tejun Heo 已提交
226
		addr = new_array ? __pa(new_array) : 0;
227
	} else
228
		addr = memblock_find_in_range(0, MEMBLOCK_ALLOC_ACCESSIBLE, new_size, sizeof(phys_addr_t));
T
Tejun Heo 已提交
229
	if (!addr) {
230 231 232 233 234 235
		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);

236 237 238
	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);

239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
	/* 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 ! */
254
	BUG_ON(memblock_reserve(addr, new_size));
255 256 257 258 259 260 261 262 263 264 265 266 267

	/* 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;
}

268 269 270 271 272 273 274
/**
 * 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)
Y
Yinghai Lu 已提交
275
{
276
	int i = 0;
Y
Yinghai Lu 已提交
277

278 279 280 281
	/* 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];
Y
Yinghai Lu 已提交
282

T
Tejun Heo 已提交
283 284 285
		if (this->base + this->size != next->base ||
		    memblock_get_region_node(this) !=
		    memblock_get_region_node(next)) {
286 287 288
			BUG_ON(this->base + this->size > next->base);
			i++;
			continue;
289 290
		}

291 292 293
		this->size += next->size;
		memmove(next, next + 1, (type->cnt - (i + 1)) * sizeof(*next));
		type->cnt--;
Y
Yinghai Lu 已提交
294
	}
295
}
Y
Yinghai Lu 已提交
296

297 298 299 300 301 302 303 304 305 306 307 308
/**
 * 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,
T
Tejun Heo 已提交
309
						   phys_addr_t size, int nid)
310 311 312 313 314 315 316
{
	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;
T
Tejun Heo 已提交
317
	memblock_set_region_node(rgn, nid);
318
	type->cnt++;
319
	type->total_size += size;
320 321 322 323 324 325 326
}

/**
 * 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
327
 * @nid: nid of the new region
328 329 330 331 332 333 334 335 336
 *
 * 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.
 */
337
static int __init_memblock memblock_add_region(struct memblock_type *type,
338
				phys_addr_t base, phys_addr_t size, int nid)
339 340
{
	bool insert = false;
341 342
	phys_addr_t obase = base;
	phys_addr_t end = base + memblock_cap_size(base, &size);
343 344 345 346
	int i, nr_new;

	/* special case for empty array */
	if (type->regions[0].size == 0) {
347
		WARN_ON(type->cnt != 1 || type->total_size);
348 349
		type->regions[0].base = base;
		type->regions[0].size = size;
350
		memblock_set_region_node(&type->regions[0], nid);
351
		type->total_size = size;
352
		return 0;
Y
Yinghai Lu 已提交
353
	}
354 355 356 357 358
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.
359
	 */
360 361
	base = obase;
	nr_new = 0;
Y
Yinghai Lu 已提交
362

363 364 365 366 367 368
	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)
Y
Yinghai Lu 已提交
369
			break;
370 371 372 373 374 375 376 377 378 379
		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,
380
						       rbase - base, nid);
Y
Yinghai Lu 已提交
381
		}
382 383
		/* area below @rend is dealt with, forget about it */
		base = min(rend, end);
Y
Yinghai Lu 已提交
384
	}
385 386 387 388 389

	/* insert the remaining portion */
	if (base < end) {
		nr_new++;
		if (insert)
390
			memblock_insert_region(type, i, base, end - base, nid);
Y
Yinghai Lu 已提交
391 392
	}

393 394 395
	/*
	 * If this was the first round, resize array and repeat for actual
	 * insertions; otherwise, merge and return.
396
	 */
397 398 399 400 401 402 403 404 405
	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;
406
	}
Y
Yinghai Lu 已提交
407 408
}

409 410 411 412 413 414
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);
}

415
int __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
416
{
417
	return memblock_add_region(&memblock.memory, base, size, MAX_NUMNODES);
Y
Yinghai Lu 已提交
418 419
}

420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
/**
 * 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)
{
440
	phys_addr_t end = base + memblock_cap_size(base, &size);
441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
	int i;

	*start_rgn = *end_rgn = 0;

	/* 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;
466 467
			rgn->size -= base - rbase;
			type->total_size -= base - rbase;
468
			memblock_insert_region(type, i, rbase, base - rbase,
469
					       memblock_get_region_node(rgn));
470 471 472 473 474 475
		} else if (rend > end) {
			/*
			 * @rgn intersects from above.  Split and redo the
			 * current region - the new bottom half.
			 */
			rgn->base = end;
476 477
			rgn->size -= end - rbase;
			type->total_size -= end - rbase;
478
			memblock_insert_region(type, i--, rbase, end - rbase,
479
					       memblock_get_region_node(rgn));
480 481 482 483 484 485 486 487 488 489 490
		} else {
			/* @rgn is fully contained, record it */
			if (!*end_rgn)
				*start_rgn = i;
			*end_rgn = i + 1;
		}
	}

	return 0;
}

491 492
static int __init_memblock __memblock_remove(struct memblock_type *type,
					     phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
493
{
494 495
	int start_rgn, end_rgn;
	int i, ret;
Y
Yinghai Lu 已提交
496

497 498 499
	ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
	if (ret)
		return ret;
Y
Yinghai Lu 已提交
500

501 502
	for (i = end_rgn - 1; i >= start_rgn; i--)
		memblock_remove_region(type, i);
503
	return 0;
Y
Yinghai Lu 已提交
504 505
}

506
int __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
507 508 509 510
{
	return __memblock_remove(&memblock.memory, base, size);
}

511
int __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
512
{
513
	memblock_dbg("   memblock_free: [%#016llx-%#016llx] %pF\n",
514 515 516
		     (unsigned long long)base,
		     (unsigned long long)base + size,
		     (void *)_RET_IP_);
517

Y
Yinghai Lu 已提交
518 519 520
	return __memblock_remove(&memblock.reserved, base, size);
}

521
int __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
522
{
523
	struct memblock_type *_rgn = &memblock.reserved;
Y
Yinghai Lu 已提交
524

525
	memblock_dbg("memblock_reserve: [%#016llx-%#016llx] %pF\n",
526 527 528
		     (unsigned long long)base,
		     (unsigned long long)base + size,
		     (void *)_RET_IP_);
Y
Yinghai Lu 已提交
529 530
	BUG_ON(0 == size);

531
	return memblock_add_region(_rgn, base, size, MAX_NUMNODES);
Y
Yinghai Lu 已提交
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 603 604 605 606 607 608 609
/**
 * __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;
}

T
Tejun Heo 已提交
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
#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;
658 659
	int start_rgn, end_rgn;
	int i, ret;
T
Tejun Heo 已提交
660

661 662 663
	ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
	if (ret)
		return ret;
T
Tejun Heo 已提交
664

665 666
	for (i = start_rgn; i < end_rgn; i++)
		type->regions[i].nid = nid;
T
Tejun Heo 已提交
667 668 669 670 671 672

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

673
phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
Y
Yinghai Lu 已提交
674
{
675
	phys_addr_t found;
Y
Yinghai Lu 已提交
676

677 678 679
	/* We align the size to limit fragmentation. Without this, a lot of
	 * small allocs quickly eat up the whole reserve array on sparc
	 */
680
	size = round_up(size, align);
Y
Yinghai Lu 已提交
681

682
	found = memblock_find_in_range(0, max_addr, size, align);
683
	if (found && !memblock_reserve(found, size))
684
		return found;
Y
Yinghai Lu 已提交
685

686
	return 0;
Y
Yinghai Lu 已提交
687 688
}

689
phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
Y
Yinghai Lu 已提交
690
{
691 692 693 694 695 696 697 698 699
	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;
Y
Yinghai Lu 已提交
700 701
}

702
phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
Y
Yinghai Lu 已提交
703
{
704 705
	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
}
Y
Yinghai Lu 已提交
706 707


708
/*
709
 * Additional node-local top-down allocators.
710 711 712 713
 *
 * WARNING: Only available after early_node_map[] has been populated,
 * on some architectures, that is after all the calls to add_active_range()
 * have been done to populate it.
714
 */
Y
Yinghai Lu 已提交
715

716 717
static phys_addr_t __init memblock_nid_range_rev(phys_addr_t start,
						 phys_addr_t end, int *nid)
718
{
719 720 721 722
#ifdef CONFIG_ARCH_POPULATES_NODE_MAP
	unsigned long start_pfn, end_pfn;
	int i;

723
	for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, nid)
724 725
		if (end > PFN_PHYS(start_pfn) && end <= PFN_PHYS(end_pfn))
			return max(start, PFN_PHYS(start_pfn));
726
#endif
727
	*nid = 0;
728
	return start;
729 730
}

731 732
phys_addr_t __init memblock_find_in_range_node(phys_addr_t start,
					       phys_addr_t end,
733 734
					       phys_addr_t size,
					       phys_addr_t align, int nid)
Y
Yinghai Lu 已提交
735
{
736 737
	struct memblock_type *mem = &memblock.memory;
	int i;
Y
Yinghai Lu 已提交
738

739
	BUG_ON(0 == size);
Y
Yinghai Lu 已提交
740

741 742 743
	/* Pump up max_addr */
	if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
		end = memblock.current_limit;
Y
Yinghai Lu 已提交
744

745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760
	for (i = mem->cnt - 1; i >= 0; i--) {
		struct memblock_region *r = &mem->regions[i];
		phys_addr_t base = max(start, r->base);
		phys_addr_t top = min(end, r->base + r->size);

		while (base < top) {
			phys_addr_t tbase, ret;
			int tnid;

			tbase = memblock_nid_range_rev(base, top, &tnid);
			if (nid == MAX_NUMNODES || tnid == nid) {
				ret = memblock_find_region(tbase, top, size, align);
				if (ret)
					return ret;
			}
			top = tbase;
Y
Yinghai Lu 已提交
761 762
		}
	}
763

T
Tejun Heo 已提交
764
	return 0;
Y
Yinghai Lu 已提交
765 766
}

767
phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
Y
Yinghai Lu 已提交
768
{
769
	phys_addr_t found;
Y
Yinghai Lu 已提交
770

771 772
	/*
	 * We align the size to limit fragmentation. Without this, a lot of
773 774
	 * small allocs quickly eat up the whole reserve array on sparc
	 */
775
	size = round_up(size, align);
776

777 778
	found = memblock_find_in_range_node(0, MEMBLOCK_ALLOC_ACCESSIBLE,
					    size, align, nid);
779
	if (found && !memblock_reserve(found, size))
780
		return found;
Y
Yinghai Lu 已提交
781

782 783 784 785 786 787 788 789 790
	return 0;
}

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;
791
	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
Y
Yinghai Lu 已提交
792 793
}

794 795 796 797 798

/*
 * Remaining API functions
 */

799
phys_addr_t __init memblock_phys_mem_size(void)
Y
Yinghai Lu 已提交
800
{
801
	return memblock.memory.total_size;
Y
Yinghai Lu 已提交
802 803
}

804 805 806 807 808 809
/* lowest address */
phys_addr_t __init_memblock memblock_start_of_DRAM(void)
{
	return memblock.memory.regions[0].base;
}

810
phys_addr_t __init_memblock memblock_end_of_DRAM(void)
Y
Yinghai Lu 已提交
811 812 813
{
	int idx = memblock.memory.cnt - 1;

814
	return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
Y
Yinghai Lu 已提交
815 816
}

817
void __init memblock_enforce_memory_limit(phys_addr_t limit)
Y
Yinghai Lu 已提交
818 819
{
	unsigned long i;
820
	phys_addr_t max_addr = (phys_addr_t)ULLONG_MAX;
Y
Yinghai Lu 已提交
821

822
	if (!limit)
Y
Yinghai Lu 已提交
823 824
		return;

825
	/* find out max address */
Y
Yinghai Lu 已提交
826
	for (i = 0; i < memblock.memory.cnt; i++) {
827
		struct memblock_region *r = &memblock.memory.regions[i];
Y
Yinghai Lu 已提交
828

829 830 831
		if (limit <= r->size) {
			max_addr = r->base + limit;
			break;
Y
Yinghai Lu 已提交
832
		}
833
		limit -= r->size;
Y
Yinghai Lu 已提交
834
	}
835 836 837 838

	/* 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);
Y
Yinghai Lu 已提交
839 840
}

841
static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858
{
	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;
}

859
int __init memblock_is_reserved(phys_addr_t addr)
Y
Yinghai Lu 已提交
860
{
861 862
	return memblock_search(&memblock.reserved, addr) != -1;
}
Y
Yinghai Lu 已提交
863

864
int __init_memblock memblock_is_memory(phys_addr_t addr)
865 866 867 868
{
	return memblock_search(&memblock.memory, addr) != -1;
}

869
int __init_memblock memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
870
{
871
	int idx = memblock_search(&memblock.memory, base);
872
	phys_addr_t end = base + memblock_cap_size(base, &size);
873 874 875

	if (idx == -1)
		return 0;
876 877
	return memblock.memory.regions[idx].base <= base &&
		(memblock.memory.regions[idx].base +
878
		 memblock.memory.regions[idx].size) >= end;
Y
Yinghai Lu 已提交
879 880
}

881
int __init_memblock memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
Y
Yinghai Lu 已提交
882
{
883
	memblock_cap_size(base, &size);
884
	return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
Y
Yinghai Lu 已提交
885 886
}

887

888
void __init_memblock memblock_set_current_limit(phys_addr_t limit)
889 890 891 892
{
	memblock.current_limit = limit;
}

T
Tejun Heo 已提交
893
static void __init_memblock memblock_dump(struct memblock_type *type, char *name)
894 895 896 897
{
	unsigned long long base, size;
	int i;

T
Tejun Heo 已提交
898
	pr_info(" %s.cnt  = 0x%lx\n", name, type->cnt);
899

T
Tejun Heo 已提交
900 901 902 903 904 905 906 907 908 909 910 911 912
	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);
913 914 915
	}
}

T
Tejun Heo 已提交
916
void __init_memblock __memblock_dump_all(void)
917 918
{
	pr_info("MEMBLOCK configuration:\n");
919 920 921
	pr_info(" memory size = %#llx reserved size = %#llx\n",
		(unsigned long long)memblock.memory.total_size,
		(unsigned long long)memblock.reserved.total_size);
922 923 924 925 926

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

927
void __init memblock_allow_resize(void)
928
{
929
	memblock_can_resize = 1;
930 931 932 933 934 935 936 937 938 939
}

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

940
#if defined(CONFIG_DEBUG_FS) && !defined(CONFIG_ARCH_DISCARD_MEMBLOCK)
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 978 979 980 981 982 983 984 985 986 987 988

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 */