| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563 |
- /* 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"
- #include "mtrr.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 4 GB
- * (MM_HIGH_LIMIT). It is not in BSS (4 GB needs 128 KB, and the kernel
- * image must end below 0x90000): mm_init() places it in the first lowmem
- * 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.
- *
- * Two zones share the bitmap: lowmem [0, MM_MAX_PHYS) is identity-mapped
- * and serves every kernel allocation; highmem above it is handed out only
- * by mm_alloc_user_page() for ring-3 pages, which the kernel reaches
- * through kmap() (paging.c). Each zone keeps its own first-free hint. */
- #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 low_words; /* bitmap words below MM_MAX_PHYS */
- static unsigned int first_free; /* lowest lowmem word with a free bit */
- static unsigned int first_free_high; /* same for highmem (>= low_words) */
- unsigned int mm_uncached_high_mb, mm_uncached_low_mb;
- 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) {
- 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_HIGH_LIMIT)
- end = MM_HIGH_LIMIT;
- 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;
- low_words = MM_MAX_PHYS / (32u * PAGE_SIZE);
- if (low_words > bitmap_words)
- low_words = bitmap_words;
- /* 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);
- /* RAM the firmware's MTRRs leave uncached. A BIOS with too few
- * variable ranges for a 3-4 GB board (the ION) can leave part of the
- * RAM above the PCI hole UC; ring-3 heaps come from highmem first, so
- * a page load's JavaScript then ran 100x slower. Such highmem is not
- * handed out at all (lowmem still serves user pages); uncached lowmem
- * is only reported, the kernel cannot do without it. */
- {
- unsigned long long a, lim = bitmap_limit();
- unsigned int high_uc = 0, low_uc = 0, w;
- if (lim > MM_HIGH_LIMIT)
- lim = MM_HIGH_LIMIT;
- for (a = 0x100000ull; a < lim; a += 0x100000ull) {
- unsigned int w0 = (unsigned int)(a >> 17);
- int any = 0, t;
- for (w = w0; w < w0 + 8 && w < bitmap_words; w++)
- if (bitmap[w] != 0xFFFFFFFFu)
- any = 1;
- if (!any)
- continue; /* no free RAM in this MB */
- t = mtrr_mem_type((unsigned int)a);
- if (t < 0)
- break; /* no usable MTRRs */
- if (t == 6)
- continue; /* write-back */
- if (a >= MM_MAX_PHYS) {
- mark_used(a, 0x100000ull);
- high_uc++;
- } else {
- low_uc++;
- }
- }
- if (high_uc || low_uc) {
- serial_puts(SERIAL_COM1, "mm: RAM not write-back by MTRR: ");
- serial_putdec(SERIAL_COM1, high_uc);
- serial_puts(SERIAL_COM1, " MB highmem (not used), ");
- serial_putdec(SERIAL_COM1, low_uc);
- serial_puts(SERIAL_COM1, " MB lowmem\n");
- }
- mm_uncached_high_mb = high_uc;
- mm_uncached_low_mb = low_uc;
- }
- /* 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;
- first_free_high = low_words;
- 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, ", highmem free ");
- serial_putdec(SERIAL_COM1, mm_free_high_pages() / 256u);
- serial_puts(SERIAL_COM1, " MB\n");
- }
- /* Scan words [from, to) for the lowest free bit; claim it. */
- static unsigned int claim_bit(unsigned int from, unsigned int to,
- unsigned int *hint)
- {
- unsigned int w;
- for (w = from; w < to; w++) {
- unsigned int word = bitmap[w];
- if (word != 0xFFFFFFFFu) {
- unsigned int i = (unsigned int)__builtin_ctz(~word);
- bitmap[w] = word | (1u << i);
- free_pages--;
- *hint = w;
- return (w * 32u + i) * PAGE_SIZE;
- }
- }
- *hint = to;
- return 0;
- }
- /* 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 flags = irq_disable_save();
- unsigned int pa = claim_bit(first_free, low_words, &first_free);
- irq_restore(flags);
- return pa;
- }
- /* A frame for a ring-3 mapping: highmem first, lowmem when highmem is
- * exhausted (or absent). The result may be above MM_MAX_PHYS, so the
- * kernel must not dereference it directly; use kmap(). */
- unsigned int mm_alloc_user_page(void)
- {
- unsigned int flags = irq_disable_save();
- unsigned int pa = claim_bit(first_free_high, bitmap_words,
- &first_free_high);
- if (!pa)
- pa = claim_bit(first_free, low_words, &first_free);
- irq_restore(flags);
- return pa;
- }
- unsigned int mm_free_high_pages(void)
- {
- unsigned int w, n = 0;
- for (w = low_words; w < bitmap_words; w++) {
- unsigned int x = ~bitmap[w];
- while (x) {
- x &= x - 1;
- n++;
- }
- }
- return n;
- }
- /* Lowest run of n free lowmem 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 < low_words * 32u) {
- 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 < low_words) {
- if (idx / 32u < first_free)
- first_free = idx / 32u;
- } else if (idx / 32u < first_free_high) {
- first_free_high = 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");
- }
|