Linux Audio

Check our new training course

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