libc: change tas/sleep locks to cas/semacquire/semrelease locks (from sources)

spinlocks have been changed to use the new semacquire/semrelease
syscalls in combination with atomic compare and swap operations.

21 files changed, 199 insertions, 284 deletions

diff --git a/sys/include/libc.h b/sys/include/libc.h
index a92e5680d..c84acc0f5 100644
--- a/sys/include/libc.h
+++ b/sys/include/libc.h
@@ -410,11 +410,18 @@ enum {
 extern	void	prof(void (*fn)(void*), void *arg, int entries, int what);
 
 /*
+ *  atomic
+ */
+extern	long	ainc(long*);
+extern	long	adec(long*);
+
+/*
  *  synchronization
  */
 typedef
 struct Lock {
-	int	val;
+	long	key;
+	long	sem;
 } Lock;
 
 extern int	_tas(int*);
@@ -701,9 +708,6 @@ extern	char*	sysname(void);
 extern	void	werrstr(char*, ...);
 #pragma	varargck	argpos	werrstr	1
 
-extern	long	ainc(long*);
-extern	long	adec(long*);
-
 extern char *argv0;
 #define	ARGBEGIN	for((argv0||(argv0=*argv)),argv++,argc--;\
 			    argv[0] && argv[0][0]=='-' && argv[0][1];\
diff --git a/sys/src/libc/68000/mkfile b/sys/src/libc/68000/mkfile
index 573d49268..cb049b6b0 100644
--- a/sys/src/libc/68000/mkfile
+++ b/sys/src/libc/68000/mkfile
@@ -24,7 +24,6 @@ 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
new file mode 100644
index 000000000..c0966fcac
--- /dev/null
+++ b/sys/src/libc/68020/lock.c
@@ -0,0 +1,41 @@
+#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 bdd359164..d486d74f7 100644
--- a/sys/src/libc/68020/mkfile
+++ b/sys/src/libc/68020/mkfile
@@ -26,7 +26,7 @@ SFILES=\
 	vlop.s\
 
 CFILES=\
-	cycles.c\
+	lock.c\
 	notejmp.c\
 	vlrt.c\
 
diff --git a/sys/src/libc/alpha/cycles.c b/sys/src/libc/alpha/cycles.c
deleted file mode 100644
index 9bad3a989..000000000
--- a/sys/src/libc/alpha/cycles.c
+++ /dev/null
@@ -1,7 +0,0 @@
-#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
new file mode 100644
index 000000000..c0966fcac
--- /dev/null
+++ b/sys/src/libc/alpha/lock.c
@@ -0,0 +1,41 @@
+#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 ef66ac423..299a97c97 100644
--- a/sys/src/libc/alpha/mkfile
+++ b/sys/src/libc/alpha/mkfile
@@ -18,7 +18,7 @@ SFILES=\
 
 CFILES=\
 	_seek.c\
-	cycles.c\
+	lock.c\
 	notejmp.c\
 
 HFILES=/sys/include/libc.h
diff --git a/sys/src/libc/arm/cycles.c b/sys/src/libc/arm/cycles.c
deleted file mode 100644
index d03e827ce..000000000
--- a/sys/src/libc/arm/cycles.c
+++ /dev/null
@@ -1,10 +0,0 @@
-#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 14f81e1b8..768bcdd46 100644
--- a/sys/src/libc/arm/mkfile
+++ b/sys/src/libc/arm/mkfile
@@ -20,7 +20,6 @@ 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 8975ac569..b907f7f59 100644
--- a/sys/src/libc/mips/atom.s
+++ b/sys/src/libc/mips/atom.s
@@ -12,7 +12,8 @@ TEXT _xinc(SB), 1, $-4			/* void _xinc(long *); */
 loop:	MOVW	$1, R3
 	LL(2, 1)
 	NOOP
-	ADD	R1,R3,R3
+	ADDU	R1, R3
+	MOVW	R3, R1			/* return new value */
 	SC(2, 3)
 	NOOP
 	BEQ	R3,loop
@@ -24,8 +25,8 @@ TEXT _xdec(SB), 1, $-4			/* long _xdec(long *); */
 loop1:	MOVW	$-1, R3
 	LL(2, 1)
 	NOOP
-	ADD	R1,R3,R3
-	MOVW	R3, R1
+	ADDU	R1, R3
+	MOVW	R3, R1			/* return new value */
 	SC(2, 3)
 	NOOP
 	BEQ	R3,loop1
@@ -49,9 +50,3 @@ 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
deleted file mode 100644
index 9c9bd2208..000000000
--- a/sys/src/libc/mips/lock.c
+++ /dev/null
@@ -1,171 +0,0 @@
-#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 3b902f6e3..460f7cd2f 100644
--- a/sys/src/libc/mips/mkfile
+++ b/sys/src/libc/mips/mkfile
@@ -23,7 +23,6 @@ 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 d754b21f6..a9bf40721 100644
--- a/sys/src/libc/mips/tas.s
+++ b/sys/src/libc/mips/tas.s
@@ -17,6 +17,7 @@ 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 3634076f8..8f1593cc1 100644
--- a/sys/src/libc/mkfile
+++ b/sys/src/libc/mkfile
@@ -37,7 +37,7 @@ update:V:
 		cd $i
 		mk $MKFLAGS update
 	}
-	update $UPDATEFLAGS /386/lib/libc.a
+	update $UPDATEFLAGS /$objtype/lib/libc.a
 
 installall:V:
 	for(objtype in $CPUS) mk $MKFLAGS install
diff --git a/sys/src/libc/68000/cycles.c b/sys/src/libc/port/cycles.c
index 9bad3a989..9bad3a989 100644
--- a/sys/src/libc/68000/cycles.c
+++ b/sys/src/libc/port/cycles.c
diff --git a/sys/src/libc/port/lock.c b/sys/src/libc/port/lock.c
index af07b9cc7..213fcd778 100644
--- a/sys/src/libc/port/lock.c
+++ b/sys/src/libc/port/lock.c
@@ -2,40 +2,32 @@
 #include <libc.h>
 
 void
-lock(Lock *lk)
+lock(Lock *l)
 {
-	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);
+	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 */
 	}
-	/* take your time */
-	while(_tas(&lk->val))
-		sleep(1000);
 }
 
-int
-canlock(Lock *lk)
+void
+unlock(Lock *l)
 {
-	if(_tas(&lk->val))
-		return 0;
-	return 1;
+	if(adec(&l->key) == 0)
+		return;	/* changed from 1 -> 0: no contention */
+	semrelease(&l->sem, 1);
 }
 
-void
-unlock(Lock *lk)
+int
+canlock(Lock *l)
 {
-	lk->val = 0;
+	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;
 }
diff --git a/sys/src/libc/port/malloc.acid b/sys/src/libc/port/malloc.acid
index ac3ca3a9e..5e7519ad4 100644
--- a/sys/src/libc/port/malloc.acid
+++ b/sys/src/libc/port/malloc.acid
@@ -122,16 +122,18 @@ Profuser = 1;
 Profkernel = 2;
 Proftime = 3;
 Profsample = 4;
-sizeofLock = 4;
+sizeofLock = 8;
 aggr Lock
 {
-	'D' 0 val;
+	'D' 0 key;
+	'D' 4 sem;
 };
 
 defn
 Lock(addr) {
 	complex Lock addr;
-	print("	val	", addr.val, "\n");
+	print("	key	", addr.key, "\n");
+	print("	sem	", addr.sem, "\n");
 };
 
 sizeofQLp = 12;
@@ -150,13 +152,13 @@ QLp(addr) {
 	print("	state	", addr.state, "\n");
 };
 
-sizeofQLock = 16;
+sizeofQLock = 20;
 aggr QLock
 {
 	Lock 0 lock;
-	'D' 4 locked;
-	'A' QLp 8 $head;
-	'A' QLp 12 $tail;
+	'D' 8 locked;
+	'A' QLp 12 $head;
+	'A' QLp 16 $tail;
 };
 
 defn
@@ -170,14 +172,14 @@ QLock(addr) {
 	print("	$tail	", addr.$tail\X, "\n");
 };
 
-sizeofRWLock = 20;
+sizeofRWLock = 24;
 aggr RWLock
 {
 	Lock 0 lock;
-	'D' 4 readers;
-	'D' 8 writer;
-	'A' QLp 12 $head;
-	'A' QLp 16 $tail;
+	'D' 8 readers;
+	'D' 12 writer;
+	'A' QLp 16 $head;
+	'A' QLp 20 $tail;
 };
 
 defn
@@ -438,12 +440,12 @@ Tos(addr) {
 };
 
 complex Tos _tos;
-sizeofPrivate = 12;
+sizeofPrivate = 16;
 aggr Private
 {
 	Lock 0 lk;
-	'D' 4 pid;
-	'D' 8 printfd;
+	'D' 8 pid;
+	'D' 12 printfd;
 };
 
 defn
diff --git a/sys/src/libc/port/mkfile b/sys/src/libc/port/mkfile
index dc2d93694..6d1f1c583 100644
--- a/sys/src/libc/port/mkfile
+++ b/sys/src/libc/port/mkfile
@@ -19,6 +19,7 @@ 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 2ec6f99af..d4bed5ef7 100644
--- a/sys/src/libc/port/pool.acid
+++ b/sys/src/libc/port/pool.acid
@@ -122,16 +122,18 @@ Profuser = 1;
 Profkernel = 2;
 Proftime = 3;
 Profsample = 4;
-sizeofLock = 4;
+sizeofLock = 8;
 aggr Lock
 {
-	'D' 0 val;
+	'D' 0 key;
+	'D' 4 sem;
 };
 
 defn
 Lock(addr) {
 	complex Lock addr;
-	print("	val	", addr.val, "\n");
+	print("	key	", addr.key, "\n");
+	print("	sem	", addr.sem, "\n");
 };
 
 sizeofQLp = 12;
@@ -150,13 +152,13 @@ QLp(addr) {
 	print("	state	", addr.state, "\n");
 };
 
-sizeofQLock = 16;
+sizeofQLock = 20;
 aggr QLock
 {
 	Lock 0 lock;
-	'D' 4 locked;
-	'A' QLp 8 $head;
-	'A' QLp 12 $tail;
+	'D' 8 locked;
+	'A' QLp 12 $head;
+	'A' QLp 16 $tail;
 };
 
 defn
@@ -170,14 +172,14 @@ QLock(addr) {
 	print("	$tail	", addr.$tail\X, "\n");
 };
 
-sizeofRWLock = 20;
+sizeofRWLock = 24;
 aggr RWLock
 {
 	Lock 0 lock;
-	'D' 4 readers;
-	'D' 8 writer;
-	'A' QLp 12 $head;
-	'A' QLp 16 $tail;
+	'D' 8 readers;
+	'D' 12 writer;
+	'A' QLp 16 $head;
+	'A' QLp 20 $tail;
 };
 
 defn
@@ -504,34 +506,20 @@ 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 listadd:list;
-complex Free listadd:node;
-complex Free listdelete:list;
-complex Free listdelete:node;
+complex Free treesplay:t;
+complex Free treesplay:N;
+complex Free treesplay:l;
+complex Free treesplay:r;
+complex Free treesplay:y;
 complex Pool pooladd:p;
 complex Alloc pooladd:anode;
-complex Free pooladd:lst;
-complex Free pooladd:olst;
 complex Free pooladd:node;
-complex Free pooladd:parent;
+complex Free pooladd:root;
 complex Pool pooldel:p;
 complex Free pooldel:node;
-complex Free pooldel:lst;
-complex Free pooldel:olst;
-complex Free pooldel:parent;
+complex Free pooldel:root;
 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
new file mode 100644
index 000000000..c0966fcac
--- /dev/null
+++ b/sys/src/libc/sparc/lock.c
@@ -0,0 +1,41 @@
+#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 af2b18944..6ef2cf55c 100644
--- a/sys/src/libc/sparc/mkfile
+++ b/sys/src/libc/sparc/mkfile
@@ -22,7 +22,7 @@ SFILES=\
 	vlop.s
 
 CFILES=\
-	cycles.c\
+	lock.c\
 	notejmp.c\
 	sqrt.c\
 	vlrt.c\