aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorhpa <hpa>2005-09-25 21:35:44 +0000
committerhpa <hpa>2005-09-25 21:35:44 +0000
commit85ab9fe14674567260cf94ecd4dc845f1988a08b (patch)
treee241d2eaf71df6dd6b7c268ff047781dfe6b9f7a
parent77477d3af776cbc8ffce61cb63ae7a27dbe0a941 (diff)
downloadsyslinux-elf-85ab9fe14674567260cf94ecd4dc845f1988a08b.tar.gz
syslinux-elf-85ab9fe14674567260cf94ecd4dc845f1988a08b.tar.xz
syslinux-elf-85ab9fe14674567260cf94ecd4dc845f1988a08b.zip
Beginnings of a file-moving API
-rw-r--r--com32/include/sys/stat.h9
-rw-r--r--com32/include/sys/types.h2
-rw-r--r--com32/lib/Makefile2
-rw-r--r--com32/lib/sys/fstat.c59
-rw-r--r--com32/lib/sys/read.c4
-rw-r--r--com32/libutil/Makefile3
-rw-r--r--com32/libutil/include/loadfile.h12
-rw-r--r--com32/libutil/include/movebits.h47
-rw-r--r--com32/libutil/loadfile.c72
-rw-r--r--com32/libutil/movebits.c434
-rw-r--r--version2
11 files changed, 640 insertions, 6 deletions
diff --git a/com32/include/sys/stat.h b/com32/include/sys/stat.h
index c0afb914..ffc41059 100644
--- a/com32/include/sys/stat.h
+++ b/com32/include/sys/stat.h
@@ -40,4 +40,13 @@
#define S_IWOTH 00002
#define S_IXOTH 00001
+/* These are the only fields in struct stat we emulate */
+struct stat {
+ mode_t st_mode;
+ off_t st_size;
+};
+
+/* Only fstat() supported */
+int fstat(int, struct stat *);
+
#endif /* _SYS_STAT_H */
diff --git a/com32/include/sys/types.h b/com32/include/sys/types.h
index d7e9cba3..2ab518c0 100644
--- a/com32/include/sys/types.h
+++ b/com32/include/sys/types.h
@@ -11,6 +11,6 @@
typedef ptrdiff_t ssize_t;
typedef int mode_t;
-typedef int64_t off_t;
+typedef size_t off_t;
#endif
diff --git a/com32/lib/Makefile b/com32/lib/Makefile
index 3aa0a620..5f9fb8fd 100644
--- a/com32/lib/Makefile
+++ b/com32/lib/Makefile
@@ -27,7 +27,7 @@ LIBOBJS = \
sys/entry.o sys/exit.o sys/argv.o sys/times.o sys/idle.o \
sys/fileinfo.o sys/opendev.o sys/read.o sys/write.o sys/ftell.o \
sys/close.o sys/open.o sys/fileread.o sys/fileclose.o \
- sys/isatty.o sys/openconsole.o sys/line_input.o \
+ sys/isatty.o sys/fstat.o sys/openconsole.o sys/line_input.o \
sys/stdcon_read.o sys/stdcon_write.o sys/rawcon_read.o \
sys/rawcon_write.o sys/err_read.o sys/err_write.o \
sys/null_read.o sys/null_write.o sys/serial_write.o \
diff --git a/com32/lib/sys/fstat.c b/com32/lib/sys/fstat.c
new file mode 100644
index 00000000..eba47b42
--- /dev/null
+++ b/com32/lib/sys/fstat.c
@@ -0,0 +1,59 @@
+#ident "$Id$"
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2005 H. Peter Anvin - All Rights Reserved
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom
+ * the Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall
+ * be included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * fstat.c
+ *
+ * Very trivial fstat emulation
+ */
+
+#include <sys/stat.h>
+#include <errno.h>
+#include "file.h"
+
+int fstat(int fd, struct stat *buf)
+{
+ struct file_info *fp = &__file_info[fd];
+
+ if ( fd >= NFILES || !fp->iop ) {
+ errno = EBADF;
+ return -1;
+ }
+
+ if ( fp->iop->flags & __DEV_FILE ) {
+ buf->st_mode = S_IFREG | 0444;
+ buf->st_size = fp->i.length;
+ } else {
+ buf->st_mode = S_IFCHR | 0666;
+ buf->st_size = 0;
+ }
+
+ return 0;
+}
+
+
diff --git a/com32/lib/sys/read.c b/com32/lib/sys/read.c
index e461cd46..4f96aad7 100644
--- a/com32/lib/sys/read.c
+++ b/com32/lib/sys/read.c
@@ -42,8 +42,8 @@
ssize_t read(int fd, void *buf, size_t count)
{
struct file_info *fp = &__file_info[fd];
-
- if ( fd >= NFILES || !fp->iop ) {
+
+ if ( fd >= NFILES || !fp->iop ) {
errno = EBADF;
return -1;
}
diff --git a/com32/libutil/Makefile b/com32/libutil/Makefile
index b9d19a5a..d66a8245 100644
--- a/com32/libutil/Makefile
+++ b/com32/libutil/Makefile
@@ -47,7 +47,8 @@ LNXCFLAGS = -I./include -W -Wall -O -g
LNXSFLAGS = -g
LNXLDFLAGS = -g
OBJCOPY = objcopy
-LIBOBJS = ansiline.o ansiraw.o get_key.o idle.o sha1hash.o unbase64.o
+LIBOBJS = ansiline.o ansiraw.o get_key.o idle.o sha1hash.o unbase64.o \
+ movebits.o loadfile.o
LNXLIBOBJS = $(patsubst %.o,%.lo,$(LIBOBJS))
.SUFFIXES: .lss .c .lo .o .elf .c32 .lnx
diff --git a/com32/libutil/include/loadfile.h b/com32/libutil/include/loadfile.h
new file mode 100644
index 00000000..fbda589d
--- /dev/null
+++ b/com32/libutil/include/loadfile.h
@@ -0,0 +1,12 @@
+#ifndef LIBUTIL_LOADFILE_H
+#define LIBUTIL_LOADFILE_H
+
+#include <stddef.h>
+
+/* loadfile() returns the true size of the file, but will guarantee valid,
+ zero-padded memory out to this boundary. */
+#define LOADFILE_ZERO_PAD 64
+
+int loadfile(const char *, void **, size_t *);
+
+#endif
diff --git a/com32/libutil/include/movebits.h b/com32/libutil/include/movebits.h
new file mode 100644
index 00000000..de6ee1ff
--- /dev/null
+++ b/com32/libutil/include/movebits.h
@@ -0,0 +1,47 @@
+#ifndef LIBUTIL_MOVEBITS_H
+#define LIBUTIL_MOVEBITS_H
+
+#include <inttypes.h>
+#include <setjmp.h>
+
+struct movelist {
+ uintptr_t dst;
+ uintptr_t src;
+ uintptr_t len;
+ struct movelist *next;
+};
+
+struct move_descriptor {
+ uint32_t dst;
+ uint32_t src;
+ uint32_t len;
+};
+
+/*
+ * Creates a movelist consisting of only one element, and
+ * if parent == NULL insert into the movelist chain immediately after
+ * the parent element.
+ */
+struct movelist *
+make_movelist(struct movelist *parent, uintptr_t dst,
+ uintptr_t src, uintptr_t len);
+
+/*
+ * Convert a movelist into a linear array of struct move_descriptors,
+ * returning the number of descriptors and freeing the movelist.
+ *
+ * Returns (size_t)-1 on failure; if so the movelist is still valid.
+ */
+size_t
+linearize_movelist(struct move_descriptor **d, struct movelist *m);
+
+/*
+ * moves is computed from "frags" and "freemem". "space" lists
+ * free memory areas at our disposal, and is (src, cnt) only.
+ */
+
+int
+compute_movelist(struct movelist **moves, struct movelist *frags,
+ struct movelist *space);
+
+#endif /* LIBUTIL_MOVEBITS_H */
diff --git a/com32/libutil/loadfile.c b/com32/libutil/loadfile.c
new file mode 100644
index 00000000..05f71184
--- /dev/null
+++ b/com32/libutil/loadfile.c
@@ -0,0 +1,72 @@
+#ident "$Id$"
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2005 H. Peter Anvin - All Rights Reserved
+ *
+ * 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
+ * the Free Software Foundation, Inc., 53 Temple Place Ste 330,
+ * Boston MA 02111-1307, USA; either version 2 of the License, or
+ * (at your option) any later version; incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * loadfile.c
+ *
+ * Read the contents of a data file into a malloc'd buffer
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+
+#include "loadfile.h"
+
+int loadfile(const char *filename, void **ptr, size_t *len)
+{
+ int fd;
+ struct stat st;
+ void *data;
+ FILE *f;
+ size_t xlen;
+
+ fd = open(filename, O_RDONLY);
+ if ( fd < 0 )
+ return -1;
+
+ f = fdopen(fd, "rb");
+ if ( !f ) {
+ close(fd);
+ return -1;
+ }
+
+ if ( fstat(fd, &st) )
+ goto err_fclose;
+
+ *len = st.st_size;
+ xlen = (st.st_size + LOADFILE_ZERO_PAD-1) & ~(LOADFILE_ZERO_PAD-1);
+
+ *ptr = data = malloc(xlen);
+ if ( !data )
+ goto err_fclose;
+
+ if ( (off_t)fread(data, 1, st.st_size, f) != st.st_size )
+ goto err_free;
+
+ memset((char *)data + st.st_size, 0, xlen-st.st_size);
+
+ fclose(f);
+ return 0;
+
+ err_free:
+ free(data);
+ err_fclose:
+ fclose(f);
+ return -1;
+}
+
+
diff --git a/com32/libutil/movebits.c b/com32/libutil/movebits.c
new file mode 100644
index 00000000..07cc59f9
--- /dev/null
+++ b/com32/libutil/movebits.c
@@ -0,0 +1,434 @@
+#include <assert.h>
+#include <stdio.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include <setjmp.h>
+
+#include "movebits.h"
+
+#ifdef TEST
+# define dprintf printf
+#else
+# define dprintf(...) ((void)0)
+#endif
+
+#define min(x,y) ((x) < (y) ? (x) : (y))
+#define max(x,y) ((x) > (y) ? (x) : (y))
+
+/*
+ * Public utility function
+ *
+ * Creates a movelist consisting of only one element, and
+ * if parent == NULL insert into the movelist chain immediately after
+ * the parent element.
+ */
+struct movelist *
+make_movelist(struct movelist *pptr, uintptr_t dst, uintptr_t src, uintptr_t len)
+{
+ struct movelist *ml = malloc(sizeof(struct movelist));
+
+ if ( !ml )
+ return NULL;
+
+ ml->dst = dst;
+ ml->src = src;
+ ml->len = len;
+ ml->next = pptr ? pptr->next : NULL;
+
+ if ( pptr )
+ pptr->next = ml;
+
+ return ml;
+}
+
+/*
+ * Public utility function
+ *
+ * Convert a movelist into a linear array of struct move_descriptors
+ */
+size_t
+linearize_movelist(struct move_descriptor **d, struct movelist *m)
+{
+ size_t n;
+ struct movelist *mm;
+ struct move_descriptor *l;
+
+ /* Count the length of the list */
+ n = 0;
+ for ( mm = m ; mm ; mm = mm->next )
+ n++;
+
+ *d = l = malloc(n * sizeof(struct move_descriptor));
+ if ( !l )
+ return (size_t)-1;
+
+ while ( m ) {
+ l->dst = m->dst;
+ l->src = m->src;
+ l->len = m->len;
+ l++;
+ mm = m;
+ m = m->next;
+ free(mm);
+ }
+
+ return n;
+}
+
+
+static jmp_buf new_movelist_bail;
+
+static struct movelist *
+new_movelist(uintptr_t dst, uintptr_t src, uintptr_t len)
+{
+ struct movelist *ml = malloc(sizeof(struct movelist));
+
+ if ( !ml )
+ longjmp(new_movelist_bail, 1);
+
+ ml->dst = dst;
+ ml->src = src;
+ ml->len = len;
+ ml->next = NULL;
+
+ return ml;
+}
+
+static struct movelist **
+split_movelist(uintptr_t start, uintptr_t len, struct movelist **parentptr)
+{
+ struct movelist *m, *ml = *parentptr;
+
+ assert(start >= ml->src);
+ assert(start < ml->src+ml->len);
+
+ /* Split off the beginning */
+ if ( start > ml->src ) {
+ uintptr_t l = start - ml->src;
+
+ m = new_movelist(ml->dst+l, start, ml->len-l);
+ m->next = ml->next;
+ ml->len = l;
+ ml->next = m;
+
+ parentptr = &ml->next;
+ ml = m; /* Continue processing the new node */
+ }
+
+ if ( ml->len > len ) {
+ uintptr_t l = ml->len - len;
+
+ m = new_movelist(ml->dst+len, ml->src+len, l);
+ m->next = ml->next;
+ ml->len = len;
+ ml->next = m;
+ }
+
+ return parentptr;
+}
+
+#if 0
+static void
+delete_movelist(struct movelist **parentptr)
+{
+ struct movelist *o = *parentptr;
+ *parentptr = o->next;
+ free(o);
+}
+#endif
+
+/*
+ * Scan the freelist looking for a particular chunk of memory
+ */
+static struct movelist **
+is_free_zone(uintptr_t start, uintptr_t len, struct movelist **space)
+{
+ struct movelist *s;
+
+ while ( (s = *space) ) {
+ if ( s->src <= start && s->src+s->len >= start+len )
+ return space;
+ space = &s->next;
+ }
+
+ return NULL;
+}
+
+/*
+ * Scan the freelist looking for the smallest chunk of memory which
+ * can fit X bytes
+ */
+static struct movelist **
+free_area(uintptr_t len, struct movelist **space)
+{
+ struct movelist **best = NULL;
+ struct movelist *s;
+
+ while ( (s = *space) ) {
+ if ( s->len >= len ) {
+ if ( !best || (*best)->len > s->len )
+ best = space;
+ }
+ space = &s->next;
+ }
+
+ return best;
+}
+
+
+/*
+ * Scan the freelist looking for the largest chunk of memory, returns parent ptr
+ */
+static struct movelist **
+free_area_max(struct movelist **space)
+{
+ struct movelist **best = NULL;
+ struct movelist *s;
+
+ while ( (s = *space) ) {
+ if ( !best || s->len > (*best)->len )
+ best = space;
+ space = &s->next;
+ }
+
+ return best;
+}
+
+/*
+ * Remove a chunk from the freelist
+ */
+static void
+allocate_from(uintptr_t start, uintptr_t len, struct movelist **parentptr)
+{
+ struct 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);
+}
+
+/*
+ * 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 movelist **frags, struct movelist **space)
+{
+ struct movelist **sep;
+ struct 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;
+ }
+}
+
+/*
+ * moves is computed from "frags" and "freemem". "space" lists
+ * free memory areas at our disposal, and is (src, cnt) only.
+ */
+
+int
+compute_movelist(struct movelist **moves, struct movelist *frags,
+ struct movelist *space)
+{
+ struct movelist *mv;
+ struct movelist *f, **fp, **ep;
+ struct movelist *o, **op;
+ uintptr_t needbase, needlen, copysrc, copydst, copylen;
+ uintptr_t freebase, freelen;
+
+ *moves = NULL;
+
+ if ( setjmp(new_movelist_bail) )
+ return -1; /* malloc() failed */
+
+ tidy_freelist(&frags, &space);
+
+ for ( fp = &frags, f = *fp ; f ; fp = &f->next, f = *fp ) {
+ dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+ f->len, f->src, f->dst);
+
+ if ( f->src == f->dst ) {
+ //delete_movelist(fp); /* Already in the right place! */
+ continue;
+ }
+
+ /* See if we can move this chunk into place by claiming
+ the destination, or in the case of partial overlap, the
+ missing portion. */
+
+ needbase = f->dst;
+ needlen = f->len;
+
+ dprintf("need: base = 0x%08x, len = 0x%08x\n", needbase, needlen);
+
+ if ( f->src < f->dst && (f->dst - f->src) < f->len ) {
+ /* "Shift up" type overlap */
+ needlen = f->dst - f->src;
+ needbase = f->dst + (f->len - needlen);
+ } else if ( f->src > f->dst && (f->src - f->dst) < f->len ) {
+ /* "Shift down" type overlap */
+ needbase = f->dst;
+ needlen = f->src - f->dst;
+ }
+
+ if ( (ep = is_free_zone(needbase, 1, &space)) ) {
+ /* We can move at least part of this chunk into place without further ado */
+ copylen = min(needlen, (*ep)->len);
+ allocate_from(needbase, copylen, ep);
+ goto move_chunk;
+ }
+
+ /* At this point, we need to evict something out of our space.
+ Find the object occupying the first byte of our target space,
+ and move it out (the whole object if we can, otherwise a subset.)
+ Then move a chunk of ourselves into place. */
+ for ( op = &f->next, o = *op ; o ; op = &o->next, o = *op ) {
+
+ dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+ o->len, o->src, o->dst);
+
+ if ( !(o->src <= needbase && o->src+o->len > needbase) )
+ continue; /* Not what we're looking for... */
+
+ /* Find somewhere to put it... */
+ if ( (ep = free_area(o->len, &space)) ) {
+ /* We got what we wanted... */
+ copydst = (*ep)->src;
+ copylen = o->len;
+ } else {
+ ep = free_area_max(&space);
+ if ( !ep )
+ return -1; /* Stuck! */
+ copydst = (*ep)->src;
+ copylen = (*ep)->len;
+ }
+ allocate_from(copydst, copylen, ep);
+
+ if ( copylen >= o->len - (needbase-o->src) ) {
+ copysrc = o->src + (o->len - copylen);
+ } else {
+ copysrc = o->src;
+ }
+
+ if ( copylen < o->len ) {
+ op = split_movelist(copysrc, copylen, op);
+ o = *op;
+ }
+
+ mv = new_movelist(copydst, copysrc, copylen);
+ dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+ mv->len, mv->src, mv->dst);
+ *moves = mv;
+ moves = &mv->next;
+
+ o->src = copydst;
+
+ 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;
+ copylen -= (needbase-copysrc);
+ }
+ if ( copylen > needlen ) {
+ mv = new_movelist(0, copysrc+needlen, copylen-needlen);
+ mv->next = space;
+ space = mv;
+ copylen = needlen;
+ }
+ }
+ goto move_chunk;
+ }
+ return -1; /* Stuck! */
+
+ move_chunk:
+ /* We're allowed to move the chunk into place now. */
+
+ if ( copylen < needlen ) {
+ /* Didn't get all we wanted, so we have to split the chunk */
+ fp = split_movelist(f->src, copylen+(needbase-f->dst), fp);
+ f = *fp;
+ }
+
+ mv = new_movelist(f->dst, f->src, f->len);
+ dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+ mv->len, mv->src, mv->dst);
+ *moves = mv;
+ moves = &mv->next;
+
+ /* Figure out what memory we just freed up */
+ if ( f->dst > f->src ) {
+ freebase = f->src;
+ freelen = min(f->len, f->dst-f->src);
+ } else if ( f->src >= f->dst+f->len ) {
+ freebase = f->src;
+ freelen = f->len;
+ } else {
+ freelen = f->src-f->dst;
+ freebase = f->dst+f->len;
+ }
+
+ mv = new_movelist(0, freebase, freelen);
+ mv->next = space;
+ space = mv;
+ }
+
+ return 0;
+}
+
+#ifdef TEST
+
+#include <stdio.h>
+
+int main(int argc, char *argv[])
+{
+ FILE *f;
+ unsigned long d, s, l;
+ struct movelist *frags;
+ struct movelist **fep = &frags;
+ struct movelist *space;
+ struct movelist **sep = &space;
+ struct movelist *mv, *moves;
+
+ f = fopen(argv[1], "r");
+ while ( fscanf(f, "%lx %lx %lx", &d, &s, &l) == 3 ) {
+ if ( d ) {
+ mv = new_movelist(d, s, l);
+ *fep = mv;
+ fep = &mv->next;
+ } else {
+ mv = new_movelist(0, s, l);
+ *sep = mv;
+ sep = &mv->next;
+ }
+ }
+ fclose(f);
+
+ if ( compute_movelist(&moves, frags, space) ) {
+ 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);
+ }
+ return 0;
+ }
+}
+
+#endif /* TEST */
+
diff --git a/version b/version
index 2c073331..b9582926 100644
--- a/version
+++ b/version
@@ -1 +1 @@
-3.11
+3.20