src/lib/memrange.c

/* SPDX-License-Identifier: GPL-2.0-only */

#include <assert.h>
#include <stdlib.h>
#include <commonlib/helpers.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_PAYLOAD_LOADER)
		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 (1ULL << ranges->align): 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, POWER_OF_2(ranges->align));
	end = begin + size + (base - begin);
	end = ALIGN_UP(end, POWER_OF_2(ranges->align)) - 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_with_alignment(struct memranges *ranges,
					 struct range_entry *to_free,
					 size_t num_free, unsigned char align)
{
	size_t i;

	ranges->entries = NULL;
	ranges->free_list = NULL;
	ranges->align = align;

	for (i = 0; i < num_free; i++)
		range_entry_link(&ranges->free_list, &to_free[i]);
}

void memranges_init_with_alignment(struct memranges *ranges,
				   unsigned long mask, unsigned long match,
				   unsigned long tag, unsigned char align)
{
	memranges_init_empty_with_alignment(ranges, NULL, 0, align);
	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_with_alignment(newranges, NULL, 0, oldranges->align);

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

/* Find a range entry that satisfies the given constraints to fit a hole that matches the
 * required alignment, is big enough, does not exceed the limit and has a matching tag. */
static const struct range_entry *
memranges_find_entry(struct memranges *ranges, resource_t limit, resource_t size,
		     unsigned char align, unsigned long tag, bool last)
{
	const struct range_entry *r, *last_entry = NULL;
	resource_t base, end;

	if (size == 0)
		return NULL;

	memranges_each_entry(r, ranges) {
		if (r->tag != tag)
			continue;

		base = ALIGN_UP(r->begin, POWER_OF_2(align));
		end = base + size - 1;

		if (end > r->end)
			continue;

		/*
		 * If end for the hole in the current range entry goes beyond the requested
		 * limit, then none of the following ranges can satisfy this request because all
		 * range entries are maintained in increasing order.
		 */
		if (end > limit)
			break;

		if (!last)
			return r;

		last_entry = r;
	}

	return last_entry;
}

bool memranges_steal(struct memranges *ranges, resource_t limit, resource_t size,
			unsigned char align, unsigned long tag, resource_t *stolen_base,
			bool from_top)
{
	const struct range_entry *r;

	r = memranges_find_entry(ranges, limit, size, align, tag, from_top);
	if (r == NULL)
		return false;

	if (from_top) {
		limit = MIN(limit, r->end);
		/* Ensure we're within the range, even aligned down.
		   Proof is simple: If ALIGN_UP(r->begin) would be
		   higher, the stolen range wouldn't fit.*/
		assert(r->begin <= ALIGN_DOWN(limit - size + 1, POWER_OF_2(align)));
		*stolen_base = ALIGN_DOWN(limit - size + 1, POWER_OF_2(align));
	} else {
		*stolen_base = ALIGN_UP(r->begin, POWER_OF_2(align));
	}
	memranges_create_hole(ranges, *stolen_base, size);

	return true;
}