/* 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"); }