/* Physical memory manager: parse the E820 map and hand out 4 KB pages. */ #include "mm.h" #include "bootinfo.h" #include "serial.h" #include "vga.h" /* One bit per 4 KB page; bit set = in use. * * The bitmap covers [0, top of RAM) rounded up to 128 KB, at most * MM_MAX_PHYS. It is not in BSS (1 GB needs 32 KB, and the kernel image * must end below 0x90000): mm_init() places it in the first E820 RAM run * above the VGA-shadow reserve that avoids the boot rootfs pack and the * LFB, then marks those pages used. The small static array is only the * fallback when no E820 map exists (the 16 MB guess) or nothing fits. */ #define MM_FALLBACK_PHYS 0x1000000u /* 16 MB */ #define MM_FALLBACK_WORDS (MM_FALLBACK_PHYS / PAGE_SIZE / 32) #define MM_PLACE_MIN (MM_SHADOW_BASE + MM_SHADOW_RESERVE) static unsigned int fallback_bitmap[MM_FALLBACK_WORDS]; static unsigned int *bitmap = fallback_bitmap; static unsigned int bitmap_words; /* words covered by the bitmap */ static unsigned int bitmap_bits; /* bitmap_words * 32 */ static unsigned int bitmap_bytes; /* page-rounded size when placed in RAM */ static unsigned int first_free; /* lowest word that may hold a free bit */ static unsigned int free_pages; static unsigned int total_ram_kb; /* ---- bitmap helpers ---- */ static inline void bit_set(unsigned int idx) { bitmap[idx / 32] |= (1u << (idx % 32)); } static inline void bit_clear(unsigned int idx) { bitmap[idx / 32] &= ~(1u << (idx % 32)); } static inline int bit_test(unsigned int idx) { return (bitmap[idx / 32] >> (idx % 32)) & 1; } /* ---- interrupt flag save/restore (allocator is not IRQ-safe) ---- */ static inline unsigned int irq_disable_save(void) { unsigned int flags; __asm__ volatile ("pushfl; popl %0; cli" : "=r"(flags)); return flags; } static inline void irq_restore(unsigned int flags) { __asm__ volatile ("pushl %0; popfl" : : "r"(flags)); } static unsigned long long bitmap_limit(void) { return (unsigned long long)bitmap_bits * PAGE_SIZE; } /* Mark a physical byte range [base, base+len) as used in the bitmap. */ static void mark_used(unsigned long long base, unsigned long long len) { unsigned long long end = base + len; unsigned long long lim = bitmap_limit(); unsigned int p0, p1, p; if (base >= lim) return; if (end > lim) end = lim; p0 = (unsigned int)(base >> 12); p1 = (unsigned int)((end + PAGE_SIZE - 1) >> 12); for (p = p0; p < p1; p++) bit_set(p); } /* Mark a physical byte range [base, base+len) as free (usable RAM). */ static void mark_free(unsigned long long base, unsigned long long len) { unsigned long long end = base + len; unsigned long long lim = bitmap_limit(); unsigned int p0, p1, p; if (base >= lim) return; if (end > lim) end = lim; p0 = (unsigned int)((base + PAGE_SIZE - 1) >> 12); p1 = (unsigned int)(end >> 12); for (p = p0; p < p1; p++) bit_clear(p); } static int e820_valid(const struct e820_map *map) { return map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES; } static int overlaps(unsigned long long a0, unsigned long long a1, unsigned long long b0, unsigned long long b1) { return b1 > b0 && a0 < b1 && b0 < a1; } /* Boot-time regions that must stay out of the allocator (and out of the * bitmap's own placement): the LFB when a BIOS put it in RAM, and the * rootfs pack until ramfs_init() has copied it. */ static unsigned long long lfb_lo, lfb_hi, pack_lo, pack_hi; static void find_boot_regions(void) { const volatile struct vga_boot_fb_info *fb = VGA_BOOT_FB; unsigned int sz, pa, ps; __asm__ volatile ("" : "+r"(fb)); lfb_lo = lfb_hi = 0; sz = (unsigned int)fb->pitch * fb->height; if (!sz) sz = 0x1000000; if (fb->valid && fb->lfb_base && fb->lfb_base < MM_MAX_PHYS) { lfb_lo = fb->lfb_base; lfb_hi = lfb_lo + sz; } pack_lo = pack_hi = 0; pa = bootinfo_pack_addr(); ps = bootinfo_pack_size(); if (pa >= MM_RESERVE_LOW && pa < MM_MAX_PHYS && ps != 0 && ps <= MM_MAX_PHYS && pa + ps > pa && pa + ps <= MM_MAX_PHYS) { pack_lo = pa; pack_hi = (unsigned long long)pa + ps; } } static unsigned long long page_up(unsigned long long a) { return (a + PAGE_SIZE - 1) & ~(unsigned long long)(PAGE_SIZE - 1); } /* First E820 RAM address >= MM_PLACE_MIN where `bytes` fit without * touching the pack or the LFB; 0 if there is none. */ static unsigned int place_bitmap(const struct e820_map *map, unsigned int bytes) { unsigned int i; for (i = 0; i < map->count; i++) { const struct e820_entry *e = &map->entry[i]; unsigned long long lo, hi, c; if (e->type != E820_RAM || e->length == 0) continue; lo = page_up(e->base); hi = e->base + e->length; if (hi > MM_MAX_PHYS) hi = MM_MAX_PHYS; c = lo < MM_PLACE_MIN ? MM_PLACE_MIN : lo; while (c + bytes <= hi) { if (overlaps(c, c + bytes, pack_lo, pack_hi)) c = page_up(pack_hi); else if (overlaps(c, c + bytes, lfb_lo, lfb_hi)) c = page_up(lfb_hi); else return (unsigned int)c; } } return 0; } /* Mark the whole bitmap as used, then walk the E820 map and free RAM. */ void mm_init(void) { const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR; unsigned long long top = 0; unsigned int i, n, at = 0; find_boot_regions(); total_ram_kb = 0; /* Size the bitmap to the highest RAM address below the ceiling. */ if (e820_valid(map)) { n = map->count; for (i = 0; i < n; i++) { const struct e820_entry *e = &map->entry[i]; unsigned long long end = e->base + e->length; if (e->type != E820_RAM || e->length == 0) continue; if (end > MM_MAX_PHYS) end = MM_MAX_PHYS; if (end > e->base) { total_ram_kb += (unsigned int)((end - e->base) >> 10); if (end > top) top = end; } } } if (top == 0) top = MM_FALLBACK_PHYS; bitmap_words = (unsigned int)((top + 32ull * PAGE_SIZE - 1) / (32ull * PAGE_SIZE)); bitmap = fallback_bitmap; bitmap_bytes = 0; if (bitmap_words > MM_FALLBACK_WORDS) { unsigned int bytes = (bitmap_words * 4u + PAGE_SIZE - 1) & ~(PAGE_SIZE - 1u); at = place_bitmap(map, bytes); if (at) { bitmap = (unsigned int *)at; bitmap_bytes = bytes; } else { serial_puts(SERIAL_COM1, "mm: no room for the frame bitmap, using 16 MB\n"); bitmap_words = MM_FALLBACK_WORDS; } } bitmap_bits = bitmap_words * 32u; /* Everything starts in-use. */ for (i = 0; i < bitmap_words; i++) bitmap[i] = 0xFFFFFFFFu; if (e820_valid(map)) { n = map->count; for (i = 0; i < n; i++) { const struct e820_entry *e = &map->entry[i]; if (e->type == E820_RAM && e->length != 0) mark_free(e->base, e->length); } } else { /* No E820 map (very old BIOS, or first kexec onto an old build): * assume 16 MB of RAM from 1 MB up. The process-stack fallback * pool keeps the system bootable if this guess is wrong. */ mark_free(0x100000ULL, 0x1000000ULL - 0x100000ULL); total_ram_kb = (0x1000000ULL - 0x100000ULL) >> 10; /* 15 MB */ } /* Re-reserve what the kernel already owns. */ mark_used(0, MM_RESERVE_LOW); mark_used(MM_SHADOW_BASE, MM_SHADOW_RESERVE); /* The VBE LFB is normally high MMIO, but a BIOS may place it inside * low RAM. Never hand framebuffer pages to the allocator: the boot * console draws into the LFB, so an allocated page directory there * would be overwritten by its own progress line. */ if (lfb_hi > lfb_lo) mark_used(lfb_lo, lfb_hi - lfb_lo); /* The boot path copied the command-pack rootfs into high RAM before * the kernel ran. Keep it away from the allocator until ramfs_init() * has taken its own copy. */ if (pack_hi > pack_lo) mark_used(pack_lo, pack_hi - pack_lo); /* The bitmap's own pages. */ if (bitmap_bytes) mark_used((unsigned int)bitmap, bitmap_bytes); /* Count free pages. */ free_pages = 0; for (i = 0; i < bitmap_words; i++) { unsigned int w = ~bitmap[i]; while (w) { w &= w - 1; free_pages++; } } first_free = 0; serial_puts(SERIAL_COM1, "mm: bitmap "); serial_putdec(SERIAL_COM1, bitmap_words * 4u); serial_puts(SERIAL_COM1, " B covers "); serial_putdec(SERIAL_COM1, bitmap_bits / 256u); serial_puts(SERIAL_COM1, " MB at "); serial_puthex(SERIAL_COM1, (unsigned int)bitmap); serial_puts(SERIAL_COM1, "\n"); } /* Lowest free page. Words below first_free are known to be full, so a * steady stream of allocations does not rescan the low, busy part. */ unsigned int mm_alloc_page(void) { unsigned int w; unsigned int flags = irq_disable_save(); for (w = first_free; w < bitmap_words; w++) { unsigned int word = bitmap[w]; if (word != 0xFFFFFFFFu) { unsigned int i = (unsigned int)__builtin_ctz(~word); bitmap[w] = word | (1u << i); free_pages--; first_free = w; irq_restore(flags); return (w * 32u + i) * PAGE_SIZE; } } first_free = bitmap_words; irq_restore(flags); return 0; } /* Lowest run of n free pages. Full words break a run and empty words * extend it 32 pages at a time; only mixed words are walked bit by bit. */ unsigned int mm_alloc_pages(unsigned int n) { unsigned int start = 0, run = 0; unsigned int p; unsigned int flags; if (n == 0) return 0; flags = irq_disable_save(); p = first_free * 32u; while (p < bitmap_bits) { if ((p & 31u) == 0) { unsigned int word = bitmap[p / 32u]; if (word == 0xFFFFFFFFu) { run = 0; p += 32; continue; } if (word == 0) { if (run == 0) start = p; run += 32; p += 32; if (run >= n) break; continue; } } if (!bit_test(p)) { if (run == 0) start = p; run++; p++; if (run == n) break; } else { run = 0; p++; } } if (run >= n) { unsigned int i; for (i = start; i < start + n; i++) bit_set(i); free_pages -= n; irq_restore(flags); return start * PAGE_SIZE; } irq_restore(flags); return 0; } void mm_free_page(unsigned int addr) { unsigned int idx = addr / PAGE_SIZE; unsigned int flags; if (addr == 0 || idx >= bitmap_bits) return; flags = irq_disable_save(); if (bit_test(idx)) { bit_clear(idx); free_pages++; if (idx / 32u < first_free) first_free = idx / 32u; } irq_restore(flags); } /* Return a boot-time reservation (the rootfs pack region) to the allocator. * Low memory and the VGA shadow reserve always stay reserved. */ void mm_free_range(unsigned int base, unsigned int size) { unsigned int end, p; if (base == 0 || size == 0) return; base &= ~(PAGE_SIZE - 1u); if (base + size < base) return; end = (base + size + PAGE_SIZE - 1u) & ~(PAGE_SIZE - 1u); if (base < MM_SHADOW_BASE + MM_SHADOW_RESERVE) return; for (p = base; p < end; p += PAGE_SIZE) mm_free_page(p); } unsigned int mm_free_pages(void) { return free_pages; } unsigned int mm_total_ram_kb(void) { return total_ram_kb; } unsigned int mm_e820_count(void) { const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR; if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES) return map->count; return 0; } const struct e820_entry *mm_e820_entry(unsigned int i) { const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR; if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES && i < map->count) return &map->entry[i]; return 0; } void mm_dump(void) { const struct e820_map *map = (const struct e820_map *)E820_MAP_ADDR; unsigned int i; serial_puts(SERIAL_COM1, "mm: E820 "); if (map->magic == E820_MAGIC && map->count <= E820_MAX_ENTRIES) { serial_putdec(SERIAL_COM1, map->count); serial_puts(SERIAL_COM1, " entries, "); for (i = 0; i < map->count; i++) { serial_puts(SERIAL_COM1, "\n ["); serial_puthex(SERIAL_COM1, (unsigned int)map->entry[i].base); serial_puts(SERIAL_COM1, " +"); serial_puthex(SERIAL_COM1, (unsigned int)map->entry[i].length); serial_puts(SERIAL_COM1, "] type "); serial_putdec(SERIAL_COM1, map->entry[i].type); } } else { serial_puts(SERIAL_COM1, "unavailable (fallback 16 MB)"); } serial_puts(SERIAL_COM1, "\nmm: total "); serial_putdec(SERIAL_COM1, total_ram_kb); serial_puts(SERIAL_COM1, " KB, free "); serial_putdec(SERIAL_COM1, free_pages * (PAGE_SIZE / 1024)); serial_puts(SERIAL_COM1, " KB\n"); }