shithub: unionfs

Download patch

ref: 53c5bcc460fdce3442789e5c55d316b3720cf691
parent: afe34cba9ac5b1721293ff06a5b36deb8d1a37b3
author: kvik <kvik@a-b.xyz>
date: Mon May 31 14:45:28 EDT 2021

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*);