[PATCH 02/10] mini-os: sort and sanitize e820 memory map

[Juergen Gross <jgross@xxxxxxxx>]

Do some processing of the E820 memory map obtained from the hypervisor:

- align the entries to page boundaries
- sort the entries by their start address
- merge adjacent entries of same type

This is relevant for PVH mode only.

Signed-off-by: Juergen Gross <jgross@xxxxxxxx>
---
 e820.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)

diff --git a/e820.c b/e820.c
index 2165280..336a8b8 100644
--- a/e820.c
+++ b/e820.c
@@ -57,6 +57,60 @@ static char *e820_types[E820_TYPES] = {
     [E820_PMEM]     = "PMEM"
 };
 
+static void e820_remove_entry(int idx)
+{
+    int i;
+
+    e820_entries--;
+    for ( i = idx; i < e820_entries; i++ )
+        e820_map[i] = e820_map[i + 1];
+}
+
+static void e820_swap_entries(int idx1, int idx2)
+{
+    struct e820entry entry;
+
+    entry = e820_map[idx1];
+    e820_map[idx1] = e820_map[idx2];
+    e820_map[idx2] = entry;
+}
+
+static void e820_sanitize(void)
+{
+    int i;
+    unsigned long end;
+
+    /* Adjust map entries to page boundaries. */
+    for ( i = 0; i < e820_entries; i++ )
+    {
+        end = (e820_map[i].addr + e820_map[i].size + PAGE_SIZE - 1) & 
PAGE_MASK;
+        e820_map[i].addr &= PAGE_MASK;
+        e820_map[i].size = end - e820_map[i].addr;
+    }
+
+    /* Sort entries by start address. */
+    for ( i = 0; i < e820_entries - 1; i++ )
+    {
+        if ( e820_map[i].addr > e820_map[i + 1].addr )
+        {
+            e820_swap_entries(i, i + 1);
+            i = -1;
+        }
+    }
+
+    /* Merge adjacent entries of same type. */
+    for ( i = 0; i < e820_entries - 1; i++ )
+    {
+        if ( e820_map[i].type == e820_map[i + 1].type &&
+             e820_map[i].addr + e820_map[i].size == e820_map[i + 1].addr )
+        {
+            e820_map[i].size += e820_map[i + 1].size;
+            e820_remove_entry(i + 1);
+            i--;
+        }
+    }
+}
+
 static void e820_get_memmap(void)
 {
     long ret;
@@ -71,6 +125,8 @@ static void e820_get_memmap(void)
         do_exit();
     }
     e820_entries = memmap.nr_entries;
+
+    e820_sanitize();
 }
 
 void arch_print_memmap(void)
-- 
2.26.2