src/lib/memrange.c - chromiumos/third_party/coreboot - Git at Google

 /*
  * 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 struct range_entry *free_list;

 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 range_entry **prev_ptr,
                                                struct range_entry *r)
 {
 	range_entry_unlink(prev_ptr, r);
 	range_entry_link(&free_list, r);
 }

 static struct range_entry *alloc_range(void)
 {
 	if (free_list != NULL) {
 		struct range_entry *r;

 		r = free_list;
 		range_entry_unlink(&free_list, r);
 		return r;
 	}
 	return malloc(sizeof(struct range_entry));
 }

 static inline struct range_entry *
 range_list_add(struct range_entry **prev_ptr, resource_t begin, resource_t end,
                unsigned long tag)
 {
 	struct range_entry *new_entry;

 	new_entry = alloc_range();
 	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(&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(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(&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 guranteed
 	 * 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(prev_ptr, begin, end, 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;

 	/* 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;
 };

 static void collect_ranges(void *gp, struct device *dev, struct resource *res)
 {
 	struct collect_context *ctx = gp;

 	memranges_insert(ctx->ranges, res->base, res->size, ctx->tag);
 }

 void memranges_add_resources(struct memranges *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 memranges_init(struct memranges *ranges,
                     unsigned long mask, unsigned long match,
                     unsigned long tag)
 {
 	ranges->entries = NULL;
 	memranges_add_resources(ranges, mask, match, tag);
 }

 void memranges_teardown(struct memranges *ranges)
 {
 	while (ranges->entries != NULL) {
 		range_entry_unlink_and_free(&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 preceed 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(&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(&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;
 }
	/*
	* 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 struct range_entry *free_list;

	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 range_entry **prev_ptr,
	struct range_entry *r)
	{
	range_entry_unlink(prev_ptr, r);
	range_entry_link(&free_list, r);
	}

	static struct range_entry *alloc_range(void)
	{
	if (free_list != NULL) {
	struct range_entry *r;

	r = free_list;
	range_entry_unlink(&free_list, r);
	return r;
	}
	return malloc(sizeof(struct range_entry));
	}

	static inline struct range_entry *
	range_list_add(struct range_entry **prev_ptr, resource_t begin, resource_t end,
	unsigned long tag)
	{
	struct range_entry *new_entry;

	new_entry = alloc_range();
	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(&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(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(&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 guranteed
	* 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(prev_ptr, begin, end, 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;

	/* 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;
	};

	static void collect_ranges(void gp, struct device dev, struct resource *res)
	{
	struct collect_context *ctx = gp;

	memranges_insert(ctx->ranges, res->base, res->size, ctx->tag);
	}

	void memranges_add_resources(struct memranges *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 memranges_init(struct memranges *ranges,
	unsigned long mask, unsigned long match,
	unsigned long tag)
	{
	ranges->entries = NULL;
	memranges_add_resources(ranges, mask, match, tag);
	}

	void memranges_teardown(struct memranges *ranges)
	{
	while (ranges->entries != NULL) {
	range_entry_unlink_and_free(&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 preceed 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(&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(&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;
	}