/* * 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. */ #include <stdlib.h> #include <console/console.h> #include <memrange.h> static inline void range_entry_link(struct range_entry **prev_ptr, struct range_entry *r) { r->next = *prev_ptr; *prev_ptr = r; } static inline void range_entry_unlink(struct range_entry **prev_ptr, struct range_entry *r) { *prev_ptr = r->next; r->next = NULL; } static inline void range_entry_unlink_and_free(struct memranges *ranges, struct range_entry **prev_ptr, struct range_entry *r) { range_entry_unlink(prev_ptr, r); range_entry_link(&ranges->free_list, r); } static struct range_entry *alloc_range(struct memranges *ranges) { if (ranges->free_list != NULL) { struct range_entry *r; r = ranges->free_list; range_entry_unlink(&ranges->free_list, r); return r; } if (ENV_RAMSTAGE) return malloc(sizeof(struct range_entry)); return NULL; } static inline struct range_entry * range_list_add(struct memranges *ranges, struct range_entry **prev_ptr, resource_t begin, resource_t end, unsigned long tag) { struct range_entry *new_entry; new_entry = alloc_range(ranges); if (new_entry == NULL) { printk(BIOS_ERR, "Could not allocate range_entry!\n"); return NULL; } new_entry->begin = begin; new_entry->end = end; new_entry->tag = tag; range_entry_link(prev_ptr, new_entry); return new_entry; } static void merge_neighbor_entries(struct memranges *ranges) { struct range_entry *cur; struct range_entry *prev; prev = NULL; /* Merge all neighbors and delete/free the leftover entry. */ for (cur = ranges->entries; cur != NULL; cur = cur->next) { /* 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; range_entry_unlink_and_free(ranges, &prev->next, cur); /* Set cur to prev so cur->next is valid since cur * was just unlinked and free. */ cur = prev; continue; } prev = cur; } } static void remove_memranges(struct memranges *ranges, resource_t begin, resource_t end, unsigned long unused) { struct range_entry *cur; struct range_entry *next; struct range_entry **prev_ptr; prev_ptr = &ranges->entries; for (cur = ranges->entries; cur != NULL; cur = next) { resource_t tmp_end; /* Cache the next value to handle unlinks. */ next = cur->next; /* No other ranges are affected. */ if (end < cur->begin) break; /* The removal range starts after this one. */ if (begin > cur->end) { prev_ptr = &cur->next; 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; range_entry_unlink_and_free(ranges, prev_ptr, cur); continue; } } /* prev_ptr can be set now that the unlink path wasn't taken. */ prev_ptr = &cur->next; /* 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(ranges, &cur->next, end + 1, cur->end, cur->tag); cur->end = begin - 1; break; } /* 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_memranges(struct memranges *ranges, resource_t begin, resource_t end, unsigned long tag) { struct range_entry *cur; struct range_entry **prev_ptr; prev_ptr = &ranges->entries; /* Remove all existing entries covered by the range. */ remove_memranges(ranges, begin, end, -1); /* Find the entry to place the new entry after. Since * remove_memranges() was called above there is a guaranteed * spot for this new entry. */ for (cur = ranges->entries; cur != NULL; cur = cur->next) { /* Found insertion spot before current entry. */ if (end < cur->begin) break; /* Keep track of previous entry to insert new entry after it. */ prev_ptr = &cur->next; /* The new entry starts after this one. */ if (begin > cur->end) continue; } /* Add new entry and merge with neighbors. */ range_list_add(ranges, prev_ptr, begin, end, tag); merge_neighbor_entries(ranges); } void memranges_update_tag(struct memranges *ranges, unsigned long old_tag, unsigned long new_tag) { struct range_entry *r; memranges_each_entry(r, ranges) { if (range_entry_tag(r) == old_tag) range_entry_update_tag(r, new_tag); } merge_neighbor_entries(ranges); } typedef void (*range_action_t)(struct memranges *ranges, resource_t begin, resource_t end, unsigned long tag); static void do_action(struct memranges *ranges, resource_t base, resource_t size, unsigned long tag, range_action_t action) { resource_t end; resource_t begin; if (size == 0) return; /* 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 = ALIGN_DOWN(base, 4096); end = begin + size + (base - begin); end = ALIGN_UP(end, 4096) - 1; action(ranges, begin, end, tag); } void memranges_create_hole(struct memranges *ranges, resource_t base, resource_t size) { do_action(ranges, base, size, -1, remove_memranges); } void memranges_insert(struct memranges *ranges, resource_t base, resource_t size, unsigned long tag) { do_action(ranges, base, size, tag, merge_add_memranges); } struct collect_context { struct memranges *ranges; unsigned long tag; memrange_filter_t filter; }; static void collect_ranges(void *gp, struct device *dev, struct resource *res) { struct collect_context *ctx = gp; if (res->size == 0) return; if (ctx->filter == NULL || ctx->filter(dev, res)) memranges_insert(ctx->ranges, res->base, res->size, ctx->tag); } void memranges_add_resources_filter(struct memranges *ranges, unsigned long mask, unsigned long match, unsigned long tag, memrange_filter_t filter) { struct collect_context context; /* Only deal with MEM resources. */ mask |= IORESOURCE_MEM; match |= IORESOURCE_MEM; context.ranges = ranges; context.tag = tag; context.filter = filter; search_global_resources(mask, match, collect_ranges, &context); } void memranges_add_resources(struct memranges *ranges, unsigned long mask, unsigned long match, unsigned long tag) { memranges_add_resources_filter(ranges, mask, match, tag, NULL); } void memranges_init_empty(struct memranges *ranges, struct range_entry *to_free, size_t num_free) { size_t i; ranges->entries = NULL; ranges->free_list = NULL; for (i = 0; i < num_free; i++) range_entry_link(&ranges->free_list, &to_free[i]); } void memranges_init(struct memranges *ranges, unsigned long mask, unsigned long match, unsigned long tag) { memranges_init_empty(ranges, NULL, 0); memranges_add_resources(ranges, mask, match, tag); } /* Clone a memrange. The new memrange has the same entries as the old one. */ void memranges_clone(struct memranges *newranges, struct memranges *oldranges) { struct range_entry *r, *cur; struct range_entry **prev_ptr; memranges_init_empty(newranges, NULL, 0); prev_ptr = &newranges->entries; memranges_each_entry(r, oldranges) { cur = range_list_add(newranges, prev_ptr, r->begin, r->end, r->tag); prev_ptr = &cur->next; } } void memranges_teardown(struct memranges *ranges) { while (ranges->entries != NULL) { range_entry_unlink_and_free(ranges, &ranges->entries, ranges->entries); } } void memranges_fill_holes_up_to(struct memranges *ranges, resource_t limit, unsigned long tag) { struct range_entry *cur; struct range_entry *prev; prev = NULL; for (cur = ranges->entries; cur != NULL; cur = cur->next) { /* First entry. Just set prev. */ if (prev == NULL) { prev = cur; continue; } /* If the previous entry does not directly precede the current * entry then add a new entry just after the previous one. */ if (range_entry_end(prev) != cur->begin) { resource_t end; end = cur->begin - 1; if (end >= limit) end = limit - 1; range_list_add(ranges, &prev->next, range_entry_end(prev), end, tag); } prev = cur; /* Hit the requested range limit. No other entries after this * are affected. */ if (cur->begin >= limit) break; } /* Handle the case where the limit was never reached. A new entry needs * to be added to cover the range up to the limit. */ if (prev != NULL && range_entry_end(prev) < limit) range_list_add(ranges, &prev->next, range_entry_end(prev), limit - 1, tag); /* Merge all entries that were newly added. */ merge_neighbor_entries(ranges); } struct range_entry *memranges_next_entry(struct memranges *ranges, const struct range_entry *r) { return r->next; }