[coreboot-gerrit] Patch set updated for coreboot: 591c066 coreboot: imd library
Aaron Durbin (adurbin@google.com)
gerrit at coreboot.org
Sat Mar 7 06:51:44 CET 2015
Aaron Durbin (adurbin at google.com) just uploaded a new patch set to gerrit, which you can find at http://review.coreboot.org/8621
-gerrit
commit 591c0668f40817eb12a1aab8ed881f548b367c71
Author: Aaron Durbin <adurbin at chromium.org>
Date: Thu Mar 5 14:11:27 2015 -0600
coreboot: 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 aboslute pointers serialized to memory.
- Allow limiting the size of the idm. i.e. provide a maximum
memory usage.
- Allow limiting the size of the root structure for tracking entries.
Change-Id: Id7438cff80d396a594d6a7330d09b45bb4fedf2e
Signed-off-by: Aaron Durbin <adurbin at chromium.org>
---
src/include/imd.h | 126 ++++++++++++++
src/lib/Makefile.inc | 3 +
src/lib/imd.c | 457 +++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 586 insertions(+)
diff --git a/src/include/imd.h b/src/include/imd.h
new file mode 100644
index 0000000..918ce11
--- /dev/null
+++ b/src/include/imd.h
@@ -0,0 +1,126 @@
+/*
+ * 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _IMD_H_
+#define _IMD_H_
+
+#include <stdint.h>
+#include <stddef.h>
+
+/*
+ * 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 entryhas a size alignment which is also provided by
+ * the caller.
+ *
+ * +----------------------+ <- upper_limit
+ * | +----| root pointer |
+ * | | +----------------------+
+ * | | | |--------+
+ * | +--->| root block |-----+ |
+ * | +----------------------+-----|--|--- root_size
+ * | | | | |
+ * | | | | |
+ * | | alloc N |<----+ |
+ * | +----------------------+ |
+ * | | | |
+ * | | | |
+ * \|/ | alloc N + 1 |<-------+
+ * v +----------------------+
+ *
+ */
+
+/*
+ * 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);
+
+/*
+ * Create an empty imd with a specified root_size and each entry is aligned to
+ * the provided entry_align.
+ */
+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 9650fd5..0aa08e6 100644
--- a/src/lib/Makefile.inc
+++ b/src/lib/Makefile.inc
@@ -85,6 +85,9 @@ ramstage-$(CONFIG_TIMER_QUEUE) += timer_queue.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 0000000..18b0352
--- /dev/null
+++ b/src/lib/imd.c
@@ -0,0 +1,457 @@
+/*
+ * 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <assert.h>
+#include <console/console.h>
+#include <imd.h>
+#include <stdlib.h>
+#include <string.h>
+
+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 inline bool is_power_of_2(size_t v)
+{
+ return !!((v & -v) == v);
+}
+
+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;
+}
+
+static struct imd_root_pointer *imd_root_pointer(const struct imd *imd)
+{
+ struct imd_root_pointer *rp;
+
+ rp = (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)rp - (intptr_t)r);
+}
+
+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;
+}
+
+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;
+
+ /* 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_root_pointer(imd);
+
+ root_offset = root_size;
+ root_offset = -root_offset;
+ /* 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, 0xff4007ff, 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;
+
+ rp = imd_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;
+ size_t i;
+
+ 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);
+
+ /*
+ * This could be calculated differently, but it's easy to just
+ * loop through the entries accumulating their sizes.
+ */
+ for (i = 0, sz_used = 0; i < r->num_entries; i++)
+ sz_used += r->entries[i].size;
+
+ *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;
+
+ if (r->num_entries == r->max_entries)
+ return NULL;
+
+ 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 (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)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;
+
+ 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)
+ continue;
+ 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;
+
+ 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)
+ continue;
+
+ 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;
+}
More information about the coreboot-gerrit
mailing list