bootloader: Split memory map handling into add/remove passes.

The memory map may be unordered and include overlapping ranges. To make
sure that nothing gets included as usable that should actually be
excluded, first scan for all usable ranges and add them, then remove
anything unusable from these ranges again.

To calculate the amount of unusable memory, count the total after the
first pass and then subtract the total after the second. This way, only
unusable ranges that actually overlap physical memory (and therefore
reduce the amount of usable memory) get excluded.

Note that the explicit ignore of the ACPI reclaim memory is subsumed by
the above. We still don't want to add this region to the usable memory
map, as that would allow the kernel to allocate pages into that region,
possibly corrupting ACPI tables before they were used. We also don't
want to add it as an allocated range, as it is not guaranteed that ACPI
is done with the tables before the unused bootloader ranges are freed in
the kernel.

Also add the missing unusable memory amount from ignoring the first MiB
of memory in the EFI loader.

May fix #16056 although it is not certain that graphics memory ranges
are actually included in the memory map.

Change-Id: Ie7991d2c4dcd988edac2995b3a7efc509fa0f4a3
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2814
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

Remove phys_addr_range, just use addr_range for both virtual and physical address ranges (as requested by Ingo).

Changes to kernel_args to make it identical for x86 and x86_64.

* Added a FixedWidthPointer template class which uses 64-bit storage to hold
a pointer. This is used in place of raw pointers in kernel_args.
* Added __attribute__((packed)) to kernel_args and all structures contained
within it. This is necessary due to different alignment behaviour for
32-bit and 64-bit compilation with GCC.
* With these changes, kernel_args will now come out the same size for both
the x86_64 kernel and the loader, excluding the preloaded_image structure
which has not yet been changed.
* Tested both an x86 GCC2 and GCC4 build, no problems caused by these changes.

Changed addr_range to use uint64.

I've tested this change on x86, causing no issues. I've checked over the code
for all other platforms and made the necessary changes and to the best of my
knowledge they should also still work, but I haven't actually built and
tested them. Once I've completed the kernel_args changes the other platforms
will need testing.

Added ignore_physical_memory_ranges_beyond_4gb() which removes the memory
beyond 4 GB from the physical memory ranges.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37224 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added shared sort_[physical_]address_ranges() to avoid code duplication. Also
fixes the m68k build.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36951 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Introduced phys_addr_range type, an equivalent to addr_range for physical
address ranges, and a set of support functions working with it.
* Changed the type of the kernel_args physical address range arrays to
phys_addr_range and adjusted the code working with those.
* Removed a bunch of duplicated address range code in the PPC's mmu.cpp.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36947 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added is_address_range_covered(), returning whether the given address range
is fully covered by the ranges in the array.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36631 a95241bf-73f2-0310-859d-f6bbb57e9c96

remove_addr_range() is actually called remove_address_range().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35824 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added get_free_address_range() to get a free range in a given range array.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35801 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Instead of its home-brewn solution, mmu_init() now uses the functions declared
in addr_range.h to add ranges to the arrays. This fixes the crashing bug reported
by Larry Baydak.
* Added some more exported functions to kernel_args.cpp (prototypes are in addr_range.h).
* TODO: let the PPC/OpenFirmware implementation use those as well.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19739 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added the prototype for insert_address_range() that can be used for the
various addr_range arrays in the kernel_args structure.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@9412 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved the addr_range struct out of kernel_args.h to a separate file.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7703 a95241bf-73f2-0310-859d-f6bbb57e9c96

Remove phys_addr_range, just use addr_range for both virtual and physical address ranges (as requested by Ingo).

Changes to kernel_args to make it identical for x86 and x86_64.

* Added a FixedWidthPointer template class which uses 64-bit storage to hold
a pointer. This is used in place of raw pointers in kernel_args.
* Added __attribute__((packed)) to kernel_args and all structures contained
within it. This is necessary due to different alignment behaviour for
32-bit and 64-bit compilation with GCC.
* With these changes, kernel_args will now come out the same size for both
the x86_64 kernel and the loader, excluding the preloaded_image structure
which has not yet been changed.
* Tested both an x86 GCC2 and GCC4 build, no problems caused by these changes.

Changed addr_range to use uint64.

I've tested this change on x86, causing no issues. I've checked over the code
for all other platforms and made the necessary changes and to the best of my
knowledge they should also still work, but I haven't actually built and
tested them. Once I've completed the kernel_args changes the other platforms
will need testing.

Added ignore_physical_memory_ranges_beyond_4gb() which removes the memory
beyond 4 GB from the physical memory ranges.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37224 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added shared sort_[physical_]address_ranges() to avoid code duplication. Also
fixes the m68k build.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36951 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Introduced phys_addr_range type, an equivalent to addr_range for physical
address ranges, and a set of support functions working with it.
* Changed the type of the kernel_args physical address range arrays to
phys_addr_range and adjusted the code working with those.
* Removed a bunch of duplicated address range code in the PPC's mmu.cpp.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36947 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added is_address_range_covered(), returning whether the given address range
is fully covered by the ranges in the array.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36631 a95241bf-73f2-0310-859d-f6bbb57e9c96

remove_addr_range() is actually called remove_address_range().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35824 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added get_free_address_range() to get a free range in a given range array.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35801 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Instead of its home-brewn solution, mmu_init() now uses the functions declared
in addr_range.h to add ranges to the arrays. This fixes the crashing bug reported
by Larry Baydak.
* Added some more exported functions to kernel_args.cpp (prototypes are in addr_range.h).
* TODO: let the PPC/OpenFirmware implementation use those as well.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19739 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added the prototype for insert_address_range() that can be used for the
various addr_range arrays in the kernel_args structure.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@9412 a95241bf-73f2-0310-859d-f6bbb57e9c96

Moved the addr_range struct out of kernel_args.h to a separate file.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7703 a95241bf-73f2-0310-859d-f6bbb57e9c96