The frame allocator is responsible for allocating physical memory in units of 64KiB. 64KiB frames are used rather than 4KiB frames because individual objects should not be stored in frames. Rather, a process' heap should be allocated with these frames, and the GC should be run within them.
Because of this limited use-case, the frame allocator doesn't need to avoid fragmentation (since frames can't be fragmented), so it can be a simple singly-linked-list of frames, where the address of the next frame is the first double-word of the frame. This additionally makes allocating a frame atomically in only a few instructions quite practical.
The page allocator is responsible for allocating virtual memory in units whose sizes are multiples of 64KiB. It sits directly on top of the frame allocator, and should almost always be used as the interface to memory allocation.
No auxiliary structures are needed by the page allocator besides the page tables themselves.
The allocator always allocates into high memory; low memory remains identity mapped. (Initially, just the kernel itself is paged into low memory; however, the page fault handler will map in the rest as it is used.) A guard page will always be allocated between two allocations.
Currently, running out of address space is a kernel panic, and address space will not be reused. In the future, this will be resolved in a GC-like manner: the (user-allocatable) virtual address space will be split into two halves, and whenever one half runs out of memory, allocations will be moved to the other half. (This is why the GC ABI requires support for moving a process' high-memory allocations.)