git: 9front

Download patch

ref: 4f6fa04fe60dde3f55e4f07589d0373e0fe841c9
parent: 882ec4ba3d42f15e630119e1f43e5400123539b5
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Sun Nov 30 17:00:03 EST 2025 

kernel: get rid of mountid and quadratic algorithms in pgrpcpy() and devproc/readns1()

Ori discovered that the 64-bit Mount.mountid was
handled incorrectly in devproc's readns1() as Chan.nrock
is 32-bit integer.

Instead of sorting the Mount entries by 64-bit mountid
using pgrpinsert(), always maintain orderd linked list in
Pgrp.mntorder.

For pgrpcpy(), we also add a Mount *norder "forward"
pointer, which we temporarily stuff new Mount's into
the original pgrp Mount's. A the end, we re-insert
all the new mounts using pgrpinsert().

Pgrpinsert() is now O(1) as it just needs to append
to the list (and we keep a tail link pointer).

Add Mhead *umh into Mount struct and devproc's readns1()
becomes trivial.

The 64-bit mountid is not needed anymore, so remove
as well as the nextmount() generator.


--- a/sys/src/9/port/chan.c
+++ b/sys/src/9/port/chan.c
@@ -742,11 +742,18 @@
 				putmhead(m);
 				nexterror();
 			}
-			m->mount = newmount(old, 0, nil);
+			f = newmount(old, 0, nil);
+			f->umh = m;
+			m->mount = f;
+			pgrpinsert(pg, f);
 			poperror();
 		}
 		*l = m;
 	}
+	for(f = nm; f != nil; f = f->next){
+		f->umh = m;
+		pgrpinsert(pg, f);
+	}
 	wlock(&m->lock);
 	um = m->mount;
 	if(um != nil && order == MAFTER){
@@ -764,6 +771,8 @@
 		m->mount = nm;
 	}
 	wunlock(&m->lock);
+	for(f = um; f != nil; f = f->next)
+		pgrpremove(pg, f);
 	wunlock(&pg->ns);
 	poperror();
 
@@ -807,10 +816,12 @@
 	}
 
 	wlock(&m->lock);
-	f = m->mount;
 	if(mounted == nil){
-		*l = m->hash;
+		for(f = m->mount; f != nil; f = f->next)
+			pgrpremove(pg, f);
+		f = m->mount;
 		m->mount = nil;
+		*l = m->hash;
 		wunlock(&m->lock);
 		wunlock(&pg->ns);
 		mountfree(f);
@@ -817,9 +828,11 @@
 		putmhead(m);
 		return;
 	}
-	for(p = &m->mount; f != nil; f = f->next){
+	p = &m->mount;
+	for(f = m->mount; f != nil; f = f->next){
 		if(eqchan(f->to, mounted, 1) ||
 		  (f->to->mchan != nil && eqchan(f->to->mchan, mounted, 1))){
+			pgrpremove(pg, f);
 			*p = f->next;
 			f->next = nil;
 			if(m->mount == nil){
--- a/sys/src/9/port/devproc.c
+++ b/sys/src/9/port/devproc.c
@@ -642,9 +642,7 @@
 readns1(Chan *c, Proc *p, char *buf, int nbuf)
 {
 	Pgrp *pg;
-	Mount *t, *cm;
-	Mhead *f, *mh;
-	ulong minid, bestmid;
+	Mount *f;
 	char flag[10], *srv;
 	int i;
 
@@ -652,49 +650,35 @@
 	if(pg == nil || p->dot == nil || p->pid != PID(c->qid))
 		error(Eprocdied);
 
-	bestmid = ~0;
-	minid = c->nrock;
-	if(minid == bestmid)
+	if(c->nrock < 0)
 		return 0;
 
 	rlock(&pg->ns);
 
-	mh = nil;
-	cm = nil;
-	for(i = 0; i < MNTHASH; i++) {
-		for(f = pg->mnthash[i]; f != nil; f = f->hash) {
-			rlock(&f->lock);
-			for(t = f->mount; t != nil; t = t->next) {
-				if(t->mountid >= minid && t->mountid < bestmid) {
-					bestmid = t->mountid;
-					cm = t;
-					mh = f;
-				}
-			}
-			runlock(&f->lock);
-		}
+	i = 0;
+	for(f = pg->mntorder; f != nil; f = f->order) {
+		if(i++ >= c->nrock)
+			break;
 	}
 
-	if(bestmid == ~0) {
-		c->nrock = bestmid;
+	if(f == nil) {
+		c->nrock = -1;
 		i = snprint(buf, nbuf, "cd %q\n", p->dot->path->s);
 	} else {
-		c->nrock = bestmid+1;
-
-		int2flag(cm->mflag, flag);
-		if(strcmp(cm->to->path->s, "#M") == 0){
-			srv = cm->to->mchan->srvname;
+		c->nrock = i;
+		int2flag(f->mflag, flag);
+		if(strcmp(f->to->path->s, "#M") == 0){
+			srv = f->to->mchan->srvname;
 			if(srv == nil)
-				srv = cm->to->mchan->path->s;
-			i = snprint(buf, nbuf, *cm->spec?
+				srv = f->to->mchan->path->s;
+			i = snprint(buf, nbuf, *f->spec?
 				"mount %s %q %q %q\n": "mount %s %q %q\n", flag,
-				srv, mh->from->path->s, cm->spec);
+				srv, f->umh->from->path->s, f->spec);
 		}else{
 			i = snprint(buf, nbuf, "bind %s %q %q\n", flag,
-				cm->to->path->s, mh->from->path->s);
+				f->to->path->s, f->umh->from->path->s);
 		}
 	}
-
 	runlock(&pg->ns);
 
 	return i;
--- a/sys/src/9/port/pgrp.c
+++ b/sys/src/9/port/pgrp.c
@@ -9,19 +9,6 @@
 	Whinesecs = 10,		/* frequency of out-of-resources printing */
 };
 
-uvlong
-nextmount(void)
-{
-	static uvlong next = 0;
-	static Lock lk;
-	uvlong n;
-
-	lock(&lk);
-	n = ++next;
-	unlock(&lk);
-	return n;
-}
-
 Pgrp*
 newpgrp(void)
 {
@@ -31,6 +18,7 @@
 	if(p == nil)
 		error(Enomem);
 	p->ref = 1;
+	p->mntordertail = &p->mntorder;
 	return p;
 }
 
@@ -77,41 +65,44 @@
 	free(p);
 }
 
-static void
-pgrpinsert(Mount **order, Mount *m)
+void
+pgrpinsert(Pgrp *pg, Mount *m)
 {
-	Mount *f;
-
 	m->order = nil;
-	for(f = *order; f != nil; f = f->order) {
-		if(m->mountid < f->mountid) {
-			m->order = f;
-			*order = m;
+	*pg->mntordertail = m;
+	pg->mntordertail = &m->order;
+}
+
+void
+pgrpremove(Pgrp *pg, Mount *m)
+{
+	Mount *f, **l = &pg->mntorder;
+
+	for(f = pg->mntorder; f != nil; f = f->order) {
+		if(f == m){
+			if((*l = f->order) == nil)
+				pg->mntordertail = l;
+			f->order = nil;
 			return;
 		}
-		order = &f->order;
+		l = &f->order;
 	}
-	*order = m;
 }
 
-/*
- * pgrpcpy MUST preserve the mountid allocation order of the parent group
- */
 void
 pgrpcpy(Pgrp *to, Pgrp *from)
 {
-	Mount *n, *m, **link, *order;
+	Mount *n, *m, **link;
 	Mhead *f, **l, *mh;
 	int i;
 
 	wlock(&to->ns);
-	rlock(&from->ns);
+	wlock(&from->ns);	/* must wlock to protect from->mntorder->norder */
 	if(waserror()){
-		runlock(&from->ns);
+		wunlock(&from->ns);
 		wunlock(&to->ns);
 		nexterror();
 	}
-	order = nil;
 	for(i = 0; i < MNTHASH; i++) {
 		l = &to->mnthash[i];
 		for(f = from->mnthash[i]; f != nil; f = f->hash) {
@@ -125,28 +116,23 @@
 			l = &mh->hash;
 			link = &mh->mount;
 			for(m = f->mount; m != nil; m = m->next) {
-				n = malloc(sizeof(Mount)+strlen(m->spec)+1);
-				if(n == nil)
-					error(Enomem);
-				n->mountid = m->mountid;
-				n->mflag = m->mflag;
-				n->to = m->to;
-				incref(n->to);
-				strcpy(n->spec, m->spec);
-				pgrpinsert(&order, n);
+				n = newmount(m->to, m->mflag, m->spec);
+				n->umh = mh;
 				*link = n;
 				link = &n->next;
+				m->norder = n;	/* for from->mntorder loop below */
 			}
 			runlock(&f->lock);
 			poperror();
 		}
 	}
-	/*
-	 * Allocate mount ids in the same sequence as the parent group
-	 */
-	for(m = order; m != nil; m = m->order)
-		m->mountid = nextmount();
-	runlock(&from->ns);
+	/* add mounts in original mntorder */
+	for(m = from->mntorder; m != nil; m = m->order){
+		n = m->norder;
+		m->norder = nil;
+		pgrpinsert(to, n);
+	}
+	wunlock(&from->ns);
 	wunlock(&to->ns);
 	poperror();
 }
@@ -272,7 +258,6 @@
 		error(Enomem);
 	m->to = to;
 	incref(to);
-	m->mountid = nextmount();
 	m->mflag = flag;
 	strcpy(m->spec, spec);
 	setmalloctag(m, getcallerpc(&to));
--- a/sys/src/9/port/portdat.h
+++ b/sys/src/9/port/portdat.h
@@ -260,11 +260,12 @@
 
 struct Mount
 {
-	uvlong	mountid;
-	int	mflag;
-	Mount*	next;
-	Mount*	order;
+	Mount*	order;			/* Pgrp.mntorder chain */
+	Mount*	norder;			/* forward pointer for pgrpcpy() */
+	Mount*	next;			/* Mhead.mount chain */
+	Mhead*	umh;			/* the union we belong to */ 
 	Chan*	to;			/* channel replacing channel */
+	int	mflag;
 	char	spec[];
 };
 
@@ -281,10 +282,9 @@
 {
 	Rendez;
 
-	ulong	vers;
-
 	vlong	off;
 	vlong	seq;
+	ulong	vers;
 
 	uint	i;
 	Mntrpc	*r[8];
@@ -513,6 +513,8 @@
 	Ref;
 	RWLock	ns;			/* Namespace n read/one write lock */
 	u64int	notallowed[4];		/* Room for 256 devices */
+	Mount	*mntorder;		/* Ordered list of mounts */
+	Mount	**mntordertail;
 	Mhead	*mnthash[MNTHASH];
 };
 
--- a/sys/src/9/port/portfns.h
+++ b/sys/src/9/port/portfns.h
@@ -245,6 +245,8 @@
 ulong		perfticks(void);
 _Noreturn void	pexit(char*, int);
 void		pgrpcpy(Pgrp*, Pgrp*);
+void		pgrpinsert(Pgrp*, Mount *);
+void		pgrpremove(Pgrp*, Mount *);
 ulong		pidalloc(Proc*);
 #define		waserror()		setlabel(&up->errlab[up->nerrlab++])
 #define		poperror()		up->nerrlab--
-- 
⑨