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