From 85ab9fe14674567260cf94ecd4dc845f1988a08b Mon Sep 17 00:00:00 2001 From: hpa Date: Sun, 25 Sep 2005 21:35:44 +0000 Subject: [PATCH] Beginnings of a file-moving API --- com32/include/sys/stat.h | 9 + com32/include/sys/types.h | 2 +- com32/lib/Makefile | 2 +- com32/lib/sys/fstat.c | 59 ++++++ com32/lib/sys/read.c | 4 +- com32/libutil/Makefile | 3 +- com32/libutil/include/loadfile.h | 12 ++ com32/libutil/include/movebits.h | 47 +++++ com32/libutil/loadfile.c | 72 +++++++ com32/libutil/movebits.c | 434 +++++++++++++++++++++++++++++++++++++++ version | 2 +- 11 files changed, 640 insertions(+), 6 deletions(-) create mode 100644 com32/lib/sys/fstat.c create mode 100644 com32/libutil/include/loadfile.h create mode 100644 com32/libutil/include/movebits.h create mode 100644 com32/libutil/loadfile.c create mode 100644 com32/libutil/movebits.c diff --git a/com32/include/sys/stat.h b/com32/include/sys/stat.h index c0afb91..ffc4105 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 d7e9cba..2ab518c 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 3aa0a62..5f9fb8f 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 0000000..eba47b4 --- /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 +#include +#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 e461cd4..4f96aad 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 b9d19a5..d66a824 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 0000000..fbda589 --- /dev/null +++ b/com32/libutil/include/loadfile.h @@ -0,0 +1,12 @@ +#ifndef LIBUTIL_LOADFILE_H +#define LIBUTIL_LOADFILE_H + +#include + +/* 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 0000000..de6ee1f --- /dev/null +++ b/com32/libutil/include/movebits.h @@ -0,0 +1,47 @@ +#ifndef LIBUTIL_MOVEBITS_H +#define LIBUTIL_MOVEBITS_H + +#include +#include + +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 0000000..05f7118 --- /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 +#include +#include +#include +#include +#include + +#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 0000000..07cc59f --- /dev/null +++ b/com32/libutil/movebits.c @@ -0,0 +1,434 @@ +#include +#include +#include +#include +#include +#include + +#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 + +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 2c07333..b958292 100644 --- a/version +++ b/version @@ -1 +1 @@ -3.11 +3.20 -- 2.7.4