aaff3932588e4436125a467be5bb5c2619da10d3
[linux-2.6.git] / arch / x86 / mm / memblock.c
1 #include <linux/kernel.h>
2 #include <linux/types.h>
3 #include <linux/init.h>
4 #include <linux/bitops.h>
5 #include <linux/memblock.h>
6 #include <linux/bootmem.h>
7 #include <linux/mm.h>
8 #include <linux/range.h>
9
10 /* Check for already reserved areas */
11 static inline bool __init bad_addr_size(u64 *addrp, u64 *sizep, u64 align)
12 {
13         struct memblock_region *r;
14         u64 addr = *addrp, last;
15         u64 size = *sizep;
16         bool changed = false;
17
18 again:
19         last = addr + size;
20         for_each_memblock(reserved, r) {
21                 if (last > r->base && addr < r->base) {
22                         size = r->base - addr;
23                         changed = true;
24                         goto again;
25                 }
26                 if (last > (r->base + r->size) && addr < (r->base + r->size)) {
27                         addr = round_up(r->base + r->size, align);
28                         size = last - addr;
29                         changed = true;
30                         goto again;
31                 }
32                 if (last <= (r->base + r->size) && addr >= r->base) {
33                         (*sizep)++;
34                         return false;
35                 }
36         }
37         if (changed) {
38                 *addrp = addr;
39                 *sizep = size;
40         }
41         return changed;
42 }
43
44 static u64 __init __memblock_x86_find_in_range_size(u64 ei_start, u64 ei_last, u64 start,
45                          u64 *sizep, u64 align)
46 {
47         u64 addr, last;
48
49         addr = round_up(ei_start, align);
50         if (addr < start)
51                 addr = round_up(start, align);
52         if (addr >= ei_last)
53                 goto out;
54         *sizep = ei_last - addr;
55         while (bad_addr_size(&addr, sizep, align) && addr + *sizep <= ei_last)
56                 ;
57         last = addr + *sizep;
58         if (last > ei_last)
59                 goto out;
60
61         return addr;
62
63 out:
64         return MEMBLOCK_ERROR;
65 }
66
67 /*
68  * Find next free range after start, and size is returned in *sizep
69  */
70 u64 __init memblock_x86_find_in_range_size(u64 start, u64 *sizep, u64 align)
71 {
72         struct memblock_region *r;
73
74         for_each_memblock(memory, r) {
75                 u64 ei_start = r->base;
76                 u64 ei_last = ei_start + r->size;
77                 u64 addr;
78
79                 addr = __memblock_x86_find_in_range_size(ei_start, ei_last, start,
80                                          sizep, align);
81
82                 if (addr != MEMBLOCK_ERROR)
83                         return addr;
84         }
85
86         return MEMBLOCK_ERROR;
87 }
88
89 static __init struct range *find_range_array(int count)
90 {
91         u64 end, size, mem;
92         struct range *range;
93
94         size = sizeof(struct range) * count;
95         end = memblock.current_limit;
96
97         mem = memblock_find_in_range(0, end, size, sizeof(struct range));
98         if (mem == MEMBLOCK_ERROR)
99                 panic("can not find more space for range array");
100
101         /*
102          * This range is tempoaray, so don't reserve it, it will not be
103          * overlapped because We will not alloccate new buffer before
104          * We discard this one
105          */
106         range = __va(mem);
107         memset(range, 0, size);
108
109         return range;
110 }
111
112 #ifdef CONFIG_NO_BOOTMEM
113 static void __init memblock_x86_subtract_reserved(struct range *range, int az)
114 {
115         u64 final_start, final_end;
116         struct memblock_region *r;
117
118         /* Take out region array itself at first*/
119         memblock_free_reserved_regions();
120
121         memblock_dbg("Subtract (%ld early reservations)\n", memblock.reserved.cnt);
122
123         for_each_memblock(reserved, r) {
124                 memblock_dbg("  [%010llx-%010llx]\n", (u64)r->base, (u64)r->base + r->size - 1);
125                 final_start = PFN_DOWN(r->base);
126                 final_end = PFN_UP(r->base + r->size);
127                 if (final_start >= final_end)
128                         continue;
129                 subtract_range(range, az, final_start, final_end);
130         }
131
132         /* Put region array back ? */
133         memblock_reserve_reserved_regions();
134 }
135
136 struct count_data {
137         int nr;
138 };
139
140 static int __init count_work_fn(unsigned long start_pfn,
141                                 unsigned long end_pfn, void *datax)
142 {
143         struct count_data *data = datax;
144
145         data->nr++;
146
147         return 0;
148 }
149
150 static int __init count_early_node_map(int nodeid)
151 {
152         struct count_data data;
153
154         data.nr = 0;
155         work_with_active_regions(nodeid, count_work_fn, &data);
156
157         return data.nr;
158 }
159
160 int __init get_free_all_memory_range(struct range **rangep, int nodeid)
161 {
162         int count;
163         struct range *range;
164         int nr_range;
165
166         count = (memblock.reserved.cnt + count_early_node_map(nodeid)) * 2;
167
168         range = find_range_array(count);
169         nr_range = 0;
170
171         /*
172          * Use early_node_map[] and memblock.reserved.region to get range array
173          * at first
174          */
175         nr_range = add_from_early_node_map(range, count, nr_range, nodeid);
176 #ifdef CONFIG_X86_32
177         subtract_range(range, count, max_low_pfn, -1ULL);
178 #endif
179         memblock_x86_subtract_reserved(range, count);
180         nr_range = clean_sort_range(range, count);
181
182         *rangep = range;
183         return nr_range;
184 }
185 #else
186 void __init memblock_x86_to_bootmem(u64 start, u64 end)
187 {
188         int count;
189         u64 final_start, final_end;
190         struct memblock_region *r;
191
192         /* Take out region array itself */
193         memblock_free_reserved_regions();
194
195         count  = memblock.reserved.cnt;
196         memblock_dbg("(%d early reservations) ==> bootmem [%#010llx-%#010llx]\n", count, start, end - 1);
197         for_each_memblock(reserved, r) {
198                 memblock_dbg("  [%#010llx-%#010llx] ", (u64)r->base, (u64)r->base + r->size - 1);
199                 final_start = max(start, r->base);
200                 final_end = min(end, r->base + r->size);
201                 if (final_start >= final_end) {
202                         memblock_dbg("\n");
203                         continue;
204                 }
205                 memblock_dbg(" ==> [%#010llx-%#010llx]\n", final_start, final_end - 1);
206                 reserve_bootmem_generic(final_start, final_end - final_start, BOOTMEM_DEFAULT);
207         }
208
209         /* Put region array back ? */
210         memblock_reserve_reserved_regions();
211 }
212 #endif
213
214 static u64 __init __memblock_x86_memory_in_range(u64 addr, u64 limit, bool get_free)
215 {
216         int i, count;
217         struct range *range;
218         int nr_range;
219         u64 final_start, final_end;
220         u64 free_size;
221         struct memblock_region *r;
222
223         count = (memblock.reserved.cnt + memblock.memory.cnt) * 2;
224
225         range = find_range_array(count);
226         nr_range = 0;
227
228         addr = PFN_UP(addr);
229         limit = PFN_DOWN(limit);
230
231         for_each_memblock(memory, r) {
232                 final_start = PFN_UP(r->base);
233                 final_end = PFN_DOWN(r->base + r->size);
234                 if (final_start >= final_end)
235                         continue;
236                 if (final_start >= limit || final_end <= addr)
237                         continue;
238
239                 nr_range = add_range(range, count, nr_range, final_start, final_end);
240         }
241         subtract_range(range, count, 0, addr);
242         subtract_range(range, count, limit, -1ULL);
243
244         /* Subtract memblock.reserved.region in range ? */
245         if (!get_free)
246                 goto sort_and_count_them;
247         for_each_memblock(reserved, r) {
248                 final_start = PFN_DOWN(r->base);
249                 final_end = PFN_UP(r->base + r->size);
250                 if (final_start >= final_end)
251                         continue;
252                 if (final_start >= limit || final_end <= addr)
253                         continue;
254
255                 subtract_range(range, count, final_start, final_end);
256         }
257
258 sort_and_count_them:
259         nr_range = clean_sort_range(range, count);
260
261         free_size = 0;
262         for (i = 0; i < nr_range; i++)
263                 free_size += range[i].end - range[i].start;
264
265         return free_size << PAGE_SHIFT;
266 }
267
268 u64 __init memblock_x86_free_memory_in_range(u64 addr, u64 limit)
269 {
270         return __memblock_x86_memory_in_range(addr, limit, true);
271 }
272
273 u64 __init memblock_x86_memory_in_range(u64 addr, u64 limit)
274 {
275         return __memblock_x86_memory_in_range(addr, limit, false);
276 }
277
278 void __init memblock_x86_reserve_range(u64 start, u64 end, char *name)
279 {
280         if (start == end)
281                 return;
282
283         if (WARN_ONCE(start > end, "memblock_x86_reserve_range: wrong range [%#llx, %#llx)\n", start, end))
284                 return;
285
286         memblock_dbg("    memblock_x86_reserve_range: [%#010llx-%#010llx] %16s\n", start, end - 1, name);
287
288         memblock_reserve(start, end - start);
289 }
290
291 void __init memblock_x86_free_range(u64 start, u64 end)
292 {
293         if (start == end)
294                 return;
295
296         if (WARN_ONCE(start > end, "memblock_x86_free_range: wrong range [%#llx, %#llx)\n", start, end))
297                 return;
298
299         memblock_dbg("       memblock_x86_free_range: [%#010llx-%#010llx]\n", start, end - 1);
300
301         memblock_free(start, end - start);
302 }
303
304 /*
305  * Need to call this function after memblock_x86_register_active_regions,
306  * so early_node_map[] is filled already.
307  */
308 u64 __init memblock_x86_find_in_range_node(int nid, u64 start, u64 end, u64 size, u64 align)
309 {
310         u64 addr;
311         addr = find_memory_core_early(nid, size, align, start, end);
312         if (addr != MEMBLOCK_ERROR)
313                 return addr;
314
315         /* Fallback, should already have start end within node range */
316         return memblock_find_in_range(start, end, size, align);
317 }
318
319 /*
320  * Finds an active region in the address range from start_pfn to last_pfn and
321  * returns its range in ei_startpfn and ei_endpfn for the memblock entry.
322  */
323 static int __init memblock_x86_find_active_region(const struct memblock_region *ei,
324                                   unsigned long start_pfn,
325                                   unsigned long last_pfn,
326                                   unsigned long *ei_startpfn,
327                                   unsigned long *ei_endpfn)
328 {
329         u64 align = PAGE_SIZE;
330
331         *ei_startpfn = round_up(ei->base, align) >> PAGE_SHIFT;
332         *ei_endpfn = round_down(ei->base + ei->size, align) >> PAGE_SHIFT;
333
334         /* Skip map entries smaller than a page */
335         if (*ei_startpfn >= *ei_endpfn)
336                 return 0;
337
338         /* Skip if map is outside the node */
339         if (*ei_endpfn <= start_pfn || *ei_startpfn >= last_pfn)
340                 return 0;
341
342         /* Check for overlaps */
343         if (*ei_startpfn < start_pfn)
344                 *ei_startpfn = start_pfn;
345         if (*ei_endpfn > last_pfn)
346                 *ei_endpfn = last_pfn;
347
348         return 1;
349 }
350
351 /* Walk the memblock.memory map and register active regions within a node */
352 void __init memblock_x86_register_active_regions(int nid, unsigned long start_pfn,
353                                          unsigned long last_pfn)
354 {
355         unsigned long ei_startpfn;
356         unsigned long ei_endpfn;
357         struct memblock_region *r;
358
359         for_each_memblock(memory, r)
360                 if (memblock_x86_find_active_region(r, start_pfn, last_pfn,
361                                            &ei_startpfn, &ei_endpfn))
362                         add_active_range(nid, ei_startpfn, ei_endpfn);
363 }
364
365 /*
366  * Find the hole size (in bytes) in the memory range.
367  * @start: starting address of the memory range to scan
368  * @end: ending address of the memory range to scan
369  */
370 u64 __init memblock_x86_hole_size(u64 start, u64 end)
371 {
372         unsigned long start_pfn = start >> PAGE_SHIFT;
373         unsigned long last_pfn = end >> PAGE_SHIFT;
374         unsigned long ei_startpfn, ei_endpfn, ram = 0;
375         struct memblock_region *r;
376
377         for_each_memblock(memory, r)
378                 if (memblock_x86_find_active_region(r, start_pfn, last_pfn,
379                                            &ei_startpfn, &ei_endpfn))
380                         ram += ei_endpfn - ei_startpfn;
381
382         return end - start - ((u64)ram << PAGE_SHIFT);
383 }