early_res: Add free_early_partial()
[linux-2.6.git] / kernel / early_res.c
1 /*
2  * early_res, could be used to replace bootmem
3  */
4 #include <linux/kernel.h>
5 #include <linux/types.h>
6 #include <linux/init.h>
7 #include <linux/bootmem.h>
8 #include <linux/mm.h>
9 #include <linux/early_res.h>
10
11 /*
12  * Early reserved memory areas.
13  */
14 /*
15  * need to make sure this one is bigger enough before
16  * find_fw_memmap_area could be used
17  */
18 #define MAX_EARLY_RES_X 32
19
20 struct early_res {
21         u64 start, end;
22         char name[15];
23         char overlap_ok;
24 };
25 static struct early_res early_res_x[MAX_EARLY_RES_X] __initdata;
26
27 static int max_early_res __initdata = MAX_EARLY_RES_X;
28 static struct early_res *early_res __initdata = &early_res_x[0];
29 static int early_res_count __initdata;
30
31 static int __init find_overlapped_early(u64 start, u64 end)
32 {
33         int i;
34         struct early_res *r;
35
36         for (i = 0; i < max_early_res && early_res[i].end; i++) {
37                 r = &early_res[i];
38                 if (end > r->start && start < r->end)
39                         break;
40         }
41
42         return i;
43 }
44
45 /*
46  * Drop the i-th range from the early reservation map,
47  * by copying any higher ranges down one over it, and
48  * clearing what had been the last slot.
49  */
50 static void __init drop_range(int i)
51 {
52         int j;
53
54         for (j = i + 1; j < max_early_res && early_res[j].end; j++)
55                 ;
56
57         memmove(&early_res[i], &early_res[i + 1],
58                (j - 1 - i) * sizeof(struct early_res));
59
60         early_res[j - 1].end = 0;
61         early_res_count--;
62 }
63
64 static void __init drop_range_partial(int i, u64 start, u64 end)
65 {
66         u64 common_start, common_end;
67         u64 old_start, old_end;
68
69         old_start = early_res[i].start;
70         old_end = early_res[i].end;
71         common_start = max(old_start, start);
72         common_end = min(old_end, end);
73
74         /* no overlap ? */
75         if (common_start >= common_end)
76                 return;
77
78         if (old_start < common_start) {
79                 /* make head segment */
80                 early_res[i].end = common_start;
81                 if (old_end > common_end) {
82                         /* add another for left over on tail */
83                         reserve_early_without_check(common_end, old_end,
84                                          early_res[i].name);
85                 }
86                 return;
87         } else {
88                 if (old_end > common_end) {
89                         /* reuse the entry for tail left */
90                         early_res[i].start = common_end;
91                         return;
92                 }
93                 /* all covered */
94                 drop_range(i);
95         }
96 }
97
98 /*
99  * Split any existing ranges that:
100  *  1) are marked 'overlap_ok', and
101  *  2) overlap with the stated range [start, end)
102  * into whatever portion (if any) of the existing range is entirely
103  * below or entirely above the stated range.  Drop the portion
104  * of the existing range that overlaps with the stated range,
105  * which will allow the caller of this routine to then add that
106  * stated range without conflicting with any existing range.
107  */
108 static void __init drop_overlaps_that_are_ok(u64 start, u64 end)
109 {
110         int i;
111         struct early_res *r;
112         u64 lower_start, lower_end;
113         u64 upper_start, upper_end;
114         char name[15];
115
116         for (i = 0; i < max_early_res && early_res[i].end; i++) {
117                 r = &early_res[i];
118
119                 /* Continue past non-overlapping ranges */
120                 if (end <= r->start || start >= r->end)
121                         continue;
122
123                 /*
124                  * Leave non-ok overlaps as is; let caller
125                  * panic "Overlapping early reservations"
126                  * when it hits this overlap.
127                  */
128                 if (!r->overlap_ok)
129                         return;
130
131                 /*
132                  * We have an ok overlap.  We will drop it from the early
133                  * reservation map, and add back in any non-overlapping
134                  * portions (lower or upper) as separate, overlap_ok,
135                  * non-overlapping ranges.
136                  */
137
138                 /* 1. Note any non-overlapping (lower or upper) ranges. */
139                 strncpy(name, r->name, sizeof(name) - 1);
140
141                 lower_start = lower_end = 0;
142                 upper_start = upper_end = 0;
143                 if (r->start < start) {
144                         lower_start = r->start;
145                         lower_end = start;
146                 }
147                 if (r->end > end) {
148                         upper_start = end;
149                         upper_end = r->end;
150                 }
151
152                 /* 2. Drop the original ok overlapping range */
153                 drop_range(i);
154
155                 i--;            /* resume for-loop on copied down entry */
156
157                 /* 3. Add back in any non-overlapping ranges. */
158                 if (lower_end)
159                         reserve_early_overlap_ok(lower_start, lower_end, name);
160                 if (upper_end)
161                         reserve_early_overlap_ok(upper_start, upper_end, name);
162         }
163 }
164
165 static void __init __reserve_early(u64 start, u64 end, char *name,
166                                                 int overlap_ok)
167 {
168         int i;
169         struct early_res *r;
170
171         i = find_overlapped_early(start, end);
172         if (i >= max_early_res)
173                 panic("Too many early reservations");
174         r = &early_res[i];
175         if (r->end)
176                 panic("Overlapping early reservations "
177                       "%llx-%llx %s to %llx-%llx %s\n",
178                       start, end - 1, name ? name : "", r->start,
179                       r->end - 1, r->name);
180         r->start = start;
181         r->end = end;
182         r->overlap_ok = overlap_ok;
183         if (name)
184                 strncpy(r->name, name, sizeof(r->name) - 1);
185         early_res_count++;
186 }
187
188 /*
189  * A few early reservtations come here.
190  *
191  * The 'overlap_ok' in the name of this routine does -not- mean it
192  * is ok for these reservations to overlap an earlier reservation.
193  * Rather it means that it is ok for subsequent reservations to
194  * overlap this one.
195  *
196  * Use this entry point to reserve early ranges when you are doing
197  * so out of "Paranoia", reserving perhaps more memory than you need,
198  * just in case, and don't mind a subsequent overlapping reservation
199  * that is known to be needed.
200  *
201  * The drop_overlaps_that_are_ok() call here isn't really needed.
202  * It would be needed if we had two colliding 'overlap_ok'
203  * reservations, so that the second such would not panic on the
204  * overlap with the first.  We don't have any such as of this
205  * writing, but might as well tolerate such if it happens in
206  * the future.
207  */
208 void __init reserve_early_overlap_ok(u64 start, u64 end, char *name)
209 {
210         drop_overlaps_that_are_ok(start, end);
211         __reserve_early(start, end, name, 1);
212 }
213
214 static void __init __check_and_double_early_res(u64 ex_start, u64 ex_end)
215 {
216         u64 start, end, size, mem;
217         struct early_res *new;
218
219         /* do we have enough slots left ? */
220         if ((max_early_res - early_res_count) > max(max_early_res/8, 2))
221                 return;
222
223         /* double it */
224         mem = -1ULL;
225         size = sizeof(struct early_res) * max_early_res * 2;
226         if (early_res == early_res_x)
227                 start = 0;
228         else
229                 start = early_res[0].end;
230         end = ex_start;
231         if (start + size < end)
232                 mem = find_fw_memmap_area(start, end, size,
233                                          sizeof(struct early_res));
234         if (mem == -1ULL) {
235                 start = ex_end;
236                 end = get_max_mapped();
237                 if (start + size < end)
238                         mem = find_fw_memmap_area(start, end, size,
239                                                  sizeof(struct early_res));
240         }
241         if (mem == -1ULL)
242                 panic("can not find more space for early_res array");
243
244         new = __va(mem);
245         /* save the first one for own */
246         new[0].start = mem;
247         new[0].end = mem + size;
248         new[0].overlap_ok = 0;
249         /* copy old to new */
250         if (early_res == early_res_x) {
251                 memcpy(&new[1], &early_res[0],
252                          sizeof(struct early_res) * max_early_res);
253                 memset(&new[max_early_res+1], 0,
254                          sizeof(struct early_res) * (max_early_res - 1));
255                 early_res_count++;
256         } else {
257                 memcpy(&new[1], &early_res[1],
258                          sizeof(struct early_res) * (max_early_res - 1));
259                 memset(&new[max_early_res], 0,
260                          sizeof(struct early_res) * max_early_res);
261         }
262         memset(&early_res[0], 0, sizeof(struct early_res) * max_early_res);
263         early_res = new;
264         max_early_res *= 2;
265         printk(KERN_DEBUG "early_res array is doubled to %d at [%llx - %llx]\n",
266                 max_early_res, mem, mem + size - 1);
267 }
268
269 /*
270  * Most early reservations come here.
271  *
272  * We first have drop_overlaps_that_are_ok() drop any pre-existing
273  * 'overlap_ok' ranges, so that we can then reserve this memory
274  * range without risk of panic'ing on an overlapping overlap_ok
275  * early reservation.
276  */
277 void __init reserve_early(u64 start, u64 end, char *name)
278 {
279         if (start >= end)
280                 return;
281
282         __check_and_double_early_res(start, end);
283
284         drop_overlaps_that_are_ok(start, end);
285         __reserve_early(start, end, name, 0);
286 }
287
288 void __init reserve_early_without_check(u64 start, u64 end, char *name)
289 {
290         struct early_res *r;
291
292         if (start >= end)
293                 return;
294
295         __check_and_double_early_res(start, end);
296
297         r = &early_res[early_res_count];
298
299         r->start = start;
300         r->end = end;
301         r->overlap_ok = 0;
302         if (name)
303                 strncpy(r->name, name, sizeof(r->name) - 1);
304         early_res_count++;
305 }
306
307 void __init free_early(u64 start, u64 end)
308 {
309         struct early_res *r;
310         int i;
311
312         i = find_overlapped_early(start, end);
313         r = &early_res[i];
314         if (i >= max_early_res || r->end != end || r->start != start)
315                 panic("free_early on not reserved area: %llx-%llx!",
316                          start, end - 1);
317
318         drop_range(i);
319 }
320
321 void __init free_early_partial(u64 start, u64 end)
322 {
323         struct early_res *r;
324         int i;
325
326 try_next:
327         i = find_overlapped_early(start, end);
328         if (i >= max_early_res)
329                 return;
330
331         r = &early_res[i];
332         /* hole ? */
333         if (r->end >= end && r->start <= start) {
334                 drop_range_partial(i, start, end);
335                 return;
336         }
337
338         drop_range_partial(i, start, end);
339         goto try_next;
340 }
341
342 #ifdef CONFIG_NO_BOOTMEM
343 static void __init subtract_early_res(struct range *range, int az)
344 {
345         int i, count;
346         u64 final_start, final_end;
347         int idx = 0;
348
349         count  = 0;
350         for (i = 0; i < max_early_res && early_res[i].end; i++)
351                 count++;
352
353         /* need to skip first one ?*/
354         if (early_res != early_res_x)
355                 idx = 1;
356
357 #define DEBUG_PRINT_EARLY_RES 1
358
359 #if DEBUG_PRINT_EARLY_RES
360         printk(KERN_INFO "Subtract (%d early reservations)\n", count);
361 #endif
362         for (i = idx; i < count; i++) {
363                 struct early_res *r = &early_res[i];
364 #if DEBUG_PRINT_EARLY_RES
365                 printk(KERN_INFO "  #%d [%010llx - %010llx] %15s\n", i,
366                         r->start, r->end, r->name);
367 #endif
368                 final_start = PFN_DOWN(r->start);
369                 final_end = PFN_UP(r->end);
370                 if (final_start >= final_end)
371                         continue;
372                 subtract_range(range, az, final_start, final_end);
373         }
374
375 }
376
377 int __init get_free_all_memory_range(struct range **rangep, int nodeid)
378 {
379         int i, count;
380         u64 start = 0, end;
381         u64 size;
382         u64 mem;
383         struct range *range;
384         int nr_range;
385
386         count  = 0;
387         for (i = 0; i < max_early_res && early_res[i].end; i++)
388                 count++;
389
390         count *= 2;
391
392         size = sizeof(struct range) * count;
393         end = get_max_mapped();
394 #ifdef MAX_DMA32_PFN
395         if (end > (MAX_DMA32_PFN << PAGE_SHIFT))
396                 start = MAX_DMA32_PFN << PAGE_SHIFT;
397 #endif
398         mem = find_fw_memmap_area(start, end, size, sizeof(struct range));
399         if (mem == -1ULL)
400                 panic("can not find more space for range free");
401
402         range = __va(mem);
403         /* use early_node_map[] and early_res to get range array at first */
404         memset(range, 0, size);
405         nr_range = 0;
406
407         /* need to go over early_node_map to find out good range for node */
408         nr_range = add_from_early_node_map(range, count, nr_range, nodeid);
409 #ifdef CONFIG_X86_32
410         subtract_range(range, count, max_low_pfn, -1ULL);
411 #endif
412         subtract_early_res(range, count);
413         nr_range = clean_sort_range(range, count);
414
415         /* need to clear it ? */
416         if (nodeid == MAX_NUMNODES) {
417                 memset(&early_res[0], 0,
418                          sizeof(struct early_res) * max_early_res);
419                 early_res = NULL;
420                 max_early_res = 0;
421         }
422
423         *rangep = range;
424         return nr_range;
425 }
426 #else
427 void __init early_res_to_bootmem(u64 start, u64 end)
428 {
429         int i, count;
430         u64 final_start, final_end;
431         int idx = 0;
432
433         count  = 0;
434         for (i = 0; i < max_early_res && early_res[i].end; i++)
435                 count++;
436
437         /* need to skip first one ?*/
438         if (early_res != early_res_x)
439                 idx = 1;
440
441         printk(KERN_INFO "(%d/%d early reservations) ==> bootmem [%010llx - %010llx]\n",
442                          count - idx, max_early_res, start, end);
443         for (i = idx; i < count; i++) {
444                 struct early_res *r = &early_res[i];
445                 printk(KERN_INFO "  #%d [%010llx - %010llx] %16s", i,
446                         r->start, r->end, r->name);
447                 final_start = max(start, r->start);
448                 final_end = min(end, r->end);
449                 if (final_start >= final_end) {
450                         printk(KERN_CONT "\n");
451                         continue;
452                 }
453                 printk(KERN_CONT " ==> [%010llx - %010llx]\n",
454                         final_start, final_end);
455                 reserve_bootmem_generic(final_start, final_end - final_start,
456                                 BOOTMEM_DEFAULT);
457         }
458         /* clear them */
459         memset(&early_res[0], 0, sizeof(struct early_res) * max_early_res);
460         early_res = NULL;
461         max_early_res = 0;
462         early_res_count = 0;
463 }
464 #endif
465
466 /* Check for already reserved areas */
467 static inline int __init bad_addr(u64 *addrp, u64 size, u64 align)
468 {
469         int i;
470         u64 addr = *addrp;
471         int changed = 0;
472         struct early_res *r;
473 again:
474         i = find_overlapped_early(addr, addr + size);
475         r = &early_res[i];
476         if (i < max_early_res && r->end) {
477                 *addrp = addr = round_up(r->end, align);
478                 changed = 1;
479                 goto again;
480         }
481         return changed;
482 }
483
484 /* Check for already reserved areas */
485 static inline int __init bad_addr_size(u64 *addrp, u64 *sizep, u64 align)
486 {
487         int i;
488         u64 addr = *addrp, last;
489         u64 size = *sizep;
490         int changed = 0;
491 again:
492         last = addr + size;
493         for (i = 0; i < max_early_res && early_res[i].end; i++) {
494                 struct early_res *r = &early_res[i];
495                 if (last > r->start && addr < r->start) {
496                         size = r->start - addr;
497                         changed = 1;
498                         goto again;
499                 }
500                 if (last > r->end && addr < r->end) {
501                         addr = round_up(r->end, align);
502                         size = last - addr;
503                         changed = 1;
504                         goto again;
505                 }
506                 if (last <= r->end && addr >= r->start) {
507                         (*sizep)++;
508                         return 0;
509                 }
510         }
511         if (changed) {
512                 *addrp = addr;
513                 *sizep = size;
514         }
515         return changed;
516 }
517
518 /*
519  * Find a free area with specified alignment in a specific range.
520  * only with the area.between start to end is active range from early_node_map
521  * so they are good as RAM
522  */
523 u64 __init find_early_area(u64 ei_start, u64 ei_last, u64 start, u64 end,
524                          u64 size, u64 align)
525 {
526         u64 addr, last;
527
528         addr = round_up(ei_start, align);
529         if (addr < start)
530                 addr = round_up(start, align);
531         if (addr >= ei_last)
532                 goto out;
533         while (bad_addr(&addr, size, align) && addr+size <= ei_last)
534                 ;
535         last = addr + size;
536         if (last > ei_last)
537                 goto out;
538         if (last > end)
539                 goto out;
540
541         return addr;
542
543 out:
544         return -1ULL;
545 }
546
547 u64 __init find_early_area_size(u64 ei_start, u64 ei_last, u64 start,
548                          u64 *sizep, u64 align)
549 {
550         u64 addr, last;
551
552         addr = round_up(ei_start, align);
553         if (addr < start)
554                 addr = round_up(start, align);
555         if (addr >= ei_last)
556                 goto out;
557         *sizep = ei_last - addr;
558         while (bad_addr_size(&addr, sizep, align) && addr + *sizep <= ei_last)
559                 ;
560         last = addr + *sizep;
561         if (last > ei_last)
562                 goto out;
563
564         return addr;
565
566 out:
567         return -1ULL;
568 }