shithub: gefs

Info  •  Files  •  Log  •  Branches

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