changelog shortlog tags branches files raw gz bz2 help

Mercurial > hg > plan9front / changeset: upas/fs: speedup mtree and henter()

changeset 7405: 82225c0fc1a2
parent 7404: 6e0c926efd3b
child 7406: 2d4a24309bdc
author: cinap_lenrek@felloff.net
date: Thu, 03 Oct 2019 15:49:53 +0200
files: sys/src/cmd/upas/fs/cache.c sys/src/cmd/upas/fs/dat.h sys/src/cmd/upas/fs/fs.c sys/src/cmd/upas/fs/mbox.c sys/src/cmd/upas/fs/mtree.c
description: upas/fs: speedup mtree and henter()

move digest pointer into Mtree structrue and embed it into Idx struct
(which is embedded in Message) to avoid one level of indirection
during mtreecmp().

get rid of mtreeisdup(). instead we have mtreeadd() return the old
message in case of a collision. this avoids double lookup.

increase the hash table size for henter() and make it a prime.
     1.1--- a/sys/src/cmd/upas/fs/cache.c
     1.2+++ b/sys/src/cmd/upas/fs/cache.c
     1.3@@ -319,14 +319,17 @@ found:
     1.4 void
     1.5 digestmessage(Mailbox *mb, Message *m)
     1.6 {
     1.7+	Message *old;
     1.8+
     1.9 	assert(m->digest == nil);
    1.10 	m->digest = emalloc(SHA1dlen);
    1.11 	sha1((uchar*)m->start, m->end - m->start, m->digest, nil);
    1.12-	if(mtreeisdup(mb, m)){
    1.13+	old = mtreeadd(mb, m);
    1.14+	if(old != nil && old != m){
    1.15+		m = mtreeadd(mb, old);
    1.16 		logmsg(m, "dup detected");
    1.17 		m->deleted = Dup;	/* no dups allowed */
    1.18-	}else
    1.19-		mtreeadd(mb, m);
    1.20+	}
    1.21 	dprint("%lud %#A\n", m->id, m->digest);
    1.22 }
    1.23 
     2.1--- a/sys/src/cmd/upas/fs/dat.h
     2.2+++ b/sys/src/cmd/upas/fs/dat.h
     2.3@@ -42,10 +42,16 @@ enum {
     2.4 	Nref		= 10,
     2.5 };
     2.6 
     2.7+typedef struct {
     2.8+	Avl;
     2.9+	uchar	*digest;
    2.10+} Mtree;
    2.11+
    2.12 typedef struct Idx Idx;
    2.13 struct Idx {
    2.14+	Mtree;
    2.15+
    2.16 	char	*str;			/* as read from idx file */
    2.17-	uchar	*digest;
    2.18 	uchar	flags;
    2.19 	uvlong	fileid;
    2.20 	ulong	lines;
    2.21@@ -136,11 +142,6 @@ struct Message {
    2.22 	};
    2.23 };
    2.24 
    2.25-typedef struct {
    2.26-	Avl;
    2.27-	Message *m;
    2.28-} Mtree;
    2.29-
    2.30 typedef struct Mcache Mcache;
    2.31 struct Mcache {
    2.32 	uvlong	cached;
    2.33@@ -256,10 +257,10 @@ void		rmidx(char*, int);
    2.34 int		vremove(char*);
    2.35 int		rename(char *, char*, int);
    2.36 
    2.37-int		mtreecmp(Avl*, Avl*);
    2.38-int		mtreeisdup(Mailbox *, Message *);
    2.39+void		mtreeinit(Mailbox *);
    2.40+void		mtreefree(Mailbox *);
    2.41 Message*	mtreefind(Mailbox*, uchar*);
    2.42-void		mtreeadd(Mailbox*, Message*);
    2.43+Message*	mtreeadd(Mailbox*, Message*);
    2.44 void		mtreedelete(Mailbox*, Message*);
    2.45 
    2.46 enum {
     3.1--- a/sys/src/cmd/upas/fs/fs.c
     3.2+++ b/sys/src/cmd/upas/fs/fs.c
     3.3@@ -122,7 +122,7 @@ static	char	hbuf[32*1024];
     3.4 static	uchar	mbuf[16*1024 + IOHDRSZ];
     3.5 static	uchar	mdata[16*1024 + IOHDRSZ];
     3.6 static	ulong	path;		/* incremented for each new file */
     3.7-static	Hash	*htab[1024];
     3.8+static	Hash	*htab[2053];
     3.9 static	Fcall	rhdr;
    3.10 static	Fcall	thdr;
    3.11 static	Fid	*fids;
     4.1--- a/sys/src/cmd/upas/fs/mbox.c
     4.2+++ b/sys/src/cmd/upas/fs/mbox.c
     4.3@@ -267,7 +267,7 @@ newmbox(char *path, char *name, int flag
     4.4 	mb->next = nil;
     4.5 	mb->id = newid();
     4.6 	mb->root = newmessage(nil);
     4.7-	mb->mtree = avlcreate(mtreecmp);
     4.8+	mtreeinit(mb);
     4.9 
    4.10 	*l = mb;
    4.11 
    4.12@@ -1187,7 +1187,7 @@ mboxdecref(Mailbox *mb)
    4.13 	if(mb->flags & ORCLOSE && mb->remove)
    4.14 	if(mb->remove(mb, mb->rmflags))
    4.15 		rmidx(mb->path, mb->rmflags);
    4.16-	free(mb->mtree);
    4.17+	mtreefree(mb);
    4.18 	free(mb->d);
    4.19 	free(mb);
    4.20 }
     5.1--- a/sys/src/cmd/upas/fs/mtree.c
     5.2+++ b/sys/src/cmd/upas/fs/mtree.c
     5.3@@ -2,79 +2,62 @@
     5.4 #include <libsec.h>
     5.5 #include "dat.h"
     5.6 
     5.7-int
     5.8+#define messageof(p)	((Message*)(((uchar*)&(p)->digest) - offsetof(Message, digest)))
     5.9+
    5.10+static int
    5.11 mtreecmp(Avl *va, Avl *vb)
    5.12 {
    5.13-	Mtree *a, *b;
    5.14-
    5.15-	a = (Mtree*)va;
    5.16-	b = (Mtree*)vb;
    5.17-	return memcmp(a->m->digest, b->m->digest, SHA1dlen);
    5.18+	return memcmp(((Mtree*)va)->digest, ((Mtree*)vb)->digest, SHA1dlen);
    5.19 }
    5.20 
    5.21-int
    5.22-mtreeisdup(Mailbox *mb, Message *m)
    5.23+void
    5.24+mtreeinit(Mailbox *mb)
    5.25 {
    5.26-	Mtree t;
    5.27+	mb->mtree = avlcreate(mtreecmp);
    5.28+}
    5.29 
    5.30-	assert(Topmsg(mb, m) && m->digest);
    5.31-	if(m->digest == nil)
    5.32-		return 0;
    5.33-	memset(&t, 0, sizeof t);
    5.34-	t.m = m;
    5.35-	if(avllookup(mb->mtree, &t, 0))
    5.36-		return 1;
    5.37-	return 0;
    5.38+void
    5.39+mtreefree(Mailbox *mb)
    5.40+{
    5.41+	free(mb->mtree);
    5.42+	mb->mtree = nil;
    5.43 }
    5.44 
    5.45 Message*
    5.46 mtreefind(Mailbox *mb, uchar *digest)
    5.47 {
    5.48-	Message m0;
    5.49 	Mtree t, *p;
    5.50 
    5.51-	m0.digest = digest;
    5.52-	memset(&t, 0, sizeof t);
    5.53-	t.m = &m0;
    5.54-	if(p = (Mtree*)avllookup(mb->mtree, &t, 0))
    5.55-		return p->m;
    5.56-	return nil;
    5.57+	t.digest = digest;
    5.58+	if((p = (Mtree*)avllookup(mb->mtree, &t, 0)) == nil)
    5.59+		return nil;
    5.60+	return messageof(p);
    5.61 }
    5.62 
    5.63-void
    5.64+Message*
    5.65 mtreeadd(Mailbox *mb, Message *m)
    5.66 {
    5.67-	Avl *old;
    5.68-	Mtree *p;
    5.69+	Mtree *old;
    5.70 
    5.71-	assert(Topmsg(mb, m) && m->digest);
    5.72-	p = emalloc(sizeof *p);
    5.73-	p->m = m;
    5.74-	old = avlinsert(mb->mtree, p);
    5.75-	assert(old == 0);
    5.76+	assert(Topmsg(mb, m) && m->digest != nil);
    5.77+	if((old = (Mtree*)avlinsert(mb->mtree, m)) == nil)
    5.78+		return nil;
    5.79+	return messageof(old);
    5.80 }
    5.81 
    5.82 void
    5.83 mtreedelete(Mailbox *mb, Message *m)
    5.84 {
    5.85-	Mtree t, *p;
    5.86+	Mtree *old;
    5.87 
    5.88 	assert(Topmsg(mb, m));
    5.89-	memset(&t, 0, sizeof t);
    5.90-	t.m = m;
    5.91+	if(m->digest == nil)
    5.92+		return;
    5.93 	if(m->deleted & ~Deleted){
    5.94-		if(m->digest == nil)
    5.95-			return;
    5.96-		p = (Mtree*)avllookup(mb->mtree, &t, 0);
    5.97-		if(p == nil || p->m != m)
    5.98+		old = (Mtree*)avllookup(mb->mtree, m, 0);
    5.99+		if(old == nil || messageof(old) != m)
   5.100 			return;
   5.101-		p = (Mtree*)avldelete(mb->mtree, &t);
   5.102-		free(p);
   5.103-		return;
   5.104 	}
   5.105-	assert(m->digest);
   5.106-	p = (Mtree*)avldelete(mb->mtree, &t);
   5.107-	if(p == nil)
   5.108-		_assert("mtree delete fails");
   5.109-	free(p);
   5.110+	old = (Mtree*)avldelete(mb->mtree, m);
   5.111+	assert(messageof(old) == m);
   5.112 }