devenv: allow environment total size of up to 1MB

Sometimes, there is the one-off occation when one needs to
pass a huge list in rc...

This change makes devenv track total memory consumption
of environment groups allowing them to grow up to 1MB in
size (including overhead).

(Before, only the variable size was restricted, but
not the amount of files being created).

The maximum value size of a single environment variable
is set to half of the total size, which allows the
occational large value. (But not many of them).

Because we track all memory consuption, it is also
now possible to create around 10k small environment
variales.

A hashtable is added for name lookups and the qid.path
was changed to allow direct indexing into the entry
array without needing a scan lookup.

All smalloc() calls have been removed, exhaustion is
handled with error(Enomem) avoiding deadlock
in case we run out of kernel memory.

3 files changed, 234 insertions, 150 deletions

diff --git a/sys/man/3/env b/sys/man/3/env
index 0318f3488..b46e171d8 100644
--- a/sys/man/3/env
+++ b/sys/man/3/env
@@ -58,6 +58,3 @@ in
 .IR plan9.ini (8)
 .SH SOURCE
 .B /sys/src/9/port/devenv.c
-.SH BUGS
-A write starting at an offset after the current extent of a file
-yields an error instead of zero filling.
diff --git a/sys/src/9/port/devenv.c b/sys/src/9/port/devenv.c
index 2308ad283..089997002 100644
--- a/sys/src/9/port/devenv.c
+++ b/sys/src/9/port/devenv.c
@@ -7,27 +7,53 @@
 
 enum
 {
+	Maxenvsize = 1*MB,
+	Maxvalsize = Maxenvsize/2,
+
 	DELTAENV = 32,
-	Maxenvsize = 16300,
 };
 
 static Egrp	*envgrp(Chan *c);
-static int	envwriteable(Chan *c);
+static int	envwritable(Chan *c);
 
 static Egrp	confegrp;	/* global environment group containing the kernel configuration */
 
+#define PATH(p,i)	((uvlong)(p) << 32 | (i))
+#define QID(quidpath)	((uint)(quidpath) & 0x7FFFFFFF)
+
 static Evalue*
-envlookup(Egrp *eg, char *name, ulong qidpath)
+envindex(Egrp *eg, uvlong qidpath)
 {
-	Evalue *e, *ee;
+	Evalue *e;
+	int i;
+
+	i = QID(qidpath);
+	if(i >= eg->nent)
+		return nil;
+	e = eg->ent[i];
+	if(e != nil && e->path != qidpath)
+		return nil;
+	return e;
+}
 
-	e = eg->ent;
-	for(ee = e + eg->nent; e < ee; e++){
-		if(e->qid.path == qidpath
-		|| (name != nil && name[0] == e->name[0] && strcmp(e->name, name) == 0))
-			return e;
+static Evalue**
+envhash(Egrp *eg, char *name)
+{
+	uint c, h = 0;
+	while(c = *name++)
+		h = h*131 + c;
+	return &eg->hash[h % ENVHASH];
+}
+
+static Evalue*
+lookupname(Evalue *e, char *name)
+{
+	while(e != nil){
+		if(strcmp(e->name, name) == 0)
+			break;
+		e = e->hash;
 	}
-	return nil;
+	return e;
 }
 
 static int
@@ -35,28 +61,40 @@ envgen(Chan *c, char *name, Dirtab*, int, int s, Dir *dp)
 {
 	Egrp *eg;
 	Evalue *e;
+	Qid q;
 
+	eg = envgrp(c);
 	if(s == DEVDOTDOT){
+		c->qid.vers = eg->vers;
 		devdir(c, c->qid, "#e", 0, eve, 0775, dp);
 		return 1;
 	}
-
-	eg = envgrp(c);
 	rlock(eg);
-	if(name != nil)
-		e = envlookup(eg, name, -1);
-	else if(s < eg->nent)
-		e = &eg->ent[s];
-	else
-		e = nil;
-	if(e == nil || name != nil && (strlen(e->name) >= sizeof(up->genbuf))) {
+	if((c->qid.type & QTDIR) == 0) {
+		e = envindex(eg, c->qid.path);
+		if(e == nil)
+			goto Notfound;
+	} else if(name != nil) {
+		if(strlen(name) >= sizeof(up->genbuf))
+			goto Notfound;
+		e = lookupname(*envhash(eg, name), name);
+		if(e == nil)
+			goto Notfound;
+	} else if(s < eg->nent) {
+		e = eg->ent[s];
+		if(e == nil) {
+			runlock(eg);
+			return 0;	/* deleted, try next */
+		}
+	} else {
+Notfound:
 		runlock(eg);
 		return -1;
 	}
-
 	/* make sure name string continues to exist after we release lock */
-	kstrcpy(up->genbuf, e->name, sizeof up->genbuf);
-	devdir(c, e->qid, up->genbuf, e->len, eve,
+	kstrcpy(up->genbuf, e->name, sizeof(up->genbuf));
+	mkqid(&q, e->path, e->vers, QTFILE);
+	devdir(c, q, up->genbuf, e->len, eve,
 		eg == &confegrp || eg != up->egrp ? 0664: 0666, dp);
 	runlock(eg);
 	return 1;
@@ -82,15 +120,34 @@ envattach(char *spec)
 static Walkqid*
 envwalk(Chan *c, Chan *nc, char **name, int nname)
 {
-	return devwalk(c, nc, name, nname, 0, 0, envgen);
+	return devwalk(c, nc, name, nname, nil, 0, envgen);
 }
 
 static int
 envstat(Chan *c, uchar *db, int n)
 {
-	if(c->qid.type & QTDIR)
-		c->qid.vers = envgrp(c)->vers;
-	return devstat(c, db, n, 0, 0, envgen);
+	return devstat(c, db, n, nil, 0, envgen);
+}
+
+static void*
+envrealloc(Egrp *eg, void *old, int newsize)
+{
+	int oldsize = old != nil ? msize(old) : 0;
+	void *new;
+
+	if(newsize == 0){
+		eg->alloc -= oldsize;
+		free(old);
+		return nil;
+	}
+	if(newsize < 0 || eg != &confegrp && (eg->alloc + newsize) - oldsize > Maxenvsize)
+		error(Enomem);
+	new = realloc(old, newsize);
+	if(new == nil)
+		error(Enomem);
+	eg->alloc += msize(new) - oldsize;
+	setmalloctag(new, getcallerpc(&eg));
+	return new;
 }
 
 static Chan*
@@ -98,7 +155,6 @@ envopen(Chan *c, int omode)
 {
 	Egrp *eg;
 	Evalue *e;
-	int trunc;
 
 	eg = envgrp(c);
 	if(c->qid.type & QTDIR) {
@@ -106,14 +162,14 @@ envopen(Chan *c, int omode)
 			error(Eperm);
 	}
 	else {
-		trunc = omode & OTRUNC;
-		if(omode != OREAD && !envwriteable(c))
+		int trunc = omode & OTRUNC;
+		if(omode != OREAD && !envwritable(c))
 			error(Eperm);
 		if(trunc)
 			wlock(eg);
 		else
 			rlock(eg);
-		e = envlookup(eg, nil, c->qid.path);
+		e = envindex(eg, c->qid.path);
 		if(e == nil) {
 			if(trunc)
 				wunlock(eg);
@@ -121,12 +177,12 @@ envopen(Chan *c, int omode)
 				runlock(eg);
 			error(Enonexist);
 		}
-		if(trunc && e->value != nil) {
-			e->qid.vers++;
-			free(e->value);
-			e->value = nil;
+		if(trunc && e->len > 0) {
+			e->value = envrealloc(eg, e->value, 0);	/* free */
 			e->len = 0;
+			e->vers++;
 		}
+		c->qid.vers = e->vers;
 		if(trunc)
 			wunlock(eg);
 		else
@@ -144,12 +200,14 @@ static Chan*
 envcreate(Chan *c, char *name, int omode, ulong)
 {
 	Egrp *eg;
-	Evalue *e;
+	Evalue *e, **h;
+	int n, i;
 
-	if(c->qid.type != QTDIR || !envwriteable(c))
+	if(c->qid.type != QTDIR || !envwritable(c))
 		error(Eperm);
 
-	if(strlen(name) >= sizeof(up->genbuf))
+	n = strlen(name)+1;
+	if(n > sizeof(up->genbuf))
 		error(Etoolong);
 
 	omode = openmode(omode);
@@ -160,28 +218,33 @@ envcreate(Chan *c, char *name, int omode, ulong)
 		nexterror();
 	}
 
-	if(envlookup(eg, name, -1) != nil)
+	h = envhash(eg, name);
+	if(lookupname(*h, name) != nil)
 		error(Eexist);
 
-	if(eg->nent == eg->ment){
-		Evalue *tmp;
+	for(i = eg->low; i < eg->nent; i++)
+		if(eg->ent[i] == nil)
+			break;
 
-		eg->ment += DELTAENV;
-		if((tmp = realloc(eg->ent, sizeof(eg->ent[0])*eg->ment)) == nil){
-			eg->ment -= DELTAENV;
-			error(Enomem);
-		}
-		eg->ent = tmp;
+	if(i >= eg->nent){
+		if((eg->nent % DELTAENV) == 0)
+			eg->ent = envrealloc(eg, eg->ent, (eg->nent+DELTAENV) * sizeof(Evalue*));
+		i = eg->nent++;
+		eg->ent[i] = nil;
+		eg->low = i;
 	}
-	eg->vers++;
-	e = &eg->ent[eg->nent++];
+
+	e = envrealloc(eg, nil, sizeof(Evalue)+n);
+	memmove(e->name, name, n);
 	e->value = nil;
 	e->len = 0;
-	e->name = smalloc(strlen(name)+1);
-	strcpy(e->name, name);
-	mkqid(&e->qid, ++eg->path, 0, QTFILE);
-	c->qid = e->qid;
-
+	e->vers = 0;
+	e->path = PATH(++eg->path, i);
+	e->hash = *h, *h = e;
+	eg->ent[i] = e;
+	eg->low = i+1;
+	eg->vers++;
+	mkqid(&c->qid, e->path, e->vers, QTFILE);
 	wunlock(eg);
 	poperror();
 	incref(eg);
@@ -196,22 +259,35 @@ static void
 envremove(Chan *c)
 {
 	Egrp *eg;
-	Evalue *e;
+	Evalue *e, **h;
+	int i;
 
-	if(c->qid.type & QTDIR || !envwriteable(c))
+	if(c->qid.type & QTDIR || !envwritable(c))
 		error(Eperm);
 
 	eg = envgrp(c);
 	wlock(eg);
-	e = envlookup(eg, nil, c->qid.path);
+	e = envindex(eg, c->qid.path);
 	if(e == nil){
 		wunlock(eg);
 		error(Enonexist);
 	}
-	free(e->name);
-	free(e->value);
-	*e = eg->ent[--eg->nent];
+	for(h = envhash(eg, e->name); *h != nil; h = &(*h)->hash){
+		if(*h == e){
+			*h = e->hash;
+			break;
+		}
+	}
+	i = QID(c->qid.path);
+	eg->ent[i] = nil;
+	if(i < eg->low)
+		eg->low = i;
 	eg->vers++;
+
+	/* free */
+	envrealloc(eg, e->value, 0);
+	envrealloc(eg, e, 0);
+
 	wunlock(eg);
 }
 
@@ -238,10 +314,9 @@ envread(Chan *c, void *a, long n, vlong off)
 {
 	Egrp *eg;
 	Evalue *e;
-	ulong offset = off;
 
 	if(c->qid.type & QTDIR)
-		return devdirread(c, a, n, 0, 0, envgen);
+		return devdirread(c, a, n, nil, 0, envgen);
 
 	eg = envgrp(c);
 	rlock(eg);
@@ -249,19 +324,17 @@ envread(Chan *c, void *a, long n, vlong off)
 		runlock(eg);
 		nexterror();
 	}
-
-	e = envlookup(eg, nil, c->qid.path);
+	e = envindex(eg, c->qid.path);
 	if(e == nil)
 		error(Enonexist);
-	if(offset >= e->len || e->value == nil)
+	if(off >= e->len)
 		n = 0;
-	else if(offset + n > e->len)
-		n = e->len - offset;
+	else if(off + n > e->len)
+		n = e->len - off;
 	if(n <= 0)
 		n = 0;
 	else
-		memmove(a, e->value+offset, n);
-
+		memmove(a, e->value+off, n);
 	runlock(eg);
 	poperror();
 	return n;
@@ -270,16 +343,9 @@ envread(Chan *c, void *a, long n, vlong off)
 static long
 envwrite(Chan *c, void *a, long n, vlong off)
 {
-	char *s;
-	ulong len;
 	Egrp *eg;
 	Evalue *e;
-	ulong offset = off;
-
-	if(n <= 0)
-		return 0;
-	if(offset > Maxenvsize || n > (Maxenvsize - offset))
-		error(Etoobig);
+	int diff;
 
 	eg = envgrp(c);
 	wlock(eg);
@@ -287,24 +353,22 @@ envwrite(Chan *c, void *a, long n, vlong off)
 		wunlock(eg);
 		nexterror();
 	}
-
-	e = envlookup(eg, nil, c->qid.path);
+	e = envindex(eg, c->qid.path);
 	if(e == nil)
 		error(Enonexist);
-
-	len = offset+n;
-	if(len > e->len) {
-		s = realloc(e->value, len);
-		if(s == nil)
-			error(Enomem);
-		memset(s+offset, 0, n);
-		e->value = s;
-		e->len = len;
-	}
-	memmove(e->value+offset, a, n);
-	e->qid.vers++;
+	if(off > Maxvalsize || n > (Maxvalsize - off))
+		error(Etoobig);
+	diff = (off+n) - e->len;
+	if(diff > 0)
+		e->value = envrealloc(eg, e->value, e->len+diff);
+	else
+		diff = 0;
+	memmove(e->value+off, a, n);	/* might fault */
+	if(off > e->len)
+		memset(e->value+e->len, 0, off-e->len);
+	e->len += diff;
+	e->vers++;
 	eg->vers++;
-
 	wunlock(eg);
 	poperror();
 	return n;
@@ -334,41 +398,58 @@ Dev envdevtab = {
 void
 envcpy(Egrp *to, Egrp *from)
 {
-	Evalue *e, *ee, *ne;
+	Evalue *e, *ne, **h;
+	int i, n;
 
 	rlock(from);
-	to->ment = ROUND(from->nent, DELTAENV);
-	to->ent = smalloc(to->ment*sizeof(to->ent[0]));
-	ne = to->ent;
-	e = from->ent;
-	for(ee = e + from->nent; e < ee; e++, ne++){
-		ne->name = smalloc(strlen(e->name)+1);
-		strcpy(ne->name, e->name);
-		if(e->value != nil){
-			ne->value = smalloc(e->len);
+	if(waserror()){
+		runlock(from);
+		nexterror();
+	}
+	to->nent = 0;
+	to->ent = envrealloc(to, nil, ROUND(from->nent, DELTAENV) * sizeof(Evalue*));
+	for(i = 0; i < from->nent; i++){
+		e = from->ent[i];
+		if(e == nil)
+			continue;
+		h = envhash(to, e->name);
+		n = strlen(e->name)+1;
+		ne = envrealloc(to, nil, sizeof(Evalue)+n);
+		memmove(ne->name, e->name, n);
+		ne->value = nil;
+		ne->len = 0;
+		ne->vers = 0;
+		ne->path = PATH(++to->path, to->nent);
+		ne->hash = *h, *h = ne;
+		to->ent[to->nent++] = ne;
+		if(e->len > 0){
+			ne->value = envrealloc(to, ne->value, e->len);
 			memmove(ne->value, e->value, e->len);
 			ne->len = e->len;
 		}
-		mkqid(&ne->qid, ++to->path, 0, QTFILE);
 	}
-	to->nent = from->nent;
+	to->low = to->nent;
 	runlock(from);
+	poperror();
 }
 
 void
 closeegrp(Egrp *eg)
 {
-	Evalue *e, *ee;
-
-	if(decref(eg) == 0 && eg != &confegrp){
-		e = eg->ent;
-		for(ee = e + eg->nent; e < ee; e++){
-			free(e->name);
-			free(e->value);
-		}
-		free(eg->ent);
-		free(eg);
+	Evalue *e;
+	int i;
+
+	if(decref(eg) || eg == &confegrp)
+		return;
+	for(i = 0; i < eg->nent; i++){
+		e = eg->ent[i];
+		if(e == nil)
+			continue;
+		free(e->value);
+		free(e);
 	}
+	free(eg->ent);
+	free(eg);
 }
 
 static Egrp*
@@ -380,7 +461,7 @@ envgrp(Chan *c)
 }
 
 static int
-envwriteable(Chan *c)
+envwritable(Chan *c)
 {
 	return c->aux == nil || c->aux == up->egrp || iseve();
 }
@@ -409,38 +490,38 @@ char *
 getconfenv(void)
 {
 	Egrp *eg = &confegrp;
-	Evalue *e, *ee;
+	Evalue *e;
 	char *p, *q;
-	int n;
+	int i, n;
 
 	rlock(eg);
-	if(waserror()) {
-		runlock(eg);
-		nexterror();
+	n = 1;
+	for(i = 0; i < eg->nent; i++){
+		e = eg->ent[i];
+		if(e == nil)
+			continue;
+		n += strlen(e->name)+e->len+2;
 	}
-	
-	/* determine size */
-	n = 0;
-	e = eg->ent;
-	for(ee = e + eg->nent; e < ee; e++)
-		n += strlen(e->name) + e->len + 2;
-
-	p = malloc(n + 1);
-	if(p == nil)
+	p = malloc(n);
+	if(p == nil){
+		runlock(eg);
 		error(Enomem);
+	}
 	q = p;
-	e = eg->ent;
-	for(ee = e + eg->nent; e < ee; e++){
-		strcpy(q, e->name);
-		q += strlen(q) + 1;
+	for(i = 0; i < eg->nent; i++){
+		e = eg->ent[i];
+		if(e == nil)
+			continue;
+		n = strlen(e->name)+1;
+		memmove(q, e->name, n);
+		q += n;
 		memmove(q, e->value, e->len);
 		q[e->len] = 0;
 		/* move up to the first null */
 		q += strlen(q) + 1;
 	}
 	*q = '\0';
-	
 	runlock(eg);
-	poperror();
+
 	return p;
 }
diff --git a/sys/src/9/port/portdat.h b/sys/src/9/port/portdat.h
index 5bb641f7f..421f673e6 100644
--- a/sys/src/9/port/portdat.h
+++ b/sys/src/9/port/portdat.h
@@ -456,6 +456,8 @@ enum
 	NFD =		100,		/* per process file descriptors */
 	PGHLOG  =	9,
 	PGHSIZE	=	1<<PGHLOG,	/* Page hash for image lookup */
+	ENVLOG =	5,
+	ENVHASH =	1<<ENVLOG,	/* Egrp hash for variable lookup */
 };
 #define REND(p,s)	((p)->rendhash[(s)&((1<<RENDLOG)-1)])
 #define MOUNTH(p,qid)	((p)->mnthash[(qid).path&((1<<MNTLOG)-1)])
@@ -493,23 +495,27 @@ struct Rgrp
 	Proc	*rendhash[RENDHASH];	/* Rendezvous tag hash */
 };
 
-struct Egrp
-{
-	Ref;
-	RWlock;
-	Evalue	*ent;
-	int	nent;
-	int	ment;
-	ulong	path;	/* qid.path of next Evalue to be allocated */
-	ulong	vers;	/* of Egrp */
-};
-
 struct Evalue
 {
-	char	*name;
 	char	*value;
 	int	len;
-	Qid	qid;
+	ulong	vers;
+	uvlong	path;			/* qid.path: Egrp.path << 32 | index (of Egrp.ent[]) */
+	Evalue	*hash;
+	char	name[];
+};
+
+struct Egrp
+{
+	Ref;
+	RWlock;
+	Evalue	**ent;
+	int	nent;			/* numer of slots in ent[] */
+	int	low;			/* lowest free index in ent[] */
+	int	alloc;			/* bytes allocated for env */
+	ulong	path;			/* generator for qid path */
+	ulong	vers;			/* of Egrp */
+	Evalue	*hash[ENVHASH];		/* hashtable for name lookup */
 };
 
 struct Fgrp