[Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Lauri Leukkunen]

[-- Attachment #1: Type: text/plain, Size: 402 bytes --]

Attached patch fixes the linux-user path mangling code for use with
real target root filesystems that have nasty symlinks and lots of
files. The old code is terribly slow and can easily end up going
through the entire host system /usr hierarchy in a recursive loop.

Compared to the previous version of this patch, fixes an issue with
attempting to free() a pointer returned by GNU basename().

/lauri

[-- Attachment #2: qemu-linux-user-path2.diff --]
[-- Type: text/x-diff, Size: 8645 bytes --]

Index: linux-user/path.c
===================================================================
RCS file: /sources/qemu/qemu/linux-user/path.c,v
retrieving revision 1.2
diff -u -r1.2 path.c
--- linux-user/path.c	13 Sep 2004 21:39:32 -0000	1.2
+++ linux-user/path.c	21 May 2007 23:06:54 -0000
@@ -3,145 +3,201 @@
 
    The assumption is that this area does not change.
 */
+
+#define _GNU_SOURCE
+
 #include <sys/types.h>
 #include <dirent.h>
 #include <unistd.h>
 #include <stdlib.h>
-#include <string.h>
 #include <errno.h>
 #include <stdio.h>
+#include <string.h>
 #include "qemu.h"
 
-struct pathelem
-{
-    /* Name of this, eg. lib */
-    char *name;
-    /* Full path name, eg. /usr/gnemul/x86-linux/lib. */
-    char *pathname;
-    struct pathelem *parent;
-    /* Children */
-    unsigned int num_entries;
-    struct pathelem *entries[0];
-};
-
-static struct pathelem *base;
-
-/* First N chars of S1 match S2, and S2 is N chars long. */
-static int strneq(const char *s1, unsigned int n, const char *s2)
-{
-    unsigned int i;
-
-    for (i = 0; i < n; i++)
-	if (s1[i] != s2[i])
-	    return 0;
-    return s2[i] == 0;
-}
+char *base = NULL;
 
-static struct pathelem *add_entry(struct pathelem *root, const char *name);
+struct path_entry {
+    struct path_entry *prev;
+    struct path_entry *next;
+    char name[PATH_MAX];
+};
 
-static struct pathelem *new_entry(const char *root,
-				  struct pathelem *parent,
-				  const char *name)
+char *decolonize_path(const char *path)
 {
-    struct pathelem *new = malloc(sizeof(*new));
-    new->name = strdup(name);
-    asprintf(&new->pathname, "%s/%s", root, name);
-    new->num_entries = 0;
-    return new;
-}
-
-#define streq(a,b) (strcmp((a), (b)) == 0)
+    char *cpath, *index, *start;
+    char cwd[PATH_MAX];
+    struct path_entry list;
+    struct path_entry *work;
+    struct path_entry *new;
+    char *buf = NULL;
 
-static struct pathelem *add_dir_maybe(struct pathelem *path)
-{
-    DIR *dir;
+    if (!path) {
+        return NULL;
+    }
 
-    if ((dir = opendir(path->pathname)) != NULL) {
-	struct dirent *dirent;
+    buf = malloc((PATH_MAX + 1) * sizeof(char));
+    memset(buf, '\0', PATH_MAX + 1);
 
-	while ((dirent = readdir(dir)) != NULL) {
-	    if (!streq(dirent->d_name,".") && !streq(dirent->d_name,"..")){
-		path = add_entry(path, dirent->d_name);
-	    }
-	}
-        closedir(dir);
+    list.next = NULL;
+    list.prev = NULL;
+    work = &list;
+
+    if (path[0] != '/') {
+        /* not an absolute path */
+        memset(cwd, '\0', PATH_MAX);
+        if (getcwd(cwd, PATH_MAX) < 0) {
+            perror("error getting current work dir\n");
+            return NULL;
+        }
+        unsigned int l = (strlen(cwd) + 1 + strlen(path) + 1);
+        cpath = malloc((strlen(cwd) + 1
+                        + strlen(path) + 1) * sizeof(char));
+        memset(cpath, '\0', l);
+        strcpy(cpath, cwd);
+        strcat(cpath, "/");
+        strcat(cpath, path);
+    } else {
+        cpath = strdup(path);
     }
-    return path;
-}
 
-static struct pathelem *add_entry(struct pathelem *root, const char *name)
-{
-    root->num_entries++;
-
-    root = realloc(root, sizeof(*root)
-		   + sizeof(root->entries[0])*root->num_entries);
+    start = cpath + 1;          /* ignore leading '/' */
+    while (1) {
+        index = strstr(start, "/");
+        if (!index) {
+            /* add the last item */
+            new = malloc(sizeof(struct path_entry));
+            memset(new->name, '\0', PATH_MAX);
+            new->prev = work;
+            work->next = new;
+            new->next = NULL;
+            strcpy(new->name, start);
+            work = new;
+            break;
+        }
+        *index = '\0';
+        if (index == (start)) {
+            goto proceed;       /* skip over empty strings 
+                                   resulting from // */
+        }
+
+        if (strcmp(start, "..") == 0) {
+            /* travel up one */
+            if (!work->prev)
+                goto proceed;
+            work = work->prev;
+            free(work->next);
+            work->next = NULL;
+        } else if (strcmp(start, ".") == 0) {
+            /* ignore */
+            goto proceed;
+        } else {
+            /* add an entry to our path_entry list */
+            new = malloc(sizeof(struct path_entry));
+            memset(new->name, '\0', PATH_MAX);
+            new->prev = work;
+            work->next = new;
+            new->next = NULL;
+            strcpy(new->name, start);
+            work = new;
+        }
+
+      proceed:
+        *index = '/';
+        start = index + 1;
+    }
 
-    root->entries[root->num_entries-1] = new_entry(root->pathname, root, name);
-    root->entries[root->num_entries-1]
-	= add_dir_maybe(root->entries[root->num_entries-1]);
-    return root;
+    work = list.next;
+    while (work) {
+        struct path_entry *tmp;
+        strcat(buf, "/");
+        strcat(buf, work->name);
+        tmp = work;
+        work = work->next;
+        free(tmp);
+    }
+    return buf;
 }
 
-/* This needs to be done after tree is stabalized (ie. no more reallocs!). */
-static void set_parents(struct pathelem *child, struct pathelem *parent)
-{
-    unsigned int i;
-
-    child->parent = parent;
-    for (i = 0; i < child->num_entries; i++)
-	set_parents(child->entries[i], child);
-}
 
 void init_paths(const char *prefix)
 {
-    if (prefix[0] != '/' ||
-        prefix[0] == '\0' ||
-        !strcmp(prefix, "/"))
-        return;
-
-    base = new_entry("", NULL, prefix+1);
-    base = add_dir_maybe(base);
-    if (base->num_entries == 0) {
-        free (base);
-        base = NULL;
-    } else {
-        set_parents(base, base);
-    }
+    base = strdup(prefix);
 }
 
-/* FIXME: Doesn't handle DIR/.. where DIR is not in emulated dir. */
-static const char *
-follow_path(const struct pathelem *cursor, const char *name)
+
+
+char *adjust_for_leakage(char *path)
 {
-    unsigned int i, namelen;
+    char tmp[PATH_MAX + 1];
+    char tmp2[PATH_MAX + 1];
+    char *buf;
+    char *bname = NULL, *dname = NULL;
+    int i;
 
-    name += strspn(name, "/");
-    namelen = strcspn(name, "/");
+    if (!path)
+        return NULL;
 
-    if (namelen == 0)
-	return cursor->pathname;
+    memset(tmp, '\0', PATH_MAX + 1);
+    memset(tmp2, '\0', PATH_MAX + 1);
+    if ((i = readlink(path, tmp, PATH_MAX) < 0)) {
+        /* not a symlink */
+        return strdup(path);
+    }
 
-    if (strneq(name, namelen, ".."))
-	return follow_path(cursor->parent, name + namelen);
+    bname = basename(path); /* relying on GNU version of basename */
+    dname = dirname(strdup(path));
 
-    if (strneq(name, namelen, "."))
-	return follow_path(cursor, name + namelen);
+    /* check if the symlink refers to itself */
+    if (strcmp(tmp, bname) == 0) {
+        /* symlink refers to itself */
+        return strdup(path);
+    }
 
-    for (i = 0; i < cursor->num_entries; i++)
-	if (strneq(name, namelen, cursor->entries[i]->name))
-	    return follow_path(cursor->entries[i], name + namelen);
+    /* make tmp absolute if it's not */
+    if (tmp[0] != '/') {
+        strcpy(tmp2, dname);
+        strcat(tmp2, "/");
+        strcat(tmp2, tmp);
+    }
 
-    /* Not found */
-    return NULL;
+    /* remove "." and ".." entries from tmp2 */
+    buf = decolonize_path(tmp2);
+    strcpy(tmp2, buf);
+
+    free(buf);
+    /* bname is not free'd, because GNU basename returns a pointer
+     * to its own buffer */
+    free(dname);
+
+    if (strncmp(tmp2, base, strlen(base)) != 0) {
+        /* tried to leak out, fix it */
+        strcpy(tmp, base);
+        strcpy(tmp, "/");
+        strcpy(tmp, tmp2);
+        return adjust_for_leakage(tmp);
+    } else {
+        return adjust_for_leakage(tmp2);
+    }
 }
 
 /* Look for path in emulation dir, otherwise return name. */
 const char *path(const char *name)
 {
-    /* Only do absolute paths: quick and dirty, but should mostly be OK.
-       Could do relative by tracking cwd. */
-    if (!base || name[0] != '/')
-	return name;
+    char *tmp, *ret;
 
-    return follow_path(base, name) ?: name;
+    if (strncmp(name, base, strlen(base)) == 0) {
+        /* name is within emulation dir */
+        ret = adjust_for_leakage(name);
+    } else {
+        /* name is elsewhere, use base + "/" + name */
+        tmp = malloc(sizeof(char) * strlen(base) + strlen(name) + 2);
+        strcpy(tmp, base);
+        if (name[0] != '/')
+            strcat(tmp, "/");
+        strcat(tmp, name);
+        ret = adjust_for_leakage(tmp);
+        free(tmp);
+    }
+    return ret;
 }

Re: [Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Kirill A. Shutemov]

[-- Attachment #1.1: Type: text/plain, Size: 653 bytes --]

On [Tue, 22.05.2007 02:22], Lauri Leukkunen wrote:
> Attached patch fixes the linux-user path mangling code for use with
> real target root filesystems that have nasty symlinks and lots of
> files. The old code is terribly slow and can easily end up going
> through the entire host system /usr hierarchy in a recursive loop.
> 
> Compared to the previous version of this patch, fixes an issue with
> attempting to free() a pointer returned by GNU basename().

My patch to solve same problems attached

-- 
Regards,  Kirill A. Shutemov
 + Belarus, Minsk
 + Velesys LLC, http://www.velesys.com/
 + ALT Linux Team, http://www.altlinux.com/

[-- Attachment #1.2: qemu-0.9.0-alt-path.patch --]
[-- Type: text/plain, Size: 5643 bytes --]

--- qemu/linux-user/path.c
+++ qemu/linux-user/path.c
@@ -1,147 +1,81 @@
 /* Code to mangle pathnames into those matching a given prefix.
    eg. open("/lib/foo.so") => open("/usr/gnemul/i386-linux/lib/foo.so");
-
-   The assumption is that this area does not change.
 */
 #include <sys/types.h>
-#include <dirent.h>
+#include <sys/stat.h>
 #include <unistd.h>
-#include <stdlib.h>
 #include <string.h>
-#include <errno.h>
 #include <stdio.h>
 #include "qemu.h"
 
-struct pathelem
-{
-    /* Name of this, eg. lib */
-    char *name;
-    /* Full path name, eg. /usr/gnemul/x86-linux/lib. */
-    char *pathname;
-    struct pathelem *parent;
-    /* Children */
-    unsigned int num_entries;
-    struct pathelem *entries[0];
+struct path_list_head {
+	    struct path_list_head *next;
+		char* path;
 };
 
-static struct pathelem *base;
-
-/* First N chars of S1 match S2, and S2 is N chars long. */
-static int strneq(const char *s1, unsigned int n, const char *s2)
-{
-    unsigned int i;
-
-    for (i = 0; i < n; i++)
-	if (s1[i] != s2[i])
-	    return 0;
-    return s2[i] == 0;
-}
-
-static struct pathelem *add_entry(struct pathelem *root, const char *name);
-
-static struct pathelem *new_entry(const char *root,
-				  struct pathelem *parent,
-				  const char *name)
-{
-    struct pathelem *new = malloc(sizeof(*new));
-    new->name = strdup(name);
-    asprintf(&new->pathname, "%s/%s", root, name);
-    new->num_entries = 0;
-    return new;
-}
-
-#define streq(a,b) (strcmp((a), (b)) == 0)
-
-static struct pathelem *add_dir_maybe(struct pathelem *path)
-{
-    DIR *dir;
-
-    if ((dir = opendir(path->pathname)) != NULL) {
-	struct dirent *dirent;
-
-	while ((dirent = readdir(dir)) != NULL) {
-	    if (!streq(dirent->d_name,".") && !streq(dirent->d_name,"..")){
-		path = add_entry(path, dirent->d_name);
-	    }
-	}
-        closedir(dir);
-    }
-    return path;
-}
-
-static struct pathelem *add_entry(struct pathelem *root, const char *name)
-{
-    root->num_entries++;
-
-    root = realloc(root, sizeof(*root)
-		   + sizeof(root->entries[0])*root->num_entries);
-
-    root->entries[root->num_entries-1] = new_entry(root->pathname, root, name);
-    root->entries[root->num_entries-1]
-	= add_dir_maybe(root->entries[root->num_entries-1]);
-    return root;
-}
-
-/* This needs to be done after tree is stabalized (ie. no more reallocs!). */
-static void set_parents(struct pathelem *child, struct pathelem *parent)
-{
-    unsigned int i;
-
-    child->parent = parent;
-    for (i = 0; i < child->num_entries; i++)
-	set_parents(child->entries[i], child);
-}
+static struct path_list_head* list_head;
 
 void init_paths(const char *prefix)
 {
     if (prefix[0] != '/' ||
-        prefix[0] == '\0' ||
-        !strcmp(prefix, "/"))
+            prefix[0] == '\0' ||
+            !strcmp(prefix, "/"))
         return;
 
-    base = new_entry("", NULL, prefix+1);
-    base = add_dir_maybe(base);
-    if (base->num_entries == 0) {
-        free (base);
-        base = NULL;
-    } else {
-        set_parents(base, base);
-    }
-}
+	list_head = malloc(sizeof(struct path_list_head));
 
-/* FIXME: Doesn't handle DIR/.. where DIR is not in emulated dir. */
-static const char *
-follow_path(const struct pathelem *cursor, const char *name)
-{
-    unsigned int i, namelen;
-
-    name += strspn(name, "/");
-    namelen = strcspn(name, "/");
-
-    if (namelen == 0)
-	return cursor->pathname;
-
-    if (strneq(name, namelen, ".."))
-	return follow_path(cursor->parent, name + namelen);
-
-    if (strneq(name, namelen, "."))
-	return follow_path(cursor, name + namelen);
-
-    for (i = 0; i < cursor->num_entries; i++)
-	if (strneq(name, namelen, cursor->entries[i]->name))
-	    return follow_path(cursor->entries[i], name + namelen);
-
-    /* Not found */
-    return NULL;
+	/* first element of list is prefix */
+	list_head->path = strdup(prefix);
+	list_head->next = NULL;
 }
 
 /* Look for path in emulation dir, otherwise return name. */
 const char *path(const char *name)
 {
+	struct path_list_head *list = list_head;
+	int path_length = strlen(list_head->path) + strlen(name) + 1;
+	char *newname = malloc(path_length);
+	struct stat buf;
+	const char * result = name;
+
     /* Only do absolute paths: quick and dirty, but should mostly be OK.
        Could do relative by tracking cwd. */
-    if (!base || name[0] != '/')
-	return name;
-
-    return follow_path(base, name) ?: name;
+    if (!list_head || result[0] != '/')
+		goto exit;
+
+	strncpy(newname, list_head->path, path_length);
+	strncat(newname, name, path_length);
+
+	/* look for place where path should be present */
+	while ( list->next && (strcmp(list->next->path, newname) < 0) )
+		list = list->next;
+
+	/* if there is no path in list */
+	if ( !list->next || strcmp(list->next->path, newname) )	{
+		/* add element to list if path exist in emulation dir */
+		if ( !stat(newname, &buf) )
+		{
+			struct path_list_head *new;
+
+			new = malloc(sizeof(struct path_list_head));
+			new->path = strdup(newname);
+			new->next = list->next;
+			list->next = new;
+			result = new->path;
+		}
+
+	} else if ( stat(list->next->path, &buf) ) {
+		/* remove element from list if path doesn't exist in emulation dir */
+		struct path_list_head* tmp;
+
+		tmp = list->next;
+		list->next = tmp->next;
+		free(tmp->path);
+		free(tmp);
+	} else
+		result = list->next->path;
+
+exit:
+	free(newname);
+	return result;
 }

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Lauri Leukkunen]

On 5/22/07, Kirill A. Shutemov <k.shutemov@velesys.com> wrote:
> On [Tue, 22.05.2007 02:22], Lauri Leukkunen wrote:
> > Attached patch fixes the linux-user path mangling code for use with
> > real target root filesystems that have nasty symlinks and lots of
> > files. The old code is terribly slow and can easily end up going
> > through the entire host system /usr hierarchy in a recursive loop.
> >
> > Compared to the previous version of this patch, fixes an issue with
> > attempting to free() a pointer returned by GNU basename().
>
> My patch to solve same problems attached

The added complexity of my version comes from preventing leaking out
of the "chroot" through symlinks or "../.." elements. If we have

$HOME/buildroot/usr/lib/libfoo.so.1 -> /usr/lib/libfoo.so.1.2 ->
/usr/lib/libfoo.so.1.2.3

and if the buildroot and host system have different versions of the
library, realpath can't be used. It gets a little messy, I agree. I
had to do similar logic in scratchbox2 to maintain the fake chroot.

regards, Lauri

Re: [Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Thiemo Seufer]

Lauri Leukkunen wrote:
> Attached patch fixes the linux-user path mangling code for use with
> real target root filesystems that have nasty symlinks and lots of
> files. The old code is terribly slow and can easily end up going
> through the entire host system /usr hierarchy in a recursive loop.
> 
> Compared to the previous version of this patch, fixes an issue with
> attempting to free() a pointer returned by GNU basename().

I gave it a try, and found:
  - It loses the path caching (which should be done incrementally to
    avoid the slowness you observe)
  - It misses to do error handling on malloc() returns
  - It is broken, an emulated "/bin/ls /.." shows it ascends above
    the root.


Thiemo

Re: [Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Lauri Leukkunen]

On 17/06/07 17:30 +0100, Thiemo Seufer wrote:
> Lauri Leukkunen wrote:
> > Attached patch fixes the linux-user path mangling code for use with
> > real target root filesystems that have nasty symlinks and lots of
> > files. The old code is terribly slow and can easily end up going
> > through the entire host system /usr hierarchy in a recursive loop.
> > 
> > Compared to the previous version of this patch, fixes an issue with
> > attempting to free() a pointer returned by GNU basename().
> 
> I gave it a try, and found:
>   - It loses the path caching (which should be done incrementally to
>     avoid the slowness you observe)

Current path mangling is not just slow, it gets stuck in a loop for 
15 minutes on my box and eats all my RAM until it exhausts all virtual memory:

3976 lleukkun  18   0 2641m 1.5g  188 R   68 77.4   1:26.36 qemu-arm

So I don't know if losing a bit of caching is that bad in comparison.
I've implemented a kinda similar path mangling system for scratchbox2, there
I'm caching the translations in a cache dir as symlinks, cuts down the
mangling overhead quite a bit, but on the other hand sb2 needs to do a lot
more work to determine how to mangle the path. Not sure it's worth the
trouble for qemu.

It seems on a current debian/testing it no longer works at all, it used to
hog all memory and then (maybe after getting a NULL from malloc()?)
continued, now it just eats all swap and keeps going as long as the kernel
permits. If you want to see the effect get a maemo rootfs from here:
http://repository.maemo.org/stable/3.1/armel/maemo-sdk-rootstrap_3.1_armel.tgz
and try giving the extracted dir to qemu-arm -L /path/to/the/rootfs

It gets tripped up by the /usr/X11R6/bin/X11 -> . symlink, don't ask me why
such a link is needed ;)

>   - It misses to do error handling on malloc() returns
>   - It is broken, an emulated "/bin/ls /.." shows it ascends above
>     the root.

I'll try to provide an updated patch with these addressed tomorrow.

/lauri

Re: [Qemu-devel] [PATCH][UPDATED] Fix path mangling in linux-user/path.c

[Lauri Leukkunen]

[-- Attachment #1: Type: text/plain, Size: 474 bytes --]

On 18/06/07 09:02 +0300, Lauri Leukkunen wrote:
> On 17/06/07 17:30 +0100, Thiemo Seufer wrote:
> > Lauri Leukkunen wrote:
> >   - It misses to do error handling on malloc() returns
> >   - It is broken, an emulated "/bin/ls /.." shows it ascends above
> >     the root.
> 
> I'll try to provide an updated patch with these addressed tomorrow.

Attached is the latest version of this patch. I've tried to test it with
various interesting paths and it works for me.

/lauri


[-- Attachment #2: qemu-linux-user-path3.diff --]
[-- Type: text/x-diff, Size: 9791 bytes --]

Index: linux-user/path.c
===================================================================
RCS file: /sources/qemu/qemu/linux-user/path.c,v
retrieving revision 1.3
diff -u -r1.3 path.c
--- linux-user/path.c	17 Jun 2007 15:32:30 -0000	1.3
+++ linux-user/path.c	18 Jun 2007 20:30:27 -0000
@@ -3,157 +3,249 @@
 
    The assumption is that this area does not change.
 */
+
 #include <sys/types.h>
 #include <dirent.h>
 #include <unistd.h>
 #include <stdlib.h>
+
+#ifdef _GNU_SOURCE
+#undef _GNU_SOURCE
 #include <string.h>
+#include <libgen.h>
+#define _GNU_SOURCE
+#else
+#include <string.h>
+#include <libgen.h>
+#endif
+
 #include <errno.h>
 #include <stdio.h>
 #include "qemu.h"
 
-struct pathelem
-{
-    /* Name of this, eg. lib */
-    char *name;
-    /* Full path name, eg. /usr/gnemul/x86-linux/lib. */
-    char *pathname;
-    struct pathelem *parent;
-    /* Children */
-    unsigned int num_entries;
-    struct pathelem *entries[0];
-};
-
-static struct pathelem *base;
+char *base = NULL;
 
-/* First N chars of S1 match S2, and S2 is N chars long. */
-static int strneq(const char *s1, unsigned int n, const char *s2)
-{
-    unsigned int i;
-
-    for (i = 0; i < n; i++)
-	if (s1[i] != s2[i])
-	    return 0;
-    return s2[i] == 0;
-}
-
-static struct pathelem *add_entry(struct pathelem *root, const char *name);
-
-static struct pathelem *new_entry(const char *root,
-				  struct pathelem *parent,
-				  const char *name)
-{
-    struct pathelem *new = malloc(sizeof(*new));
-    new->name = strdup(name);
-    asprintf(&new->pathname, "%s/%s", root, name);
-    new->num_entries = 0;
-    return new;
-}
-
-#define streq(a,b) (strcmp((a), (b)) == 0)
+struct path_entry {
+    struct path_entry *prev;
+    struct path_entry *next;
+    char name[PATH_MAX];
+};
 
-static struct pathelem *add_dir_maybe(struct pathelem *path)
+char *decolonize_path(const char *path)
 {
-    DIR *dir;
+    char *cpath, *index, *start;
+    char cwd[PATH_MAX];
+    struct path_entry list;
+    struct path_entry *work;
+    struct path_entry *new;
+    char *buf = NULL;
 
-    if ((dir = opendir(path->pathname)) != NULL) {
-	struct dirent *dirent;
-
-	while ((dirent = readdir(dir)) != NULL) {
-	    if (!streq(dirent->d_name,".") && !streq(dirent->d_name,"..")){
-		path = add_entry(path, dirent->d_name);
-	    }
-	}
-        closedir(dir);
+    if (!path) {
+        return NULL;
     }
-    return path;
-}
 
-static struct pathelem *add_entry(struct pathelem *root, const char *name)
-{
-    root->num_entries++;
+    buf = malloc((PATH_MAX + 1) * sizeof(char));
+    memset(buf, '\0', PATH_MAX + 1);
 
-    root = realloc(root, sizeof(*root)
-		   + sizeof(root->entries[0])*root->num_entries);
+    list.next = NULL;
+    list.prev = NULL;
+    work = &list;
+
+    if (path[0] != '/') {
+        /* not an absolute path */
+        memset(cwd, '\0', PATH_MAX);
+        if (getcwd(cwd, PATH_MAX) < 0) {
+            perror("error getting current work dir\n");
+            return NULL;
+        }
+        unsigned int l = (strlen(cwd) + 1 + strlen(path) + 1);
+        cpath = malloc((strlen(cwd) + 1
+                        + strlen(path) + 1) * sizeof(char));
+        if (!cpath)
+            abort();
 
-    root->entries[root->num_entries-1] = new_entry(root->pathname, root, name);
-    root->entries[root->num_entries-1]
-	= add_dir_maybe(root->entries[root->num_entries-1]);
-    return root;
-}
+        memset(cpath, '\0', l);
+        strcpy(cpath, cwd);
+        strcat(cpath, "/");
+        strcat(cpath, path);
+    } else {
+        if (!(cpath = strdup(path)))
+            abort();
+    }
 
-/* This needs to be done after tree is stabalized (ie. no more reallocs!). */
-static void set_parents(struct pathelem *child, struct pathelem *parent)
-{
-    unsigned int i;
+    start = cpath + 1;          /* ignore leading '/' */
+    while (1) {
+        unsigned int last = 0;
+        
+        index = strstr(start, "/");
+        if (!index) {
+            last = 1;
+        } else {
+            *index = '\0';
+        }
+
+        if (index == start) {
+            goto proceed;       /* skip over empty strings 
+                                   resulting from // */
+        }
+
+        if (strcmp(start, "..") == 0) {
+            /* travel up one */
+            if (!work->prev)
+                goto proceed;
+            work = work->prev;
+            free(work->next);
+            work->next = NULL;
+        } else if (strcmp(start, ".") == 0) {
+            /* ignore */
+            goto proceed;
+        } else {
+            /* add an entry to our path_entry list */
+            if (!(new = malloc(sizeof(struct path_entry))))
+                abort();
+            memset(new->name, '\0', PATH_MAX);
+            new->prev = work;
+            work->next = new;
+            new->next = NULL;
+            strcpy(new->name, start);
+            work = new;
+        }
+
+      proceed:
+        if (last)
+            break;
+        *index = '/';
+        start = index + 1;
+    }
 
-    child->parent = parent;
-    for (i = 0; i < child->num_entries; i++)
-	set_parents(child->entries[i], child);
+    work = list.next;
+    while (work) {
+        struct path_entry *tmp;
+        strcat(buf, "/");
+        strcat(buf, work->name);
+        tmp = work;
+        work = work->next;
+        free(tmp);
+    }
+    return buf;
 }
 
-/* FIXME: Doesn't handle DIR/.. where DIR is not in emulated dir. */
-static const char *
-follow_path(const struct pathelem *cursor, const char *name)
-{
-    unsigned int i, namelen;
-
-    name += strspn(name, "/");
-    namelen = strcspn(name, "/");
-
-    if (namelen == 0)
-	return cursor->pathname;
-
-    if (strneq(name, namelen, ".."))
-	return follow_path(cursor->parent, name + namelen);
-
-    if (strneq(name, namelen, "."))
-	return follow_path(cursor, name + namelen);
-
-    for (i = 0; i < cursor->num_entries; i++)
-	if (strneq(name, namelen, cursor->entries[i]->name))
-	    return follow_path(cursor->entries[i], name + namelen);
-
-    /* Not found */
-    return NULL;
-}
 
 void init_paths(const char *prefix)
 {
     char pref_buf[PATH_MAX];
-
     if (prefix[0] == '\0' ||
         !strcmp(prefix, "/"))
         return;
+    
+    if (!realpath(prefix, pref_buf))
+        abort();
+
+    if (!(base = strdup(pref_buf)))
+        abort();
+}
+
+char *adjust_for_leakage(const char *path)
+{
+    char tmp[PATH_MAX + 1];
+    char tmp2[PATH_MAX + 1];
+    char *buf;
+    char *bname = NULL, *dname = NULL;
+    char *bpath = NULL, *dpath = NULL;
+    int i;
+
+    if (!path)
+        return NULL;
+
+    memset(tmp, '\0', PATH_MAX + 1);
+    memset(tmp2, '\0', PATH_MAX + 1);
+    if ((i = readlink(path, tmp, PATH_MAX) < 0)) {
+        /* not a symlink */
+        if (!(buf = strdup(path)))
+            abort();
+        return buf;
+    }
+
+    if (!(bpath = strdup(path)))
+        abort();
+    bname = basename(bpath); /* free bpath, not bname */
+    if (!(dpath = strdup(path)))
+        abort();
+    dname = dirname(dpath); /* free dpath, not dname */
+
+    /* check if the symlink refers to itself */
+    if (strcmp(tmp, bname) == 0) {
+        /* symlink refers to itself */
+        if (!(buf = strdup(path)))
+            abort();
+        free(dpath);
+        free(bpath);
+        return buf;
+    }
+
+    /* make tmp absolute if it's not */
+    if (tmp[0] != '/') {
+        strcpy(tmp2, dname);
+        strcat(tmp2, "/");
+        strcat(tmp2, tmp);
+    }
 
-    if (prefix[0] != '/') {
-        char *cwd = get_current_dir_name();
-	if (!cwd)
-            abort();
-	strcpy(pref_buf, cwd);
-        strcat(pref_buf, "/");
-        strcat(pref_buf, prefix);
-        free(cwd);
-    } else
-        strcpy(pref_buf,prefix + 1);
-
-    base = new_entry("", NULL, pref_buf);
-    base = add_dir_maybe(base);
-    if (base->num_entries == 0) {
-        free (base);
-        base = NULL;
+    /* remove "." and ".." entries from tmp */
+    buf = decolonize_path(tmp2);
+    strcpy(tmp2, buf);
+
+    free(buf);
+    free(bpath);
+    free(dpath);
+
+    if (strncmp(tmp2, base, strlen(base)) != 0) {
+        /* tried to leak out, fix it */
+        strcpy(tmp, base);
+        strcpy(tmp, "/");
+        strcpy(tmp, tmp2);
+        return adjust_for_leakage(tmp);
     } else {
-        set_parents(base, base);
+        return adjust_for_leakage(tmp2);
     }
 }
 
-/* Look for path in emulation dir, otherwise return name. */
+/* mangle name to reside always in the emulation dir */
 const char *path(const char *name)
 {
-    /* Only do absolute paths: quick and dirty, but should mostly be OK.
-       Could do relative by tracking cwd. */
-    if (!base || name[0] != '/')
-	return name;
+    char *tmp, *ret, *clean_name;
+    char cmp1[PATH_MAX], cmp2[PATH_MAX];
 
-    return follow_path(base, name) ?: name;
+    if (!base) {
+        if (!(tmp = strdup(name)))
+            abort();
+        return tmp;
+    }
+
+    clean_name = decolonize_path(name);
+    
+    memset(cmp1, '\0', PATH_MAX);
+    memset(cmp2, '\0', PATH_MAX);
+
+    strcpy(cmp1, clean_name);
+    cmp1[strlen(clean_name)] = '/';
+    strcpy(cmp2, base);
+    cmp2[strlen(base)] = '/';
+
+    if (strncmp(cmp1, cmp2, strlen(cmp2)) == 0) {
+        /* name is within emulation dir */
+        ret = adjust_for_leakage(clean_name);
+    } else {
+        /* name is elsewhere, use base + "/" + name */
+        if (!(tmp = malloc(sizeof(char) * strlen(base) 
+                        + strlen(clean_name) + 2)))
+            abort();
+        
+        strcpy(tmp, base);
+        if (clean_name[0] != '/')
+            strcat(tmp, "/");
+        strcat(tmp, clean_name);
+        ret = adjust_for_leakage(tmp);
+        free(tmp);
+    }
+    return ret;
 }