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