xref: /linux/mm/memblock.c (revision 1f5026a7e21e409c2b9dd54f6dfb9446511fb7c5)
195f72d1eSYinghai Lu /*
295f72d1eSYinghai Lu  * Procedures for maintaining information about logical memory blocks.
395f72d1eSYinghai Lu  *
495f72d1eSYinghai Lu  * Peter Bergner, IBM Corp.	June 2001.
595f72d1eSYinghai Lu  * Copyright (C) 2001 Peter Bergner.
695f72d1eSYinghai Lu  *
795f72d1eSYinghai Lu  *      This program is free software; you can redistribute it and/or
895f72d1eSYinghai Lu  *      modify it under the terms of the GNU General Public License
995f72d1eSYinghai Lu  *      as published by the Free Software Foundation; either version
1095f72d1eSYinghai Lu  *      2 of the License, or (at your option) any later version.
1195f72d1eSYinghai Lu  */
1295f72d1eSYinghai Lu 
1395f72d1eSYinghai Lu #include <linux/kernel.h>
14142b45a7SBenjamin Herrenschmidt #include <linux/slab.h>
1595f72d1eSYinghai Lu #include <linux/init.h>
1695f72d1eSYinghai Lu #include <linux/bitops.h>
17449e8df3SBenjamin Herrenschmidt #include <linux/poison.h>
18c196f76fSBenjamin Herrenschmidt #include <linux/pfn.h>
196d03b885SBenjamin Herrenschmidt #include <linux/debugfs.h>
206d03b885SBenjamin Herrenschmidt #include <linux/seq_file.h>
2195f72d1eSYinghai Lu #include <linux/memblock.h>
2295f72d1eSYinghai Lu 
2310d06439SYinghai Lu struct memblock memblock __initdata_memblock;
2495f72d1eSYinghai Lu 
2510d06439SYinghai Lu int memblock_debug __initdata_memblock;
2610d06439SYinghai Lu int memblock_can_resize __initdata_memblock;
2710d06439SYinghai Lu static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS + 1] __initdata_memblock;
2810d06439SYinghai Lu static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS + 1] __initdata_memblock;
2995f72d1eSYinghai Lu 
30142b45a7SBenjamin Herrenschmidt /* inline so we don't get a warning when pr_debug is compiled out */
31142b45a7SBenjamin Herrenschmidt static inline const char *memblock_type_name(struct memblock_type *type)
32142b45a7SBenjamin Herrenschmidt {
33142b45a7SBenjamin Herrenschmidt 	if (type == &memblock.memory)
34142b45a7SBenjamin Herrenschmidt 		return "memory";
35142b45a7SBenjamin Herrenschmidt 	else if (type == &memblock.reserved)
36142b45a7SBenjamin Herrenschmidt 		return "reserved";
37142b45a7SBenjamin Herrenschmidt 	else
38142b45a7SBenjamin Herrenschmidt 		return "unknown";
39142b45a7SBenjamin Herrenschmidt }
40142b45a7SBenjamin Herrenschmidt 
416ed311b2SBenjamin Herrenschmidt /*
426ed311b2SBenjamin Herrenschmidt  * Address comparison utilities
436ed311b2SBenjamin Herrenschmidt  */
4410d06439SYinghai Lu static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
452898cc4cSBenjamin Herrenschmidt 				       phys_addr_t base2, phys_addr_t size2)
4695f72d1eSYinghai Lu {
4795f72d1eSYinghai Lu 	return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
4895f72d1eSYinghai Lu }
4995f72d1eSYinghai Lu 
5010d06439SYinghai Lu long __init_memblock memblock_overlaps_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
516ed311b2SBenjamin Herrenschmidt {
526ed311b2SBenjamin Herrenschmidt 	unsigned long i;
536ed311b2SBenjamin Herrenschmidt 
546ed311b2SBenjamin Herrenschmidt 	for (i = 0; i < type->cnt; i++) {
556ed311b2SBenjamin Herrenschmidt 		phys_addr_t rgnbase = type->regions[i].base;
566ed311b2SBenjamin Herrenschmidt 		phys_addr_t rgnsize = type->regions[i].size;
576ed311b2SBenjamin Herrenschmidt 		if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
586ed311b2SBenjamin Herrenschmidt 			break;
596ed311b2SBenjamin Herrenschmidt 	}
606ed311b2SBenjamin Herrenschmidt 
616ed311b2SBenjamin Herrenschmidt 	return (i < type->cnt) ? i : -1;
626ed311b2SBenjamin Herrenschmidt }
636ed311b2SBenjamin Herrenschmidt 
646ed311b2SBenjamin Herrenschmidt /*
656ed311b2SBenjamin Herrenschmidt  * Find, allocate, deallocate or reserve unreserved regions. All allocations
666ed311b2SBenjamin Herrenschmidt  * are top-down.
676ed311b2SBenjamin Herrenschmidt  */
686ed311b2SBenjamin Herrenschmidt 
69cd79481dSYinghai Lu static phys_addr_t __init_memblock memblock_find_region(phys_addr_t start, phys_addr_t end,
706ed311b2SBenjamin Herrenschmidt 					  phys_addr_t size, phys_addr_t align)
716ed311b2SBenjamin Herrenschmidt {
726ed311b2SBenjamin Herrenschmidt 	phys_addr_t base, res_base;
736ed311b2SBenjamin Herrenschmidt 	long j;
746ed311b2SBenjamin Herrenschmidt 
75f1af98c7SYinghai Lu 	/* In case, huge size is requested */
76f1af98c7SYinghai Lu 	if (end < size)
77*1f5026a7STejun Heo 		return 0;
78f1af98c7SYinghai Lu 
79348968ebSTejun Heo 	base = round_down(end - size, align);
80f1af98c7SYinghai Lu 
8125818f0fSBenjamin Herrenschmidt 	/* Prevent allocations returning 0 as it's also used to
8225818f0fSBenjamin Herrenschmidt 	 * indicate an allocation failure
8325818f0fSBenjamin Herrenschmidt 	 */
8425818f0fSBenjamin Herrenschmidt 	if (start == 0)
8525818f0fSBenjamin Herrenschmidt 		start = PAGE_SIZE;
8625818f0fSBenjamin Herrenschmidt 
876ed311b2SBenjamin Herrenschmidt 	while (start <= base) {
886ed311b2SBenjamin Herrenschmidt 		j = memblock_overlaps_region(&memblock.reserved, base, size);
896ed311b2SBenjamin Herrenschmidt 		if (j < 0)
906ed311b2SBenjamin Herrenschmidt 			return base;
916ed311b2SBenjamin Herrenschmidt 		res_base = memblock.reserved.regions[j].base;
926ed311b2SBenjamin Herrenschmidt 		if (res_base < size)
936ed311b2SBenjamin Herrenschmidt 			break;
94348968ebSTejun Heo 		base = round_down(res_base - size, align);
956ed311b2SBenjamin Herrenschmidt 	}
966ed311b2SBenjamin Herrenschmidt 
97*1f5026a7STejun Heo 	return 0;
986ed311b2SBenjamin Herrenschmidt }
996ed311b2SBenjamin Herrenschmidt 
1003661ca66SYinghai Lu static phys_addr_t __init_memblock memblock_find_base(phys_addr_t size,
1013661ca66SYinghai Lu 			phys_addr_t align, phys_addr_t start, phys_addr_t end)
1026ed311b2SBenjamin Herrenschmidt {
1036ed311b2SBenjamin Herrenschmidt 	long i;
1046ed311b2SBenjamin Herrenschmidt 
1056ed311b2SBenjamin Herrenschmidt 	BUG_ON(0 == size);
1066ed311b2SBenjamin Herrenschmidt 
1076ed311b2SBenjamin Herrenschmidt 	/* Pump up max_addr */
108fef501d4SBenjamin Herrenschmidt 	if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
109fef501d4SBenjamin Herrenschmidt 		end = memblock.current_limit;
1106ed311b2SBenjamin Herrenschmidt 
1116ed311b2SBenjamin Herrenschmidt 	/* We do a top-down search, this tends to limit memory
1126ed311b2SBenjamin Herrenschmidt 	 * fragmentation by keeping early boot allocs near the
1136ed311b2SBenjamin Herrenschmidt 	 * top of memory
1146ed311b2SBenjamin Herrenschmidt 	 */
1156ed311b2SBenjamin Herrenschmidt 	for (i = memblock.memory.cnt - 1; i >= 0; i--) {
1166ed311b2SBenjamin Herrenschmidt 		phys_addr_t memblockbase = memblock.memory.regions[i].base;
1176ed311b2SBenjamin Herrenschmidt 		phys_addr_t memblocksize = memblock.memory.regions[i].size;
118fef501d4SBenjamin Herrenschmidt 		phys_addr_t bottom, top, found;
1196ed311b2SBenjamin Herrenschmidt 
1206ed311b2SBenjamin Herrenschmidt 		if (memblocksize < size)
1216ed311b2SBenjamin Herrenschmidt 			continue;
122fef501d4SBenjamin Herrenschmidt 		if ((memblockbase + memblocksize) <= start)
123fef501d4SBenjamin Herrenschmidt 			break;
124fef501d4SBenjamin Herrenschmidt 		bottom = max(memblockbase, start);
125fef501d4SBenjamin Herrenschmidt 		top = min(memblockbase + memblocksize, end);
126fef501d4SBenjamin Herrenschmidt 		if (bottom >= top)
127fef501d4SBenjamin Herrenschmidt 			continue;
128fef501d4SBenjamin Herrenschmidt 		found = memblock_find_region(bottom, top, size, align);
129*1f5026a7STejun Heo 		if (found)
130fef501d4SBenjamin Herrenschmidt 			return found;
1316ed311b2SBenjamin Herrenschmidt 	}
132*1f5026a7STejun Heo 	return 0;
1336ed311b2SBenjamin Herrenschmidt }
1346ed311b2SBenjamin Herrenschmidt 
1355303b68fSYinghai Lu /*
1365303b68fSYinghai Lu  * Find a free area with specified alignment in a specific range.
1375303b68fSYinghai Lu  */
1385303b68fSYinghai Lu u64 __init_memblock memblock_find_in_range(u64 start, u64 end, u64 size, u64 align)
1395303b68fSYinghai Lu {
1405303b68fSYinghai Lu 	return memblock_find_base(size, align, start, end);
1415303b68fSYinghai Lu }
1425303b68fSYinghai Lu 
1437950c407SYinghai Lu /*
1447950c407SYinghai Lu  * Free memblock.reserved.regions
1457950c407SYinghai Lu  */
1467950c407SYinghai Lu int __init_memblock memblock_free_reserved_regions(void)
1477950c407SYinghai Lu {
1487950c407SYinghai Lu 	if (memblock.reserved.regions == memblock_reserved_init_regions)
1497950c407SYinghai Lu 		return 0;
1507950c407SYinghai Lu 
1517950c407SYinghai Lu 	return memblock_free(__pa(memblock.reserved.regions),
1527950c407SYinghai Lu 		 sizeof(struct memblock_region) * memblock.reserved.max);
1537950c407SYinghai Lu }
1547950c407SYinghai Lu 
1557950c407SYinghai Lu /*
1567950c407SYinghai Lu  * Reserve memblock.reserved.regions
1577950c407SYinghai Lu  */
1587950c407SYinghai Lu int __init_memblock memblock_reserve_reserved_regions(void)
1597950c407SYinghai Lu {
1607950c407SYinghai Lu 	if (memblock.reserved.regions == memblock_reserved_init_regions)
1617950c407SYinghai Lu 		return 0;
1627950c407SYinghai Lu 
1637950c407SYinghai Lu 	return memblock_reserve(__pa(memblock.reserved.regions),
1647950c407SYinghai Lu 		 sizeof(struct memblock_region) * memblock.reserved.max);
1657950c407SYinghai Lu }
1667950c407SYinghai Lu 
16710d06439SYinghai Lu static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
16895f72d1eSYinghai Lu {
16995f72d1eSYinghai Lu 	unsigned long i;
17095f72d1eSYinghai Lu 
171e3239ff9SBenjamin Herrenschmidt 	for (i = r; i < type->cnt - 1; i++) {
172e3239ff9SBenjamin Herrenschmidt 		type->regions[i].base = type->regions[i + 1].base;
173e3239ff9SBenjamin Herrenschmidt 		type->regions[i].size = type->regions[i + 1].size;
17495f72d1eSYinghai Lu 	}
175e3239ff9SBenjamin Herrenschmidt 	type->cnt--;
17695f72d1eSYinghai Lu 
1778f7a6605SBenjamin Herrenschmidt 	/* Special case for empty arrays */
1788f7a6605SBenjamin Herrenschmidt 	if (type->cnt == 0) {
1798f7a6605SBenjamin Herrenschmidt 		type->cnt = 1;
1808f7a6605SBenjamin Herrenschmidt 		type->regions[0].base = 0;
1818f7a6605SBenjamin Herrenschmidt 		type->regions[0].size = 0;
1828f7a6605SBenjamin Herrenschmidt 	}
18395f72d1eSYinghai Lu }
18495f72d1eSYinghai Lu 
185142b45a7SBenjamin Herrenschmidt /* Defined below but needed now */
186142b45a7SBenjamin Herrenschmidt static long memblock_add_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size);
187142b45a7SBenjamin Herrenschmidt 
18810d06439SYinghai Lu static int __init_memblock memblock_double_array(struct memblock_type *type)
189142b45a7SBenjamin Herrenschmidt {
190142b45a7SBenjamin Herrenschmidt 	struct memblock_region *new_array, *old_array;
191142b45a7SBenjamin Herrenschmidt 	phys_addr_t old_size, new_size, addr;
192142b45a7SBenjamin Herrenschmidt 	int use_slab = slab_is_available();
193142b45a7SBenjamin Herrenschmidt 
194142b45a7SBenjamin Herrenschmidt 	/* We don't allow resizing until we know about the reserved regions
195142b45a7SBenjamin Herrenschmidt 	 * of memory that aren't suitable for allocation
196142b45a7SBenjamin Herrenschmidt 	 */
197142b45a7SBenjamin Herrenschmidt 	if (!memblock_can_resize)
198142b45a7SBenjamin Herrenschmidt 		return -1;
199142b45a7SBenjamin Herrenschmidt 
200142b45a7SBenjamin Herrenschmidt 	/* Calculate new doubled size */
201142b45a7SBenjamin Herrenschmidt 	old_size = type->max * sizeof(struct memblock_region);
202142b45a7SBenjamin Herrenschmidt 	new_size = old_size << 1;
203142b45a7SBenjamin Herrenschmidt 
204142b45a7SBenjamin Herrenschmidt 	/* Try to find some space for it.
205142b45a7SBenjamin Herrenschmidt 	 *
206142b45a7SBenjamin Herrenschmidt 	 * WARNING: We assume that either slab_is_available() and we use it or
207142b45a7SBenjamin Herrenschmidt 	 * we use MEMBLOCK for allocations. That means that this is unsafe to use
208142b45a7SBenjamin Herrenschmidt 	 * when bootmem is currently active (unless bootmem itself is implemented
209142b45a7SBenjamin Herrenschmidt 	 * on top of MEMBLOCK which isn't the case yet)
210142b45a7SBenjamin Herrenschmidt 	 *
211142b45a7SBenjamin Herrenschmidt 	 * This should however not be an issue for now, as we currently only
212142b45a7SBenjamin Herrenschmidt 	 * call into MEMBLOCK while it's still active, or much later when slab is
213142b45a7SBenjamin Herrenschmidt 	 * active for memory hotplug operations
214142b45a7SBenjamin Herrenschmidt 	 */
215142b45a7SBenjamin Herrenschmidt 	if (use_slab) {
216142b45a7SBenjamin Herrenschmidt 		new_array = kmalloc(new_size, GFP_KERNEL);
217*1f5026a7STejun Heo 		addr = new_array ? __pa(new_array) : 0;
218142b45a7SBenjamin Herrenschmidt 	} else
219fef501d4SBenjamin Herrenschmidt 		addr = memblock_find_base(new_size, sizeof(phys_addr_t), 0, MEMBLOCK_ALLOC_ACCESSIBLE);
220*1f5026a7STejun Heo 	if (!addr) {
221142b45a7SBenjamin Herrenschmidt 		pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
222142b45a7SBenjamin Herrenschmidt 		       memblock_type_name(type), type->max, type->max * 2);
223142b45a7SBenjamin Herrenschmidt 		return -1;
224142b45a7SBenjamin Herrenschmidt 	}
225142b45a7SBenjamin Herrenschmidt 	new_array = __va(addr);
226142b45a7SBenjamin Herrenschmidt 
227ea9e4376SYinghai Lu 	memblock_dbg("memblock: %s array is doubled to %ld at [%#010llx-%#010llx]",
228ea9e4376SYinghai Lu 		 memblock_type_name(type), type->max * 2, (u64)addr, (u64)addr + new_size - 1);
229ea9e4376SYinghai Lu 
230142b45a7SBenjamin Herrenschmidt 	/* Found space, we now need to move the array over before
231142b45a7SBenjamin Herrenschmidt 	 * we add the reserved region since it may be our reserved
232142b45a7SBenjamin Herrenschmidt 	 * array itself that is full.
233142b45a7SBenjamin Herrenschmidt 	 */
234142b45a7SBenjamin Herrenschmidt 	memcpy(new_array, type->regions, old_size);
235142b45a7SBenjamin Herrenschmidt 	memset(new_array + type->max, 0, old_size);
236142b45a7SBenjamin Herrenschmidt 	old_array = type->regions;
237142b45a7SBenjamin Herrenschmidt 	type->regions = new_array;
238142b45a7SBenjamin Herrenschmidt 	type->max <<= 1;
239142b45a7SBenjamin Herrenschmidt 
240142b45a7SBenjamin Herrenschmidt 	/* If we use SLAB that's it, we are done */
241142b45a7SBenjamin Herrenschmidt 	if (use_slab)
242142b45a7SBenjamin Herrenschmidt 		return 0;
243142b45a7SBenjamin Herrenschmidt 
244142b45a7SBenjamin Herrenschmidt 	/* Add the new reserved region now. Should not fail ! */
2458f7a6605SBenjamin Herrenschmidt 	BUG_ON(memblock_add_region(&memblock.reserved, addr, new_size));
246142b45a7SBenjamin Herrenschmidt 
247142b45a7SBenjamin Herrenschmidt 	/* If the array wasn't our static init one, then free it. We only do
248142b45a7SBenjamin Herrenschmidt 	 * that before SLAB is available as later on, we don't know whether
249142b45a7SBenjamin Herrenschmidt 	 * to use kfree or free_bootmem_pages(). Shouldn't be a big deal
250142b45a7SBenjamin Herrenschmidt 	 * anyways
251142b45a7SBenjamin Herrenschmidt 	 */
252142b45a7SBenjamin Herrenschmidt 	if (old_array != memblock_memory_init_regions &&
253142b45a7SBenjamin Herrenschmidt 	    old_array != memblock_reserved_init_regions)
254142b45a7SBenjamin Herrenschmidt 		memblock_free(__pa(old_array), old_size);
255142b45a7SBenjamin Herrenschmidt 
256142b45a7SBenjamin Herrenschmidt 	return 0;
257142b45a7SBenjamin Herrenschmidt }
258142b45a7SBenjamin Herrenschmidt 
25910d06439SYinghai Lu extern int __init_memblock __weak memblock_memory_can_coalesce(phys_addr_t addr1, phys_addr_t size1,
260d2cd563bSBenjamin Herrenschmidt 					  phys_addr_t addr2, phys_addr_t size2)
261d2cd563bSBenjamin Herrenschmidt {
262d2cd563bSBenjamin Herrenschmidt 	return 1;
263d2cd563bSBenjamin Herrenschmidt }
264d2cd563bSBenjamin Herrenschmidt 
2658f7a6605SBenjamin Herrenschmidt static long __init_memblock memblock_add_region(struct memblock_type *type,
2668f7a6605SBenjamin Herrenschmidt 						phys_addr_t base, phys_addr_t size)
26795f72d1eSYinghai Lu {
2688f7a6605SBenjamin Herrenschmidt 	phys_addr_t end = base + size;
2698f7a6605SBenjamin Herrenschmidt 	int i, slot = -1;
27095f72d1eSYinghai Lu 
2718f7a6605SBenjamin Herrenschmidt 	/* First try and coalesce this MEMBLOCK with others */
2728f7a6605SBenjamin Herrenschmidt 	for (i = 0; i < type->cnt; i++) {
2738f7a6605SBenjamin Herrenschmidt 		struct memblock_region *rgn = &type->regions[i];
2748f7a6605SBenjamin Herrenschmidt 		phys_addr_t rend = rgn->base + rgn->size;
2758f7a6605SBenjamin Herrenschmidt 
2768f7a6605SBenjamin Herrenschmidt 		/* Exit if there's no possible hits */
2778f7a6605SBenjamin Herrenschmidt 		if (rgn->base > end || rgn->size == 0)
2788f7a6605SBenjamin Herrenschmidt 			break;
2798f7a6605SBenjamin Herrenschmidt 
2808f7a6605SBenjamin Herrenschmidt 		/* Check if we are fully enclosed within an existing
2818f7a6605SBenjamin Herrenschmidt 		 * block
2828f7a6605SBenjamin Herrenschmidt 		 */
2838f7a6605SBenjamin Herrenschmidt 		if (rgn->base <= base && rend >= end)
2848f7a6605SBenjamin Herrenschmidt 			return 0;
2858f7a6605SBenjamin Herrenschmidt 
2868f7a6605SBenjamin Herrenschmidt 		/* Check if we overlap or are adjacent with the bottom
2878f7a6605SBenjamin Herrenschmidt 		 * of a block.
2888f7a6605SBenjamin Herrenschmidt 		 */
2898f7a6605SBenjamin Herrenschmidt 		if (base < rgn->base && end >= rgn->base) {
2908f7a6605SBenjamin Herrenschmidt 			/* If we can't coalesce, create a new block */
2918f7a6605SBenjamin Herrenschmidt 			if (!memblock_memory_can_coalesce(base, size,
2928f7a6605SBenjamin Herrenschmidt 							  rgn->base,
2938f7a6605SBenjamin Herrenschmidt 							  rgn->size)) {
2948f7a6605SBenjamin Herrenschmidt 				/* Overlap & can't coalesce are mutually
2958f7a6605SBenjamin Herrenschmidt 				 * exclusive, if you do that, be prepared
2968f7a6605SBenjamin Herrenschmidt 				 * for trouble
2978f7a6605SBenjamin Herrenschmidt 				 */
2988f7a6605SBenjamin Herrenschmidt 				WARN_ON(end != rgn->base);
2998f7a6605SBenjamin Herrenschmidt 				goto new_block;
3008f7a6605SBenjamin Herrenschmidt 			}
3018f7a6605SBenjamin Herrenschmidt 			/* We extend the bottom of the block down to our
3028f7a6605SBenjamin Herrenschmidt 			 * base
3038f7a6605SBenjamin Herrenschmidt 			 */
3048f7a6605SBenjamin Herrenschmidt 			rgn->base = base;
3058f7a6605SBenjamin Herrenschmidt 			rgn->size = rend - base;
3068f7a6605SBenjamin Herrenschmidt 
3078f7a6605SBenjamin Herrenschmidt 			/* Return if we have nothing else to allocate
3088f7a6605SBenjamin Herrenschmidt 			 * (fully coalesced)
3098f7a6605SBenjamin Herrenschmidt 			 */
3108f7a6605SBenjamin Herrenschmidt 			if (rend >= end)
3118f7a6605SBenjamin Herrenschmidt 				return 0;
3128f7a6605SBenjamin Herrenschmidt 
3138f7a6605SBenjamin Herrenschmidt 			/* We continue processing from the end of the
3148f7a6605SBenjamin Herrenschmidt 			 * coalesced block.
3158f7a6605SBenjamin Herrenschmidt 			 */
3168f7a6605SBenjamin Herrenschmidt 			base = rend;
3178f7a6605SBenjamin Herrenschmidt 			size = end - base;
3188f7a6605SBenjamin Herrenschmidt 		}
3198f7a6605SBenjamin Herrenschmidt 
3208f7a6605SBenjamin Herrenschmidt 		/* Now check if we overlap or are adjacent with the
3218f7a6605SBenjamin Herrenschmidt 		 * top of a block
3228f7a6605SBenjamin Herrenschmidt 		 */
3238f7a6605SBenjamin Herrenschmidt 		if (base <= rend && end >= rend) {
3248f7a6605SBenjamin Herrenschmidt 			/* If we can't coalesce, create a new block */
3258f7a6605SBenjamin Herrenschmidt 			if (!memblock_memory_can_coalesce(rgn->base,
3268f7a6605SBenjamin Herrenschmidt 							  rgn->size,
3278f7a6605SBenjamin Herrenschmidt 							  base, size)) {
3288f7a6605SBenjamin Herrenschmidt 				/* Overlap & can't coalesce are mutually
3298f7a6605SBenjamin Herrenschmidt 				 * exclusive, if you do that, be prepared
3308f7a6605SBenjamin Herrenschmidt 				 * for trouble
3318f7a6605SBenjamin Herrenschmidt 				 */
3328f7a6605SBenjamin Herrenschmidt 				WARN_ON(rend != base);
3338f7a6605SBenjamin Herrenschmidt 				goto new_block;
3348f7a6605SBenjamin Herrenschmidt 			}
3358f7a6605SBenjamin Herrenschmidt 			/* We adjust our base down to enclose the
3368f7a6605SBenjamin Herrenschmidt 			 * original block and destroy it. It will be
3378f7a6605SBenjamin Herrenschmidt 			 * part of our new allocation. Since we've
3388f7a6605SBenjamin Herrenschmidt 			 * freed an entry, we know we won't fail
3398f7a6605SBenjamin Herrenschmidt 			 * to allocate one later, so we won't risk
3408f7a6605SBenjamin Herrenschmidt 			 * losing the original block allocation.
3418f7a6605SBenjamin Herrenschmidt 			 */
3428f7a6605SBenjamin Herrenschmidt 			size += (base - rgn->base);
3438f7a6605SBenjamin Herrenschmidt 			base = rgn->base;
3448f7a6605SBenjamin Herrenschmidt 			memblock_remove_region(type, i--);
3458f7a6605SBenjamin Herrenschmidt 		}
3468f7a6605SBenjamin Herrenschmidt 	}
3478f7a6605SBenjamin Herrenschmidt 
3488f7a6605SBenjamin Herrenschmidt 	/* If the array is empty, special case, replace the fake
3498f7a6605SBenjamin Herrenschmidt 	 * filler region and return
3508f7a6605SBenjamin Herrenschmidt 	 */
351e3239ff9SBenjamin Herrenschmidt 	if ((type->cnt == 1) && (type->regions[0].size == 0)) {
352e3239ff9SBenjamin Herrenschmidt 		type->regions[0].base = base;
353e3239ff9SBenjamin Herrenschmidt 		type->regions[0].size = size;
35495f72d1eSYinghai Lu 		return 0;
35595f72d1eSYinghai Lu 	}
35695f72d1eSYinghai Lu 
3578f7a6605SBenjamin Herrenschmidt  new_block:
358142b45a7SBenjamin Herrenschmidt 	/* If we are out of space, we fail. It's too late to resize the array
359142b45a7SBenjamin Herrenschmidt 	 * but then this shouldn't have happened in the first place.
360142b45a7SBenjamin Herrenschmidt 	 */
361142b45a7SBenjamin Herrenschmidt 	if (WARN_ON(type->cnt >= type->max))
36295f72d1eSYinghai Lu 		return -1;
36395f72d1eSYinghai Lu 
36495f72d1eSYinghai Lu 	/* Couldn't coalesce the MEMBLOCK, so add it to the sorted table. */
365e3239ff9SBenjamin Herrenschmidt 	for (i = type->cnt - 1; i >= 0; i--) {
366e3239ff9SBenjamin Herrenschmidt 		if (base < type->regions[i].base) {
367e3239ff9SBenjamin Herrenschmidt 			type->regions[i+1].base = type->regions[i].base;
368e3239ff9SBenjamin Herrenschmidt 			type->regions[i+1].size = type->regions[i].size;
36995f72d1eSYinghai Lu 		} else {
370e3239ff9SBenjamin Herrenschmidt 			type->regions[i+1].base = base;
371e3239ff9SBenjamin Herrenschmidt 			type->regions[i+1].size = size;
3728f7a6605SBenjamin Herrenschmidt 			slot = i + 1;
37395f72d1eSYinghai Lu 			break;
37495f72d1eSYinghai Lu 		}
37595f72d1eSYinghai Lu 	}
376e3239ff9SBenjamin Herrenschmidt 	if (base < type->regions[0].base) {
377e3239ff9SBenjamin Herrenschmidt 		type->regions[0].base = base;
378e3239ff9SBenjamin Herrenschmidt 		type->regions[0].size = size;
3798f7a6605SBenjamin Herrenschmidt 		slot = 0;
38095f72d1eSYinghai Lu 	}
381e3239ff9SBenjamin Herrenschmidt 	type->cnt++;
38295f72d1eSYinghai Lu 
383142b45a7SBenjamin Herrenschmidt 	/* The array is full ? Try to resize it. If that fails, we undo
384142b45a7SBenjamin Herrenschmidt 	 * our allocation and return an error
385142b45a7SBenjamin Herrenschmidt 	 */
386142b45a7SBenjamin Herrenschmidt 	if (type->cnt == type->max && memblock_double_array(type)) {
3878f7a6605SBenjamin Herrenschmidt 		BUG_ON(slot < 0);
3888f7a6605SBenjamin Herrenschmidt 		memblock_remove_region(type, slot);
389142b45a7SBenjamin Herrenschmidt 		return -1;
390142b45a7SBenjamin Herrenschmidt 	}
391142b45a7SBenjamin Herrenschmidt 
39295f72d1eSYinghai Lu 	return 0;
39395f72d1eSYinghai Lu }
39495f72d1eSYinghai Lu 
39510d06439SYinghai Lu long __init_memblock memblock_add(phys_addr_t base, phys_addr_t size)
39695f72d1eSYinghai Lu {
397e3239ff9SBenjamin Herrenschmidt 	return memblock_add_region(&memblock.memory, base, size);
39895f72d1eSYinghai Lu 
39995f72d1eSYinghai Lu }
40095f72d1eSYinghai Lu 
4018f7a6605SBenjamin Herrenschmidt static long __init_memblock __memblock_remove(struct memblock_type *type,
4028f7a6605SBenjamin Herrenschmidt 					      phys_addr_t base, phys_addr_t size)
40395f72d1eSYinghai Lu {
4042898cc4cSBenjamin Herrenschmidt 	phys_addr_t end = base + size;
40595f72d1eSYinghai Lu 	int i;
40695f72d1eSYinghai Lu 
4078f7a6605SBenjamin Herrenschmidt 	/* Walk through the array for collisions */
408e3239ff9SBenjamin Herrenschmidt 	for (i = 0; i < type->cnt; i++) {
4098f7a6605SBenjamin Herrenschmidt 		struct memblock_region *rgn = &type->regions[i];
4108f7a6605SBenjamin Herrenschmidt 		phys_addr_t rend = rgn->base + rgn->size;
41195f72d1eSYinghai Lu 
4128f7a6605SBenjamin Herrenschmidt 		/* Nothing more to do, exit */
4138f7a6605SBenjamin Herrenschmidt 		if (rgn->base > end || rgn->size == 0)
4148f7a6605SBenjamin Herrenschmidt 			break;
4158f7a6605SBenjamin Herrenschmidt 
4168f7a6605SBenjamin Herrenschmidt 		/* If we fully enclose the block, drop it */
4178f7a6605SBenjamin Herrenschmidt 		if (base <= rgn->base && end >= rend) {
4188f7a6605SBenjamin Herrenschmidt 			memblock_remove_region(type, i--);
4198f7a6605SBenjamin Herrenschmidt 			continue;
4208f7a6605SBenjamin Herrenschmidt 		}
4218f7a6605SBenjamin Herrenschmidt 
4228f7a6605SBenjamin Herrenschmidt 		/* If we are fully enclosed within a block
4238f7a6605SBenjamin Herrenschmidt 		 * then we need to split it and we are done
4248f7a6605SBenjamin Herrenschmidt 		 */
4258f7a6605SBenjamin Herrenschmidt 		if (base > rgn->base && end < rend) {
4268f7a6605SBenjamin Herrenschmidt 			rgn->size = base - rgn->base;
4278f7a6605SBenjamin Herrenschmidt 			if (!memblock_add_region(type, end, rend - end))
4288f7a6605SBenjamin Herrenschmidt 				return 0;
4298f7a6605SBenjamin Herrenschmidt 			/* Failure to split is bad, we at least
4308f7a6605SBenjamin Herrenschmidt 			 * restore the block before erroring
4318f7a6605SBenjamin Herrenschmidt 			 */
4328f7a6605SBenjamin Herrenschmidt 			rgn->size = rend - rgn->base;
4338f7a6605SBenjamin Herrenschmidt 			WARN_ON(1);
4348f7a6605SBenjamin Herrenschmidt 			return -1;
4358f7a6605SBenjamin Herrenschmidt 		}
4368f7a6605SBenjamin Herrenschmidt 
4378f7a6605SBenjamin Herrenschmidt 		/* Check if we need to trim the bottom of a block */
4388f7a6605SBenjamin Herrenschmidt 		if (rgn->base < end && rend > end) {
4398f7a6605SBenjamin Herrenschmidt 			rgn->size -= end - rgn->base;
4408f7a6605SBenjamin Herrenschmidt 			rgn->base = end;
44195f72d1eSYinghai Lu 			break;
44295f72d1eSYinghai Lu 		}
44395f72d1eSYinghai Lu 
4448f7a6605SBenjamin Herrenschmidt 		/* And check if we need to trim the top of a block */
4458f7a6605SBenjamin Herrenschmidt 		if (base < rend)
4468f7a6605SBenjamin Herrenschmidt 			rgn->size -= rend - base;
44795f72d1eSYinghai Lu 
44895f72d1eSYinghai Lu 	}
44995f72d1eSYinghai Lu 	return 0;
45095f72d1eSYinghai Lu }
45195f72d1eSYinghai Lu 
45210d06439SYinghai Lu long __init_memblock memblock_remove(phys_addr_t base, phys_addr_t size)
45395f72d1eSYinghai Lu {
45495f72d1eSYinghai Lu 	return __memblock_remove(&memblock.memory, base, size);
45595f72d1eSYinghai Lu }
45695f72d1eSYinghai Lu 
4573661ca66SYinghai Lu long __init_memblock memblock_free(phys_addr_t base, phys_addr_t size)
45895f72d1eSYinghai Lu {
45995f72d1eSYinghai Lu 	return __memblock_remove(&memblock.reserved, base, size);
46095f72d1eSYinghai Lu }
46195f72d1eSYinghai Lu 
4623661ca66SYinghai Lu long __init_memblock memblock_reserve(phys_addr_t base, phys_addr_t size)
46395f72d1eSYinghai Lu {
464e3239ff9SBenjamin Herrenschmidt 	struct memblock_type *_rgn = &memblock.reserved;
46595f72d1eSYinghai Lu 
46695f72d1eSYinghai Lu 	BUG_ON(0 == size);
46795f72d1eSYinghai Lu 
46895f72d1eSYinghai Lu 	return memblock_add_region(_rgn, base, size);
46995f72d1eSYinghai Lu }
47095f72d1eSYinghai Lu 
4716ed311b2SBenjamin Herrenschmidt phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
47295f72d1eSYinghai Lu {
4736ed311b2SBenjamin Herrenschmidt 	phys_addr_t found;
47495f72d1eSYinghai Lu 
4756ed311b2SBenjamin Herrenschmidt 	/* We align the size to limit fragmentation. Without this, a lot of
4766ed311b2SBenjamin Herrenschmidt 	 * small allocs quickly eat up the whole reserve array on sparc
4776ed311b2SBenjamin Herrenschmidt 	 */
478348968ebSTejun Heo 	size = round_up(size, align);
4796ed311b2SBenjamin Herrenschmidt 
480fef501d4SBenjamin Herrenschmidt 	found = memblock_find_base(size, align, 0, max_addr);
481*1f5026a7STejun Heo 	if (found && !memblock_add_region(&memblock.reserved, found, size))
4826ed311b2SBenjamin Herrenschmidt 		return found;
4836ed311b2SBenjamin Herrenschmidt 
4846ed311b2SBenjamin Herrenschmidt 	return 0;
48595f72d1eSYinghai Lu }
48695f72d1eSYinghai Lu 
4876ed311b2SBenjamin Herrenschmidt phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
48895f72d1eSYinghai Lu {
4896ed311b2SBenjamin Herrenschmidt 	phys_addr_t alloc;
4906ed311b2SBenjamin Herrenschmidt 
4916ed311b2SBenjamin Herrenschmidt 	alloc = __memblock_alloc_base(size, align, max_addr);
4926ed311b2SBenjamin Herrenschmidt 
4936ed311b2SBenjamin Herrenschmidt 	if (alloc == 0)
4946ed311b2SBenjamin Herrenschmidt 		panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
4956ed311b2SBenjamin Herrenschmidt 		      (unsigned long long) size, (unsigned long long) max_addr);
4966ed311b2SBenjamin Herrenschmidt 
4976ed311b2SBenjamin Herrenschmidt 	return alloc;
49895f72d1eSYinghai Lu }
49995f72d1eSYinghai Lu 
5006ed311b2SBenjamin Herrenschmidt phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
50195f72d1eSYinghai Lu {
5026ed311b2SBenjamin Herrenschmidt 	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
50395f72d1eSYinghai Lu }
50495f72d1eSYinghai Lu 
50595f72d1eSYinghai Lu 
5066ed311b2SBenjamin Herrenschmidt /*
5076ed311b2SBenjamin Herrenschmidt  * Additional node-local allocators. Search for node memory is bottom up
5086ed311b2SBenjamin Herrenschmidt  * and walks memblock regions within that node bottom-up as well, but allocation
509c196f76fSBenjamin Herrenschmidt  * within an memblock region is top-down. XXX I plan to fix that at some stage
510c196f76fSBenjamin Herrenschmidt  *
511c196f76fSBenjamin Herrenschmidt  * WARNING: Only available after early_node_map[] has been populated,
512c196f76fSBenjamin Herrenschmidt  * on some architectures, that is after all the calls to add_active_range()
513c196f76fSBenjamin Herrenschmidt  * have been done to populate it.
5146ed311b2SBenjamin Herrenschmidt  */
51595f72d1eSYinghai Lu 
5162898cc4cSBenjamin Herrenschmidt phys_addr_t __weak __init memblock_nid_range(phys_addr_t start, phys_addr_t end, int *nid)
517c3f72b57SBenjamin Herrenschmidt {
518c196f76fSBenjamin Herrenschmidt #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
519c196f76fSBenjamin Herrenschmidt 	/*
520c196f76fSBenjamin Herrenschmidt 	 * This code originates from sparc which really wants use to walk by addresses
521c196f76fSBenjamin Herrenschmidt 	 * and returns the nid. This is not very convenient for early_pfn_map[] users
522c196f76fSBenjamin Herrenschmidt 	 * as the map isn't sorted yet, and it really wants to be walked by nid.
523c196f76fSBenjamin Herrenschmidt 	 *
524c196f76fSBenjamin Herrenschmidt 	 * For now, I implement the inefficient method below which walks the early
525c196f76fSBenjamin Herrenschmidt 	 * map multiple times. Eventually we may want to use an ARCH config option
526c196f76fSBenjamin Herrenschmidt 	 * to implement a completely different method for both case.
527c196f76fSBenjamin Herrenschmidt 	 */
528c196f76fSBenjamin Herrenschmidt 	unsigned long start_pfn, end_pfn;
529c196f76fSBenjamin Herrenschmidt 	int i;
530c196f76fSBenjamin Herrenschmidt 
531c196f76fSBenjamin Herrenschmidt 	for (i = 0; i < MAX_NUMNODES; i++) {
532c196f76fSBenjamin Herrenschmidt 		get_pfn_range_for_nid(i, &start_pfn, &end_pfn);
533c196f76fSBenjamin Herrenschmidt 		if (start < PFN_PHYS(start_pfn) || start >= PFN_PHYS(end_pfn))
534c196f76fSBenjamin Herrenschmidt 			continue;
535c196f76fSBenjamin Herrenschmidt 		*nid = i;
536c196f76fSBenjamin Herrenschmidt 		return min(end, PFN_PHYS(end_pfn));
537c196f76fSBenjamin Herrenschmidt 	}
538c196f76fSBenjamin Herrenschmidt #endif
539c3f72b57SBenjamin Herrenschmidt 	*nid = 0;
540c3f72b57SBenjamin Herrenschmidt 
541c3f72b57SBenjamin Herrenschmidt 	return end;
542c3f72b57SBenjamin Herrenschmidt }
543c3f72b57SBenjamin Herrenschmidt 
5442898cc4cSBenjamin Herrenschmidt static phys_addr_t __init memblock_alloc_nid_region(struct memblock_region *mp,
5452898cc4cSBenjamin Herrenschmidt 					       phys_addr_t size,
5462898cc4cSBenjamin Herrenschmidt 					       phys_addr_t align, int nid)
54795f72d1eSYinghai Lu {
5482898cc4cSBenjamin Herrenschmidt 	phys_addr_t start, end;
54995f72d1eSYinghai Lu 
55095f72d1eSYinghai Lu 	start = mp->base;
55195f72d1eSYinghai Lu 	end = start + mp->size;
55295f72d1eSYinghai Lu 
553348968ebSTejun Heo 	start = round_up(start, align);
55495f72d1eSYinghai Lu 	while (start < end) {
5552898cc4cSBenjamin Herrenschmidt 		phys_addr_t this_end;
55695f72d1eSYinghai Lu 		int this_nid;
55795f72d1eSYinghai Lu 
55835a1f0bdSBenjamin Herrenschmidt 		this_end = memblock_nid_range(start, end, &this_nid);
55995f72d1eSYinghai Lu 		if (this_nid == nid) {
5603a9c2c81SBenjamin Herrenschmidt 			phys_addr_t ret = memblock_find_region(start, this_end, size, align);
561*1f5026a7STejun Heo 			if (ret &&
5628f7a6605SBenjamin Herrenschmidt 			    !memblock_add_region(&memblock.reserved, ret, size))
56395f72d1eSYinghai Lu 				return ret;
56495f72d1eSYinghai Lu 		}
56595f72d1eSYinghai Lu 		start = this_end;
56695f72d1eSYinghai Lu 	}
56795f72d1eSYinghai Lu 
568*1f5026a7STejun Heo 	return 0;
56995f72d1eSYinghai Lu }
57095f72d1eSYinghai Lu 
5712898cc4cSBenjamin Herrenschmidt phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
57295f72d1eSYinghai Lu {
573e3239ff9SBenjamin Herrenschmidt 	struct memblock_type *mem = &memblock.memory;
57495f72d1eSYinghai Lu 	int i;
57595f72d1eSYinghai Lu 
57695f72d1eSYinghai Lu 	BUG_ON(0 == size);
57795f72d1eSYinghai Lu 
5787f219c73SBenjamin Herrenschmidt 	/* We align the size to limit fragmentation. Without this, a lot of
5797f219c73SBenjamin Herrenschmidt 	 * small allocs quickly eat up the whole reserve array on sparc
5807f219c73SBenjamin Herrenschmidt 	 */
581348968ebSTejun Heo 	size = round_up(size, align);
5827f219c73SBenjamin Herrenschmidt 
583c3f72b57SBenjamin Herrenschmidt 	/* We do a bottom-up search for a region with the right
584c3f72b57SBenjamin Herrenschmidt 	 * nid since that's easier considering how memblock_nid_range()
585c3f72b57SBenjamin Herrenschmidt 	 * works
586c3f72b57SBenjamin Herrenschmidt 	 */
58795f72d1eSYinghai Lu 	for (i = 0; i < mem->cnt; i++) {
5882898cc4cSBenjamin Herrenschmidt 		phys_addr_t ret = memblock_alloc_nid_region(&mem->regions[i],
58995f72d1eSYinghai Lu 					       size, align, nid);
590*1f5026a7STejun Heo 		if (ret)
59195f72d1eSYinghai Lu 			return ret;
59295f72d1eSYinghai Lu 	}
59395f72d1eSYinghai Lu 
5949d1e2492SBenjamin Herrenschmidt 	return 0;
5959d1e2492SBenjamin Herrenschmidt }
5969d1e2492SBenjamin Herrenschmidt 
5979d1e2492SBenjamin Herrenschmidt phys_addr_t __init memblock_alloc_try_nid(phys_addr_t size, phys_addr_t align, int nid)
5989d1e2492SBenjamin Herrenschmidt {
5999d1e2492SBenjamin Herrenschmidt 	phys_addr_t res = memblock_alloc_nid(size, align, nid);
6009d1e2492SBenjamin Herrenschmidt 
6019d1e2492SBenjamin Herrenschmidt 	if (res)
6029d1e2492SBenjamin Herrenschmidt 		return res;
60315fb0972STejun Heo 	return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
60495f72d1eSYinghai Lu }
60595f72d1eSYinghai Lu 
6069d1e2492SBenjamin Herrenschmidt 
6079d1e2492SBenjamin Herrenschmidt /*
6089d1e2492SBenjamin Herrenschmidt  * Remaining API functions
6099d1e2492SBenjamin Herrenschmidt  */
6109d1e2492SBenjamin Herrenschmidt 
61195f72d1eSYinghai Lu /* You must call memblock_analyze() before this. */
6122898cc4cSBenjamin Herrenschmidt phys_addr_t __init memblock_phys_mem_size(void)
61395f72d1eSYinghai Lu {
6144734b594SBenjamin Herrenschmidt 	return memblock.memory_size;
61595f72d1eSYinghai Lu }
61695f72d1eSYinghai Lu 
61710d06439SYinghai Lu phys_addr_t __init_memblock memblock_end_of_DRAM(void)
61895f72d1eSYinghai Lu {
61995f72d1eSYinghai Lu 	int idx = memblock.memory.cnt - 1;
62095f72d1eSYinghai Lu 
621e3239ff9SBenjamin Herrenschmidt 	return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
62295f72d1eSYinghai Lu }
62395f72d1eSYinghai Lu 
62495f72d1eSYinghai Lu /* You must call memblock_analyze() after this. */
6252898cc4cSBenjamin Herrenschmidt void __init memblock_enforce_memory_limit(phys_addr_t memory_limit)
62695f72d1eSYinghai Lu {
62795f72d1eSYinghai Lu 	unsigned long i;
6282898cc4cSBenjamin Herrenschmidt 	phys_addr_t limit;
629e3239ff9SBenjamin Herrenschmidt 	struct memblock_region *p;
63095f72d1eSYinghai Lu 
63195f72d1eSYinghai Lu 	if (!memory_limit)
63295f72d1eSYinghai Lu 		return;
63395f72d1eSYinghai Lu 
63495f72d1eSYinghai Lu 	/* Truncate the memblock regions to satisfy the memory limit. */
63595f72d1eSYinghai Lu 	limit = memory_limit;
63695f72d1eSYinghai Lu 	for (i = 0; i < memblock.memory.cnt; i++) {
637e3239ff9SBenjamin Herrenschmidt 		if (limit > memblock.memory.regions[i].size) {
638e3239ff9SBenjamin Herrenschmidt 			limit -= memblock.memory.regions[i].size;
63995f72d1eSYinghai Lu 			continue;
64095f72d1eSYinghai Lu 		}
64195f72d1eSYinghai Lu 
642e3239ff9SBenjamin Herrenschmidt 		memblock.memory.regions[i].size = limit;
64395f72d1eSYinghai Lu 		memblock.memory.cnt = i + 1;
64495f72d1eSYinghai Lu 		break;
64595f72d1eSYinghai Lu 	}
64695f72d1eSYinghai Lu 
64795f72d1eSYinghai Lu 	memory_limit = memblock_end_of_DRAM();
64895f72d1eSYinghai Lu 
64995f72d1eSYinghai Lu 	/* And truncate any reserves above the limit also. */
65095f72d1eSYinghai Lu 	for (i = 0; i < memblock.reserved.cnt; i++) {
651e3239ff9SBenjamin Herrenschmidt 		p = &memblock.reserved.regions[i];
65295f72d1eSYinghai Lu 
65395f72d1eSYinghai Lu 		if (p->base > memory_limit)
65495f72d1eSYinghai Lu 			p->size = 0;
65595f72d1eSYinghai Lu 		else if ((p->base + p->size) > memory_limit)
65695f72d1eSYinghai Lu 			p->size = memory_limit - p->base;
65795f72d1eSYinghai Lu 
65895f72d1eSYinghai Lu 		if (p->size == 0) {
65995f72d1eSYinghai Lu 			memblock_remove_region(&memblock.reserved, i);
66095f72d1eSYinghai Lu 			i--;
66195f72d1eSYinghai Lu 		}
66295f72d1eSYinghai Lu 	}
66395f72d1eSYinghai Lu }
66495f72d1eSYinghai Lu 
665cd79481dSYinghai Lu static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
66672d4b0b4SBenjamin Herrenschmidt {
66772d4b0b4SBenjamin Herrenschmidt 	unsigned int left = 0, right = type->cnt;
66872d4b0b4SBenjamin Herrenschmidt 
66972d4b0b4SBenjamin Herrenschmidt 	do {
67072d4b0b4SBenjamin Herrenschmidt 		unsigned int mid = (right + left) / 2;
67172d4b0b4SBenjamin Herrenschmidt 
67272d4b0b4SBenjamin Herrenschmidt 		if (addr < type->regions[mid].base)
67372d4b0b4SBenjamin Herrenschmidt 			right = mid;
67472d4b0b4SBenjamin Herrenschmidt 		else if (addr >= (type->regions[mid].base +
67572d4b0b4SBenjamin Herrenschmidt 				  type->regions[mid].size))
67672d4b0b4SBenjamin Herrenschmidt 			left = mid + 1;
67772d4b0b4SBenjamin Herrenschmidt 		else
67872d4b0b4SBenjamin Herrenschmidt 			return mid;
67972d4b0b4SBenjamin Herrenschmidt 	} while (left < right);
68072d4b0b4SBenjamin Herrenschmidt 	return -1;
68172d4b0b4SBenjamin Herrenschmidt }
68272d4b0b4SBenjamin Herrenschmidt 
6832898cc4cSBenjamin Herrenschmidt int __init memblock_is_reserved(phys_addr_t addr)
68495f72d1eSYinghai Lu {
68572d4b0b4SBenjamin Herrenschmidt 	return memblock_search(&memblock.reserved, addr) != -1;
68695f72d1eSYinghai Lu }
68772d4b0b4SBenjamin Herrenschmidt 
6883661ca66SYinghai Lu int __init_memblock memblock_is_memory(phys_addr_t addr)
68972d4b0b4SBenjamin Herrenschmidt {
69072d4b0b4SBenjamin Herrenschmidt 	return memblock_search(&memblock.memory, addr) != -1;
69172d4b0b4SBenjamin Herrenschmidt }
69272d4b0b4SBenjamin Herrenschmidt 
6933661ca66SYinghai Lu int __init_memblock memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
69472d4b0b4SBenjamin Herrenschmidt {
695abb65272STomi Valkeinen 	int idx = memblock_search(&memblock.memory, base);
69672d4b0b4SBenjamin Herrenschmidt 
69772d4b0b4SBenjamin Herrenschmidt 	if (idx == -1)
69895f72d1eSYinghai Lu 		return 0;
699abb65272STomi Valkeinen 	return memblock.memory.regions[idx].base <= base &&
700abb65272STomi Valkeinen 		(memblock.memory.regions[idx].base +
701abb65272STomi Valkeinen 		 memblock.memory.regions[idx].size) >= (base + size);
70295f72d1eSYinghai Lu }
70395f72d1eSYinghai Lu 
70410d06439SYinghai Lu int __init_memblock memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
70595f72d1eSYinghai Lu {
706f1c2c19cSBenjamin Herrenschmidt 	return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
70795f72d1eSYinghai Lu }
70895f72d1eSYinghai Lu 
709e63075a3SBenjamin Herrenschmidt 
7103661ca66SYinghai Lu void __init_memblock memblock_set_current_limit(phys_addr_t limit)
711e63075a3SBenjamin Herrenschmidt {
712e63075a3SBenjamin Herrenschmidt 	memblock.current_limit = limit;
713e63075a3SBenjamin Herrenschmidt }
714e63075a3SBenjamin Herrenschmidt 
71510d06439SYinghai Lu static void __init_memblock memblock_dump(struct memblock_type *region, char *name)
7166ed311b2SBenjamin Herrenschmidt {
7176ed311b2SBenjamin Herrenschmidt 	unsigned long long base, size;
7186ed311b2SBenjamin Herrenschmidt 	int i;
7196ed311b2SBenjamin Herrenschmidt 
7206ed311b2SBenjamin Herrenschmidt 	pr_info(" %s.cnt  = 0x%lx\n", name, region->cnt);
7216ed311b2SBenjamin Herrenschmidt 
7226ed311b2SBenjamin Herrenschmidt 	for (i = 0; i < region->cnt; i++) {
7236ed311b2SBenjamin Herrenschmidt 		base = region->regions[i].base;
7246ed311b2SBenjamin Herrenschmidt 		size = region->regions[i].size;
7256ed311b2SBenjamin Herrenschmidt 
726ea9e4376SYinghai Lu 		pr_info(" %s[%#x]\t[%#016llx-%#016llx], %#llx bytes\n",
7276ed311b2SBenjamin Herrenschmidt 		    name, i, base, base + size - 1, size);
7286ed311b2SBenjamin Herrenschmidt 	}
7296ed311b2SBenjamin Herrenschmidt }
7306ed311b2SBenjamin Herrenschmidt 
73110d06439SYinghai Lu void __init_memblock memblock_dump_all(void)
7326ed311b2SBenjamin Herrenschmidt {
7336ed311b2SBenjamin Herrenschmidt 	if (!memblock_debug)
7346ed311b2SBenjamin Herrenschmidt 		return;
7356ed311b2SBenjamin Herrenschmidt 
7366ed311b2SBenjamin Herrenschmidt 	pr_info("MEMBLOCK configuration:\n");
7376ed311b2SBenjamin Herrenschmidt 	pr_info(" memory size = 0x%llx\n", (unsigned long long)memblock.memory_size);
7386ed311b2SBenjamin Herrenschmidt 
7396ed311b2SBenjamin Herrenschmidt 	memblock_dump(&memblock.memory, "memory");
7406ed311b2SBenjamin Herrenschmidt 	memblock_dump(&memblock.reserved, "reserved");
7416ed311b2SBenjamin Herrenschmidt }
7426ed311b2SBenjamin Herrenschmidt 
7436ed311b2SBenjamin Herrenschmidt void __init memblock_analyze(void)
7446ed311b2SBenjamin Herrenschmidt {
7456ed311b2SBenjamin Herrenschmidt 	int i;
7466ed311b2SBenjamin Herrenschmidt 
7476ed311b2SBenjamin Herrenschmidt 	/* Check marker in the unused last array entry */
7486ed311b2SBenjamin Herrenschmidt 	WARN_ON(memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS].base
7496ed311b2SBenjamin Herrenschmidt 		!= (phys_addr_t)RED_INACTIVE);
7506ed311b2SBenjamin Herrenschmidt 	WARN_ON(memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS].base
7516ed311b2SBenjamin Herrenschmidt 		!= (phys_addr_t)RED_INACTIVE);
7526ed311b2SBenjamin Herrenschmidt 
7536ed311b2SBenjamin Herrenschmidt 	memblock.memory_size = 0;
7546ed311b2SBenjamin Herrenschmidt 
7556ed311b2SBenjamin Herrenschmidt 	for (i = 0; i < memblock.memory.cnt; i++)
7566ed311b2SBenjamin Herrenschmidt 		memblock.memory_size += memblock.memory.regions[i].size;
757142b45a7SBenjamin Herrenschmidt 
758142b45a7SBenjamin Herrenschmidt 	/* We allow resizing from there */
759142b45a7SBenjamin Herrenschmidt 	memblock_can_resize = 1;
7606ed311b2SBenjamin Herrenschmidt }
7616ed311b2SBenjamin Herrenschmidt 
7627590abe8SBenjamin Herrenschmidt void __init memblock_init(void)
7637590abe8SBenjamin Herrenschmidt {
764236260b9SJeremy Fitzhardinge 	static int init_done __initdata = 0;
765236260b9SJeremy Fitzhardinge 
766236260b9SJeremy Fitzhardinge 	if (init_done)
767236260b9SJeremy Fitzhardinge 		return;
768236260b9SJeremy Fitzhardinge 	init_done = 1;
769236260b9SJeremy Fitzhardinge 
7707590abe8SBenjamin Herrenschmidt 	/* Hookup the initial arrays */
7717590abe8SBenjamin Herrenschmidt 	memblock.memory.regions	= memblock_memory_init_regions;
7727590abe8SBenjamin Herrenschmidt 	memblock.memory.max		= INIT_MEMBLOCK_REGIONS;
7737590abe8SBenjamin Herrenschmidt 	memblock.reserved.regions	= memblock_reserved_init_regions;
7747590abe8SBenjamin Herrenschmidt 	memblock.reserved.max	= INIT_MEMBLOCK_REGIONS;
7757590abe8SBenjamin Herrenschmidt 
7767590abe8SBenjamin Herrenschmidt 	/* Write a marker in the unused last array entry */
7777590abe8SBenjamin Herrenschmidt 	memblock.memory.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
7787590abe8SBenjamin Herrenschmidt 	memblock.reserved.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
7797590abe8SBenjamin Herrenschmidt 
7807590abe8SBenjamin Herrenschmidt 	/* Create a dummy zero size MEMBLOCK which will get coalesced away later.
7817590abe8SBenjamin Herrenschmidt 	 * This simplifies the memblock_add() code below...
7827590abe8SBenjamin Herrenschmidt 	 */
7837590abe8SBenjamin Herrenschmidt 	memblock.memory.regions[0].base = 0;
7847590abe8SBenjamin Herrenschmidt 	memblock.memory.regions[0].size = 0;
7857590abe8SBenjamin Herrenschmidt 	memblock.memory.cnt = 1;
7867590abe8SBenjamin Herrenschmidt 
7877590abe8SBenjamin Herrenschmidt 	/* Ditto. */
7887590abe8SBenjamin Herrenschmidt 	memblock.reserved.regions[0].base = 0;
7897590abe8SBenjamin Herrenschmidt 	memblock.reserved.regions[0].size = 0;
7907590abe8SBenjamin Herrenschmidt 	memblock.reserved.cnt = 1;
7917590abe8SBenjamin Herrenschmidt 
7927590abe8SBenjamin Herrenschmidt 	memblock.current_limit = MEMBLOCK_ALLOC_ANYWHERE;
7937590abe8SBenjamin Herrenschmidt }
7947590abe8SBenjamin Herrenschmidt 
7956ed311b2SBenjamin Herrenschmidt static int __init early_memblock(char *p)
7966ed311b2SBenjamin Herrenschmidt {
7976ed311b2SBenjamin Herrenschmidt 	if (p && strstr(p, "debug"))
7986ed311b2SBenjamin Herrenschmidt 		memblock_debug = 1;
7996ed311b2SBenjamin Herrenschmidt 	return 0;
8006ed311b2SBenjamin Herrenschmidt }
8016ed311b2SBenjamin Herrenschmidt early_param("memblock", early_memblock);
8026ed311b2SBenjamin Herrenschmidt 
80310d06439SYinghai Lu #if defined(CONFIG_DEBUG_FS) && !defined(ARCH_DISCARD_MEMBLOCK)
8046d03b885SBenjamin Herrenschmidt 
8056d03b885SBenjamin Herrenschmidt static int memblock_debug_show(struct seq_file *m, void *private)
8066d03b885SBenjamin Herrenschmidt {
8076d03b885SBenjamin Herrenschmidt 	struct memblock_type *type = m->private;
8086d03b885SBenjamin Herrenschmidt 	struct memblock_region *reg;
8096d03b885SBenjamin Herrenschmidt 	int i;
8106d03b885SBenjamin Herrenschmidt 
8116d03b885SBenjamin Herrenschmidt 	for (i = 0; i < type->cnt; i++) {
8126d03b885SBenjamin Herrenschmidt 		reg = &type->regions[i];
8136d03b885SBenjamin Herrenschmidt 		seq_printf(m, "%4d: ", i);
8146d03b885SBenjamin Herrenschmidt 		if (sizeof(phys_addr_t) == 4)
8156d03b885SBenjamin Herrenschmidt 			seq_printf(m, "0x%08lx..0x%08lx\n",
8166d03b885SBenjamin Herrenschmidt 				   (unsigned long)reg->base,
8176d03b885SBenjamin Herrenschmidt 				   (unsigned long)(reg->base + reg->size - 1));
8186d03b885SBenjamin Herrenschmidt 		else
8196d03b885SBenjamin Herrenschmidt 			seq_printf(m, "0x%016llx..0x%016llx\n",
8206d03b885SBenjamin Herrenschmidt 				   (unsigned long long)reg->base,
8216d03b885SBenjamin Herrenschmidt 				   (unsigned long long)(reg->base + reg->size - 1));
8226d03b885SBenjamin Herrenschmidt 
8236d03b885SBenjamin Herrenschmidt 	}
8246d03b885SBenjamin Herrenschmidt 	return 0;
8256d03b885SBenjamin Herrenschmidt }
8266d03b885SBenjamin Herrenschmidt 
8276d03b885SBenjamin Herrenschmidt static int memblock_debug_open(struct inode *inode, struct file *file)
8286d03b885SBenjamin Herrenschmidt {
8296d03b885SBenjamin Herrenschmidt 	return single_open(file, memblock_debug_show, inode->i_private);
8306d03b885SBenjamin Herrenschmidt }
8316d03b885SBenjamin Herrenschmidt 
8326d03b885SBenjamin Herrenschmidt static const struct file_operations memblock_debug_fops = {
8336d03b885SBenjamin Herrenschmidt 	.open = memblock_debug_open,
8346d03b885SBenjamin Herrenschmidt 	.read = seq_read,
8356d03b885SBenjamin Herrenschmidt 	.llseek = seq_lseek,
8366d03b885SBenjamin Herrenschmidt 	.release = single_release,
8376d03b885SBenjamin Herrenschmidt };
8386d03b885SBenjamin Herrenschmidt 
8396d03b885SBenjamin Herrenschmidt static int __init memblock_init_debugfs(void)
8406d03b885SBenjamin Herrenschmidt {
8416d03b885SBenjamin Herrenschmidt 	struct dentry *root = debugfs_create_dir("memblock", NULL);
8426d03b885SBenjamin Herrenschmidt 	if (!root)
8436d03b885SBenjamin Herrenschmidt 		return -ENXIO;
8446d03b885SBenjamin Herrenschmidt 	debugfs_create_file("memory", S_IRUGO, root, &memblock.memory, &memblock_debug_fops);
8456d03b885SBenjamin Herrenschmidt 	debugfs_create_file("reserved", S_IRUGO, root, &memblock.reserved, &memblock_debug_fops);
8466d03b885SBenjamin Herrenschmidt 
8476d03b885SBenjamin Herrenschmidt 	return 0;
8486d03b885SBenjamin Herrenschmidt }
8496d03b885SBenjamin Herrenschmidt __initcall(memblock_init_debugfs);
8506d03b885SBenjamin Herrenschmidt 
8516d03b885SBenjamin Herrenschmidt #endif /* CONFIG_DEBUG_FS */
852