com32/lib/syslinux/shuffle.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 2007-2009 H. Peter Anvin - All Rights Reserved
   4  *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
   5  *
   6  *   Permission is hereby granted, free of charge, to any person
   7  *   obtaining a copy of this software and associated documentation
   8  *   files (the "Software"), to deal in the Software without
   9  *   restriction, including without limitation the rights to use,
  10  *   copy, modify, merge, publish, distribute, sublicense, and/or
  11  *   sell copies of the Software, and to permit persons to whom
  12  *   the Software is furnished to do so, subject to the following
  13  *   conditions:
  14  *
  15  *   The above copyright notice and this permission notice shall
  16  *   be included in all copies or substantial portions of the Software.
  17  *
  18  *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  20  *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  22  *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  23  *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  24  *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25  *   OTHER DEALINGS IN THE SOFTWARE.
  26  *
  27  * ----------------------------------------------------------------------- */
  28
  29 /*
  30  * shuffle.c
  31  *
  32  * Common code for "shuffle and boot" operation; generates a shuffle list
  33  * and puts it in the bounce buffer.  Returns the number of shuffle
  34  * descriptors.
  35  */
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <inttypes.h>
  40 #include <com32.h>
  41 #include <core.h>
  42 #include <minmax.h>
  43 #include <dprintf.h>
  44 #include <syslinux/movebits.h>
  45 #include <klibc/compiler.h>
  46 #include <syslinux/boot.h>
  47
  48 struct shuffle_descriptor {
  49     addr_t dst, src, len;
  50 };
  51
  52 /*
  53  * Allocate descriptor memory in these chunks; if this is large we may
  54  * waste memory, if it is small we may get slow convergence.
  55  */
  56 #define DESC_BLOCK_SIZE 256
  57
  58 int syslinux_do_shuffle(struct syslinux_movelist *fraglist,
  59                         struct syslinux_memmap *memmap,
  60                         addr_t entry_point, addr_t entry_type,
  61                         uint16_t bootflags)
  62 {
  63     int rv = -1;
  64     struct syslinux_movelist *moves = NULL, *mp;
  65     struct syslinux_memmap *rxmap = NULL, *ml;
  66     struct shuffle_descriptor *dp, *dbuf;
  67     int np;
  68     int desc_blocks, need_blocks;
  69     int need_ptrs;
  70     addr_t desczone, descfree, descaddr;
  71     int nmoves, nzero;
  72
  73 #ifndef __FIRMWARE_BIOS__
  74     errno = ENOSYS;
  75     return -1;                  /* Not supported at this time*/
  76 #endif
  77
  78     descaddr = 0;
  79     dp = dbuf = NULL;
  80
  81     /* Count the number of zero operations */
  82     nzero = 0;
  83     for (ml = memmap; ml->type != SMT_END; ml = ml->next) {
  84         if (ml->type == SMT_ZERO)
  85             nzero++;
  86     }
  87
  88     /* Find the largest contiguous region unused by input *and* output;
  89        this is where we put the move descriptor list and safe area */
  90
  91     rxmap = syslinux_dup_memmap(memmap);
  92     if (!rxmap)
  93         goto bail;
  94     /* Avoid using the low 1 MB for the shuffle area -- this avoids
  95        possible interference with the real mode code or stack */
  96     if (syslinux_add_memmap(&rxmap, 0, 1024 * 1024, SMT_RESERVED))
  97         goto bail;
  98     for (mp = fraglist; mp; mp = mp->next) {
  99         if (syslinux_add_memmap(&rxmap, mp->src, mp->len, SMT_ALLOC) ||
 100             syslinux_add_memmap(&rxmap, mp->dst, mp->len, SMT_ALLOC))
 101             goto bail;
 102     }
 103     if (syslinux_memmap_largest(rxmap, SMT_FREE, &desczone, &descfree))
 104         goto bail;
 105
 106     syslinux_free_memmap(rxmap);
 107
 108     dprintf("desczone = 0x%08zx, descfree = 0x%08zx\n", desczone, descfree);
 109
 110     rxmap = syslinux_dup_memmap(memmap);
 111     if (!rxmap)
 112         goto bail;
 113
 114     desc_blocks = (nzero + DESC_BLOCK_SIZE - 1) / DESC_BLOCK_SIZE;
 115     for (;;) {
 116         /* We want (desc_blocks) allocation blocks, plus the terminating
 117            descriptor, plus the shuffler safe area. */
 118         addr_t descmem = desc_blocks *
 119             sizeof(struct shuffle_descriptor) * DESC_BLOCK_SIZE
 120             + sizeof(struct shuffle_descriptor)
 121             + syslinux_shuffler_size();
 122
 123         descaddr = (desczone + descfree - descmem) & ~3;
 124
 125         if (descaddr < desczone)
 126             goto bail;          /* No memory block large enough */
 127
 128         /* Mark memory used by shuffle descriptors as reserved */
 129         if (syslinux_add_memmap(&rxmap, descaddr, descmem, SMT_RESERVED))
 130             goto bail;
 131
 132 #if DEBUG > 1
 133         syslinux_dump_movelist(fraglist);
 134 #endif
 135
 136         if (syslinux_compute_movelist(&moves, fraglist, rxmap))
 137             goto bail;
 138
 139         nmoves = 0;
 140         for (mp = moves; mp; mp = mp->next)
 141             nmoves++;
 142
 143         need_blocks = (nmoves + nzero + DESC_BLOCK_SIZE - 1) / DESC_BLOCK_SIZE;
 144
 145         if (desc_blocks >= need_blocks)
 146             break;              /* Sufficient memory, yay */
 147
 148         desc_blocks = need_blocks;      /* Try again... */
 149     }
 150
 151 #if DEBUG > 1
 152     dprintf("Final movelist:\n");
 153     syslinux_dump_movelist(moves);
 154 #endif
 155
 156     syslinux_free_memmap(rxmap);
 157     rxmap = NULL;
 158
 159     need_ptrs = nmoves + nzero + 1;
 160     dbuf = malloc(need_ptrs * sizeof(struct shuffle_descriptor));
 161     if (!dbuf)
 162         goto bail;
 163
 164 #if DEBUG
 165     {
 166         addr_t descoffs = descaddr - (addr_t) dbuf;
 167
 168         dprintf("nmoves = %d, nzero = %d, dbuf = %p, offs = 0x%08zx\n",
 169                 nmoves, nzero, dbuf, descoffs);
 170     }
 171 #endif
 172
 173     /* Copy the move sequence into the descriptor buffer */
 174     np = 0;
 175     dp = dbuf;
 176     for (mp = moves; mp; mp = mp->next) {
 177         dp->dst = mp->dst;
 178         dp->src = mp->src;
 179         dp->len = mp->len;
 180         dprintf2("[ %08zx %08zx %08zx ]\n", dp->dst, dp->src, dp->len);
 181         dp++;
 182         np++;
 183     }
 184
 185     /* Copy bzero operations into the descriptor buffer */
 186     for (ml = memmap; ml->type != SMT_END; ml = ml->next) {
 187         if (ml->type == SMT_ZERO) {
 188             dp->dst = ml->start;
 189             dp->src = (addr_t) - 1;     /* bzero region */
 190             dp->len = ml->next->start - ml->start;
 191             dprintf2("[ %08zx %08zx %08zx ]\n", dp->dst, dp->src, dp->len);
 192             dp++;
 193             np++;
 194         }
 195     }
 196
 197     /* Finally, record the termination entry */
 198     dp->dst = entry_point;
 199     dp->src = entry_type;
 200     dp->len = 0;
 201     dp++;
 202     np++;
 203
 204     if (np != need_ptrs) {
 205         dprintf("!!! np = %d : nmoves = %d, nzero = %d, desc_blocks = %d\n",
 206                 np, nmoves, nzero, desc_blocks);
 207     }
 208
 209     rv = 0;
 210
 211 bail:
 212     /* This is safe only because free() doesn't use the bounce buffer!!!! */
 213     if (moves)
 214         syslinux_free_movelist(moves);
 215     if (rxmap)
 216         syslinux_free_memmap(rxmap);
 217
 218     if (rv)
 219         return rv;
 220
 221     /* Actually do it... */
 222     bios_do_shuffle_and_boot(bootflags, descaddr, dbuf,
 223                              (size_t)dp - (size_t)dbuf);
 224
 225     return -1;                  /* Shouldn't have returned! */
 226 }
 227
 228 /*
 229  * Common helper routine: takes a memory map and blots out the
 230  * zones which are used in the destination of a fraglist
 231  */
 232 struct syslinux_memmap *syslinux_target_memmap(struct syslinux_movelist
 233                                                *fraglist,
 234                                                struct syslinux_memmap *memmap)
 235 {
 236     struct syslinux_memmap *tmap;
 237     struct syslinux_movelist *mp;
 238
 239     tmap = syslinux_dup_memmap(memmap);
 240     if (!tmap)
 241         return NULL;
 242
 243     for (mp = fraglist; mp; mp = mp->next) {
 244         if (syslinux_add_memmap(&tmap, mp->dst, mp->len, SMT_ALLOC)) {
 245             syslinux_free_memmap(tmap);
 246             return NULL;
 247         }
 248     }
 249
 250     return tmap;
 251 }