New locking primitive for 2.5

This is a request for comment on a new locking primitive called a combilock.

The goal of this development is:

1. To allow for a better SMP scalability of semaphores used as Mutex
2. As a replacement for long held spinlocks in an preemptible kernel

The new lock uses a combination of a spinlock and a (mutex-)semaphore. You can lock it for short-term issues in a spin-lock mode:

combi_spin_lock(struct combilock *x)
combi_spin_unlock(struct combilock *x)

and for longer lasting tasks in a sleeping mode by:

combi_mutex_lock(struct combilock *x)
combi_mutex_unlock(struct combilock *x)

If a spin_lock request is blocked by a mutex_lock call, the spin_lock attempt also sleeps i.e. behaves like a semaphore.
If you gained ownership of the lock, you can switch between spin-mode and mutex-(ie.e sleeping) mode by calling:

combi_to_mutex_mode(struct combilock *x)
combi_to_spin_mode(struct combilock *x)

without loosing the lock. So you may start with a spin-lock and relax to a sleeping lock if for example you need to call a non-atomic kmalloc.

This approach is less automatic than a first_spin_then_sleep mutex, but normally the programmer knows better if he is going to do quick things, or maybe unbounded stuff.

Note: For a preemptible kernel this approach could lead to much less scheduling ping-pong also for UP if a spinlock is replaced by a combilock instead of a semaphore.

Limitations:
1. In the current implementation the combilock is not irq-save

2. Although the combilock shares some advantages with a spin-lock (no unnecessary scheduling for short time locking) it may behave like a semaphore on entry also if you call combi_spin_lock. For example

        spin_lock(&slock);
        combi_spin_lock(&clock);

is a BUG because combi_spin_lock may sleep while holding slock!

Open questions:

* Does it make sense to also provide irq-save versions of the locking functions? This means you could use the unlock functions from interrupt context. But the main use in this situation is completion handling and there are already (new) completion handlers available. So I don't think this is a must have.

* I there any need to provide non exclusive versions of the waiting functions? For real-time applications this would lead to an automatic selection of the highest priority task that's waiting for the lock. But on the other hand it leads to a lot of unnecessary scheduling and I doubt it's really worth it. But maybe there are other good reasons to wakeup all waiters.

Possible optimizations:

If a further extension to a priority inheritance scheme is discarded the owner may be replace by a simple flag. And if this is done, one possibly could group together the owner flag and the waitqueue spinlock to a single 3-state lock. But on architectures without a cmpxchg command this may give no real performance win. And also on i386 this would need a tweaking of the waitqueue code.

To really take any benefit from a preemptible kernel a lot of spin locks will have to be replaced by mutex locks. The combi-lock approach may convince more people who typically fear the higher scheduling pressure of sleeping locks to do so, if they can decide on each instance which approach (spin of sleep) will be taken.

Here comes the code:

diff -ruP linux-2.5.3/include/linux/combilock.h
linux/include/linux/combilock.h

@@ -0,0 +1,86 @@
+#ifndef __LINUX_COMBILOCK_H
+#define __LINUX_COMBILOCK_H
+
+/*
+* combilock data structure.
+* See kernel/sched.c for details.
+*/
+
+
+#include <linux/wait.h>
+#include <asm/current.h>
+
+struct combilock {
+	struct task_struct volatile   *owner;
+	wait_queue_head_t             wait;
+};
+
+#define COMBILOCK_INITIALIZER(work) \
+	{ NULL, __WAIT_QUEUE_HEAD_INITIALIZER((work).wait) }
+
+#define DECLARE_COMBILOCK(work) \
+	struct combilock work = COMBILOCK_INITIALIZER(work)
+
+static inline void init_combilock(struct combilock *x)
+{
+	x->owner = NULL;
+	init_waitqueue_head(&x->wait);
+}
+
+extern int  FASTCALL(combi_mutex_trylock(struct combilock *x));
+extern void FASTCALL(combi_mutex_lock(struct combilock *x));
+extern int  FASTCALL(combi_mutex_lock_interruptible(struct combilock

*x));
+extern void FASTCALL(combi_mutex_unlock(struct combilock *x)); +extern void FASTCALL(__combi_wait(struct combilock *x));
+
+static inline struct task_struct volatile *combi_owner(struct combilock *x)
+{
+ return x->owner;
+}
+
+static inline void combi_spin_lock(struct combilock *x)
+{
+ spin_lock(&x->wait.lock);
+ if (unlikely(x->owner))
+ __combi_wait(x);
+}
+
+static inline int combi_spin_trylock(struct combilock *x) +{
+ if (unlikely(spin_trylock(&x->wait.lock)))
+ return 1;
+ if (unlikely(x->owner))
+ __combi_wait(x);
+ return 0;
+}
+
+static inline void combi_spin_unlock(struct combilock *x) +{
+ spin_unlock(&x->wait.lock);
+}
+
+static inline void combi_to_mutex_mode(struct combilock *x) +{
+ if (likely(!x->owner)) {
+ x->owner=current;
+ spin_unlock(&x->wait.lock);
+ }
+}
+
+static inline void combi_to_spin_mode(struct combilock *x) +{
+ if (likely(x->owner)) {
+ spin_lock(&x->wait.lock);
+ x->owner=NULL;
+ }
+}
+
+static inline void combi_generic_unlock(struct combilock *x) +{
+ if (likely(!x->owner))
+ combi_spin_unlock(x);
+ else
+ combi_mutex_unlock(x);
+}
+
+#endif
diff -ruP -X /home/adlex/linuxdiffpattern.txt linux-2.5.3/kernel/ksyms.c linux/kernel/ksyms.c

@@ -46,6 +46,7 @@
 #include <linux/tty.h>
 #include <linux/in6.h>
 #include <linux/completion.h>
+#include <linux/combilock.h>
 #include <linux/seq_file.h>
 #include <asm/checksum.h>
 

@@ -371,6 +372,13 @@
 /* completion handling */
 EXPORT_SYMBOL(wait_for_completion);
 EXPORT_SYMBOL(complete);
+
+/* combilock non-inline functions */
+EXPORT_SYMBOL(combi_mutex_trylock);
+EXPORT_SYMBOL(combi_mutex_lock);
+EXPORT_SYMBOL(combi_mutex_lock_interruptible);
+EXPORT_SYMBOL(combi_mutex_unlock);
+EXPORT_SYMBOL(__combi_wait);
 
 /* The notion of irq probe/assignment is foreign to S/390 */
 

diff -ruP -X /home/adlex/linuxdiffpattern.txt linux-2.5.3/kernel/sched.c linux/kernel/sched.c

TASK_INTERRUPTIBLE,1, 0);
+ spin_unlock(&x->wait.lock);
+}
+
+

#define SLEEP_ON_VAR \
unsigned long flags; \

Spinaphore :-)

Daniel

Or mutabloat :-(

				Regards,

					Richard....
Permanent: [email protected]
Current:   [email protected]

I think this API is really ugly. If both pathes actually do the same, just with different defaults, one lock function with a flag would be much nicer. Also why do we need two unlock functions?

What about the following instead:

	combi_lock(struct combilock *x, int spin);
	combi_unlock(struct combilock *x);

This looks really ugly. I'd really prefer an automatic fallback from spinning to sleeping after some timeout like e.g. solaris adaptive mutices.

You are no supposed to sleep in irq context, so irq-save combi-locks don't make that much sense, IMHO.

Christoph

Of course it doesn't work. We've performed a software upgrade.

Look closer at what he said. You'd take the lock, then you might decide you had to do something on a slow/blocking path, for example, a copy to/from user, so you could do that without leaving waiters spinning, or having to acquire a different lock and re-establish the state. It bears thinking about.

Daniel

What is easier to read:

	combi_lock(zzzt_clock, 1);	
	// go grepping .h to find out what this 1 means
or
	combi_spin_lock(zzzt_clock);

?

OTOH single unlock() looks good.
--
vda

Interesting ...

The question I raise is, how many locks do we have where we have a single resource we lock where in some codepaths the lock is used for short duration and in other places the lock is long-duration?

It would be useful to identify a few locks where this would benefit and apply the appropriate combi variant and do some benchmarking.

Some of the talk I've heard has been toward an adaptive lock. These are locks like Solaris's that can spin or sleep, usually depending on the state of the lock's holder. Another alternative, which I prefer since it is much less overhead, is a lock that spins-then-sleeps unconditionally.

This can be bad. What if I grab a spinlock in a codepath where only a spinlock is appropriate (i.e. somewhere I can't sleep, like an irq handler) -- and then I sleep?

Very true ... but only assuming we can find locks where there are differing profiles of use.

You can't sleep in an interrupt request handler, so this wouldn't make a lot of sense.

Non-exclusive wakeups are common ... see the uses of normal wake_up vs wake_up_exclusive.

We shouldn't engage in wholesale changing of spinlocks to semaphores without a priority-inheritance mechanism. And _that_ is the bigger issue ...

Robert Love

Quite a few. Significant ones. pagemap_lru_lock and lru_list_lock come to mind.

I dunno. The spin-a-bit-then-sleep lock has always struck me as i_dont_know_what_the_fuck_im_doing_lock(). Martin's approach puts the decision in the hands of the programmer, rather than saying "Oh gee I goofed" at runtime.

I need to think about all of this some more...

hmmm.

Let's back off a bit. What are we trying to achieve here? What problem are we trying to solve? Is it to allow preemptability
inside the infamous long-held locks? If so then I'd favour
a piecemeal approach to handling each one, rather than magic bullets. Now it may be that certain of the locks are best handled via a new primitive, but that's not obviously true at this time, to me.

-

ugh. Are you sure we want to *sleep* with something like pagemap_lru_lock held? That pretty much brings all pagecache related operations to a grinding halt. I think complex spinlocked sections should be simplified rather.

Ingo

Not guilty :) I was answering rml's question.

I suspect lru_list_lock is the shining example. We often take it for very short periods and occasionally take it for enormous periods.

yup. We'd go into a sheduling storm until we find the process which holds the lock.

yes.

-

I completely agree, and I couldn't have put it better! Kernel programmers really should know exactly why, what, where and for how long they are holding a lock.

This is why, incidently, I don't like any of the so-called lockless schemes, including the original unix kernel monitor lock (i.e. only one kernel thread active at a time), because they encourage unmaintainable code where the critical sections are invisible to everyone and are easily broken when someone accidently inserts a blocking function into one of the invisible critical sections.

Nigel Gamble [email protected]
Mountain View, CA, USA. http://www.nrg.org/

Should != do.

And any kernel programmer who says they do in a fine grained multithreaded kernel is full of it. Look at IRIX, look at Solaris, and show me someone who says they know for a fact how long they hold each lock and I'll show you a liar.

Furthermore, while adaptive spin-then-sleep locks may look stupid, I think you may be missing the point. If you are running an SMP kernel on a UP, you want the lock to sleep immediately. If you are running an SMP kernel on an SMP, then you want to spin if the lock is held by some other CPU but sleep if it is held by this CPU. I suspect that that is what was really meant by spin-a-bit-then-sleep, it just got lost in translation.

---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

The spin-then-sleep lock could be interesting as a replacement for the BKL in places where a semaphore causes performance degredation. In quite a few places where we replaced the BKL with a more finely grained semapore (not a spinlock because we needed to sleep during the hold), instead of spinning for a bit, it would schedule instead. This was bad :). Spin-then-sleep would be great behaviour in this situation.

Dave Hansen
[email protected]

So what's the difference between combi_spin and combi_mutex? combi_spin becomes
if not mutex locked, spin
else sleep
Bizzare

The entire concept is revolting.

no, the real optimization is that when spin meets spin, they will not mutex. If a mutex-user has it then spins turn into mutex, but that (is supposed to) happen rarely.

i think one example *could* be to turn inode->i_sem into a combi-lock. Eg. generic_file_llseek() could use the spin variant.

this is a real performance problem, i've seen scheduling storms in dbench-type runs due to llseek taking the inode semaphore.

whether combi-locks truly bring performance benefits remains to be seen, but the patch definitely needs to provide some working example and some hard numbers for some real workload.

Ingo

No. i_sem should be split into a spinlock for short-time accessed fields that get written to even if the file content is only read (i.e. atime) and a read-write semaphore.

Read-write semaphores should never be used. As others have pointed out, they cause really intractable priority inversion problems (because a high priority writer will often have to wait for an unbounded number of lower priority readers, some of which may have called a blocking function while holding the read lock).

Note that I'm not talking about read-write spinlocks, which are (or should be) held for a short, bounded time and can't be held over a blocking call, so they are not quite so problematic.

Nigel Gamble [email protected]
Mountain View, CA, USA. http://www.nrg.org/

Read-write semaphores have their use and the current Linux implementation (big reader/occasional writer) guarantees that the writer is not starved as incoming read locks are put to sleep as soon as a write lock request comes in, even if that is sleeping waiting for the old readlocks to be released (unless the readers are holding the semaphore forever in which case this is the programmers fault and not the rw semaphore implementations fault). [I should add I only am familliar with the i386 implementation but I assume the others are the same.]

The value of allowing multiple cpus to read the same data simultaneously by far offsets the priority problems IMVHO. At least the way I am using rw semaphores in ntfs it is. Readlocks are grabbed loads and loads of times to serialize meta data access in the page cache while writelocks are a minute number in comparison and because the data required to be accessed may not be cached in memory (page cache page is not read in, is swapped out, whatever) a disk access may be required which means a rw spin lock is no good. In fact ntfs would be the perfect candidate for automatic rw combi locks where the locking switches from spinning to sleeping if the code path reaches a disk access. I can't use a manually controlled lock as the page cache lookups are done via the mm/filemap.c access functions which are the only ones who can know if a disk access is required or not so ntfs would never know if it is going to sleep or not so unless the locks had autodetection of whether to spin or sleep they would be useless.

I guess the point I am trying to make is that both rw semaphores and combi locks are not bad per se but, as all other locking mechanisms, they should be used in situations appropriate for their locktype and their implementation...

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/
ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/

...

Here's the context: the preemption patch puts pressure on Linux to move from BKL to semaphores and then it will be seen that semaphores need to have dynamic priority inherit to sort-of-work, and then it will be seen that read/write lock is a problem!

this is absolutely correct. However, once the decision has been made or fallen into to go to a priority inherit scheme, Linux will find itself in the same bind as Solaris.

Seem like the lock is simply grabbed way to far up.

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

It cannot be taken any later. NTFS is a database both in memory and on disk and in fact the in memory meta data is the on-disk structures (i.e. no conversion between the two is performed, except in few speed optimization cases and in cases where meta data is compressed on disk).

Because everything is ogranized in database records, I need to grab the lock as soon as I intend to access the record (in fact the lock itself is taken by map_mft_record(READ or WRITE) which returns a locked record, that is mapped and pinned in memory, to the caller. I can then do all sorts of things with the record, like search it, parse data from it, etc. When finished I unmap_mft_record(READ or WRITE) which undoes everything map_mft_record() did, i.e. unpins the record, unmaps it and releases the lock.

All transactions with the on disk storage are done via the page cache and read_cache_page() using a special readpage() and a special async io completion handler.

Because of the abstraction of access layers it is undesirable to operate on the same locks in different layers, hence the top most layer is the one locking and unlocking the records. The lower layers don't even know the locks exist. Also pushing the lock deep into the layers is not actually possible as it would probably need to be taken in reac_cache_page() (the only place where the code knows if the page is present in memory or not and a disk access is required) which is a VFS/MM function and hence that is not an option.

Further, I may need to allocate memory in order to store decompressed metadata for example but I won't know if I need to do that until I have already locked the record and accessed it to determine if the metadata is compressed or not.

So basically I can only obtain sufficient info for deciding what lock I need after I have already accessed parts of the record, but to access it I need to have locked it. Chicken and egg situation... So the locks are always semaphores and are taken in the top layer.

A combi lock would allow spinning in the case where it turns out the code paths will not hit disk or sleep in kmalloc, etc and sleeping in the disk/kmalloc hit case.

(Yes I know atomic kmalloc exists but I actually need vmalloc in some cases depending how much memory I need to handle the metadata...)

Best regards,

Anton

  "I've not lost my mind. It's backed up on tape somewhere." - Unknown
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/
ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/

I don't see any strong reason for taking i_sem in the generic seek functions. The only thing we seem to need to protect in there is the non-atomic access to 64-bit i_size on 32-bit platforms, for which a spinlock is appropriate.

I'd be interested in hearing more details on the regression which Ingo has seen due to the introduction of i_sem locking in llseek. Not just for "I told you so" value, but for the body of knowledge :)

-

i saw heavy scheduling during dbench runs (even if just running 6 threads on an 8 CPU box), and checked out the source of the scheduling storm - most of it was due to llseek()'s down().

i also wrote a dbench-alike load simulator for pagecache scalability, there i saw this in an even more prominent way, 200k/sec reschedules in a situation when there should be none.

i'd suggest 64-bit update instructions on x86 as well, they do exist. spinlock only for the truly hopeless cases like SMP boxes composed of i486's. We really want llseek() to scale ...

Ingo

Ingo, are you sure that you actually saw llseek() causing problems? And not, say it, ext2_get_block()?

If you've got a heavy holder of some lock + lots of guys who grab it for a short periods, the real trouble is the former, not the latter.

I'm going to send ext2-without-BKL patches to Linus - tonight or tomorrow. I really wonder what effect that would have on the things.

yes.

no. I saw ext2_get_block() overhead in other workloads, but not this one. (this was a fully cached pagecache-only workload.)

no, i simply had code that called llseek() pretty often for the same inode (big database file), and on multiple CPUs it was just way too easy for one semaphore user to cause another one to block.

oh, that is a really cool thing!

llseek() is unrelated, and i think pretty gross. Is there any other reason to llseek()'s i_sem usage other than the 64-bit atomic update of the file offset value? We can do lockless, SMP-correct 64-bit updates on x86 pretty easily.

Ingo

Umm... Wait a second. You've seen the problems on ->i_sem variant of llseek()? My apologies - I've misparsed you.

I seriously suspect that BKL-for-lseek() will be good enough once we kill BKL in ext2_get_block() and friends. IOW, I doubt that generic_file_lseek() showing up in BKL contention is the real problem...

It seems like what you want is:
if the lock is about to be released, spin, else sleep.
But what is proposed is
if the lock is locked as a mutex, sleep, else spin
although I doubt either of these work - they seem like attempts to avoid designing the code.

llseek:
atomic_enquee request
if no room gotta sleep
else if trylock mutex
return
else
do work
loop:
process any pending requests
release lock;
if pending_requests && !(trylock mutex) goto loop

I think it's a lot easier to propose lock structures than to work on reducing synchronization problems.

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

This is how printk() works. It was a very powerful and satisfactory solution to a nasty locking/atomicity problem. It'd be nice to have a more generic way of expressing that solution.

-

note how I put in the goto so Ingo would be more happy with it -)

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Christoph Hellwig <[email protected]> [02/02/07 14:41]:

how about

        combi_lock (struct combilock *x, int canblock, int shouldblock);

Where the should block flag is copied to the mutex once it's held by the caller to indicate to new threads grabbing the lock how long the lock will be held for.

For locks that are held for some short duration tasks and some long duration tasks, the holder should indicate how long the lock will be held. I'd consider that an improvement over the "spin for a while then block" idea.

Interrupt handlers can't block, so we need a flag to never block.

-mark

But surely you *knew*, from inspection, which code paths needed a spinning lock, and which code paths needed a sleeping lock?

Assuming the answer is "yes" then a nice fix would be to use two separate locks - one which spins and one which sleeps.

Now, if the resource which is being protected truly cannot be split up into spin-protected and sleep-protected sections then a lock which can be atomically converted from spinning to sleeping at the programmer's discretion seems appropriate.

A dynamic lock which says "we've spun for too long, let's sleep" seems to be a tradeoff between programmer effort and efficiency, and a bad one at that.

Possibly the locks could become more adaptive, and could, at each call site, "learn" the expected spintime. But it all seems too baroque to me.

-

I'm not so sure. What if we can't _know_ how long the lock will be held because we don't know the status of the holder? What if _he_ is sleeping on some other lock or their are a lot of contending processes?

Certainly I agree, we need to put forth effort into designing things right and with a minimal amount of lock held time.

Agreed, this is much too much ;-)

Robert Love

Cool. We can then have the Solaris "this usually doesn't fail on test" priority inherit read/write lock. I can hardly wait.

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Or, we could do things right and not.

Robert Love

I'd love to hear how things could be done right here.
There seem to be 3 choices for reader writer locks
1. Do the right thing and say no to inheritance: and this means no inheritance on mutexes either.
2. Use the Solaris - "sometimes kinda works" method.
3. Make readers/writer locks very slow and expensive e.g
a complete list of reader identities that with atomic insert/delete and with check for uniqueness on insert! Not to mention the write promotion, any interactions between the "favor writes" design it should have and inheritance, links for a mutex inheriting lock to follow down the complete tree of paths from the r/w lock ...

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Assuming there is no

4. a solution that works

(and I do not assume that) we can just not do inheritance under reader-writer locks and that means they remain as spin locks. Normal spin locks remain proper candidates.

I never mentioned anything about reader-writer locks in my original email. Most of the long-held locks I am considering are not in this category anyway ...

Robert Love

P.S. If this is going to turn into another priority-inheritance flame, I am stopping here. Let's take it off-list or just drop it, please. I'd much prefer to discuss the current combilock issue which is at hand. ;)

I'm content to let it drop here, but I simply observe that you keep bringing up the glorious future of inheritance without addressing any of the hard problems. My contention is that the very capable Solaris engineers did not find the
(4) above because it does not exist.

It's the same issue.

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Just to use plain numbers is not very instructive, so you ask for a macro
definition like COMBI_LOCK_SPIN_MODE ?????

There is the generic_unlock function, if you forgot in which mode you are.
The main reason is performance for the spin mode: combi_spin_unlock is just
a spin_unlock, no test, no branch. So you are faster if you know what you did
a few lines of code before ;-)

As noted in my initial e-mail the current implementation is not for use in irq-handlers or BHs etc.

You of course were only allowed to call the unlock() functions!! Therefore you could use them to free a resource from the handler (but that's very much completion handling, see above).

The combilock at least can be used to narrow the time windows for priority
inversion because for most purposes you would use the spin mode. I thinking
about some extension in this direction (that's why the owner field is a pointer
to the owning task btw.).

That the e.g. the aproach of Solaris which results in about 5 time higher
latencies from a hardware interrupt to the waiting process.

Martin Wirth

Not necessarily, look at Ingo's observation about replacing semaphores with combi-locks as opposed to replacing spinlocks with combi-locks.

Daniel

The underlying issue is an attempt to find a magic trick that will make hard synchronization problems go away. The result is usually something that makes hard synchronization problems more obscure. Ingo points to a case, apparently triggered only by a wierd benchmark artefact where a queue of very short term operations builds up a queue of expensive process reschedules. The problem is that the same semaphore is used to for slow and fast operations and the solution is to split them apart somehow or to conclude that its not an important case.

As Ingo points out, you need some actual positive results here, not a plausibility argument.

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Yup.

Daniel

Wouldn't it be sufficient to include the following patch of code at the beginning of __combi_wait(...):

        if (smp_processor_id() != owner->cpu) {
                int cnt=MAX_LOOP_CNT;
retry:
                spin_unlock(&x->wait.lock) 
                do {
                        barrier();
                while (--cnt && x->owner);
                spin_lock(&x->wait.lock);
                if (!x->owner)
                        return;
                if (cnt)
                        goto retry;
        }
       then the sleep code of __combi_wait(...)

If one fears that the owner (or current if the kernel is made preemptible) migrated to the same cpu while we are spinning for x->owner and hence may
make no progress, one could let the waiting loop last about a typical process switch time and add an outer loop that checks if the cpu of the owner is still different.

Martin Wirth

Now, before we go further, can people explain _why_ we want this?

If something is getting a lot of short contention as a semaphore, maybe it's just broken locking. Let's not work around it with a new locking primitive just because we can.

What is the _existing_ problem this is trying to solve, and why?

Linus

There are currently several attempts discussed to push out the BKL and replace it by a semaphore e.g. the next step Robert Love planned for his ll_seek patch (replace the BKL by inode i_sem).

The naive replacement BKL -> semaphore is surely bad. Now on the other extreme you may always find a splitting of the data you want to protected into short locked and long locked sections like Christoph Hellwig suggested for i_sem:

But this approach needs a lot a proper documentation and discipline.

So for most BKL removal work I suggested the combi-lock which scales better than a semaphore but is more manageable than splitted locking.

Martin

P.S.: I posted the combi-lock as a practical RFC to bring the discussion about lock scalability, latency and possible preemptiblity of the linux kernel back to a concrete technical level (if you look at the "[2.4.17/18] VM and swap - it's really unusable" thread some weeks ago you can surely imagine why). And the simple reason is that for my real time data acquisition systems I really would like to get rid of my SunOS 5.8 and W2K machines. But the truth is that the standard linux kernel is a real (worst case) latency hog even when compared with these two bloated OS, at least for my applications. Only Andrew Morton's (full)-ll patch boosts linux to comparable performance (less than 1-2 ms latency under heavy io-load). (I know that SunOS 5.8 and W2K also can have larger latencies under special circumstances, but not for a simple streaming data acquisition with some online visualization).

But that won't have any contention anyway, so it's a non-issue.

Linus

... and this attitude is my main beef with B^WLSE crowd.

Folks, if you have nothing else to do - *don't* mess with locking just for the heck of it. And yes, you are supposed to understand WTF you are doing.

-

... so just make it a spinlock instead.

The semaphore is overkill, as the only thing we're really protecting is one 64-bit access against other updates.

Linus

I'm not sure that we really need a separate spinlock here. BKL might be just fine, provided that we remove it from real hogs. And we can do it now.

Had anyone actually seen lseek() vs. lseek() contention prior to the switch to ->i_sem-based variant? If the mix looked like
infrequently called BKL hog + many lseeks()
almost all contention cases would have lseek() spinning while a hog holds BKL. And real problem here is a hog...

yes, i've seen this for years. (if you accept dbench overhead.)

and regarding the reintroduction of BKL, *please* do not just use a global locks around such pieces of code, lock bouncing sucks on SMP, even if there is no overhead.

Ingo

I'd suggest not having a lock at all, but instead add two functions: one to read a 64-bit value atomically, the other to write it atomically (and they'd be atomic only wrt each other, no memory barriers etc implied).

On 64-bit architectures that's just a direct dereference, and even on x86 it's just a "cmpxchg8b".

Linus

Are there architectures out there that absolutely must implement this with a spinlock? Your suggested API of functions to read/write 64-bit values atomically would work for such a case, but still I am just curious.

Jeff

Jeff Garzik      | "I went through my candy like hot oatmeal
Building 1024    |  through an internally-buttered weasel."
MandrakeSoft     |             - goats.com

At least PPC32 can't do that without a spinlock_irq

Ben.

We don't need to be irq-safe for this, though. Just specify it to be process safe - which means that on UP it boils down to at most maybe having to protect against preemption.

Linus

SMP 486s would need that (if there is such a beast). What point does x86 get the 64 bit instructions? If after 586, then it would definately need a spinlock or somesuch in those functions.

Mike

There are SMP 486 class x86 machines that are MP 1.1 compliant. They are sufficiently rare that I think its quite acceptable to "implement" a cmpxchg8b macro on 486 as spin_lock_irqsave/blah/spin_unlock_irqrestore. It would be wrong to cripple the other 99.99% of SMP users

Sorry, I only meant to say that the only question is where the split should be between spin-lock and 64bit instruction...

This would be included in the appropriate config option.

Mike

Yes, I did, even on my 2-way.

Additionally, when I posted the remove-bkl-llseek patch, someone from SGI noted that on a 24-processor NUMA IA-64 machine, _50%_ of machine time was spent spinning on the BKL in llseek-intense operations.

The bkl is not held for a long time, but it is acquired often, and there are definitely workloads that show a big hit with the BKL in there.

Robert Love

That doesn't say _anything_ about the source of contention.

Sigh... OK, here's an exercise:

You have a spinlock and two functions - hog() and light(). Both grab that spinlock. light() releases it and returns fast. hog() spends quite a while in critical area and then releases the lock.

a) show that if lock gets contended then most of the time it will be held by hog()

b) show that time spent spinning in light() depends mostly on the amount of time spent in hog()

c) replace light() with light1(), ..., lightN(). Compare the effect of removing lock from one of them with that of removing it from hog().

d) characterize the dependence of light()/light() contention upon the amount of time spent in hog(). (hint: attempts to call light() while hog() is running will lead to accumulation of contenders and when hog() is done they _will_ figth each other).

General rules:
* go for hogs first, don't try to pick the light ones.
* one spinning most is not necessary the cause of contention.
* even when you see real light/light contention - check the
history immediately before; you may find the hog that had had held them back.

combi_spin_lock():
If not mutex locked, spin - will be released shortly else sleep - may take long time before released
* lock released *
spin lock it! <=== this is the difference -
combi_mutex_lock would mutex lock it here

What's wrong with this?
--
vda

In the elegant words of Andrew Morton, this is a "I don't know what the fuck I'm doing lock".

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

Can you sleep if acquired as the spinlock?

Is there any measurable (or at least plausible reason why there should be) performance improvement? (No, "should make preemptible kernel faster" doesn't cut it at all for me). Or any hope that it will substantially simplify kernel programming with _no_ performance degradation by replacing both semphores and spinlocks?

Horst von Brand			     http://counter.li.org # 22616