[coreboot-gerrit] New patch to review for coreboot: 2006b1e lib: add memrange infrastructure
Aaron Durbin (adurbin@google.com)
gerrit at coreboot.org
Sat Mar 23 06:44:45 CET 2013
Aaron Durbin (adurbin at google.com) just uploaded a new patch set to gerrit, which you can find at http://review.coreboot.org/2888
-gerrit
commit 2006b1e08b8cfab4645c0b415e13cc9d8b0935bc
Author: Aaron Durbin <adurbin at chromium.org>
Date: Fri Mar 22 20:44:46 2013 -0500
lib: add memrange infrastructure
The memrange infrastructure allows for keeping track of the
machine's physical address space. Each memory_range entry in
a memory_ranges structure can be tagged with an arbitrary value.
It supports merging and deleting ranges as well as filling in
holes in the address space with a particular tag.
The memrange infrastructure will serve as a shared implementation
for address tracking by the MTRR and coreboot mem table code.
Change-Id: Id5bea9d2a419114fca55c59af0fdca063551110e
Signed-off-by: Aaron Durbin <adurbin at chromium.org>
---
src/include/memrange.h | 101 +++++++++++++++++
src/lib/Makefile.inc | 1 +
src/lib/memrange.c | 293 +++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 395 insertions(+)
diff --git a/src/include/memrange.h b/src/include/memrange.h
new file mode 100644
index 0000000..f087c83
--- /dev/null
+++ b/src/include/memrange.h
@@ -0,0 +1,101 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2013 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 MEMRANGE_H_
+#define MEMRANGE_H_
+
+#include <device/resource.h>
+#include <list.h>
+
+/* Each memory_range covers the inclusive addresses of [begin, end]. Even
+ * though the fields are exposed in this header file the wrapper functions
+ * below should be used for obtaining base, end, and size for forward API
+ * compatibility. */
+struct memory_range {
+ resource_t begin;
+ resource_t end;
+ struct list_head siblings;
+ unsigned long tag;
+};
+
+/* A memory_ranges structure consists of a list of memory_range(s). */
+struct memory_ranges {
+ struct list_head list;
+};
+
+/* Return inclusive base address of memory range. */
+static inline resource_t memory_range_base(const struct memory_range *r)
+{
+ return r->begin;
+}
+
+/* Return exclusive end address of memory range. */
+static inline resource_t memory_range_end(const struct memory_range *r)
+{
+ return r->end + 1;
+}
+
+/* Return size of of memory range. */
+static inline resource_t memory_range_size(const struct memory_range *r)
+{
+ return r->end - r->begin + 1;
+}
+
+static inline unsigned long memory_range_tag(const struct memory_range *r)
+{
+ return r->tag;
+}
+
+/* Iterate over each entry in a memory_ranges structure. Ranges cannot
+ * be deleted while processing each entry as the list cannot be safely
+ * traversed after such an operation.
+ * r - memory_range pointer.
+ * ranges - memory_rnages pointer */
+#define memory_ranges_each_entry(r, ranges) \
+ list_for_each_entry(r, &(ranges)->list, siblings)
+
+/* Initialize and fill a memory_ranges structure according to the
+ * mask and match type for all memory resources. Tag each entry with the
+ * specified type. */
+void memory_ranges_init(struct memory_ranges *ranges,
+ unsigned long mask, unsigned long match,
+ unsigned long tag);
+
+/* Remove and free all entries within the memory_ranges structure. */
+void memory_ranges_teardown(struct memory_ranges *ranges);
+
+/* Add memory resources that match with the corresponding mask and match.
+ * Each entry will be tagged with the provided tag. */
+void memory_ranges_add_resources(struct memory_ranges *ranges,
+ unsigned long mask, unsigned long match,
+ unsigned long tag);
+
+/* Fill all address ranges not covered by an entry associated with tag. */
+void memory_ranges_fill_holes(struct memory_ranges *ranges, unsigned long tag);
+
+/* Delete a resource from the given memory_ranges. */
+void delete_memory_range(struct memory_ranges *ranges,
+ resource_t base, resource_t size);
+
+/* Insert a resource to the given memory_ranges. All existing ranges
+ * covered by range specified by base and size will be removed before a
+ * new one is added. */
+void insert_memory_range(struct memory_ranges *ranges,
+ resource_t base, resource_t size, unsigned long tag);
+
+#endif /* MEMRANGE_H_ */
diff --git a/src/lib/Makefile.inc b/src/lib/Makefile.inc
index 6193e63..e8ed4f4 100644
--- a/src/lib/Makefile.inc
+++ b/src/lib/Makefile.inc
@@ -85,6 +85,7 @@ ramstage-$(CONFIG_TRACE) += trace.c
ramstage-$(CONFIG_COLLECT_TIMESTAMPS) += timestamp.c
ramstage-$(CONFIG_COVERAGE) += libgcov.c
ramstage-$(CONFIG_MAINBOARD_DO_NATIVE_VGA_INIT) += edid.c
+ramstage-y += memrange.c
# The CBMEM implementations are chosen based on CONFIG_DYNAMIC_CBMEM.
ifeq ($(CONFIG_DYNAMIC_CBMEM),y)
diff --git a/src/lib/memrange.c b/src/lib/memrange.c
new file mode 100644
index 0000000..027d860
--- /dev/null
+++ b/src/lib/memrange.c
@@ -0,0 +1,293 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2013 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 <stdlib.h>
+#include <console/console.h>
+#include <memrange.h>
+
+/* Coreboot doesn't have a free() function. Therefore, keep a cache of
+ * free'd entries. */
+static LIST_HEAD(free_list);
+
+static inline void memory_range_unlink(struct memory_range *r)
+{
+ list_del_init(&r->siblings);
+}
+
+static struct memory_range *alloc_range(void)
+{
+ if (!list_empty(&free_list)) {
+ struct memory_range *r;
+
+ r = list_first_entry(&free_list, struct memory_range, siblings);
+ memory_range_unlink(r);
+ return r;
+ }
+ return malloc(sizeof(struct memory_range));
+}
+
+static void memory_range_free(struct memory_range *e)
+{
+ if (!list_empty(&e->siblings))
+ printk(BIOS_ERR, "Freeing linked memory_range!\n");
+ list_add(&free_list, &e->siblings);
+}
+
+static inline struct memory_range *
+range_list_add(struct list_head *head, resource_t begin, resource_t end,
+ unsigned long tag)
+{
+ struct memory_range *new_entry;
+
+ new_entry = alloc_range();
+ if (new_entry == NULL) {
+ printk(BIOS_ERR, "Could not allocate memory_range!\n");
+ return NULL;
+ }
+ new_entry->begin = begin;
+ new_entry->end = end;
+ new_entry->tag = tag;
+ list_add(&new_entry->siblings, head);
+
+ return new_entry;
+}
+
+static void merge_neighbor_entries(struct memory_ranges *ranges)
+{
+ struct memory_range *cur;
+ struct memory_range *prev;
+ struct memory_range *tmp;
+
+ prev = NULL;
+ /* Merge all neighbors and delete/free the leftover entry. */
+ list_for_each_entry_safe(cur, tmp, &ranges->list, siblings) {
+ /* First entry. Just set prev. */
+ if (prev == NULL) {
+ prev = cur;
+ continue;
+ }
+
+ /* If the previous entry merges with the current update the
+ * previous entry to cover full range and delete current from
+ * the list. */
+ if (prev->end + 1 >= cur->begin && prev->tag == cur->tag) {
+ prev->end = cur->end;
+ memory_range_unlink(cur);
+ memory_range_free(cur);
+ continue;
+ }
+
+ prev = cur;
+ }
+}
+
+static void remove_memory_range(struct memory_ranges *ranges,
+ resource_t begin, resource_t end,
+ unsigned long unused)
+{
+ struct memory_range *cur;
+ struct memory_range *tmp;
+
+ list_for_each_entry_safe(cur, tmp, &ranges->list, siblings) {
+ resource_t tmp_end;
+
+ /* No other ranges are affected. */
+ if (end < cur->begin)
+ break;
+
+ /* The removal range starts after this one. */
+ if (begin > cur->end)
+ continue;
+
+ /* The removal range overlaps with the current entry either
+ * partially or fully. However, we need to adjust the removal
+ * range for any holes. */
+ if (begin <= cur->begin) {
+ begin = cur->begin;
+
+ /* Full removal. */
+ if (end >= cur->end) {
+ begin = cur->end + 1;
+ memory_range_unlink(cur);
+ memory_range_free(cur);
+ continue;
+ }
+ }
+
+ /* Clip the end fragment to do proper splitting. */
+ tmp_end = end;
+ if (end > cur->end)
+ tmp_end = cur->end;
+
+ /* Hole punched in middle of entry. */
+ if (begin > cur->begin && tmp_end < cur->end) {
+ range_list_add(&cur->siblings, end + 1, cur->end,
+ cur->tag);
+ cur->end = begin - 1;
+ continue;
+ }
+
+ /* Removal at beginning. */
+ if (begin == cur->begin)
+ cur->begin = tmp_end + 1;
+
+ /* Removal at end. */
+ if (tmp_end == cur->end)
+ cur->end = begin - 1;
+ }
+}
+
+static void merge_add_memory_range(struct memory_ranges *ranges,
+ resource_t begin, resource_t end,
+ unsigned long tag)
+{
+ struct memory_range *cur;
+ struct list_head *head;
+
+ head = &ranges->list;
+
+ /* Remove all existing entries covered by the range. */
+ remove_memory_range(ranges, begin, end, -1);
+
+ /* Find the entry to place the new entry after. Since
+ * remove_memory_range() was called above there is a guranteed
+ * spot for this new entry. */
+ list_for_each_entry(cur, &ranges->list, siblings) {
+ /* Found insertion spot before current entry. */
+ if (end < cur->begin)
+ break;
+
+ /* Keep track of previous entry to insert new entry after it. */
+ head = &cur->siblings;
+
+ /* The new entry starts after this one. */
+ if (begin > cur->end)
+ continue;
+
+ }
+
+ /* Add new entry and merge with neighbors. */
+ range_list_add(head, begin, end, tag);
+ merge_neighbor_entries(ranges);
+}
+
+typedef void (*range_action_t)(struct memory_ranges *ranges,
+ resource_t begin, resource_t end,
+ unsigned long tag);
+
+static void do_action(struct memory_ranges *ranges,
+ resource_t base, resource_t size, unsigned long tag,
+ range_action_t action)
+{
+ resource_t end;
+ resource_t begin;
+
+ /* The addresses are aligned to 4096 bytes: the begin address is
+ * aligned down while the end address is aligned up to be conservative
+ * about the full range covered. */
+ begin = round_down(base, 4096);
+ end = begin + size + (base - begin);
+ end = round_up(end, 4096) - 1;
+ action(ranges, begin, end, tag);
+}
+
+void delete_memory_range(struct memory_ranges *ranges,
+ resource_t base, resource_t size)
+{
+ do_action(ranges, base, size, -1, remove_memory_range);
+}
+
+void insert_memory_range(struct memory_ranges *ranges,
+ resource_t base, resource_t size, unsigned long tag)
+{
+ do_action(ranges, base, size, tag, merge_add_memory_range);
+}
+
+struct collect_context {
+ struct memory_ranges *ranges;
+ unsigned long tag;
+};
+
+static void collect_ranges(void *gp, struct device *dev, struct resource *res)
+{
+ struct collect_context *ctx = gp;
+
+ insert_memory_range(ctx->ranges, res->base, res->size, ctx->tag);
+}
+
+void memory_ranges_add_resources(struct memory_ranges *ranges,
+ unsigned long mask, unsigned long match,
+ unsigned long tag)
+{
+ struct collect_context context;
+
+ /* Only deal with MEM resources. */
+ mask |= IORESOURCE_MEM;
+ match |= IORESOURCE_MEM;
+
+ context.ranges = ranges;
+ context.tag = tag;
+ search_global_resources(mask, match, collect_ranges, &context);
+}
+
+void memory_ranges_init(struct memory_ranges *ranges,
+ unsigned long mask, unsigned long match,
+ unsigned long tag)
+{
+ INIT_LIST_HEAD(&ranges->list);
+
+ memory_ranges_add_resources(ranges, mask, match, tag);
+}
+
+void memory_ranges_teardown(struct memory_ranges *ranges)
+{
+ struct memory_range *cur;
+ struct memory_range *tmp;
+
+ /* Merge all neighbors and delete/free the leftover entry. */
+ list_for_each_entry_safe(cur, tmp, &ranges->list, siblings) {
+ memory_range_unlink(cur);
+ memory_range_free(cur);
+ }
+}
+
+void memory_ranges_fill_holes(struct memory_ranges *ranges, unsigned long tag)
+{
+ struct memory_range *cur;
+ struct memory_range *prev;
+ struct memory_range *tmp;
+
+ prev = NULL;
+ list_for_each_entry_safe(cur, tmp, &ranges->list, siblings) {
+ /* First entry. Just set prev. */
+ if (prev == NULL) {
+ prev = cur;
+ continue;
+ }
+
+ /* If the previous entry does not directly preceed the current
+ * entry then add a new entry just after the previous one. */
+ if (prev->end + 1 != cur->begin)
+ range_list_add(&prev->siblings, prev->end + 1,
+ cur->begin - 1, tag);
+
+ prev = cur;
+ }
+ /* Merge all entries that were newly added. */
+ merge_neighbor_entries(ranges);
+}
More information about the coreboot-gerrit
mailing list