403 lines
9.1 KiB
C
403 lines
9.1 KiB
C
/* ----------------------------------------------------------------------- *
|
|
*
|
|
* 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;
|
|
}
|