shithub: gefs

Download patch

ref: 2ffda6b58c2e5fc7993066ca323898149e66495f
parent: 11398465c52e4fed4e62451f7ad31290726f6754
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Jan 31 12:21:28 EST 2022

tree: implement optimized upsert

The copying and small merges were expensive;
this optimized version is better, though it
still copies the blocks more than I want.

--- a/blk.c
+++ b/blk.c
@@ -103,8 +103,6 @@
 
 	switch(b->type){
 	default:
-		if(flg&GBraw)
-			break;
 		fprint(2, "invalid block @%llx\n", bp);
 		abort();
 		break;
@@ -674,9 +672,29 @@
 		return nil;
 	if((b = initblk(bp, t)) == nil)
 		return nil;
-
 	setmalloctag(b, getcallerpc(&t));
 	return b;
+}
+
+Blk*
+dupblk(Blk *b)
+{
+	Blk *r;
+
+	if((r = newblk(b->type)) == nil)
+		return nil;
+
+	setflag(r, Bdirty);
+	r->bp.hash = b->bp.hash;
+	r->nval = b->nval;
+	r->valsz = b->valsz;
+	r->nbuf = b->nbuf;
+	r->bufsz = b->bufsz;
+	r->logsz = b->logsz;
+	r->lognxt = b->lognxt;
+	memcpy(r->buf, b->buf, sizeof(r->buf));
+	setmalloctag(b, getcallerpc(&b));
+	return r;
 }
 
 void
--- a/dat.h
+++ b/dat.h
@@ -86,7 +86,6 @@
 	Ktref,	/* tag[8] = snapid[]		scratch snapshot label */
 	Ksnap,	/* sid[8] => ref[8], tree[52]:	snapshot root */
 	Ksuper,	/* qid[8] => Kent:		parent dir */
-	Kdirty,	/* [0] => [0]:			mark dirty unmount */
 };
 
 enum {
@@ -392,6 +391,10 @@
 	int	ht;
 	Bptr	bp;
 	vlong	gen;
+	Msg	flush[16];
+	int	nflush;
+	int	flushsz;
+	char	flushbuf[Bufspc/2];
 	Dlist	dead[Ndead];
 };
 
--- a/fns.h
+++ b/fns.h
@@ -12,6 +12,7 @@
 extern char*	forceuser;
 
 Blk*	newblk(int type);
+Blk*	dupblk(Blk*);
 Blk*	getroot(Tree*, int*);
 Blk*	getblk(Bptr, int);
 Blk*	refblk(Blk*);
--- a/tree.c
+++ b/tree.c
@@ -194,8 +194,6 @@
 			hi = mid-1;
 			break;
 		case 0:
-			if(same != nil)
-				*same = 1;
 			ri = mid;
 			hi = mid-1;
 			break;
@@ -214,7 +212,7 @@
 		ri = lo-1;
 	else
 		*same = 1;
-	if(ri >= 0)
+	if(m != nil && ri >= 0)
 		getmsg(b, ri, m);
 	return ri;
 }
@@ -237,8 +235,6 @@
 			hi = mid-1;
 			break;
 		case 0:
-			if(same != nil)
-				*same = 1;
 			ri = mid;
 			hi = mid-1;
 			break;
@@ -1112,6 +1108,62 @@
 	}
 }
 
+static char*
+fastupsert(Tree *t, Blk *b, Msg *msg, int nmsg)
+{
+	int i, c, o, ri, lo, hi, mid, nbuf;
+	Msg cmp;
+	char *p;
+	Blk *r;
+
+	if((r = dupblk(b)) == nil)
+		return Emem;
+	
+	nbuf = r->nbuf;
+	for(i = 0; i < nmsg; i++)
+		setmsg(r, &msg[i]);
+
+	for(i = 0; i < nmsg; i++){
+		ri = -1;
+		lo = 0;
+		hi = nbuf+i-1;
+		while(lo <= hi){
+			mid = (hi + lo) / 2;
+			getmsg(r, mid, &cmp);
+			c = keycmp(&msg[i], &cmp);
+			switch(c){
+			case -1:
+				hi = mid-1;
+				break;
+			case 0:
+				ri = mid+1;
+				lo = mid+1;
+				break;
+			case 1:
+				lo = mid+1;
+				break;
+			}
+		}
+		if(ri == -1)
+			ri = hi+1;
+		p = r->data + Pivspc + 2*(nbuf+i);
+		o = GBIT16(p);
+		p = r->data + Pivspc + 2*ri;
+		memmove(p+2, p, 2*(nbuf+i-ri));
+		PBIT16(p, o);
+	}
+	lock(&t->lk);
+	t->bp = r->bp;
+	unlock(&t->lk);
+
+	freeblk(t, b);
+	enqueue(r);
+	putblk(b);
+	putblk(r);
+	return nil;
+}
+	
+
 char*
 btupsert(Tree *t, Msg *msg, int nmsg)
 {
@@ -1129,6 +1181,8 @@
 Again:
 	if((b = getroot(t, &height)) == nil)
 		return Efs;
+	if(b->type == Tpivot && !filledbuf(b, nmsg, sz))
+		return fastupsert(t, b, msg, nmsg);
 
 	/*
 	 * The tree can grow in height by 1 when we