Frame allocator assumes memory map is in ascending start address order

[tsoutsman]

Currently, LegacyFrameAllocator::allocate_frame_from_descriptor only ever increases self.next_frame. This is problematic, as the memory map descriptors aren't guaranteed to be in ascending start address order (at least for UEFI). If the first descriptor provided by the memory map were also the one with the largest start address, the frame allocator would not allocate from the other descriptors.

Rather than checking whether self.next_frame < self.start_frame in allocate_frame_from_descriptor, we should set self.next_frame to the start address of the descriptor when we find the next suitable descriptor in allocate_frame.

[tsoutsman]

This does however complicate the LegacyFrameAllocator::new_starting_at function. We would have to add a new field that tracks the minimum allowed address.

[phil-opp]

Good catch, thanks a lot for reporting! Your proposed solution sounds good to me. To summarize:

• Add a new min_frame field to LegacyFrameAllocator and set this field in new_starting_at. The next_frame field should be initialized to 0.
• Set self.next_frame to core::cmp::max(descriptor.start(), self.min_frame) when selecting a new descriptor. The assignment should happen just after the Usable check here:

  bootloader/common/src/legacy_memory_region.rs

  Lines 250 to 254 in fffa7ce

  	while let Some(descriptor) = self.memory_map.next() {
  	if descriptor.kind() != MemoryRegionKind::Usable {
  	continue;
  	}
  	if let Some(frame) = self.allocate_frame_from_descriptor(descriptor) {

• Assert that self.next_frame >= start_frame in allocate_frame_from_descriptor (since this should always be the case now) instead of the current comparison:

  bootloader/common/src/legacy_memory_region.rs

  Lines 66 to 69 in fffa7ce

  	// increase self.next_frame to start_frame if smaller
  	if self.next_frame < start_frame {
  	self.next_frame = start_frame;
  	}

• Edit: We also need to change construct_memory_map to mark all descriptors before self.current_descriptor as MemoryRegionKind::Bootloader, instead of just relying on self.next_frame.

I'd be happy to merge a PR that implements the above.

[tsoutsman]

Looking at the code for construct_memory_map, that would need to be changed as well. We would need to compare original and memory_map to see which memory regions have already been consumed by the allocator.

[phil-opp]

Oh yes, good point! I added an additional bullet point about this to the list above.

[Freax13]

Could we just sort the memory map?

[JarlEvanson]

I don't think Iterators are sortable, so we would need to be able to collect the iterator, which would have to be able to be done on the stack, since we don't have access to a heap or dynamic allocation other than that. I don't think it's possible

[Freax13]

For BIOS the iterator is created from a slice. If we sort the slice, the iterator is also sorted. For UEFI the iterator is not created from a Rust slice but some raw bytes that are casted to descriptors. The uefi crate currently doesn't have an API to sort those descriptors, but I think it might be possible to add that.

[JarlEvanson]

I am working on getting sorting implemented in the uefi crate, and then will start work on the bios sorting.

[Freax13]

Bios is already sorted:

bootloader/bios/stage-4/src/main.rs

Line 35 in 52a0a67

memory_map.sort_unstable_by_key(|e| e.start_addr);

[phil-opp]

Once #360 is merged, we will be able to sort the UEFI memory map as well using the new MemoryMap::sort method.

[phil-opp]

I just merged #360. I PR to sort the memory map would be appreciated!