From owner-freebsd-hackers  Tue Jul  2 06:50:42 1996
Return-Path: owner-hackers
Received: (from root@localhost)
          by freefall.freebsd.org (8.7.5/8.7.3) id GAA08789
          for hackers-outgoing; Tue, 2 Jul 1996 06:50:42 -0700 (PDT)
Received: from terra.Sarnoff.COM (terra.sarnoff.com [130.33.11.203])
          by freefall.freebsd.org (8.7.5/8.7.3) with SMTP id GAA08784
          for <hackers@freebsd.org>; Tue, 2 Jul 1996 06:50:38 -0700 (PDT)
Received: (from rminnich@localhost) by terra.Sarnoff.COM (8.6.12/8.6.12) id JAA10688; Tue, 2 Jul 1996 09:50:02 -0400
Date: Tue, 2 Jul 1996 09:50:01 -0400 (EDT)
From: "Ron G. Minnich" <rminnich@Sarnoff.COM>
X-Sender: rminnich@terra
To: hackers@freebsd.org
Subject: OK, here goes fastlock:
In-Reply-To: <199607020516.BAA01761@kropotkin.gnu.ai.mit.edu>
Message-ID: <Pine.SUN.3.91.960702091646.10486A-100000@terra>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-hackers@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

Here's a simple test-and-set function for the 386 (tested and works):

int
tset(int *i, int lockval, int unlockval)
{
  int j = 0;
        asm("movl 16(%ebp), %eax");
        asm("movl 8(%ebp),%ecx");
        asm("movl 12(%ebp),%edx");
        asm("cmpxchg %edx, (%ecx)");
        asm("jne failed");
        asm("movl %eax, -4(%ebp)");
        asm("jmp done");
        asm("failed: movl %eax, -4(%ebp)");
        asm("done:");
  return j;
}

This will run a bit faster than a file lock system call :-). But what about 
contention? notice that this function, if it fails, fails. so we need a 
retry strategy. IF you fail, should you spin forever? NO! Do that, and 
you eat the processor doing nothing. You ought to have a reasonable way 
to, say, spin one or two more times, then go to a more heavyweight sleep. 

SO: here's the fastlock library call (#ifdef USEMOD is for LKM )

void
fastlock(int *address, int lockval, int unlockval)
{
        int testval;
#ifdef USEMOD
	static int syscallnum = -1;
        if (syscallnum < 0)
                syscallnum = syscallfind("fastlock");
        if (syscallnum < 0) {
                perror("fastlock syscallfind");
                return;
        }
#endif

  testval = tset(address, lockval, unlockval);
  if (testval == unlockval) {
#ifdef FASTLOCKDEBUG
        printf("(%d)fastlock quickout\n", getpid());
#endif
        return;
  }
  /* attempt to lock failed. test then wait in kernel sleep() */
  while (1)
    {
      /* set the high-order bit. This tells the unlocker to do the system
       * call and free up the lock.
       */
      (void) tset(address, testval|0x80000000,testval);
#ifdef FASTLOCKDEBUG
      printf("(%d)hang in there\n", getpid());
#endif
      /* we should be checking here to make sure that high-order bit is 
       * set. But this second tset fails only 
       * in the event of contention, in which case 
       * someone else has set the high-order
       * bit too ... seems pointless, esp. given that fastlock has a timeout
       */
      syscall(syscallnum, 1, address, unlockval);
      testval = tset(address, lockval, unlockval);
      if (testval == unlockval)
        return;
    }
  
}

So what are we doing? We're doing the tset. If it fails, then we do one 
more tset, to set the high order bit, then drop into the fastlock system 
call. Once we return from that, we try to tset the variable again. If 
that fails, we drop once again into the system call. 

Here's fastunlock: 
void
fastunlock(int *address, int unlockval)
{
  int dosyscall = 0;
  static int syscallnum = -1; /* this is really in the file */
#ifdef USEMOD
        if (syscallnum < 0)
                syscallnum = syscallfind("fastlock");
        if (syscallnum < 0) {
                perror("fastunlock syscallfind");
                return;
        }
#endif
  if (*address & 0x80000000)
    dosyscall = 1;
  *address = unlockval;
#ifdef FASTLOCKDEBUG
  printf("(%d)fastunlock dosyscall is %d\n", getpid(), dosyscall);
  if (dosyscall) printf("conflict %d\n", getpid());
  fflush(stdout);
#endif
  if (dosyscall)
    syscall(syscallnum, 0, address, unlockval);
}

Ok, this one tests to see if it needs to wake any sleepers, clears the 
memory variable, then drops into the kernel if needed (if (dosyscall) ...)

Here's the system call. Note several things: 
1) the definition of 'unlocked' is passed in to the system call for the 
final test, not assumed to be zero. 
2) The 'address' argument does NOT NEED TO BE AN ADDRESS. it's a number
   that all the procs have to agree on, that is all.
3) if you accidently awake more than one sleeper, the loop in fastlock
   handles that properly
4) This system call handles both waking up and sleeping
5) For my measurements, this thing is a whole lot faster than anything
   else available on (e.g.) freebsd. Questions to me. 

int
fastlock(p, uap, retval)
        struct proc *p;
        struct flu *uap;
        int retval[];
{
        extern int hz;
        retval[0] = 0;
/*
        printf("fastlockunlock: com %d address 0x%x unlocked %d\n",
                uap->com, uap->address, uap->unlocked);
 */
        if (uap->com == 0) /* unlock */
                wakeup((void *) uap->address);
        else
                {
                        /* last chance */
			/* try one last time to see if it is unlocked */
                        int curval = fuword((void *) uap->address);
                        if (curval == uap->unlocked)
                                return;
                        tsleep((void *) uap->address, PUSER, NULL, 10*hz);
                }
        return 0;
}



Ron Minnich                |"Inferno runs on MIPS ..., Intel ..., and AMD's
rminnich@sarnoff.com       |29-kilobit-per-second chip-based architectures ..."
(609)-734-3120             |  Comm. week, may 13, pg. 4. 
ftp://ftp.sarnoff.com/pub/mnfs/www/docs/cluster.html