memblock: Add debug markers at the end of the array
[linux-2.6.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/init.h>
15 #include <linux/bitops.h>
16 #include <linux/poison.h>
17 #include <linux/memblock.h>
18
19 struct memblock memblock;
20
21 static int memblock_debug;
22 static struct memblock_region memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS + 1];
23 static struct memblock_region memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS + 1];
24
25 static int __init early_memblock(char *p)
26 {
27         if (p && strstr(p, "debug"))
28                 memblock_debug = 1;
29         return 0;
30 }
31 early_param("memblock", early_memblock);
32
33 static void memblock_dump(struct memblock_type *region, char *name)
34 {
35         unsigned long long base, size;
36         int i;
37
38         pr_info(" %s.cnt  = 0x%lx\n", name, region->cnt);
39
40         for (i = 0; i < region->cnt; i++) {
41                 base = region->regions[i].base;
42                 size = region->regions[i].size;
43
44                 pr_info(" %s[0x%x]\t0x%016llx - 0x%016llx, 0x%llx bytes\n",
45                     name, i, base, base + size - 1, size);
46         }
47 }
48
49 void memblock_dump_all(void)
50 {
51         if (!memblock_debug)
52                 return;
53
54         pr_info("MEMBLOCK configuration:\n");
55         pr_info(" memory size = 0x%llx\n", (unsigned long long)memblock.memory_size);
56
57         memblock_dump(&memblock.memory, "memory");
58         memblock_dump(&memblock.reserved, "reserved");
59 }
60
61 static unsigned long memblock_addrs_overlap(phys_addr_t base1, phys_addr_t size1,
62                                        phys_addr_t base2, phys_addr_t size2)
63 {
64         return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
65 }
66
67 static long memblock_addrs_adjacent(phys_addr_t base1, phys_addr_t size1,
68                                phys_addr_t base2, phys_addr_t size2)
69 {
70         if (base2 == base1 + size1)
71                 return 1;
72         else if (base1 == base2 + size2)
73                 return -1;
74
75         return 0;
76 }
77
78 static long memblock_regions_adjacent(struct memblock_type *type,
79                                  unsigned long r1, unsigned long r2)
80 {
81         phys_addr_t base1 = type->regions[r1].base;
82         phys_addr_t size1 = type->regions[r1].size;
83         phys_addr_t base2 = type->regions[r2].base;
84         phys_addr_t size2 = type->regions[r2].size;
85
86         return memblock_addrs_adjacent(base1, size1, base2, size2);
87 }
88
89 static void memblock_remove_region(struct memblock_type *type, unsigned long r)
90 {
91         unsigned long i;
92
93         for (i = r; i < type->cnt - 1; i++) {
94                 type->regions[i].base = type->regions[i + 1].base;
95                 type->regions[i].size = type->regions[i + 1].size;
96         }
97         type->cnt--;
98 }
99
100 /* Assumption: base addr of region 1 < base addr of region 2 */
101 static void memblock_coalesce_regions(struct memblock_type *type,
102                 unsigned long r1, unsigned long r2)
103 {
104         type->regions[r1].size += type->regions[r2].size;
105         memblock_remove_region(type, r2);
106 }
107
108 void __init memblock_init(void)
109 {
110         /* Hookup the initial arrays */
111         memblock.memory.regions = memblock_memory_init_regions;
112         memblock.memory.max             = INIT_MEMBLOCK_REGIONS;
113         memblock.reserved.regions       = memblock_reserved_init_regions;
114         memblock.reserved.max   = INIT_MEMBLOCK_REGIONS;
115
116         /* Write a marker in the unused last array entry */
117         memblock.memory.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
118         memblock.reserved.regions[INIT_MEMBLOCK_REGIONS].base = (phys_addr_t)RED_INACTIVE;
119
120         /* Create a dummy zero size MEMBLOCK which will get coalesced away later.
121          * This simplifies the memblock_add() code below...
122          */
123         memblock.memory.regions[0].base = 0;
124         memblock.memory.regions[0].size = 0;
125         memblock.memory.cnt = 1;
126
127         /* Ditto. */
128         memblock.reserved.regions[0].base = 0;
129         memblock.reserved.regions[0].size = 0;
130         memblock.reserved.cnt = 1;
131
132         memblock.current_limit = MEMBLOCK_ALLOC_ANYWHERE;
133 }
134
135 void __init memblock_analyze(void)
136 {
137         int i;
138
139         /* Check marker in the unused last array entry */
140         WARN_ON(memblock_memory_init_regions[INIT_MEMBLOCK_REGIONS].base
141                 != (phys_addr_t)RED_INACTIVE);
142         WARN_ON(memblock_reserved_init_regions[INIT_MEMBLOCK_REGIONS].base
143                 != (phys_addr_t)RED_INACTIVE);
144
145         memblock.memory_size = 0;
146
147         for (i = 0; i < memblock.memory.cnt; i++)
148                 memblock.memory_size += memblock.memory.regions[i].size;
149 }
150
151 static long memblock_add_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
152 {
153         unsigned long coalesced = 0;
154         long adjacent, i;
155
156         if ((type->cnt == 1) && (type->regions[0].size == 0)) {
157                 type->regions[0].base = base;
158                 type->regions[0].size = size;
159                 return 0;
160         }
161
162         /* First try and coalesce this MEMBLOCK with another. */
163         for (i = 0; i < type->cnt; i++) {
164                 phys_addr_t rgnbase = type->regions[i].base;
165                 phys_addr_t rgnsize = type->regions[i].size;
166
167                 if ((rgnbase == base) && (rgnsize == size))
168                         /* Already have this region, so we're done */
169                         return 0;
170
171                 adjacent = memblock_addrs_adjacent(base, size, rgnbase, rgnsize);
172                 if (adjacent > 0) {
173                         type->regions[i].base -= size;
174                         type->regions[i].size += size;
175                         coalesced++;
176                         break;
177                 } else if (adjacent < 0) {
178                         type->regions[i].size += size;
179                         coalesced++;
180                         break;
181                 }
182         }
183
184         if ((i < type->cnt - 1) && memblock_regions_adjacent(type, i, i+1)) {
185                 memblock_coalesce_regions(type, i, i+1);
186                 coalesced++;
187         }
188
189         if (coalesced)
190                 return coalesced;
191         if (type->cnt >= type->max)
192                 return -1;
193
194         /* Couldn't coalesce the MEMBLOCK, so add it to the sorted table. */
195         for (i = type->cnt - 1; i >= 0; i--) {
196                 if (base < type->regions[i].base) {
197                         type->regions[i+1].base = type->regions[i].base;
198                         type->regions[i+1].size = type->regions[i].size;
199                 } else {
200                         type->regions[i+1].base = base;
201                         type->regions[i+1].size = size;
202                         break;
203                 }
204         }
205
206         if (base < type->regions[0].base) {
207                 type->regions[0].base = base;
208                 type->regions[0].size = size;
209         }
210         type->cnt++;
211
212         return 0;
213 }
214
215 long memblock_add(phys_addr_t base, phys_addr_t size)
216 {
217         return memblock_add_region(&memblock.memory, base, size);
218
219 }
220
221 static long __memblock_remove(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
222 {
223         phys_addr_t rgnbegin, rgnend;
224         phys_addr_t end = base + size;
225         int i;
226
227         rgnbegin = rgnend = 0; /* supress gcc warnings */
228
229         /* Find the region where (base, size) belongs to */
230         for (i=0; i < type->cnt; i++) {
231                 rgnbegin = type->regions[i].base;
232                 rgnend = rgnbegin + type->regions[i].size;
233
234                 if ((rgnbegin <= base) && (end <= rgnend))
235                         break;
236         }
237
238         /* Didn't find the region */
239         if (i == type->cnt)
240                 return -1;
241
242         /* Check to see if we are removing entire region */
243         if ((rgnbegin == base) && (rgnend == end)) {
244                 memblock_remove_region(type, i);
245                 return 0;
246         }
247
248         /* Check to see if region is matching at the front */
249         if (rgnbegin == base) {
250                 type->regions[i].base = end;
251                 type->regions[i].size -= size;
252                 return 0;
253         }
254
255         /* Check to see if the region is matching at the end */
256         if (rgnend == end) {
257                 type->regions[i].size -= size;
258                 return 0;
259         }
260
261         /*
262          * We need to split the entry -  adjust the current one to the
263          * beginging of the hole and add the region after hole.
264          */
265         type->regions[i].size = base - type->regions[i].base;
266         return memblock_add_region(type, end, rgnend - end);
267 }
268
269 long memblock_remove(phys_addr_t base, phys_addr_t size)
270 {
271         return __memblock_remove(&memblock.memory, base, size);
272 }
273
274 long __init memblock_free(phys_addr_t base, phys_addr_t size)
275 {
276         return __memblock_remove(&memblock.reserved, base, size);
277 }
278
279 long __init memblock_reserve(phys_addr_t base, phys_addr_t size)
280 {
281         struct memblock_type *_rgn = &memblock.reserved;
282
283         BUG_ON(0 == size);
284
285         return memblock_add_region(_rgn, base, size);
286 }
287
288 long memblock_overlaps_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size)
289 {
290         unsigned long i;
291
292         for (i = 0; i < type->cnt; i++) {
293                 phys_addr_t rgnbase = type->regions[i].base;
294                 phys_addr_t rgnsize = type->regions[i].size;
295                 if (memblock_addrs_overlap(base, size, rgnbase, rgnsize))
296                         break;
297         }
298
299         return (i < type->cnt) ? i : -1;
300 }
301
302 static phys_addr_t memblock_align_down(phys_addr_t addr, phys_addr_t size)
303 {
304         return addr & ~(size - 1);
305 }
306
307 static phys_addr_t memblock_align_up(phys_addr_t addr, phys_addr_t size)
308 {
309         return (addr + (size - 1)) & ~(size - 1);
310 }
311
312 static phys_addr_t __init memblock_alloc_region(phys_addr_t start, phys_addr_t end,
313                                            phys_addr_t size, phys_addr_t align)
314 {
315         phys_addr_t base, res_base;
316         long j;
317
318         base = memblock_align_down((end - size), align);
319         while (start <= base) {
320                 j = memblock_overlaps_region(&memblock.reserved, base, size);
321                 if (j < 0) {
322                         /* this area isn't reserved, take it */
323                         if (memblock_add_region(&memblock.reserved, base, size) < 0)
324                                 base = ~(phys_addr_t)0;
325                         return base;
326                 }
327                 res_base = memblock.reserved.regions[j].base;
328                 if (res_base < size)
329                         break;
330                 base = memblock_align_down(res_base - size, align);
331         }
332
333         return ~(phys_addr_t)0;
334 }
335
336 phys_addr_t __weak __init memblock_nid_range(phys_addr_t start, phys_addr_t end, int *nid)
337 {
338         *nid = 0;
339
340         return end;
341 }
342
343 static phys_addr_t __init memblock_alloc_nid_region(struct memblock_region *mp,
344                                                phys_addr_t size,
345                                                phys_addr_t align, int nid)
346 {
347         phys_addr_t start, end;
348
349         start = mp->base;
350         end = start + mp->size;
351
352         start = memblock_align_up(start, align);
353         while (start < end) {
354                 phys_addr_t this_end;
355                 int this_nid;
356
357                 this_end = memblock_nid_range(start, end, &this_nid);
358                 if (this_nid == nid) {
359                         phys_addr_t ret = memblock_alloc_region(start, this_end, size, align);
360                         if (ret != ~(phys_addr_t)0)
361                                 return ret;
362                 }
363                 start = this_end;
364         }
365
366         return ~(phys_addr_t)0;
367 }
368
369 phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
370 {
371         struct memblock_type *mem = &memblock.memory;
372         int i;
373
374         BUG_ON(0 == size);
375
376         /* We do a bottom-up search for a region with the right
377          * nid since that's easier considering how memblock_nid_range()
378          * works
379          */
380         size = memblock_align_up(size, align);
381
382         for (i = 0; i < mem->cnt; i++) {
383                 phys_addr_t ret = memblock_alloc_nid_region(&mem->regions[i],
384                                                size, align, nid);
385                 if (ret != ~(phys_addr_t)0)
386                         return ret;
387         }
388
389         return memblock_alloc(size, align);
390 }
391
392 phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
393 {
394         return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
395 }
396
397 phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
398 {
399         phys_addr_t alloc;
400
401         alloc = __memblock_alloc_base(size, align, max_addr);
402
403         if (alloc == 0)
404                 panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
405                       (unsigned long long) size, (unsigned long long) max_addr);
406
407         return alloc;
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         long i;
413         phys_addr_t base = 0;
414         phys_addr_t res_base;
415
416         BUG_ON(0 == size);
417
418         size = memblock_align_up(size, align);
419
420         /* Pump up max_addr */
421         if (max_addr == MEMBLOCK_ALLOC_ACCESSIBLE)
422                 max_addr = memblock.current_limit;
423
424         /* We do a top-down search, this tends to limit memory
425          * fragmentation by keeping early boot allocs near the
426          * top of memory
427          */
428         for (i = memblock.memory.cnt - 1; i >= 0; i--) {
429                 phys_addr_t memblockbase = memblock.memory.regions[i].base;
430                 phys_addr_t memblocksize = memblock.memory.regions[i].size;
431
432                 if (memblocksize < size)
433                         continue;
434                 base = min(memblockbase + memblocksize, max_addr);
435                 res_base = memblock_alloc_region(memblockbase, base, size, align);
436                 if (res_base != ~(phys_addr_t)0)
437                         return res_base;
438         }
439         return 0;
440 }
441
442 /* You must call memblock_analyze() before this. */
443 phys_addr_t __init memblock_phys_mem_size(void)
444 {
445         return memblock.memory_size;
446 }
447
448 phys_addr_t memblock_end_of_DRAM(void)
449 {
450         int idx = memblock.memory.cnt - 1;
451
452         return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
453 }
454
455 /* You must call memblock_analyze() after this. */
456 void __init memblock_enforce_memory_limit(phys_addr_t memory_limit)
457 {
458         unsigned long i;
459         phys_addr_t limit;
460         struct memblock_region *p;
461
462         if (!memory_limit)
463                 return;
464
465         /* Truncate the memblock regions to satisfy the memory limit. */
466         limit = memory_limit;
467         for (i = 0; i < memblock.memory.cnt; i++) {
468                 if (limit > memblock.memory.regions[i].size) {
469                         limit -= memblock.memory.regions[i].size;
470                         continue;
471                 }
472
473                 memblock.memory.regions[i].size = limit;
474                 memblock.memory.cnt = i + 1;
475                 break;
476         }
477
478         memory_limit = memblock_end_of_DRAM();
479
480         /* And truncate any reserves above the limit also. */
481         for (i = 0; i < memblock.reserved.cnt; i++) {
482                 p = &memblock.reserved.regions[i];
483
484                 if (p->base > memory_limit)
485                         p->size = 0;
486                 else if ((p->base + p->size) > memory_limit)
487                         p->size = memory_limit - p->base;
488
489                 if (p->size == 0) {
490                         memblock_remove_region(&memblock.reserved, i);
491                         i--;
492                 }
493         }
494 }
495
496 static int memblock_search(struct memblock_type *type, phys_addr_t addr)
497 {
498         unsigned int left = 0, right = type->cnt;
499
500         do {
501                 unsigned int mid = (right + left) / 2;
502
503                 if (addr < type->regions[mid].base)
504                         right = mid;
505                 else if (addr >= (type->regions[mid].base +
506                                   type->regions[mid].size))
507                         left = mid + 1;
508                 else
509                         return mid;
510         } while (left < right);
511         return -1;
512 }
513
514 int __init memblock_is_reserved(phys_addr_t addr)
515 {
516         return memblock_search(&memblock.reserved, addr) != -1;
517 }
518
519 int memblock_is_memory(phys_addr_t addr)
520 {
521         return memblock_search(&memblock.memory, addr) != -1;
522 }
523
524 int memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
525 {
526         int idx = memblock_search(&memblock.reserved, base);
527
528         if (idx == -1)
529                 return 0;
530         return memblock.reserved.regions[idx].base <= base &&
531                 (memblock.reserved.regions[idx].base +
532                  memblock.reserved.regions[idx].size) >= (base + size);
533 }
534
535 int memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
536 {
537         return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
538 }
539
540
541 void __init memblock_set_current_limit(phys_addr_t limit)
542 {
543         memblock.current_limit = limit;
544 }
545