shithub: unionfs

Info  •  Files  •  Log  •  Branches

Implement deduplication of directory entries

--- /dev/null

+++ b/dirlist.c

@@ -1,0 +1,78 @@

+#include "unionfs.h"

+

+static uvlong

+hash(char *s)

+{

+	uvlong h;

+	

+	h = 14695981039346656037ULL;

+	while(*s++){

+		h ^= *s;

+		h *= 1099511628211ULL;

+	}

+	return h;

+}

+

+static int

+seen(Dirlist *dl, char *name)

+{

+	usize probe, omseen, i;

+	char *n, **oseen;

+

+	probe = hash(name) % dl->mseen;

+	while((n = dl->seen[probe]) != nil){

+		if(strcmp(n, name) == 0)

+			return 1;

+		probe = (probe + 1) % dl->mseen;

+	}

+	dl->seen[probe] = name;

+	dl->nseen++;

+	if(dl->nseen > dl->mseen / 2){

+		oseen = dl->seen;

+		omseen = dl->mseen;

+		dl->mseen *= 2;

+		dl->nseen = 0;

+		dl->seen = emalloc(dl->mseen * sizeof(char*));

+		for(i = 0; i < omseen; i++)

+			if(oseen[i] != nil)

+				seen(dl, oseen[i]);

+		free(oseen);

+	}

+	return 0;

+}

+

+void

+dirlistfree(Dirlist *dl)

+{

+	if(dl == nil)

+		return;

+	free(dl->seen);

+	free(dl->dirs);

+	free(dl->all);

+	free(dl);

+}

+

+Dirlist*

+dirlist(int fd)

+{

+	long i, j;

+	Dir *d;

+	Dirlist *dl;

+	

+	dl = emalloc(sizeof(Dirlist));

+	if((dl->nall = dirreadall(fd, &dl->all)) == -1){

+		free(dl);

+		return nil;

+	}

+	dl->dirs = emalloc((dl->nall + 1) * sizeof(Dir*));

+	dl->mseen = dl->nall;

+	dl->seen = emalloc(dl->mseen * sizeof(char*));

+	for(j = 0, i = 0; d = &dl->all[i], i < dl->nall; i++){

+		if(seen(dl, d->name))

+			continue;

+		dl->dirs[j++] = d;

+	}

+	dl->dirs[j] = nil;

+	dl->ndirs = j;

+	return dl;

+}

--- a/mkfile

+++ b/mkfile

@@ -9,6 +9,7 @@

 OFILES=\

 	util.$O\

 	qmap.$O\

+	dirlist.$O\

 	unionfs.$O

 </sys/src/cmd/mkone

--- a/qmap.c

+++ b/qmap.c

@@ -49,10 +49,7 @@

  * almost the entire space just for paths.

  */

-#include <u.h>

-#include <libc.h>

-

-void *emalloc(ulong);

+#include "unionfs.h"

 #define mask(v) ((1ull << v) - 1)

--- a/unionfs.c

+++ b/unionfs.c

@@ -1,9 +1,3 @@

-#include <u.h>

-#include <libc.h>

-#include <String.h>

-#include <fcall.h>

-#include <thread.h>

-#include <9p.h>

 #include "unionfs.h"

 Srv thefs;

@@ -61,7 +55,7 @@

 	if(f->path) s_free(f->path);

 	if(f->realpath) s_free(f->realpath);

 	if(f->fd != -1) close(f->fd);

-	if(f->dirs) free(f->dirs);

+	if(f->dl) dirlistfree(f->dl);

 	if(f->mtpt) mtptfree(f->mtpt);

 	free(f);

 }

@@ -242,22 +236,14 @@

 int

 dirgen(int i, Dir *d, void *aux)

 {

-	FILE *f = aux;

+	Dirlist *dl = aux;

+	Dir *dd;

-	if(i == 0){

-		if(f->dirs){

-			free(f->dirs);

-			f->dirs = nil;

-			f->ndirs = 0;

-		}

-		f->ndirs = dirreadall(f->fd, &f->dirs);

-		if(f->ndirs == -1)

-			sysfatal("dirreadall: %r");

-	}

-	if(f->ndirs == i)

+	if(dl->ndirs == i)

 		return -1;

-	dircopy(d, &f->dirs[i]);

-	d->qid = qencode(d);

+	dd = dl->dirs[i];

+	dircopy(d, dd);

+	d->qid = qencode(dd);

 	return 0;

 }

@@ -274,16 +260,25 @@

 	srvrelease(&thefs);

 	if(f->mode&DMDIR){

-		dirread9p(r, dirgen, f);

-	}else{

-		if((n = pread(f->fd, R->data, T->count, T->offset)) < 0){

-			responderror(r);

-			goto done;

+		if(T->offset == 0){

+			if(seek(f->fd, 0, 0) == -1)

+				goto error;

+			if(f->dl != nil)

+				dirlistfree(f->dl);

+			if((f->dl = dirlist(f->fd)) == nil)

+				goto error;

 		}

+		dirread9p(r, dirgen, f->dl);

+	}else{

+		if((n = pread(f->fd, R->data, T->count, T->offset)) < 0)

+			goto error;

 		r->ofcall.count = n;

 	}

 	respond(r, nil);

-done:

+	srvacquire(&thefs);

+	return;

+error:

+	responderror(r);

 	srvacquire(&thefs);

 }

--- a/unionfs.h

+++ b/unionfs.h

@@ -1,6 +1,14 @@

+#include <u.h>

+#include <libc.h>

+#include <String.h>

+#include <fcall.h>

+#include <thread.h>

+#include <9p.h>

+

 typedef struct Branch Branch;

 typedef struct FILE FILE;

 typedef struct Mtpt Mtpt;

+typedef struct Dirlist Dirlist;

 struct Branch {

 	char *root;

@@ -14,8 +22,7 @@

 	int fd;

 	Mtpt *mtpt;

-	Dir *dirs;

-	long ndirs;

+	Dirlist *dl;

 };

 struct Mtpt {

@@ -23,8 +30,20 @@

 	Mtpt *next;

 };

+struct Dirlist {

+	Dir *all;

+	long nall;

+	Dir **dirs;

+	long ndirs;

+	

+	/* implementation-specific */

+	char **seen;

+	usize nseen, mseen;

+};

+

 void usage(void);

 Qid qencode(Dir*);

-char *mkpath(char*, ...);

+Dirlist *dirlist(int);

+void dirlistfree(Dirlist*);

 void *emalloc(ulong);

 char *estrdup(char*);