summaryrefslogtreecommitdiff
path: root/com32/lib/syslinux/movebits.c
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2008-04-08 16:47:12 -0700
committerH. Peter Anvin <hpa@zytor.com>2008-04-08 16:47:12 -0700
commit16d2e6eaaa01b147d8e85ccb31c85e0f713369a7 (patch)
tree5b7a90660b24f049aa3acc5f62b6dec8c24e1f3e /com32/lib/syslinux/movebits.c
parentc9cc284ca6ce22d94470cb03029bf2e9a64287df (diff)
downloadsyslinux-16d2e6eaaa01b147d8e85ccb31c85e0f713369a7.tar.gz
movebits: use the memmap data structure for the freelist
Use the syslinux_memmap data structure for the free memory list. This means we get range coalescing; this sometimes generates lists that are vastly shorter than without range coalescing.
Diffstat (limited to 'com32/lib/syslinux/movebits.c')
-rw-r--r--com32/lib/syslinux/movebits.c232
1 files changed, 80 insertions, 152 deletions
diff --git a/com32/lib/syslinux/movebits.c b/com32/lib/syslinux/movebits.c
index c9253396..1258e23b 100644
--- a/com32/lib/syslinux/movebits.c
+++ b/com32/lib/syslinux/movebits.c
@@ -97,6 +97,14 @@ dup_movelist(struct syslinux_movelist *src)
return dst;
}
+static void
+add_freelist(struct syslinux_memmap **mmap, addr_t start,
+ addr_t len, enum syslinux_memmap_types type)
+{
+ if (syslinux_add_memmap(mmap, start, len, type))
+ longjmp(new_movelist_bail, 1);
+}
+
/*
* Take a chunk, entirely confined in **parentptr, and split it off so that
* it has its own structure.
@@ -153,103 +161,58 @@ free_movelist(struct syslinux_movelist **parentptr)
/*
* Scan the freelist looking for a particular chunk of memory
*/
-static struct syslinux_movelist **
-is_free_zone(addr_t start, addr_t len, struct syslinux_movelist **space)
+static const struct syslinux_memmap *
+is_free_zone(const struct syslinux_memmap *mmap, addr_t start, addr_t len)
{
- struct syslinux_movelist *s;
+ while (mmap->next->type != SMT_END && mmap->next->start < start)
+ mmap = mmap->next;
- while ( (s = *space) ) {
- if ( s->src <= start && s->src+s->len >= start+len )
- return space;
- space = &s->next;
- }
+ if (mmap->start > start)
+ return NULL;
+ if (mmap->next->start - mmap->start < len)
+ return NULL;
- return NULL;
+ return mmap->type == SMT_FREE ? mmap : NULL;
}
/*
* Scan the freelist looking for the smallest chunk of memory which
- * can fit X bytes
+ * can fit X bytes; returns the length of the block on success.
*/
-static struct syslinux_movelist **
-free_area(addr_t len, struct syslinux_movelist **space)
+static addr_t free_area(const struct syslinux_memmap *mmap,
+ addr_t len, addr_t *start)
{
- struct syslinux_movelist **best = NULL;
- struct syslinux_movelist *s;
-
- while ( (s = *space) ) {
- if ( s->len >= len ) {
- if ( !best || (*best)->len > s->len )
- best = space;
+ const struct syslinux_memmap *best = NULL;
+ const struct syslinux_memmap *s;
+ addr_t slen, best_len = -1;
+
+ for (s = mmap; s->type != SMT_END; s = s->next) {
+ slen = s->next->start - s->start;
+ if (slen >= len) {
+ if (!best || best_len > slen) {
+ best = s;
+ best_len = slen;
+ }
}
- space = &s->next;
}
- return best;
-}
-
-
-/*
- * Scan the freelist looking for the largest chunk of memory,
- * returns parent ptr
- */
-static struct syslinux_movelist **
-free_area_max(struct syslinux_movelist **space)
-{
- struct syslinux_movelist **best = NULL;
- struct syslinux_movelist *s;
-
- while ( (s = *space) ) {
- if ( !best || s->len > (*best)->len )
- best = space;
- space = &s->next;
+ if (best) {
+ *start = best->start;
+ return best_len;
+ } else {
+ return 0;
}
-
- return best;
}
/*
* Remove a chunk from the freelist
*/
-static void
-allocate_from(addr_t start, addr_t len, struct syslinux_movelist **parentptr)
+static inline void
+allocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len)
{
- struct syslinux_movelist *c = *parentptr;
-
- assert(c->src <= start);
- assert(c->src+c->len >= start+len);
-
- if ( c->src != start || c->len != len ) {
- parentptr = split_movelist(start, len, parentptr);
- c = *parentptr;
- }
-
- *parentptr = c->next;
- free(c);
+ syslinux_add_memmap(mmap, start, len, SMT_ALLOC);
}
-#if 0
-/*
- * Remove any chunk from the freelist which is already
- * claimed by source data. This somewhat frivolously
- * assumes that the fragments are either completely
- * covered by a free zone or not covered at all.
- */
-static void
-tidy_freelist(struct syslinux_movelist **frags,
- struct syslinux_movelist **space)
-{
- struct syslinux_movelist **sep;
- struct syslinux_movelist *f;
-
- while ( (f = *frags) ) {
- if ( (sep = is_free_zone(f->src, f->len, space)) )
- allocate_from(f->src, f->len, sep);
- frags = &f->next;
- }
-}
-#endif
-
/*
* moves is computed from "frags" and "freemem". "space" lists
* free memory areas at our disposal, and is (src, cnt) only.
@@ -260,16 +223,18 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
struct syslinux_movelist *ifrags,
struct syslinux_memmap *memmap)
{
- struct syslinux_memmap *mmap = NULL, *mm;
+ struct syslinux_memmap *mmap = NULL;
+ const struct syslinux_memmap *mm, *ep;
struct syslinux_movelist *frags = NULL;
- struct syslinux_movelist *mv, *space;
- struct syslinux_movelist *f, **fp, **ep;
+ struct syslinux_movelist *mv;
+ struct syslinux_movelist *f, **fp;
struct syslinux_movelist *o, **op;
addr_t needbase, needlen, copysrc, copydst, copylen;
addr_t freebase, freelen;
- addr_t mstart, avail;
+ addr_t avail;
+ addr_t fstart, flen;
addr_t cbyte;
- int m_ok;
+ addr_t ep_len;
int rv = -1;
int reverse;
int again;
@@ -277,68 +242,34 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
dprintf("entering syslinux_compute_movelist()...\n");
if (setjmp(new_movelist_bail)) {
+ nomem:
dprintf("Out of working memory!\n");
goto bail;
}
*moves = NULL;
- /* Mark any memory that's in use by source material busy in the memory map */
- mmap = syslinux_dup_memmap(memmap);
+ /* Create our memory map. Anything that is SMT_FREE or SMT_ZERO is
+ fair game, but mark anything used by source material as SMT_ALLOC. */
+ mmap = syslinux_init_memmap();
if (!mmap)
- goto bail;
+ goto nomem;
frags = dup_movelist(ifrags);
-#if DEBUG
- dprintf("Initial memory map:\n");
- syslinux_dump_memmap(stdout, mmap);
-#endif
+ 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);
- for (f = frags; f; f = f->next) {
- if (syslinux_add_memmap(&mmap, f->src, f->len, SMT_ALLOC)) {
- dprintf("Cannot generate free map\n");
- goto bail;
- }
- }
-
-#if DEBUG
- dprintf("Adjusted memory map:\n");
- syslinux_dump_memmap(stdout, mmap);
-#endif
-
- /* Compute the freelist in movelist format. */
- space = NULL;
- ep = &space;
- mstart = -1;
- m_ok = 0;
-
- /* Yes, we really do want to run through the loop on SMT_END */
- for (mm = mmap; mm; mm = mm->next) {
- /* We can safely use to-be-zeroed memory as a scratch area. */
- if (mmap->type == SMT_FREE || mmap->type == SMT_ZERO) {
- if (!m_ok) {
- m_ok = 1;
- mstart = mmap->start;
- }
- } else {
- if (m_ok) {
- f = new_movelist(0, mstart, mmap->start - mstart);
- *ep = f;
- ep = &f->next;
- m_ok = 0;
- }
- }
-
- mmap = mmap->next;
- }
+ for (f = frags; f; f = f->next)
+ add_freelist(&mmap, f->src, f->len, SMT_ALLOC);
do {
again = 0;
#if DEBUG
dprintf("Current free list:\n");
- syslinux_dump_movelist(stdout, space);
+ syslinux_dump_memmap(stdout, mmap);
dprintf("Current frag list:\n");
syslinux_dump_movelist(stdout, frags);
#endif
@@ -380,12 +311,13 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
"reverse = %d, cbyte = 0x%08x\n",
needbase, needlen, reverse, cbyte);
- ep = is_free_zone(cbyte, 1, &space);
+ ep = is_free_zone(mmap, cbyte, 1);
if (ep) {
+ ep_len = ep->next->start - ep->start;
if (reverse)
- avail = needbase+needlen - (*ep)->src;
+ avail = needbase+needlen - ep->start;
else
- avail = (*ep)->len - (needbase - (*ep)->src);
+ avail = ep_len - (needbase - ep->start);
} else {
avail = 0;
}
@@ -394,13 +326,13 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
/* We can move at least part of this chunk into place without
further ado */
dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
- (*ep)->src, (*ep)->len, avail);
+ ep->start, ep_len, avail);
copylen = min(needlen, avail);
if (reverse)
- allocate_from(needbase+needlen-copylen, copylen, ep);
+ allocate_from(&mmap, needbase+needlen-copylen, copylen);
else
- allocate_from(needbase, copylen, ep);
+ allocate_from(&mmap, needbase, copylen);
goto move_chunk;
}
@@ -419,33 +351,32 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
/* Find somewhere to put it... */
- if ( (ep = is_free_zone(o->dst, o->len, &space)) ) {
+ if ( is_free_zone(mmap, o->dst, o->len) ) {
/* Score! We can move it into place directly... */
copydst = o->dst;
copylen = o->len;
- } else if ( (ep = free_area(o->len, &space)) ) {
+ } else if ( free_area(mmap, o->len, &fstart) ) {
/* We can move the whole chunk */
- copydst = (*ep)->src;
+ copydst = fstart;
copylen = o->len;
} else {
/* Well, copy as much as we can... */
- ep = free_area_max(&space);
- if ( !ep ) {
+ if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) {
dprintf("No free memory at all!\n");
goto bail; /* Stuck! */
}
/* Make sure we include the critical byte */
- copydst = (*ep)->src;
+ copydst = fstart;
if (reverse) {
- copysrc = max(o->src, cbyte+1 - (*ep)->len);
+ copysrc = max(o->src, cbyte+1 - flen);
copylen = cbyte+1 - copysrc;
} else {
copysrc = cbyte;
- copylen = min((*ep)->len, o->len - (cbyte-o->src));
+ copylen = min(flen, o->len - (cbyte-o->src));
}
}
- allocate_from(copydst, copylen, ep);
+ allocate_from(&mmap, copydst, copylen);
if ( copylen < o->len ) {
op = split_movelist(copysrc, copylen, op);
@@ -463,15 +394,11 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
if ( copylen > needlen ) {
/* We don't need all the memory we freed up. Mark it free. */
if ( copysrc < needbase ) {
- mv = new_movelist(0, copysrc, needbase-copysrc);
- mv->next = space;
- space = mv;
+ add_freelist(&mmap, copysrc, needbase-copysrc, SMT_FREE);
copylen -= (needbase-copysrc);
}
if ( copylen > needlen ) {
- mv = new_movelist(0, copysrc+needlen, copylen-needlen);
- mv->next = space;
- space = mv;
+ add_freelist(&mmap, copysrc+needlen, copylen-needlen, SMT_FREE);
copylen = needlen;
}
}
@@ -494,7 +421,7 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
copydst += (f->len-copylen);
copysrc += (f->len-copylen);
}
-
+
dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
copylen, copysrc, copydst);
@@ -509,6 +436,9 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
*moves = mv;
moves = &mv->next;
+ /* Mark the new memory range occupied */
+ add_freelist(&mmap, f->dst, f->len, SMT_ALLOC);
+
/* Figure out what memory we just freed up */
if ( f->dst > f->src ) {
freebase = f->src;
@@ -523,10 +453,8 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
- mv = new_movelist(0, freebase, freelen);
- mv->next = space;
- space = mv;
-
+ add_freelist(&mmap, freebase, freelen, SMT_FREE);
+
delete_movelist(fp);
again = 1; /* At least one chunk was moved */
}