summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2009-05-02 17:27:03 -0700
committerH. Peter Anvin <hpa@zytor.com>2009-05-02 17:27:03 -0700
commitb55f8a80e17e7b9c1b003c808ea8048c49fbf59c (patch)
tree0aeb376fcaf40764d94bcf526b9b9f438f217c78
parent9cd4a3b4fb21482b474d63486fe677966eeb2761 (diff)
downloadsyslinux-b55f8a80e17e7b9c1b003c808ea8048c49fbf59c.tar.gz
shuffler: correctly handle one-to-many relationshipssyslinux-3.80-pre7
One-to-many relationships, in which one chunk of a file is used in more than one place, tends to naturally show up in decoding certain fileformats, including (but not limited to) Microsoft SDI. Make the shuffler library handle those cases correctly, and remove a special-purpose hack in sdi.c. This is based on the observation that all one-to-many relationships can be treated as a one-to-one shuffle followed by destination-to-destination copies; i.e. one copy is (arbitrarily) assigned the "master copy" status, and all aliases are then copied from the master copy when the master copy is already in its final place. All other copies can then be simply ignored for the duration of the shuffle, just as zero-memory is. Signed-off-by: H. Peter Anvin <hpa@zytor.com>
-rw-r--r--com32/lib/syslinux/movebits.c148
-rw-r--r--com32/modules/sdi.c11
2 files changed, 133 insertions, 26 deletions
diff --git a/com32/lib/syslinux/movebits.c b/com32/lib/syslinux/movebits.c
index 5e4a0c39..1114bfb8 100644
--- a/com32/lib/syslinux/movebits.c
+++ b/com32/lib/syslinux/movebits.c
@@ -1,6 +1,7 @@
/* ----------------------------------------------------------------------- *
*
* Copyright 2007-2008 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
@@ -43,6 +44,8 @@
#include <stdlib.h>
#include <inttypes.h>
#include <setjmp.h>
+#include <minmax.h>
+#include <stdbool.h>
#include <syslinux/movebits.h>
@@ -61,9 +64,6 @@
# define dprintf(...) ((void)0)
#endif
-#define min(x,y) ((x) < (y) ? (x) : (y))
-#define max(x,y) ((x) > (y) ? (x) : (y))
-
static jmp_buf new_movelist_bail;
static struct syslinux_movelist *
@@ -230,6 +230,97 @@ allocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len)
}
/*
+ * Find chunks of a movelist which are one-to-many (one source, multiple
+ * destinations.) Those chunks can get turned into post-shuffle copies,
+ * to avoid confusing the shuffler.
+ */
+static void shuffle_dealias(struct syslinux_movelist **fraglist,
+ struct syslinux_movelist **postcopy)
+{
+ struct syslinux_movelist *mp, **mpp, *mx, *np;
+ addr_t ps, pe, xs, xe, delta;
+ bool advance;
+
+#if DEBUG
+ dprintf("Before alias resolution:\n");
+ syslinux_dump_movelist(stdout, *fraglist);
+#endif
+
+ *postcopy = NULL;
+
+ /*
+ * Note: as written, this is an O(n^2) algorithm; by producing a list
+ * sorted by destination address we could reduce it to O(n log n).
+ */
+ mpp = fraglist;
+ while ((mp = *mpp)) {
+ dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len);
+ ps = mp->src;
+ pe = mp->src + mp->len - 1;
+ for (mx = *fraglist; mx != mp; mx = mx->next) {
+ dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len);
+ /*
+ * If there is any overlap between mx and mp, mp should be
+ * modified and possibly split.
+ */
+ xs = mx->src;
+ xe = mx->src + mx->len - 1;
+
+ dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
+
+ if (pe <= xs || ps >= xe)
+ continue; /* No overlap */
+
+ advance = false;
+ *mpp = mp->next; /* Remove from list */
+
+ if (pe > xe) {
+ delta = pe-xe;
+ np = new_movelist(mp->dst+mp->len-delta, mp->src+mp->len-delta, delta);
+ mp->len -= delta; pe = xe;
+ np->next = *mpp;
+ *mpp = np;
+ advance = true;
+ }
+ if (ps < xs) {
+ delta = xs-ps;
+ np = new_movelist(mp->dst, ps, delta);
+ mp->src += delta; ps = mp->src;
+ mp->dst += delta;
+ mp->len -= delta;
+ np->next = *mpp;
+ *mpp = np;
+ advance = true;
+ }
+
+ assert(ps >= xs && pe <= xe);
+
+ dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
+
+ mp->src = mx->dst + (ps-xs);
+ mp->next = *postcopy;
+ *postcopy = mp;
+
+ mp = *mpp;
+
+ if (!advance)
+ goto restart;
+ }
+
+ mpp = &mp->next;
+ restart:
+ ;
+ }
+
+#if DEBUG
+ dprintf("After alias resolution:\n");
+ syslinux_dump_movelist(stdout, *fraglist);
+ dprintf("Post-shuffle copies:\n");
+ syslinux_dump_movelist(stdout, *postcopy);
+#endif
+}
+
+/*
* The code to actually emit moving of a chunk into its final place.
*/
static void
@@ -304,7 +395,6 @@ move_chunk(struct syslinux_movelist ***moves,
* moves is computed from "frags" and "freemem". "space" lists
* free memory areas at our disposal, and is (src, cnt) only.
*/
-
int
syslinux_compute_movelist(struct syslinux_movelist **moves,
struct syslinux_movelist *ifrags,
@@ -313,6 +403,7 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
struct syslinux_memmap *mmap = NULL;
const struct syslinux_memmap *mm, *ep;
struct syslinux_movelist *frags = NULL;
+ struct syslinux_movelist *postcopy = NULL;
struct syslinux_movelist *mv;
struct syslinux_movelist *f, **fp;
struct syslinux_movelist *o, **op;
@@ -342,6 +433,9 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
frags = dup_movelist(ifrags);
+ /* Process one-to-many conditions */
+ shuffle_dealias(&frags, &postcopy);
+
for (mm = memmap; mm->type != SMT_END; mm = mm->next)
add_freelist(&mmap, mm->start, mm->next->start - mm->start,
mm->type == SMT_ZERO ? SMT_FREE : mm->type);
@@ -540,12 +634,20 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
move_chunk(&moves, &mmap, fp, copylen);
}
+ /* Finally, append the postcopy chain to the end of the moves list */
+ for (op = moves; (o = *op); op = &o->next)
+ ; /* Locate the end of the list */
+ *op = postcopy;
+ postcopy = NULL;
+
rv = 0;
bail:
if (mmap)
syslinux_free_memmap(mmap);
if (frags)
free_movelist(&frags);
+ if (postcopy)
+ free_movelist(&postcopy);
return rv;
}
@@ -559,32 +661,42 @@ int main(int argc, char *argv[])
unsigned long d, s, l;
struct syslinux_movelist *frags;
struct syslinux_movelist **fep = &frags;
- struct syslinux_movelist *space;
- struct syslinux_movelist **sep = &space;
struct syslinux_movelist *mv, *moves;
+ struct syslinux_memmap *memmap;
+
+ (void)argc;
+
+ memmap = syslinux_init_memmap();
f = fopen(argv[1], "r");
- while ( fscanf(f, "%lx %lx %lx", &d, &s, &l) == 3 ) {
+ while ( fscanf(f, "%lx %lx %lx", &s, &d, &l) == 3 ) {
if ( d ) {
- mv = new_movelist(d, s, l);
- *fep = mv;
- fep = &mv->next;
+ if (s == -1UL) {
+ syslinux_add_memmap(&memmap, d, l, SMT_ZERO);
+ } else {
+ mv = new_movelist(d, s, l);
+ *fep = mv;
+ fep = &mv->next;
+ }
} else {
- mv = new_movelist(0, s, l);
- *sep = mv;
- sep = &mv->next;
+ syslinux_add_memmap(&memmap, s, l, SMT_FREE);
}
}
fclose(f);
- if ( syslinux_compute_movelist(&moves, frags, space) ) {
+ *fep = NULL;
+
+ printf("Input move list:\n");
+ syslinux_dump_movelist(stdout, frags);
+ printf("Input free list:\n");
+ syslinux_dump_memmap(stdout, memmap);
+
+ if ( syslinux_compute_movelist(&moves, frags, memmap) ) {
printf("Failed to compute a move sequence\n");
return 1;
} else {
- for ( mv = moves ; mv ; mv = mv->next ) {
- printf("0x%08x bytes at 0x%08x -> 0x%08x\n",
- mv->len, mv->src, mv->dst);
- }
+ printf("Final move list:\n");
+ syslinux_dump_movelist(stdout, moves);
return 0;
}
}
diff --git a/com32/modules/sdi.c b/com32/modules/sdi.c
index 7c898591..a5df4dab 100644
--- a/com32/modules/sdi.c
+++ b/com32/modules/sdi.c
@@ -1,6 +1,7 @@
/* ----------------------------------------------------------------------- *
*
* Copyright 2008 H. Peter Anvin - All Rights Reserved
+ * Copyright 2009 Intel Corporation; author: H. Peter Anvin
*
* 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
@@ -116,14 +117,8 @@ static int boot_sdi(void *ptr, size_t len)
}
if (syslinux_add_memmap(&amap, 0x7c00, hdr->BootCodeSize, SMT_ALLOC))
goto bail;
-
- /* The shuffle library doesn't handle duplication well... */
- boot_blob = malloc(hdr->BootCodeSize);
- if (!boot_blob)
- goto bail;
- memcpy(boot_blob, (char *)ptr + hdr->BootCodeOffset, hdr->BootCodeSize);
-
- if (syslinux_add_movelist(&ml, 0x7c00, (addr_t)boot_blob, hdr->BootCodeSize))
+ if (syslinux_add_movelist(&ml, 0x7c00, (addr_t)ptr + hdr->BootCodeOffset,
+ hdr->BootCodeSize))
goto bail;
/* **** Map the entire image to SDI_LOAD_ADDR **** */