From 20686d851ce450750039f5f871160d49118a2210 Mon Sep 17 00:00:00 2001 From: Aaron Durbin Date: Thu, 5 Mar 2015 14:11:27 -0600 Subject: coreboot: add imd library The imd (internal memory database) library provides a way to track memory regions by assigning ids to each region. The implementation is a direct descendant of dynamic cbmem. The intent is to replace the existing mechanisms which do similar things: dynamic cbmem, stage cache, etc. Differences between dynamic cbmem and imd: - All structures/objects are relative to one another. There are no absolute pointers serialized to memory. - Allow limiting the size of the idm. i.e. provide a maximum memory usage. - Allow setting the size of the root structure which allows control of the number of allocations to track. Change-Id: Id7438cff80d396a594d6a7330d09b45bb4fedf2e Signed-off-by: Aaron Durbin Reviewed-on: http://review.coreboot.org/8621 Tested-by: build bot (Jenkins) Reviewed-by: Marc Jones --- src/include/cbmem.h | 2 + src/include/imd.h | 139 +++++++++++++++ src/lib/Makefile.inc | 3 + src/lib/imd.c | 481 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 625 insertions(+) create mode 100644 src/include/imd.h create mode 100644 src/lib/imd.c diff --git a/src/include/cbmem.h b/src/include/cbmem.h index fdcb829b83..38f9d0320b 100644 --- a/src/include/cbmem.h +++ b/src/include/cbmem.h @@ -57,6 +57,7 @@ #define CBMEM_ID_GDT 0x4c474454 #define CBMEM_ID_HOB_POINTER 0x484f4221 #define CBMEM_ID_IGD_OPREGION 0x4f444749 +#define CBMEM_ID_IMD_ROOT 0xff4017ff #define CBMEM_ID_MEMINFO 0x494D454D #define CBMEM_ID_MPTABLE 0x534d5054 #define CBMEM_ID_MRCDATA 0x4d524344 @@ -103,6 +104,7 @@ struct cbmem_id_to_name { { CBMEM_ID_ELOG, "ELOG " }, \ { CBMEM_ID_FREESPACE, "FREE SPACE " }, \ { CBMEM_ID_GDT, "GDT " }, \ + { CBMEM_ID_IMD_ROOT, "IMD ROOT " }, \ { CBMEM_ID_MEMINFO, "MEM INFO " }, \ { CBMEM_ID_MPTABLE, "SMP TABLE " }, \ { CBMEM_ID_MRCDATA, "MRC DATA " }, \ diff --git a/src/include/imd.h b/src/include/imd.h new file mode 100644 index 0000000000..8d5c4522b7 --- /dev/null +++ b/src/include/imd.h @@ -0,0 +1,139 @@ +/* + * 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. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc. + */ + +#ifndef _IMD_H_ +#define _IMD_H_ + +#include +#include + +/* + * imd is an in-memory database/directory/datastore (whatever d word you + * desire). It grows downwards in memory from provided upper limit and + * root size. Each entry has a size alignment which is also provided by + * the caller. + * + * +----------------------+ <- upper_limit + * | +----| root pointer | + * | | +----------------------+ + * | | | |--------+ + * | +--->| root block |-----+ | + * | +----------------------+-----|--|--- root_size + * | | | | | + * | | | | | + * | | alloc N |<----+ | + * | +----------------------+ | + * | | | | + * | | | | + * \|/ | alloc N + 1 |<-------+ + * v +----------------------+ + * + * The root_size in imd_create_empty() encompasses the root pointer + * and root block. The root_size value, therefore, dictates the number + * of allocations maintained by the imd. + */ + +/* + * NOTE: This API has the following calling conventions: all functions + * returning int supply 0 on success or < 0 on error. + */ + +struct imd_entry; +struct imd; + +/* + * Initialize handle to use for working with an imd. Upper limit is the + * exclusive address to start allocating down from. This function needs + * to be called at least once before any other imd related functions + * can be used. + */ +void imd_handle_init(struct imd *imd, void *upper_limit); + +/* + * Initialize a handle with a shallow recovery. This function doesn't + * verify every entry, but it does set up the root pointer. Because of + * this behavior it's not very safe. However, the current CBMEM constraints + * demand having these semantics. + */ +void imd_handle_init_partial_recovery(struct imd *imd); + +/* + * Create an empty imd with a specified root_size and each entry is aligned to + * the provided entry_align. As noted above the root size encompasses the + * root pointer and root block leading to the number of imd entries being a + * function of the root_size parameter. + */ +int imd_create_empty(struct imd *imd, size_t root_size, size_t entry_align); + +/* + * Recover a previously created imd. + */ +int imd_recover(struct imd *imd); + +/* Limit imd to provided max_size. */ +int imd_limit_size(struct imd *imd, size_t max_size); + +/* Lock down imd from further modifications. */ +int imd_lockdown(struct imd *imd); + +/* Fill in base address and size of region used by imd. */ +int imd_region_used(struct imd *imd, void **base, size_t *size); + +/* Add an entry to the imd. If id already exists NULL is returned. */ +const struct imd_entry *imd_entry_add(const struct imd *imd, uint32_t id, + size_t size); + +/* Locate an entry within the imd. NULL is returned when not found. */ +const struct imd_entry *imd_entry_find(const struct imd *imd, uint32_t id); + +/* Find an existing entry or add a new one. */ +const struct imd_entry *imd_entry_find_or_add(const struct imd *imd, + uint32_t id, size_t size); + +/* Returns size of entry or 0 on failure. */ +size_t imd_entry_size(const struct imd *imd, const struct imd_entry *entry); + +/* Returns pointer to region described by entry or NULL on failure. */ +void *imd_entry_at(const struct imd *imd, const struct imd_entry *entry); + +/* Attempt to remove entry from imd. */ +int imd_entry_remove(const struct imd *imd, const struct imd_entry *entry); + +/* Print the entry information provided by lookup with the specified size. */ +struct imd_lookup { + uint32_t id; + const char *name; +}; + +int imd_print_entries(const struct imd *imd, const struct imd_lookup *lookup, + size_t size); + + +/* + * The struct imd is a handle for working with an in-memory directory. + * + * NOTE: Do not directly touch any fields within this structure. An imd pointer + * is meant to be opaque, but the fields are exposed for stack allocation. + */ +struct imd { + uintptr_t limit; + void *r; +}; + +#endif /* _IMD_H_ */ diff --git a/src/lib/Makefile.inc b/src/lib/Makefile.inc index 19ff2b291a..5c715d7a61 100644 --- a/src/lib/Makefile.inc +++ b/src/lib/Makefile.inc @@ -102,6 +102,9 @@ ramstage-y += b64_decode.c romstage-y += cbmem_common.c dynamic_cbmem.c ramstage-y += cbmem_common.c dynamic_cbmem.c +romstage-y += imd.c +ramstage-y += imd.c + ramstage-y += hexdump.c romstage-y += hexdump.c diff --git a/src/lib/imd.c b/src/lib/imd.c new file mode 100644 index 0000000000..ff3aa75a64 --- /dev/null +++ b/src/lib/imd.c @@ -0,0 +1,481 @@ +/* + * 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. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc. + */ + +#include +#include +#include +#include +#include +#include + +/* 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 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; +} __attribute__((packed)); + +struct imd_entry { + uint32_t magic; + /* start is located relative to imd_root */ + int32_t start_offset; + uint32_t size; + uint32_t id; +} __attribute__((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]; +} __attribute__((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 *imd_root(const struct imd *imd) +{ + return imd->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 *imd_get_root_pointer(const struct imd *imd) +{ + struct imd_root_pointer *rp; + + rp = relative_pointer((void *)imd->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 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 bool root_is_locked(const struct imd_root *r) +{ + return !!(r->flags & IMD_FLAG_LOCKED); +} + +static struct imd_entry *root_last_entry(struct imd_root *r) +{ + return &r->entries[r->num_entries - 1]; +} + +/* Initialize imd handle. */ +void imd_handle_init(struct imd *imd, void *upper_limit) +{ + uintptr_t limit = (uintptr_t)upper_limit; + /* Upper limit is aligned down to 4KiB */ + imd->limit = ALIGN_DOWN(limit, LIMIT_ALIGN); + imd->r = NULL; +} + +void imd_handle_init_partial_recovery(struct imd *imd) +{ + struct imd_root_pointer *rp; + + imd_handle_init(imd, (void *)imd->limit); + + rp = imd_get_root_pointer(imd); + imd->r = relative_pointer(rp, rp->root_offset); +} + +int imd_create_empty(struct imd *imd, 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; + size_t entries_size; + + if (!imd->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)); + + /* + * root_size needs to be large enough to accomodate 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 = imd_get_root_pointer(imd); + + root_offset = -(ssize_t)root_size; + /* Set root pointer. */ + imd->r = relative_pointer((void *)imd->limit, root_offset); + r = imd_root(imd); + imd_link_root(rp, r); + + memset(r, 0, sizeof(*r)); + r->entry_align = entry_align; + + /* Calculate size left for entries. */ + entries_size = root_size; + entries_size -= sizeof(*rp); + entries_size -= sizeof(*r); + + r->max_entries = entries_size / sizeof(r->entries[0]); + + /* 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; +} + +int imd_limit_size(struct imd *imd, size_t max_size) +{ + struct imd_root *r; + ssize_t smax_size; + size_t root_size; + + r = imd_root(imd); + if (r == NULL) + return -1; + + root_size = imd->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; +} + +int imd_recover(struct imd *imd) +{ + struct imd_root_pointer *rp; + struct imd_root *r; + uintptr_t low_limit; + size_t i; + + if (!imd->limit); + return -1; + + rp = imd_get_root_pointer(imd); + + 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) != + imd->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 >= imd->limit || + (start_addr + e->size) > imd->limit) + return -1; + } + + /* Set root pointer. */ + imd->r = r; + + return 0; +} + +int imd_lockdown(struct imd *imd) +{ + struct imd_root *r; + + r = imd_root(imd); + if (r == NULL) + return -1; + + 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->limit) + return -1; + + r = imd_root(imd); + + 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->limit - (uintptr_t)low_addr; + + *base = low_addr; + *size = sz_used; + + return 0; +} + +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); + + last_entry = root_last_entry(r); + + /* See if size overflows imd total size. */ + if (r->max_offset != 0) { + size_t remaining = last_entry->start_offset - r->max_offset; + + if (used_size > remaining) + return NULL; + } + + /* + * Determine if offset field overflows. All offsets should be lower + * than the previous one. + */ + 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; +} + +const struct imd_entry *imd_entry_add(const struct imd *imd, uint32_t id, + size_t size) +{ + struct imd_root *r; + + r = imd_root(imd); + + if (r == NULL) + return NULL; + + if (root_is_locked(r)) + return NULL; + + return imd_entry_add_to_root(r, id, size); +} + +const struct imd_entry *imd_entry_find(const struct imd *imd, uint32_t id) +{ + struct imd_root *r; + struct imd_entry *e; + size_t i; + + r = imd_root(imd); + + 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) { + e = &r->entries[i]; + break; + } + } + + 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 entry->size; +} + +void *imd_entry_at(const struct imd *imd, const struct imd_entry *entry) +{ + struct imd_root *r; + + r = imd_root(imd); + + if (r == NULL) + return NULL; + + return relative_pointer(r, entry->start_offset); +} + +int imd_entry_remove(const struct imd *imd, const struct imd_entry *entry) +{ + struct imd_root *r; + + r = imd_root(imd); + + 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; +} + +int imd_print_entries(const struct imd *imd, const struct imd_lookup *lookup, + size_t size) +{ + struct imd_root *r; + size_t i; + size_t j; + + if (imd == NULL) + return -1; + + r = imd_root(imd); + + if (r == NULL) + return -1; + + 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; + } + } + + if (name == NULL) + printk(BIOS_DEBUG, "%08x ", e->id); + else + printk(BIOS_DEBUG, "%s", name); + printk(BIOS_DEBUG, "%2zu. ", i); + printk(BIOS_DEBUG, "%p ", imd_entry_at(imd, e)); + printk(BIOS_DEBUG, "%08zx\n", imd_entry_size(imd, e)); + } + + return 0; +} -- cgit v1.2.3