176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ----------------------------------------------------------------------- * 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Copyright 2007-2008 H. Peter Anvin - All Rights Reserved 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Copyright 2009 Intel Corporation; author: H. Peter Anvin 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Permission is hereby granted, free of charge, to any person 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * obtaining a copy of this software and associated documentation 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * files (the "Software"), to deal in the Software without 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * restriction, including without limitation the rights to use, 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * copy, modify, merge, publish, distribute, sublicense, and/or 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * sell copies of the Software, and to permit persons to whom 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the Software is furnished to do so, subject to the following 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * conditions: 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * The above copyright notice and this permission notice shall 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * be included in all copies or substantial portions of the Software. 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * OTHER DEALINGS IN THE SOFTWARE. 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * ----------------------------------------------------------------------- */ 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * movebits.c 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Utility function to take a list of memory areas to shuffle and 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * convert it to a set of shuffle operations. 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Note: a lot of the functions in this file deal with "parent pointers", 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * which are pointers to a pointer to a list, or part of the list. 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * They can be pointers to a variable holding the list root pointer, 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * or pointers to a next field of a previous entry. 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <assert.h> 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdio.h> 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <errno.h> 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdlib.h> 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <inttypes.h> 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <setjmp.h> 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <minmax.h> 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdbool.h> 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <syslinux/movebits.h> 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <dprintf.h> 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic jmp_buf new_movelist_bail; 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist *new_movelist(addr_t dst, addr_t src, 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t len) 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *ml = malloc(sizeof(struct syslinux_movelist)); 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!ml) 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman longjmp(new_movelist_bail, 1); 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->dst = dst; 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->src = src; 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->len = len; 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->next = NULL; 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return ml; 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist *dup_movelist(struct syslinux_movelist *src) 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *dst = NULL, **dstp = &dst, *ml; 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (src) { 7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml = new_movelist(src->dst, src->src, src->len); 7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *dstp = ml; 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dstp = &ml->next; 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman src = src->next; 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return dst; 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanadd_freelist(struct syslinux_memmap **mmap, addr_t start, 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t len, enum syslinux_memmap_types type) 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (syslinux_add_memmap(mmap, start, len, type)) 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman longjmp(new_movelist_bail, 1); 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Take a chunk, entirely confined in **parentptr, and split it off so that 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * it has its own structure. 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist **split_movelist(addr_t start, addr_t len, 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman **parentptr) 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *m, *ml = *parentptr; 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(start >= ml->src); 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(start < ml->src + ml->len); 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Split off the beginning */ 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (start > ml->src) { 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t l = start - ml->src; 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m = new_movelist(ml->dst + l, start, ml->len - l); 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m->next = ml->next; 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->len = l; 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->next = m; 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman parentptr = &ml->next; 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml = m; /* Continue processing the new node */ 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Split off the end */ 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ml->len > len) { 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t l = ml->len - len; 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m = new_movelist(ml->dst + len, ml->src + len, l); 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m->next = ml->next; 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->len = len; 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ml->next = m; 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return parentptr; 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void delete_movelist(struct syslinux_movelist **parentptr) 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *o = *parentptr; 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *parentptr = o->next; 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman free(o); 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void free_movelist(struct syslinux_movelist **parentptr) 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (*parentptr) 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delete_movelist(parentptr); 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Scan the freelist looking for a particular chunk of memory. Returns 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the memmap chunk containing to the first byte of the region. 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic const struct syslinux_memmap *is_free_zone(const struct syslinux_memmap 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *list, addr_t start, 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t len) 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t last, llast; 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("f: 0x%08x bytes at 0x%08x\n", len, start); 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman last = start + len - 1; 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (list->type != SMT_END) { 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (list->start <= start) { 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const struct syslinux_memmap *ilist = list; 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (valid_terminal_type(list->type)) { 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman llast = list->next->start - 1; 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (llast >= last) 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return ilist; 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list = list->next; 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (list->start > start) 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return NULL; /* Invalid type in region */ 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman list = list->next; 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return NULL; /* Internal error? */ 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Scan the freelist looking for the smallest chunk of memory which 18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * can fit X bytes; returns the length of the block on success. 18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic addr_t free_area(const struct syslinux_memmap *mmap, 18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t len, addr_t * start) 18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const struct syslinux_memmap *best = NULL; 18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const struct syslinux_memmap *s; 18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t slen, best_len = -1; 18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (s = mmap; s->type != SMT_END; s = s->next) { 19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (s->type != SMT_FREE) 19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; 19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman slen = s->next->start - s->start; 19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (slen >= len) { 19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!best || best_len > slen) { 19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman best = s; 19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman best_len = slen; 19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (best) { 20276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *start = best->start; 20376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return best_len; 20476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 20576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return 0; 20676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 20776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 20876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 20976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 21076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Remove a chunk from the freelist 21176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 21276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void 21376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanallocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len) 21476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 21576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_add_memmap(mmap, start, len, SMT_ALLOC); 21676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 21776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 21976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Find chunks of a movelist which are one-to-many (one source, multiple 22076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * destinations.) Those chunks can get turned into post-shuffle copies, 22176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * to avoid confusing the shuffler. 22276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 22376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void shuffle_dealias(struct syslinux_movelist **fraglist, 22476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist **postcopy) 22576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 22676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *mp, **mpp, *mx, *np; 22776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t ps, pe, xs, xe, delta; 22876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman bool advance; 22976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 23076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Before alias resolution:\n"); 23176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(*fraglist); 23276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 23376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *postcopy = NULL; 23476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 23576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* 23676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Note: as written, this is an O(n^2) algorithm; by producing a list 23776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * sorted by destination address we could reduce it to O(n log n). 23876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 23976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mpp = fraglist; 24076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while ((mp = *mpp)) { 24176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len); 24276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ps = mp->src; 24376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pe = mp->src + mp->len - 1; 24476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (mx = *fraglist; mx != mp; mx = mx->next) { 24576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len); 24676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* 24776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * If there is any overlap between mx and mp, mp should be 24876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * modified and possibly split. 24976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 25076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman xs = mx->src; 25176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman xe = mx->src + mx->len - 1; 25276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe); 25476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (pe <= xs || ps >= xe) 25676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; /* No overlap */ 25776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman advance = false; 25976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *mpp = mp->next; /* Remove from list */ 26076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 26176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (pe > xe) { 26276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delta = pe - xe; 26376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman np = new_movelist(mp->dst + mp->len - delta, 26476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->src + mp->len - delta, delta); 26576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->len -= delta; 26676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman pe = xe; 26776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman np->next = *mpp; 26876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *mpp = np; 26976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman advance = true; 27076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 27176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ps < xs) { 27276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delta = xs - ps; 27376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman np = new_movelist(mp->dst, ps, delta); 27476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->src += delta; 27576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ps = mp->src; 27676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->dst += delta; 27776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->len -= delta; 27876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman np->next = *mpp; 27976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *mpp = np; 28076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman advance = true; 28176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 28276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 28376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(ps >= xs && pe <= xe); 28476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 28576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe); 28676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 28776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->src = mx->dst + (ps - xs); 28876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp->next = *postcopy; 28976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *postcopy = mp; 29076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mp = *mpp; 29276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!advance) 29476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto restart; 29576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 29676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mpp = &mp->next; 29876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanrestart: 29976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ; 30076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 30176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 30276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("After alias resolution:\n"); 30376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(*fraglist); 30476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Post-shuffle copies:\n"); 30576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(*postcopy); 30676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 30776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 30876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 30976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * The code to actually emit moving of a chunk into its final place. 31076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 31176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void 31276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmove_chunk(struct syslinux_movelist ***moves, 31376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_memmap **mmap, 31476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist **fp, addr_t copylen) 31576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 31676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t copydst, copysrc; 31776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t freebase, freelen; 31876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t needlen; 31976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int reverse; 32076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *f = *fp, *mv; 32176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 32276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (f->src < f->dst && (f->dst - f->src) < f->len) { 32376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift up" type overlap */ 32476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->dst - f->src; 32576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 1; 32676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else if (f->src > f->dst && (f->src - f->dst) < f->len) { 32776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift down" type overlap */ 32876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->src - f->dst; 32976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 33076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 33176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->len; 33276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 33376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 33476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copydst = f->dst; 33676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = f->src; 33776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen); 33976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (copylen < needlen) { 34176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (reverse) { 34276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copydst += (f->len - copylen); 34376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc += (f->len - copylen); 34476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 34576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n", 34776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen, copysrc, copydst); 34876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Didn't get all we wanted, so we have to split the chunk */ 35076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fp = split_movelist(copysrc, copylen, fp); /* Is this right? */ 35176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman f = *fp; 35276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 35376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mv = new_movelist(f->dst, f->src, f->len); 35576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n", mv->len, mv->src, mv->dst); 35676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman **moves = mv; 35776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *moves = &mv->next; 35876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Figure out what memory we just freed up */ 36076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (f->dst > f->src) { 36176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freebase = f->src; 36276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freelen = min(f->len, f->dst - f->src); 36376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else if (f->src >= f->dst + f->len) { 36476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freebase = f->src; 36576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freelen = f->len; 36676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 36776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freelen = f->src - f->dst; 36876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman freebase = f->dst + f->len; 36976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 37076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase); 37276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman add_freelist(mmap, freebase, freelen, SMT_FREE); 37476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delete_movelist(fp); 37676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 37776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 37976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * moves is computed from "frags" and "freemem". "space" lists 38076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * free memory areas at our disposal, and is (src, cnt) only. 38176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 38276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanint 38376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmansyslinux_compute_movelist(struct syslinux_movelist **moves, 38476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *ifrags, 38576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_memmap *memmap) 38676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 38776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_memmap *mmap = NULL; 38876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const struct syslinux_memmap *mm, *ep; 38976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *frags = NULL; 39076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *postcopy = NULL; 39176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *mv; 39276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *f, **fp; 39376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *o, **op; 39476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t needbase, needlen, copysrc, copydst, copylen; 39576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t avail; 39676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t fstart, flen; 39776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t cbyte; 39876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman addr_t ep_len; 39976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int rv = -1; 40076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int reverse; 40176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 40276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("entering syslinux_compute_movelist()...\n"); 40376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 40476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (setjmp(new_movelist_bail)) { 40576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmannomem: 40676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Out of working memory!\n"); 40776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto bail; 40876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 40976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *moves = NULL; 41176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Create our memory map. Anything that is SMT_FREE or SMT_ZERO is 41376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fair game, but mark anything used by source material as SMT_ALLOC. */ 41476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mmap = syslinux_init_memmap(); 41576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!mmap) 41676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto nomem; 41776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman frags = dup_movelist(ifrags); 41976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 42076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Process one-to-many conditions */ 42176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman shuffle_dealias(&frags, &postcopy); 42276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 42376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (mm = memmap; mm->type != SMT_END; mm = mm->next) 42476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman add_freelist(&mmap, mm->start, mm->next->start - mm->start, 42576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mm->type == SMT_ZERO ? SMT_FREE : mm->type); 42676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 42776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (f = frags; f; f = f->next) 42876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman add_freelist(&mmap, f->src, f->len, SMT_ALLOC); 42976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 43076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* As long as there are unprocessed fragments in the chain... */ 43176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while ((fp = &frags, f = *fp)) { 43276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 43376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Current free list:\n"); 43476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_memmap(mmap); 43576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Current frag list:\n"); 43676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(frags); 43776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 43876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Scan for fragments which can be discarded without action. */ 43976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (f->src == f->dst) { 44076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delete_movelist(fp); 44176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; 44276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 44376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman op = &f->next; 44476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while ((o = *op)) { 44576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (o->src == o->dst) 44676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman delete_movelist(op); 44776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 44876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman op = &o->next; 44976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 45076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 45176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Scan for fragments which can be immediately moved 45276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman to their final destination, if so handle them now */ 45376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (op = fp; (o = *op); op = &o->next) { 45476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (o->src < o->dst && (o->dst - o->src) < o->len) { 45576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift up" type overlap */ 45676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = o->dst - o->src; 45776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = o->dst + (o->len - needlen); 45876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 1; 45976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = o->dst + o->len - 1; 46076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else if (o->src > o->dst && (o->src - o->dst) < o->len) { 46176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift down" type overlap */ 46276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = o->src - o->dst; 46376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = o->dst; 46476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 46576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = o->dst; /* "Critical byte" */ 46676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 46776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = o->len; 46876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = o->dst; 46976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 47076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = o->dst; /* "Critical byte" */ 47176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 47276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 47376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (is_free_zone(mmap, needbase, needlen)) { 47476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fp = op, f = o; 47576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("!: 0x%08x bytes at 0x%08x -> 0x%08x\n", 47676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman f->len, f->src, f->dst); 47776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = f->src; 47876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = needlen; 47976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman allocate_from(&mmap, needbase, copylen); 48076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto move_chunk; 48176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 48276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 48376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 48476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Ok, bother. Need to do real work at least with one chunk. */ 48576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 48676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n", 48776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman f->len, f->src, f->dst); 48876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 48976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* See if we can move this chunk into place by claiming 49076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman the destination, or in the case of partial overlap, the 49176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman missing portion. */ 49276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 49376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (f->src < f->dst && (f->dst - f->src) < f->len) { 49476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift up" type overlap */ 49576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->dst - f->src; 49676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = f->dst + (f->len - needlen); 49776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 1; 49876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = f->dst + f->len - 1; 49976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else if (f->src > f->dst && (f->src - f->dst) < f->len) { 50076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* "Shift down" type overlap */ 50176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->src - f->dst; 50276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = f->dst; 50376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 50476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = f->dst; /* "Critical byte" */ 50576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 50676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needlen = f->len; 50776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase = f->dst; 50876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 50976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman cbyte = f->dst; 51076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 51176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 51276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("need: base = 0x%08x, len = 0x%08x, " 51376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman "reverse = %d, cbyte = 0x%08x\n", 51476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman needbase, needlen, reverse, cbyte); 51576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 51676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ep = is_free_zone(mmap, cbyte, 1); 51776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (ep) { 51876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ep_len = ep->next->start - ep->start; 51976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (reverse) 52076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman avail = needbase + needlen - ep->start; 52176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 52276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman avail = ep_len - (needbase - ep->start); 52376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 52476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman avail = 0; 52576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 52676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 52776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (avail) { 52876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* We can move at least part of this chunk into place without 52976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman further ado */ 53076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n", 53176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ep->start, ep_len, avail); 53276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = min(needlen, avail); 53376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 53476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (reverse) 53576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman allocate_from(&mmap, needbase + needlen - copylen, copylen); 53676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 53776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman allocate_from(&mmap, needbase, copylen); 53876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 53976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto move_chunk; 54076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 54176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 54276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* At this point, we need to evict something out of our space. 54376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Find the object occupying the critical byte of our target space, 54476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman and move it out (the whole object if we can, otherwise a subset.) 54576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Then move a chunk of ourselves into place. */ 54676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (op = &f->next, o = *op; o; op = &o->next, o = *op) { 54776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 54876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n", 54976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o->len, o->src, o->dst); 55076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 55176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (!(o->src <= cbyte && o->src + o->len > cbyte)) 55276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman continue; /* Not what we're looking for... */ 55376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 55476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Find somewhere to put it... */ 55576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 55676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (is_free_zone(mmap, o->dst, o->len)) { 55776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Score! We can move it into place directly... */ 55876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copydst = o->dst; 55976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = o->src; 56076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = o->len; 56176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else if (free_area(mmap, o->len, &fstart)) { 56276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* We can move the whole chunk */ 56376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copydst = fstart; 56476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = o->src; 56576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = o->len; 56676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 56776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Well, copy as much as we can... */ 56876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) { 56976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("No free memory at all!\n"); 57076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto bail; /* Stuck! */ 57176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 57276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 57376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Make sure we include the critical byte */ 57476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copydst = fstart; 57576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (reverse) { 57676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = max(o->src, cbyte + 1 - flen); 57776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = cbyte + 1 - copysrc; 57876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 57976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copysrc = cbyte; 58076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = min(flen, o->len - (cbyte - o->src)); 58176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 58276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 58376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman allocate_from(&mmap, copydst, copylen); 58476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 58576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (copylen < o->len) { 58676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman op = split_movelist(copysrc, copylen, op); 58776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o = *op; 58876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 58976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 59076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mv = new_movelist(copydst, copysrc, copylen); 59176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n", 59276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mv->len, mv->src, mv->dst); 59376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *moves = mv; 59476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman moves = &mv->next; 59576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 59676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o->src = copydst; 59776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 59876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (copylen > needlen) { 59976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* We don't need all the memory we freed up. Mark it free. */ 60076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (copysrc < needbase) { 60176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman add_freelist(&mmap, copysrc, needbase - copysrc, SMT_FREE); 60276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen -= (needbase - copysrc); 60376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 60476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (copylen > needlen) { 60576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman add_freelist(&mmap, copysrc + needlen, copylen - needlen, 60676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman SMT_FREE); 60776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copylen = needlen; 60876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 60976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 61076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman reverse = 0; 61176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto move_chunk; 61276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 61376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Cannot find the chunk containing the critical byte\n"); 61476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto bail; /* Stuck! */ 61576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 61676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmove_chunk: 61776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman move_chunk(&moves, &mmap, fp, copylen); 61876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 61976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 62076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* Finally, append the postcopy chain to the end of the moves list */ 62176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (op = moves; (o = *op); op = &o->next) ; /* Locate the end of the list */ 62276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op = postcopy; 62376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman postcopy = NULL; 62476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 62576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman rv = 0; 62676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanbail: 62776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (mmap) 62876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_free_memmap(mmap); 62976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (frags) 63076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman free_movelist(&frags); 63176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (postcopy) 63276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman free_movelist(&postcopy); 63376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return rv; 63476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 63576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 63676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef TEST 63776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 63876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdio.h> 63976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 64076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanint main(int argc, char *argv[]) 64176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 64276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman FILE *f; 64376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long d, s, l; 64476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *frags; 64576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist **fep = &frags; 64676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_movelist *mv, *moves; 64776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman struct syslinux_memmap *memmap; 64876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman char line[BUFSIZ]; 64976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 65076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (void)argc; 65176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 65276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman memmap = syslinux_init_memmap(); 65376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 65476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman f = fopen(argv[1], "r"); 65576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (fgets(line, sizeof line, f) != NULL) { 65676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (sscanf(line, "%lx %lx %lx", &s, &d, &l) == 3) { 65776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (d) { 65876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (s == -1UL) { 65976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_add_memmap(&memmap, d, l, SMT_ZERO); 66076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 66176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mv = new_movelist(d, s, l); 66276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *fep = mv; 66376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fep = &mv->next; 66476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 66576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 66676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_add_memmap(&memmap, s, l, SMT_FREE); 66776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 66876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 66976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 67076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fclose(f); 67176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 67276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *fep = NULL; 67376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 67476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Input move list:\n"); 67576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(frags); 67676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Input free list:\n"); 67776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_memmap(memmap); 67876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 67976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (syslinux_compute_movelist(&moves, frags, memmap)) { 68076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman printf("Failed to compute a move sequence\n"); 68176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return 1; 68276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } else { 68376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman dprintf("Final move list:\n"); 68476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman syslinux_dump_movelist(moves); 68576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return 0; 68676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 68776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 68876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 68976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* TEST */ 690