mm.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563
  1. /* Physical memory manager: parse the E820 map and hand out 4 KB pages. */
  2. #include "mm.h"
  3. #include "bootinfo.h"
  4. #include "serial.h"
  5. #include "vga.h"
  6. #include "mtrr.h"
  7. /* One bit per 4 KB page; bit set = in use.
  8. *
  9. * The bitmap covers [0, top of RAM) rounded up to 128 KB, at most 4 GB
  10. * (MM_HIGH_LIMIT). It is not in BSS (4 GB needs 128 KB, and the kernel
  11. * image must end below 0x90000): mm_init() places it in the first lowmem
  12. * E820 RAM run above the VGA-shadow reserve that avoids the boot rootfs
  13. * pack and the LFB, then marks those pages used. The small static array is
  14. * only the fallback when no E820 map exists (the 16 MB guess) or nothing
  15. * fits.
  16. *
  17. * Two zones share the bitmap: lowmem [0, MM_MAX_PHYS) is identity-mapped
  18. * and serves every kernel allocation; highmem above it is handed out only
  19. * by mm_alloc_user_page() for ring-3 pages, which the kernel reaches
  20. * through kmap() (paging.c). Each zone keeps its own first-free hint. */
  21. #define MM_FALLBACK_PHYS 0x1000000u /* 16 MB */
  22. #define MM_FALLBACK_WORDS (MM_FALLBACK_PHYS / PAGE_SIZE / 32)
  23. #define MM_PLACE_MIN (MM_SHADOW_BASE + MM_SHADOW_RESERVE)
  24. static unsigned int fallback_bitmap[MM_FALLBACK_WORDS];
  25. static unsigned int *bitmap = fallback_bitmap;
  26. static unsigned int bitmap_words; /* words covered by the bitmap */
  27. static unsigned int bitmap_bits; /* bitmap_words * 32 */
  28. static unsigned int bitmap_bytes; /* page-rounded size when placed in RAM */
  29. static unsigned int low_words; /* bitmap words below MM_MAX_PHYS */
  30. static unsigned int first_free; /* lowest lowmem word with a free bit */
  31. static unsigned int first_free_high; /* same for highmem (>= low_words) */
  32. unsigned int mm_uncached_high_mb, mm_uncached_low_mb;
  33. static unsigned int free_pages;
  34. static unsigned int total_ram_kb;
  35. /* ---- bitmap helpers ---- */
  36. static inline void bit_set(unsigned int idx)
  37. {
  38. bitmap[idx / 32] |= (1u << (idx % 32));
  39. }
  40. static inline void bit_clear(unsigned int idx)
  41. {
  42. bitmap[idx / 32] &= ~(1u << (idx % 32));
  43. }
  44. static inline int bit_test(unsigned int idx)
  45. {
  46. return (bitmap[idx / 32] >> (idx % 32)) & 1;
  47. }
  48. /* ---- interrupt flag save/restore (allocator is not IRQ-safe) ---- */
  49. static inline unsigned int irq_disable_save(void)
  50. {
  51. unsigned int flags;
  52. __asm__ volatile ("pushfl; popl %0; cli" : "=r"(flags));
  53. return flags;
  54. }
  55. static inline void irq_restore(unsigned int flags)
  56. {
  57. __asm__ volatile ("pushl %0; popfl" : : "r"(flags));
  58. }
  59. static unsigned long long bitmap_limit(void)
  60. {
  61. return (unsigned long long)bitmap_bits * PAGE_SIZE;
  62. }
  63. /* Mark a physical byte range [base, base+len) as used in the bitmap. */
  64. static void mark_used(unsigned long long base, unsigned long long len)
  65. {
  66. unsigned long long end = base + len;
  67. unsigned long long lim = bitmap_limit();
  68. unsigned int p0, p1, p;
  69. if (base >= lim)
  70. return;
  71. if (end > lim)
  72. end = lim;
  73. p0 = (unsigned int)(base >> 12);
  74. p1 = (unsigned int)((end + PAGE_SIZE - 1) >> 12);
  75. for (p = p0; p < p1; p++)
  76. bit_set(p);
  77. }
  78. /* Mark a physical byte range [base, base+len) as free (usable RAM). */
  79. static void mark_free(unsigned long long base, unsigned long long len)
  80. {
  81. unsigned long long end = base + len;
  82. unsigned long long lim = bitmap_limit();
  83. unsigned int p0, p1, p;
  84. if (base >= lim)
  85. return;
  86. if (end > lim)
  87. end = lim;
  88. p0 = (unsigned int)((base + PAGE_SIZE - 1) >> 12);
  89. p1 = (unsigned int)(end >> 12);
  90. for (p = p0; p < p1; p++)
  91. bit_clear(p);
  92. }
  93. static int e820_valid(const struct e820_map *map)
  94. {
  95. return map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES;
  96. }
  97. static int overlaps(unsigned long long a0, unsigned long long a1,
  98. unsigned long long b0, unsigned long long b1)
  99. {
  100. return b1 > b0 && a0 < b1 && b0 < a1;
  101. }
  102. /* Boot-time regions that must stay out of the allocator (and out of the
  103. * bitmap's own placement): the LFB when a BIOS put it in RAM, and the
  104. * rootfs pack until ramfs_init() has copied it. */
  105. static unsigned long long lfb_lo, lfb_hi, pack_lo, pack_hi;
  106. static void find_boot_regions(void)
  107. {
  108. const volatile struct vga_boot_fb_info *fb = VGA_BOOT_FB;
  109. unsigned int sz, pa, ps;
  110. __asm__ volatile ("" : "+r"(fb));
  111. lfb_lo = lfb_hi = 0;
  112. sz = (unsigned int)fb->pitch * fb->height;
  113. if (!sz)
  114. sz = 0x1000000;
  115. if (fb->valid && fb->lfb_base) {
  116. lfb_lo = fb->lfb_base;
  117. lfb_hi = lfb_lo + sz;
  118. }
  119. pack_lo = pack_hi = 0;
  120. pa = bootinfo_pack_addr();
  121. ps = bootinfo_pack_size();
  122. if (pa >= MM_RESERVE_LOW && pa < MM_MAX_PHYS && ps != 0 &&
  123. ps <= MM_MAX_PHYS && pa + ps > pa && pa + ps <= MM_MAX_PHYS) {
  124. pack_lo = pa;
  125. pack_hi = (unsigned long long)pa + ps;
  126. }
  127. }
  128. static unsigned long long page_up(unsigned long long a)
  129. {
  130. return (a + PAGE_SIZE - 1) & ~(unsigned long long)(PAGE_SIZE - 1);
  131. }
  132. /* First E820 RAM address >= MM_PLACE_MIN where `bytes` fit without
  133. * touching the pack or the LFB; 0 if there is none. */
  134. static unsigned int place_bitmap(const struct e820_map *map,
  135. unsigned int bytes)
  136. {
  137. unsigned int i;
  138. for (i = 0; i < map->count; i++) {
  139. const struct e820_entry *e = &map->entry[i];
  140. unsigned long long lo, hi, c;
  141. if (e->type != E820_RAM || e->length == 0)
  142. continue;
  143. lo = page_up(e->base);
  144. hi = e->base + e->length;
  145. if (hi > MM_MAX_PHYS)
  146. hi = MM_MAX_PHYS;
  147. c = lo < MM_PLACE_MIN ? MM_PLACE_MIN : lo;
  148. while (c + bytes <= hi) {
  149. if (overlaps(c, c + bytes, pack_lo, pack_hi))
  150. c = page_up(pack_hi);
  151. else if (overlaps(c, c + bytes, lfb_lo, lfb_hi))
  152. c = page_up(lfb_hi);
  153. else
  154. return (unsigned int)c;
  155. }
  156. }
  157. return 0;
  158. }
  159. /* Mark the whole bitmap as used, then walk the E820 map and free RAM. */
  160. void mm_init(void)
  161. {
  162. const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR;
  163. unsigned long long top = 0;
  164. unsigned int i, n, at = 0;
  165. find_boot_regions();
  166. total_ram_kb = 0;
  167. /* Size the bitmap to the highest RAM address below the ceiling. */
  168. if (e820_valid(map)) {
  169. n = map->count;
  170. for (i = 0; i < n; i++) {
  171. const struct e820_entry *e = &map->entry[i];
  172. unsigned long long end = e->base + e->length;
  173. if (e->type != E820_RAM || e->length == 0)
  174. continue;
  175. if (end > MM_HIGH_LIMIT)
  176. end = MM_HIGH_LIMIT;
  177. if (end > e->base) {
  178. total_ram_kb +=
  179. (unsigned int)((end - e->base) >> 10);
  180. if (end > top)
  181. top = end;
  182. }
  183. }
  184. }
  185. if (top == 0)
  186. top = MM_FALLBACK_PHYS;
  187. bitmap_words = (unsigned int)((top + 32ull * PAGE_SIZE - 1) /
  188. (32ull * PAGE_SIZE));
  189. bitmap = fallback_bitmap;
  190. bitmap_bytes = 0;
  191. if (bitmap_words > MM_FALLBACK_WORDS) {
  192. unsigned int bytes = (bitmap_words * 4u + PAGE_SIZE - 1) &
  193. ~(PAGE_SIZE - 1u);
  194. at = place_bitmap(map, bytes);
  195. if (at) {
  196. bitmap = (unsigned int *)at;
  197. bitmap_bytes = bytes;
  198. } else {
  199. serial_puts(SERIAL_COM1,
  200. "mm: no room for the frame bitmap, using 16 MB\n");
  201. bitmap_words = MM_FALLBACK_WORDS;
  202. }
  203. }
  204. bitmap_bits = bitmap_words * 32u;
  205. low_words = MM_MAX_PHYS / (32u * PAGE_SIZE);
  206. if (low_words > bitmap_words)
  207. low_words = bitmap_words;
  208. /* Everything starts in-use. */
  209. for (i = 0; i < bitmap_words; i++)
  210. bitmap[i] = 0xFFFFFFFFu;
  211. if (e820_valid(map)) {
  212. n = map->count;
  213. for (i = 0; i < n; i++) {
  214. const struct e820_entry *e = &map->entry[i];
  215. if (e->type == E820_RAM && e->length != 0)
  216. mark_free(e->base, e->length);
  217. }
  218. } else {
  219. /* No E820 map (very old BIOS, or first kexec onto an old build):
  220. * assume 16 MB of RAM from 1 MB up. The process-stack fallback
  221. * pool keeps the system bootable if this guess is wrong. */
  222. mark_free(0x100000ULL, 0x1000000ULL - 0x100000ULL);
  223. total_ram_kb = (0x1000000ULL - 0x100000ULL) >> 10; /* 15 MB */
  224. }
  225. /* Re-reserve what the kernel already owns. */
  226. mark_used(0, MM_RESERVE_LOW);
  227. mark_used(MM_SHADOW_BASE, MM_SHADOW_RESERVE);
  228. /* The VBE LFB is normally high MMIO, but a BIOS may place it inside
  229. * low RAM. Never hand framebuffer pages to the allocator: the boot
  230. * console draws into the LFB, so an allocated page directory there
  231. * would be overwritten by its own progress line. */
  232. if (lfb_hi > lfb_lo)
  233. mark_used(lfb_lo, lfb_hi - lfb_lo);
  234. /* The boot path copied the command-pack rootfs into high RAM before
  235. * the kernel ran. Keep it away from the allocator until ramfs_init()
  236. * has taken its own copy. */
  237. if (pack_hi > pack_lo)
  238. mark_used(pack_lo, pack_hi - pack_lo);
  239. /* The bitmap's own pages. */
  240. if (bitmap_bytes)
  241. mark_used((unsigned int)bitmap, bitmap_bytes);
  242. /* RAM the firmware's MTRRs leave uncached. A BIOS with too few
  243. * variable ranges for a 3-4 GB board (the ION) can leave part of the
  244. * RAM above the PCI hole UC; ring-3 heaps come from highmem first, so
  245. * a page load's JavaScript then ran 100x slower. Such highmem is not
  246. * handed out at all (lowmem still serves user pages); uncached lowmem
  247. * is only reported, the kernel cannot do without it. */
  248. {
  249. unsigned long long a, lim = bitmap_limit();
  250. unsigned int high_uc = 0, low_uc = 0, w;
  251. if (lim > MM_HIGH_LIMIT)
  252. lim = MM_HIGH_LIMIT;
  253. for (a = 0x100000ull; a < lim; a += 0x100000ull) {
  254. unsigned int w0 = (unsigned int)(a >> 17);
  255. int any = 0, t;
  256. for (w = w0; w < w0 + 8 && w < bitmap_words; w++)
  257. if (bitmap[w] != 0xFFFFFFFFu)
  258. any = 1;
  259. if (!any)
  260. continue; /* no free RAM in this MB */
  261. t = mtrr_mem_type((unsigned int)a);
  262. if (t < 0)
  263. break; /* no usable MTRRs */
  264. if (t == 6)
  265. continue; /* write-back */
  266. if (a >= MM_MAX_PHYS) {
  267. mark_used(a, 0x100000ull);
  268. high_uc++;
  269. } else {
  270. low_uc++;
  271. }
  272. }
  273. if (high_uc || low_uc) {
  274. serial_puts(SERIAL_COM1, "mm: RAM not write-back by MTRR: ");
  275. serial_putdec(SERIAL_COM1, high_uc);
  276. serial_puts(SERIAL_COM1, " MB highmem (not used), ");
  277. serial_putdec(SERIAL_COM1, low_uc);
  278. serial_puts(SERIAL_COM1, " MB lowmem\n");
  279. }
  280. mm_uncached_high_mb = high_uc;
  281. mm_uncached_low_mb = low_uc;
  282. }
  283. /* Count free pages. */
  284. free_pages = 0;
  285. for (i = 0; i < bitmap_words; i++) {
  286. unsigned int w = ~bitmap[i];
  287. while (w) {
  288. w &= w - 1;
  289. free_pages++;
  290. }
  291. }
  292. first_free = 0;
  293. first_free_high = low_words;
  294. serial_puts(SERIAL_COM1, "mm: bitmap ");
  295. serial_putdec(SERIAL_COM1, bitmap_words * 4u);
  296. serial_puts(SERIAL_COM1, " B covers ");
  297. serial_putdec(SERIAL_COM1, bitmap_bits / 256u);
  298. serial_puts(SERIAL_COM1, " MB at ");
  299. serial_puthex(SERIAL_COM1, (unsigned int)bitmap);
  300. serial_puts(SERIAL_COM1, ", highmem free ");
  301. serial_putdec(SERIAL_COM1, mm_free_high_pages() / 256u);
  302. serial_puts(SERIAL_COM1, " MB\n");
  303. }
  304. /* Scan words [from, to) for the lowest free bit; claim it. */
  305. static unsigned int claim_bit(unsigned int from, unsigned int to,
  306. unsigned int *hint)
  307. {
  308. unsigned int w;
  309. for (w = from; w < to; w++) {
  310. unsigned int word = bitmap[w];
  311. if (word != 0xFFFFFFFFu) {
  312. unsigned int i = (unsigned int)__builtin_ctz(~word);
  313. bitmap[w] = word | (1u << i);
  314. free_pages--;
  315. *hint = w;
  316. return (w * 32u + i) * PAGE_SIZE;
  317. }
  318. }
  319. *hint = to;
  320. return 0;
  321. }
  322. /* Lowest free page. Words below first_free are known to be full, so a
  323. * steady stream of allocations does not rescan the low, busy part. */
  324. unsigned int mm_alloc_page(void)
  325. {
  326. unsigned int flags = irq_disable_save();
  327. unsigned int pa = claim_bit(first_free, low_words, &first_free);
  328. irq_restore(flags);
  329. return pa;
  330. }
  331. /* A frame for a ring-3 mapping: highmem first, lowmem when highmem is
  332. * exhausted (or absent). The result may be above MM_MAX_PHYS, so the
  333. * kernel must not dereference it directly; use kmap(). */
  334. unsigned int mm_alloc_user_page(void)
  335. {
  336. unsigned int flags = irq_disable_save();
  337. unsigned int pa = claim_bit(first_free_high, bitmap_words,
  338. &first_free_high);
  339. if (!pa)
  340. pa = claim_bit(first_free, low_words, &first_free);
  341. irq_restore(flags);
  342. return pa;
  343. }
  344. unsigned int mm_free_high_pages(void)
  345. {
  346. unsigned int w, n = 0;
  347. for (w = low_words; w < bitmap_words; w++) {
  348. unsigned int x = ~bitmap[w];
  349. while (x) {
  350. x &= x - 1;
  351. n++;
  352. }
  353. }
  354. return n;
  355. }
  356. /* Lowest run of n free lowmem pages. Full words break a run and empty words
  357. * extend it 32 pages at a time; only mixed words are walked bit by bit. */
  358. unsigned int mm_alloc_pages(unsigned int n)
  359. {
  360. unsigned int start = 0, run = 0;
  361. unsigned int p;
  362. unsigned int flags;
  363. if (n == 0)
  364. return 0;
  365. flags = irq_disable_save();
  366. p = first_free * 32u;
  367. while (p < low_words * 32u) {
  368. if ((p & 31u) == 0) {
  369. unsigned int word = bitmap[p / 32u];
  370. if (word == 0xFFFFFFFFu) {
  371. run = 0;
  372. p += 32;
  373. continue;
  374. }
  375. if (word == 0) {
  376. if (run == 0)
  377. start = p;
  378. run += 32;
  379. p += 32;
  380. if (run >= n)
  381. break;
  382. continue;
  383. }
  384. }
  385. if (!bit_test(p)) {
  386. if (run == 0)
  387. start = p;
  388. run++;
  389. p++;
  390. if (run == n)
  391. break;
  392. } else {
  393. run = 0;
  394. p++;
  395. }
  396. }
  397. if (run >= n) {
  398. unsigned int i;
  399. for (i = start; i < start + n; i++)
  400. bit_set(i);
  401. free_pages -= n;
  402. irq_restore(flags);
  403. return start * PAGE_SIZE;
  404. }
  405. irq_restore(flags);
  406. return 0;
  407. }
  408. void mm_free_page(unsigned int addr)
  409. {
  410. unsigned int idx = addr / PAGE_SIZE;
  411. unsigned int flags;
  412. if (addr == 0 || idx >= bitmap_bits)
  413. return;
  414. flags = irq_disable_save();
  415. if (bit_test(idx)) {
  416. bit_clear(idx);
  417. free_pages++;
  418. if (idx / 32u < low_words) {
  419. if (idx / 32u < first_free)
  420. first_free = idx / 32u;
  421. } else if (idx / 32u < first_free_high) {
  422. first_free_high = idx / 32u;
  423. }
  424. }
  425. irq_restore(flags);
  426. }
  427. /* Return a boot-time reservation (the rootfs pack region) to the allocator.
  428. * Low memory and the VGA shadow reserve always stay reserved. */
  429. void mm_free_range(unsigned int base, unsigned int size)
  430. {
  431. unsigned int end, p;
  432. if (base == 0 || size == 0)
  433. return;
  434. base &= ~(PAGE_SIZE - 1u);
  435. if (base + size < base)
  436. return;
  437. end = (base + size + PAGE_SIZE - 1u) & ~(PAGE_SIZE - 1u);
  438. if (base < MM_SHADOW_BASE + MM_SHADOW_RESERVE)
  439. return;
  440. for (p = base; p < end; p += PAGE_SIZE)
  441. mm_free_page(p);
  442. }
  443. unsigned int mm_free_pages(void)
  444. {
  445. return free_pages;
  446. }
  447. unsigned int mm_total_ram_kb(void)
  448. {
  449. return total_ram_kb;
  450. }
  451. unsigned int mm_e820_count(void)
  452. {
  453. const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR;
  454. if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES)
  455. return map->count;
  456. return 0;
  457. }
  458. const struct e820_entry *mm_e820_entry(unsigned int i)
  459. {
  460. const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR;
  461. if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES &&
  462. i < map->count)
  463. return &map->entry[i];
  464. return 0;
  465. }
  466. void mm_dump(void)
  467. {
  468. const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR;
  469. unsigned int i;
  470. serial_puts(SERIAL_COM1, "mm: E820 ");
  471. if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES) {
  472. serial_putdec(SERIAL_COM1, map->count);
  473. serial_puts(SERIAL_COM1, " entries, ");
  474. for (i = 0; i < map->count; i++) {
  475. serial_puts(SERIAL_COM1, "\n [");
  476. serial_puthex(SERIAL_COM1, (unsigned int)map->entry[i].base);
  477. serial_puts(SERIAL_COM1, " +");
  478. serial_puthex(SERIAL_COM1, (unsigned int)map->entry[i].length);
  479. serial_puts(SERIAL_COM1, "] type ");
  480. serial_putdec(SERIAL_COM1, map->entry[i].type);
  481. }
  482. } else {
  483. serial_puts(SERIAL_COM1, "unavailable (fallback 16 MB)");
  484. }
  485. serial_puts(SERIAL_COM1, "\nmm: total ");
  486. serial_putdec(SERIAL_COM1, total_ram_kb);
  487. serial_puts(SERIAL_COM1, " KB, free ");
  488. serial_putdec(SERIAL_COM1, free_pages * (PAGE_SIZE / 1024));
  489. serial_puts(SERIAL_COM1, " KB\n");
  490. }