Parse the BIOS Memory Map (E820)

Topic Overview

E820 Memory Map

Firmware INT 15h AX=E820 returns address ranges and types (usable, reserved, ACPI). Kernels must not place page tables in reserved regions including MMIO holes.

Entry Types

Common ACPI types:

• Type 1: usable RAM
• Type 2: reserved
• Type 3: ACPI reclaimable

For example, a machine might report usable 0x00000000-0x0009FFFF and 0x00100000-0x7FEFFFFF with a hole for VGA framebuffer.

Why This Matters in Production

The E820 memory map you're parsing here is exactly what GRUB passes to every multiboot-compliant kernel, and it's the only way an OS learns which physical addresses are real RAM versus reserved for the VGA buffer, ACPI tables, or memory-mapped PCI devices. Allocating a page from a region you mistakenly marked usable is how kernels corrupt firmware data structures or write straight into device registers.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will call the BIOS hook in your bootloader and store an array of regions for the kernel allocator. This exercise requires marking which ranges are safe for buddy allocation.

Your Task

At boot, the BIOS describes physical memory with E820 entries (base, length, type). The raw list can be unsorted and can overlap, so the kernel first sanitises it into a clean map. It then reports how much RAM it has and hands out early allocations, which are page-aligned blocks above 1 MiB. Build that pipeline.

Input

cCopy
Loading…

Types: 1 usable, 2 reserved, 3 ACPI reclaimable, 4 ACPI NVS, 5 bad memory. Allocated blocks count as a sixth kind, allocated, which ranks above all of them.

Rules

• Sanitising. Where entries overlap, the higher-ranked kind wins (allocated > 5 > 4 > 3 > 2 > 1). Holes that no entry covers are left out. Neighbouring pieces of the same kind merge, and the map is sorted by address. The map is rebuilt after every entry and every successful alloc.
• A zero-length entry prints entry 0xBASE: zero length, ignored. Any other type prints entry 0xBASE: unknown type T, treated as reserved and is stored as type 2.
• alloc. Round SIZE up to a multiple of 4096. Scan the usable regions in address order. Start at the region's base, or at 0x100000 if the base is lower, then round up to 4 KiB. Take the first region where the block fits, and carve the block from that position. A size of zero prints alloc 0x0: invalid size. If no region fits, print alloc 0xSIZE: out of memory.
• summary. Usable bytes, split at 4 GiB (a region that crosses 4 GiB is split). The largest usable region. Types 2-5 together count as "not usable". Allocated bytes. Page frames are the whole 4 KiB pages inside each usable region, after rounding the base up and the end down. The highest usable address is the last byte of the last usable region, or 0x0 if there is none.
• Sizes print as N KiB if they divide by 1024, otherwise N B.

Output

cCopy
Loading…

Map lines show an inclusive end, 16 hex digits, and the type name padded to 16 characters.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Sanitise with a boundary sweep: sort all start and end points, and give each gap between consecutive points the highest-ranked type that covers it.
2. Record allocations as entries in the map, so a later alloc never returns the same memory twice.

Hidden tests cover allocations that skip low memory, round up odd sizes, run out of memory or ask for zero bytes, page frames in regions that are not page-aligned, memory above and across 4 GiB, bad memory inside a usable range, unknown types, and zero-length entries.