bhyve: add allocation function to E820

This function makes it easy to allocate new E820 entries. It will be
used to allocate graphics memory for Intel integrated graphic devices.

Reviewed by:		markj
MFC after:		1 week
Sponsored by:		Beckhoff Automation GmbH & Co. KG
Differential Revision:	https://reviews.freebsd.org/D39547

(cherry picked from commit 5597f564870e94d56111dec638b8859423c936a9)

2 files changed, 120 insertions, 0 deletions

diff --git a/usr.sbin/bhyve/e820.c b/usr.sbin/bhyve/e820.c
index 95b83c056b9b..922381d032ce 100644
--- a/usr.sbin/bhyve/e820.c
+++ b/usr.sbin/bhyve/e820.c
@@ -20,6 +20,14 @@
 #include "e820.h"
 #include "qemu_fwcfg.h"
 
+/*
+ * E820 always uses 64 bit entries. Emulation code will use vm_paddr_t since it
+ * works on physical addresses. If vm_paddr_t is larger than uint64_t E820 can't
+ * hold all possible physical addresses and we can get into trouble.
+ */
+static_assert(sizeof(vm_paddr_t) <= sizeof(uint64_t),
+    "Unable to represent physical memory by E820 table");
+
 #define E820_FWCFG_FILE_NAME "etc/e820"
 
 #define KB (1024UL)
@@ -282,6 +290,102 @@ e820_add_memory_hole(const uint64_t base, const uint64_t end)
 	return (0);
 }
 
+static uint64_t
+e820_alloc_highest(const uint64_t max_address, const uint64_t length,
+    const uint64_t alignment, const enum e820_memory_type type)
+{
+	struct e820_element *element;
+
+	TAILQ_FOREACH_REVERSE(element, &e820_table, e820_table, chain) {
+		uint64_t address, base, end;
+
+		end = MIN(max_address, element->end);
+		base = roundup2(element->base, alignment);
+
+		/*
+		 * If end - length == 0, we would allocate memory at address 0. This
+		 * address is mostly unusable and we should avoid allocating it.
+		 * Therefore, search for another block in that case.
+		 */
+		if (element->type != E820_TYPE_MEMORY || end < base ||
+		    end - base < length || end - length == 0) {
+			continue;
+		}
+
+		address = rounddown2(end - length, alignment);
+
+		if (e820_add_entry(address, address + length, type) != 0) {
+			return (0);
+		}
+
+		return (address);
+	}
+
+	return (0);
+}
+
+static uint64_t
+e820_alloc_lowest(const uint64_t min_address, const uint64_t length,
+    const uint64_t alignment, const enum e820_memory_type type)
+{
+	struct e820_element *element;
+
+	TAILQ_FOREACH(element, &e820_table, chain) {
+		uint64_t base, end;
+
+		end = element->end;
+		base = MAX(min_address, roundup2(element->base, alignment));
+
+		/*
+		 * If base == 0, we would allocate memory at address 0. This
+		 * address is mostly unusable and we should avoid allocating it.
+		 * Therefore, search for another block in that case.
+		 */
+		if (element->type != E820_TYPE_MEMORY || end < base ||
+		    end - base < length || base == 0) {
+			continue;
+		}
+
+		if (e820_add_entry(base, base + length, type) != 0) {
+			return (0);
+		}
+
+		return (base);
+	}
+
+	return (0);
+}
+
+uint64_t
+e820_alloc(const uint64_t address, const uint64_t length,
+    const uint64_t alignment, const enum e820_memory_type type,
+    const enum e820_allocation_strategy strategy)
+{
+	assert(powerof2(alignment));
+	assert((address & (alignment - 1)) == 0);
+
+	switch (strategy) {
+	case E820_ALLOCATE_ANY:
+		/*
+		 * Allocate any address. Therefore, ignore the address parameter
+		 * and reuse the code path for allocating the lowest address.
+		 */
+		return (e820_alloc_lowest(0, length, alignment, type));
+	case E820_ALLOCATE_LOWEST:
+		return (e820_alloc_lowest(address, length, alignment, type));
+	case E820_ALLOCATE_HIGHEST:
+		return (e820_alloc_highest(address, length, alignment, type));
+	case E820_ALLOCATE_SPECIFIC:
+		if (e820_add_entry(address, address + length, type) != 0) {
+			return (0);
+		}
+
+		return (address);
+	}
+
+	return (0);
+}
+
 int
 e820_init(struct vmctx *const ctx)
 {
diff --git a/usr.sbin/bhyve/e820.h b/usr.sbin/bhyve/e820.h
index 6843ad5dc736..8b8e23422e1f 100644
--- a/usr.sbin/bhyve/e820.h
+++ b/usr.sbin/bhyve/e820.h
@@ -18,11 +18,27 @@ enum e820_memory_type {
 	E820_TYPE_NVS = 4
 };
 
+enum e820_allocation_strategy {
+	/* allocate any address */
+	E820_ALLOCATE_ANY,
+	/* allocate lowest address larger than address */
+	E820_ALLOCATE_LOWEST,
+	/* allocate highest address lower than address */
+	E820_ALLOCATE_HIGHEST,
+	/* allocate a specific address */
+	E820_ALLOCATE_SPECIFIC
+};
+
 struct e820_entry {
 	uint64_t base;
 	uint64_t length;
 	uint32_t type;
 } __packed;
 
+#define E820_ALIGNMENT_NONE 1
+
+uint64_t e820_alloc(const uint64_t address, const uint64_t length,
+    const uint64_t alignment, const enum e820_memory_type type,
+    const enum e820_allocation_strategy strategy);
 struct qemu_fwcfg_item *e820_get_fwcfg_item(void);
 int e820_init(struct vmctx *const ctx);