1/* 2 * linux/mm/bootmem.c 3 * 4 * Copyright (C) 1999 Ingo Molnar 5 * Discontiguous memory support, Kanoj Sarcar, SGI, Nov 1999 6 * 7 * simple boot-time physical memory area allocator and 8 * free memory collector. It's used to deal with reserved 9 * system memory and memory holes as well. 10 */ 11 12#include <linux/mm.h> 13#include <linux/kernel_stat.h> 14#include <linux/swap.h> 15#include <linux/swapctl.h> 16#include <linux/interrupt.h> 17#include <linux/init.h> 18#include <linux/bootmem.h> 19#include <linux/mmzone.h> 20#include <asm/dma.h> 21#include <asm/io.h> 22 23/* 24 * Access to this subsystem has to be serialized externally. (this is 25 * true for the boot process anyway) 26 */ 27unsigned long max_low_pfn; 28unsigned long min_low_pfn; 29unsigned long max_pfn; 30 31/* return the number of _pages_ that will be allocated for the boot bitmap */ 32unsigned long __init bootmem_bootmap_pages (unsigned long pages) 33{ 34 unsigned long mapsize; 35 36 mapsize = (pages+7)/8; 37 mapsize = (mapsize + ~PAGE_MASK) & PAGE_MASK; 38 mapsize >>= PAGE_SHIFT; 39 40 return mapsize; 41} 42 43/* 44 * Called once to set up the allocator itself. 45 */ 46static unsigned long __init init_bootmem_core (pg_data_t *pgdat, 47 unsigned long mapstart, unsigned long start, unsigned long end) 48{ 49 bootmem_data_t *bdata = pgdat->bdata; 50 unsigned long mapsize = ((end - start)+7)/8; 51 52 pgdat->node_next = pgdat_list; 53 pgdat_list = pgdat; 54 55 mapsize = (mapsize + (sizeof(long) - 1UL)) & ~(sizeof(long) - 1UL); 56 bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT); 57 bdata->node_boot_start = (start << PAGE_SHIFT); 58 bdata->node_low_pfn = end; 59 60#if !defined(CONFIG_HWSIM) || defined(CONFIG_HWSIM_ZMEM) 61 /* 62 * Initially all pages are reserved - setup_arch() has to 63 * register free RAM areas explicitly. 64 */ 65 memset(bdata->node_bootmem_map, 0xff, mapsize); 66#endif 67 68 return mapsize; 69} 70 71/* 72 * Marks a particular physical memory range as unallocatable. Usable RAM 73 * might be used for boot-time allocations - or it might get added 74 * to the free page pool later on. 75 */ 76static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size) 77{ 78 unsigned long i; 79 /* 80 * round up, partially reserved pages are considered 81 * fully reserved. 82 */ 83 unsigned long sidx = (addr - bdata->node_boot_start)/PAGE_SIZE; 84 unsigned long eidx = (addr + size - bdata->node_boot_start + 85 PAGE_SIZE-1)/PAGE_SIZE; 86 unsigned long end = (addr + size + PAGE_SIZE-1)/PAGE_SIZE; 87 88 if (!size) BUG(); 89 90 if (sidx < 0) 91 BUG(); 92 if (eidx < 0) 93 BUG(); 94 if (sidx >= eidx) 95 BUG(); 96 if ((addr >> PAGE_SHIFT) >= bdata->node_low_pfn) 97 BUG(); 98 if (end > bdata->node_low_pfn) 99 BUG(); 100 for (i = sidx; i < eidx; i++) 101 if (test_and_set_bit(i, bdata->node_bootmem_map)) 102 printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE); 103} 104 105static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr, unsigned long size) 106{ 107 unsigned long i; 108 unsigned long start; 109 /* 110 * round down end of usable mem, partially free pages are 111 * considered reserved. 112 */ 113 unsigned long sidx; 114 unsigned long eidx = (addr + size - bdata->node_boot_start)/PAGE_SIZE; 115 unsigned long end = (addr + size)/PAGE_SIZE; 116 117 if (!size) BUG(); 118 if (end > bdata->node_low_pfn) 119 BUG(); 120 121 /* 122 * Round up the beginning of the address. 123 */ 124 start = (addr + PAGE_SIZE-1) / PAGE_SIZE; 125 sidx = start - (bdata->node_boot_start/PAGE_SIZE); 126 127 for (i = sidx; i < eidx; i++) { 128 if (!test_and_clear_bit(i, bdata->node_bootmem_map)) 129 BUG(); 130 } 131} 132 133/* 134 * We 'merge' subsequent allocations to save space. We might 'lose' 135 * some fraction of a page if allocations cannot be satisfied due to 136 * size constraints on boxes where there is physical RAM space 137 * fragmentation - in these cases * (mostly large memory boxes) this 138 * is not a problem. 139 * 140 * On low memory boxes we get it right in 100% of the cases. 141 */ 142 143/* 144 * alignment has to be a power of 2 value. 145 */ 146static void * __init __alloc_bootmem_core (bootmem_data_t *bdata, 147 unsigned long size, unsigned long align, unsigned long goal) 148{ 149 unsigned long i, start = 0; 150 void *ret; 151 unsigned long offset, remaining_size; 152 unsigned long areasize, preferred, incr; 153 unsigned long eidx = bdata->node_low_pfn - (bdata->node_boot_start >> 154 PAGE_SHIFT); 155 156 if (!size) BUG(); 157 158 if (align & (align-1)) 159 BUG(); 160 161 offset = 0; 162 if (align && 163 (bdata->node_boot_start & (align - 1UL)) != 0) 164 offset = (align - (bdata->node_boot_start & (align - 1UL))); 165 offset >>= PAGE_SHIFT; 166 167 /* 168 * We try to allocate bootmem pages above 'goal' 169 * first, then we try to allocate lower pages. 170 */ 171 if (goal && (goal >= bdata->node_boot_start) && 172 ((goal >> PAGE_SHIFT) < bdata->node_low_pfn)) { 173 preferred = goal - bdata->node_boot_start; 174 } else 175 preferred = 0; 176 177 preferred = ((preferred + align - 1) & ~(align - 1)) >> PAGE_SHIFT; 178 preferred += offset; 179 areasize = (size+PAGE_SIZE-1)/PAGE_SIZE; 180 incr = align >> PAGE_SHIFT ? : 1; 181 182restart_scan: 183 for (i = preferred; i < eidx; i += incr) { 184 unsigned long j; 185 if (test_bit(i, bdata->node_bootmem_map)) 186 continue; 187 for (j = i + 1; j < i + areasize; ++j) { 188 if (j >= eidx) 189 goto fail_block; 190 if (test_bit (j, bdata->node_bootmem_map)) 191 goto fail_block; 192 } 193 start = i; 194 goto found; 195 fail_block:; 196 } 197 if (preferred) { 198 preferred = offset; 199 goto restart_scan; 200 } 201 return NULL; 202found: 203 if (start >= eidx) 204 BUG(); 205 206 /* 207 * Is the next page of the previous allocation-end the start 208 * of this allocation's buffer? If yes then we can 'merge' 209 * the previous partial page with this allocation. 210 */ 211 if (align <= PAGE_SIZE 212 && bdata->last_offset && bdata->last_pos+1 == start) { 213 offset = (bdata->last_offset+align-1) & ~(align-1); 214 if (offset > PAGE_SIZE) 215 BUG(); 216 remaining_size = PAGE_SIZE-offset; 217 if (size < remaining_size) { 218 areasize = 0; 219 // last_pos unchanged 220 bdata->last_offset = offset+size; 221 ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset + 222 bdata->node_boot_start); 223 } else { 224 remaining_size = size - remaining_size; 225 areasize = (remaining_size+PAGE_SIZE-1)/PAGE_SIZE; 226 ret = phys_to_virt(bdata->last_pos*PAGE_SIZE + offset + 227 bdata->node_boot_start); 228 bdata->last_pos = start+areasize-1; 229 bdata->last_offset = remaining_size; 230 } 231 bdata->last_offset &= ~PAGE_MASK; 232 } else { 233 bdata->last_pos = start + areasize - 1; 234 bdata->last_offset = size & ~PAGE_MASK; 235 ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start); 236 } 237 /* 238 * Reserve the area now: 239 */ 240 for (i = start; i < start+areasize; i++) 241 if (test_and_set_bit(i, bdata->node_bootmem_map)) 242 BUG(); 243#ifndef CONFIG_HWSIM 244 memset(ret, 0, size); 245#endif 246 return ret; 247} 248 249static unsigned long __init free_all_bootmem_core(pg_data_t *pgdat) 250{ 251 struct page *page = pgdat->node_mem_map; 252 bootmem_data_t *bdata = pgdat->bdata; 253 unsigned long i, count, total = 0; 254 unsigned long idx; 255 256 if (!bdata->node_bootmem_map) BUG(); 257 258 count = 0; 259 idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT); 260 for (i = 0; i < idx; i++, page++) { 261 if (!test_bit(i, bdata->node_bootmem_map)) { 262 count++; 263 ClearPageReserved(page); 264 set_page_count(page, 1); 265 __free_page(page); 266 } 267 } 268 total += count; 269 270 /* 271 * Now free the allocator bitmap itself, it's not 272 * needed anymore: 273 */ 274 page = virt_to_page(bdata->node_bootmem_map); 275 count = 0; 276 for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) { 277 count++; 278 ClearPageReserved(page); 279 set_page_count(page, 1); 280 __free_page(page); 281 } 282 total += count; 283 bdata->node_bootmem_map = NULL; 284 285 return total; 286} 287 288unsigned long __init init_bootmem_node (pg_data_t *pgdat, unsigned long freepfn, unsigned long startpfn, unsigned long endpfn) 289{ 290 return(init_bootmem_core(pgdat, freepfn, startpfn, endpfn)); 291} 292 293void __init reserve_bootmem_node (pg_data_t *pgdat, unsigned long physaddr, unsigned long size) 294{ 295 reserve_bootmem_core(pgdat->bdata, physaddr, size); 296} 297 298void __init free_bootmem_node (pg_data_t *pgdat, unsigned long physaddr, unsigned long size) 299{ 300 return(free_bootmem_core(pgdat->bdata, physaddr, size)); 301} 302 303unsigned long __init free_all_bootmem_node (pg_data_t *pgdat) 304{ 305 return(free_all_bootmem_core(pgdat)); 306} 307 308unsigned long __init init_bootmem (unsigned long start, unsigned long pages) 309{ 310 max_low_pfn = pages; 311 min_low_pfn = start; 312 return(init_bootmem_core(&contig_page_data, start, 0, pages)); 313} 314 315void __init reserve_bootmem (unsigned long addr, unsigned long size) 316{ 317 reserve_bootmem_core(contig_page_data.bdata, addr, size); 318} 319 320void __init free_bootmem (unsigned long addr, unsigned long size) 321{ 322 return(free_bootmem_core(contig_page_data.bdata, addr, size)); 323} 324 325unsigned long __init free_all_bootmem (void) 326{ 327 return(free_all_bootmem_core(&contig_page_data)); 328} 329 330void * __init __alloc_bootmem (unsigned long size, unsigned long align, unsigned long goal) 331{ 332 pg_data_t *pgdat; 333 void *ptr; 334 335 for_each_pgdat(pgdat) 336 if ((ptr = __alloc_bootmem_core(pgdat->bdata, size, 337 align, goal))) 338 return(ptr); 339 340 /* 341 * Whoops, we cannot satisfy the allocation request. 342 */ 343 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size); 344 panic("Out of memory"); 345 return NULL; 346} 347 348void * __init __alloc_bootmem_node (pg_data_t *pgdat, unsigned long size, unsigned long align, unsigned long goal) 349{ 350 void *ptr; 351 352 ptr = __alloc_bootmem_core(pgdat->bdata, size, align, goal); 353 if (ptr) 354 return (ptr); 355 356 /* 357 * Whoops, we cannot satisfy the allocation request. 358 */ 359 printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size); 360 panic("Out of memory"); 361 return NULL; 362} 363 364