shithub: gefs

Download patch

ref: 3f842a00016a70d021ddf27a901d564a8e97ab61
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Dec 28 20:07:18 EST 2020 

initial commit


--- /dev/null
+++ b/blk.c
@@ -1,0 +1,52 @@
+#include <u.h>
+#include <libc.h>
+
+#include "dat.h"
+#include "fns.h"
+
+Blk*
+newblk(int t)
+{
+	Blk *b;
+
+	b = emalloc(sizeof(Blk));
+	b->flag |= Bdirty;
+	b->type = t;
+	return b;	
+}
+
+Blk*
+getblk(uvlong bp, uvlong bh)
+{
+	Blk *b;
+
+	b = (Blk*)bp;
+	if(blkhash(b) != bh){
+		werrstr("corrupt block %llx\n", bp);
+		fprint(2, "corrupt block %llx\n", bp);
+//		abort();
+	}
+	return b;
+}
+
+void
+freeblk(Blk *b)
+{
+	b->refs--;
+	if(b->refs == 0)
+		free(b);
+}
+
+uvlong
+blkhash(Blk *b)
+{
+	return siphash(b->data, Blksz);
+}
+
+int
+putblk(Blk *b)
+{
+	USED(b);
+	/* TODO: unref. */
+	return 0;
+}
--- /dev/null
+++ b/check.c
@@ -1,0 +1,142 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include "dat.h"
+#include "fns.h"
+
+char	spc[128];
+int	debug;
+
+static int
+invalidblk(Blk *b, int h, Kvp *lo, Kvp *hi)
+{
+	Kvp x, y;
+	int i, r;
+	Blk *c;
+	int fail;
+
+	fail = 0;
+	if(b->type == Leaf){
+		if(h != fs->height){
+			fprint(2, "unbalanced leaf\n");
+			fail++;
+		}
+		if(h != 1 && b->nent < 2){
+			fprint(2, "underfilled leaf\n");
+			fail++;
+		}
+	}
+	if(b->type == Pivot && b->nent < 2){
+		fprint(2, "underfilled  pivot\n");
+		fail++;
+	}
+	getval(b, 0, &x);
+	if(lo && keycmp(lo, &x) != 0)
+		fprint(2, "out of range keys %P != %P\n", lo, &x);
+	for(i = 1; i < b->nent; i++){
+		getval(b, i, &y);
+		if(hi && keycmp(&y, hi) >= 0){
+			fprint(2, "out of range keys %P >= %P\n", &y, hi);
+			fail++;
+		}
+		if(b->type == Pivot){
+			c = getblk(x.bp, x.bh);
+			if(invalidblk(c, h + 1, &x, &y))
+				fail++;
+		}
+		r = keycmp(&x, &y);
+		switch(r){
+		case -1:
+			break;
+		case 0:
+			fprint(2, "duplicate keys %P, %P\n", &x, &y);
+			fail++;
+			break;
+		case 1:
+			fprint(2, "misordered keys %P, %P\n", &x, &y);
+			fail++;
+			break;
+		}
+		x = y;
+	}
+	return fail;
+}
+	
+
+/* TODO: this will grow into fsck. */
+int
+checkfs(void)
+{
+	return invalidblk(fs->root, 1, nil, nil) == 0;
+}
+
+static void
+rshowblk(Blk *b, int indent)
+{
+	Blk *c;
+	int i;
+	Kvp kv;
+	Msg m;
+
+	if(indent > sizeof(spc)/4)
+		indent = sizeof(spc)/4;
+	if(b == nil){
+		print("NIL\n");
+		return;
+	}
+	if(b->type == Pivot){
+		for(i = 0; i < b->nmsg; i++){
+			getmsg(b, i, &m);
+			print("%.*s|%M\n", 4*indent, spc, &m);
+		}
+	}
+	for(i = 0; i < b->nent; i++){
+		getval(b, i, &kv);
+		print("%.*s|%P\n", 4*indent, spc, &kv);
+		if(b->type == Pivot){
+			if((c = getblk(kv.bp, kv.bh)) == nil)
+				sysfatal("falied load: %r");
+			rshowblk(c, indent + 1);
+		}
+	}
+}
+
+
+void
+initshow(void)
+{
+	int i;
+
+	memset(spc, ' ', sizeof(spc));
+	for(i = 0; i < sizeof(spc); i += 4)
+		spc[i] = '|';
+}
+
+void
+showblk(Blk *b, char *m)
+{
+	if(m != nil)
+		print("=== %s\n", m);
+	rshowblk(b, 0);
+}
+
+void
+showfs(char *m)
+{
+	if(m != nil)
+		print("=== %s\n", m);
+	rshowblk(fs->root, 0);
+}
+
+
+void
+showpath(Path *p, int np)
+{
+	int i;
+
+	for(i = 0; i < np; i++){
+		print("==> b=%p, n=%p, idx=%d\n", p[i].b, p[i].n, p[i].idx);
+		print("\tclear=(%d, %d):%d\n", p[i].lo, p[i].hi, p[i].sz);
+		print("\tl=%p, r=%p, n=%p, split=%d\n", p[i].l, p[i].r, p[i].n, p[i].split);
+	}
+}
--- /dev/null
+++ b/dat.h
@@ -1,0 +1,139 @@
+typedef struct Blk	Blk;
+typedef struct Gefs	Gefs;
+typedef struct Msg	Msg;
+typedef struct Key	Key;
+typedef struct Val	Val;
+typedef struct Kvp	Kvp;
+typedef struct Path	Path;
+
+enum {
+	// buffer for the whole block
+	Blksz	= 256,
+	// will store what type of block
+	Hdrsz	= 16,
+	Blkspc	= Blksz - Hdrsz,
+	// space for message buffer
+	Bufspc  = Blkspc / 2,
+	// space for pivot keys and offsets
+	Pivspc	= Blkspc - Bufspc,
+	Leafspc = Blkspc,
+	Keymax	= 16,
+	Inlmax	= 64,
+	Ptrsz	= 16,
+	Kvmax	= Keymax + Inlmax,	/* Key and value */
+	Kpmax	= Keymax + Ptrsz,	/* Key and pointer */
+	Msgmax  = 1 + (Kvmax > Kpmax ? Kvmax : Kpmax)
+};
+
+enum {
+	Bdirty = 1 << 0,
+};
+
+#define Efs	"i will not buy this fs, it is scratched"
+#define Eexist	"does not exist"
+#define Ebotch	"protocol botch"
+#define Emode	"unknown mode"
+#define Efull	"file system full"
+#define Eauth	"authentication failed"
+#define Elength	"name too long"
+#define Eperm	"permission denied"
+
+/*
+ * The type of block. Pivot nodes are internal to the tree,
+ * while leaves inhabit the edges. Pivots are split in half,
+ * containing a buffer for the data, and keys to direct the
+ * searches. Their buffers contain messages en-route to the
+ * leaves.
+ *
+ * Leaves contain the key, and some chunk of data as the
+ * value.
+ */
+enum {
+	Pivot,
+	Leaf,
+};
+
+enum {
+	Vinl,	/* Inline value */
+	Vref,	/* Block pointer */
+};
+
+enum {
+	Ocreate,
+	Odelete,
+	Owrite,
+	Owstat,
+};
+
+/*
+ * Overall state of the file sytem.
+ * Shadows the superblock contents.
+ */
+struct Gefs {
+	int	blksz;
+	int	bufsz;
+	int	pivsz;
+	int	hdrsz;
+
+	int	height;
+	Blk	*root;
+	
+};
+
+struct Key{
+	char	*k;
+	int	nk;
+};
+
+struct Val {
+	int type;
+	union {
+		/* block pointer */
+		struct {
+			uvlong	bp;
+			uvlong	bh;
+		};
+		/* inline values */
+		struct {
+			short	nv;
+			char	*v;
+		};
+	};
+};
+
+struct Kvp {
+	Key;
+	Val;
+};
+
+struct Msg {
+	char	op;
+	Kvp;
+};
+
+struct Path {
+	/* Flowing down for flush */
+	Blk	*b;	/* insertion */
+	int	idx;	/* insert at */
+	int	lo;	/* key range */
+	int	hi;	/* key range */
+	int	sz;	/* size of range */
+
+	/* Flowing up from flush */
+	Blk	*l;	/* left of split */
+	Blk	*r;	/* right of split */
+	Blk	*n;	/* shadowed node */
+	int	split;	/* did we split? */
+};
+
+struct Blk {
+	char	type;
+	char	flag;
+	short	nent;
+	short	valsz;
+	short   nmsg;
+	short   bufsz;
+	vlong	off;	/* -1 for unallocated */
+	int	refs;	/* TODO: move out */
+	char	data[Blksz];
+};
--- /dev/null
+++ b/fns.h
@@ -1,0 +1,44 @@
+#pragma varargck type "M"	Msg*
+#pragma varargck type "P"	Kvp*
+#pragma varargck type "K"	Key*
+#pragma varargck type "V"	Val*
+#pragma varargck type "B"	Blk*
+
+extern Gefs	*fs;
+extern int	debug;
+
+void	initfs(void);
+
+Blk*	newblk(int type);
+Blk*	shadow(Blk*, Path*, Path*);
+int	putblk(Blk*);
+Blk*	getblk(uvlong bp, uvlong bh);
+void	freeblk(Blk *b);
+uvlong	blkhash(Blk*);
+uvlong	siphash(void*, usize);
+
+int	fsupsert(Msg*);
+char	*fswalk1(Key*, Kvp*);
+
+void*	emalloc(usize);
+void*	erealloc(void*, usize);
+char*	estrdup(char*);
+
+int	keycmp(Key *, Key *);
+
+/* for dumping */
+void	getval(Blk *, int, Kvp *);
+void	getmsg(Blk *, int, Msg *);
+
+void	initshow(void);
+void	showblk(Blk*, char*);
+void	showpath(Path*, int);
+void	showfs(char*);
+int	checkfs(void);
+
+/* scratch */
+void	setmsg(Blk *, int, Msg *);
+void	bufinsert(Blk *, Msg *);
+void victim(Blk *b, Path *p);
+void blkinsert(Blk *b, Kvp *kv);
+
--- /dev/null
+++ b/hash.c
@@ -1,0 +1,99 @@
+/*
+ Copyright (c) 2013  Marek Majkowski <marek@popcount.org>
+
+ 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.
+
+ Original location:
+    https://github.com/majek/csiphash/
+
+ Solution inspired by code from:
+    Samuel Neves (supercop/crypto_auth/siphash24/little)
+    djb (supercop/crypto_auth/siphash24/little2)
+    Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c)
+*/
+#include <u.h>
+#include <libc.h>
+#include <fcall.h>
+
+#define _le64toh(x) \
+	GBIT64((char*)&x)
+
+
+#define ROTATE(x, b) (u64int)( ((x) << (b)) | ( (x) >> (64 - (b))) )
+
+#define HALF_ROUND(a,b,c,d,s,t)			\
+	a += b; c += d;				\
+	b = ROTATE(b, s) ^ a;			\
+	d = ROTATE(d, t) ^ c;			\
+	a = ROTATE(a, 32);
+
+#define DOUBLE_ROUND(v0,v1,v2,v3)		\
+	HALF_ROUND(v0,v1,v2,v3,13,16);		\
+	HALF_ROUND(v2,v1,v0,v3,17,21);		\
+	HALF_ROUND(v0,v1,v2,v3,13,16);		\
+	HALF_ROUND(v2,v1,v0,v3,17,21);
+
+
+u64int
+siphash24(const void *src, unsigned long src_sz, const char key[16]) {
+	const u64int *_key = (u64int *)key;
+	u64int k0 = _le64toh(_key[0]);
+	u64int k1 = _le64toh(_key[1]);
+	u64int b = (u64int)src_sz << 56;
+	const u64int *in = (u64int*)src;
+
+	u64int v0 = k0 ^ 0x736f6d6570736575ULL;
+	u64int v1 = k1 ^ 0x646f72616e646f6dULL;
+	u64int v2 = k0 ^ 0x6c7967656e657261ULL;
+	u64int v3 = k1 ^ 0x7465646279746573ULL;
+
+	while (src_sz >= 8) {
+		u64int mi = _le64toh(*in);
+		in += 1; src_sz -= 8;
+		v3 ^= mi;
+		DOUBLE_ROUND(v0,v1,v2,v3);
+		v0 ^= mi;
+	}
+
+	u64int t = 0; u8int *pt = (u8int *)&t; u8int *m = (u8int *)in;
+	switch (src_sz) {
+	case 7: pt[6] = m[6];
+	case 6: pt[5] = m[5];
+	case 5: pt[4] = m[4];
+	case 4: *((u32int*)&pt[0]) = *((u32int*)&m[0]); break;
+	case 3: pt[2] = m[2];
+	case 2: pt[1] = m[1];
+	case 1: pt[0] = m[0];
+	}
+	b |= _le64toh(t);
+
+	v3 ^= b;
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	v0 ^= b; v2 ^= 0xff;
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	DOUBLE_ROUND(v0,v1,v2,v3);
+	return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+u64int
+siphash(void *src, usize len)
+{
+	char key[16] = "gefsgefsgefsgefs";
+	return siphash24(src, len, key);
+}
--- /dev/null
+++ b/main.c
@@ -1,0 +1,163 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include "dat.h"
+#include "fns.h"
+
+Gefs *fs;
+
+static int
+Bconv(Fmt *fmt)
+{
+	Blk *b;
+
+	b = va_arg(fmt->args, Blk*);
+	if(b == nil)
+		return fmtprint(fmt, "Blk(nil)");
+	return fmtprint(fmt, "Blk(%c)", (b->type == Pivot) ? 'P' : 'L');
+}
+
+static int
+Mconv(Fmt *fmt)
+{
+	char *opname[] = {
+	[Ocreate]	"Ocreate",
+	[Odelete]	"Odelete",
+	[Owrite]	"Owrite",
+	[Owstat]	"Owstat",
+	};
+	Msg *m;
+
+	m = va_arg(fmt->args, Msg*);
+	return fmtprint(fmt, "Msg(%s, %.*s,%.*s)", opname[m->op], m->nk, m->k, m->nv, m->v);
+}
+
+static int
+Pconv(Fmt *fmt)
+{
+	Kvp *kv;
+
+	kv = va_arg(fmt->args, Kvp*);
+	if(kv->type == Vinl)
+		return fmtprint(fmt, "Kvp(%.*s,%.*s)", kv->nk, kv->k, kv->nv, kv->v);
+	else
+		return fmtprint(fmt, "Kvp(%.*s,(%llx,%llx))", kv->nk, kv->k, kv->bp, kv->bh);
+}
+
+static int
+Kconv(Fmt *fmt)
+{
+	Key *k;
+
+	k = va_arg(fmt->args, Key*);
+	return fmtprint(fmt, "Key(%.*s)", k->nk, k->k);
+}
+
+static void
+init(void)
+{
+	initshow();
+	quotefmtinstall();
+	fmtinstall('B', Bconv);
+	fmtinstall('M', Mconv);
+	fmtinstall('P', Pconv);
+	fmtinstall('K', Kconv);
+	fs = emalloc(sizeof(Gefs));
+	fs->root = newblk(Leaf);
+	fs->height = 1;
+}
+
+int
+test(char *path)
+{
+	Biobuf *bfd;
+	char *e, *ln, *f[3];
+	int nf;
+	Msg m;
+	Kvp r;
+	Key k;
+
+	if((bfd = Bopen(path, OREAD)) == nil)
+		sysfatal("open %s: %r", path);
+	while((ln = Brdstr(bfd, '\n', 1)) != nil){
+		memset(f, 0, sizeof(f));
+		nf = tokenize(ln, f, nelem(f));
+		if(nf < 1 || strlen(f[0]) != 1)
+			sysfatal("malformed test file");
+		switch(*f[0]){
+		case '#':
+			break;
+		case 'I':
+			if(nf != 3)
+				sysfatal("malformed insert");
+			m.type = Vinl;
+			m.k = f[1];
+			m.v = f[2];
+			m.op = Ocreate;
+			m.nk = strlen(f[1]);
+			m.nv = strlen(f[2]);
+			print("insert (%s, %s)\n", m.k, m.v);
+			if(fsupsert(&m) == -1){
+				print("failed insert (%s, %s): %r\n", f[1], f[2]);
+				return -1;
+			}
+			break;
+		case 'D':
+			if(nf != 2)
+				sysfatal("malformed delete");
+			m.type = Vinl;
+			m.op = Odelete;
+			m.k = f[1];
+			m.v = nil;
+			m.nk = strlen(f[1]);
+			m.nv = 0;
+			print("delete %s\n", f[1]);
+			if(fsupsert(&m) == -1){
+				print("failed delete (%s): %r\n", f[1]);
+				return -1;
+			}
+			break;
+		case 'G':
+			k.k = f[1];
+			k.nk = strlen(f[1]);
+			e = fswalk1(&k, &r);
+			if(e != nil){
+				print("failed lookup on (%s): %s\n", f[1], e);
+				return -1;
+			}
+			break;
+		case 'S':
+			showfs("fs");
+			print("\n\n");
+			break;
+		case 'C':
+			checkfs();
+			break;
+		case 'V':
+			debug++;
+			break;
+		case 'X':
+			exits(f[1]);
+			break;
+		}
+//		if(!checkfs())
+//			abort();
+		free(ln);
+	}
+	return 0;
+}
+
+void
+main(int argc, char **argv)
+{
+	int i;
+
+	ARGBEGIN{
+	}ARGEND;
+
+	init();
+	for(i = 0; i < argc; i++)
+		if(test(argv[0]) == -1)
+			sysfatal("test %s: %r\n", argv[i]);
+	exits(nil);
+}
--- /dev/null
+++ b/mkfile
@@ -1,0 +1,16 @@
+</$objtype/mkfile
+
+TARG=gefs
+OFILES=\
+	blk.$O\
+	check.$O\
+	hash.$O\
+	main.$O\
+	tree.$O\
+	util.$O\
+
+HFILES=\
+	dat.h\
+	fns.h
+
+</sys/src/cmd/mkone
--- /dev/null
+++ b/tree.c
@@ -1,0 +1,771 @@
+#include <u.h>
+#include <libc.h>
+#include <fcall.h>
+
+#include "dat.h"
+#include "fns.h"
+
+int lookup;
+void
+dprint(char *fmt, ...)
+{
+	va_list ap;
+
+	if(!debug)
+		return;
+	va_start(ap, fmt);
+	vfprint(2, fmt, ap);
+	va_end(ap);
+}
+
+int
+keycmp(Key *a, Key *b)
+{
+	int c, n;
+
+	n = (a->nk < b->nk) ? a->nk : b->nk;
+	if((c = memcmp(a->k, b->k, n)) != 0)
+		return c < 0 ? -1 : 1;
+	if(a->nk < b->nk)
+		return -1;
+	else if(a->nk > b->nk)
+		return 1;
+	else
+		return 0;
+}
+
+int
+msgsz(Msg *m)
+{
+	return 1 + 2 + m->nk + 2 + m->nv;
+}
+
+int
+valsz(Kvp *kv)
+{
+	if(kv->type == Vref)
+		return 2+kv->nk + Ptrsz;
+	else
+		return 2+kv->nk + 2+kv->nv;
+}
+
+void
+getval(Blk *b, int i, Kvp *kv)
+{
+	int o;
+
+	assert(i >= 0 && i < b->nent);
+	o = GBIT16(b->data + 2*i);
+	if(b->type == Pivot){
+		kv->type = Vref;
+		kv->nk = GBIT16(b->data + o);
+		kv->k = b->data + o + 2;
+		kv->bp = GBIT64(kv->k + kv->nk + 0);
+		kv->bh = GBIT64(kv->k + kv->nk + 8);
+	}else{
+		kv->type = Vinl;
+		kv->nk = GBIT16(b->data + o);
+		kv->k = b->data + o + 2;
+		kv->nv = GBIT16(kv->k + kv->nk);
+		kv->v = kv->k + kv->nk + 2;
+	}
+}
+
+static void
+setval(Blk *b, int i, Kvp *kv, int replace)
+{
+	int o, nk, nv, ksz, vsz, spc;
+	char *p;
+
+	assert(i >= 0 && i <= b->nent);
+	spc = (b->type == Leaf) ? Leafspc : Pivspc;
+	p = b->data + 2*i;
+	nk = 2 + kv->nk;
+	nv = (kv->type == Vref) ? Ptrsz : 2 + kv->nv;
+	if (i < 0)
+		i = 0;
+	if(!replace || b->nent == i){
+		memmove(p + 2, p, 2*(b->nent - i));
+		b->nent++;
+		b->valsz += nk + nv;
+		o = spc - b->valsz;
+	}else{
+		/*
+		 * If we can't put it where it was before,
+		 * we need to allocate new space for the
+		 * key-value data. It'll get compacted when
+		 * we split or merge.
+		 */
+		o = GBIT16(b->data + 2*i);
+		ksz = 2 + GBIT16(b->data + o);
+		if(b->type == Leaf)
+			vsz = 2 + GBIT16(b->data + o + ksz);
+		else
+			vsz = 16;
+		if(ksz + vsz < nk + nv){
+			b->valsz += nk + nv;
+			o = spc - b->valsz;
+		}
+	}
+
+	if(2*b->nent + b->valsz > spc)
+		showblk(b, "setval overflow");
+	assert(2*b->nent + b->valsz <= spc);
+	assert(2*b->nent < o);
+	p = b->data + o;
+	if(b->type == Pivot){
+		assert(kv->type == Vref);
+		PBIT16(b->data + 2*i, o);
+		PBIT16(p +  0, kv->nk);
+		memcpy(p +  2, kv->k, kv->nk);
+		PBIT64(p + kv->nk +  2, kv->bp);
+		PBIT64(p + kv->nk + 10, kv->bh);
+	} else {
+		assert(kv->type == Vinl);
+		PBIT16(b->data + 2*i, o);
+		PBIT16(p +  0, kv->nk);
+		memcpy(p +  2, kv->k, kv->nk);
+		PBIT16(p + kv->nk + 2, kv->nv);
+		memcpy(p + kv->nk + 4, kv->v, kv->nv);
+	}
+}
+
+static int
+delval(Blk *b, int i)
+{
+	char *p;
+
+	assert(i >= 0 && i <= b->nent);
+	b->nent--;
+	p = b->data + 2*i;
+	memmove(p, p + 2, 2*(b->nent - i));
+	return 0;
+}
+
+void
+setmsg(Blk *b, int i, Msg *m)
+{
+	char *p;
+	int o;
+
+	assert(b->type == Pivot);
+	assert(i >= 0 && i <= b->nmsg);
+	b->nmsg++;
+	b->bufsz += msgsz(m);
+	assert(2*b->nent + b->bufsz <= Bufspc);
+
+	p = b->data + Pivspc;
+	o = Pivspc - b->bufsz;
+	memmove(p + 2*(i+1), p+2*i, 2*(b->nmsg - i));
+	PBIT16(p + 2*i, o);
+
+	p = b->data + Bufspc + o;
+	*p = m->op;
+	PBIT16(p + 1, m->nk);
+	memcpy(p + 3, m->k, m->nk);
+	PBIT16(p + 3 + m->nk, m->nv);
+	memcpy(p + 5 + m->nk, m->v, m->nv);
+}
+
+void
+getmsg(Blk *b, int i, Msg *m)
+{
+	char *p;
+	int o;
+
+	assert(b->type == Pivot);
+	assert(i >= 0 && i < b->nmsg);
+	o = GBIT16(b->data + Pivspc + 2*i);
+
+	p = b->data + Pivspc + o;
+	m->type = Vinl;
+	m->op = *p;
+	m->nk = GBIT16(p + 1);
+	m->k = p + 3;
+	m->nv = GBIT16(p + 3 + m->nk);
+	m->v = p + 5 + m->nk;
+}
+
+void
+blkinsert(Blk *b, Kvp *kv)
+{
+	int lo, hi, mid, r;
+	Kvp cmp;
+
+	r = -1;
+	lo = 0;
+	hi = b->nent;
+	while(lo < hi){
+		mid = (hi + lo) / 2;
+		getval(b, mid, &cmp);
+		r = keycmp(kv, &cmp);
+		if(r <= 0)
+			hi = mid;
+		else
+			lo = mid + 1;
+	}
+	if(lo < b->nent){
+		getval(b, lo, &cmp);
+		r = keycmp(kv, &cmp);
+	}
+	setval(b, lo, kv, (r == 0));
+}
+
+void
+bufinsert(Blk *b, Msg *m)
+{
+	int lo, hi, mid, r;
+	Msg cmp;
+
+	lo = 0;
+	hi = b->nmsg;
+	while(lo < hi){
+		mid = (hi + lo) / 2;
+		getmsg(b, mid, &cmp);
+		r = keycmp(m, &cmp);
+		if(r <= 0)
+			hi = mid;
+		else
+			lo = mid + 1;
+	}
+	setmsg(b, lo, m);
+}
+
+static int
+bufsearch(Blk *b, Key *k, Msg *m, int *idx)
+{
+	int lo, hi, mid, r;
+
+	lo = 0;
+	hi = b->nmsg - 1;
+	while(lo <= hi){
+		mid = (hi + lo) / 2;
+		getmsg(b, mid, m);
+		r = keycmp(k, m);
+		if(r == 0){
+			*idx = mid;
+			return 0;
+		}
+		if(r < 0)
+			hi = mid - 1;
+		else
+			lo = mid + 1;
+	}
+	return -1;
+}
+
+int
+blkdelete(Blk *b, Kvp *kv)
+{
+	int lo, hi, mid, r;
+	Kvp cmp;
+
+	lo = 0;
+	hi = b->nent - 1;
+	while(lo <= hi){
+		mid = (hi + lo) / 2;
+		getval(b, mid, &cmp);
+		r = keycmp(kv, &cmp);
+		if(r == 0)
+			delval(b, mid);
+		if(r <= 0)
+			hi = mid - 1;
+		else
+			lo = mid + 1;
+	}
+	return -1;
+}
+
+int
+blksearch(Blk *b, Key *k, Kvp *rp, int *idx, int *same)
+{
+	int lo, hi, mid, r;
+	Kvp cmp;
+
+	r = -1;
+	lo = 0;
+	hi = b->nent;
+	while(lo < hi){
+		mid = (hi + lo) / 2;
+		getval(b, mid, &cmp);
+		r = keycmp(k, &cmp);
+		if(r < 0)
+			hi = mid;
+		else
+			lo = mid + 1;
+	}
+	lo--;
+	if(lo >= 0){
+		getval(b, lo, rp);
+		r = keycmp(k, rp);
+	}
+	if(same != nil)
+		*same = (r == 0);
+	if(idx != nil)
+		*idx = lo;
+	return 0;
+}
+int
+filledbuf(Blk *b, int needed)
+{
+	assert(b->type == Pivot);
+	return 2*b->nmsg + b->bufsz > Bufspc - needed;
+}
+
+
+int
+filledleaf(Blk *b, int needed)
+{
+	assert(b->type == Leaf);
+	return 2*b->nent + b->valsz > Leafspc - needed;
+}
+
+int
+filledpiv(Blk *b, int reserve)
+{
+	/* 
+	 * We need to guarantee there's room for one message
+	 * at all times, so that splits along the whole path
+	 * have somewhere to go.
+	 */
+	assert(b->type == Pivot);
+	return 2*b->nent + b->valsz > Pivspc - reserve*Kpmax;
+}
+
+int
+copyup(Blk *n, int i, Path *pp, int *nbytes)
+{
+	Kvp kv;
+
+	
+	if(pp->split){
+		getval(pp->l, 0, &kv);
+		kv.type = Vref;
+		kv.bp = (uintptr)pp->l;
+		kv.bh = blkhash(pp->l);
+		setval(n, i++, &kv, 0);
+		if(nbytes != nil)
+			*nbytes += 2 + valsz(&kv);
+
+		getval(pp->r, 0, &kv);
+		kv.type = Vref;
+		kv.bp = (uintptr)pp->r;
+		kv.bh = blkhash(pp->r);
+		setval(n, i++, &kv, 0);
+		if(nbytes != nil)
+			*nbytes += 2 + valsz(&kv);
+	}else{
+		getval(pp->n, 0, &kv);
+		kv.type = Vref;
+		kv.bp = (uintptr)pp->n;
+		kv.bh = blkhash(pp->n);
+		setval(n, i++, &kv, 1);
+		if(nbytes != nil)
+			*nbytes += 2 + valsz(&kv);
+	}
+	return i;
+}
+
+/*
+ * Creates a new block with the contents of the old
+ * block. When copying the contents, it repacks them
+ * to minimize the space uses, and applies the changes
+ * pending from the downpath blocks.
+ *
+ * When pidx != -1, 
+ */
+Blk*
+update(Blk *b, Path *p, Path *pp)
+{
+	int i, j, lo, hi, pidx;
+	Blk *n;
+	Msg m;
+
+	j = 0;
+	lo = (p != nil) ? p->lo : -1;
+	hi = (p != nil) ? p->hi : -1;
+	pidx = (p != nil) ? p->idx : -1;
+	n = newblk(b->type);
+	for(i = 0; i < b->nent; i++){
+		if(i == pidx){
+			j = copyup(n, j, pp, nil);
+			continue;
+		}
+		getval(b, i, &m);
+		setval(n, j++, &m, 0);
+	}
+	if(b->type == Pivot){
+		i = 0;
+		j = 0;
+		while(i < b->nmsg){
+			if(i == lo)
+				i = hi;
+			if(i == b->nmsg)
+				break;
+			getmsg(b, i++, &m);
+			setmsg(n, j++, &m);
+		}
+		b->nmsg = j;
+	}
+	return n;
+}
+
+
+/*
+ * Splits a node, returning the block that msg
+ * would be inserted into. Split must never
+ * grow the total height of the 
+ */
+int
+split(Blk *b, Path *p, Path *pp, Kvp *mid)
+{
+	int i, j, copied, halfsz;
+	int lo, hi, pidx;
+	Blk *l, *r;
+	Kvp t;
+	Msg m;
+
+	/*
+	 * If the block one entry up the
+	 * p is nil, we're at the root,
+	 * so we want to make a new block.
+	 */
+	l = newblk(b->type);
+	r = newblk(b->type);
+	if(l == nil || r == nil)
+		goto error;
+
+	lo = (p != nil) ? p->lo : -1;
+	hi = (p != nil) ? p->hi : -1;
+	pidx = (p != nil) ? p->idx : -1;
+
+	j = 0;
+	copied = 0;
+	halfsz = (2*b->nent + b->valsz)/2;
+	for(i = 0; copied < halfsz; i++){
+		if(i == pidx){
+			j = copyup(l, j, pp, &copied);
+			continue;
+		}
+		getval(b, i, &t);
+		setval(l, j++, &t, 0);
+		copied += 2 + valsz(&t);
+	}
+	j = 0;
+	getval(b, i, mid);
+	for(; i < b->nent; i++){
+		if(i == pidx){
+			j = copyup(r, j, pp, nil);
+			continue;
+		}
+		getval(b, i, &t);
+		setval(r, j++, &t, 0);
+	}
+	if(b->type == Pivot){
+		i = 0;
+		for(j = 0; i < b->nmsg; i++, j++){
+			if(i == lo)
+				i = hi;
+			if(i == b->nmsg)
+				break;
+			getmsg(b, i, &m);
+			if(keycmp(&m, mid) >= 0)
+				break;
+			setmsg(l, j, &m);
+		}
+		for(j = 0; i < b->nmsg; i++, j++){
+			if(i == lo)
+				i = hi;
+			if(i == b->nmsg)
+				break;
+			getmsg(b, i, &m);
+			setmsg(r, j, &m);
+		}
+	}
+	p->split = 1;
+	p->l = l;
+	p->r = r;
+	return 0;
+error:
+	if(l != nil) freeblk(l);
+	if(r != nil) freeblk(r);
+	return -1;
+}
+
+int
+apply(Blk *b, Msg *m)
+{
+	assert(b->type == Leaf);
+	assert(b->flag & Bdirty);
+	switch(m->op){
+	case Ocreate:
+		blkinsert(b, m);
+		break;
+	case Odelete:
+		blkdelete(b, m);
+		break;
+	case Owrite:
+		werrstr("unimplemented");
+		goto error;
+	}
+	return 0;
+error:
+	werrstr("invalid upsert");
+	return -1;
+}
+
+static int
+flush(Path *path, int npath, Msg *ins, int *redo)
+{
+	static int nins;
+
+	Path *p, *pp;
+	Blk *b;
+	Kvp mid;
+	Msg m;
+	int i, ret;
+
+	ret = -1;
+	/*
+	 * The path must contain at minimum two elements:
+	 * we must have 1 node we're inserting into, and
+	 * an empty element at the top of the path that
+	 * we put the new root into if the root gets split.
+	 */
+	assert(npath >= 2);
+	*redo = 0;
+	pp = nil;
+	p = &path[npath - 1];
+	if(p->b->type == Leaf){
+		if(!filledleaf(p->b, p[-1].sz)){
+			p->n = update(p->b, p, pp);
+			for(i = p[-1].lo; i < p[-1].hi; i++){
+				getmsg(p[-1].b, i, &m);
+				if(filledleaf(p->n, msgsz(&m)))
+					break;
+				apply(p->n, &m);
+			}
+		}else{
+			if(split(p->b, p, pp, &mid) == -1)
+				goto error;
+			b = p->l;
+			for(i = p[-1].lo; i < p[-1].hi; i++){
+				getmsg(p[-1].b, i, &m);
+				if(keycmp(&m, &mid) >= 0)
+					b = p->r;
+				if(filledleaf(b, msgsz(&m)))
+					continue;
+				if(apply(b, &m) == -1)
+					goto error;
+			}
+		}
+		assert(p->n || (p->l && p->r));
+		pp = p;
+		p--;
+	}
+	for(; p > path; p--){
+		if(!filledpiv(p->b, 1)){
+			p->n = update(p->b, p, pp);
+			for(i = p[-1].lo; i < p[-1].hi; i++){
+				getmsg(p[-1].b, i, &m);
+				if(filledbuf(p->n, msgsz(&m)))
+					break;
+				bufinsert(p->n, &m);
+			}
+		}else{
+			if(split(p->b, p, pp, &mid) == -1)
+				goto error;
+			b = p->l;
+			for(i = p[-1].lo; i < p[-1].hi; i++){
+				getmsg(p[-1].b, i, &m);
+				if(keycmp(&m, &mid) >= 0)
+					b = p->r;
+				if(filledbuf(b, msgsz(&m)))
+					continue;
+				bufinsert(b, &m);
+			}
+		}
+		pp = p;
+	}
+	if(path[1].split){
+		if((path[0].n = newblk(Pivot)) == nil)
+			goto error;
+		copyup(path[0].n, 0, &path[1], nil);
+		bufinsert(path[0].n, ins);
+	}else{
+		if(path[1].b->type == Leaf && !filledleaf(path[1].b, msgsz(ins)))
+			apply(path[1].n, ins);
+		else if(!filledbuf(path[1].n, msgsz(ins)))
+			bufinsert(path[1].n, ins);
+		else
+			*redo = 1;
+	}
+	ret = 0;
+error:
+	for(p = path; p != path + npath; p++){
+		if(p->b != nil)
+			putblk(p->b);
+		if(p->n != nil)
+			putblk(p->n);
+		if(p->l != nil)
+			putblk(p->l);
+		if(p->r != nil)
+			putblk(p->r);
+	}
+	return ret;
+}
+
+/*
+ * Select child node that with the largest message
+ * segment in the current node's buffer.
+ */
+void
+victim(Blk *b, Path *p)
+{
+	int i, j, lo, maxsz, cursz;
+	Kvp kv;
+	Msg m;
+
+	j = 0;
+	lo = 0;
+	maxsz = 0;
+	p->b = b;
+	/* 
+	 * Start at the second pivot: all values <= this
+	 * go to the first node. Stop *after* the last entry,
+	 * because entries >= the last entry all go into it.
+	 */
+	for(i = 1; i <= b->nent; i++){
+		if(i < b->nent)
+			getval(b, i, &kv);
+		cursz = 0;
+		for(; j < b->nmsg; j++){
+			getmsg(b, j, &m);
+			if(i < b->nent && keycmp(&m, &kv) >= 0)
+				break;
+			/* 2 bytes for offset, plus message size in buffer */
+			cursz += 2 + msgsz(&m);
+		}
+		if(cursz > maxsz){
+			maxsz = cursz;
+			p->lo = lo;
+			p->hi = j;
+			p->sz = maxsz;
+			p->idx = i - 1;
+			lo = j;
+		}
+	}
+}
+
+int
+fsupsert(Msg *m)
+{
+	Blk *b, *n, *s;
+	int npath, redo;
+	Path *path;
+	Kvp sep;
+
+	if(m->nk + 2 > Keymax){
+		werrstr("overlong key");
+		return -1;
+	}
+	/*
+	 * The tree can grow in height by 1 when we
+	 * split, so we allocate room for one extra
+	 * node in the path.
+	 */
+again:
+	n = nil;
+	s = nil;
+	redo = 0;
+	npath = 0;
+	path = emalloc((fs->height + 2)*sizeof(Path));
+	path[npath].b = nil;
+	path[npath].idx = -1;
+	npath++;
+
+	b = fs->root;
+	path[0].sz = msgsz(m);
+	while(b->type == Pivot){
+		if(!filledbuf(b, path[npath - 1].sz))
+			break;
+		victim(b, &path[npath]);
+		getval(b, path[npath].idx, &sep);
+		b = getblk(sep.bp, sep.bh);
+		if(b == nil)
+			goto error;
+		npath++;
+	}
+	path[npath].b = b;
+	path[npath].idx = -1;
+	path[npath].lo = 0;
+	path[npath].hi = 0;
+	npath++;
+	if(flush(path, npath, m, &redo) == -1)
+		goto error;
+	b = path[0].n;
+	if(b != nil)
+		fs->height++;
+	else
+		b = path[1].n;
+	fs->root = b;
+	free(path);
+	if(redo)
+		goto again;
+	return 0;
+error:
+	if(n != nil) freeblk(n);
+	if(s != nil) freeblk(s);
+	free(path);
+	return -1;
+}
+
+static char*
+collect(Blk *b, Key *k, Kvp *r, int *done)
+{
+	int i, idx;
+	Msg m;
+
+	*done = 0;
+	if(bufsearch(b, k, &m, &idx) != 0)
+		return nil;
+	for(i = idx; i < b->nmsg; i++){
+		getmsg(b, i, &m);
+		if(keycmp(&m, k) != 0)
+			break;
+		switch(m.op){
+		case Ocreate:
+			*r = m.Kvp;
+			*done = 1;
+			return nil;
+		case Odelete:
+			*done = 1;
+			return Eexist;
+		/* The others don't affect walks */
+		}
+	}
+	return nil;
+}
+
+char*
+fswalk1(Key *k, Kvp *r)
+{
+	int idx, same, done;
+	char *ret;
+	Blk *b;
+
+	b = fs->root;
+	while(b->type == Pivot){
+		ret = collect(b, k, r, &done);
+		if(done)
+			return ret;
+		if(blksearch(b, k, r, &idx, nil) == -1 || idx == -1)
+			return Eexist;
+		if((b = getblk(r->bp, r->bh)) == nil)
+			return Efs;
+	}
+	assert(b->type == Leaf);
+	if(blksearch(b, k, r, nil, &same) == -1 || !same)
+		return Eexist;
+	return nil;
+}
--- /dev/null
+++ b/util.c
@@ -1,0 +1,38 @@
+#include <u.h>
+#include <libc.h>
+#include "dat.h"
+#include "fns.h"
+
+void *
+emalloc(usize n)
+{
+	void *v;
+	
+	v = mallocz(n, 1);
+	if(v == nil)
+		sysfatal("malloc: %r");
+	setmalloctag(v, getcallerpc(&n));
+	return v;
+}
+
+void *
+erealloc(void *p, usize n)
+{
+	void *v;
+	
+	v = realloc(p, n);
+	if(v == nil)
+		sysfatal("realloc: %r");
+	setmalloctag(v, getcallerpc(&n));
+	return v;
+}
+
+char*
+estrdup(char *s)
+{
+	s = strdup(s);
+	if(s == nil)
+		sysfatal("strdup: %r");
+	setmalloctag(s, getcallerpc(&s));
+	return s;
+}