text: /*
   * This file is part of the coreboot project.
   *
   * Copyright 2015 Google, Inc.
   *
   * This program is free software; you can redistribute it and/or modify
   * it under the terms of the GNU General Public License as published by
   * the Free Software Foundation; version 2 of the License.
   *
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   */
  
  #include <compiler.h>
  #include <assert.h>
  #include <cbmem.h>
  #include <console/console.h>
  #include <imd.h>
  #include <stdlib.h>
  #include <string.h>
  
  /* For more details on implementation and usage please see the imd.h header. */
  
  static const uint32_t IMD_ROOT_PTR_MAGIC = 0xc0389481;
  static const uint32_t IMD_ENTRY_MAGIC = ~0xc0389481;
  static const uint32_t SMALL_REGION_ID = CBMEM_ID_IMD_SMALL;
  static const size_t LIMIT_ALIGN = 4096;
  
  /* In-memory data structures. */
  struct imd_root_pointer {
  	uint32_t magic;
  	/* Relative to upper limit/offset. */
  	int32_t root_offset;
  } __packed;
  
  struct imd_entry {
  	uint32_t magic;
  	/* start is located relative to imd_root */
  	int32_t start_offset;
  	uint32_t size;
  	uint32_t id;
  } __packed;
  
  struct imd_root {
  	uint32_t max_entries;
  	uint32_t num_entries;
  	uint32_t flags;
  	uint32_t entry_align;
  	/* Used for fixing the size of an imd. Relative to the root. */
  	int32_t max_offset;
  	struct imd_entry entries[0];
  } __packed;
  
  #define IMD_FLAG_LOCKED 1
  
  static void *relative_pointer(void *base, ssize_t offset)
  {
  	intptr_t b = (intptr_t)base;
  	b += offset;
  	return (void *)b;
  }
  
  static bool imd_root_pointer_valid(const struct imd_root_pointer *rp)
  {
  	return !!(rp->magic == IMD_ROOT_PTR_MAGIC);
  }
  
  static struct imd_root *imdr_root(const struct imdr *imdr)
  {
  	return imdr->r;
  }
  
  /*
   * The root pointer is relative to the upper limit of the imd. i.e. It sits
   * just below the upper limit.
   */
  static struct imd_root_pointer *imdr_get_root_pointer(const struct imdr *imdr)
  {
  	struct imd_root_pointer *rp;
  
  	rp = relative_pointer((void *)imdr->limit, -sizeof(*rp));
  
  	return rp;
  }
  
  static void imd_link_root(struct imd_root_pointer *rp, struct imd_root *r)
  {
  	rp->magic = IMD_ROOT_PTR_MAGIC;
  	rp->root_offset = (int32_t)((intptr_t)r - (intptr_t)rp);
  }
  
  static struct imd_entry *root_last_entry(struct imd_root *r)
  {
  	return &r->entries[r->num_entries - 1];
  }
  
  static size_t root_num_entries(size_t root_size)
  {
  	size_t entries_size;
  
  	entries_size = root_size;
  	entries_size -= sizeof(struct imd_root_pointer);
  	entries_size -= sizeof(struct imd_root);
  
  	return entries_size / sizeof(struct imd_entry);
  }
  
  static size_t imd_root_data_left(struct imd_root *r)
  {
  	struct imd_entry *last_entry;
  
  	last_entry = root_last_entry(r);
  
  	if (r->max_offset != 0)
  		return last_entry->start_offset - r->max_offset;
  
  	return ~(size_t)0;
  }
  
  static bool root_is_locked(const struct imd_root *r)
  {
  	return !!(r->flags & IMD_FLAG_LOCKED);
  }
  
  static void imd_entry_assign(struct imd_entry *e, uint32_t id,
  				ssize_t offset, size_t size)
  {
  	e->magic = IMD_ENTRY_MAGIC;
  	e->start_offset = offset;
  	e->size = size;
  	e->id = id;
  }
  
  static void imdr_init(struct imdr *ir, void *upper_limit)
  {
  	uintptr_t limit = (uintptr_t)upper_limit;
  	/* Upper limit is aligned down to 4KiB */
  	ir->limit = ALIGN_DOWN(limit, LIMIT_ALIGN);
  	ir->r = NULL;
  }
  
  static int imdr_create_empty(struct imdr *imdr, size_t root_size,
  				size_t entry_align)
  {
  	struct imd_root_pointer *rp;
  	struct imd_root *r;
  	struct imd_entry *e;
  	ssize_t root_offset;
  
  	if (!imdr->limit)
  		return -1;
  
  	/* root_size and entry_align should be a power of 2. */
  	assert(IS_POWER_OF_2(root_size));
  	assert(IS_POWER_OF_2(entry_align));
  
  	if (!imdr->limit)
  		return -1;
  
  	/*
  	 * root_size needs to be large enough to accommodate root pointer and
  	 * root book keeping structure. The caller needs to ensure there's
  	 * enough room for tracking individual allocations.
  	 */
  	if (root_size < (sizeof(*rp) + sizeof(*r)))
  		return -1;
  
  	/* For simplicity don't allow sizes or alignments to exceed LIMIT_ALIGN.
  	 */
  	if (root_size > LIMIT_ALIGN || entry_align > LIMIT_ALIGN)
  		return -1;
  
  	/* Additionally, don't handle an entry alignment > root_size. */
  	if (entry_align > root_size)
  		return -1;
  
  	rp = imdr_get_root_pointer(imdr);
  
  	root_offset = -(ssize_t)root_size;
  	/* Set root pointer. */
  	imdr->r = relative_pointer((void *)imdr->limit, root_offset);
  	r = imdr_root(imdr);
  	imd_link_root(rp, r);
  
  	memset(r, 0, sizeof(*r));
  	r->entry_align = entry_align;
  
  	/* Calculate size left for entries. */
  	r->max_entries = root_num_entries(root_size);
  
  	/* Fill in first entry covering the root region. */
  	r->num_entries = 1;
  	e = &r->entries[0];
  	imd_entry_assign(e, CBMEM_ID_IMD_ROOT, 0, root_size);
  
  	printk(BIOS_DEBUG, "IMD: root @ %p %u entries.\n", r, r->max_entries);
  
  	return 0;
  }
  
  static int imdr_recover(struct imdr *imdr)
  {
  	struct imd_root_pointer *rp;
  	struct imd_root *r;
  	uintptr_t low_limit;
  	size_t i;
  
  	if (!imdr->limit)
  		return -1;
  
  	rp = imdr_get_root_pointer(imdr);
  
  	if (!imd_root_pointer_valid(rp))
  		return -1;
  
  	r = relative_pointer(rp, rp->root_offset);
  
  	/* Confirm the root and root pointer are just under the limit. */
  	if (ALIGN_UP((uintptr_t)&r->entries[r->max_entries], LIMIT_ALIGN) !=
  			imdr->limit)
  		return -1;
  
  	if (r->num_entries > r->max_entries)
  		return -1;
  
  	/* Entry alignment should be power of 2. */
  	if (!IS_POWER_OF_2(r->entry_align))
  		return -1;
  
  	low_limit = (uintptr_t)relative_pointer(r, r->max_offset);
  
  	/* If no max_offset then lowest limit is 0. */
  	if (low_limit == (uintptr_t)r)
  		low_limit = 0;
  
  	for (i = 0; i < r->num_entries; i++) {
  		uintptr_t start_addr;
  		const struct imd_entry *e = &r->entries[i];
  
  		if (e->magic != IMD_ENTRY_MAGIC)
  			return -1;
  
  		start_addr = (uintptr_t)relative_pointer(r, e->start_offset);
  		if (start_addr  < low_limit)
  			return -1;
  		if (start_addr >= imdr->limit ||
  				(start_addr + e->size) > imdr->limit)
  			return -1;
  	}
  
  	/* Set root pointer. */
  	imdr->r = r;
  
  	return 0;
  }
  
  static const struct imd_entry *imdr_entry_find(const struct imdr *imdr,
  						uint32_t id)
  {
  	struct imd_root *r;
  	struct imd_entry *e;
  	size_t i;
  
  	r = imdr_root(imdr);
  
  	if (r == NULL)
  		return NULL;
  
  	e = NULL;
  	/* Skip first entry covering the root. */
  	for (i = 1; i < r->num_entries; i++) {
  		if (id != r->entries[i].id)
  			continue;
  		e = &r->entries[i];
  		break;
  	}
  
  	return e;
  }
  
  static int imdr_limit_size(struct imdr *imdr, size_t max_size)
  {
  	struct imd_root *r;
  	ssize_t smax_size;
  	size_t root_size;
  
  	r = imdr_root(imdr);
  	if (r == NULL)
  		return -1;
  
  	root_size = imdr->limit - (uintptr_t)r;
  
  	if (max_size < root_size)
  		return -1;
  
  	/* Take into account the root size. */
  	smax_size = max_size - root_size;
  	smax_size = -smax_size;
  
  	r->max_offset = smax_size;
  
  	return 0;
  }
  
  static size_t imdr_entry_size(const struct imdr *imdr,
  				const struct imd_entry *e)
  {
  	return e->size;
  }
  
  static void *imdr_entry_at(const struct imdr *imdr, const struct imd_entry *e)
  {
  	return relative_pointer(imdr_root(imdr), e->start_offset);
  }
  
  static struct imd_entry *imd_entry_add_to_root(struct imd_root *r, uint32_t id,
  						size_t size)
  {
  	struct imd_entry *entry;
  	struct imd_entry *last_entry;
  	ssize_t e_offset;
  	size_t used_size;
  
  	if (r->num_entries == r->max_entries)
  		return NULL;
  
  	/* Determine total size taken up by entry. */
  	used_size = ALIGN_UP(size, r->entry_align);
  
  	/* See if size overflows imd total size. */
  	if (used_size > imd_root_data_left(r))
  		return NULL;
  
  	/*
  	 * Determine if offset field overflows. All offsets should be lower
  	 * than the previous one.
  	 */
  	last_entry = root_last_entry(r);
  	e_offset = last_entry->start_offset;
  	e_offset -= (ssize_t)used_size;
  	if (e_offset > last_entry->start_offset)
  		return NULL;
  
  	entry = root_last_entry(r) + 1;
  	r->num_entries++;
  
  	imd_entry_assign(entry, id, e_offset, size);
  
  	return entry;
  }
  
  static const struct imd_entry *imdr_entry_add(const struct imdr *imdr,
  						uint32_t id, size_t size)
  {
  	struct imd_root *r;
  
  	r = imdr_root(imdr);
  
  	if (r == NULL)
  		return NULL;
  
  	if (root_is_locked(r))
  		return NULL;
  
  	return imd_entry_add_to_root(r, id, size);
  }
  
  static bool imdr_has_entry(const struct imdr *imdr, const struct imd_entry *e)
  {
  	struct imd_root *r;
  	size_t idx;
  
  	r = imdr_root(imdr);
  	if (r == NULL)
  		return false;
  
  	/* Determine if the entry is within this root structure. */
  	idx = e - &r->entries[0];
  	if (idx >= r->num_entries)
  		return false;
  
  	return true;
  }
  
  static const struct imdr *imd_entry_to_imdr(const struct imd *imd,
  						const struct imd_entry *entry)
  {
  	if (imdr_has_entry(&imd->lg, entry))
  		return &imd->lg;
  
  	if (imdr_has_entry(&imd->sm, entry))
  		return &imd->sm;
  
  	return NULL;
  }
  
  /* Initialize imd handle. */
  void imd_handle_init(struct imd *imd, void *upper_limit)
  {
  	imdr_init(&imd->lg, upper_limit);
  	imdr_init(&imd->sm, NULL);
  }
  
  void imd_handle_init_partial_recovery(struct imd *imd)
  {
  	const struct imd_entry *e;
  	struct imd_root_pointer *rp;
  	struct imdr *imdr;
  
  	if (imd->lg.limit == 0)
  		return;
  
  	imd_handle_init(imd, (void *)imd->lg.limit);
  
  	/* Initialize root pointer for the large regions. */
  	imdr = &imd->lg;
  	rp = imdr_get_root_pointer(imdr);
  	imdr->r = relative_pointer(rp, rp->root_offset);
  
  	e = imdr_entry_find(imdr, SMALL_REGION_ID);
  
  	if (e == NULL)
  		return;
  
  	imd->sm.limit = (uintptr_t)imdr_entry_at(imdr, e);
  	imd->sm.limit += imdr_entry_size(imdr, e);
  	imdr = &imd->sm;
  	rp = imdr_get_root_pointer(imdr);
  	imdr->r = relative_pointer(rp, rp->root_offset);
  }
  
  int imd_create_empty(struct imd *imd, size_t root_size, size_t entry_align)
  {
  	return imdr_create_empty(&imd->lg, root_size, entry_align);
  }
  
  int imd_create_tiered_empty(struct imd *imd,
  				size_t lg_root_size, size_t lg_entry_align,
  				size_t sm_root_size, size_t sm_entry_align)
  {
  	size_t sm_region_size;
  	const struct imd_entry *e;
  	struct imdr *imdr;
  
  	imdr = &imd->lg;
  
  	if (imdr_create_empty(imdr, lg_root_size, lg_entry_align) != 0)
  		return -1;
  
  	/* Calculate the size of the small region to request. */
  	sm_region_size = root_num_entries(sm_root_size) * sm_entry_align;
  	sm_region_size += sm_root_size;
  	sm_region_size = ALIGN_UP(sm_region_size, lg_entry_align);
  
  	/* Add a new entry to the large region to cover the root and entries. */
  	e = imdr_entry_add(imdr, SMALL_REGION_ID, sm_region_size);
  
  	if (e == NULL)
  		goto fail;
  
  	imd->sm.limit = (uintptr_t)imdr_entry_at(imdr, e);
  	imd->sm.limit += sm_region_size;
  
  	if (imdr_create_empty(&imd->sm, sm_root_size, sm_entry_align) != 0 ||
  		imdr_limit_size(&imd->sm, sm_region_size))
  		goto fail;
  
  	return 0;
  fail:
  	imd_handle_init(imd, (void *)imdr->limit);
  	return -1;
  }
  
  int imd_recover(struct imd *imd)
  {
  	const struct imd_entry *e;
  	uintptr_t small_upper_limit;
  	struct imdr *imdr;
  
  	imdr = &imd->lg;
  	if (imdr_recover(imdr) != 0)
  		return -1;
  
  	/* Determine if small region is region is present. */
  	e = imdr_entry_find(imdr, SMALL_REGION_ID);
  
  	if (e == NULL)
  		return 0;
  
  	small_upper_limit = (uintptr_t)imdr_entry_at(imdr, e);
  	small_upper_limit += imdr_entry_size(imdr, e);
  
  	imd->sm.limit = small_upper_limit;
  
  	/* Tear down any changes on failure. */
  	if (imdr_recover(&imd->sm) != 0) {
  		imd_handle_init(imd, (void *)imd->lg.limit);
  		return -1;
  	}
  
  	return 0;
  }
  
  int imd_limit_size(struct imd *imd, size_t max_size)
  {
  	return imdr_limit_size(&imd->lg, max_size);
  }
  
  int imd_lockdown(struct imd *imd)
  {
  	struct imd_root *r;
  
  	r = imdr_root(&imd->lg);
  	if (r == NULL)
  		return -1;
  
  	r->flags |= IMD_FLAG_LOCKED;
  
  	r = imdr_root(&imd->sm);
  	if (r != NULL)
  		r->flags |= IMD_FLAG_LOCKED;
  
  	return 0;
  }
  
  int imd_region_used(struct imd *imd, void **base, size_t *size)
  {
  	struct imd_root *r;
  	struct imd_entry *e;
  	void *low_addr;
  	size_t sz_used;
  
  	if (!imd->lg.limit)
  		return -1;
  
  	r = imdr_root(&imd->lg);
  
  	if (r == NULL)
  		return -1;
  
  	/* Use last entry to obtain lowest address. */
  	e = root_last_entry(r);
  
  	low_addr = relative_pointer(r, e->start_offset);
  
  	/* Total size used is the last entry's base up to the limit. */
  	sz_used = imd->lg.limit - (uintptr_t)low_addr;
  
  	*base = low_addr;
  	*size = sz_used;
  
  	return 0;
  }
  
  const struct imd_entry *imd_entry_add(const struct imd *imd, uint32_t id,
  					size_t size)
  {
  	struct imd_root *r;
  	const struct imdr *imdr;
  	const struct imd_entry *e = NULL;
  
  	/*
  	 * Determine if requested size is less than 1/4 of small data
  	 * region is left.
  	 */
  	imdr = &imd->sm;
  	r = imdr_root(imdr);
  
  	/* No small region. Use the large region. */
  	if (r == NULL)
  		return imdr_entry_add(&imd->lg, id, size);
  	else if (size <= r->entry_align || size <= imd_root_data_left(r) / 4)
  		e = imdr_entry_add(imdr, id, size);
  
  	/* Fall back on large region allocation. */
  	if (e == NULL)
  		e = imdr_entry_add(&imd->lg, id, size);
  
  	return e;
  }
  
  const struct imd_entry *imd_entry_find(const struct imd *imd, uint32_t id)
  {
  	const struct imd_entry *e;
  
  	/* Many of the smaller allocations are used a lot. Therefore, try
  	 * the small region first. */
  	e = imdr_entry_find(&imd->sm, id);
  
  	if (e == NULL)
  		e = imdr_entry_find(&imd->lg, id);
  
  	return e;
  }
  
  const struct imd_entry *imd_entry_find_or_add(const struct imd *imd,
  						uint32_t id, size_t size)
  {
  	const struct imd_entry *e;
  
  	e = imd_entry_find(imd, id);
  
  	if (e != NULL)
  		return e;
  
  	return imd_entry_add(imd, id, size);
  }
  
  size_t imd_entry_size(const struct imd *imd, const struct imd_entry *entry)
  {
  	return imdr_entry_size(NULL, entry);
  }
  
  void *imd_entry_at(const struct imd *imd, const struct imd_entry *entry)
  {
  	const struct imdr *imdr;
  
  	imdr = imd_entry_to_imdr(imd, entry);
  
  	if (imdr == NULL)
  		return NULL;
  
  	return imdr_entry_at(imdr, entry);
  }
  
  uint32_t imd_entry_id(const struct imd *imd, const struct imd_entry *entry)
  {
  	return entry->id;
  }
  
  int imd_entry_remove(const struct imd *imd, const struct imd_entry *entry)
  {
  	struct imd_root *r;
  	const struct imdr *imdr;
  
  	imdr = imd_entry_to_imdr(imd, entry);
  
  	if (imdr == NULL)
  		return -1;
  
  	r = imdr_root(imdr);
  
  	if (r == NULL)
  		return -1;
  
  	if (root_is_locked(r))
  		return -1;
  
  	if (entry != root_last_entry(r))
  		return -1;
  
  	r->num_entries--;
  
  	return 0;
  }
  
  static void imdr_print_entries(const struct imdr *imdr, const char *indent,
  				const struct imd_lookup *lookup, size_t size)
  {
  	struct imd_root *r;
  	size_t i;
  	size_t j;
  
  	if (imdr == NULL)
  		return;
  
  	r = imdr_root(imdr);
  
  	for (i = 0; i < r->num_entries; i++) {
  		const char *name = NULL;
  		const struct imd_entry *e = &r->entries[i];
  
  		for (j = 0; j < size; j++) {
  			if (lookup[j].id == e->id) {
  				name = lookup[j].name;
  				break;
  			}
  		}
  
  		printk(BIOS_DEBUG, "%s", indent);
  
  		if (name == NULL)
  			printk(BIOS_DEBUG, "%08x   ", e->id);
  		else
  			printk(BIOS_DEBUG, "%s", name);
  		printk(BIOS_DEBUG, "%2zu. ", i);
  		printk(BIOS_DEBUG, "%p ", imdr_entry_at(imdr, e));
  		printk(BIOS_DEBUG, "%08zx\n", imdr_entry_size(imdr, e));
  	}
  }
  
  int imd_print_entries(const struct imd *imd, const struct imd_lookup *lookup,
  			size_t size)
  {
  	if (imdr_root(&imd->lg) == NULL)
  		return -1;
  
  	imdr_print_entries(&imd->lg, "", lookup, size);
  	if (imdr_root(&imd->sm) != NULL) {
  		printk(BIOS_DEBUG, "IMD small region:\n");
  		imdr_print_entries(&imd->sm, "  ", lookup, size);
  	}
  
  	return 0;
  }
  
  int imd_cursor_init(const struct imd *imd, struct imd_cursor *cursor)
  {
  	if (imd == NULL || cursor == NULL)
  		return -1;
  
  	memset(cursor, 0, sizeof(*cursor));
  
  	cursor->imdr[0] = &imd->lg;
  	cursor->imdr[1] = &imd->sm;
  
  	return 0;
  }
  
  const struct imd_entry *imd_cursor_next(struct imd_cursor *cursor)
  {
  	struct imd_root *r;
  	const struct imd_entry *e;
  
  	if (cursor->current_imdr >= ARRAY_SIZE(cursor->imdr))
  		return NULL;
  
  	r = imdr_root(cursor->imdr[cursor->current_imdr]);
  
  	if (r == NULL)
  		return NULL;
  
  	if (cursor->current_entry >= r->num_entries) {
  		/* Try next imdr. */
  		cursor->current_imdr++;
  		cursor->current_entry = 0;
  		return imd_cursor_next(cursor);
  	}
  
  	e = &r->entries[cursor->current_entry];
  	cursor->current_entry++;
  
  	return e;
  }
  