/* ----------------------------------------------------------------------- *
 *
 *   Copyright 2007-2009 H. Peter Anvin - All Rights Reserved
 *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
 *
 *   Permission is hereby granted, free of charge, to any person
 *   obtaining a copy of this software and associated documentation
 *   files (the "Software"), to deal in the Software without
 *   restriction, including without limitation the rights to use,
 *   copy, modify, merge, publish, distribute, sublicense, and/or
 *   sell copies of the Software, and to permit persons to whom
 *   the Software is furnished to do so, subject to the following
 *   conditions:
 *
 *   The above copyright notice and this permission notice shall
 *   be included in all copies or substantial portions of the Software.
 *
 *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 *   OTHER DEALINGS IN THE SOFTWARE.
 *
 * ----------------------------------------------------------------------- */

/*
 * zonelist.c
 *
 * Deal with syslinux_memmap's, which are data structures designed to
 * hold memory maps.  A zonelist is a sorted linked list of memory
 * ranges, with the guarantee that no two adjacent blocks have the
 * same range type.  Additionally, all unspecified memory have a range
 * type of zero.
 */

#include <stdlib.h>
#include <syslinux/align.h>
#include <syslinux/movebits.h>
#include <dprintf.h>

/*
 * Create an empty syslinux_memmap list.
 */
struct syslinux_memmap *syslinux_init_memmap(void)
{
    struct syslinux_memmap *sp, *ep;

    sp = malloc(sizeof(*sp));
    if (!sp)
	return NULL;

    ep = malloc(sizeof(*ep));
    if (!ep) {
	free(sp);
	return NULL;
    }

    sp->start = 0;
    sp->type = SMT_UNDEFINED;
    sp->next = ep;

    ep->start = 0;		/* Wrap around... */
    ep->type = SMT_END;		/* End of chain */
    ep->next = NULL;

    return sp;
}

/*
 * Add an item to a syslinux_memmap list, potentially overwriting
 * what is already there.
 */
int syslinux_add_memmap(struct syslinux_memmap **list,
			addr_t start, addr_t len,
			enum syslinux_memmap_types type)
{
    addr_t last;
    struct syslinux_memmap *mp, **mpp;
    struct syslinux_memmap *range;
    enum syslinux_memmap_types oldtype;

    dprintf("Input memmap:\n");
    syslinux_dump_memmap(*list);

    /* Remove this to make len == 0 mean all of memory */
    if (len == 0)
	return 0;

    /* Last byte -- to avoid rollover */
    last = start + len - 1;

    mpp = list;
    oldtype = SMT_END;		/* Impossible value */
    while (mp = *mpp, start > mp->start && mp->type != SMT_END) {
	oldtype = mp->type;
	mpp = &mp->next;
    }

    if (start < mp->start || mp->type == SMT_END) {
	if (type != oldtype) {
	    /* Splice in a new start token */
	    range = malloc(sizeof(*range));
	    if (!range)
		return -1;

	    range->start = start;
	    range->type = type;
	    *mpp = range;
	    range->next = mp;
	    mpp = &range->next;
	}
    } else {
	/* mp is exactly aligned with the start of our region */
	if (type != oldtype) {
	    /* Reclaim this entry as our own boundary marker */
	    oldtype = mp->type;
	    mp->type = type;
	    mpp = &mp->next;
	}
    }

    while (mp = *mpp, last > mp->start - 1) {
	oldtype = mp->type;
	*mpp = mp->next;
	free(mp);
    }

    if (last < mp->start - 1) {
	if (oldtype != type) {
	    /* Need a new end token */
	    range = malloc(sizeof(*range));
	    if (!range)
		return -1;

	    range->start = last + 1;
	    range->type = oldtype;
	    *mpp = range;
	    range->next = mp;
	}
    } else {
	if (mp->type == type) {
	    /* Merge this region with the following one */
	    *mpp = mp->next;
	    free(mp);
	}
    }

    dprintf("After adding (%#x,%#x,%d):\n", start, len, type);
    syslinux_dump_memmap(*list);

    return 0;
}

/*
 * Verify what type a certain memory region is.  This function returns
 * SMT_ERROR if the memory region has multiple types, except that
 * SMT_FREE can be demoted to SMT_TERMINAL.
 */
enum syslinux_memmap_types syslinux_memmap_type(struct syslinux_memmap *list,
						addr_t start, addr_t len)
{
    addr_t last, llast;

    last = start + len - 1;

    while (list->type != SMT_END) {
	llast = list->next->start - 1;
	if (list->start <= start) {
	    if (llast >= last) {
		return list->type;	/* Region has a well-defined type */
	    } else if (llast >= start) {
		/* Crosses region boundary */
		while (valid_terminal_type(list->type)) {
		    list = list->next;
		    llast = list->next->start - 1;
		    if (llast >= last)
			return SMT_TERMINAL;
		}
		return SMT_ERROR;
	    }
	}
	list = list->next;
    }

    return SMT_ERROR;		/* Internal error? */
}

/*
 * Find the largest zone of a specific type.  Returns -1 on failure.
 */
int syslinux_memmap_largest(struct syslinux_memmap *list,
			    enum syslinux_memmap_types type,
			    addr_t * start, addr_t * len)
{
    addr_t size, best_size = 0;
    struct syslinux_memmap *best = NULL;

    while (list->type != SMT_END) {
	size = list->next->start - list->start;

	if (list->type == type && size > best_size) {
	    best = list;
	    best_size = size;
	}

	list = list->next;
    }

    if (!best)
	return -1;

    *start = best->start;
    *len = best_size;

    return 0;
}

/*
 * Find the highest zone of a specific type that satisfies the
 * constraints.
 *
 * 'start' is updated with the highest address on success. 'start' can
 * be used to set a minimum address to begin searching from.
 *
 * Returns -1 on failure.
 */
int syslinux_memmap_highest(const struct syslinux_memmap *list,
			    enum syslinux_memmap_types type,
			    addr_t *start, addr_t len,
			    addr_t ceiling, addr_t align)
{
    addr_t size, best;

    for (best = 0; list->type != SMT_END; list = list->next) {
	size = list->next->start - list->start;

	if (list->type != type)
	    continue;

	if (list->start + size <= *start)
	    continue;

	if (list->start + len >= ceiling)
	    continue;

	if (list->start + size < ceiling)
	    best = ALIGN_DOWN(list->start + size - len, align);
	else
	    best = ALIGN_DOWN(ceiling - len, align);

	if (best < *start)
	    best = 0;
    }

    if (!best)
	return -1;

    *start = best;

    return 0;
}

/*
 * Find the first (lowest address) zone of a specific type and of
 * a certain minimum size, with an optional starting address.
 * The input values of start and len are used as minima.
 */
int syslinux_memmap_find_type(struct syslinux_memmap *list,
			      enum syslinux_memmap_types type,
			      addr_t * start, addr_t * len, addr_t align)
{
    addr_t min_start = *start;
    addr_t min_len = *len;

    while (list->type != SMT_END) {
	if (list->type == type) {
	    addr_t xstart, xlen;
	    xstart = min_start > list->start ? min_start : list->start;
	    xstart = ALIGN_UP(xstart, align);

	    if (xstart < list->next->start) {
		xlen = list->next->start - xstart;
		if (xlen >= min_len) {
		    *start = xstart;
		    *len = xlen;
		    return 0;
		}
	    }
	}
	list = list->next;
    }

    return -1;			/* Not found */
}

/*
 * Free a zonelist.
 */
void syslinux_free_memmap(struct syslinux_memmap *list)
{
    struct syslinux_memmap *ml;

    while (list) {
	ml = list;
	list = list->next;
	free(ml);
    }
}

/*
 * Duplicate a zonelist.  Returns NULL on failure.
 */
struct syslinux_memmap *syslinux_dup_memmap(struct syslinux_memmap *list)
{
    struct syslinux_memmap *newlist = NULL, **nlp = &newlist;
    struct syslinux_memmap *ml;

    while (list) {
	ml = malloc(sizeof(*ml));
	if (!ml) {
	    syslinux_free_memmap(newlist);
	    return NULL;
	}
	ml->start = list->start;
	ml->type = list->type;
	ml->next = NULL;
	*nlp = ml;
	nlp = &ml->next;

	list = list->next;
    }

    return newlist;
}

/*
 * Find a memory region, given a set of heuristics and update 'base' if
 * successful.
 */
int syslinux_memmap_find(struct syslinux_memmap *mmap,
			 addr_t *base, size_t size,
			 bool relocate, size_t align,
			 addr_t start_min, addr_t start_max,
			 addr_t end_min, addr_t end_max)
{
    const struct syslinux_memmap *mp;
    enum syslinux_memmap_types type;
    bool ok;

    if (!size)
	return 0;

    type = syslinux_memmap_type(mmap, *base, size);

    /* This assumes SMT_TERMINAL is OK if we can get the exact address */
    if (valid_terminal_type(type))
	return 0;

    if (!relocate) {
	dprintf("Cannot relocate\n");
	return -1;
    }

    ok = false;
    for (mp = mmap; mp && mp->type != SMT_END; mp = mp->next) {
	addr_t start, end;
	start = mp->start;
	end = mp->next->start;

	if (mp->type != SMT_FREE)
	    continue;

	/* min */
	if (end <= end_min)
	    continue;	/* Only relocate upwards */

	if (start < start_min)
	    start = start_min;

	/* max */
	if (end > end_max)
	    end = end_max;

	start = ALIGN_UP(start, align);
	if (start > start_max || start >= end)
	    continue;

	if (end - start >= size) {
	    *base = start;
	    ok = true;
	    break;
	}
    }

    if (!ok)
	return -1;

    return 0;
}