[U-Boot,09/16] efi_loader: Implement memory allocation and map

The EFI loader needs to maintain views of memory - general system memory
windows as well as used locations inside those and potential runtime service
MMIO windows.

To manage all of these, add a few helpers that maintain an internal
representation of the map the similar to how the EFI API later on reports
it to the application.

For allocations, the scheme is very simple. We basically allow allocations
to replace chunks of previously done maps, so that a new LOADER_DATA
allocation for example can remove a piece of the RAM map. When no specific
address is given, we just take the highest possible address in the lowest
RAM map that fits the allocation size.

Signed-off-by: Alexander Graf <agraf@suse.de>

---

v2 -> v3:

  - Rewrite memory allocation and map
  - Document header
---
 common/board_r.c            |   3 +
 include/efi_loader.h        |  19 +++
 lib/efi_loader/efi_memory.c | 314 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 336 insertions(+)
 create mode 100644 lib/efi_loader/efi_memory.c

On Tue, Feb 02, 2016 at 03:45:07AM +0100, Alexander Graf wrote:
> The EFI loader needs to maintain views of memory - general system memory
> windows as well as used locations inside those and potential runtime service
> MMIO windows.
> 
> To manage all of these, add a few helpers that maintain an internal
> representation of the map the similar to how the EFI API later on reports
> it to the application.
> 
> For allocations, the scheme is very simple. We basically allow allocations
> to replace chunks of previously done maps, so that a new LOADER_DATA
> allocation for example can remove a piece of the RAM map. When no specific
> address is given, we just take the highest possible address in the lowest
> RAM map that fits the allocation size.
> 
> Signed-off-by: Alexander Graf <agraf@suse.de>
> 
> ---
> 
> v2 -> v3:
> 
>   - Rewrite memory allocation and map
>   - Document header
> ---
>  common/board_r.c            |   3 +
>  include/efi_loader.h        |  19 +++
>  lib/efi_loader/efi_memory.c | 314 ++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 336 insertions(+)
>  create mode 100644 lib/efi_loader/efi_memory.c
> 
> diff --git a/common/board_r.c b/common/board_r.c
> index 420e2c8..2ed8e4b 100644
> --- a/common/board_r.c
> +++ b/common/board_r.c
> @@ -785,6 +785,9 @@ init_fnc_t init_sequence_r[] = {
>  #ifdef CONFIG_CLOCKS
>  	set_cpu_clk_info, /* Setup clock information */
>  #endif
> +#ifdef CONFIG_EFI_LOADER
> +	efi_memory_init,
> +#endif
>  	stdio_init_tables,
>  	initr_serial,
>  	initr_announce,
> diff --git a/include/efi_loader.h b/include/efi_loader.h
> index 91ab6cb..e38be12 100644
> --- a/include/efi_loader.h
> +++ b/include/efi_loader.h
> @@ -109,6 +109,25 @@ efi_status_t efi_exit_func(efi_status_t ret);
>  /* Call this to relocate the runtime section to an address space */
>  void efi_runtime_relocate(ulong offset, struct efi_mem_desc *map);
>  
> +/* Generic EFI memory allocator, call this to get memory */
> +void *efi_alloc(uint64_t len, int memory_type);
> +/* More specific EFI memory allocator, called by EFI payloads */
> +efi_status_t efi_allocate_pages(int type, int memory_type, unsigned long pages,
> +				uint64_t *memory);
> +/* EFI memory free function. Not implemented today */
> +efi_status_t efi_free_pages(uint64_t memory, unsigned long pages);
> +/* Returns the EFI memory map */
> +efi_status_t efi_get_memory_map(unsigned long *memory_map_size,
> +				struct efi_mem_desc *memory_map,
> +				unsigned long *map_key,
> +				unsigned long *descriptor_size,
> +				uint32_t *descriptor_version);
> +/* Adds a range into the EFI memory map */
> +uint64_t efi_add_memory_map(uint64_t start, uint64_t pages, int memory_type,
> +			    bool overlap_only_ram);
> +/* Called by board init to initialize the EFI memory map */
> +int efi_memory_init(void);
> +
>  /*
>   * Use these to indicate that your code / data should go into the EFI runtime
>   * section and thus still be available when the OS is running
> diff --git a/lib/efi_loader/efi_memory.c b/lib/efi_loader/efi_memory.c
> new file mode 100644
> index 0000000..e58d190
> --- /dev/null
> +++ b/lib/efi_loader/efi_memory.c
> @@ -0,0 +1,314 @@
> +/*
> + *  EFI application memory management
> + *
> + *  Copyright (c) 2016 Alexander Graf
> + *
> + *  SPDX-License-Identifier:     GPL-2.0+
> + */
> +
> +/* #define DEBUG_EFI */
> +
> +#include <common.h>
> +#include <efi_loader.h>
> +#include <malloc.h>
> +#include <asm/global_data.h>
> +#include <libfdt_env.h>
> +#include <inttypes.h>
> +#include <watchdog.h>
> +
> +DECLARE_GLOBAL_DATA_PTR;
> +
> +struct efi_mem_list {
> +	struct list_head link;
> +	struct efi_mem_desc desc;
> +};
> +
> +/* This list contains all memory map items */
> +LIST_HEAD(efi_mem);
> +
> +/*
> + * Unmaps all memory occupied by the carve_desc region from the
> + * list entry pointed to by map.
> + *
> + * Returns 1 if carving was performed or 0 if the regions don't overlap.
> + * Returns -1 if it would affect non-RAM regions but overlap_only_ram is set.
> + * Carving is only guaranteed to complete when all regions return 0.
> + */
> +static int efi_mem_carve_out(struct efi_mem_list *map,
> +			     struct efi_mem_desc *carve_desc,
> +			     bool overlap_only_ram)
> +{
> +	struct efi_mem_list *newmap;
> +	struct efi_mem_desc *map_desc = &map->desc;
> +	uint64_t map_start = map_desc->physical_start;
> +	uint64_t map_end = map_start + (map_desc->num_pages << 12);

Can we replace the magic 12 with an EFI_PAGE_SHIFT define?

> +	uint64_t carve_start = carve_desc->physical_start;
> +	uint64_t carve_end = carve_start + (carve_desc->num_pages << 12);
> +
> +	/* check whether we're overlapping */
> +	if ((carve_end <= map_start) || (carve_start >= map_end))
> +		return 0;
> +
> +	/* We're overlapping with non-RAM, warn the caller if desired */
> +	if (overlap_only_ram && (map_desc->type != EFI_CONVENTIONAL_MEMORY))
> +		return -1;
> +
> +	/* Sanitize carve_start and carve_end to lie within our bounds */
> +	carve_start = max(carve_start, map_start);
> +	carve_end = min(carve_end, map_end);
> +
> +	/* Carving at the beginning of our map? Just move it! */
> +	if (carve_start == map_start) {
> +		if (map_end == carve_end) {
> +			/* Full overlap, just remove map */
> +			list_del(&map->link);
> +		}
> +
> +		map_desc->physical_start = carve_end;
> +		map_desc->num_pages = (map_end - carve_end) >> 12;
> +		return 1;
> +	}
> +
> +	/*
> +	 * Overlapping maps, just split the list map at carve_start,
> +	 * it will get moved or removed in the next iteration.
> +	 *
> +	 * [ map_desc |__carve_start__| newmap ]
> +	 */
> +
> +	/* Create a new map from [ carve_start ... map_end ] */
> +	newmap = calloc(1, sizeof(*newmap));
> +	newmap->desc = map->desc;
> +	newmap->desc.physical_start = carve_start;
> +	newmap->desc.num_pages = (map_end - carve_start) >> 12;
> +        list_add_tail(&newmap->link, &efi_mem);
> +
> +	/* Shrink the map to [ map_start ... carve_start ] */
> +	map_desc->num_pages = (carve_start - map_start) >> 12;
> +
> +	return 1;
> +}
> +
> +uint64_t efi_add_memory_map(uint64_t start, uint64_t pages, int memory_type,
> +			    bool overlap_only_ram)
> +{
> +	struct list_head *lhandle;
> +	struct efi_mem_list *newlist;
> +	bool do_carving;
> +
> +	if (!pages)
> +		return start;
> +
> +	newlist = calloc(1, sizeof(*newlist));
> +	newlist->desc.type = memory_type;
> +	newlist->desc.physical_start = start;
> +	newlist->desc.virtual_start = start;
> +	newlist->desc.num_pages = pages;
> +
> +	switch (memory_type) {
> +	case EFI_RUNTIME_SERVICES_CODE:
> +	case EFI_RUNTIME_SERVICES_DATA:
> +		newlist->desc.attribute = (1 << EFI_MEMORY_WB_SHIFT) |
> +					  (1ULL << EFI_MEMORY_RUNTIME_SHIFT);
> +		break;
> +	case EFI_MMAP_IO:
> +		newlist->desc.attribute = 1ULL << EFI_MEMORY_RUNTIME_SHIFT;
> +		break;
> +	default:
> +		newlist->desc.attribute = 1 << EFI_MEMORY_WB_SHIFT;
> +		break;
> +	}
> +
> +	/* Add our new map */
> +	do {
> +		do_carving = false;
> +		list_for_each(lhandle, &efi_mem) {
> +			struct efi_mem_list *lmem;
> +			int r;
> +
> +			lmem = list_entry(lhandle, struct efi_mem_list, link);
> +			r = efi_mem_carve_out(lmem, &newlist->desc,
> +					      overlap_only_ram);
> +			if (r < 0) {
> +				return 0;
> +			} else if (r) {
> +				do_carving = true;
> +				break;
> +			}
> +		}
> +	} while (do_carving);
> +
> +	/* Add our new map */
> +        list_add_tail(&newlist->link, &efi_mem);
> +
> +	return start;
> +}
> +
> +static uint64_t efi_find_free_memory(uint64_t len, uint64_t max_addr)
> +{
> +	struct list_head *lhandle;
> +
> +	list_for_each(lhandle, &efi_mem) {
> +		struct efi_mem_list *lmem = list_entry(lhandle,
> +			struct efi_mem_list, link);
> +		struct efi_mem_desc *desc = &lmem->desc;
> +		uint64_t desc_len = desc->num_pages << 12;
> +		uint64_t desc_end = desc->physical_start + desc_len;
> +		uint64_t curmax = min(max_addr, desc_end);
> +		uint64_t ret = curmax - len;
> +
> +		/* We only take memory from free RAM */
> +		if (desc->type != EFI_CONVENTIONAL_MEMORY)
> +			continue;
> +
> +		/* Out of bounds for max_addr */
> +		if ((ret + len) > max_addr)
> +			continue;
> +
> +		/* Out of bounds for upper map limit */
> +		if ((ret + len) > desc_end)
> +			continue;
> +
> +		/* Out of bounds for lower map limit */
> +		if (ret < desc->physical_start)
> +			continue;
> +
> +		/* Return the highest address in this map within bounds */
> +		return ret;
> +	}
> +
> +	return 0;
> +}
> +
> +efi_status_t efi_allocate_pages(int type, int memory_type,
> +				unsigned long pages, uint64_t *memory)
> +{
> +	u64 len = pages << 12;
> +	efi_status_t r = EFI_SUCCESS;
> +	uint64_t addr;
> +
> +	switch (type) {
> +	case 0:
> +		/* Any page */
> +		addr = efi_find_free_memory(len, gd->ram_top);
> +		if (!addr) {
> +			r = EFI_NOT_FOUND;
> +			break;
> +		}
> +		break;
> +	case 1:
> +		/* Max address */
> +		addr = efi_find_free_memory(len, *memory);
> +		if (!addr) {
> +			r = EFI_NOT_FOUND;
> +			break;
> +		}
> +		break;
> +	case 2:
> +		/* Exact address, reserve it. The addr is already in *memory. */
> +		addr = *memory;
> +		break;

Still concerned over the lack of checking for clashes with existing
allocations. Ah, no, you trap that below. Sneaky :)

> +	default:
> +		/* UEFI doesn't specify other allocation types */
> +		r = EFI_INVALID_PARAMETER;
> +		break;
> +	}
> +
> +	if (r == EFI_SUCCESS) {
> +		uint64_t ret;
> +
> +		/* Reserve that map in our memory maps */
> +		ret = efi_add_memory_map(addr, pages, memory_type, true);
> +		if (ret == addr) {
> +			*memory = addr;
> +		} else {
> +			/* Map would overlap, bail out */
> +			r = EFI_NOT_FOUND;

EFI_OUT_OF_RESOURCES?

> +		}
> +	}
> +
> +	return r;
> +}
> +
> +void *efi_alloc(uint64_t len, int memory_type)
> +{
> +	uint64_t ret = 0;
> +	efi_status_t r;
> +
> +	r = efi_allocate_pages(0, memory_type, (len + 0xfff) >> 12, &ret);

A define for the 0xfff value as well? (EFI_PAGE_SIZE - 1)?

> +	if (r == EFI_SUCCESS)
> +		return (void*)(uintptr_t)ret;
> +
> +	return NULL;
> +}
> +
> +efi_status_t efi_free_pages(uint64_t memory, unsigned long pages)
> +{
> +	/* We don't free, let's cross our fingers we have plenty RAM */
> +	return EFI_SUCCESS;
> +}

This would actually be quite easy to implement correctly now with your
latest changes :)

But I won't insist it needs to be fixed for initial inclusion.

> +
> +efi_status_t efi_get_memory_map(unsigned long *memory_map_size,
> +			       struct efi_mem_desc *memory_map,
> +			       unsigned long *map_key,
> +			       unsigned long *descriptor_size,
> +			       uint32_t *descriptor_version)
> +{
> +	ulong map_size = 0;
> +	struct list_head *lhandle;
> +
> +	list_for_each(lhandle, &efi_mem)
> +		map_size += sizeof(struct efi_mem_desc);
> +
> +	*memory_map_size = map_size;
> +
> +	if (descriptor_size)
> +		*descriptor_size = sizeof(struct efi_mem_desc);
> +
> +	if (*memory_map_size < map_size)
> +		return EFI_BUFFER_TOO_SMALL;
> +
> +	/* Copy list into array */
> +	if (memory_map) {
> +		list_for_each(lhandle, &efi_mem) {
> +			struct efi_mem_list *lmem;
> +
> +			lmem = list_entry(lhandle, struct efi_mem_list, link);
> +			*memory_map = lmem->desc;
> +			memory_map++;
> +		}
> +	}
> +
> +	return EFI_SUCCESS;
> +}
> +
> +int efi_memory_init(void)
> +{
> +	uint64_t runtime_start, runtime_end, runtime_pages;
> +	uint64_t uboot_start, uboot_pages;
> +	uint64_t uboot_stack_size = 16 * 1024 * 1024;
> +	int i;
> +
> +	/* Add RAM */
> +	for (i = 0; i < CONFIG_NR_DRAM_BANKS; i++) {
> +		ulong start = (gd->bd->bi_dram[i].start + 0xfff) & ~0xfffULL;
> +		ulong pages = (gd->bd->bi_dram[i].size + 0xfff) >> 12;

(EFI_PAGE_SIZE -1)

> +
> +		efi_add_memory_map(start, pages, EFI_CONVENTIONAL_MEMORY,
> +				   false);
> +	}

Much prettier with the multi-bank handling. Thanks.

> +
> +	/* Add U-Boot */
> +	uboot_start = (gd->start_addr_sp - uboot_stack_size) & ~0xfffULL;
> +	uboot_pages = (gd->ram_top - uboot_start) >> 12;
> +	efi_add_memory_map(uboot_start, uboot_pages, EFI_LOADER_DATA, false);
> +
> +	/* Add Runtime Services */
> +	runtime_start = (ulong)&__efi_runtime_start & ~0xfffULL;
> +	runtime_end = ((ulong)&__efi_runtime_stop + 0xfff) & ~0xfffULL;
> +	runtime_pages = (runtime_end - runtime_start) >> 12;
> +	efi_add_memory_map(runtime_start, runtime_pages,
> +			   EFI_RUNTIME_SERVICES_CODE, false);
> +
> +	return 0;
> +}
> -- 
> 2.6.2
>

On 1 February 2016 at 19:45, Alexander Graf <agraf@suse.de> wrote:
> The EFI loader needs to maintain views of memory - general system memory
> windows as well as used locations inside those and potential runtime service
> MMIO windows.
>
> To manage all of these, add a few helpers that maintain an internal
> representation of the map the similar to how the EFI API later on reports
> it to the application.
>
> For allocations, the scheme is very simple. We basically allow allocations
> to replace chunks of previously done maps, so that a new LOADER_DATA
> allocation for example can remove a piece of the RAM map. When no specific
> address is given, we just take the highest possible address in the lowest
> RAM map that fits the allocation size.
>
> Signed-off-by: Alexander Graf <agraf@suse.de>
>
> ---
>
> v2 -> v3:
>
>   - Rewrite memory allocation and map
>   - Document header
> ---
>  common/board_r.c            |   3 +
>  include/efi_loader.h        |  19 +++
>  lib/efi_loader/efi_memory.c | 314 ++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 336 insertions(+)
>  create mode 100644 lib/efi_loader/efi_memory.c

Reviewed-by: Simon Glass <sjg@chromium.org>
Tested on Beaglebone Black and Minnowboard MAX:
Tested-by: Simon Glass <sjg@chromium.org>