mm.c 12 KB

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