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