|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [PATCH v2 02/10] mini-os: sort and sanitize e820 memory map
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>
---
V2:
- correct page boundary rounding
- handle overlaps after rounding (Samuel Thibault)
- improve sorting (Samuel Thibault)
---
e820.c | 186 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 186 insertions(+)
diff --git a/e820.c b/e820.c
index 2165280..1770158 100644
--- a/e820.c
+++ b/e820.c
@@ -57,6 +57,190 @@ static char *e820_types[E820_TYPES] = {
[E820_PMEM] = "PMEM"
};
+/*
+ * E820 type based bitmask for deciding how to round entries to page
+ * boundaries: A set bit means the type relates to a resource managed by
+ * Mini-OS (e.g. RAM), so rounding needs to be done to only include pages
+ * completely of the related type (narrowing). All other types need to be
+ * rounded to include all pages with parts of that type (widening).
+ */
+#define E820_NARROW ((1U << E820_RAM) | (1U << E820_NVS) | (1 << E820_PMEM))
+
+/* Private type used to mark a range temporarily as reserved (lowest prio). */
+#define E820_TMP_RESERVED 0
+
+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_insert_entry_at(int idx, unsigned long addr,
+ unsigned long size, unsigned int type)
+{
+ int i;
+
+ if ( e820_entries == E820_MAX )
+ {
+ xprintk("E820 memory map overflow\n");
+ do_exit();
+ }
+
+ e820_entries++;
+ for ( i = e820_entries - 1; i > idx; i-- )
+ e820_map[i] = e820_map[i - 1];
+
+ e820_map[idx].addr = addr;
+ e820_map[idx].size = size;
+ e820_map[idx].type = type;
+}
+
+static void e820_insert_entry(unsigned long addr, unsigned long size,
+ unsigned int type)
+{
+ int i;
+
+ for ( i = 0; i < e820_entries && addr > e820_map[i].addr; i++ );
+
+ e820_insert_entry_at(i, addr, size, type);
+}
+
+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;
+}
+
+/*
+ * Do a memory map sanitizing sweep:
+ * - sort the entries by start address
+ * - remove overlaps of entries (higher type value wins)
+ * - merge adjacent entries of same type
+ */
+static void e820_process_entries(void)
+{
+ int i, j;
+ unsigned long end, start;
+ unsigned int type;
+
+ /* Sort entries. */
+ for ( i = 1; i < e820_entries; i++ )
+ for ( j = i; j > 0 && e820_map[j - 1].addr > e820_map[j].addr; j-- )
+ e820_swap_entries(j - 1, j);
+
+ /* Handle overlapping entries (higher type values win). */
+ for ( i = 1; i < e820_entries; i++ )
+ {
+ if ( e820_map[i - 1].addr + e820_map[i - 1].size <= e820_map[i].addr )
+ continue;
+ if ( e820_map[i - 1].addr < e820_map[i].addr )
+ {
+ e820_insert_entry_at(i - 1, e820_map[i - 1].addr,
+ e820_map[i].addr - e820_map[i - 1].addr,
+ e820_map[i - 1].type);
+ e820_map[i].addr += e820_map[i - 1].size;
+ e820_map[i].size -= e820_map[i - 1].size;
+ i++;
+ }
+ if ( e820_map[i - 1].type < e820_map[i].type )
+ e820_swap_entries(i - 1, i);
+ if ( e820_map[i - 1].size >= e820_map[i].size )
+ {
+ e820_remove_entry(i);
+ i--;
+ }
+ else
+ {
+ start = e820_map[i].addr + e820_map[i - 1].size;
+ end = e820_map[i].addr + e820_map[i].size;
+ type = e820_map[i].type;
+ e820_remove_entry(i);
+ e820_insert_entry(start, end - start, type);
+ }
+ }
+
+ /* Merge adjacent entries. */
+ 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 )
+ {
+ if ( e820_map[i].addr + e820_map[i].size <
+ e820_map[i + 1].addr + e820_map[i + 1].size )
+ {
+ e820_map[i].size = e820_map[i + 1].addr - e820_map[i].addr +
+ e820_map[i + 1].size;
+ }
+ e820_remove_entry(i + 1);
+ i--;
+ }
+ }
+}
+
+/*
+ * Transform memory map into a well sorted map without any overlaps.
+ * - sort map entries by start address
+ * - handle overlaps
+ * - merge adjacent entries of same type (possibly removing boundary in the
+ * middle of a page)
+ * - trim entries to page boundaries (depending on type either expanding
+ * the entry or narrowing it down)
+ * - repeat first 3 sanitizing steps
+ * - make remaining temporarily reserved entries permanently reserved
+ */
+static void e820_sanitize(void)
+{
+ int i;
+ unsigned long end, start;
+
+ /* Sanitize memory map in current form. */
+ e820_process_entries();
+
+ /* Adjust map entries to page boundaries. */
+ for ( i = 0; i < e820_entries; i++ )
+ {
+ start = e820_map[i].addr;
+ end = start + e820_map[i].size;
+ if ( (1U << e820_map[i].type) & E820_NARROW )
+ {
+ if ( start & (PAGE_SIZE - 1) )
+ {
+ start = round_pgup(start);
+ e820_insert_entry_at(i, start - PAGE_SIZE, PAGE_SIZE,
+ E820_TMP_RESERVED);
+ i++;
+ }
+ if ( end & (PAGE_SIZE - 1) )
+ {
+ end = round_pgdown(end);
+ e820_insert_entry_at(i, end, PAGE_SIZE, E820_TMP_RESERVED);
+ i++;
+ }
+ }
+ else
+ {
+ start = round_pgdown(start);
+ end = round_pgup(end);
+ }
+ e820_map[i].addr = start;
+ e820_map[i].size = end - start;
+ }
+
+ /* Sanitize memory map (again). */
+ e820_process_entries();
+
+ /* Make remaining temporarily reserved entries permanently reserved. */
+ for ( i = 0; i < e820_entries; i++ )
+ if ( e820_map[i].type == E820_TMP_RESERVED )
+ e820_map[i].type = E820_RESERVED;
+}
+
static void e820_get_memmap(void)
{
long ret;
@@ -71,6 +255,8 @@ static void e820_get_memmap(void)
do_exit();
}
e820_entries = memmap.nr_entries;
+
+ e820_sanitize();
}
void arch_print_memmap(void)
--
2.26.2
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |