memblock: Add array resizing support
[linux-3.10.git] / mm / memblock.c
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/memblock.h>
19
20 struct memblock memblock;
21
22 static int memblock_debug, memblock_can_resize;
23 static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS + 1];
24 static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS + 1];
25
26 #define MEMBLOCK_ERROR  (~(phys_addr_t)0)
27
28 /* inline so we don't get a warning when pr_debug is compiled out */
29 static inline const char *memblock_type_name(struct memblock_type *type)
30 {
31         if (type == &memblock.memory)
32                 return "memory";
33         else if (type == &memblock.reserved)
34                 return "reserved";
35         else
36                 return "unknown";
37 }
38
39 /*
40  * Address comparison utilities
41  */
42
43 static phys_addr_t memblock_align_down(phys_addr_t addr, phys_addr_t size)
44 {
45         return addr & ~(size - 1);
46 }
47
48 static phys_addr_t memblock_align_up(phys_addr_t addr, phys_addr_t size)
49 {
50         return (addr + (size - 1)) & ~(size - 1);
51 }
52
53 static unsigned long memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
54                                        phys_addr_t base2, phys_addr_t size2)
55 {
56         return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
57 }
58
59 static long memblock_addrs_adjacent(phys_addr_t base1, phys_addr_t size1,
60                                phys_addr_t base2, phys_addr_t size2)
61 {
62         if (base2 == base1 + size1)
63                 return 1;
64         else if (base1 == base2 + size2)
65                 return -1;
66
67         return 0;
68 }
69
70 static long memblock_regions_adjacent(struct memblock_type *type,
71                                  unsigned long r1, unsigned long r2)
72 {
73         phys_addr_t base1 = type->regions[r1].base;
74         phys_addr_t size1 = type->regions[r1].size;
75         phys_addr_t base2 = type->regions[r2].base;
76         phys_addr_t size2 = type->regions[r2].size;
77
78         return memblock_addrs_adjacent(base1, size1, base2, size2);
79 }
80
81 long memblock_overlaps_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
82 {
83         unsigned long i;
84
85         for (i = 0; i < type->cnt; i++) {
86                 phys_addr_t rgnbase = type->regions[i].base;
87                 phys_addr_t rgnsize = type->regions[i].size;
88                 if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
89                         break;
90         }
91
92         return (i < type->cnt) ? i : -1;
93 }
94
95 /*
96  * Find, allocate, deallocate or reserve unreserved regions. All allocations
97  * are top-down.
98  */
99
100 static phys_addr_t __init memblock_find_region(phys_addr_t start, phys_addr_t end,
101                                           phys_addr_t size, phys_addr_t align)
102 {
103         phys_addr_t base, res_base;
104         long j;
105
106         base = memblock_align_down((end - size), align);
107         while (start <= base) {
108                 j = memblock_overlaps_region(&memblock.reserved, base, size);
109                 if (j < 0)
110                         return base;
111                 res_base = memblock.reserved.regions[j].base;
112                 if (res_base < size)
113                         break;
114                 base = memblock_align_down(res_base - size, align);
115         }
116
117         return MEMBLOCK_ERROR;
118 }
119
120 static phys_addr_t __init memblock_find_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
121 {
122         long i;
123         phys_addr_t base = 0;
124         phys_addr_t res_base;
125
126         BUG_ON(0 == size);
127
128         size = memblock_align_up(size, align);
129
130         /* Pump up max_addr */
131         if (max_addr == MEMBLOCK_ALLOC_ACCESSIBLE)
132                 max_addr = memblock.current_limit;
133
134         /* We do a top-down search, this tends to limit memory
135          * fragmentation by keeping early boot allocs near the
136          * top of memory
137          */
138         for (i = memblock.memory.cnt - 1; i >= 0; i--) {
139                 phys_addr_t memblockbase = memblock.memory.regions[i].base;
140                 phys_addr_t memblocksize = memblock.memory.regions[i].size;
141
142                 if (memblocksize < size)
143                         continue;
144                 base = min(memblockbase + memblocksize, max_addr);
145                 res_base = memblock_find_region(memblockbase, base, size, align);
146                 if (res_base != MEMBLOCK_ERROR)
147                         return res_base;
148         }
149         return MEMBLOCK_ERROR;
150 }
151
152 static void memblock_remove_region(struct memblock_type *type, unsigned long r)
153 {
154         unsigned long i;
155
156         for (i = r; i < type->cnt - 1; i++) {
157                 type->regions[i].base = type->regions[i + 1].base;
158                 type->regions[i].size = type->regions[i + 1].size;
159         }
160         type->cnt--;
161 }
162
163 /* Assumption: base addr of region 1 < base addr of region 2 */
164 static void memblock_coalesce_regions(struct memblock_type *type,
165                 unsigned long r1, unsigned long r2)
166 {
167         type->regions[r1].size += type->regions[r2].size;
168         memblock_remove_region(type, r2);
169 }
170
171 /* Defined below but needed now */
172 static long memblock_add_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size);
173
174 static int memblock_double_array(struct memblock_type *type)
175 {
176         struct memblock_region *new_array, *old_array;
177         phys_addr_t old_size, new_size, addr;
178         int use_slab = slab_is_available();
179
180         /* We don't allow resizing until we know about the reserved regions
181          * of memory that aren't suitable for allocation
182          */
183         if (!memblock_can_resize)
184                 return -1;
185
186         pr_debug("memblock: %s array full, doubling...", memblock_type_name(type));
187
188         /* Calculate new doubled size */
189         old_size = type->max * sizeof(struct memblock_region);
190         new_size = old_size << 1;
191
192         /* Try to find some space for it.
193          *
194          * WARNING: We assume that either slab_is_available() and we use it or
195          * we use MEMBLOCK for allocations. That means that this is unsafe to use
196          * when bootmem is currently active (unless bootmem itself is implemented
197          * on top of MEMBLOCK which isn't the case yet)
198          *
199          * This should however not be an issue for now, as we currently only
200          * call into MEMBLOCK while it's still active, or much later when slab is
201          * active for memory hotplug operations
202          */
203         if (use_slab) {
204                 new_array = kmalloc(new_size, GFP_KERNEL);
205                 addr = new_array == NULL ? MEMBLOCK_ERROR : __pa(new_array);
206         } else
207                 addr = memblock_find_base(new_size, sizeof(phys_addr_t), MEMBLOCK_ALLOC_ACCESSIBLE);
208         if (addr == MEMBLOCK_ERROR) {
209                 pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
210                        memblock_type_name(type), type->max, type->max * 2);
211                 return -1;
212         }
213         new_array = __va(addr);
214
215         /* Found space, we now need to move the array over before
216          * we add the reserved region since it may be our reserved
217          * array itself that is full.
218          */
219         memcpy(new_array, type->regions, old_size);
220         memset(new_array + type->max, 0, old_size);
221         old_array = type->regions;
222         type->regions = new_array;
223         type->max <<= 1;
224
225         /* If we use SLAB that's it, we are done */
226         if (use_slab)
227                 return 0;
228
229         /* Add the new reserved region now. Should not fail ! */
230         BUG_ON(memblock_add_region(&memblock.reserved, addr, new_size) < 0);
231
232         /* If the array wasn't our static init one, then free it. We only do
233          * that before SLAB is available as later on, we don't know whether
234          * to use kfree or free_bootmem_pages(). Shouldn't be a big deal
235          * anyways
236          */
237         if (old_array != memblock_memory_init_regions &&
238             old_array != memblock_reserved_init_regions)
239                 memblock_free(__pa(old_array), old_size);
240
241         return 0;
242 }
243
244 static long memblock_add_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
245 {
246         unsigned long coalesced = 0;
247         long adjacent, i;
248
249         if ((type->cnt == 1) && (type->regions[0].size == 0)) {
250                 type->regions[0].base = base;
251                 type->regions[0].size = size;
252                 return 0;
253         }
254
255         /* First try and coalesce this MEMBLOCK with another. */
256         for (i = 0; i < type->cnt; i++) {
257                 phys_addr_t rgnbase = type->regions[i].base;
258                 phys_addr_t rgnsize = type->regions[i].size;
259
260                 if ((rgnbase == base) && (rgnsize == size))
261                         /* Already have this region, so we're done */
262                         return 0;
263
264                 adjacent = memblock_addrs_adjacent(base, size, rgnbase, rgnsize);
265                 if (adjacent > 0) {
266                         type->regions[i].base -= size;
267                         type->regions[i].size += size;
268                         coalesced++;
269                         break;
270                 } else if (adjacent < 0) {
271                         type->regions[i].size += size;
272                         coalesced++;
273                         break;
274                 }
275         }
276
277         if ((i < type->cnt - 1) && memblock_regions_adjacent(type, i, i+1)) {
278                 memblock_coalesce_regions(type, i, i+1);
279                 coalesced++;
280         }
281
282         if (coalesced)
283                 return coalesced;
284
285         /* If we are out of space, we fail. It's too late to resize the array
286          * but then this shouldn't have happened in the first place.
287          */
288         if (WARN_ON(type->cnt >= type->max))
289                 return -1;
290
291         /* Couldn't coalesce the MEMBLOCK, so add it to the sorted table. */
292         for (i = type->cnt - 1; i >= 0; i--) {
293                 if (base < type->regions[i].base) {
294                         type->regions[i+1].base = type->regions[i].base;
295                         type->regions[i+1].size = type->regions[i].size;
296                 } else {
297                         type->regions[i+1].base = base;
298                         type->regions[i+1].size = size;
299                         break;
300                 }
301         }
302
303         if (base < type->regions[0].base) {
304                 type->regions[0].base = base;
305                 type->regions[0].size = size;
306         }
307         type->cnt++;
308
309         /* The array is full ? Try to resize it. If that fails, we undo
310          * our allocation and return an error
311          */
312         if (type->cnt == type->max && memblock_double_array(type)) {
313                 type->cnt--;
314                 return -1;
315         }
316
317         return 0;
318 }
319
320 long memblock_add(phys_addr_t base, phys_addr_t size)
321 {
322         return memblock_add_region(&memblock.memory, base, size);
323
324 }
325
326 static long __memblock_remove(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
327 {
328         phys_addr_t rgnbegin, rgnend;
329         phys_addr_t end = base + size;
330         int i;
331
332         rgnbegin = rgnend = 0; /* supress gcc warnings */
333
334         /* Find the region where (base, size) belongs to */
335         for (i=0; i < type->cnt; i++) {
336                 rgnbegin = type->regions[i].base;
337                 rgnend = rgnbegin + type->regions[i].size;
338
339                 if ((rgnbegin <= base) && (end <= rgnend))
340                         break;
341         }
342
343         /* Didn't find the region */
344         if (i == type->cnt)
345                 return -1;
346
347         /* Check to see if we are removing entire region */
348         if ((rgnbegin == base) && (rgnend == end)) {
349                 memblock_remove_region(type, i);
350                 return 0;
351         }
352
353         /* Check to see if region is matching at the front */
354         if (rgnbegin == base) {
355                 type->regions[i].base = end;
356                 type->regions[i].size -= size;
357                 return 0;
358         }
359
360         /* Check to see if the region is matching at the end */
361         if (rgnend == end) {
362                 type->regions[i].size -= size;
363                 return 0;
364         }
365
366         /*
367          * We need to split the entry -  adjust the current one to the
368          * beginging of the hole and add the region after hole.
369          */
370         type->regions[i].size = base - type->regions[i].base;
371         return memblock_add_region(type, end, rgnend - end);
372 }
373
374 long memblock_remove(phys_addr_t base, phys_addr_t size)
375 {
376         return __memblock_remove(&memblock.memory, base, size);
377 }
378
379 long __init memblock_free(phys_addr_t base, phys_addr_t size)
380 {
381         return __memblock_remove(&memblock.reserved, base, size);
382 }
383
384 long __init memblock_reserve(phys_addr_t base, phys_addr_t size)
385 {
386         struct memblock_type *_rgn = &memblock.reserved;
387
388         BUG_ON(0 == size);
389
390         return memblock_add_region(_rgn, base, size);
391 }
392
393 phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
394 {
395         phys_addr_t found;
396
397         /* We align the size to limit fragmentation. Without this, a lot of
398          * small allocs quickly eat up the whole reserve array on sparc
399          */
400         size = memblock_align_up(size, align);
401
402         found = memblock_find_base(size, align, max_addr);
403         if (found != MEMBLOCK_ERROR &&
404             memblock_add_region(&memblock.reserved, found, size) >= 0)
405                 return found;
406
407         return 0;
408 }
409
410 phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
411 {
412         phys_addr_t alloc;
413
414         alloc = __memblock_alloc_base(size, align, max_addr);
415
416         if (alloc == 0)
417                 panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
418                       (unsigned long long) size, (unsigned long long) max_addr);
419
420         return alloc;
421 }
422
423 phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
424 {
425         return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
426 }
427
428
429 /*
430  * Additional node-local allocators. Search for node memory is bottom up
431  * and walks memblock regions within that node bottom-up as well, but allocation
432  * within an memblock region is top-down.
433  */
434
435 phys_addr_t __weak __init memblock_nid_range(phys_addr_t start, phys_addr_t end, int *nid)
436 {
437         *nid = 0;
438
439         return end;
440 }
441
442 static phys_addr_t __init memblock_alloc_nid_region(struct memblock_region *mp,
443                                                phys_addr_t size,
444                                                phys_addr_t align, int nid)
445 {
446         phys_addr_t start, end;
447
448         start = mp->base;
449         end = start + mp->size;
450
451         start = memblock_align_up(start, align);
452         while (start < end) {
453                 phys_addr_t this_end;
454                 int this_nid;
455
456                 this_end = memblock_nid_range(start, end, &this_nid);
457                 if (this_nid == nid) {
458                         phys_addr_t ret = memblock_find_region(start, this_end, size, align);
459                         if (ret != MEMBLOCK_ERROR &&
460                             memblock_add_region(&memblock.reserved, ret, size) >= 0)
461                                 return ret;
462                 }
463                 start = this_end;
464         }
465
466         return MEMBLOCK_ERROR;
467 }
468
469 phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
470 {
471         struct memblock_type *mem = &memblock.memory;
472         int i;
473
474         BUG_ON(0 == size);
475
476         /* We align the size to limit fragmentation. Without this, a lot of
477          * small allocs quickly eat up the whole reserve array on sparc
478          */
479         size = memblock_align_up(size, align);
480
481         /* We do a bottom-up search for a region with the right
482          * nid since that's easier considering how memblock_nid_range()
483          * works
484          */
485         for (i = 0; i < mem->cnt; i++) {
486                 phys_addr_t ret = memblock_alloc_nid_region(&mem->regions[i],
487                                                size, align, nid);
488                 if (ret != MEMBLOCK_ERROR)
489                         return ret;
490         }
491
492         return memblock_alloc(size, align);
493 }
494
495 /* You must call memblock_analyze() before this. */
496 phys_addr_t __init memblock_phys_mem_size(void)
497 {
498         return memblock.memory_size;
499 }
500
501 phys_addr_t memblock_end_of_DRAM(void)
502 {
503         int idx = memblock.memory.cnt - 1;
504
505         return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
506 }
507
508 /* You must call memblock_analyze() after this. */
509 void __init memblock_enforce_memory_limit(phys_addr_t memory_limit)
510 {
511         unsigned long i;
512         phys_addr_t limit;
513         struct memblock_region *p;
514
515         if (!memory_limit)
516                 return;
517
518         /* Truncate the memblock regions to satisfy the memory limit. */
519         limit = memory_limit;
520         for (i = 0; i < memblock.memory.cnt; i++) {
521                 if (limit > memblock.memory.regions[i].size) {
522                         limit -= memblock.memory.regions[i].size;
523                         continue;
524                 }
525
526                 memblock.memory.regions[i].size = limit;
527                 memblock.memory.cnt = i + 1;
528                 break;
529         }
530
531         memory_limit = memblock_end_of_DRAM();
532
533         /* And truncate any reserves above the limit also. */
534         for (i = 0; i < memblock.reserved.cnt; i++) {
535                 p = &memblock.reserved.regions[i];
536
537                 if (p->base > memory_limit)
538                         p->size = 0;
539                 else if ((p->base + p->size) > memory_limit)
540                         p->size = memory_limit - p->base;
541
542                 if (p->size == 0) {
543                         memblock_remove_region(&memblock.reserved, i);
544                         i--;
545                 }
546         }
547 }
548
549 static int memblock_search(struct memblock_type *type, phys_addr_t addr)
550 {
551         unsigned int left = 0, right = type->cnt;
552
553         do {
554                 unsigned int mid = (right + left) / 2;
555
556                 if (addr < type->regions[mid].base)
557                         right = mid;
558                 else if (addr >= (type->regions[mid].base +
559                                   type->regions[mid].size))
560                         left = mid + 1;
561                 else
562                         return mid;
563         } while (left < right);
564         return -1;
565 }
566
567 int __init memblock_is_reserved(phys_addr_t addr)
568 {
569         return memblock_search(&memblock.reserved, addr) != -1;
570 }
571
572 int memblock_is_memory(phys_addr_t addr)
573 {
574         return memblock_search(&memblock.memory, addr) != -1;
575 }
576
577 int memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
578 {
579         int idx = memblock_search(&memblock.reserved, base);
580
581         if (idx == -1)
582                 return 0;
583         return memblock.reserved.regions[idx].base <= base &&
584                 (memblock.reserved.regions[idx].base +
585                  memblock.reserved.regions[idx].size) >= (base + size);
586 }
587
588 int memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
589 {
590         return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
591 }
592
593
594 void __init memblock_set_current_limit(phys_addr_t limit)
595 {
596         memblock.current_limit = limit;
597 }
598
599 static void memblock_dump(struct memblock_type *region, char *name)
600 {
601         unsigned long long base, size;
602         int i;
603
604         pr_info(" %s.cnt  = 0x%lx\n", name, region->cnt);
605
606         for (i = 0; i < region->cnt; i++) {
607                 base = region->regions[i].base;
608                 size = region->regions[i].size;
609
610                 pr_info(" %s[0x%x]\t0x%016llx - 0x%016llx, 0x%llx bytes\n",
611                     name, i, base, base + size - 1, size);
612         }
613 }
614
615 void memblock_dump_all(void)
616 {
617         if (!memblock_debug)
618                 return;
619
620         pr_info("MEMBLOCK configuration:\n");
621         pr_info(" memory size = 0x%llx\n", (unsigned long long)memblock.memory_size);
622
623         memblock_dump(&memblock.memory, "memory");
624         memblock_dump(&memblock.reserved, "reserved");
625 }
626
627 void __init memblock_analyze(void)
628 {
629         int i;
630
631         /* Check marker in the unused last array entry */
632         WARN_ON(memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS].base
633                 != (phys_addr_t)RED_INACTIVE);
634         WARN_ON(memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS].base
635                 != (phys_addr_t)RED_INACTIVE);
636
637         memblock.memory_size = 0;
638
639         for (i = 0; i < memblock.memory.cnt; i++)
640                 memblock.memory_size += memblock.memory.regions[i].size;
641
642         /* We allow resizing from there */
643         memblock_can_resize = 1;
644 }
645
646 void __init memblock_init(void)
647 {
648         /* Hookup the initial arrays */
649         memblock.memory.regions = memblock_memory_init_regions;
650         memblock.memory.max             = INIT_MEMBLOCK_REGIONS;
651         memblock.reserved.regions       = memblock_reserved_init_regions;
652         memblock.reserved.max   = INIT_MEMBLOCK_REGIONS;
653
654         /* Write a marker in the unused last array entry */
655         memblock.memory.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
656         memblock.reserved.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
657
658         /* Create a dummy zero size MEMBLOCK which will get coalesced away later.
659          * This simplifies the memblock_add() code below...
660          */
661         memblock.memory.regions[0].base = 0;
662         memblock.memory.regions[0].size = 0;
663         memblock.memory.cnt = 1;
664
665         /* Ditto. */
666         memblock.reserved.regions[0].base = 0;
667         memblock.reserved.regions[0].size = 0;
668         memblock.reserved.cnt = 1;
669
670         memblock.current_limit = MEMBLOCK_ALLOC_ANYWHERE;
671 }
672
673 static int __init early_memblock(char *p)
674 {
675         if (p && strstr(p, "debug"))
676                 memblock_debug = 1;
677         return 0;
678 }
679 early_param("memblock", early_memblock);
680