mm.c 14 KB

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