1/* ----------------------------------------------------------------------- *
2 *
3 *   Copyright 2007-2008 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 * movebits.c
31 *
32 * Utility function to take a list of memory areas to shuffle and
33 * convert it to a set of shuffle operations.
34 *
35 * Note: a lot of the functions in this file deal with "parent pointers",
36 * which are pointers to a pointer to a list, or part of the list.
37 * They can be pointers to a variable holding the list root pointer,
38 * or pointers to a next field of a previous entry.
39 */
40
41#include <assert.h>
42#include <stdio.h>
43#include <errno.h>
44#include <stdlib.h>
45#include <inttypes.h>
46#include <setjmp.h>
47#include <minmax.h>
48#include <stdbool.h>
49
50#include <syslinux/movebits.h>
51#include <dprintf.h>
52
53static jmp_buf new_movelist_bail;
54
55static struct syslinux_movelist *new_movelist(addr_t dst, addr_t src,
56					      addr_t len)
57{
58    struct syslinux_movelist *ml = malloc(sizeof(struct syslinux_movelist));
59
60    if (!ml)
61	longjmp(new_movelist_bail, 1);
62
63    ml->dst = dst;
64    ml->src = src;
65    ml->len = len;
66    ml->next = NULL;
67
68    return ml;
69}
70
71static struct syslinux_movelist *dup_movelist(struct syslinux_movelist *src)
72{
73    struct syslinux_movelist *dst = NULL, **dstp = &dst, *ml;
74
75    while (src) {
76	ml = new_movelist(src->dst, src->src, src->len);
77	*dstp = ml;
78	dstp = &ml->next;
79	src = src->next;
80    }
81
82    return dst;
83}
84
85static void
86add_freelist(struct syslinux_memmap **mmap, addr_t start,
87	     addr_t len, enum syslinux_memmap_types type)
88{
89    if (syslinux_add_memmap(mmap, start, len, type))
90	longjmp(new_movelist_bail, 1);
91}
92
93/*
94 * Take a chunk, entirely confined in **parentptr, and split it off so that
95 * it has its own structure.
96 */
97static struct syslinux_movelist **split_movelist(addr_t start, addr_t len,
98						 struct syslinux_movelist
99						 **parentptr)
100{
101    struct syslinux_movelist *m, *ml = *parentptr;
102
103    assert(start >= ml->src);
104    assert(start < ml->src + ml->len);
105
106    /* Split off the beginning */
107    if (start > ml->src) {
108	addr_t l = start - ml->src;
109
110	m = new_movelist(ml->dst + l, start, ml->len - l);
111	m->next = ml->next;
112	ml->len = l;
113	ml->next = m;
114
115	parentptr = &ml->next;
116	ml = m;			/* Continue processing the new node */
117    }
118
119    /* Split off the end */
120    if (ml->len > len) {
121	addr_t l = ml->len - len;
122
123	m = new_movelist(ml->dst + len, ml->src + len, l);
124	m->next = ml->next;
125	ml->len = len;
126	ml->next = m;
127    }
128
129    return parentptr;
130}
131
132static void delete_movelist(struct syslinux_movelist **parentptr)
133{
134    struct syslinux_movelist *o = *parentptr;
135    *parentptr = o->next;
136    free(o);
137}
138
139static void free_movelist(struct syslinux_movelist **parentptr)
140{
141    while (*parentptr)
142	delete_movelist(parentptr);
143}
144
145/*
146 * Scan the freelist looking for a particular chunk of memory.  Returns
147 * the memmap chunk containing to the first byte of the region.
148 */
149static const struct syslinux_memmap *is_free_zone(const struct syslinux_memmap
150						  *list, addr_t start,
151						  addr_t len)
152{
153    addr_t last, llast;
154
155    dprintf("f: 0x%08x bytes at 0x%08x\n", len, start);
156
157    last = start + len - 1;
158
159    while (list->type != SMT_END) {
160	if (list->start <= start) {
161	    const struct syslinux_memmap *ilist = list;
162	    while (valid_terminal_type(list->type)) {
163		llast = list->next->start - 1;
164		if (llast >= last)
165		    return ilist;
166		list = list->next;
167	    }
168
169	    if (list->start > start)
170		return NULL;	/* Invalid type in region */
171	}
172	list = list->next;
173    }
174
175    return NULL;		/* Internal error? */
176}
177
178/*
179 * Scan the freelist looking for the smallest chunk of memory which
180 * can fit X bytes; returns the length of the block on success.
181 */
182static addr_t free_area(const struct syslinux_memmap *mmap,
183			addr_t len, addr_t * start)
184{
185    const struct syslinux_memmap *best = NULL;
186    const struct syslinux_memmap *s;
187    addr_t slen, best_len = -1;
188
189    for (s = mmap; s->type != SMT_END; s = s->next) {
190	if (s->type != SMT_FREE)
191	    continue;
192	slen = s->next->start - s->start;
193	if (slen >= len) {
194	    if (!best || best_len > slen) {
195		best = s;
196		best_len = slen;
197	    }
198	}
199    }
200
201    if (best) {
202	*start = best->start;
203	return best_len;
204    } else {
205	return 0;
206    }
207}
208
209/*
210 * Remove a chunk from the freelist
211 */
212static void
213allocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len)
214{
215    syslinux_add_memmap(mmap, start, len, SMT_ALLOC);
216}
217
218/*
219 * Find chunks of a movelist which are one-to-many (one source, multiple
220 * destinations.)  Those chunks can get turned into post-shuffle copies,
221 * to avoid confusing the shuffler.
222 */
223static void shuffle_dealias(struct syslinux_movelist **fraglist,
224			    struct syslinux_movelist **postcopy)
225{
226    struct syslinux_movelist *mp, **mpp, *mx, *np;
227    addr_t ps, pe, xs, xe, delta;
228    bool advance;
229
230    dprintf("Before alias resolution:\n");
231    syslinux_dump_movelist(*fraglist);
232
233    *postcopy = NULL;
234
235    /*
236     * Note: as written, this is an O(n^2) algorithm; by producing a list
237     * sorted by destination address we could reduce it to O(n log n).
238     */
239    mpp = fraglist;
240    while ((mp = *mpp)) {
241	dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len);
242	ps = mp->src;
243	pe = mp->src + mp->len - 1;
244	for (mx = *fraglist; mx != mp; mx = mx->next) {
245	    dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len);
246	    /*
247	     * If there is any overlap between mx and mp, mp should be
248	     * modified and possibly split.
249	     */
250	    xs = mx->src;
251	    xe = mx->src + mx->len - 1;
252
253	    dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
254
255	    if (pe <= xs || ps >= xe)
256		continue;	/* No overlap */
257
258	    advance = false;
259	    *mpp = mp->next;	/* Remove from list */
260
261	    if (pe > xe) {
262		delta = pe - xe;
263		np = new_movelist(mp->dst + mp->len - delta,
264				  mp->src + mp->len - delta, delta);
265		mp->len -= delta;
266		pe = xe;
267		np->next = *mpp;
268		*mpp = np;
269		advance = true;
270	    }
271	    if (ps < xs) {
272		delta = xs - ps;
273		np = new_movelist(mp->dst, ps, delta);
274		mp->src += delta;
275		ps = mp->src;
276		mp->dst += delta;
277		mp->len -= delta;
278		np->next = *mpp;
279		*mpp = np;
280		advance = true;
281	    }
282
283	    assert(ps >= xs && pe <= xe);
284
285	    dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
286
287	    mp->src = mx->dst + (ps - xs);
288	    mp->next = *postcopy;
289	    *postcopy = mp;
290
291	    mp = *mpp;
292
293	    if (!advance)
294		goto restart;
295	}
296
297	mpp = &mp->next;
298restart:
299	;
300    }
301
302    dprintf("After alias resolution:\n");
303    syslinux_dump_movelist(*fraglist);
304    dprintf("Post-shuffle copies:\n");
305    syslinux_dump_movelist(*postcopy);
306}
307
308/*
309 * The code to actually emit moving of a chunk into its final place.
310 */
311static void
312move_chunk(struct syslinux_movelist ***moves,
313	   struct syslinux_memmap **mmap,
314	   struct syslinux_movelist **fp, addr_t copylen)
315{
316    addr_t copydst, copysrc;
317    addr_t freebase, freelen;
318    addr_t needlen;
319    int reverse;
320    struct syslinux_movelist *f = *fp, *mv;
321
322    if (f->src < f->dst && (f->dst - f->src) < f->len) {
323	/* "Shift up" type overlap */
324	needlen = f->dst - f->src;
325	reverse = 1;
326    } else if (f->src > f->dst && (f->src - f->dst) < f->len) {
327	/* "Shift down" type overlap */
328	needlen = f->src - f->dst;
329	reverse = 0;
330    } else {
331	needlen = f->len;
332	reverse = 0;
333    }
334
335    copydst = f->dst;
336    copysrc = f->src;
337
338    dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen);
339
340    if (copylen < needlen) {
341	if (reverse) {
342	    copydst += (f->len - copylen);
343	    copysrc += (f->len - copylen);
344	}
345
346	dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
347		copylen, copysrc, copydst);
348
349	/* Didn't get all we wanted, so we have to split the chunk */
350	fp = split_movelist(copysrc, copylen, fp);	/* Is this right? */
351	f = *fp;
352    }
353
354    mv = new_movelist(f->dst, f->src, f->len);
355    dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n", mv->len, mv->src, mv->dst);
356    **moves = mv;
357    *moves = &mv->next;
358
359    /* Figure out what memory we just freed up */
360    if (f->dst > f->src) {
361	freebase = f->src;
362	freelen = min(f->len, f->dst - f->src);
363    } else if (f->src >= f->dst + f->len) {
364	freebase = f->src;
365	freelen = f->len;
366    } else {
367	freelen = f->src - f->dst;
368	freebase = f->dst + f->len;
369    }
370
371    dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
372
373    add_freelist(mmap, freebase, freelen, SMT_FREE);
374
375    delete_movelist(fp);
376}
377
378/*
379 * moves is computed from "frags" and "freemem".  "space" lists
380 * free memory areas at our disposal, and is (src, cnt) only.
381 */
382int
383syslinux_compute_movelist(struct syslinux_movelist **moves,
384			  struct syslinux_movelist *ifrags,
385			  struct syslinux_memmap *memmap)
386{
387    struct syslinux_memmap *mmap = NULL;
388    const struct syslinux_memmap *mm, *ep;
389    struct syslinux_movelist *frags = NULL;
390    struct syslinux_movelist *postcopy = NULL;
391    struct syslinux_movelist *mv;
392    struct syslinux_movelist *f, **fp;
393    struct syslinux_movelist *o, **op;
394    addr_t needbase, needlen, copysrc, copydst, copylen;
395    addr_t avail;
396    addr_t fstart, flen;
397    addr_t cbyte;
398    addr_t ep_len;
399    int rv = -1;
400    int reverse;
401
402    dprintf("entering syslinux_compute_movelist()...\n");
403
404    if (setjmp(new_movelist_bail)) {
405nomem:
406	dprintf("Out of working memory!\n");
407	goto bail;
408    }
409
410    *moves = NULL;
411
412    /* Create our memory map.  Anything that is SMT_FREE or SMT_ZERO is
413       fair game, but mark anything used by source material as SMT_ALLOC. */
414    mmap = syslinux_init_memmap();
415    if (!mmap)
416	goto nomem;
417
418    frags = dup_movelist(ifrags);
419
420    /* Process one-to-many conditions */
421    shuffle_dealias(&frags, &postcopy);
422
423    for (mm = memmap; mm->type != SMT_END; mm = mm->next)
424	add_freelist(&mmap, mm->start, mm->next->start - mm->start,
425		     mm->type == SMT_ZERO ? SMT_FREE : mm->type);
426
427    for (f = frags; f; f = f->next)
428	add_freelist(&mmap, f->src, f->len, SMT_ALLOC);
429
430    /* As long as there are unprocessed fragments in the chain... */
431    while ((fp = &frags, f = *fp)) {
432
433	dprintf("Current free list:\n");
434	syslinux_dump_memmap(mmap);
435	dprintf("Current frag list:\n");
436	syslinux_dump_movelist(frags);
437
438	/* Scan for fragments which can be discarded without action. */
439	if (f->src == f->dst) {
440	    delete_movelist(fp);
441	    continue;
442	}
443	op = &f->next;
444	while ((o = *op)) {
445	    if (o->src == o->dst)
446		delete_movelist(op);
447	    else
448		op = &o->next;
449	}
450
451	/* Scan for fragments which can be immediately moved
452	   to their final destination, if so handle them now */
453	for (op = fp; (o = *op); op = &o->next) {
454	    if (o->src < o->dst && (o->dst - o->src) < o->len) {
455		/* "Shift up" type overlap */
456		needlen = o->dst - o->src;
457		needbase = o->dst + (o->len - needlen);
458		reverse = 1;
459		cbyte = o->dst + o->len - 1;
460	    } else if (o->src > o->dst && (o->src - o->dst) < o->len) {
461		/* "Shift down" type overlap */
462		needlen = o->src - o->dst;
463		needbase = o->dst;
464		reverse = 0;
465		cbyte = o->dst;	/* "Critical byte" */
466	    } else {
467		needlen = o->len;
468		needbase = o->dst;
469		reverse = 0;
470		cbyte = o->dst;	/* "Critical byte" */
471	    }
472
473	    if (is_free_zone(mmap, needbase, needlen)) {
474		fp = op, f = o;
475		dprintf("!: 0x%08x bytes at 0x%08x -> 0x%08x\n",
476			f->len, f->src, f->dst);
477		copysrc = f->src;
478		copylen = needlen;
479		allocate_from(&mmap, needbase, copylen);
480		goto move_chunk;
481	    }
482	}
483
484	/* Ok, bother.  Need to do real work at least with one chunk. */
485
486	dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
487		f->len, f->src, f->dst);
488
489	/* See if we can move this chunk into place by claiming
490	   the destination, or in the case of partial overlap, the
491	   missing portion. */
492
493	if (f->src < f->dst && (f->dst - f->src) < f->len) {
494	    /* "Shift up" type overlap */
495	    needlen = f->dst - f->src;
496	    needbase = f->dst + (f->len - needlen);
497	    reverse = 1;
498	    cbyte = f->dst + f->len - 1;
499	} else if (f->src > f->dst && (f->src - f->dst) < f->len) {
500	    /* "Shift down" type overlap */
501	    needlen = f->src - f->dst;
502	    needbase = f->dst;
503	    reverse = 0;
504	    cbyte = f->dst;	/* "Critical byte" */
505	} else {
506	    needlen = f->len;
507	    needbase = f->dst;
508	    reverse = 0;
509	    cbyte = f->dst;
510	}
511
512	dprintf("need: base = 0x%08x, len = 0x%08x, "
513		"reverse = %d, cbyte = 0x%08x\n",
514		needbase, needlen, reverse, cbyte);
515
516	ep = is_free_zone(mmap, cbyte, 1);
517	if (ep) {
518	    ep_len = ep->next->start - ep->start;
519	    if (reverse)
520		avail = needbase + needlen - ep->start;
521	    else
522		avail = ep_len - (needbase - ep->start);
523	} else {
524	    avail = 0;
525	}
526
527	if (avail) {
528	    /* We can move at least part of this chunk into place without
529	       further ado */
530	    dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
531		    ep->start, ep_len, avail);
532	    copylen = min(needlen, avail);
533
534	    if (reverse)
535		allocate_from(&mmap, needbase + needlen - copylen, copylen);
536	    else
537		allocate_from(&mmap, needbase, copylen);
538
539	    goto move_chunk;
540	}
541
542	/* At this point, we need to evict something out of our space.
543	   Find the object occupying the critical byte of our target space,
544	   and move it out (the whole object if we can, otherwise a subset.)
545	   Then move a chunk of ourselves into place. */
546	for (op = &f->next, o = *op; o; op = &o->next, o = *op) {
547
548	    dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
549		    o->len, o->src, o->dst);
550
551	    if (!(o->src <= cbyte && o->src + o->len > cbyte))
552		continue;	/* Not what we're looking for... */
553
554	    /* Find somewhere to put it... */
555
556	    if (is_free_zone(mmap, o->dst, o->len)) {
557		/* Score!  We can move it into place directly... */
558		copydst = o->dst;
559		copysrc = o->src;
560		copylen = o->len;
561	    } else if (free_area(mmap, o->len, &fstart)) {
562		/* We can move the whole chunk */
563		copydst = fstart;
564		copysrc = o->src;
565		copylen = o->len;
566	    } else {
567		/* Well, copy as much as we can... */
568		if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) {
569		    dprintf("No free memory at all!\n");
570		    goto bail;	/* Stuck! */
571		}
572
573		/* Make sure we include the critical byte */
574		copydst = fstart;
575		if (reverse) {
576		    copysrc = max(o->src, cbyte + 1 - flen);
577		    copylen = cbyte + 1 - copysrc;
578		} else {
579		    copysrc = cbyte;
580		    copylen = min(flen, o->len - (cbyte - o->src));
581		}
582	    }
583	    allocate_from(&mmap, copydst, copylen);
584
585	    if (copylen < o->len) {
586		op = split_movelist(copysrc, copylen, op);
587		o = *op;
588	    }
589
590	    mv = new_movelist(copydst, copysrc, copylen);
591	    dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
592		    mv->len, mv->src, mv->dst);
593	    *moves = mv;
594	    moves = &mv->next;
595
596	    o->src = copydst;
597
598	    if (copylen > needlen) {
599		/* We don't need all the memory we freed up.  Mark it free. */
600		if (copysrc < needbase) {
601		    add_freelist(&mmap, copysrc, needbase - copysrc, SMT_FREE);
602		    copylen -= (needbase - copysrc);
603		}
604		if (copylen > needlen) {
605		    add_freelist(&mmap, copysrc + needlen, copylen - needlen,
606				 SMT_FREE);
607		    copylen = needlen;
608		}
609	    }
610	    reverse = 0;
611	    goto move_chunk;
612	}
613	dprintf("Cannot find the chunk containing the critical byte\n");
614	goto bail;		/* Stuck! */
615
616move_chunk:
617	move_chunk(&moves, &mmap, fp, copylen);
618    }
619
620    /* Finally, append the postcopy chain to the end of the moves list */
621    for (op = moves; (o = *op); op = &o->next) ;	/* Locate the end of the list */
622    *op = postcopy;
623    postcopy = NULL;
624
625    rv = 0;
626bail:
627    if (mmap)
628	syslinux_free_memmap(mmap);
629    if (frags)
630	free_movelist(&frags);
631    if (postcopy)
632	free_movelist(&postcopy);
633    return rv;
634}
635
636#ifdef TEST
637
638#include <stdio.h>
639
640int main(int argc, char *argv[])
641{
642    FILE *f;
643    unsigned long d, s, l;
644    struct syslinux_movelist *frags;
645    struct syslinux_movelist **fep = &frags;
646    struct syslinux_movelist *mv, *moves;
647    struct syslinux_memmap *memmap;
648    char line[BUFSIZ];
649
650    (void)argc;
651
652    memmap = syslinux_init_memmap();
653
654    f = fopen(argv[1], "r");
655    while (fgets(line, sizeof line, f) != NULL) {
656	if (sscanf(line, "%lx %lx %lx", &s, &d, &l) == 3) {
657	    if (d) {
658		if (s == -1UL) {
659		    syslinux_add_memmap(&memmap, d, l, SMT_ZERO);
660		} else {
661		    mv = new_movelist(d, s, l);
662		    *fep = mv;
663		    fep = &mv->next;
664		}
665	    } else {
666		syslinux_add_memmap(&memmap, s, l, SMT_FREE);
667	    }
668	}
669    }
670    fclose(f);
671
672    *fep = NULL;
673
674    dprintf("Input move list:\n");
675    syslinux_dump_movelist(frags);
676    dprintf("Input free list:\n");
677    syslinux_dump_memmap(memmap);
678
679    if (syslinux_compute_movelist(&moves, frags, memmap)) {
680	printf("Failed to compute a move sequence\n");
681	return 1;
682    } else {
683	dprintf("Final move list:\n");
684	syslinux_dump_movelist(moves);
685	return 0;
686    }
687}
688
689#endif /* TEST */
690