memblock: Make memblock_find_region() out of memblock_alloc_region()
[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_find_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                         return base;
323                 res_base = memblock.reserved.regions[j].base;
324                 if (res_base < size)
325                         break;
326                 base = memblock_align_down(res_base - size, align);
327         }
328
329         return ~(phys_addr_t)0;
330 }
331
332 phys_addr_t __weak __init memblock_nid_range(phys_addr_t start, phys_addr_t end, int *nid)
333 {
334         *nid = 0;
335
336         return end;
337 }
338
339 static phys_addr_t __init memblock_alloc_nid_region(struct memblock_region *mp,
340                                                phys_addr_t size,
341                                                phys_addr_t align, int nid)
342 {
343         phys_addr_t start, end;
344
345         start = mp->base;
346         end = start + mp->size;
347
348         start = memblock_align_up(start, align);
349         while (start < end) {
350                 phys_addr_t this_end;
351                 int this_nid;
352
353                 this_end = memblock_nid_range(start, end, &this_nid);
354                 if (this_nid == nid) {
355                         phys_addr_t ret = memblock_find_region(start, this_end, size, align);
356                         if (ret != ~(phys_addr_t)0 &&
357                             memblock_add_region(&memblock.reserved, ret, size) >= 0)
358                                 return ret;
359                 }
360                 start = this_end;
361         }
362
363         return ~(phys_addr_t)0;
364 }
365
366 phys_addr_t __init memblock_alloc_nid(phys_addr_t size, phys_addr_t align, int nid)
367 {
368         struct memblock_type *mem = &memblock.memory;
369         int i;
370
371         BUG_ON(0 == size);
372
373         /* We do a bottom-up search for a region with the right
374          * nid since that's easier considering how memblock_nid_range()
375          * works
376          */
377         size = memblock_align_up(size, align);
378
379         for (i = 0; i < mem->cnt; i++) {
380                 phys_addr_t ret = memblock_alloc_nid_region(&mem->regions[i],
381                                                size, align, nid);
382                 if (ret != ~(phys_addr_t)0)
383                         return ret;
384         }
385
386         return memblock_alloc(size, align);
387 }
388
389 phys_addr_t __init memblock_alloc(phys_addr_t size, phys_addr_t align)
390 {
391         return memblock_alloc_base(size, align, MEMBLOCK_ALLOC_ACCESSIBLE);
392 }
393
394 phys_addr_t __init memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
395 {
396         phys_addr_t alloc;
397
398         alloc = __memblock_alloc_base(size, align, max_addr);
399
400         if (alloc == 0)
401                 panic("ERROR: Failed to allocate 0x%llx bytes below 0x%llx.\n",
402                       (unsigned long long) size, (unsigned long long) max_addr);
403
404         return alloc;
405 }
406
407 phys_addr_t __init __memblock_alloc_base(phys_addr_t size, phys_addr_t align, phys_addr_t max_addr)
408 {
409         long i;
410         phys_addr_t base = 0;
411         phys_addr_t res_base;
412
413         BUG_ON(0 == size);
414
415         size = memblock_align_up(size, align);
416
417         /* Pump up max_addr */
418         if (max_addr == MEMBLOCK_ALLOC_ACCESSIBLE)
419                 max_addr = memblock.current_limit;
420
421         /* We do a top-down search, this tends to limit memory
422          * fragmentation by keeping early boot allocs near the
423          * top of memory
424          */
425         for (i = memblock.memory.cnt - 1; i >= 0; i--) {
426                 phys_addr_t memblockbase = memblock.memory.regions[i].base;
427                 phys_addr_t memblocksize = memblock.memory.regions[i].size;
428
429                 if (memblocksize < size)
430                         continue;
431                 base = min(memblockbase + memblocksize, max_addr);
432                 res_base = memblock_find_region(memblockbase, base, size, align);
433                 if (res_base != ~(phys_addr_t)0 &&
434                     memblock_add_region(&memblock.reserved, res_base, size) >= 0)
435                         return res_base;
436         }
437         return 0;
438 }
439
440 /* You must call memblock_analyze() before this. */
441 phys_addr_t __init memblock_phys_mem_size(void)
442 {
443         return memblock.memory_size;
444 }
445
446 phys_addr_t memblock_end_of_DRAM(void)
447 {
448         int idx = memblock.memory.cnt - 1;
449
450         return (memblock.memory.regions[idx].base + memblock.memory.regions[idx].size);
451 }
452
453 /* You must call memblock_analyze() after this. */
454 void __init memblock_enforce_memory_limit(phys_addr_t memory_limit)
455 {
456         unsigned long i;
457         phys_addr_t limit;
458         struct memblock_region *p;
459
460         if (!memory_limit)
461                 return;
462
463         /* Truncate the memblock regions to satisfy the memory limit. */
464         limit = memory_limit;
465         for (i = 0; i < memblock.memory.cnt; i++) {
466                 if (limit > memblock.memory.regions[i].size) {
467                         limit -= memblock.memory.regions[i].size;
468                         continue;
469                 }
470
471                 memblock.memory.regions[i].size = limit;
472                 memblock.memory.cnt = i + 1;
473                 break;
474         }
475
476         memory_limit = memblock_end_of_DRAM();
477
478         /* And truncate any reserves above the limit also. */
479         for (i = 0; i < memblock.reserved.cnt; i++) {
480                 p = &memblock.reserved.regions[i];
481
482                 if (p->base > memory_limit)
483                         p->size = 0;
484                 else if ((p->base + p->size) > memory_limit)
485                         p->size = memory_limit - p->base;
486
487                 if (p->size == 0) {
488                         memblock_remove_region(&memblock.reserved, i);
489                         i--;
490                 }
491         }
492 }
493
494 static int memblock_search(struct memblock_type *type, phys_addr_t addr)
495 {
496         unsigned int left = 0, right = type->cnt;
497
498         do {
499                 unsigned int mid = (right + left) / 2;
500
501                 if (addr < type->regions[mid].base)
502                         right = mid;
503                 else if (addr >= (type->regions[mid].base +
504                                   type->regions[mid].size))
505                         left = mid + 1;
506                 else
507                         return mid;
508         } while (left < right);
509         return -1;
510 }
511
512 int __init memblock_is_reserved(phys_addr_t addr)
513 {
514         return memblock_search(&memblock.reserved, addr) != -1;
515 }
516
517 int memblock_is_memory(phys_addr_t addr)
518 {
519         return memblock_search(&memblock.memory, addr) != -1;
520 }
521
522 int memblock_is_region_memory(phys_addr_t base, phys_addr_t size)
523 {
524         int idx = memblock_search(&memblock.reserved, base);
525
526         if (idx == -1)
527                 return 0;
528         return memblock.reserved.regions[idx].base <= base &&
529                 (memblock.reserved.regions[idx].base +
530                  memblock.reserved.regions[idx].size) >= (base + size);
531 }
532
533 int memblock_is_region_reserved(phys_addr_t base, phys_addr_t size)
534 {
535         return memblock_overlaps_region(&memblock.reserved, base, size) >= 0;
536 }
537
538
539 void __init memblock_set_current_limit(phys_addr_t limit)
540 {
541         memblock.current_limit = limit;
542 }
543