Hi,

It seems that the Linux kernel will very shortly acquire a lightweight
userlevel locking primitive (called futexes), thanks primarily to Rusty
and Hubertus.  It looks to be very useful for the sort of locking that
databases of various types need to do.

They have a bunch of rather nice properties:

a) low overhead in the no-contention case - a single locked
   instruction on i386
b) no kernel overhead for non-contended locks - make as
   many as you like, the kernel memory cost is only
   O(number of locks with waiters)
c) are interruptible / restartable across signals
d) the name :-)

They don't do:

a) deadlock detection
b) cleanup on process exit -- the kernel doesn't know who
   had the lock, so it can't help here

A reader/writer version is available, though it's currently implemented
with two futexes.  Spin-for-a-while-before-sleeping versions are planned.

The API looks like this:

	/* these can be stored anywhere -- mmapped file,
	 * sysv shm, shared anonymous memory */
	struct futex lock;

	/* this does mprotect(.., ...|PROT_SEM, ...);
	 * seemingly some architectures need to do odd
	 * things to get atomic/coherent memory */
	if(futex_region(lock, sizeof(lock)))
		fail("futexes not available on this kernel");

	futex_init(&lock);

	...

	/* grab the lock -- we also have a futex_trydown */
	if(futex_down(&lock))
		fail("couldn't get lock");

	/* critical section */

	/* release lock */
	futex_up(&lock);


We're looking for interesting applications to try this stuff out on.
Are there:

a) parts of postgresql which would like this, or
b) changes to the interface (or feature set) which
   would make it more suited

?

The LWLocks look not unlike this, but my impression is that they are
low-contention, so any improvement would be small.

Any pointers into appropriate bits of source would be greatly appreciated.

Thanks,

Matthew.


Tue, 12 Mar 2002 21:25:12 +0000 (GMT)
Matthew Kirkwood <matthew@hairy.beasts.org>
Lightweight locking primitive
Matthew Kirkwood wrote:
> 
> Hi,
> 
> It seems that the Linux kernel will very shortly acquire a lightweight
> userlevel locking primitive (called futexes), thanks primarily to Rusty
> and Hubertus.  It looks to be very useful for the sort of locking that
> databases of various types need to do.
> 
> They have a bunch of rather nice properties:

I am curious how 'futexes' are different/better than POSIX (pthread
style) mutexes?

> 
> a) low overhead in the no-contention case - a single locked
>    instruction on i386

should be same for pthread_mutex_lock()

> b) no kernel overhead for non-contended locks - make as
>    many as you like, the kernel memory cost is only
>    O(number of locks with waiters)

Well it can't have kernel overhead for non-contended locks if a
non-contended lock is one opcode, can it?

> c) are interruptible / restartable across signals

Not sure what 'restartable' means? Do you mean locking primitives would
restarted by kernel when interrupted by signals? Like kernel calls with
SA_RESTART set? How that would be possible if kernel does not even know
about non-contended locks?

> d) the name :-)
> 
> They don't do:
> 
> a) deadlock detection
> b) cleanup on process exit -- the kernel doesn't know who
>    had the lock, so it can't help here
> 
> A reader/writer version is available, though it's currently implemented
> with two futexes.  Spin-for-a-while-before-sleeping versions are planned.
> 

RW locks are defined by POSIX too and can be implemented by mutex +
condvar. I wonder what is wrong with those... At the same time Linux has
POSIX semaphores which can not be shared across processes, making them
quite useless. Fixing that could help postgres quite a bit more I
think...

-- igor

Tue, 12 Mar 2002 15:48:23 -0600
Igor Kovalenko <Igor.Kovalenko@motorola.com>
Re: Lightweight locking primitive
Igor Kovalenko <Igor.Kovalenko@motorola.com> writes:

> Matthew Kirkwood wrote:
> > 
> > Hi,
> > 
> > It seems that the Linux kernel will very shortly acquire a lightweight
> > userlevel locking primitive (called futexes), thanks primarily to Rusty
> > and Hubertus.  It looks to be very useful for the sort of locking that
> > databases of various types need to do.
> > 
> > They have a bunch of rather nice properties:
> 
> I am curious how 'futexes' are different/better than POSIX (pthread
> style) mutexes?

They're basically the same thing.  Currently, pthread_mutexes on Linux
(implemented in glibc) are fairly gross in the contended case, since
there is no clean way to wait for lock release, and they interact
fairly nastily with signal semantics.  The futex patches create a new
system call which lets you cleanly wait for a locked futex (an
unlocking task checks for waiting lockers and calls into the kernel
for wakeups if it finds any).

There's no reason that POSIX mutextes and semaphores couldn't be
implemented on top of futexes, usable both in threaded and
multiprocess shared-memory environments. 

> Not sure what 'restartable' means? Do you mean locking primitives would
> restarted by kernel when interrupted by signals? Like kernel calls with
> SA_RESTART set? How that would be possible if kernel does not even know
> about non-contended locks?

I interpret the above as meaning: contended case (blocked in
futex_wait syscall or whatever it's called) can be cleanly interrupted
and by a signal and restarted automatically.

> RW locks are defined by POSIX too and can be implemented by mutex +
> condvar. I wonder what is wrong with those...

There's no conflict between POSIX locks and futexes; the latter are
just a good, new way to implement the former.

>                                           At the same time Linux has
> POSIX semaphores which can not be shared across processes, making them
> quite useless. Fixing that could help postgres quite a bit more I
> think...

Yes, having mutexes and semaphores shareable by different processes
is one of the benefits of the new locks as I understand them.

-Doug
-- 
Doug McNaught       Wireboard Industries      http://www.wireboard.com/

      Custom software development, systems and network consulting.
      Java PostgreSQL Enhydra Python Zope Perl Apache Linux BSD...

12 Mar 2002 17:18:16 -0500
Doug McNaught <doug@wireboard.com>
Re: Lightweight locking primitive
Doug McNaught wrote:
> They're basically the same thing.  Currently, pthread_mutexes on Linux
> (implemented in glibc) are fairly gross in the contended case, since
> there is no clean way to wait for lock release, and they interact
> fairly nastily with signal semantics.  The futex patches create a new
> system call which lets you cleanly wait for a locked futex (an
> unlocking task checks for waiting lockers and calls into the kernel
> for wakeups if it finds any).

Strange that it doesn't wait for the lock.  BSD/OS has:

     The pthread_mutex_lock() function locks the mutex pointed to by mutex. If
     mutex is already locked, the calling thread will block until the mutex
     becomes available.  Upon success the pthread_mutex_lock() function re-
     turns with the mutex locked and the calling thread as its owner.

In fact, they have a pthread_mutex_trylock() version that doesn't block:

     The pthread_mutex_trylock() function performs a non-blocking mutex lock
     operation.  It behaves exactly like pthread_mutex_lock() except that if
     any thread (including the calling thread) currently owns the mutex, an
     immediate error return is performed.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Tue, 12 Mar 2002 19:08:50 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Lightweight locking primitive
On Tue, 12 Mar 2002, Bruce Momjian wrote:

> > They're basically the same thing.  Currently, pthread_mutexes on Linux
> > (implemented in glibc) are fairly gross in the contended case, since
> > there is no clean way to wait for lock release,

> Strange that it doesn't wait for the lock.
[..]

It does wait, in that the call will not return before or unless
the thread has acquired the lock.  However, it waits in an ugly
way, via spin-and-yield or some evil signal or pipe hackery via
a manager thread.

pthread_mutexes are fairly ugly, but they should still be
lightweight.  Until now, there was no way to do that under
Linux.  (I don't know how the other free Unixes do it, but I
suspect it is not much better.)

Matthew.


Wed, 13 Mar 2002 00:51:37 +0000 (GMT)
Matthew Kirkwood <matthew@hairy.beasts.org>
Re: Lightweight locking primitive
Bruce Momjian <pgman@candle.pha.pa.us> writes:

> Doug McNaught wrote:
> > They're basically the same thing.  Currently, pthread_mutexes on Linux
> > (implemented in glibc) are fairly gross in the contended case, since
> > there is no clean way to wait for lock release, and they interact
> > fairly nastily with signal semantics.  The futex patches create a new
> > system call which lets you cleanly wait for a locked futex (an
> > unlocking task checks for waiting lockers and calls into the kernel
> > for wakeups if it finds any).
> 
> Strange that it doesn't wait for the lock.  BSD/OS has:

It does wait.  If the lock is already locked (atomic test in
userspace) the process makes a futex_wait system call, which puts the
process on a kernel waitqueue. 

 From what I can see, the new Linux locks are not a replacement for
POSIX locks/semaphores, they're simply a fairly clean way of
implementing them.  They also just went into the development kernel,
so any appearance in production systems may take a few months at
least. 

-Doug
-- 
Doug McNaught       Wireboard Industries      http://www.wireboard.com/

      Custom software development, systems and network consulting.
      Java PostgreSQL Enhydra Python Zope Perl Apache Linux BSD...

12 Mar 2002 23:29:22 -0500
Doug McNaught <doug@wireboard.com>
Re: Lightweight locking primitive
Matthew Kirkwood wrote:
> 
> On Tue, 12 Mar 2002, Bruce Momjian wrote:
> 
> > > They're basically the same thing.  Currently, pthread_mutexes on Linux
> > > (implemented in glibc) are fairly gross in the contended case, since
> > > there is no clean way to wait for lock release,
> 
> > Strange that it doesn't wait for the lock.
> [..]
> 
> It does wait, in that the call will not return before or unless
> the thread has acquired the lock.  However, it waits in an ugly
> way, via spin-and-yield or some evil signal or pipe hackery via
> a manager thread.
> 
> pthread_mutexes are fairly ugly, but they should still be
> lightweight.  Until now, there was no way to do that under
> Linux.  (I don't know how the other free Unixes do it, but I
> suspect it is not much better.)

If all free Unixes do it in such an ugly way then well, what you get is
what you paid for ;) 
I still would be surprized if all implementations were as bad as Linux
one is. Pthread mutexes are very lightweight and fast on Solaris and QNX
(I mostly work with those). They can be shared across processes on both.
Implementation-wise, QNX has corresponding blocking state so when some
thread locks a mutex other contenders get blocked by kernel. They are
(one of them) unblocked by kernel when mutex is released.

Speaking about ugliness, the only issue I see with pthread mutexes is
that they can get orphaned. There is no portable way to deal with that,
but again both Solaris and QNX have extended API which allows some
thread to aqcuire ownership of an orphaned mutex. I guess that
eventually will make its way into POSIX.

-- igor

Tue, 12 Mar 2002 22:41:05 -0600
Igor Kovalenko <Igor.Kovalenko@motorola.com>
Re: Lightweight locking primitive