reverting semaphore lock changes from sources (r41ccd6d221da, rb28756e5ba29)

semaphore locks have much higher overhead than initially presented
in the "Semaphores in Plan9" paper. until the reason for it has been
found out i will revert the changes.

20 files changed, 280 insertions, 191 deletions

diff --git a/sys/src/libc/port/cycles.c b/sys/src/libc/68000/cycles.c
index 9bad3a989..9bad3a989 100644
--- a/sys/src/libc/port/cycles.c
+++ b/sys/src/libc/68000/cycles.c
diff --git a/sys/src/libc/68000/mkfile b/sys/src/libc/68000/mkfile
index cb049b6b0..573d49268 100644
--- a/sys/src/libc/68000/mkfile
+++ b/sys/src/libc/68000/mkfile
@@ -24,6 +24,7 @@ SFILES=\
 	strlen.s\
 
 CFILES=\
+	cycles.c\
 	notejmp.c\
 	vlrt.c\
 
diff --git a/sys/src/libc/68020/lock.c b/sys/src/libc/68020/lock.c
deleted file mode 100644
index c0966fcac..000000000
--- a/sys/src/libc/68020/lock.c
+++ /dev/null
@@ -1,41 +0,0 @@
-#include <u.h>
-#include <libc.h>
-
-void
-lock(Lock *lk)
-{
-	int i;
-
-	/* once fast */
-	if(!_tas((int*)&lk->key))
-		return;
-	/* a thousand times pretty fast */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(0);
-	}
-	/* now nice and slow */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(100);
-	}
-	/* take your time */
-	while(_tas((int*)&lk->key))
-		sleep(1000);
-}
-
-int
-canlock(Lock *lk)
-{
-	if(_tas((int*)&lk->key))
-		return 0;
-	return 1;
-}
-
-void
-unlock(Lock *lk)
-{
-	lk->key = 0;
-}
diff --git a/sys/src/libc/68020/mkfile b/sys/src/libc/68020/mkfile
index d486d74f7..bdd359164 100644
--- a/sys/src/libc/68020/mkfile
+++ b/sys/src/libc/68020/mkfile
@@ -26,7 +26,7 @@ SFILES=\
 	vlop.s\
 
 CFILES=\
-	lock.c\
+	cycles.c\
 	notejmp.c\
 	vlrt.c\
 
diff --git a/sys/src/libc/alpha/cycles.c b/sys/src/libc/alpha/cycles.c
new file mode 100644
index 000000000..9bad3a989
--- /dev/null
+++ b/sys/src/libc/alpha/cycles.c
@@ -0,0 +1,7 @@
+#include <u.h>
+#include <libc.h>
+
+void	cycles(uvlong*u)
+{
+	*u = 0LL;
+}
diff --git a/sys/src/libc/alpha/lock.c b/sys/src/libc/alpha/lock.c
deleted file mode 100644
index c0966fcac..000000000
--- a/sys/src/libc/alpha/lock.c
+++ /dev/null
@@ -1,41 +0,0 @@
-#include <u.h>
-#include <libc.h>
-
-void
-lock(Lock *lk)
-{
-	int i;
-
-	/* once fast */
-	if(!_tas((int*)&lk->key))
-		return;
-	/* a thousand times pretty fast */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(0);
-	}
-	/* now nice and slow */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(100);
-	}
-	/* take your time */
-	while(_tas((int*)&lk->key))
-		sleep(1000);
-}
-
-int
-canlock(Lock *lk)
-{
-	if(_tas((int*)&lk->key))
-		return 0;
-	return 1;
-}
-
-void
-unlock(Lock *lk)
-{
-	lk->key = 0;
-}
diff --git a/sys/src/libc/alpha/mkfile b/sys/src/libc/alpha/mkfile
index 299a97c97..ef66ac423 100644
--- a/sys/src/libc/alpha/mkfile
+++ b/sys/src/libc/alpha/mkfile
@@ -18,7 +18,7 @@ SFILES=\
 
 CFILES=\
 	_seek.c\
-	lock.c\
+	cycles.c\
 	notejmp.c\
 
 HFILES=/sys/include/libc.h
diff --git a/sys/src/libc/arm/cycles.c b/sys/src/libc/arm/cycles.c
new file mode 100644
index 000000000..d03e827ce
--- /dev/null
+++ b/sys/src/libc/arm/cycles.c
@@ -0,0 +1,10 @@
+#include <u.h>
+#include <libc.h>
+
+#pragma profile off
+
+void
+cycles(uvlong*u)
+{
+	*u = 0LL;
+}
diff --git a/sys/src/libc/arm/mkfile b/sys/src/libc/arm/mkfile
index 768bcdd46..14f81e1b8 100644
--- a/sys/src/libc/arm/mkfile
+++ b/sys/src/libc/arm/mkfile
@@ -20,6 +20,7 @@ SFILES=\
 	vlop.s\
 
 CFILES=\
+	cycles.c\
 	notejmp.c\
 	vlrt.c\
 
diff --git a/sys/src/libc/mips/atom.s b/sys/src/libc/mips/atom.s
index b907f7f59..8975ac569 100644
--- a/sys/src/libc/mips/atom.s
+++ b/sys/src/libc/mips/atom.s
@@ -12,8 +12,7 @@ TEXT _xinc(SB), 1, $-4			/* void _xinc(long *); */
 loop:	MOVW	$1, R3
 	LL(2, 1)
 	NOOP
-	ADDU	R1, R3
-	MOVW	R3, R1			/* return new value */
+	ADD	R1,R3,R3
 	SC(2, 3)
 	NOOP
 	BEQ	R3,loop
@@ -25,8 +24,8 @@ TEXT _xdec(SB), 1, $-4			/* long _xdec(long *); */
 loop1:	MOVW	$-1, R3
 	LL(2, 1)
 	NOOP
-	ADDU	R1, R3
-	MOVW	R3, R1			/* return new value */
+	ADD	R1,R3,R3
+	MOVW	R3, R1
 	SC(2, 3)
 	NOOP
 	BEQ	R3,loop1
@@ -50,3 +49,9 @@ spincas:
 fail:
 	MOVW	$0, R1
 	RET
+
+/* general-purpose abort */
+_trap:
+	MOVD	$0, R0
+	MOVD	0(R0), R0
+	RET
diff --git a/sys/src/libc/mips/lock.c b/sys/src/libc/mips/lock.c
new file mode 100644
index 000000000..9c9bd2208
--- /dev/null
+++ b/sys/src/libc/mips/lock.c
@@ -0,0 +1,171 @@
+#include <u.h>
+#include <libc.h>
+
+enum
+{
+	Pagesize	= 4096,
+	Semperpg	= Pagesize/(16*sizeof(uint)),
+	Lockaddr	= 0x60000000,
+
+	POWER		= 0x320,
+	MAGNUM		= 0x330,
+	MAGNUMII	= 0x340,
+	R4K		= 0x500,
+};
+
+static	int arch;
+extern	int C_3ktas(int*);
+extern	int C_4ktas(int*);
+extern	int C_fcr0(void);
+
+static void
+lockinit(void)
+{
+	void *v;
+
+	if(arch != 0)
+		return;	/* allow multiple calls */
+	arch = C_fcr0();
+	switch(arch) {
+	case POWER:
+		v = (void*)Lockaddr;
+		if(segattach(SG_CEXEC, "lock", v, Pagesize) == (void*)-1) {
+			arch = MAGNUM;
+			break;
+		}
+		memset(v, 0, Pagesize);
+		break;
+	case MAGNUM:
+	case MAGNUMII:
+	case R4K:
+		break;
+	default:
+		arch = R4K;
+		break;
+	}
+}
+
+void
+lock(Lock *lk)
+{
+	int *hwsem;
+	int hash;
+
+retry:
+	switch(arch) {
+	case 0:
+		lockinit();
+		goto retry;
+	case MAGNUM:
+	case MAGNUMII:
+		while(C_3ktas(&lk->val))
+			sleep(0);
+		return;
+	case R4K:
+		for(;;){
+			while(lk->val)
+				;
+			if(C_4ktas(&lk->val) == 0)
+				return;
+		}
+		break;
+	case POWER:
+		/* Use low order lock bits to generate hash */
+		hash = ((int)lk/sizeof(int)) & (Semperpg-1);
+		hwsem = (int*)Lockaddr+hash;
+
+		for(;;) {
+			if((*hwsem & 1) == 0) {
+				if(lk->val)
+					*hwsem = 0;
+				else {
+					lk->val = 1;
+					*hwsem = 0;
+					return;
+				}
+			}
+			while(lk->val)
+				;
+		}
+	}
+}
+
+int
+canlock(Lock *lk)
+{
+	int *hwsem;
+	int hash;
+
+retry:
+	switch(arch) {
+	case 0:
+		lockinit();
+		goto retry;
+	case MAGNUM:
+	case MAGNUMII:
+		if(C_3ktas(&lk->val))
+			return 0;
+		return 1;
+	case R4K:
+		if(C_4ktas(&lk->val))
+			return 0;
+		return 1;
+	case POWER:
+		/* Use low order lock bits to generate hash */
+		hash = ((int)lk/sizeof(int)) & (Semperpg-1);
+		hwsem = (int*)Lockaddr+hash;
+
+		if((*hwsem & 1) == 0) {
+			if(lk->val)
+				*hwsem = 0;
+			else {
+				lk->val = 1;
+				*hwsem = 0;
+				return 1;
+			}
+		}
+		break;
+	}
+	return 0;
+}
+
+void
+unlock(Lock *lk)
+{
+	lk->val = 0;
+}
+
+int
+_tas(int *p)
+{
+	int *hwsem;
+	int hash;
+
+retry:
+	switch(arch) {
+	case 0:
+		lockinit();
+		goto retry;
+	case MAGNUM:
+	case MAGNUMII:
+		return C_3ktas(p);
+	case R4K:
+		return C_4ktas(p);
+	case POWER:
+		/* Use low order lock bits to generate hash */
+		hash = ((int)p/sizeof(int)) & (Semperpg-1);
+		hwsem = (int*)Lockaddr+hash;
+
+		if((*hwsem & 1) == 0) {
+			if(*p)
+				*hwsem = 0;
+			else {
+				*p = 1;
+				*hwsem = 0;
+				return 0;
+			}
+		}
+		break;
+	}
+	return 1;
+}
diff --git a/sys/src/libc/mips/mkfile b/sys/src/libc/mips/mkfile
index 460f7cd2f..3b902f6e3 100644
--- a/sys/src/libc/mips/mkfile
+++ b/sys/src/libc/mips/mkfile
@@ -23,6 +23,7 @@ SFILES=\
 
 CFILES=\
 	cycles.c\
+	lock.c\
 	notejmp.c\
 	sqrt.c\
 	vlrt.c\
diff --git a/sys/src/libc/mips/tas.s b/sys/src/libc/mips/tas.s
index a9bf40721..d754b21f6 100644
--- a/sys/src/libc/mips/tas.s
+++ b/sys/src/libc/mips/tas.s
@@ -17,7 +17,6 @@ btas:
 	BLTZ	R1, btas
 	RET
 
-	TEXT	_tas(SB),$0
 	TEXT	C_4ktas(SB), $0
 	MOVW	R1, R2		/* address of key */
 tas1:
diff --git a/sys/src/libc/mkfile b/sys/src/libc/mkfile
index 8f1593cc1..3634076f8 100644
--- a/sys/src/libc/mkfile
+++ b/sys/src/libc/mkfile
@@ -37,7 +37,7 @@ update:V:
 		cd $i
 		mk $MKFLAGS update
 	}
-	update $UPDATEFLAGS /$objtype/lib/libc.a
+	update $UPDATEFLAGS /386/lib/libc.a
 
 installall:V:
 	for(objtype in $CPUS) mk $MKFLAGS install
diff --git a/sys/src/libc/port/lock.c b/sys/src/libc/port/lock.c
index 213fcd778..af07b9cc7 100644
--- a/sys/src/libc/port/lock.c
+++ b/sys/src/libc/port/lock.c
@@ -2,32 +2,40 @@
 #include <libc.h>
 
 void
-lock(Lock *l)
+lock(Lock *lk)
 {
-	if(ainc(&l->key) == 1)
-		return;	/* changed from 0 -> 1: we hold lock */
-	/* otherwise wait in kernel */
-	while(semacquire(&l->sem, 1) < 0){
-		/* interrupted; try again */
+	int i;
+
+	/* once fast */
+	if(!_tas(&lk->val))
+		return;
+	/* a thousand times pretty fast */
+	for(i=0; i<1000; i++){
+		if(!_tas(&lk->val))
+			return;
+		sleep(0);
+	}
+	/* now nice and slow */
+	for(i=0; i<1000; i++){
+		if(!_tas(&lk->val))
+			return;
+		sleep(100);
 	}
+	/* take your time */
+	while(_tas(&lk->val))
+		sleep(1000);
 }
 
-void
-unlock(Lock *l)
+int
+canlock(Lock *lk)
 {
-	if(adec(&l->key) == 0)
-		return;	/* changed from 1 -> 0: no contention */
-	semrelease(&l->sem, 1);
+	if(_tas(&lk->val))
+		return 0;
+	return 1;
 }
 
-int
-canlock(Lock *l)
+void
+unlock(Lock *lk)
 {
-	if(ainc(&l->key) == 1)
-		return 1;	/* changed from 0 -> 1: success */
-	/* Undo increment (but don't miss wakeup) */
-	if(adec(&l->key) == 0)
-		return 0;	/* changed from 1 -> 0: no contention */
-	semrelease(&l->sem, 1);
-	return 0;
+	lk->val = 0;
 }
diff --git a/sys/src/libc/port/malloc.acid b/sys/src/libc/port/malloc.acid
index 5e7519ad4..ac3ca3a9e 100644
--- a/sys/src/libc/port/malloc.acid
+++ b/sys/src/libc/port/malloc.acid
@@ -122,18 +122,16 @@ Profuser = 1;
 Profkernel = 2;
 Proftime = 3;
 Profsample = 4;
-sizeofLock = 8;
+sizeofLock = 4;
 aggr Lock
 {
-	'D' 0 key;
-	'D' 4 sem;
+	'D' 0 val;
 };
 
 defn
 Lock(addr) {
 	complex Lock addr;
-	print("	key	", addr.key, "\n");
-	print("	sem	", addr.sem, "\n");
+	print("	val	", addr.val, "\n");
 };
 
 sizeofQLp = 12;
@@ -152,13 +150,13 @@ QLp(addr) {
 	print("	state	", addr.state, "\n");
 };
 
-sizeofQLock = 20;
+sizeofQLock = 16;
 aggr QLock
 {
 	Lock 0 lock;
-	'D' 8 locked;
-	'A' QLp 12 $head;
-	'A' QLp 16 $tail;
+	'D' 4 locked;
+	'A' QLp 8 $head;
+	'A' QLp 12 $tail;
 };
 
 defn
@@ -172,14 +170,14 @@ QLock(addr) {
 	print("	$tail	", addr.$tail\X, "\n");
 };
 
-sizeofRWLock = 24;
+sizeofRWLock = 20;
 aggr RWLock
 {
 	Lock 0 lock;
-	'D' 8 readers;
-	'D' 12 writer;
-	'A' QLp 16 $head;
-	'A' QLp 20 $tail;
+	'D' 4 readers;
+	'D' 8 writer;
+	'A' QLp 12 $head;
+	'A' QLp 16 $tail;
 };
 
 defn
@@ -440,12 +438,12 @@ Tos(addr) {
 };
 
 complex Tos _tos;
-sizeofPrivate = 16;
+sizeofPrivate = 12;
 aggr Private
 {
 	Lock 0 lk;
-	'D' 8 pid;
-	'D' 12 printfd;
+	'D' 4 pid;
+	'D' 8 printfd;
 };
 
 defn
diff --git a/sys/src/libc/port/mkfile b/sys/src/libc/port/mkfile
index 6d1f1c583..dc2d93694 100644
--- a/sys/src/libc/port/mkfile
+++ b/sys/src/libc/port/mkfile
@@ -19,7 +19,6 @@ CFILES=\
 	cleanname.c\
 	crypt.c\
 	ctype.c\
-	cycles.c\
 	encodefmt.c\
 	execl.c\
 	exp.c\
diff --git a/sys/src/libc/port/pool.acid b/sys/src/libc/port/pool.acid
index d4bed5ef7..2ec6f99af 100644
--- a/sys/src/libc/port/pool.acid
+++ b/sys/src/libc/port/pool.acid
@@ -122,18 +122,16 @@ Profuser = 1;
 Profkernel = 2;
 Proftime = 3;
 Profsample = 4;
-sizeofLock = 8;
+sizeofLock = 4;
 aggr Lock
 {
-	'D' 0 key;
-	'D' 4 sem;
+	'D' 0 val;
 };
 
 defn
 Lock(addr) {
 	complex Lock addr;
-	print("	key	", addr.key, "\n");
-	print("	sem	", addr.sem, "\n");
+	print("	val	", addr.val, "\n");
 };
 
 sizeofQLp = 12;
@@ -152,13 +150,13 @@ QLp(addr) {
 	print("	state	", addr.state, "\n");
 };
 
-sizeofQLock = 20;
+sizeofQLock = 16;
 aggr QLock
 {
 	Lock 0 lock;
-	'D' 8 locked;
-	'A' QLp 12 $head;
-	'A' QLp 16 $tail;
+	'D' 4 locked;
+	'A' QLp 8 $head;
+	'A' QLp 12 $tail;
 };
 
 defn
@@ -172,14 +170,14 @@ QLock(addr) {
 	print("	$tail	", addr.$tail\X, "\n");
 };
 
-sizeofRWLock = 24;
+sizeofRWLock = 20;
 aggr RWLock
 {
 	Lock 0 lock;
-	'D' 8 readers;
-	'D' 12 writer;
-	'A' QLp 16 $head;
-	'A' QLp 20 $tail;
+	'D' 4 readers;
+	'D' 8 writer;
+	'A' QLp 12 $head;
+	'A' QLp 16 $tail;
 };
 
 defn
@@ -506,20 +504,34 @@ MINBLOCKSIZE = 32;
 complex Free checklist:t;
 complex Free checklist:q;
 complex Free checktree:t;
+complex Free ltreewalk:t;
+complex Free ltreewalk:f;
+complex Free treeinsert:tree;
+complex Free treeinsert:node;
+complex Free treeinsert:loc;
+complex Free treeinsert:repl;
+complex Free treedelete:tree;
+complex Free treedelete:node;
+complex Free treedelete:loc;
+complex Free treedelete:lsucc;
+complex Free treedelete:succ;
 complex Free treelookupgt:t;
 complex Free treelookupgt:lastgood;
-complex Free treesplay:t;
-complex Free treesplay:N;
-complex Free treesplay:l;
-complex Free treesplay:r;
-complex Free treesplay:y;
+complex Free listadd:list;
+complex Free listadd:node;
+complex Free listdelete:list;
+complex Free listdelete:node;
 complex Pool pooladd:p;
 complex Alloc pooladd:anode;
+complex Free pooladd:lst;
+complex Free pooladd:olst;
 complex Free pooladd:node;
-complex Free pooladd:root;
+complex Free pooladd:parent;
 complex Pool pooldel:p;
 complex Free pooldel:node;
-complex Free pooldel:root;
+complex Free pooldel:lst;
+complex Free pooldel:olst;
+complex Free pooldel:parent;
 complex Pool dsize2bsize:p;
 complex Pool bsize2asize:p;
 complex Pool blockmerge:pool;
diff --git a/sys/src/libc/sparc/lock.c b/sys/src/libc/sparc/lock.c
deleted file mode 100644
index c0966fcac..000000000
--- a/sys/src/libc/sparc/lock.c
+++ /dev/null
@@ -1,41 +0,0 @@
-#include <u.h>
-#include <libc.h>
-
-void
-lock(Lock *lk)
-{
-	int i;
-
-	/* once fast */
-	if(!_tas((int*)&lk->key))
-		return;
-	/* a thousand times pretty fast */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(0);
-	}
-	/* now nice and slow */
-	for(i=0; i<1000; i++){
-		if(!_tas((int*)&lk->key))
-			return;
-		sleep(100);
-	}
-	/* take your time */
-	while(_tas((int*)&lk->key))
-		sleep(1000);
-}
-
-int
-canlock(Lock *lk)
-{
-	if(_tas((int*)&lk->key))
-		return 0;
-	return 1;
-}
-
-void
-unlock(Lock *lk)
-{
-	lk->key = 0;
-}
diff --git a/sys/src/libc/sparc/mkfile b/sys/src/libc/sparc/mkfile
index 6ef2cf55c..af2b18944 100644
--- a/sys/src/libc/sparc/mkfile
+++ b/sys/src/libc/sparc/mkfile
@@ -22,7 +22,7 @@ SFILES=\
 	vlop.s
 
 CFILES=\
-	lock.c\
+	cycles.c\
 	notejmp.c\
 	sqrt.c\
 	vlrt.c\