[RFC/PATCH] FUSYN Realtime & robust mutexes for Linux try 2.2

[RFC/PATCH] FUSYN Realtime & robust mutexes for Linux try 2.2

[inaky.perez-gonzalez]

Hi All

This is a new release of the code for providing a user and kernel
space synchronization infrastructure that provides real-time friendly
behavior, priority inversion protection (through serialized unlocks,
priority inheritance and protection), deadlock detection and
robustness [as in it doesn't fry when a mutex owner dies].

It builds upon the design of futexes and its usage model as NPTL does.

Please look at the first patch, containing the documentation for
information on how is it implemented. Kind of outdated, but useful
anyway. As well, the OLS 2004 paper is available on the web site.

High level changelog since release 2.2:

- Requeue-like support implemented for fuqueues and fulocks, to
speed up conditional variable broadcast.

- auto detection of the best unlock mode (based on an idea by
Jamie Lokier).

- Improve the taking of timeouts from user space by creating a
'struct timeout' that can take an absolute or relative
specification. POSIX uses absolute, so it is dumb to go to the
kernel twice, once to ask for the current time and then
compute a relative sleep and another one to do the actual
sleep.

- Added the ability to selectively compile out some parts of the
code via CONFIG_ options. Could add some more grain.

- Pages are no longer pinned while waiting.

- Fixed a big bunch of race conditions and bugs.

- priority lists are now fully O(140) ~= O(1) [except for
splice, which is still a hack that needs polishing].

Still to-do:

- Finally finish implementing priority protection; the core is
there, only the glue to use it is needed.

- Wipe out debug stuff

- Call fuqueue_waiter_cancel() into try_to_wake_up?

The patch is split in the following parts:


1/11: documentation files
2/11: priority based O(1) lists
3/11: kernel fuqueues
4/11: kernel fulocks
5/11: user space/kernel space tracker
6/11: user space fuqueues
7/11: user space fulocks
8/11: Arch-specific support
9/11: Modifications to the core: basic
10/11: Modifications to the core: struct timeout
11/11: Modifications to the core: scheduler

We have a site at http://developer.osdl.org/dev/robustmutexes
with references to all the releases, test code and NPTL
modifications (rtnptl) to use this code. As well, the patch
is there in a single file, in case you don't want to paste
them manually.

[RFC/PATCH] FUSYN 1/11: documentation files

[inaky.perez-gonzalez]

 fusyn.txt |  679 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 679 insertions(+)

--- /dev/null	Thu Jul 22 14:30:55 2004
+++ Documentation/fusyn.txt Tue Feb 3 00:56:52 2004
@@ -0,0 +1,679 @@
+
+FUSYN - Fast User SYNChronization primitives
+
+http://developer.osdl.org/dev/robustmutexes/
+
+I am calling these things FUSYNs to distinguish them from the original
+futexes they base on, as they behave kind of different (the naming
+sucks, you are welcome to suggest new names).
+
+This is my second big time attempt to implement real-time locking in
+the Linux kernel to solve the short comings of a locking system based
+on futexes, being mainly:
+
+   - no robustness support without kernel cooperation
+
+   - no priority inheritance/protection
+
+   - no real-time wake up (priority based, no priority inversion
+     holes, etc)
+
+   - No way to implement detection of complex deadlock scenarios.
+
+The main objects to implement are:
+
+  - fuqueues: Priority-sorted wait queues -- other than that, mostly
+    equal to futexes. Usable from kernel and user space.
+
+  - fulock: 
+
+    This is a full blown "mutex" implementation that can be used from
+    kernel and user space (with user-space fast [un]locking on
+    non-contended situations), robustness (if owner dies, ownership is
+    passed on), priority inheritance and (FUTURE) priority protection.
+
+    They are just a fuqueue that supports the ownership concept, to
+    allow for robustness and priority inheritace/protection.
+
+    It also supports serialized and non-serialized unlocks [see FAQ].
+  
+All the non-blocking calls (wake() and unlock() can be used from
+interrupt context; the data structures are protected by IRQ safe spin
+locks). This is heavier weight, but is needed to properly support
+priority change while waiting and priority inheritance. As well, it
+helps to avoid cache line bouncing of the spin locks that protect the
+structures.
+
+Released files:
+
+http://developer.osdl.org/dev/robustmutexes/
+
+fusyn-KERNEL-VERSION.PATCH-VERSION.patch   Patch file against Linus' tree
+fusyn-test-PATCH-VERSION.tar.gz      Sample test library and code
+
+
+Contents:
+---------
+
+- quick intro
+- vlocators
+- fuqueues
+- fulocks
+- issues/future work
+- FAQ [some definitions here, try wild search]
+
+
+QUICK INTRO
+-----------
+
+Fuqueues are more or less like waitqueues and like futexes (the user
+space one, ufuqueues), but they are priority sorted and if you change
+the priority of a waiter while blocked, it will update it's position
+in the wait list. 
+
+The priority sorting is O(N) in addition now, but I will change that
+sometime to be O(1) [actually, O(N) with N bounded to the max number
+of supported priorities, so O(1)].
+
+Fulocks build on top of fuqueues and just adds the concept of 'owner'
+plus some flags. A fulock can only be owned by a single task at the
+same time; a task contains a list of the fulocks it owns.
+
+This is for kernel space; for user space, each fu* structure has a
+ufu* counterpart that adds a vlocator--that is used to associate the
+user space address the kernel space pointer of the ufu* struct.. ufu*
+objects are allocated on demand; when noone is using them, they are
+released after a while (so we have caching) [use means somebody
+waiting on it to be woken up/acquire the lock or somebody owning the
+[u]fulock]. 
+
+To speed things up, there is a fast-mode (non-KCO) to lock/unlock
+fulocks in user-space without need for kernel intervention (just like
+NPTL's using futexes). To allow for robustness, priority inheritance
+and the like, we need to know who owns the lock, so we lock using the
+PID of the locking thread [more on this below].
+
+
+VLOCATORS
+---------
+
+This is an structure (struct vlocator) and the associated code to map
+a user space address to a kernel object that is kept in a hash
+table. As well, it provides and uses a reference count for the object,
+as well as a hash table cleanup function.
+
+It uses the 'struct futex_key' as done by Jamie Lokier; the code is in
+include/linux/vlocator.h and kernel/vlocator.c. 
+
+Two very simple operations: find an object in 'current's space by
+address and find-or-allocate (vl_find() and vl_locate()).
+
+The cleanup function (or garbage collector) runs periodically and
+releases items with a reference count of zero. This allows the get/put
+operations to be lockless.
+
+
+FUQUEUES
+--------
+
+Fuqueues are just wait-queues, like futexes; the differences are in
+the wake up process, as it is done not in a FIFO order but by
+priority. As well, if the task changes its priority while waiting, its
+position in the list is updated. The code is in include/linux/fuqueue.h
+and kernel/fuqueue.c.
+
+They consist of a 'struct fuqueue' which has a priority-sorted wait
+list and a lock to protect access to it. They can be used in
+kernel-space as a wait queue.
+
+Entry points:
+
+fuqueue_wait() -- wait on a fuqueue
+fuqueue_wake() -- wake N waiters from a fuqueue with code C.
+
+The code is split in various functions to allow fulocks to use the
+fuqueue stuff for integration. The wlist*_t thing is a reminder of
+something that will go away; it stands for 'wait list' and is setup
+with a #define based redirection to support different types of sorted
+wait list implementations (for example, one that is O(1) using a
+priority array -- that is huge). That is going to be deprecated in
+favor of a O(1) priority sorted list that is not as big (see FUTURE
+WORK).
+
+'struct ufuqueue' is a fuqueue plus the stuff to link it to a possibly
+shared user space address (a vfuqueue) (the vlocator), so that is the
+real futex equivalent. The code is in kernel/ufuqueue.c and just
+consists on the syscall wrappers to associate the proper ufuqueue to
+the vfuqueue and then call the fuqueue layer.
+
+Need to add more stuff to make fuqueues more of a waitqueue
+equivalent. 
+
+
+FULOCKS
+-------
+
+The mother of the whole thing. Fulocks are a full mutex
+implementation; it is basically the concept of an owner and a list of
+tasks waiting to own the mutex (implemented with a 'struct fuqueue'). 
+
+The 'struct fulock' holds all the fulock properties (most in the flags
+member). As well, there is an ownership list node, where all the
+fulocks that a task currently owns are linked to the task
+(task->fulock_olist).
+
+Properties of a fulock:
+
+- owner/state: locked or unlocked
+
+- mode of operation (encoded in the flags):
+
+  + pi xor pp: fulock is priority inheritance or protection (or
+    none). 
+
+  + deadlock detection: lock() checks for deadlocks before allowing
+    it.
+
+  + sun-mode robustness: do robustness not-so-flexibly
+
+  + KCO (no fast path) xor non-KCO (fast path allowed).
+
+  Robustness is always enabled as it is easy for user space to
+  simulate the hangs that happen when you don't have it.
+
+- priority:
+
+  + Priority Inheritance: the priority of a fulock is that of the
+    highest priority waiter on its wait list. If no waiters, then it
+    has minimal priority.
+
+  + Priority Protection: the priority of the fulock is its priority
+    ceiling. The priority ceiling is encoded in the flags too.
+
+  + Normal (no PI or PP): the priority is the minium one (this nops
+    everything in the PI/PP mechanisms).
+
+  This priority is assigned to the ownership list node so that the
+  fulocks in the ownership list are sorted. This is importante for
+  priority inheritance and protection.
+
+- health state: healthy, dead-owner or not-recoverable (see the FAQ
+  for the definitions). It is encoded in the flags.
+
+The entry points are [kernel/fulock.c, include/linux/fulock.h]:
+
+fulock_lock()
+fulock_unlock()
+fulock_consistency() [for manipulating the state]
+
+How PI/PP works is by always keeping the priorities of the
+waiters/fulocks around. The fulock has a prio that comes from the wait
+list (if PI), from the prio ceiling (if PP) or minimal (none). When
+anybody owns that fulock, the fulock is added to the ownership list by
+fulock prio order. The highest prio fulock determines the prio of the
+list, and that is what is called the "bost" priority, which is stored
+in task->boost_prio. I've hacked up the scheduler to, whenever it
+needs the prio of a task for activating it, to choose from the maximum
+prio from the real prio and the boost one. This way, when the boost is
+higher, the task is effectively boosted (see __prio_boost() in
+sched.c). The hack is still a wee hackish, need to make it more
+optimized so that we don't need to calculate the minimum everytime,
+but just once, when we change the boosting thingie.
+
+
+A user level fulock (struct ufulock) is a fulock that can be used from
+the user space--it is represented by a (potentially shared) memory
+address (a vfulock) in user space. A vlocator is used to track
+it. Implemented in kernel/ufulock.c.
+
+Now, depending on certain parameters (arch supporting atomiooic
+compare-and-exchange, anal-retentive robustness need and something
+else I can't remember) you might one to use fast-path mode (non-KCO)
+or KCO mode. KCO stands for Kernel Controlled Ownership. In this mode,
+every [un]lock() operation goes through the kernel, without user space
+optimizations for the low contention case.
+
+In non-KCO mode (fast-path), the vfulock may have different values
+that server to define the state of a lock:
+
+0                       Unlocked [can be fast-locked]
+PID (< VFULOCK_WP)      Fast-locked by PID, no waiters in the
+                        kernel. [can be fast-unlocked].
+VFULOCK_WP              Locked by someone, kernel knows who, waiters 
+                        in the kernel.
+VFULOCK_DEAD            Previous owner died (maybe unlocked or
+                        locked), the kernel keeps the status [this is
+                        effectively identical to KCO mode]).
+VFULOCK_NR              Not recoverable.
+
+In KCO mode locks, we just keep the health state of the lock in the
+vfulock (to account for the volatility of KCO ufulocks in kernel
+space; if a KCO ufulock is owned, it exists in userspace; if not, it
+will end up being released back to the kmem cache): 
+
+VFULOCK_HEALTHY (==VFULOCK_UNLOCKED)  Fulock is healthy, normal
+VFULOCK_DEAD                          Fulock owner died
+VFULOCK_NR                            Ditto ...
+
+Now, back to non-KCO mode (the complex case :), this is how it works: 
+
+When user space goes to lock a ufulock with a fast operation, it
+issues an atomic compare and swap on the vfulock of its PID against 0
+(VFULOCK_UNLOCKED); if it succeeds, its the owner, done; if not, it
+goes to the kernel (sys_ufulock_lock()), who will put it to wait [see
+test/src/include/kernel-lock.h:vfulock_lock() in the fusyn-test
+package] or do the lock() according to the rules for dead fulocks.
+
+Unlock is fairly similar: if the value is VFULOCK_{WP,DEAD}, go to the
+kernel, sys_ufulock_unlock(); if VFULOCK_NR, return error; if not, it
+is a PID and need to do an atomic compare and exchange of 0
+(VFULOCK_UNLOCKED) (unlock) against the PID [again, check
+vfulock_unlock()].
+
+The kernel will always maintain the value in the vfulock and the
+corresponding fulock in the 'struct ufulock' in sync [vfulock_sync()
+in kernel/ufulock.c], and will do that everytime we enter it through
+one of the fulock system calls (sys_ufulock_{[un]lock,consistency}().
+
+The kernel will use the PID set by the fast-locker to match who is the
+owner when he doesn't know about it [afterwards it will be registered
+in the kernel)--check __fulock_id_owner() for ideas on how to avoid
+collision due to PID reuse].
+
+Once that is done, what is left is a 'fulock' that can be handled by
+the fulock layer.
+
+Now [uv]fulocks support:
+
+    - Real time: the unlock procedure is realtime in the sense that it
+      is O(1) and the next owner is the highest priority one; as well,
+      the fulock (actually, the vfulock) is never unlocked in the
+      meantime, the ownership is transferred instead of unlocking the
+      lock, waking up the first waiter and waiting for it to acquire
+      it. This avoids priority inversions by lower priority threads
+      sneaking in from other processors at the worst time.
+
+      However, this has a cost: the convoy phenomenon. To avoid that,
+      the unlock can be performed in a non-serialized fashion, where
+      the fulock is unlocked and then the new owner-to-be woken up so
+      it contends for it. Check "What are the two kinds of unlock" in
+      the FAQ below.
+
+    - Deadlock checking: complex dead lock scenarios where a
+      ownership/wait chain [see definition in FAQ] is involved are
+      catched if FULOCK_FL_ERROR_CHK is set.
+
+    - Priority change support: when the priority of the waiting task
+      is changed, it's position in the list is updated. See below for
+      effects on priority inheritance.
+
+    - Robustness: when a task who is a fulock owner dies and the
+      kernel knew about it (ie: it was registered in the
+      task->fulock_list), then the fulock is made dead-owner, unlocked
+      and the next waiter gets ownership, with a -EDEADOWNER return
+      code. 
+
+      This is always enabled; user space can emulate the
+      hangs+timeouts that would happen if this were not detected.
+
+      If the kernel knew nothing about it (ie: it was fast-locked),
+      then __fulock_id_owner() will fail to map the PID in the vfulock
+      to an existing task; then the current claimer would be
+      considered the owner after marking the fulock dead-owner.
+
+      Note the comments in __fulock_id_owner() for ideas on how to
+      avoid collisions due to PID reuse.
+
+    - Priority protection: when the owner is set, it's priority is
+      raised to the priority ceiling of the fulock; when it unlocks,
+      its prio is driven back to what it was before (or if there are
+      any other boosts in effect, whichever is effective).
+
+    - Priority inheritance: when a waiter queues for a fulock that has
+      the FULOCK_FL_PI bit set and its priority is higher than that of
+      the owner, it will boost the owner's priority to its own; this
+      will propagate in an ownership/wait chain (if the owner was
+      waiting on for a fulock, etc). As well, priority changes will
+      also be propagated.
+
+      The guts of these have been explained above; I should work on
+      the order of the explanations...
+
+
+FUTURE WORK
+-----------
+  
+  - fucond: conditional variables; although they can be implemented
+    in user space + fuqueues, doing it in the kernel helps a lot in
+    atomicity issues (and the performance should be much better).
+
+    We tried doing that (see releases up to 1.12 in the website) and
+    generally  it sucked because of the code bloat in the kernel, so
+    we decided to extirpate it.
+  
+  - rw lock: only the first locker can do the fast operation; the
+    others go to the kernel to sign up. This way ownership is
+    supported. If a reader dies, nothing happens (after all, it is
+    supposed to be read-only access), but we need to keep track of
+    readers dying so they don't hold writers off. If a writer dies,
+    next locker (reader or writer) gets dead-owner.
+
+    These guys could also get, like this, PI and PP, as they would be
+    very similar to fulocks, but with two waiting lists. One for
+    writers, one for readers, and they allow many ownerships at the
+    same time (when there are readers).
+
+    Maybe different operation modes to primer writers over readers?
+    FIXME, need to explore.
+
+  - Spinlocks: they could be implemented as a trylock() on a fulock
+    for N loops, and after it'd degenerate into a mutex wait. This
+    wait they'd automagically support robustness, PI and PP.
+
+  - Barriers: futexes offer enough functionality for implementing
+    them, however wake up should be real-time (priority based). Not a
+    real issue though, as in barriers everybody is woken up. It can be
+    done also with fuqueues.
+
+  - Getting rid of the vlocator hash table and doing direct mapping
+    [so that we avoid the O(N) lookup] by storing in user space some
+    short of pointer to a in-kernel data struct. The pointer has to be
+    "validated", so that user space cannot have the kernel point to
+    some random or pontentially dangerous space. 
+
+    A way would be to store two values, the pointer itself plus a
+    kernel-crypted copy that the can be used to verify.
+
+    Need more research into this.
+
+  - O(1) priority list: current plist is not O(1) in addition, because
+    it has to locate the proper position in the list where to add. I
+    plan to modify the plist code to be O(N) where N is the number of
+    priority levels, and as it is fixed at compilation time, it is
+    effectively O(1). 
+
+    The idea is to have something similar to a priority array, but
+    instead of having N list heads, we have only the first node of
+    each priority being the list head, and the rest of the guys in
+    that prio hanging from him.
+
+  - Sun-mode robustness. Solaris implements robustness in a slightly
+    more restrictive way. We want to add an small compatibility layer
+    so both models can be used.
+
+  - That page pinning when waiting for a fulock...
+
+
+FAQ
+---
+
+This set of Q&A is what I use myself to track my ideas and concepts
+(and not to forget why did I decide anything).
+
+
+Q: What is PI?
+
+Priority Inheritance: when task A holds resource R and task B claims
+it, and prio (B) > prio (A), then B can force A to take its priority
+so it finishes sooner and B can take the resource ownership. The
+priority boost ends when A releases R.
+
+
+Q: What is PP?
+
+Priority Protection: resources have an associated priority ceiling;
+any task that acquires a resource will have its prio raised to that
+prioirty ceiling while holding it.
+
+
+Q: What is RM?
+
+Robust Mutex, or robustness, for short: when the owner of a resource
+dies, we want the next owner to know that somebody died while holding
+the resource, so s/he is able to determine if a cleanup is needed.
+
+
+Q: What is a healthy fulock?
+
+This is a fulock in its normal state, that is: initialized and not in
+dead-owner or not-recoverable states.
+
+
+Q: What is a dead-owner fulock?
+
+A fulock is in dead-owner state when it was locked (some task owned
+it) and the task died without unlocking it.
+
+
+Q: What is a not-recoverable fulock?
+
+A fulock is in not-recoverable state when it went into dead-owner
+state and some task that acquired it in dead-owner state decided that
+it had to be made not-recoverable.
+
+The rationale behind this is that normally you have some lock
+protecting access to some data. When the lock goes dead-owner, the
+task that owned it and died could have died in the middle of updating
+the data, and thus it can be inconsistent. Subsequent owners of the
+lock get it with the dead-owner state, so that they are aware of the
+situation. If any of them can fix it, it can move the lock back to
+healthy state and continue operating, but if there is no way to fix
+the data, it is moved to not-recoverable state.
+
+When moved, all the pending waiters are given an error code
+(ENOTRECOVERABLE) indicating the new state, so that they can bail out
+and report up to their managers for what to do. As well, new
+contenders that try to acquire the lock will get also the EBADR error
+code.
+
+The only way to make the fulock healthy again is to reinitialized it.
+
+
+Q: What is a dead-owner dead-lock?
+
+When some task that has to unlock a locked fulock dies and others are
+waiting for it to release the fulock.
+
+
+Q: What is a dead-owner recovery?
+
+When a lock owner dies, the next waiter or next guy who locks and gets
+ownership gets it with an special code that indicates that some
+previous owner died and that the state of the lock is "dead-owner",
+that recovery on the data structures protected by the lock must be
+done in order to ensure consistency.
+
+Once a fulock is in dead-owner state, it can be moved back to
+normal/healthy or made inconsistent (so only an initialization returns
+it to normal).
+
+
+Q: Why does the kernel have to set the value of the fulock?
+   Why cannot the value of the fulock after unlock be set by user
+   space?
+
+This applies only to non-KCO (fast-path) mode fulocks.
+
+There is a risk of overwritten values and missed waiters.
+
+For example, task B claims fulock F (locked by task A) so it goes to
+the kernel to wait; now the fulock value is VFULOCK_WP (waiters
+blocked in the kernel). Before it reaches the kernel, task C releases
+the fulock for task A; as there are no waiters, it returns UNLOCKED
+and task C has to set it to UNLOCKED, thus overwriting VFULOCK_WP; as
+_WP is overwritten, task B is going to be dead-locked in the kernel,
+waiting.
+
+Furthermore, it helps guaranteeing robustness. If the just-woken up
+task that has to set the value the kernel passes dies before being
+able to do it, you hit a dead-owner dead-lock because nobody wakes up
+the waiters until somebody tries to lock and realizes the fulock is
+dead.
+
+
+Q: What are the two kinds of unlock?
+
+The two kinds of unlock are serialized and non-serialized. Each one is
+explained in more detail in the next two Qs.
+
+You need both because the serialized one can be slower, as it might
+force a context switch.
+
+I thought initially that this would show only in synthetic benchmarks
+(very tight loop acquiring and releasing the lock against some other
+threads doing the same thing), but I was wrong. Max Hailperin pointed
+to me that what I was seeing was the "Convoy Phenomenon", documented
+by Mike Blasgen, Jim Gray, Mike Mitoma and Tom Price, in 1977
+[http://portal.acm.org/citation.cfm?id=850659&jmp=cit&dl=GUIDE&dl=ACM]
+when I was still poking in my nose and sucking my thumb.
+
+After thinking about it, I concluded it would mostly apply in the
+following conditions:
+
+- user space only [in kernel space the lock itself is the spinlock
+  that protects the 'struct fulock'; we spin and disable preemtion, so
+  there is no context switch].
+
+- non real-time environments/processes (where preemption is likely)
+
+- real-time SMP environments with non-KCO fulocks, where two tasks
+  might compete for a lock at the _same_ time (so to avoid it in this
+  case, it might be interesting to spin a wee bit in user space before
+  blocking).
+
+Now, in order to gain robustness you need serialization (*), so a
+userspace user is recommended to use serialized wake ups only when:
+
+- need *full* and complete robustness guarantee
+
+- needs real-time priority-inversion protection guarantee (in SMP, not
+  needed for UP).
+
+(*) See the next Q, but summarizing: Task A holds M, task B and C are
+waiting; A unlocks(), non-serialized, M is unlocked (in the kernel,
+the vfulock is still VFULOCK_WP), A is woken up. A goes back to user
+space and contends, sees VFULOCK_WP and goes to the kernel to lock,
+but before he gets there, it dies. Now B is stuck there because the
+fulock is unlocked and nobody knew he was waiting.
+
+A way to solve this could be to mark the task B and fulock M as B
+should lock M. If on the way of death (do_exit()) we see that, we mark
+M as dead and initiate recovery in the next waiter. FIXME: need to
+research. 
+
+
+Q: What is a non-serialized unlock?
+
+A non-serialized unlock works by setting the fulock to unlocked and
+waking up as many waiters as desired. The waiters then re-contend for
+the fulock, the winner owns it and the others go back to wait on it.
+
+This approach is not as heavy in forcing context switches, and thus
+can yield better performance, avoiding the convoy phenomenon.
+
+However, drawbacks are that you loose priority-inversion protection
+and the ability to guarantee robustness.
+  
+- Say we have a fulock with M guys waiting and we wake up N (1 < N <
+  M), a non-serialized wakeup. Thus, there are M - N guys still
+  waiting in the kernel.
+  
+  In order for the unlock to be non-serialized, the waker first sets
+  the lock to UNLOCKED.
+  
+  Now, how do the woken up processes know that there are still
+  processes in the kernel?
+  
+  A solution is to set the vfulock not to UNLOCKED, but to _WP; this
+  way, whowever tries to acquire will see that and go down to the
+  kernel to do the lock operation.
+  
+  However, it still does not solve the fact that when setting to _WP
+  and waking N, if those N die before locking, the waiters go into
+  dead-owner dead-lock.
+  
+  When somebody tries to lock that, the kernel should be able to
+  notice that there are waiters and it is unlocked and thus give
+  way to the first locker with dead-owner recover --it might be too late.
+  
+  Another option might be to tag the woken-up processes before they
+  exit the kernel, so that if they die, do_exit can trap it (but there
+  are many side issues to this, like how do I make sure that the N who
+  I woke up have gone through it, one has locked, the other N-1 have
+  gone to sleep, how do I clean it up and stuff like that--makes it
+  pretty ugly, not to talk about how many resources it'd need to tag it).
+  
+  Gosh, it is a mess -- I would say that robust mutexes have to
+  require serialized unlocks. Period.
+
+  Not even talk about adding a short timer to verify that the thing
+  was locked...shrivers
+
+  RESEARCH: tentative ownership: when we wake up some guys who are
+  supposed to go and try to lock again, tie the fulock they should
+  lock to their task_struct and on exit(), check they don't have it
+  there ... [many details need to be worked out].
+
+- It could also be solved by waking up _all_ the waiters; this way no
+  dead-owner dead-lock could ever happen; however, it is a sure recipe
+  for an scheduling storm some day.
+
+
+Q: What is a serialized unlock?
+
+A serialized unlock transfers the ownership of the fulock to the first
+waiter in the kernel. 
+
+- Only one waiter can be woken up at the same time with this method.
+
+- It prevents priority inversion (as the fulock stays locked during
+  the whole operation no low priority thread can acquire it in the
+  meantime).
+
+- dead-owner dead-lock is not possible, because the owner is always
+  known during the operation. As well, if the new owner dies on it's
+  way up to user space, its ownership is also known.
+
+Slower (still not proved seriously--postulated and proven in some
+very synthetic benchmarks) because it forces a context switch.
+
+
+Q: What is an vfulock?
+
+It is the address in user space associated to a fulock in kernel
+space. 
+
+
+Q: What is owner identification?
+
+Owner identification is a property that the KCO ufulocks have:
+basically, they can identify who is the owner based on the vfulock (in
+user space) or the internal kernel data structures that refer to it
+(if the vfulock is VFULOCK_KCO, that means that the kernel tracks the
+ownership); if vfulock < VFULOCK_KCO, it means that the ownership is
+tracked only in user space, and the vfulock is the PID of the owner.
+
+
+Q: What is a kernel-controlled-ownership fulock? (KCO)
+
+A fulock that has no fast-path; every operation is done through the
+kernel.  This happens when:
+
+     - The fulock is locked and there are waiters on the kernel
+     - The fulock is dead (and the ownership keeps track for it)
+     - The fulock is a priority protected fulock or called with
+       FULOCK_FL_CO in the flags.
+
+Basically it is a way to indicate that the fastpath for
+locking/unlocking cannot be taken.
+
+
+Q: What is an ownership/wait chain?
+
+The structure that is formed when task A owns lock F and is waiting
+for lock G, owned by task B that is waiting for lock H, that is owned
+be task C that is waiting for lock I ... etc. 
+
+When this chain is circular (eg: lock I is owned by A) then there is a
+deadlock. Priority protection propagates through this chains, as well
+as priority changes in any part of the chain.

[RFC/PATCH] FUSYN 2/11: priority based O(1) lists

[inaky.perez-gonzalez]

These are lists similar to the ones in linux/list.h; however,
they are sorted by descending priority, which each node has;
as well, nodes with the same priority are queued together in
sublist, so insertion is O(K), where K is a constant meaning
the number of different priorities you are using [in the case
of the scheduler, it'd be O(140)].


 include/linux/plist.h |  268 ++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/Makefile          |    2 
 lib/plist.c           |   96 +++++++++++++++++
 3 files changed, 365 insertions(+), 1 deletion(-)

--- /dev/null	Thu Jul 22 14:30:56 2004
+++ include/linux/plist.h Tue Jul 20 03:21:03 2004
@@ -0,0 +1,268 @@
+/*
+ * Descending-priority-sorted double-linked list
+ *
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on simple lists (include/linux/list.h).
+ *
+ * 
+ * This is a priority-sorted list of nodes; each node has a >= 0
+ * priority from 0 (highest) to INT_MAX (lowest). The list itself has
+ * a priority too (the highest of all the nodes), stored in the head
+ * of the list (that is a node itself).
+ *
+ * Addition is O(1), removal is O(1), change of priority of a node is
+ * O(1).
+ *
+ * Addition and change of priority's order is really O(K), where K is
+ * a constant being the maximum number of different priorities you
+ * will store in the list. Being a constant, it means it is O(1).
+ *
+ * This list is really a list of lists:
+ *
+ *  - The tier 1 list is the dp list (Different Priority)
+ *
+ *  - The tier 2 list is the sp list (Same Priority)
+ *
+ * All the nodes in a SP list have the same priority, and all the DP
+ * lists have different priorities (and are sorted by priority, of
+ * course).
+ *
+ * Addition means: look for the DP node in the DP list for the
+ * priority of the node and append to the SP list corresponding to
+ * that node. If it is the first node of that priority, add it to the
+ * DP list in the right position and it will be the head of the SP
+ * list for his priority.
+ *
+ * Removal means remove it from the SP list corresponding to its
+ * prio. If it is the only one, it means its also the head and thus a
+ * DP node, so we remove it from the DP list. If it is the head but
+ * there are others in its SP list, then we remove it from both and
+ * get the first one of the SP list to be the new head.
+ *
+ * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX
+ * is lowest priority.
+ *
+ * No locking is done, up to the caller.
+ *
+ * NOTE: This implementation does not offer as many interfaces as
+ *       linux/list.h does -- it is lazily minimal. You are welcome to
+ *       add them.
+ */
+
+#ifndef _LINUX_PLIST_H_
+#define _LINUX_PLIST_H_
+
+#include <linux/list.h>
+
+/* Priority-sorted list */
+struct plist {
+	int prio;
+	struct list_head dp_node;
+	struct list_head sp_node;
+};
+
+#define plist_INIT(p,__prio)				\
+{							\
+	.prio = __prio,					\
+	.dp_node = LIST_HEAD_INIT((p)->dp_node),	\
+	.sp_node = LIST_HEAD_INIT((p)->sp_node),	\
+}
+
+/* Initialize a pl */
+static inline
+void plist_init (struct plist *pl, int prio)
+{
+	pl->prio = prio;
+	INIT_LIST_HEAD (&pl->dp_node);
+	INIT_LIST_HEAD (&pl->sp_node);
+}
+
+/* Return the first node (and thus, highest priority)
+ *
+ * Assumes the plist is _not_ empty.
+ */
+static inline
+struct plist * plist_first (struct plist *plist)
+{
+	return list_entry (plist->dp_node.next, struct plist, dp_node);
+}
+
+/* Return if the plist is empty. */
+static inline
+unsigned plist_empty (const struct plist *plist)
+{
+	return list_empty (&plist->dp_node);
+}
+
+/* Update the maximum priority of the whole list
+ *
+ * @returns !0 if the plist prio changed, 0 otherwise.
+ * 
+ * __plist_update_prio() assumes the plist is not empty.
+ */
+static inline
+unsigned __plist_update_prio (struct plist *plist)
+{
+	int prio = plist_first (plist)->prio;
+	if (plist->prio == prio)
+		return 0;
+	plist->prio = prio;
+	return !0;
+}
+
+static inline
+unsigned plist_update_prio (struct plist *plist)
+{
+	int old_prio = plist->prio;
+	/* plist empty, lowest prio = INT_MAX */
+	plist->prio = plist_empty (plist)? INT_MAX : plist_first (plist)->prio;
+	return old_prio != plist->prio;
+}
+
+/* Add a node to the plist [internal]
+ *
+ * pl->prio == INT_MAX is an special case, means low priority, get
+ * down to the end of the plist. Note the we want FIFO behaviour on
+ * the same priority.
+ */
+static inline
+void __plist_add_sorted (struct plist *plist, struct plist *pl)
+{
+	struct list_head *itr;
+	struct plist *itr_pl;
+
+
+	if (pl->prio < INT_MAX) {
+		list_for_each (itr, &plist->dp_node) {
+			itr_pl = list_entry (itr, struct plist, dp_node);
+			if (pl->prio == itr_pl->prio)
+				goto existing_sp_head;
+			else if (pl->prio < itr_pl->prio)
+				goto new_sp_head;
+		}
+		itr_pl = plist;
+		goto new_sp_head;
+	}
+	/* Append to end, SP list for prio INT_MAX */
+	itr_pl = container_of (plist->dp_node.prev, struct plist, dp_node);
+	if (!list_empty (&plist->dp_node) && itr_pl->prio == INT_MAX)
+		goto existing_sp_head;
+	itr_pl = plist;
+
+new_sp_head:
+	list_add_tail (&pl->dp_node, &itr_pl->dp_node);
+	INIT_LIST_HEAD (&pl->sp_node);
+	return;
+	
+existing_sp_head:
+	list_add_tail (&pl->sp_node, &itr_pl->sp_node);
+	INIT_LIST_HEAD (&pl->dp_node);
+	return;
+}
+
+
+/**
+ * Add node @pl to @plist @returns !0 if the plist prio changed, 0
+ * otherwise. 
+ */
+static inline
+unsigned plist_add (struct plist *plist, struct plist *pl)
+{
+	__plist_add_sorted (plist, pl);
+	/* Are we setting a higher priority? */
+	if (pl->prio < plist->prio) {
+		plist->prio = pl->prio;
+		return !0;
+	}
+	return 0;
+}
+
+
+/* Grunt to do the real removal work of @pl from the plist. */
+static inline
+void __plist_del (struct plist *pl)
+{
+	struct list_head *victim;
+	if (list_empty (&pl->dp_node))  	/* SP-node, not head */
+		victim = &pl->sp_node;
+	else if (list_empty (&pl->sp_node)) 	/* DP-node, empty SP list */
+		victim = &pl->dp_node;
+	else {					/* SP list head, not empty */
+		struct plist *pl_new = container_of (pl->sp_node.next,
+						     struct plist, sp_node);
+		victim = &pl->sp_node;
+		list_replace (&pl_new->dp_node, &pl->dp_node);
+	}
+	list_del_init (victim);
+}
+
+
+/**
+ * Remove a node @pl from @plist. @returns !0 if the plist prio
+ * changed, 0 otherwise.
+ */
+static inline
+unsigned plist_del (struct plist *plist, struct plist *pl)
+{
+	__plist_del (pl);
+	return plist_update_prio (plist);
+}
+
+/* Return the priority a pl node */
+static inline
+int plist_prio (struct plist *pl)
+{
+	return pl->prio;
+}
+
+/* Change the priority of a pl node, without updating plist position */
+static inline
+void __plist_chprio (struct plist *pl, int new_prio)
+{
+	pl->prio = new_prio;
+}
+
+/**
+ * Change the priority of node @pl in @plist (updating the list's max
+ * priority).  @returns !0 if the plist's maximum priority changes
+ */
+static inline
+unsigned plist_chprio (struct plist *plist, struct plist *pl, int new_prio)
+{
+	if (new_prio == plist->prio)
+		return 0;
+	__plist_chprio (pl, new_prio);
+	__plist_del (pl);
+	__plist_add_sorted (plist, pl);
+	return __plist_update_prio (plist);
+}
+
+
+static inline
+struct plist * __plist_dp_next (struct plist *node_dp) 
+{
+	return container_of (node_dp->dp_node.next, struct plist, dp_node);
+}
+
+
+extern void __plist_splice (struct plist *dst, struct plist *src);
+
+/** Join @src plist to @src plist and reinitialise @src. @returns !0 */
+static inline
+unsigned plist_splice_init (struct plist *dst, struct plist *src)
+{
+	int old_prio;
+	if (plist_empty (src))
+		return 0;
+	old_prio = dst->prio;
+	__plist_splice (dst, src);
+	plist_init (src, INT_MAX);
+	return old_prio != dst->prio;
+}
+
+#endif /* #ifndef _LINUX_PLIST_H_ */
+
--- lib/Makefile:1.1.1.6 Tue Apr 6 00:23:06 2004
+++ lib/Makefile Sun Jul 18 19:19:38 2004
@@ -6,7 +6,7 @@
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
 	 kobject.o idr.o div64.o parser.o int_sqrt.o \
-	 bitmap.o extable.o
+	 bitmap.o extable.o plist.o
 
 # hack for now till some static code uses krefs, then it can move up above...
 obj-y += kref.o
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ lib/plist.c Sun Jul 18 19:19:27 2004
@@ -0,0 +1,96 @@
+
+/*
+ * Descending-priority-sorted double-linked list
+ *
+ * (C) 2002-2004 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on simple lists (include/linux/list.h).
+ *
+ * See include/linux/plist.h for the whole story.
+ */
+
+#include <linux/plist.h>
+
+/**
+ * Join @src plist to @dst plist.
+ */
+void __plist_splice (struct plist *dst, struct plist *src)
+{
+#warning FIXME: Lame plist_splice--fix the optimized version
+#if 1
+	/*
+	 * Lame quick version that for sure doesn't fail but is O(N^2)
+	 * and pretty slow.
+	 */
+	struct plist *itr;
+	while (!plist_empty (src)) {
+		itr = plist_first (src);
+		plist_del (src, itr);
+		plist_add (dst, itr);
+	}
+#else
+	/*
+	 * This version is broken, don't use it. Works generally, but
+	 * sometimes it screws up, so I need to check it in detail.
+	 */
+	
+	struct plist *src_dp_itr, *dst_dp_itr, *src_dp_next;
+	
+	if (plist_empty (src))
+		return;
+
+	src_dp_itr = __plist_dp_next (src);
+	dst_dp_itr = __plist_dp_next (dst);
+	
+	while (1) {
+		/* Insert src before dst */
+		if (src_dp_itr->prio < dst_dp_itr->prio) {
+			src_dp_next = __plist_dp_next (src_dp_itr);
+			list_del_init (&src_dp_itr->dp_node);
+			list_add_tail (&src_dp_itr->dp_node,
+				       &dst_dp_itr->dp_node);
+			if (src_dp_next == src)
+				break;
+			src_dp_itr = src_dp_next;
+			continue;
+		}
+		/* Append to dst's SP list--note our first SP node is
+		 * not just a head, is also part of the list
+		 * itself, so we have to do it manually */
+		else if (src_dp_itr->prio == dst_dp_itr->prio) {
+			struct list_head *src_sp_first, *src_sp_last,
+				*dst_sp_first, *dst_sp_last;
+
+			src_dp_next = __plist_dp_next (src_dp_itr);
+			list_del_init (&dst_dp_itr->dp_node);
+			
+			src_sp_first = &src_dp_itr->sp_node;
+			src_sp_last = src_dp_itr->sp_node.prev;
+			dst_sp_first = &dst_dp_itr->sp_node;
+			dst_sp_last = dst_dp_itr->sp_node.prev;
+
+			dst_sp_first->prev = src_sp_last;
+			dst_sp_last->next = src_sp_first;
+			src_sp_first->prev = dst_sp_last;
+			src_sp_last->next = dst_sp_first;
+				
+			if (src_dp_next == src)
+				break;
+			src_dp_itr = src_dp_next;
+			continue;
+		}
+		dst_dp_itr = __plist_dp_next (dst_dp_itr);
+		/* Dest list finished, we just can append the
+		 * remainder of the source list */
+		if (dst_dp_itr == dst) {
+			__list_splice (src_dp_itr->dp_node.prev,
+				       dst_dp_itr->dp_node.prev);
+			break;
+		}
+	}
+	dst->prio = __plist_dp_next (dst)->prio;
+#endif /* #if 1 */
+}

[RFC/PATCH] FUSYN 3/11: kernel fuqueues

[inaky.perez-gonzalez]

These are the basic queues, similar to the futexes, but
usable only from kernel space--some resemblance to
waitqueues, but that has to be improved.

It includes all the stuff for building on top of them (for
fulocks and the user space support) as well as the basic
debug macros--these will go away IANF.


 include/linux/fuqueue.h     |  410 ++++++++++++++++++++++++++++++++++++++++++++
 include/linux/fusyn-debug.h |  152 ++++++++++++++++
 kernel/fuqueue.c            |  349 +++++++++++++++++++++++++++++++++++++
 3 files changed, 911 insertions(+)

--- /dev/null	Thu Jul 22 14:30:56 2004
+++ include/linux/fuqueue.h Mon Jul 19 16:30:13 2004
@@ -0,0 +1,410 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ *
+ * Quick usage guide:
+ *
+ * struct fuqueue f = fuqueue_INIT (&f);
+ *
+ * fuqueue_wait (&f, 4343)	Wait for max 4343 jiffies
+ * fuqueue_wake (&f, 5, -EPERM) Wake the first five guys waiting on f
+ *				with -EPERM.
+ *
+ * These are simple priority-sorted wait queues that can be used from
+ * the kernel. They provide the foundation for more complex items
+ * (fulocks, fuconds, ufulocks, ufuconds) and use from user-space
+ * (ufuqueues, just like futexes).
+ *
+ * The type 'struct plist' provides the sorting for the wait list. The
+ * type 'struct fuqueue_waiter' represents a waiting task on a
+ * fuqueue. The 'struct fuqueue_ops' is what allows extensibility for
+ * other synchronization primitives.
+ *
+ * I have just realized that this is too similar to the wait_queues...
+ */
+
+#ifndef __linux_fuqueue_h__
+#define __linux_fuqueue_h__
+
+enum { FUQUEUE_WAITER_GOT_LOCK = 0x401449 };
+
+/** Fuqueue control actions */
+enum fuqueue_ctl {
+	FUQUEUE_CTL_RELEASE = 0,	/* Release an ufuqueue */
+	FUQUEUE_CTL_WAITERS,   		/* Do we have waiters? */
+};
+
+#ifdef __KERNEL__
+#include <linux/config.h>
+#include <linux/fusyn-debug.h>
+
+#ifndef CONFIG_FUSYN
+struct task_struct;
+static inline
+void fuqueue_waiter_cancel (struct task_struct *dummy1, int dummy2) {}
+
+static inline
+void fuqueue_waiter_chprio (struct task_struct *task, int old_prio) {}
+
+#else /* #ifndef CONFIG_FUSYN */
+
+#include <linux/errno.h>
+#include <linux/spinlock.h>
+#include <linux/plist.h>
+#include <linux/sched.h>
+#include <asm/hardirq.h>
+#include <linux/vlocator.h>
+
+struct task_struct;
+struct fuqueue;
+
+/**
+ * Type for fuqueue task wake function (or callback)
+ *
+ * @fuqueue: fuqueue we are waiting from
+ * @w: fuqueue wait structure where called from
+ * @state_mask: as passed to fuqueue_wake()
+ * @sync: perform a sync wake up or not.
+ * @returns: return 0 on success, !0 on error or any other condition
+ *           you feel like. This will tell __fuqueue_wake() to stop
+ *           waking up any other tasks if they were going to be woken
+ *           up. 
+ *           
+ * This function (if the pointer is non-NULL) is called from atomic
+ * context inside __fuqueue_wake().
+ */
+typedef int (*fuqueue_wake_f) (struct fuqueue *fuqueue, struct fuqueue_waiter *w,
+			       unsigned state_mask, int sync);
+
+/** Descriptor of a waiting task */
+struct fuqueue_waiter {
+	struct plist wlist_node;	/* node for the wait list */
+	struct task_struct *task;	/* task that is waiting */
+	int result;			/* what happened */
+	unsigned flags;			/* how is it supposed to happen */
+	fuqueue_wake_f wake_func;	/* call this upon wake up */
+};
+
+
+/* Bit-flags for influencing the wake up */
+enum {
+	FUQUEUE_WT_FL_QUEUE = 1,	/* Waiting for a queue */
+	FUQUEUE_WT_FL_EXCLUSIVE = 2,	/* Task is exclusive waiter */
+};
+
+
+/*
+ * Special parameters for fuqueue_wake*()
+ */
+
+/** fuqueue_wake*()'s @howmany: wake everybody */
+static const size_t FUQUEUE_WAKE_ALL = ULONG_MAX;
+
+
+/**
+ * Initializer for the fuqueue_waiter (we only initialize the fields
+ * that can cause trouble because they might not be overwritten by the
+ * queuing functions.
+ */
+#define fuqueue_waiter_INIT(_task)		\
+{						\
+	.task = (_task),			\
+	.flags = 0,				\
+	.wake_func = NULL,			\
+} 
+
+
+/**
+ * Operations on a fuqueue.
+ *
+ * All ops have to be atomic, no sleeping allowed.
+ * 
+ * NOTE: is it worth to have get/put? maybe they should be enforced
+ *	 for every fuqueue, this way we don't have to query the ops
+ *	 structure for the get/put method and if it is there, call
+ *	 it. We'd have to move the get/put ops over to the vlocator,
+ *	 but that's not much of a problem.
+ *
+ *	 The decision factor is that an atomic operation needs to
+ *	 lock the whole bus and is not as scalable as testing a ptr
+ *	 for NULLness.
+ *
+ *	 For simplicity, probably the idea of forcing the refcount in
+ *	 the fuqueue makes sense.
+ */
+struct fuqueue_ops {
+	void (* get) (struct fuqueue *);
+	void (* put) (struct fuqueue *);
+	unsigned (* waiter_cancel) (struct fuqueue *,
+				    struct fuqueue_waiter *);
+	struct task_struct * (* waiter_chprio) (
+		struct task_struct *, struct fuqueue *,
+		struct fuqueue_waiter *);
+};
+
+/** A fuqueue, a prioritized wait queue usable from kernel space. */
+struct fuqueue {
+	spinlock_t lock;	
+	struct plist wlist;
+	struct fuqueue_ops *ops;
+};
+
+/** A ufuqueue, tied to a user-space vm address. */
+struct ufuqueue {
+	struct fuqueue fuqueue;
+	struct vlocator vlocator;
+};
+
+
+/** Initialize a @fuqueue structure with given @ops */
+static inline
+void __fuqueue_init (struct fuqueue *fuqueue, struct fuqueue_ops *ops)
+{
+	spin_lock_init (&fuqueue->lock);
+	plist_init (&fuqueue->wlist, BOTTOM_PRIO);
+	fuqueue->ops = ops;
+}
+
+/** Statically initialize a @fuqueue with given @ops. */
+#define __fuqueue_INIT(fuqueue, fuqueue_ops) {			\
+	.lock = SPIN_LOCK_UNLOCKED,				\
+	.wlist = plist_INIT (&(fuqueue)->wlist, BOTTOM_PRIO),	\
+	.ops = (fuqueue_ops)					\
+}
+
+
+/** fuqueue operations for in-kernel usage */
+extern struct fuqueue_ops fuqueue_ops;
+
+
+/** Initialize a @fuqueue for usage within the kernel */
+static inline
+void fuqueue_init (struct fuqueue *fuqueue)
+{
+	__fuqueue_init (fuqueue, &fuqueue_ops);
+}
+
+/** Statically initialize a @fuqueue for usage within the kernel */
+#define fuqueue_INIT(fuqueue) __fuqueue_INIT(fuqueue, &fuqueue_ops)
+
+
+/** Wait for a @fuqueue to be woken for as much as @timeout, @returns
+ * wake up code */
+extern int fuqueue_wait (struct fuqueue *fuqueue, const struct timeout *);
+/**
+ * Wait for a @fuqueue to be woken for as much as @timeout, @return
+ * wake up code.
+ *
+ * Use provided @flags for waiting, as well as the specified wake up
+ * function callback (will be called before the task is woken up in
+ * atomic context).  */
+extern int fuqueue_wait_fcb (struct fuqueue *fuqueue, const struct timeout *,
+			     unsigned flags, fuqueue_wake_f callback);
+
+/**
+ * Wake waiters from a fuqueue.
+ *
+ * @fuqueue: where to wake from.
+ * @howmany: number of waiters to wake up. If 0 (FUQUEUE_WAKE_ALL),
+ *           wake all of them.
+ * @code: return code they should see when woken.
+ * @state_mask: mask of task states that should be woken.
+ * @sync: do a sync wake up or not.
+ */
+extern void fuqueue_wake_state (struct fuqueue *fuqueue, size_t howmany,
+				int code, unsigned int state_mask, int sync);
+
+/**
+ * Same as @fuqueue_wake_state(), defaulting to stopped, interruptible and
+ * uninterruptible tasks, no sync wake-up.
+ */
+static inline
+void fuqueue_wake (struct fuqueue *fuqueue, size_t howmany, int code)
+{
+	fuqueue_wake_state (fuqueue, howmany, code,
+			    TASK_STOPPED | TASK_INTERRUPTIBLE
+			    | TASK_UNINTERRUPTIBLE, 0);
+} 
+
+/* Cancel the wait on a fuqueue */
+extern void __fuqueue_waiter_cancel (struct task_struct *, int);
+extern unsigned __fuqueue_waiter_queue (struct fuqueue *,
+					struct fuqueue_waiter *);
+extern void __fuqueue_waiter_unqueue (struct fuqueue_waiter *);
+extern unsigned __fuqueue_op_waiter_cancel (struct fuqueue *,
+					    struct fuqueue_waiter *);
+extern void __fuqueue_waiter_chprio (struct task_struct *);
+
+
+/** Quick check if the task is fuqueue waiting and if so cancel. */
+static inline
+void fuqueue_waiter_cancel (struct task_struct *t, int code)
+{
+	if (unlikely (t->fuqueue_wait != NULL))
+		__fuqueue_waiter_cancel (t, code);
+}
+
+
+/*
+ * The following are functions to be able to access fuqueue
+ * functionality when building on top of it, like the [u]fulocks,
+ * and ufuqueues.
+ */
+
+
+/**
+ * Wakes up a single waiter and cleans up it's task wait information.
+ *
+ * @returns 0 if the plist's priority didn't change, !0 otherwise.
+ * 
+ * WARNING: call with preeempt and local IRQs disabled!!
+ */
+static inline
+unsigned fuqueue_waiter_unqueue (struct fuqueue *fuqueue,
+				 struct fuqueue_waiter *w)
+{
+	ftrace ("(%p [%d])\n", w, w->task->pid);
+
+	__fuqueue_waiter_unqueue (w);
+	return plist_update_prio (&fuqueue->wlist);
+}
+
+
+extern int __fuqueue_waiter_block (struct fuqueue *fuqueue,
+				   struct fuqueue_waiter *w,
+				   const struct timeout *timeout);
+
+/** @Returns true if the @fuqueue has no waiters. */
+static inline
+unsigned __fuqueue_empty (const struct fuqueue *fuqueue)
+{
+	return plist_empty (&fuqueue->wlist);
+}
+
+
+/** Return the first waiter on a @fuqueue */
+static inline
+struct fuqueue_waiter * __fuqueue_first (struct fuqueue *fuqueue)
+{
+	return container_of (plist_first (&fuqueue->wlist),
+			     struct fuqueue_waiter, wlist_node);
+}
+
+
+/**
+ * Default wake function callback
+ *
+ * @fuqueue: the task is being woken from
+ * @w: fuqueue waiter structure
+ * @state_mask: mask of task states that can be woken up and FUQUEUE_WAKE_*.
+ * @returns: 0, success, always.
+ * 
+ * This is provided in case you want to daisy chain.
+ */
+static inline
+int fuqueue_default_wake_function (struct fuqueue *fuqueue,
+				   struct fuqueue_waiter *w,
+				   unsigned state_mask, int sync)
+{
+	try_to_wake_up (w->task, state_mask, sync);
+	return 0;
+}
+
+
+/**
+ * Wake @howmany @fuqueue waiters with @code (this function is here
+ * so other fusyn components can inline it--nobody should use it,
+ * fuqueue_wake is for that).
+ */
+static inline
+void __fuqueue_wake_state (struct fuqueue *fuqueue, size_t howmany,
+			   int code, unsigned state_mask, int sync)
+{
+	struct fuqueue_waiter *w = NULL;
+
+	ftrace ("(%p, %zu, %d)\n", fuqueue, howmany, code);
+	
+	while (howmany-- && !__fuqueue_empty (fuqueue)) {
+		w = __fuqueue_first (fuqueue);
+		__fuqueue_waiter_unqueue (w);
+		w->result = code;
+		wmb();
+		if (w->wake_func == NULL)
+			fuqueue_default_wake_function (fuqueue, w,
+						       state_mask, sync);
+		else if (w->wake_func (fuqueue, w, state_mask, sync))
+			break;
+		if (w->flags & FUQUEUE_WT_FL_EXCLUSIVE)
+			break;
+	}
+	if (likely (w != NULL))
+		plist_update_prio (&fuqueue->wlist);
+}
+
+/**
+ * Same as @__fuqueue_wake_state(), defaulting to stopped, interruptible and
+ * uninterruptible tasks, no sync wake-up.
+ */
+static inline
+void __fuqueue_wake (struct fuqueue *fuqueue, size_t howmany, int code)
+{
+	__fuqueue_wake_state (fuqueue, howmany, code,
+			      TASK_STOPPED | TASK_INTERRUPTIBLE
+			      | TASK_UNINTERRUPTIBLE, 0);
+}
+
+
+
+/** A waiting @task changed its priority, propagate it. */
+static inline
+void fuqueue_waiter_chprio (struct task_struct *task, int old_prio)
+{
+	unsigned long flags;
+	
+	ftrace ("(%p [%d], %d)\n", task, task->pid, old_prio);
+
+	if (old_prio == task->prio)
+		return;
+	if (task->fuqueue_wait == NULL)
+		return;
+	local_irq_save (flags);
+	preempt_disable();
+	__fuqueue_waiter_chprio (task);
+	local_irq_restore (flags);
+	preempt_enable();
+}
+
+
+/**
+ * Set the priority of a fuqueue waiter, repositioning it in the wait
+ * list.
+ *
+ * This does not set the prio of the process itself! 
+ *
+ * @task: waiting task to reprioritize 
+ * @fuqueue: fuqueue the task is waiting for [locked]
+ * @w: waiter @task is waiting with in @fuqueue.
+ * @returns: NULL (as there is no propagation).
+ *	     
+ * Assumptions: prio != task->prio
+ *		fuqueue->lock held
+ */
+static inline
+struct task_struct * __fuqueue_op_waiter_chprio (
+	struct task_struct *task, struct fuqueue *fuqueue,
+	struct fuqueue_waiter *w)
+{
+	plist_chprio (&fuqueue->wlist, &w->wlist_node, task->prio);
+	return NULL;
+}
+
+#endif /* #ifndef CONFIG_FUSYN */
+#endif /* #ifdef __KERNEL__ */
+#endif /* #ifndef __linux_fuqueue_h__ */
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ include/linux/fusyn-debug.h Thu Jul 15 17:19:39 2004
@@ -0,0 +1,152 @@
+
+/*
+ * THIS FILE WILL GO AWAY!!!
+ *
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Debug utilities
+ */
+
+#ifndef __linux_fusyn_debug_h__
+#define __linux_fusyn_debug_h__
+
+#include <linux/spinlock.h>
+
+#ifdef __KERNEL__
+
+  /*
+   * move forward for seeing the real meat
+   * 
+   * Levels
+   * 
+   *	0 Nothing activated, all compiled out
+   * > 0 Activates assertions, memory allocation tracking
+   * > 1 Activates debug messages
+   * > 2 Activates [most] function traces
+   * > 3 Activates random debug stuff
+   */
+
+#undef DEBUG
+#define DEBUG 0
+
+
+
+/* Dump straight to ttyS0 on ia32 machines */
+#if 1 && defined (__i386__)
+#include <linux/serial_reg.h>
+#include <linux/stringify.h>
+static inline void __debug_serial_outb (unsigned val, int port) {
+	__asm__ __volatile__ ("outb %b0,%w1" : : "a" (val), "Nd" (port));
+}
+static inline unsigned __debug_serial_inb (int port) {
+	unsigned value;
+	__asm__ __volatile__ ("inb %w1,%b0" : "=a" (value) : "Nd" (port));
+	return value;
+}
+static inline
+void __debug_serial_printstr (const char *str) {
+	const int port = 0x03f8;  
+	while (*str) {
+		while (!(__debug_serial_inb (port + UART_LSR) & UART_LSR_THRE));
+		__debug_serial_outb (*str++, port+UART_TX);
+	}
+	__debug_serial_outb ('\r', port + UART_TX);
+}
+#endif /* #ifdef __i386__ */
+
+extern spinlock_t __debug_lock;
+
+static inline
+void __debug_printstr (const char *str) 
+{
+	if (DEBUG == 0)
+		return;
+#ifdef __i386__
+	__debug_serial_printstr (str);
+#else
+	printk (str);
+#endif
+}
+
+static inline
+u64 __tsc_read (void)
+{
+	u64 tsc;
+#if defined(__i386__)
+	__asm__ __volatile__("rdtsc" : "=A" (tsc));
+#elif defined (__ia64__)
+	__asm__ __volatile__("mov %0=ar.itc" : "=r" (tsc) : : "memory");
+#else
+#warning "Architecture not supported in __tsc_read()!"
+	tsc = 0;
+#endif
+	return tsc;
+}
+
+#define __debug(a...)								    \
+do {										    \
+	if (DEBUG > 0) {							    \
+		/* Dirty: Try to avoid >1 CPUs printing ... will suck */	    \
+		char __X_buf[256];						    \
+		unsigned __X_len;						    \
+		unsigned long __X_flags;					    \
+		__X_len = snprintf (__X_buf, 255, "%Lu: %s:%d: %s[%d:%d] ",	    \
+				    __tsc_read(), __FILE__, __LINE__, __FUNCTION__, \
+				    current->pid, current->thread_info->cpu);	    \
+		snprintf (__X_buf + __X_len, 255 - __X_len, a);			    \
+		spin_lock_irqsave (&__debug_lock, __X_flags);			    \
+		__debug_printstr (__X_buf);					    \
+		spin_unlock_irqrestore (&__debug_lock, __X_flags);		    \
+	}									    \
+} while (0)
+
+/* The real debug statements */
+
+#define ldebug(l,a...)	 do { if (DEBUG >= l) __debug (a); } while (0)
+#define debug(a...)	 ldebug(1,a)
+#define fdebug(f, a...)	 do { if ((DEBUG >= 2) && f) __debug (a); } while (0)
+#define __ftrace(l,a...) do { if ((l)) __debug (a); } while (0)
+#define ftrace(a...)	 __ftrace((DEBUG >= 2),a)
+#define assert(c, a...)	 do { if ((DEBUG >= 0) && !(c)) BUG(); } while (0)
+
+
+/*
+ * Helpers for debugging memory allocation [needs to be here so it can
+ * be shared by ufuqueue.c and ufulock.c].
+ */
+
+#if DEBUG >= 1
+static atomic_t allocated_count = ATOMIC_INIT(0);
+static inline
+
+int allocated_get (void) {
+	return atomic_read (&allocated_count);
+}
+
+static inline
+int allocated_inc (void) {
+	atomic_inc (&allocated_count);
+	return allocated_get();
+}
+
+static inline
+int allocated_dec (void) {
+	atomic_dec (&allocated_count);
+	return allocated_get();
+}
+
+#else
+
+static inline int allocated_get (void) { return 0; }
+static inline int allocated_inc (void) { return 0; }
+static inline int allocated_dec (void) { return 0; }
+
+#endif /* DEBUG >= 1 */
+
+
+#endif /* #ifdef __KERNEL__ */
+#endif /* #ifndef __linux_fusyn_debug_h__ */
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ kernel/fuqueue.c Mon Jul 19 16:29:29 2004
@@ -0,0 +1,349 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ *
+ * see the doc in linux/fuqueue.h for some info.
+ */
+
+#define DEBUG 8
+
+#include <linux/fuqueue.h>
+#include <linux/sched.h>
+#include <linux/plist.h>
+#include <linux/errno.h>
+
+#if DEBUG > 0
+spinlock_t __debug_lock = SPIN_LOCK_UNLOCKED;
+#endif
+
+
+/**
+ * Setup @current to wait for a fuqueue.
+ *
+ * This only setups, it does not block.
+ * 
+ * @fuqueue: fuqueue to wait on.
+ * @w: waiter structure to fill up and queue.
+ * @return: 0 if the fuqueue's priority didn't change, !0 otherwise.
+ *
+ * Fills up @current's fuqueue_wait* info and queues up @w after
+ * filling it.
+ *
+ * WARNING: Call with preempt and local IRQs disabled
+ */
+unsigned __fuqueue_waiter_queue (struct fuqueue *fuqueue,
+				 struct fuqueue_waiter *w)
+{
+	ftrace ("(%p, %p)\n", fuqueue, w);
+	
+	_raw_spin_lock (&current->fuqueue_wait_lock);
+	current->fuqueue_wait = fuqueue;
+	current->fuqueue_waiter = w;
+	_raw_spin_unlock (&current->fuqueue_wait_lock);
+	w->result = INT_MAX;
+	plist_init (&w->wlist_node, current->prio);
+	return plist_add (&fuqueue->wlist, &w->wlist_node);
+}
+
+
+/**
+ * Wait for a @fuqueue until woken up, @returns wake up code
+ *
+ * @fuqueue: where to wait on. Needs to be spinlocked.
+ * @w: waiter structure to wait with.
+ * @timeout: how long to wait. If ~0, wait for ever.
+ * 
+ * Needs to be called with the fuqueue lock held, local IRQs disabled
+ * and preempt disabled. Will release the lock, enable IRQs and
+ * preemtion. 
+ */
+int __fuqueue_waiter_block (struct fuqueue *fuqueue, struct fuqueue_waiter *w,
+			    const struct timeout *timeout)
+{
+	int result;
+	ftrace ("(%p, %p, %p)\n", fuqueue, w, timeout);
+	
+	set_current_state (TASK_INTERRUPTIBLE);
+	_raw_spin_unlock (&fuqueue->lock);
+	local_irq_enable();
+	preempt_enable_no_resched();
+	
+	/* Wait until we are woken up */
+	schedule_timeout_ext (timeout);
+	set_current_state (TASK_RUNNING);
+	/*
+	 * Now, whoever woke us up had to call first
+	 * fuqueue->ops->waiter_cancel() through fuqueue_waiter_cancel(),
+	 * and thus, unqueued us and set up a return code in
+	 * w->result. However, if w->result is still pristine as left
+	 * by __fuqueue_wait_queue(), that means our waker either
+	 * didn't know we were waiting or we have signal(s) pending,
+	 * so we do it ourselves.
+	 */
+	result = w->result;
+#warning FIXME: Need to recalc relative timeout if interrupted
+	if (unlikely (result == INT_MAX)) {
+		result = -ETIMEDOUT;
+		if (signal_pending (current))
+			result = -EINTR;
+		if (unlikely (current->fuqueue_wait != NULL))
+			__fuqueue_waiter_cancel (current, result);
+	}
+	return result;
+}
+
+
+/**
+ * Unqueue a single waiter and cleans up it's task wait information.
+ *
+ * Return -1 if the if the plist's priority didn't change, the new
+ * priority otherwise.
+ * 
+ * WARNING: call with preeempt and local IRQs disabled!!
+ */
+void __fuqueue_waiter_unqueue (struct fuqueue_waiter *w)
+{
+	struct task_struct *task = w->task;
+	
+	ftrace ("(%p [%d])\n", w, w->task->pid);
+	
+	__plist_del (&w->wlist_node);
+	_raw_spin_lock (&task->fuqueue_wait_lock);
+	task->fuqueue_wait = NULL;
+	task->fuqueue_waiter = NULL;
+	_raw_spin_unlock (&task->fuqueue_wait_lock);
+}
+
+
+/**
+ * Wait for a @fuqueue to be woken for as much as @timeout, @returns
+ * wake up code. See __fuqueue_waiter_block() for docs on @timeout.
+ *
+ * If wakeup code is FUQUEUE_WAITER_GOT_LOCK or -EOWNERDEAD, then it
+ * means the waiter was requeued to a fulock and that upon wake up, it
+ * was assigned ownership.
+ * 
+ * WARNING: can only be called from process context
+ */
+int fuqueue_wait (struct fuqueue *fuqueue, const struct timeout *timeout)
+{
+	struct fuqueue_waiter w = fuqueue_waiter_INIT (current);
+	
+	ftrace ("(%p, %p)\n", fuqueue, timeout);
+	
+	spin_lock_irq (&fuqueue->lock);
+	w.flags = FUQUEUE_WT_FL_QUEUE;
+	__fuqueue_waiter_queue (fuqueue, &w);
+	return __fuqueue_waiter_block (fuqueue, &w, timeout); /* unlocks */
+}
+
+
+int fuqueue_wait_fcb (struct fuqueue *fuqueue, const struct timeout *timeout,
+		      unsigned flags, fuqueue_wake_f wake_func)
+{
+	struct fuqueue_waiter w = fuqueue_waiter_INIT (current);
+	
+	ftrace ("(%p, %p)\n", fuqueue, timeout);
+	
+	spin_lock_irq (&fuqueue->lock);
+	w.flags = FUQUEUE_WT_FL_QUEUE | flags;
+	w.wake_func = wake_func;
+	__fuqueue_waiter_queue (fuqueue, &w);
+	return __fuqueue_waiter_block (fuqueue, &w, timeout); /* unlocks */
+}
+
+
+/*
+ * Wake @howmany waiters waiting on a @fuqueue, with return code (for
+ * them) @code.
+ *
+ *  
+ */
+#warning FIXME: how to emulate nr_exclusive from waitqueues?
+void fuqueue_wake_state (struct fuqueue *fuqueue, size_t howmany,
+			 int code, unsigned int state_mask, int sync)
+{
+	unsigned long flags;
+
+	ftrace ("(%p, %zu, %d, 0x%x, %d)\n", fuqueue, howmany, code,
+		state_mask, sync);
+	
+	spin_lock_irqsave (&fuqueue->lock, flags);
+	__fuqueue_wake_state (fuqueue, howmany, code, state_mask, sync);
+	spin_unlock_irqrestore (&fuqueue->lock, flags);
+}
+
+
+/**
+ * Change the priority of a waiter.
+ *
+ * @task: task whose priority has to be changed.
+ *
+ * This is the entry point that the scheduler functions call when a
+ * task that is waiting for a fuqueue changes its priority. It will
+ * call the fuqueue-specific chprio function after safely determining
+ * what is the fuqueue it is waiting for and then, if the
+ * specific chprio function determines that the prio change has to be
+ * propagated, it will keep doing it.
+ *
+ * The task that the chprio function returns has to be returned with a
+ * get_task_struct() reference.
+ *
+ * Note the weird locking: we are one of the little places that needs
+ * to take the locks in inverse order (most are fuqueue first,
+ * task_wait later--FT), we need to do TF, so we do T, test F, if it
+ * fails, unlock T, try again.
+ */
+void __fuqueue_waiter_chprio (struct task_struct *task)
+{
+	struct fuqueue_ops *ops;
+	struct fuqueue *fuqueue;
+	struct fuqueue_waiter *w;
+
+	ftrace ("(%p [%d])\n", task, task->pid);
+	
+	get_task_struct (task);
+next:
+	/* Who is the task waiting for? safely acquire and lock it */
+	if (task->fuqueue_wait == NULL)
+		goto out_task_put;
+	_raw_spin_lock (&task->fuqueue_wait_lock);
+	fuqueue = task->fuqueue_wait;
+	if (fuqueue == NULL)				/* Ok, not waiting */
+		goto out_task_unlock;
+	if (!_raw_spin_trylock (&fuqueue->lock)) {	/* Spin dance... */
+		_raw_spin_unlock (&task->fuqueue_wait_lock);
+		goto next;
+	}
+	ops = fuqueue->ops;
+	if (ops->get)
+		ops->get (fuqueue);
+	
+	w = task->fuqueue_waiter;
+	_raw_spin_unlock (&task->fuqueue_wait_lock);
+	put_task_struct (task);
+	/* propagate the prio change in a fuqueue-specific fashion */
+	task = ops->waiter_chprio (task, fuqueue, w);
+	if (task == NULL)	     /* no other task to propagate to? */
+		goto out_fuqueue_unlock;
+	/* We were given a task to propagate to, proceed? */
+	get_task_struct (task);
+	_raw_spin_unlock (&fuqueue->lock);
+	if (ops->put)
+		ops->put (fuqueue);
+	goto next;
+
+out_fuqueue_unlock:
+	_raw_spin_unlock (&fuqueue->lock);
+	if (ops->put)
+		ops->put (fuqueue);
+	goto out;
+	
+out_task_unlock:
+	_raw_spin_unlock (&task->fuqueue_wait_lock);
+out_task_put:
+	put_task_struct (task);
+out:
+	return;
+}
+
+/** Cancel @task's wait on @fuqueue and update the wait list priority */
+unsigned __fuqueue_op_waiter_cancel (struct fuqueue *fuqueue,
+				     struct fuqueue_waiter *w)
+{
+	ftrace ("(%p, %p [%d])\n", fuqueue, w, w->task->pid);
+	
+	return plist_del (&fuqueue->wlist, &w->wlist_node);
+}
+
+
+/**
+ * Cancel the wait of a task on a fuqueue and wake it up.
+ *
+ * @task: task whose wait is to be canceled
+ * 
+ * Called by:
+ * - signal_wake_up()
+ * - process_timeout()
+ * - __wake_up_common()
+ * - FIXME
+ * 
+ * when the task they are about to wake is waiting on a
+ * fuqueue. Safely acquires which fuqueue the task is waiting for,
+ * references it, cleans up the task->fuqueue_wait* information, and
+ * then calls the fuqueue specific waiter_cancel() function.
+ *
+ * FIXME: the entry points we get called from don't seem to be all of
+ * them; the perfect thing here would be to hook into
+ * try_to_wake_up()--but is kind of tricky..,
+ *
+ * Note that for this function to actually do anything, the task must
+ * be a task waiting on a fuqueue (so that means TASK_INTERRUPTIBLE
+ * and off the runqueues).
+ */
+void __fuqueue_waiter_cancel (struct task_struct *task, int result)
+{
+	struct fuqueue_ops *ops;
+	struct fuqueue *fuqueue;
+	struct fuqueue_waiter *w;
+	unsigned long flags;
+
+	ftrace ("(%p [%d], %d)\n", task, task->pid, result);
+	
+	local_irq_save (flags);
+	preempt_disable();
+	get_task_struct (task);
+retry:
+	/* Who is the task waiting for? safely acquire and lock it */
+	_raw_spin_lock (&task->fuqueue_wait_lock);
+	fuqueue = task->fuqueue_wait;
+	if (fuqueue == NULL)				/* Ok, not waiting */
+		goto out_task_unlock;
+	if (!_raw_spin_trylock (&fuqueue->lock)) {	/* Spin dance... */
+		_raw_spin_unlock (&task->fuqueue_wait_lock);
+		goto retry;
+	}
+	ops = fuqueue->ops;
+	if (ops->get)
+		ops->get (fuqueue);
+
+	w = task->fuqueue_waiter;
+	
+	/* Do the specific cancel op */
+	ops->waiter_cancel (fuqueue, w);
+	w->result = result;
+	wmb();
+	task->fuqueue_wait = NULL;
+	task->fuqueue_waiter = NULL;
+	_raw_spin_unlock (&task->fuqueue_wait_lock);
+	put_task_struct (task);
+	_raw_spin_unlock (&fuqueue->lock);
+	local_irq_restore (flags);
+	preempt_enable();
+	if (ops->put)
+		ops->put (fuqueue);
+	return;
+		
+out_task_unlock:
+	_raw_spin_unlock (&task->fuqueue_wait_lock);
+	put_task_struct (task);
+	local_irq_restore (flags);
+	preempt_enable();
+	return;
+}
+
+
+/** Fuqueue operations for usage within the kernel */
+struct fuqueue_ops fuqueue_ops = {
+	.get = NULL,
+	.put = NULL,
+	.waiter_cancel = __fuqueue_op_waiter_cancel,
+	.waiter_chprio = __fuqueue_op_waiter_chprio
+};

[RFC/PATCH] FUSYN 4/11: kernel fulocks

[inaky.perez-gonzalez]

These are the "mutexes" for using within kernel space. As
with fuqueues, they also include the stuff to build on top of
them (esentially to perform user space support).

Included is also the addition of to new E* error codes for
denoting a mutex whose owner has died (EOWNERDEAD) or a mutex
that is not recoverable from that situation
(ENOTRECOVERABLE).


 include/asm-alpha/errno.h   |    3 
 include/asm-generic/errno.h |    3 
 include/asm-mips/errno.h    |    3 
 include/asm-parisc/errno.h  |    2 
 include/asm-sparc/errno.h   |    3 
 include/asm-sparc64/errno.h |    3 
 include/linux/fulock.h      |  455 ++++++++++++++++++++++++++
 kernel/fulock.c             |  743 ++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 1215 insertions(+)

--- include/asm-generic/errno.h:1.1.1.1 Thu Jul 10 12:27:27 2003
+++ include/asm-generic/errno.h Thu May 27 00:34:06 2004
@@ -97,4 +97,7 @@
 #define	ENOMEDIUM	123	/* No medium found */
 #define	EMEDIUMTYPE	124	/* Wrong medium type */
 
+#define EOWNERDEAD	125	/* Mutex owner died */
+#define ENOTRECOVERABLE 126	/* Mutex state is not recoverable */
+
 #endif
--- include/asm-mips/errno.h:1.1.1.1 Thu Jul 10 12:27:27 2003
+++ include/asm-mips/errno.h Thu May 27 00:34:06 2004
@@ -111,6 +111,9 @@
 #define ENOMEDIUM	159	/* No medium found */
 #define EMEDIUMTYPE	160	/* Wrong medium type */
 
+#define EOWNERDEAD      161	/* Mutex owner died */
+#define ENOTRECOVERABLE 162	/* Mutex state is not recoverable */
+
 #define EDQUOT		1133	/* Quota exceeded */
 
 #ifdef __KERNEL__
--- include/asm-parisc/errno.h:1.1.1.1 Thu Jul 10 12:27:28 2003
+++ include/asm-parisc/errno.h Thu May 27 00:34:07 2004
@@ -67,6 +67,8 @@
 #define	EREMOTEIO	181	/* Remote I/O error */
 #define	ENOMEDIUM	182	/* No medium found */
 #define	EMEDIUMTYPE	183	/* Wrong medium type */
+#define EOWNERDEAD	184	/* Mutex owner died */
+#define ENOTRECOVERABLE 185	/* Mutex state is not recoverable */
 
 /* We now return you to your regularly scheduled HPUX. */
 
--- include/asm-sparc/errno.h:1.1.1.1 Thu Jul 10 12:27:32 2003
+++ include/asm-sparc/errno.h Thu May 27 00:34:07 2004
@@ -102,4 +102,7 @@
 #define	ENOMEDIUM	125	/* No medium found */
 #define	EMEDIUMTYPE	126	/* Wrong medium type */
 
+#define EOWNERDEAD	127	/* Mutex owner died */
+#define ENOTRECOVERABLE 128	/* Mutex state is not recoverable */
+
 #endif
--- include/asm-sparc64/errno.h:1.1.1.1 Thu Jul 10 12:27:32 2003
+++ include/asm-sparc64/errno.h Thu May 27 00:34:07 2004
@@ -102,4 +102,7 @@
 #define ENOMEDIUM       125     /* No medium found */
 #define EMEDIUMTYPE     126     /* Wrong medium type */
 
+#define EOWNERDEAD	127	/* Mutex owner died */
+#define ENOTRECOVERABLE 128	/* Mutex state is not recoverable */
+
 #endif /* !(_SPARC64_ERRNO_H) */
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ include/linux/fulock.h Tue Jul 20 02:39:07 2004
@@ -0,0 +1,455 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ *
+ * Quickie guide:
+ *
+ * struct fulock = fulock_INIT (&fulock);
+ *
+ * fulock_init (&fulock);
+ * fulock_release (&fulock);
+ * fulock_lock (&fulock, TIMEOUT);
+ * fulock_unlock (&fulock, UNLOCK_TYPE);
+ * fulock_ctl (&fulock, COMMAND)
+ */
+
+#ifndef __linux_fulock_h__
+#define __linux_fulock_h__
+
+/**
+ * User space provided fulock flags
+ *
+ * fulocks/ufulocks are *always* robust, it is up to the caller to
+ * emulate a hang if a robust behavior is not desired. However, the
+ * NOT_RM (not robust mutex) flag is kept and checked on exit and if
+ * there are owned fulocks, a warning will be printed.
+ */
+enum {
+	FULOCK_FL_USER_MK =	0xfffff000, /* Flags provided by user space */
+	FULOCK_FL_PI =		0x80000000, /* Priority inherit */
+	FULOCK_FL_PP =		0x40000000, /* Priority protected */
+	FULOCK_FL_RM_SUN =	0x20000000, /* Robust mutex (sun style) */
+	FULOCK_FL_RM =		0x10000000, /* Robust mutex [warns only] */
+	FULOCK_FL_KCO =		0x08000000, /* No fast path, KCO mode always */
+	__FULOCK_FL_KCO =	FULOCK_FL_KCO | FULOCK_FL_PP,
+	FULOCK_FL_ERROR_CHK =	0x04000000, /* Perform POSIX error checks */
+/* Priority ceiling masks */
+	FULOCK_FL_PP_PLC_MK =	0x00f00000, /* Policy */
+	FULOCK_FL_PP_PRIO_MK =	0x000ff000  /* Priority */
+};
+
+/** Ways to unlock a fulock */
+enum fulock_unlock_type {
+	FULOCK_UNLOCK_SERIAL = 0, /* Transfer ownership to 1st waiter, wake up */
+	FULOCK_UNLOCK_PARALLEL,   /* Unlock fulock, wakeup 1st waiter */
+	FULOCK_UNLOCK_AUTO        /* SERIAL if 1st waiter's prio is RT */
+};
+
+/** Fulock health state */
+enum fulock_st {
+	FULOCK_ST_HEALTHY,   /* Normal, healthy */
+	FULOCK_ST_DEAD,	     /* Some previous owner died */
+	FULOCK_ST_NR	     /* idem, plus cannot be recovered */
+};
+
+
+/** Fulock control actions */
+enum fulock_ctl {
+	FULOCK_CTL_NOP = 0,   /* No-op, just return actual health state */
+	FULOCK_CTL_HEAL,      /* Move from dead to healthy */
+	FULOCK_CTL_NR,	      /* Move from dead to not-recoverable */
+	FULOCK_CTL_RELEASE,   /* Destroy the fulock/ufulock it */
+	FULOCK_CTL_INIT = FULOCK_CTL_RELEASE,
+	FULOCK_CTL_WAITERS,   /* Do we have waiters? */
+	FULOCK_CTL_LOCKED,    /* Is it locked? */
+	FULOCK_CTL_SETPRIOCEIL	/* Set the priority ceiling */
+};
+
+
+/**
+ * vfulock: fulock value in the user space word. Denotes the lock
+ * state and health state of the lock. If it is not this, is the PID
+ * (or cookie) of the owner who fast locked.
+ */
+enum vfulock {
+	VFULOCK_UNLOCKED  = 0x00000000,	/* Unlocked */
+	VFULOCK_HEALTHY	  = VFULOCK_UNLOCKED, /* KCO mode: the lock is healthy */
+	VFULOCK_WP	  = 0xfffffffd,	/* Waiters blocked in the kernel */
+	VFULOCK_DEAD	  = 0xfffffffe,	/* dead, kernel controls ownership */
+	VFULOCK_NR	  = 0xffffffff	/* fulock is not-recoverable */
+};
+
+#ifdef __KERNEL__
+
+#include <linux/config.h>
+#include <linux/fusyn-debug.h>
+
+#ifndef CONFIG_FULOCK
+struct task_struct;
+static inline
+void exit_fulocks(struct task_struct *dummy) {}
+static inline
+void init_fulocks(struct task_struct *dummy) {}
+
+#else /* #ifndef CONFIG_FULOCK */
+
+#include <linux/fuqueue.h>
+#include <linux/plist.h>
+#include <linux/vlocator.h>
+#include <asm/errno.h>
+
+/* Internal fulock flags */
+enum {
+	FULOCK_FL_NR =		0x00000100, /* not recoverable */
+	FULOCK_FL_DEAD =	0x00000200, /* dead-owner */
+	FULOCK_FL_NEEDS_SYNC =	0x00000800, /* Need sync from user space */
+	FULOCK_FL_PP_MK =	0x000000ff  /* raw priority ceiling */
+};
+
+struct fulock;
+
+/** Operations on a fulock. */
+struct fulock_ops 
+{
+	struct fuqueue_ops fuqueue;
+	unsigned (* owner_set) (struct fulock *, struct task_struct *);
+	unsigned (* owner_reset) (struct fulock *);
+	enum fulock_unlock_type (* unlock_type) (int *, struct fulock *,
+						 struct fuqueue_waiter *,
+						 enum fulock_unlock_type,
+						 void *) ;
+	void (* unqueue) (struct fulock *, struct fuqueue_waiter *,
+			  enum fulock_unlock_type, void *);
+	void (* exit) (struct fulock *); /* called from do_exit() context */
+};
+
+/* In-kernel fulock operations */
+extern struct fulock_ops fulock_ops;
+extern struct fulock_ops ufulock_ops;
+extern struct vlocator_ops ufulock_vops;
+
+
+/** A fulock, mutex usable from the kernel. */
+struct fulock {
+	struct fuqueue fuqueue;
+	struct task_struct *owner;
+	unsigned flags;
+	struct plist olist_node;
+};
+
+
+/** Initialize a @fulock with given ops */
+static inline
+void __fulock_init (struct fulock *fulock, struct fulock_ops *ops)
+{
+	__fuqueue_init (&fulock->fuqueue, &ops->fuqueue);
+	fulock->owner = NULL;
+	fulock->flags = 0;
+	plist_init (&fulock->olist_node, BOTTOM_PRIO);
+}
+
+/** Statically initialize a @fulock with given ops */
+#define __fulock_INIT(fulock, fulock_ops) {				\
+	.fuqueue = __fuqueue_INIT (&(fulock)->fuqueue,			\
+				   &(fulock_ops)->fuqueue),		\
+	.owner = NULL,							\
+	.flags = 0,							\
+	.olist_node = plist_INIT (&(fulock)->olist_node, BOTTOM_PRIO)	\
+}
+
+/** Initialize a @fulock for usage within the kernel */
+static inline
+void fulock_init (struct fulock *fulock, int flags)
+{
+	__fulock_init (fulock, &fulock_ops);
+	BUG_ON (flags & FULOCK_FL_PP && flags & FULOCK_FL_PI);
+	fulock->flags = flags;
+}
+
+/** Statically initialize a @fulock for usage within the kernel */
+#define fulock_INIT(fulock) __fulock_INIT (fulock, &fulock_ops)
+
+
+/* Primitives for locking/unlocking/waiting/signalling */
+extern int __fulock_lock (struct fulock *,  struct fuqueue_waiter *,
+			  const struct timeout *);
+extern void __fulock_unlock (struct fulock *fulock,
+			     enum fulock_unlock_type unlock_type, void *);
+extern void __fulock_unlock_unqueue (struct fulock *, struct fuqueue_waiter *,
+				     enum fulock_unlock_type);
+extern int __fulock_ctl (struct fulock *fulock, enum fulock_ctl ctl, void *);
+extern void __fulock_requeue (struct fuqueue *fuqueue,
+			      struct fulock *fulock, void *);
+extern void __fulock_kill_message (struct fulock *);
+extern void exit_fulocks (struct task_struct *task);
+
+/** More internal stuff for building on top of fulock */
+extern void init_fulocks (struct task_struct *);
+extern unsigned __fulock_op_waiter_cancel (struct fuqueue *,
+					   struct fuqueue_waiter *);
+extern struct task_struct * __fulock_op_waiter_chprio (
+	struct task_struct *, struct fuqueue *, struct fuqueue_waiter *);
+extern void fulock_op_unqueue (struct fulock *fulock,
+			       struct fuqueue_waiter *w,
+			       enum fulock_unlock_type unlock_type,
+			       void *priv);
+
+/** Release a fulock -- now it is unusable [use fulock_init()] */
+static inline
+void fulock_release (struct fulock *fulock)
+{
+	__fulock_ctl (fulock, FULOCK_CTL_RELEASE, NULL);
+}
+
+
+/**
+ * Lock a fulock, maybe wait for it to be available.
+ * 
+ * See __fulock_lock() for complete docs.
+ */
+static inline
+int fulock_lock (struct fulock *fulock, const struct timeout *timeout) 
+{
+	struct fuqueue_waiter w = fuqueue_waiter_INIT (current);
+	int result;
+	do {
+		spin_lock_irq (&fulock->fuqueue.lock);
+		result = __fulock_lock (fulock, &w, timeout);
+	} while (result == -EAGAIN);
+	return result;
+}
+
+
+/**
+ * Unlock a fulock, wake up waiter(s)
+ *
+ * @f:	     fulock.
+ * @howmany: Wake up this many waiters; if 0, wake up only one,
+ *	     forcing a serialization in the acquisition of the
+ *	     futex, so that no other task (in user or kernel space)
+ *	     can acquire it.
+ * @returns: Number of tasks woken up, < 0 errno code on error.
+ *
+ * Can be called from any context [I hope].
+ */
+static inline
+void fulock_unlock (struct fulock *fulock,
+		    enum fulock_unlock_type unlock_type)
+{
+	unsigned long flags;
+	
+	ftrace ("(%p, %d)\n", fulock, unlock_type);
+	
+	spin_lock_irqsave (&fulock->fuqueue.lock, flags);
+	__fulock_unlock (fulock, unlock_type, NULL);
+	spin_unlock_irqrestore (&fulock->fuqueue.lock, flags);
+}
+
+
+/**
+ * Requeue a fuqueue to a fulock, maybe make the first one owner.
+ *
+ * Can be called from any context [I hope].
+ */
+static inline
+void fulock_requeue (struct fuqueue *fuqueue, struct fulock *fulock)
+{
+	unsigned long flags;
+	
+	ftrace ("(%p, %p)\n", fuqueue, fulock);
+	
+	spin_lock_irqsave (&fulock->fuqueue.lock, flags);
+	_raw_spin_lock (&fuqueue->lock);
+	if (!__fuqueue_empty (fuqueue))
+		__fulock_requeue (fuqueue, fulock, NULL);
+	_raw_spin_unlock (&fuqueue->lock);
+	spin_unlock_irqrestore (&fulock->fuqueue.lock, flags);
+}
+
+
+/**
+ * Manipulate the state of a fulock
+ *
+ * @f: fulock to set
+ * @ctl: Control command to modify the fulock's state.
+ * @returns: 'enum fulock_st' health state; < 0 errno code on
+ *	     error.
+ *
+ * FIXME: this function set is kind of too convoluted, I am afraid.
+ *
+ * Can be called from only from process context, as it checks for
+ * current being the current owner.
+ */
+static inline
+int fulock_ctl (struct fulock *fulock, enum fulock_ctl ctl)
+{
+	int result;
+	unsigned long flags;
+	ftrace ("(%p, %d)\n", fulock, ctl);
+	
+	spin_lock_irqsave (&fulock->fuqueue.lock, flags);
+	result = __fulock_ctl (fulock, ctl, NULL);
+	spin_unlock_irqrestore (&fulock->fuqueue.lock, flags);
+	return result;
+}
+
+
+/** A ufulock, tied to a user-space vm address. */
+struct ufulock {
+	struct fulock fulock;
+	struct vlocator vlocator;
+	struct page *page;
+};
+
+
+/** @Return true if the fulock @f has no waiters. */
+static inline
+unsigned __fulock_empty (const struct fulock *f)
+{
+	return __fuqueue_empty (&f->fuqueue);
+}
+
+
+/** [Internal] Make task @task the owner of fulock @f. */
+static inline
+unsigned __fulock_op_owner_set (struct fulock *fulock,
+				struct task_struct *task)
+{
+	unsigned prio_changed;
+	
+	ftrace ("(%p, %p [%d])\n", fulock, task, task->pid);
+	
+	fulock->owner = task;
+	prio_changed = plist_add (&task->fulock_olist, &fulock->olist_node);
+	return prio_changed;
+}
+
+
+/** [Internal] Reset ownership of fulock @f. */
+static inline
+unsigned __fulock_op_owner_reset (struct fulock *fulock)
+{
+	unsigned prio_changed;
+	struct task_struct *owner = fulock->owner;
+	
+	ftrace ("(%p)\n", fulock);
+  
+	prio_changed = plist_del (&owner->fulock_olist, &fulock->olist_node);
+	fulock->owner = NULL;
+	return prio_changed;
+}
+
+
+/**
+ * Determine the appropiate way to unlock a fulock.
+ *
+ * @pcode: where to store the wake up code for the waiter
+ * @fulock: fulock being unlocked
+ * @w: waiter that is going to be unblocked to obtain the fulock.
+ * @unlock_type: tentative unlock method selected by the user.
+ * @priv: private pointer for use in an specific way.
+ *
+ * If the waiters comes from a requeue, it will become a serial
+ * unlock, no matter what. If auto, it will depend on if the task to
+ * be given ownership is RT or not (serial for FIFO/RR, normal for
+ * timesharing). 
+ * 
+ * Needs to be inline for ufulock_op_unlock_type() to pick up.
+ */
+static inline
+enum fulock_unlock_type
+fulock_op_unlock_type (int *pcode, struct fulock *fulock,
+		       struct fuqueue_waiter *w,
+		       enum fulock_unlock_type unlock_type, void *priv) 
+{
+	int code;
+	
+	if (w->flags & FUQUEUE_WT_FL_QUEUE) {
+		unlock_type = FULOCK_UNLOCK_SERIAL;
+		code = fulock->flags & FULOCK_FL_DEAD?
+			-EOWNERDEAD : FUQUEUE_WAITER_GOT_LOCK;
+	}
+	else {
+		if (unlock_type == FULOCK_UNLOCK_AUTO)
+			unlock_type = rt_task (w->task)?
+				FULOCK_UNLOCK_SERIAL : FULOCK_UNLOCK_PARALLEL;
+		if (unlock_type == FULOCK_UNLOCK_SERIAL)
+			code = fulock->flags & FULOCK_FL_DEAD? -EOWNERDEAD : 0;
+		else
+			code = -EAGAIN;
+	}
+	*pcode = code;
+	return unlock_type;
+}
+
+
+/** Do we have fast-path support in the arch? */
+enum {
+#ifdef __HAVE_ARCH_CMPXCHG
+	VFULOCK_FAST = 1
+#else
+	VFULOCK_FAST = 0
+#endif
+};
+
+
+/**
+ * Atomic compare and swap with a twist.
+ *
+ * @value     Pointer to the value to compare and swap.
+ * @old_value Value that *value has to have for the swap to occur.
+ * @new_value New value to set it *value == old_value.
+ * @return    !0 if the swap succeeded. 0 if failed.
+ *
+ * Used for locking a vfulock. It exists to wrap arch-specific cache
+ * idiosyncrasies.
+ *
+ * WARNING FIXME: we need a way to handle the idiosyncrasies. Some
+ *                arches have weird cache management schemes that show
+ *                when we modify a kmapped area and user space doesn't
+ *                see the change. This should be hook in here or
+ *                something.
+ */
+static inline
+unsigned vfulock_acas (volatile unsigned *value,
+		       unsigned old_value, unsigned new_value)
+{
+#ifdef __HAVE_ARCH_CMPXCHG
+	unsigned result = cmpxchg (value, old_value, new_value);
+	return result == old_value;
+#else
+	return 0;
+#endif
+}
+
+
+/**
+ * Set an ufulock's associated value.
+ *
+ * @vfulock: Pointer to the address of the ufulock to contain for.
+ * @value:    New value to assign.
+ *
+ * This exists to wrap arch-specific cache idiosyncrasies.
+ *
+ * WARNING FIXME: we need a way to handle the idiosyncrasies. Some
+ *                arches have weird cache management schemes that show
+ *                when we modify a kmapped area and user space doesn't
+ *                see the change. This should be hook in here or
+ *                something.
+ */
+static inline
+void vfulock_set (volatile unsigned *vfulock, unsigned value)
+{
+	*vfulock = value;
+}
+
+#endif /* #ifndef CONFIG_FULOCK */
+#endif /* #ifdef __KERNEL__ */
+#endif /* #ifndef __linux_fulock_h__ */
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ kernel/fulock.c Tue Jul 20 02:40:17 2004
@@ -0,0 +1,743 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ */
+
+#include <linux/fulock.h>
+#include <linux/plist.h>
+#include <linux/time.h>	    /* struct timespec */
+#include <linux/sched.h>
+#include <linux/errno.h>
+
+/* FIXME: TODO: FIFO mode for the waiters list: simply make
+ *              wlist_nodes INT_MAX. */ 
+
+/**
+ * @returns !0 if the ops are those of a fulock or ufulock.
+ *
+ * The compiler will optimize it pretty good.
+ */
+static inline
+unsigned fulock_test_ops (struct fuqueue_ops *ops)
+{
+	if (ops == &fulock_ops.fuqueue)
+		return !0;
+#ifdef CONFIG_UFULOCK
+	if (ops == &ufulock_ops.fuqueue)
+		return !0;
+#endif
+	return 0;
+}
+
+/**
+ * A waiter on this fulock was added, removed or reprioritized and
+ * that caused the wlist priority to change, so we must update the
+ * fulock priority in the owner's ownership list.
+ *
+ * @fulock: The defendant [nossir, I haven't been groklawing]. 
+ * @returns: !0 if the boost priority for the owner was changed.
+ *
+ * It is possible that the lock is not owned if we did a parallel
+ * unlock, so we have to check for that case.
+ * 
+ * WARNING: Needs to be called with IRQs and preemtion disabled.
+ */
+static
+unsigned __fulock_prio_update (struct fulock *fulock)
+{
+	unsigned prio_changed;
+	struct task_struct *owner;
+	int prio;
+	unsigned result = 0;
+
+	ftrace ("(%p)\n", fulock);
+
+	owner = fulock->owner;
+	prio = plist_prio (&fulock->fuqueue.wlist);
+	if (owner == NULL) {
+		prio_changed = plist_prio (&fulock->olist_node) != prio;
+		__plist_chprio (&fulock->olist_node, prio);
+		goto out;
+	}
+	/* reposition this fulock on it's owner's ownership list */
+	_raw_spin_lock (&owner->fulock_olist_lock);
+	prio_changed = plist_chprio (&owner->fulock_olist,
+				     &fulock->olist_node, prio);
+	_raw_spin_unlock (&owner->fulock_olist_lock);
+	/* there is a new maximum on the list? maybe chprio the owner */
+	if (prio_changed)
+		result = __prio_boost (owner, prio);
+out:
+	return prio_changed;
+}
+
+
+
+
+/**
+ * Test if 'current' would deadlock if it waits for a fulock.
+ *
+ * Simple as it is, it looks ugly as hell. Basically, the fulock we
+ * are about to lock will have an owner, so we check the owner; if it
+ * is us, deadlock, if not, we see if the fulock is waiting for
+ * anything; if so, we check it is a fulock, and if so, who's the
+ * owner; if it is us, then deadlock, if not, start again ...
+ *
+ * Now, the trick is to keep the reference counts, and the locks and
+ * all the crap. A single lock for everything would be *so* beautiful
+ * (and not scalable :).
+ * 
+ * @fulock: the fulock to check
+ * @returns: 0 if ok, < 0 errno on error.
+ *
+ * This *should* be safe being lock-less [famous last words].
+ *
+ * WARNING: Needs to be called with IRQs and preemtion disabled.
+ */
+int __fulock_check_deadlock (struct fulock *fulock)
+{
+	int result = 0;
+	struct fuqueue_ops *ops;
+	struct task_struct *owner;
+	struct task_struct *task = current;
+	struct fuqueue *fuqueue;
+	
+	ftrace ("(%p, %p)\n", task, fulock);
+	
+	/* first fulock to trace is already locked and we won't unlock it */
+	owner = fulock->owner;
+	if (owner == NULL)
+		goto out;
+	result = -EDEADLK;
+	if (owner == task)
+		goto out;
+	get_task_struct (owner);
+next:
+	result = 0;
+	/* Who is the owner waiting for? safely acquire and lock it */
+	_raw_spin_lock (&owner->fuqueue_wait_lock);
+	fuqueue = owner->fuqueue_wait;
+	if (fuqueue == NULL)				/* Ok, not waiting */
+		goto out_owner_unlock;
+	if (!_raw_spin_trylock (&fuqueue->lock)) {	/* Spin dance... */
+		_raw_spin_unlock (&owner->fuqueue_wait_lock);
+		goto next;
+	}
+	ops = fuqueue->ops;
+	if (ops->get)
+		ops->get (fuqueue);
+	_raw_spin_unlock (&owner->fuqueue_wait_lock);	
+	put_task_struct (owner);
+	
+	/* Is a fulock whatever the owner is waiting for? */
+	if (!fulock_test_ops (ops))
+		goto out_fuqueue_unlock;
+	fulock = container_of (fuqueue, struct fulock, fuqueue);
+	owner = fulock->owner;		      /* Who's the fulock's owner? */
+	if (unlikely (owner == NULL))	      /* Released before we locked it? */
+		goto out_fuqueue_unlock;	
+	result = -EDEADLK;		      /* It is us? ooops */
+	if (owner == task)
+		goto out_fuqueue_unlock;
+	
+	/* What's the owner waiting for? Proceed to it */
+	get_task_struct (owner);
+	_raw_spin_unlock (&fulock->fuqueue.lock);
+	if (ops->put)
+		ops->put (fuqueue);
+	goto next;
+
+out_owner_unlock:
+	_raw_spin_unlock (&owner->fuqueue_wait_lock);
+	put_task_struct (owner);
+	return result;
+	
+out_fuqueue_unlock:
+	_raw_spin_unlock (&fulock->fuqueue.lock);
+	if (ops->put)
+		ops->put (fuqueue);
+out:
+	return result;
+}
+
+
+/**
+ * Check if a process is allowed to lock a PP fulock.
+ *
+ * @fulock: fulock to check on.
+ * @returns: 0 if ok, errno code on error (disallowed)
+ */
+int __fulock_pp_allowed (struct fulock *fulock)
+{
+#warning FIXME: finish _pp_allowed()
+#if 0
+	int policy = fulock->flags & FULOCK_FL_PP_PLC_MK >> 20;
+	int priority = fulock->flags & FULOCK_FL_PP_PRIO_MK >> 12;
+	int prio;
+
+	if (policy != SCHED_NORMAL)
+		prio = MAX_USER_RT_PRIO - 1 - priority;
+	else
+		prio = priority;
+	fulock->flags &= ~FULOCK_FL_PP_PRIO_MK;
+	fulock->flags |= prio & FULOCK_FL_PP_PRIO_MK;
+#warning FIXME: interaction with PI? Compare against static, not dynamic?
+	if (prio > current->prio)
+		return -EINVAL;
+#endif
+	return -ENOSYS;
+}
+
+
+/**
+ * [Try]lock a fulock
+ *
+ * @fulock: Fulock to lock.
+ * 
+ * @timeout: Pointer on struct describing how long to wait for the
+ *           timeout. If NULL, just trylock (don't block), if ~0, wait
+ *           for ever, otherwise, wait as specified by the pointed to
+ *           struct. 
+ *
+ * @returns: 0	     Acquired the fulock
+ *	     -EOWNERDEAD  Acquired the fulock, some previous owner died.
+ *	     -ENOTRECOVERABLE  Not acquired, fulock is not recoverable
+ *	     -EBUSY  Not acquired, it is locked [and trylock was
+ *		     requested].
+ *	     -EAGAIN Not acquired, try again [FIXME: change this,
+ *		     POSIX uses it for mutexes].
+ *	     *	     Not acquired, error.
+ *
+ * Can ONLY be called from process context. Note unlocks the fulock's
+ * spinlock on return and re-enables IRQs and preemption.
+ *
+ * WARNING: Needs to be called with IRQs and preemtion disabled [the
+ * fuqueue lock acquired with spin_lock_irq()].
+ *
+ * Note that some operations involving flag reading don't need locking
+ * because for changing those values, we calling task needs to be the
+ * owner of the fulock, and once we come out of wait without errors,
+ * we are the owners.
+ */
+int __fulock_lock (struct fulock *fulock,
+		   struct fuqueue_waiter *w,
+		   const struct timeout *timeout)
+{
+	unsigned prio_changed;
+	int result = 0;
+	int prio = BOTTOM_PRIO;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	
+	ftrace ("(%p [flags 0x%x], %p)\n", fulock, fulock->flags, timeout);
+	
+	/* Verify if we can lock */
+	result = -ENOTRECOVERABLE;
+	if (fulock->flags & FULOCK_FL_NR)
+		goto out_unlock;
+	if (fulock->flags & FULOCK_FL_PP
+	    && (result = __fulock_pp_allowed (fulock)))
+		goto out_unlock;
+	if (fulock->owner == NULL)
+		goto its_unlocked;
+	/* Nchts, we have to wait. */
+	result = -EBUSY;
+	if (!timeout)
+		goto out_unlock;
+	if (fulock->flags & (FULOCK_FL_ERROR_CHK | FULOCK_FL_PI)
+	    && (result = __fulock_check_deadlock (fulock)))
+		goto out_unlock;
+	prio_changed = __fuqueue_waiter_queue (&fulock->fuqueue, w);
+	if (prio_changed
+	    && fulock->flags & FULOCK_FL_PI
+	    && __fulock_prio_update (fulock))
+		__fuqueue_waiter_chprio (fulock->owner);
+	return __fuqueue_waiter_block (&fulock->fuqueue, w, timeout);
+
+its_unlocked:		/* whoa! take it, it's free */
+	result = fulock->flags & FULOCK_FL_DEAD? -EOWNERDEAD : 0;
+	_raw_spin_lock (&current->fulock_olist_lock);
+	prio_changed = ops->owner_set (fulock, w->task);
+	if (prio_changed) {
+		/* The ownership list's prio changed, update boost */
+		prio = plist_prio (&fulock->olist_node);
+		__prio_boost (current, prio);
+	}
+	_raw_spin_unlock (&current->fulock_olist_lock);
+out_unlock:
+	_raw_spin_unlock (&fulock->fuqueue.lock);
+	local_irq_enable();
+	preempt_enable();
+	return result;
+}
+
+
+/**
+ * Grunt for the unlock work: take care of the waking up part.
+ *
+ * Unqueue the first waiter and either transfer ownership to it
+ * (serial wake up) or not (parallel). If transferring and the fulock
+ * is PI, propagate the fulock's fuqueue priority to the fulock (to
+ * it's ownership list). Then register the fulock in the new owner's
+ * ownership list and maybe boost him. We always do the boost (not
+ * caring if PI or PP) because if it is neither, the new_oprio would
+ * be INT_MAX, and that will never cause a boost.
+ *
+ * Note we don't need to do a boost propagation; if somebody happens
+ * to wake up the guy before we do, he will see its w->result still
+ * unmodified from INT_MAX and will have to take this fulock's
+ * spinlock to cancel its wait [see __fuqueue_waiter_block()]--he will
+ * have to wait until WE release the spinlock, so he is not able to do
+ * anything that would require a prio boost propagation.
+ *
+ * @unlock_type:
+ *           How to unlock, serialized or parallel.
+ *
+ * NOTE: Assumes the fulock is NOT EMPTY.
+ *       Does not unboost the old owner
+ */
+void __fulock_unlock_unqueue (struct fulock *fulock, struct fuqueue_waiter *w,
+			      enum fulock_unlock_type unlock_type)
+{
+	unsigned wprio_changed, oprio_changed;
+	int new_wprio, new_oprio;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	struct task_struct *new_owner = w->task;
+	
+        wprio_changed = fuqueue_waiter_unqueue (&fulock->fuqueue, w);
+        if (unlock_type == FULOCK_UNLOCK_SERIAL) {
+		if (wprio_changed && fulock->flags & FULOCK_FL_PI) {
+			new_wprio = plist_prio (&fulock->fuqueue.wlist);
+			__plist_chprio (&fulock->olist_node, new_wprio);
+		}
+		_raw_spin_lock (&new_owner->fulock_olist_lock);
+		oprio_changed = ops->owner_set (fulock, new_owner);
+		if (oprio_changed) {			
+			new_oprio = plist_prio (&new_owner->fulock_olist);
+			__prio_boost (new_owner, new_oprio);
+		}
+		_raw_spin_unlock (&new_owner->fulock_olist_lock);
+        }
+}
+
+
+/**
+ * Unlock a fulock, wake up waiter(s) [internal version]
+ *
+ * @fulock: Address for the fulock (kernel space).
+ * @unlock_type: How to unlock, serialized, parallel or auto (serial
+ *               if first waiter is real-time).
+ * @priv: private pointer to pass to different fulock-type specific
+ *        ops.
+ */
+void __fulock_unlock (struct fulock *fulock,
+		      enum fulock_unlock_type unlock_type,
+		      void *priv)
+{
+	int new_oprio, code;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	struct task_struct *old_owner;
+	struct fuqueue_waiter *w;
+        
+	ftrace ("(%p, %d, %p)\n", fulock, unlock_type, priv);
+
+	/* Unlock the fulock */
+	old_owner = fulock->owner;
+	if (old_owner == NULL)		/* Unlocked? */
+		goto out;
+	_raw_spin_lock (&old_owner->fulock_olist_lock);
+	ops->owner_reset (fulock);
+	if (__fulock_empty (fulock))    /* nobody to wake */
+		goto out_unboost;
+	_raw_spin_unlock (&old_owner->fulock_olist_lock);
+
+	/* Get the guy we have to wake up, decide how */
+	w = __fuqueue_first (&fulock->fuqueue);
+	unlock_type = ops->unlock_type (&code, fulock, w, unlock_type, priv);
+	
+	/* (Maybe) transfer ownership, unqueue */
+	ops->unqueue (fulock, w, unlock_type, priv);
+	w->result = code;
+	wmb();
+	wake_up_process (w->task);
+	/* Now we can unboost (if we have to). prio_changed can be
+	 * true only if PI or PP (and the prio actually changed) */
+	_raw_spin_lock (&old_owner->fulock_olist_lock);
+out_unboost:
+	new_oprio = plist_prio (&old_owner->fulock_olist);
+	if (new_oprio != old_owner->prio
+	    && __prio_boost (old_owner, new_oprio))
+		__fuqueue_waiter_chprio (old_owner);
+	_raw_spin_unlock (&old_owner->fulock_olist_lock);
+out:
+	return;
+}
+
+
+/**
+ * Requeue all waiters from a fuqueue to a fulock.
+ *
+ * @fuqueue:      Pointer to the fuqueue.
+ * @fulock:	  Pointer to the fulock.
+ * @fulock_flags: Flags for the fulock.
+ * @returns: 0 if ok, < 0 errno code on error.
+ *
+ * We place all the waiters on the fuqueue in the ufulock's
+ * fuqueue--in such a way that unlock recognizes it is not a fulock
+ * waiter per se.
+ *
+ * We might catch the ufulock is unlocked, this may only happen if we
+ * got the spinlock to the fulock in the middle of a parallel wake up
+ * sequence.
+ * 
+ * USER CONTEXT ONLY
+ *
+ * Expects the fulock spinlocked, IRQs and preemption disabled. The
+ * fuqueue should not be locked.
+ */
+void __fulock_requeue (struct fuqueue *fuqueue,
+		       struct fulock *fulock, void *priv)
+{
+	int code;
+	enum fulock_unlock_type unlock_type = FULOCK_UNLOCK_SERIAL;
+	unsigned prio_changed;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	struct fuqueue_waiter *w;
+	
+	ftrace ("(%p, %p, %p)\n", fuqueue, fulock, priv);
+	
+	/* Move everybody, hop, hop! */
+	prio_changed = plist_splice_init (&fulock->fuqueue.wlist,
+					  &fuqueue->wlist);
+	if (fulock->owner == NULL) {
+		/* Unlocked? Wake up the first guy */
+		w = __fuqueue_first (&fulock->fuqueue);
+		unlock_type = ops->unlock_type (&code, fulock, w,
+						unlock_type, priv);
+		/* Assign/transfer ownership, unqueue */
+		ops->unqueue (fulock, w, unlock_type, priv);
+		w->result = code;
+		wmb();
+		wake_up_process (w->task);
+	}
+	else if (prio_changed
+		 && fulock->flags & FULOCK_FL_PI
+		 && __fulock_prio_update (fulock))
+		__fuqueue_waiter_chprio (fulock->owner);
+	return;
+}
+
+
+/**
+ * Modify/query the internal state of a fulock.
+ *
+ * @fulock: fulock to modify. 
+ * @ctl: control command to issue.
+ * @returns: depending; < 0 errno code on error, 0 if ok, except
+ * health state for CTL_NOP
+ */
+int __fulock_ctl (struct fulock *fulock, enum fulock_ctl ctl, void *priv)
+{
+	int result = 0;
+
+	ftrace ("(%p, %d)\n", fulock, ctl);
+	
+	/* Gather actual state */
+	
+	/* Now, what to do? */
+	switch (ctl) {
+		/* Nothing, so just say how are we standing */
+	case FULOCK_CTL_NOP:
+		if (fulock->flags & FULOCK_FL_NR)
+			result = FULOCK_ST_NR;
+		else if (fulock->flags & FULOCK_FL_DEAD)
+			result = FULOCK_ST_DEAD;
+		else
+			result = FULOCK_ST_HEALTHY;
+		break;
+
+		/* Destroy the fulock--use fulock_init() to re-use */
+	case FULOCK_CTL_RELEASE:
+		__fuqueue_wake (&fulock->fuqueue, (size_t) ~0, -ENOENT);
+		__fulock_unlock (fulock, FULOCK_UNLOCK_SERIAL, priv);
+		fulock->flags |= FULOCK_FL_NR;
+		break;
+		
+		/* Mark it healthy */
+	case FULOCK_CTL_HEAL:
+		result = -EINVAL;
+		if (!(fulock->flags & FULOCK_FL_DEAD))
+			break;
+		result = -EPERM;
+		if (fulock->owner != current)	/* Who are you? */
+			break;
+		fulock->flags &= ~FULOCK_FL_DEAD;
+		result = 0;
+		break;
+		
+	    /* Make it not recoverable; wake up every waiter with error;
+	     * unlock. */ 
+	case FULOCK_CTL_NR:
+		result = -EINVAL;
+		if (!(fulock->flags & FULOCK_FL_DEAD))
+			break;
+		result = -EPERM;
+		if (fulock->owner != current)	/* Who are you? */
+			break;
+		__fuqueue_wake (&fulock->fuqueue, (size_t) ~0, -ENOTRECOVERABLE);
+		__fulock_unlock (fulock, FULOCK_UNLOCK_SERIAL, priv);
+		fulock->flags &= ~FULOCK_FL_DEAD;
+		fulock->flags |= FULOCK_FL_NR;
+		result = 0;
+		break;
+
+		/* Set the prio ceiling */
+	case FULOCK_CTL_SETPRIOCEIL:
+#if 0
+#warning FIXME: this is most probably WRONG
+#warning FIXME: Finish me, set prio ceil
+		result = -EINVAL;
+		if (!(fulock->flags & FULOCK_FL_PP))
+			break;
+		result = -EPERM;
+		if (fulock->owner != current)	/* Who are you? */
+			break;
+		_raw_spin_lock (&owner->fulock_olist_lock);
+		prio = fulock->flags & FULOCK_FL_PP_MK;
+		prio_changed = plist_chprio (&current->fulock_olist,
+					     &fulock->olist_node, prio);
+		_raw_spin_unlock (&owner->fulock_olist_lock);
+		if (prio_changed)
+			__prio_boost (owner, prio);
+#endif
+		result = -ENOSYS;
+		break;	
+		
+	default:
+		result = -EINVAL;
+	}
+	return result;
+}
+
+
+/**
+ * Set the priority of a fulock waiter.
+ *
+ * @task: task to re-prioritize 
+ * @fuqueue: fuqueue of the fulock the task is waiting for [locked]
+ * @w: waiter @task is waiting on in @fuqueue.
+ * @returns: NULL (if there is no need to propagate), task where
+ * propagation would need to continue.	 
+ *
+ * This does not set the prio of the process itself!
+ * 
+ * WARNING: Needs to be called with IRQs and preemtion disabled.
+ */
+struct task_struct * __fulock_op_waiter_chprio (
+	struct task_struct *task, struct fuqueue *fuqueue,
+	struct fuqueue_waiter *w)
+{
+	struct fuqueue_ops *ops;
+	struct fulock *fulock;
+	unsigned prio_changed;
+	
+	ftrace ("(%p [%d], %p, %p)\n", task, task->pid, fuqueue, w);
+	
+	/* Verify this is really a fulock */
+	ops = fuqueue->ops;
+	BUG_ON (!fulock_test_ops (ops));
+	fulock = container_of (fuqueue, struct fulock, fuqueue);
+	/* Update the waiter's position in the fulock's wlist */
+	prio_changed = plist_chprio (&fuqueue->wlist, &w->wlist_node,
+				     task->prio);
+	/* The prio change of the waiter caused the wlist prio to
+	 * change; if we are PI, we change the prio of the fulock AND
+	 * if that changed the prio of the owner, return it. */
+	if (prio_changed
+	    && fulock->flags & FULOCK_FL_PI
+	    && __fulock_prio_update (fulock))
+		return fulock->owner;
+	return NULL;
+}
+
+
+/**
+ * Grunt for the unlock work: unqueue and maybe transfer ownership
+ *
+ * Unqueue the first waiter and either transfer ownership to it
+ * (serial wake up) or not (parallel). If transferring and the fulock
+ * is PI, propagate the fulock's fuqueue priority to the fulock (to
+ * it's ownership list). Then register the fulock in the new owner's
+ * ownership list and maybe boost him. We always do the boost (not
+ * caring if PI or PP) because if it is neither, the new_oprio would
+ * be INT_MAX, and that will never cause a boost.
+ *
+ * Note we don't need to do a boost propagation; if somebody happens
+ * to wake up the guy before we do, he will see its w->result still
+ * unmodified from INT_MAX and will have to take this fulock's
+ * spinlock to cancel its wait [see __fuqueue_waiter_block()]--he will
+ * have to wait until WE release the spinlock, so he is not able to do
+ * anything that would require a prio boost propagation.
+ *
+ * @unlock_type:
+ *           How to unlock, serialized or parallel.
+ *
+ * NOTE: Assumes the fulock is NOT EMPTY.
+ *       Does not unboost the old owner
+ */
+void fulock_op_unqueue (struct fulock *fulock, struct fuqueue_waiter *w,
+			enum fulock_unlock_type unlock_type, void *priv)
+{
+	unsigned wprio_changed, oprio_changed;
+	int new_wprio, new_oprio;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	struct task_struct *new_owner = w->task;
+	
+	ftrace ("(%p, %p, %d, %p)\n", fulock, w, unlock_type, priv);
+	
+        wprio_changed = fuqueue_waiter_unqueue (&fulock->fuqueue, w);
+        if (unlock_type == FULOCK_UNLOCK_SERIAL) {
+		if (wprio_changed && fulock->flags & FULOCK_FL_PI) {
+			new_wprio = plist_prio (&fulock->fuqueue.wlist);
+			__plist_chprio (&fulock->olist_node, new_wprio);
+		}
+		_raw_spin_lock (&new_owner->fulock_olist_lock);
+		oprio_changed = ops->owner_set (fulock, new_owner);
+		if (oprio_changed) {			
+			new_oprio = plist_prio (&new_owner->fulock_olist);
+			__prio_boost (new_owner, new_oprio);
+		}
+		_raw_spin_unlock (&new_owner->fulock_olist_lock);
+        }
+}
+
+
+/**
+ * Initialize fulock specific stuff for a newly cloned task.
+ */
+void init_fulocks (struct task_struct *task)
+{
+	__ftrace (0, "(task %p)\n", task);
+	
+	spin_lock_init (&task->fuqueue_wait_lock);
+	task->fuqueue_wait = NULL;
+	task->fuqueue_waiter = NULL;
+	spin_lock_init (&task->fulock_olist_lock);
+	plist_init (&task->fulock_olist, BOTTOM_PRIO);
+}
+
+
+/**
+ * Mark @fulock as dead and warns if not robust, @returns 0 if it was
+ * dead already, !0 otherwise.
+ */
+void __fulock_kill_message (struct fulock *fulock)
+{
+	if (!(fulock->flags & FULOCK_FL_RM))
+		printk (KERN_WARNING "Task %d [%s] exited holding non-robust "
+			"fulock %p; waiters might block for ever\n",
+			current->pid, current->comm, fulock);	
+}
+
+
+/** Release as dead a @fulock because the owner is exiting. */
+static
+void fulock_op_exit (struct fulock *fulock)
+{
+	ftrace ("(%p)\n", fulock);
+
+	_raw_spin_lock (&fulock->fuqueue.lock);
+	if (fulock->owner == current) {
+		__fulock_kill_message (fulock);
+		__fulock_unlock (fulock, FULOCK_UNLOCK_SERIAL, NULL);
+	}
+	_raw_spin_unlock (&fulock->fuqueue.lock);	  
+}
+
+
+/**
+ * When @task exits, release all the fulocks it holds as dead.
+ *
+ * We have to discriminate between ufulocks and locks; when it is an
+ * ufulock, we just need to see if we have to put() the reference that
+ * the owner had or not (when the ownership is successfully passed to
+ * somebody else, we don't have to put it).
+ */
+#warning FIXME: hook up to exec()?
+void exit_fulocks (struct task_struct *task)
+{
+	struct plist *itr;
+	struct fulock *fulock;
+	struct fulock_ops *ops;
+	unsigned long flags;
+	
+	if (DEBUG > 0 && !plist_empty (&task->fulock_olist))
+		ftrace ("(%p [%d])\n", task, task->pid);
+
+	/* FIXME: there is a better way to do this, but I feel toooo
+	 * thick today -- the problem is fulock->ops->exit() is going
+	 * to take fulock_olist_lock to reset the ownership...so
+	 * whatever it is, we have to call without holding it. */
+	spin_lock_irqsave (&task->fulock_olist_lock, flags);
+	while (!plist_empty (&task->fulock_olist)) {
+		itr = plist_first (&task->fulock_olist);
+		fulock = container_of (itr, struct fulock, olist_node);
+		ops = container_of (fulock->fuqueue.ops,
+				    struct fulock_ops, fuqueue);
+		if (ops->fuqueue.get)
+			ops->fuqueue.get (&fulock->fuqueue);
+		spin_unlock_irqrestore (&task->fulock_olist_lock, flags);
+		
+		ops->exit (fulock);
+		
+		if (ops->fuqueue.put)
+			ops->fuqueue.put (&fulock->fuqueue);
+		spin_lock_irqsave (&task->fulock_olist_lock, flags);
+	}
+	spin_unlock_irqrestore (&task->fulock_olist_lock, flags);
+}
+
+
+/** Cancel @task's wait on @fuqueue and update the wait list priority */
+unsigned __fulock_op_waiter_cancel (struct fuqueue *fuqueue,
+				    struct fuqueue_waiter *w)
+{
+	unsigned prio_changed;
+	struct fulock *fulock =
+		container_of (fuqueue, struct fulock, fuqueue);
+	
+	ftrace ("(%p, %p [%d], %p)\n",
+		fuqueue, w, w->task->pid, w);
+
+	prio_changed = __fuqueue_op_waiter_cancel (fuqueue, w);
+	if (prio_changed && fulock->flags & FULOCK_FL_PI
+	    && __fulock_prio_update (fulock))
+		__fuqueue_waiter_chprio (fulock->owner);
+	return prio_changed;
+}
+
+
+/** Fulock operations */
+struct fulock_ops fulock_ops = {
+	.fuqueue = {
+		.get = NULL,
+		.put = NULL,
+		.waiter_cancel = __fulock_op_waiter_cancel,
+		.waiter_chprio = __fulock_op_waiter_chprio
+	},
+	.owner_set = __fulock_op_owner_set,
+	.owner_reset = __fulock_op_owner_reset,
+	.exit = fulock_op_exit
+};
+
--- include/asm-alpha/errno.h:1.1.1.1 Thu Jul 10 12:27:32 2003
+++ include/asm-alpha/errno.h Thu May 27 00:34:06 2004
@@ -111,4 +111,7 @@
 #define ENOMEDIUM	129	/* No medium found */
 #define EMEDIUMTYPE	130	/* Wrong medium type */
 
+#define EOWNERDEAD	131	/* Mutex owner died */
+#define ENOTRECOVERABLE 132	/* Mutex state is not recoverable */
+
 #endif

[RFC/PATCH] FUSYN 5/11: user space/kernel space tracker

[inaky.perez-gonzalez]

This module provides means to do a refcounted tracking of an
object in kernel space based on a user space virtual
address. Cleanup is automatic when the object count drops to
zero (well, it is delayed).


 include/linux/vlocator.h |  206 ++++++++++++++++++
 kernel/vlocator.c        |  518 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 724 insertions(+)

--- /dev/null	Thu Jul 22 14:30:56 2004
+++ include/linux/vlocator.h Mon Jul 12 18:00:42 2004
@@ -0,0 +1,206 @@
+/*
+ * Generic mapping of kernel objects to user space addresses
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Heavily based on futexes (futex.c), (C) Rusty Russell and Jamie
+ * Lokier's futex key work (actually, in many places it is a shameless
+ * copy)...good invention this GPL thingie :) Blame me for the
+ * mistakes, though.
+ *
+ * Please refer to Documentation/fusyn.txt for more info.
+ *
+ * Stuff to map user space addresses to kernel space objects in a
+ * controlled way. 
+ */
+
+#ifndef __linux_vlocator_h__
+#define __linux_vlocator_h__
+
+#ifdef __KERNEL__
+
+#include <linux/list.h>
+#include <asm/atomic.h>
+#include <linux/mm.h>
+#include <linux/pagemap.h>
+#include <linux/fusyn-debug.h>
+
+/**
+ * Key to track user space addresses by hashing it.
+ *
+ * vlocators are matched on equal values of this key. The key type
+ * depends on whether it's a shared or private mapping.
+ *
+ * offset is aligned to a multiple of sizeof(u32) (== 4) by definition.
+ * We set bit 0 to indicate if it's an inode-based key.
+ */
+union vl_key {
+	struct {
+		unsigned long pgoff;
+		struct inode *inode;
+		int offset;
+	} shared;
+	struct {
+		unsigned long uaddr;
+		struct mm_struct *mm;
+		int offset;
+	} private;
+	struct {
+		unsigned long word;
+		void *ptr;
+		int offset;
+	} both;
+};
+
+
+/* Create a key for a given user space address */
+extern int vl_key_create (struct page **ppage, union vl_key *key,
+			  struct task_struct *task, unsigned long uaddr);
+
+
+/** Get references for @key */
+static inline
+void vl_key_get (union vl_key *key) 
+{
+	if (key->both.offset & 1)
+		atomic_inc (&key->shared.inode->i_count);
+	else
+		atomic_inc (&key->private.mm->mm_count);
+}
+
+
+/**
+ * Drop the references on @key.
+ */
+static inline
+void vl_key_put (union vl_key *key)
+{
+	if (key->both.offset & 1)
+		iput (key->shared.inode);
+	else
+		mmdrop (key->private.mm);
+}
+
+
+/* Get a page [maybe from swap] and pin it */
+extern int vl_page_get (struct page **ppage, struct task_struct *task,
+			struct mm_struct *mm, unsigned long uaddr);
+
+
+/** Put a page [unpin it] */
+static inline
+void vl_page_put (struct page *page) {
+	return put_page (page);
+}
+
+extern int __vl_key_page_get_shared (struct page **ppage, union vl_key *key);
+
+
+/**
+ * Get a page from a vl_key.
+ *
+ * @key: vl_key to bring the page from; needs to be referenced with
+ *       vl_key_get().
+ * @returns 0 if ok, < 0 errno code on error. If -ENOMEM, you can call
+ *          shrink_all_pages() and try again... I guess. 
+ *
+ * This function will pin in physical memory the page that is referred
+ * to by @key, referencing it and blocking modifications to the
+ * mappings it is at.
+ *          
+ * You have to call vl_key_page_put() on the page once done. No
+ * sleeping in between is very recommended.
+ */
+static inline
+int vl_key_page_get (struct page **ppage, union vl_key *key)
+{
+	int result;
+	
+	ftrace ("(%p, %p)\n", ppage, key);	
+	might_sleep();
+	
+	if (key->both.offset & 1) 
+		result = __vl_key_page_get_shared (ppage, key);
+	else {		/* Private mapping */
+		struct mm_struct *mm = key->private.mm;
+		down_read (&mm->mmap_sem);
+		result = vl_page_get (ppage, current, mm, key->private.uaddr);
+		if (unlikely (result < 0))
+			up_read (&mm->mmap_sem);
+	}
+	return result;
+}
+
+
+/** Release @page as mapped in from @key by vl_key_page_get(). */
+static inline
+void vl_key_page_put (struct page *page, union vl_key *key)
+{
+	ftrace ("(%p, %p)\n", page, key);
+	if (key->both.offset & 1) {
+		/* Shared mapping */
+		page_cache_release (page);
+		up (&key->shared.inode->i_mapping->i_shared_sem);
+	}
+	else {
+		/* Private mapping */
+		vl_page_put (page);
+		up_read (&key->private.mm->mmap_sem);
+	}
+}
+
+
+/** Object that can be associated to a user space address */
+struct vlocator {
+	atomic_t refcount;
+	struct list_head hash_list;
+	union vl_key key;
+	const struct vlocator_ops *ops;
+};
+
+
+/** Initialize a vlocator struct */
+static inline
+void vlocator_init (struct vlocator *vlocator)
+{
+	atomic_set (&vlocator->refcount, 0);
+	INIT_LIST_HEAD (&vlocator->hash_list);
+}
+
+
+/** vlocator operations on the items that are to be located. */
+struct vlocator_ops
+{
+	struct vlocator * (* alloc) (void);
+	int (* create) (struct vlocator *,
+			const union vl_key *, unsigned long priv);
+	void (* release) (struct vlocator *);
+	void (* free) (struct vlocator *);
+};
+
+
+/** Reference an vlocator @vlocator. */
+static inline
+void vl_get (struct vlocator *vl) {
+	atomic_inc (&vl->refcount);
+}
+
+
+/** Unreference an @vlocator; return true if it drops to zero. */
+static inline
+unsigned vl_put (struct vlocator *vlocator) {
+	return atomic_dec_and_test (&vlocator->refcount);
+}
+
+
+/* Find a vlocator by key */
+extern int vl_find (struct vlocator **pvl, const union vl_key *key,
+		    const struct vlocator_ops *ops);
+extern int vl_find_or_create (struct vlocator **pvl, const union vl_key *key,
+			      const struct vlocator_ops *ops, unsigned long priv);
+extern void vl_dispose (struct vlocator *vl);
+
+#endif /* #ifdef __KERNEL__ */
+#endif /* #ifndef __linux_vlocator_h__ */
--- /dev/null	Thu Jul 22 14:30:56 2004
+++ kernel/vlocator.c Tue Jul 13 17:34:38 2004
@@ -0,0 +1,518 @@
+
+/*
+ * fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ */
+
+#include <linux/init.h>
+#include <linux/vlocator.h>
+#include <linux/pagemap.h>
+#include <linux/jhash.h>
+#include <linux/fusyn-debug.h>
+
+#define VL_GC_PERIOD 20 /* do garbage collection every 20 seconds */
+#define VL_HASH_BITS 8
+#define VL_HASH_QUEUES (1 << VL_HASH_BITS)
+static struct vl_queue __vl_hash[VL_HASH_QUEUES];
+static struct list_head __vl_disposal = LIST_HEAD_INIT (__vl_disposal); 
+static spinlock_t __vl_disposal_lock = SPIN_LOCK_UNLOCKED;
+
+
+/** @returns a 32 bit hash for @key. */
+static inline
+u32 vl_key_hash (const union vl_key *key)
+{
+	u32 hash = jhash2 (
+		(u32*) &key->both.word,
+		(sizeof (key->both.word) + sizeof (key->both.ptr)) / 4,
+		key->both.offset);
+	return hash;
+}
+
+
+/** @returns true if @key1 and @key2 are equal. */
+static inline
+int vl_key_equal (const union vl_key *key1, const union vl_key *key2)
+{
+	return !memcmp (key1, key2, sizeof (*key1));
+}
+
+
+/**
+ * Low level grunt for getting a page from a shared key.
+ *
+ * @ppage: where to put the pointer to the page.
+ * @key: key to get a page from (has to be referenced with
+ * vl_key_get().
+ * @returns 0 if ok, < 0 errno code on error.
+ *
+ * Do not call directly (use vl_key_page_get()).
+ */
+int __vl_key_page_get_shared (struct page **ppage, union vl_key *key)
+{
+	int result;
+	struct page *page;
+	struct address_space *mapping = key->shared.inode->i_mapping;
+
+	ftrace ("(%p, %p)\n", ppage, key);	
+
+#warning: FIXME: block/lock the mapping...I am not that sure of this
+	down (&mapping->i_shared_sem);
+	page = read_cache_page (mapping, key->shared.pgoff, 
+				(filler_t *) mapping->a_ops->readpage, NULL);
+	result = PTR_ERR (page);
+	if (IS_ERR (page))
+		goto out_up;
+	
+	wait_on_page_locked (page);
+	if (!PageUptodate (page)) {
+		page_cache_release (page);
+		page = ERR_PTR (-EIO);
+	}
+	*ppage = page;
+	return 0;
+
+out_up:
+	up (&mapping->i_shared_sem);
+	return result;
+}
+
+
+/** A hash bucket. */
+struct vl_queue
+{
+	spinlock_t lock;
+	struct list_head queue;
+	unsigned additions;
+};
+
+
+/** Get the hash index for futex_key @k. */
+static inline
+struct vl_queue * vl_hash (const union vl_key *key) {
+	return &__vl_hash[vl_key_hash (key) & (VL_HASH_QUEUES - 1)];
+};
+
+	
+/** Search in a queue. */
+static inline
+struct vlocator * __vl_find (struct vl_queue *vlq,
+			     const union vl_key *key)
+{
+	struct vlocator *vl = NULL;
+	struct list_head *itr;
+
+	list_for_each (itr, &vlq->queue) {
+		vl = container_of (itr, struct vlocator, hash_list);
+		if (vl_key_equal (key, &vl->key))
+			goto out;
+	}
+	vl = NULL;
+out:
+	return vl;
+}
+
+
+/** Search in a queue [backwards - locates faster recent additions]. */
+static inline
+struct vlocator * __vl_find_r (struct vl_queue *vlq,
+			       const union vl_key *key)
+{
+	struct vlocator *vl = NULL;
+	struct list_head *itr;
+
+	list_for_each_prev (itr, &vlq->queue) {
+		vl = container_of (itr, struct vlocator, hash_list);
+		if (vl_key_equal (key, &vl->key))
+			goto out;
+	}
+	vl = NULL;
+out:
+	return vl;
+}
+
+
+/** Append @vlocator to queue @vlq. */ 
+static inline
+void __vl_add (struct vl_queue *vlq, struct vlocator *vl)
+{
+	vlq->additions++;
+	list_add (&vl->hash_list, &vlq->queue);
+}
+
+
+/** Remove @vlocator from queue @vlq if its use count is zero (and
+ * return true). */ 
+static inline
+unsigned __vl_rem (struct vlocator *v)
+{
+	unsigned result = 0, refcount;
+	refcount = atomic_read (&v->refcount);
+	if (refcount == 0) {
+		list_del (&v->hash_list);
+		result = 1;
+	}
+	return result;
+}
+
+
+/**
+ * Pin a page in memory given the user space address.
+ *
+ * @ppage: pointer to where to store the pinned page
+ * @task: task whose address space we have to use.
+ * @uaddr: user space address to pin
+ * @returns: 0 if ok and the page in **ppage, < 0 errno code on
+ *           error.
+ * 
+ * Needs mm->mmap_sem down for read.
+ *
+ * Taken from the original futex code.
+ */
+int vl_page_get (struct page **ppage, struct task_struct *task,
+		 struct mm_struct *mm, unsigned long uaddr)
+{
+	int result = 0;
+	struct page *page;
+	
+	spin_lock (&mm->page_table_lock);
+	page = follow_page (mm, uaddr, 0);
+	if (likely (page != NULL)) {
+		if (!PageReserved (page))
+			get_page (page);
+		*ppage = page;
+		spin_unlock (&mm->page_table_lock);
+		goto out;
+	}
+	spin_unlock (&mm->page_table_lock);
+
+	/* Do it the general way. */
+	result = get_user_pages (task, mm, uaddr, 1, 0, 0, ppage, NULL);
+out:
+	return result;
+}
+
+
+/**
+ * Generate a key for a user space address.
+ *
+ * @ppage: pointer to page struct where the space is. The page has
+ *         been pinned in memory with vl_page_get() and needs a
+ *         vl_page_put() when done.
+ * @key: Pointer to where to store the key. Upon return, the key is
+ *       filled up and has been referenced with vl_key_get().
+ * @task: task that owns the user space address.
+ * @uaddr: user space address
+ * @returns: 0 if ok, < 0 errno code on error.
+ *
+ * Needs to be called with mm->mmap_sem down for read.
+ */
+int vl_key_create (struct page **ppage, union vl_key *key,
+		   struct task_struct *task, unsigned long uaddr)
+{
+	int result, update_shared = 0;
+	struct page *page;
+	struct mm_struct *mm = current->mm;
+	struct vm_area_struct *vma;
+	
+	ftrace ("(%p, %p, %p [%d], %lx)\n",
+		ppage, key, task, task->pid, uaddr);
+
+	/* The futex address must be "naturally" aligned. */
+	key->both.offset = uaddr % PAGE_SIZE;
+	if (unlikely ((key->both.offset % sizeof (u32)) != 0))
+		return -EINVAL;
+	uaddr -= key->both.offset;
+	
+	/*
+	 * The futex is hashed differently depending on whether
+	 * it's in a shared or private mapping.	 So check vma first.
+	 */
+	vma = find_extend_vma (mm, uaddr);
+	result = -EFAULT;
+	if (unlikely (!vma))
+		goto out;
+	/* Permissions. */
+	result = (vma->vm_flags & VM_IO) ? -EPERM : -EACCES;
+	if (unlikely ((vma->vm_flags & (VM_IO|VM_READ)) != VM_READ))
+		goto out;
+	/*
+	 * Private mappings are handled in a simple way.
+	 *
+	 * NOTE: When userspace waits on a MAP_SHARED mapping, even if
+	 * it's a read-only handle, it's expected that futexes attach to
+	 * the object not the particular process.  Therefore we use
+	 * VM_MAYSHARE here, not VM_SHARED which is restricted to shared
+	 * mappings of _writable_ handles.
+	 */
+	result = 0;
+	if (likely (!(vma->vm_flags & VM_MAYSHARE))) {
+		key->private.mm = mm;
+		key->private.uaddr = uaddr;
+		goto out_page_get;
+	}
+	/* Linear file mappings are also simple. */
+	key->shared.inode = vma->vm_file->f_dentry->d_inode;
+	key->both.offset++; /* Bit 0 of offset indicates inode-based key. */
+	if (likely (!(vma->vm_flags & VM_NONLINEAR))) {
+		key->shared.pgoff =
+			(((uaddr - vma->vm_start) >> PAGE_SHIFT)
+			 + vma->vm_pgoff);
+		goto out_page_get;
+	}
+	update_shared = 1;
+out_page_get:
+	result = vl_page_get (&page, current, mm, uaddr);
+	if (unlikely (result < 0))
+		goto out;
+	if (update_shared)
+		key->shared.pgoff =
+			page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
+	vl_key_get (key);
+	*ppage = page;
+out:
+	return result;
+}
+
+
+/**
+ * Find a vlocator in the hash table.
+ * 
+ * @pvl: Pointer to where to store a pointer to the found vlocator.
+ *       
+ * @key: key to locate the item; it has to have been referenced with
+ *       vl_key_get() [vl_key_create() does it].
+ * 
+ * @ops: vl operations structure for verification.
+ * 
+ * @returns 0 if ok and *pvl has the pointer to the vlocator
+ *            corresponding to @key. It has been referenced with
+ *            vl_get() before returning.
+ *            -ENOENT: not found
+ *            -ENOMEM: cannot allocate a new item.
+ *            -EFAULT: if an item was found, but its ops are different
+ *            to the ones provided).
+ *            < 0 errno code on error from ops->create().
+ */
+int vl_find (struct vlocator **pvl, const union vl_key *key,
+	     const struct vlocator_ops *ops)
+{
+	int result = -ENOENT;
+	struct vl_queue *vlq;
+	struct vlocator *vl;
+	
+	ftrace ("(%p, %p, %p)\n", pvl, key, ops);
+
+	/* Is it in the hash already? [do we know about it?] */
+	vlq = vl_hash (key);
+	spin_lock (&vlq->lock);
+	vl = __vl_find (vlq, key);
+	if (unlikely (vl == NULL))
+		goto out_unlock;
+	/* Check the type is correct */
+	result = -EFAULT;
+	if (unlikely (vl->ops != ops))
+		goto out_unlock;
+	result = 0;
+	vl_get (vl);
+	*pvl = vl;
+out_unlock:
+	spin_unlock (&vlq->lock);
+	return result;
+}
+
+
+/**
+ * Find or create a vlocator in the hash table.
+ * 
+ * @pvl: Pointer to where to store a pointer to the found vlocator
+ *       item or the newly allocated and hashed one.
+ *       
+ * @key: key to locate the item; it has to have been referenced with
+ *       vl_key_get() [vl_key_create() does it].
+ * 
+ * @ops: vl operations structure for creation/allocation/freeing.
+ *
+ * @priv: private data passed to ops->create().
+ * 
+ * @returns 0 if ok and *pvl has the pointer to the vlocator
+ *            corresponding to @key. If not found, one is allocated
+ *            and inserted into the hash. In both cases, it has been 
+ *            referenced with vl_get() before returning it.
+ *            -ENOMEM: cannot allocate a new item.
+ *            -EFAULT: if an item was found, but its ops are different
+ *            to the ones provided).
+ *            < 0 errno code on error from ops->create().
+ */
+int vl_find_or_create (struct vlocator **pvl, const union vl_key *key,
+		       const struct vlocator_ops *ops, unsigned long priv)
+{
+	int result;
+	struct vl_queue *vlq;
+	struct vlocator *vl, *vl_alt;
+	unsigned additions0;
+	
+	ftrace ("(%p, %p, %p, %lx)\n", pvl, key, ops, priv);
+	might_sleep();
+	
+	/* Is it in the hash already? [do we know about it?] */
+	vlq = vl_hash (key);
+	spin_lock (&vlq->lock);
+	vl = __vl_find (vlq, key);
+	if (likely (vl != NULL))
+		goto out_check;
+	additions0 = vlq->additions;
+	spin_unlock (&vlq->lock);
+
+	/* Naaah, let's alloc it */
+	result = -ENOMEM;
+	vl = ops->alloc();
+	if (unlikely (vl == NULL))
+		goto out;
+	
+	/* Ok, allocated - did somebody add it while we were allocating?
+	 * [we try to speed up by checking if anybody has added since
+	 * we dropped the lock--we live up with the chance of 4G
+	 * allocations wrapping up the counter in the middle *grin*]. */
+	spin_lock (&vlq->lock);
+	if (additions0 == vlq->additions
+	    || (vl_alt = __vl_find_r (vlq, key)) == NULL) {
+		result = ops->create (vl, key, priv);
+		if (unlikely (result != 0)) {
+			ops->free (vl);
+			goto out_unlock;
+		}
+		vl->ops = ops;
+		__vl_add (vlq, vl);
+		goto out_ref;
+	}
+	/* Allocation collision, get the new one, discard ours */  
+	ops->free (vl);
+	vl = vl_alt;
+out_check:
+	result = -EFAULT;
+	if (unlikely (vl->ops != ops))	/* Check the type is correct */
+		goto out_unlock;
+	result = 0;
+out_ref:
+	vl_get (vl);
+	*pvl = vl;
+out_unlock:
+	spin_unlock (&vlq->lock);
+out:
+	return result;
+}
+
+
+/**
+ * Dispose a vlocator
+ *
+ * When a vlocator is no longer needed, remove it from the hash table
+ * (add it to a delete list so the garbage collector can properly get
+ * rid of it).
+ */
+void vl_dispose (struct vlocator *vl)
+{
+	struct vl_queue *vlq;
+
+	/* In the hash, move it out */
+	vlq = vl_hash (&vl->key);
+	spin_lock (&vlq->lock);
+	list_del (&vl->hash_list);
+	spin_lock (&__vl_disposal_lock);
+	list_add_tail (&vl->hash_list, &__vl_disposal);
+	spin_unlock (&__vl_disposal_lock);
+	spin_unlock (&vlq->lock);
+}
+
+
+/** Work structure for the garbage collector */
+static void vl_garbage_collector (void *);
+DECLARE_WORK(vl_workqueue, vl_garbage_collector, NULL);
+
+
+/**
+ * Do garbage collection (called from the work-queue) and re-arm 
+ *
+ * The most important action is to cleanup the ownership of [u]fulocks
+ * that were assigned to init because the owner died and robustness
+ * was not enabled. This means that only ufulocks get to optionally
+ * suport robustness; kernel based fulocks have to do robustness
+ * always. 
+ */
+
+static 
+void __vl_garbage_collect (struct list_head *purge_list,
+			   struct list_head *list)
+{
+	struct list_head *itr, *nxt;
+	struct vlocator *vl;
+	list_for_each_safe (itr, nxt, list) {
+		vl = container_of (itr, struct vlocator, hash_list);
+		if (__vl_rem (vl))
+			list_add_tail (&vl->hash_list, purge_list);
+	}
+}
+
+static
+void vl_garbage_collector (void *dummy)
+{
+	unsigned cnt;
+	struct vl_queue *vlq;
+	struct list_head purge_list = LIST_HEAD_INIT (purge_list);
+	struct list_head *itr, *nxt;
+	struct vlocator *vl;
+	
+	/* Collect from the vlocator hash: anything with a zero refcount */
+	for (cnt = 0; cnt < VL_HASH_QUEUES; cnt++) {
+		vlq = &__vl_hash[cnt];
+		if (list_empty (&vlq->queue)) /* Some cheating always helps... */
+			continue;
+		spin_lock (&vlq->lock);
+		__vl_garbage_collect (&purge_list, &vlq->queue);
+		spin_unlock (&vlq->lock);
+	}
+	/* Collect the list of stuff marked for disposal */
+	spin_lock (&__vl_disposal_lock);
+	__vl_garbage_collect (&purge_list, &__vl_disposal);
+	spin_unlock (&__vl_disposal_lock);
+	/* Cleanup the collected stuff and re-arm */
+	list_for_each_safe (itr, nxt, &purge_list) {
+		vl = container_of (itr, struct vlocator, hash_list);
+		if (vl->ops->release)
+			vl->ops->release (vl);
+		vl->ops->free (vl);
+	}
+	schedule_delayed_work (&vl_workqueue, VL_GC_PERIOD * HZ);
+}
+
+
+/** Initilize vlocator queue @vlq. */
+static inline
+void vl_queue_init (struct vl_queue *vlq)
+{
+	vlq->lock = SPIN_LOCK_UNLOCKED;
+	INIT_LIST_HEAD (&vlq->queue);
+	vlq->additions = 0;
+}
+
+/** Initialize the vlocator subsystem. */
+static
+int __init vl_subsys_init (void)
+{
+	unsigned i;
+	for (i = 0; i < sizeof (__vl_hash) / sizeof (__vl_hash[0]); i++)
+		vl_queue_init (&__vl_hash[i]);
+	/* Set up the garbage collector to run every 10 seconds */
+	schedule_delayed_work (&vl_workqueue, VL_GC_PERIOD * HZ);
+	return 0;
+}
+__initcall (vl_subsys_init);
+
+

[RFC/PATCH] FUSYN 6/11: user space fuqueues

[inaky.perez-gonzalez]

Support for exporting fuqueues to user space: ufuqueues. Each
is represented by a user space memory word, a vfuqueue.


 ufuqueue.c |  311 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 311 insertions(+)

--- /dev/null	Thu Jul 22 14:30:56 2004
+++ kernel/ufuqueue.c Sat Jul 17 20:32:40 2004
@@ -0,0 +1,311 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ */
+
+#include <linux/sched.h>
+#include <linux/init.h>
+#include <linux/highmem.h>   /* kmap_atomic() */
+#include <linux/vlocator.h>
+#include <linux/fuqueue.h>
+#include <asm/uaccess.h>
+
+static struct fuqueue_ops ufuqueue_ops;
+
+/** Slab for allocation of 'struct ufuqueue's. */
+static kmem_cache_t *ufuqueue_slab;
+
+
+/** Initialize an @ufuqueue (for slab object construction). */
+static inline
+void ufuqueue_ctor (void *obj, kmem_cache_t *slab, unsigned long flags)
+{
+	struct ufuqueue *ufuqueue = obj;
+	__fuqueue_init (&ufuqueue->fuqueue, &ufuqueue_ops);
+	vlocator_init (&ufuqueue->vlocator);
+}
+
+
+/** Allocate an ufuqueue maintaining debug-allocation counts. */
+static inline
+struct vlocator * ufuqueue_vl_op_alloc (void)
+{
+	struct ufuqueue *ufuqueue;
+	ufuqueue = kmem_cache_alloc (ufuqueue_slab, GFP_KERNEL);
+	if (DEBUG > 0 && ufuqueue != NULL)
+		ldebug (1, "ufuqueue %p allocated, total: %d\n",
+			ufuqueue, allocated_inc());
+	return &ufuqueue->vlocator;
+}
+
+
+/**
+ * Create a ufuqueue that is going to be inserted to the hash
+ * [called from vlocator.c:vl_locate() throught the vlocator ops]
+ */
+static
+int ufuqueue_vl_op_create (struct vlocator *vl, const union vl_key *key,
+			   unsigned long priv)
+{
+	memcpy (&vl->key, key, sizeof (*key));
+	return 0;
+}
+
+
+/** Free an ufuqueue maintaining debug-allocation counts. */
+static inline
+void ufuqueue_vl_op_free (struct vlocator *vl)
+{
+	struct ufuqueue *ufuqueue =
+		container_of (vl, struct ufuqueue, vlocator);
+	kmem_cache_free (ufuqueue_slab, ufuqueue);
+	if (DEBUG > 0 && ufuqueue != NULL)
+		ldebug (1, "ufuqueue %p freed, total: %d\n",
+			ufuqueue, allocated_dec());
+}
+
+
+struct vlocator_ops ufuqueue_vl_ops = {
+	.alloc = ufuqueue_vl_op_alloc,
+	.create = ufuqueue_vl_op_create,
+	.release = NULL,
+	.free = ufuqueue_vl_op_free
+};
+
+
+/**
+ * Wait on a fuqueue
+ *
+ * @_vfuqueue: address in user space
+ * @val: value of the _vfuqueue before we entered the kernel
+ * @_timeout: timeout information. ~0 means block for ever.
+ * 
+ * @returns: 0 if ok, < 0 errno code on error. If it returns
+ *           FUQUEUE_WAITER_GOT_LOCK (defined in linux/fuqueue.h) or
+ *           -EOWNERDEAD it means this fuqueue was requeued to a
+ *           fulock and when woken up, it has been assigned ownership
+ *           of the fulock.
+ *
+ * This is just a thin shell that locates the kernel descriptors for
+ * the fuqueue, places the timeout info in place, queues and blocks.
+ */
+asmlinkage
+int sys_ufuqueue_wait (volatile unsigned __user *_vfuqueue, unsigned val,
+		       const struct timeout __user *_timeout)
+{
+	int result = -EINVAL;
+	struct ufuqueue *ufuqueue;
+	struct page *page;
+	unsigned new_val;
+	struct vlocator *vl;
+	union vl_key key;
+	struct timeout *timeout, timeout_kernel;
+	struct fuqueue_waiter w = fuqueue_waiter_INIT (current);
+	struct mm_struct *mm = current->mm;
+	
+		
+	ftrace ("(%p, %x, %p)\n", _vfuqueue, val, _timeout);
+	might_sleep();
+
+	/* We are going to block on the ufuqueue, so get the timeout first */
+	if ((struct timeout *) _timeout == MAX_SCHEDULE_TIMEOUT_EXT)
+		timeout = MAX_SCHEDULE_TIMEOUT_EXT;
+	else {
+		result = -EFAULT;
+		timeout = &timeout_kernel;
+		if (copy_from_user (timeout, _timeout, sizeof (*timeout)))
+			goto error_copy;
+	}
+
+	/* Generate a key for the _vfuqueue, find the ufuqueue for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current, (unsigned long) _vfuqueue);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find_or_create (&vl, &key, &ufuqueue_vl_ops, 0);
+	if (unlikely (result < 0))
+		goto error_find_or_create;
+	ufuqueue = container_of (vl, struct ufuqueue, vlocator);
+
+	/* Queue and check the value hasn't changed */
+	w.flags = FUQUEUE_WT_FL_QUEUE;
+	spin_lock_irq (&ufuqueue->fuqueue.lock);
+	__fuqueue_waiter_queue (&ufuqueue->fuqueue, &w);
+	/* The page is pinned in memory, so we can get_user() without
+	 * atomicity issues--as well, we are sure it is mapped, so no
+	 * errors should happen.
+	 * Now, are we ok with the value? */
+	if (get_user (new_val, _vfuqueue))
+		BUG();
+	if (val != new_val)
+		goto error_wouldblock;
+	vl_page_put (page);
+	up_read (&mm->mmap_sem);
+	/* ok, go ahead and wait (it will unlock and restore irqs/preempt) */
+	result = __fuqueue_waiter_block (&ufuqueue->fuqueue, &w, timeout);
+	vl_put (vl);
+	vl_key_put (&key);
+	return result;
+	
+error_wouldblock:
+	result = -EWOULDBLOCK;
+	__fuqueue_waiter_unqueue (&w);
+	spin_unlock_irq (&ufuqueue->fuqueue.lock);
+	vl_put (vl);
+error_find_or_create:
+	vl_key_put (&key);
+	vl_page_put (page);
+error_key_create:
+	up_read (&mm->mmap_sem);
+error_copy:
+	return result;
+}
+
+	
+/**
+ * Wake up waiters of a fuqueue
+ *
+ * @_vfuqueue: pointer to the fuqueue
+ * @howmany: number of waiters to wake up
+ * @code: code to return to the waiters [default it to zero]
+ * @returns: 0 if ok, < 0 errno code on error.
+ */
+asmlinkage
+int sys_ufuqueue_wake (volatile unsigned __user *_vfuqueue,
+		       size_t howmany, int code)
+{
+	int result;
+	struct mm_struct *mm = current->mm;
+	struct page *page;
+	union vl_key key;
+	struct vlocator *vl;
+	struct ufuqueue *ufuqueue;
+	
+	ftrace ("(%p, %u)\n", _vfuqueue, howmany);
+	might_sleep();
+	
+	/* Generate a key for the _vfuqueue, find the ufuqueue for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current, (unsigned long) _vfuqueue);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find (&vl, &key, &ufuqueue_vl_ops);
+	if (unlikely (result < 0))
+		goto error_find;
+	ufuqueue = container_of (vl, struct ufuqueue, vlocator);
+	/* Wake'em up */
+	spin_lock_irq (&ufuqueue->fuqueue.lock);
+	__fuqueue_wake (&ufuqueue->fuqueue, howmany, code);
+	spin_unlock_irq (&ufuqueue->fuqueue.lock);
+	result = 0;
+	vl_put (vl);
+error_find:
+	vl_key_put (&key);
+	vl_page_put (page);
+error_key_create:
+	up_read (&mm->mmap_sem);
+	return result;
+}
+
+	
+/**
+ * Control operations on a fuqueue
+ *
+ * @_vfuqueue: pointer to the fuqueue
+ * @ctl: control operation on the fuqueue
+ * @returns: 0 if ok, < 0 errno code on error.
+ */
+asmlinkage
+int sys_ufuqueue_ctl (volatile unsigned __user *_vfuqueue, enum fuqueue_ctl ctl)
+{
+	int result;
+	struct mm_struct *mm = current->mm;
+	struct page *page;
+	union vl_key key;
+	struct vlocator *vl;
+	struct ufuqueue *ufuqueue;
+	
+	ftrace ("(%p, %d)\n", _vfuqueue, ctl);
+	might_sleep();
+	
+	/* Generate a key for the _vfuqueue, find the ufuqueue for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current, (unsigned long) _vfuqueue);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find (&vl, &key, &ufuqueue_vl_ops);
+	if (unlikely (result < 0))
+		goto error_find;
+	ufuqueue = container_of (vl, struct ufuqueue, vlocator);
+	/* Check it up */
+	spin_lock_irq (&ufuqueue->fuqueue.lock);
+	switch (ctl) {
+	case FUQUEUE_CTL_RELEASE:
+		vl_dispose (vl);
+		__fuqueue_wake (&ufuqueue->fuqueue, ~0, -ENOENT);
+		result = 0;
+		break;
+	case FUQUEUE_CTL_WAITERS:
+		result = __fuqueue_empty (&ufuqueue->fuqueue)? 0 : 1;
+		break;
+	default:
+		result = -EINVAL;
+		break;
+	}
+	spin_unlock_irq (&ufuqueue->fuqueue.lock);
+	vl_put (vl);
+error_find:
+	vl_key_put (&key);
+	vl_page_put (page);
+error_key_create:
+	up_read (&mm->mmap_sem);
+	return result;
+}
+
+
+/** Initialize the ufuqueue subsystem. */
+static
+int __init subsys_ufuqueue_init (void)
+{
+	ufuqueue_slab = kmem_cache_create ("ufuqueue", sizeof (struct ufuqueue),
+					  0, 0, ufuqueue_ctor, NULL);
+	if (ufuqueue_slab == NULL) 
+		panic ("subsys_ufuqueue_init(): "
+		       "Unable to initialize ufuqueue slab allocator.\n");
+	return 0;
+}
+__initcall (subsys_ufuqueue_init);
+
+
+/* Adaptors for fulock operations */
+static
+void ufuqueue_op_put (struct fuqueue *fuqueue) 
+{
+	struct ufuqueue *ufuqueue =
+		container_of (fuqueue, struct ufuqueue, fuqueue);
+	vl_put (&ufuqueue->vlocator);
+}
+
+static
+void ufuqueue_op_get (struct fuqueue *fuqueue) 
+{
+	struct ufuqueue *ufuqueue =
+		container_of (fuqueue, struct ufuqueue, fuqueue);
+	vl_get (&ufuqueue->vlocator);
+}
+
+/** Ufuqueue operations */
+static
+struct fuqueue_ops ufuqueue_ops = {
+	.get = ufuqueue_op_get,
+	.put = ufuqueue_op_put,
+	.waiter_cancel = __fuqueue_op_waiter_cancel,
+	.waiter_chprio = __fuqueue_op_waiter_chprio
+};

[RFC/PATCH] FUSYN 7/11: user space fulocks

[inaky.perez-gonzalez]

Support for exporting fulocks to user space: ufulocks. Each
is represented by a user space memory word, a vfulock.


 ufulock.c | 1217 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 1217 insertions(+)

--- /dev/null	Thu Jul 22 14:30:56 2004
+++ kernel/ufulock.c Tue Jul 20 02:33:52 2004
@@ -0,0 +1,1217 @@
+
+/*
+ * Fast User real-time/pi/pp/robust/deadlock SYNchronization
+ * (C) 2002-2003 Intel Corp
+ * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
+ *
+ * Licensed under the FSF's GNU Public License v2 or later.
+ *
+ * Based on normal futexes (futex.c), (C) Rusty Russell.
+ * Please refer to Documentation/fusyn.txt for more info.
+ *
+ *
+ * The ufulocks are fulocks with a vlocator to help pinpoint them from
+ * a user space address.
+ *
+ * The vfulock is the value in an address in user space that is
+ * associated to the ufulock. The trick here is to keep them in sync
+ * [__vfulock_sync()]. I think it is doing the right thing when we
+ * know about a ufulock in the kernel and something wipes it to some
+ * crappy value in user space (wild pointer)--however, it cannot be
+ * perfect.
+ *
+ * Mapping the address in user space to the ufulock is done through a
+ * hash table kept by the vlocator.h code - vl_locate() does the full
+ * work; give it an adress, you get a ufulock. No need to worry about
+ * anything else.
+ *
+ * QUICK ROADMAP:
+ *
+ * sys_ufulock_lock(): [try]lock a fulock from user space
+ * sys_ufulock_unlock(): unlock a fulock from user space
+ * sys_ufulock_ctl(): control the state of a ufulock
+ * __ufulock_exit(): called from fulock.c:exit_fulocks() when a
+ *		     process exits and still holds fulocks.
+ *
+ * TODOs:
+ *
+ * - All the #warning FIXME's need to be sorted out
+ * - vfulock_*(), when taking a fulock, should take a ufulock instead
+ *   of a fulock.
+ */
+
+#include <linux/sched.h>
+#include <linux/swap.h>
+#include <linux/highmem.h>
+#include <linux/plist.h>
+#include <asm/uaccess.h>    /* copy_from_user() */
+#include <linux/init.h>
+#include <linux/pagemap.h>
+
+#include <linux/vlocator.h>
+#include <linux/fulock.h>
+
+extern struct vlocator_ops ufuqueue_vl_ops;
+
+/** Slab for allocation of 'struct ufulock's. */
+static kmem_cache_t *ufulock_slab; 
+
+/** fulock operations for user space fulocks */
+struct fulock_ops ufulock_ops;
+
+
+/**
+ * Set @vfulock, maintaining consistency with @fulock.
+ *
+ * We just make sure that whichever value we put doesn't override the
+ * VFULOCK_DEAD or VFULOCK_NR indicators.
+ */
+static inline
+void __vfulock_update (volatile unsigned *vfulock,
+		       const struct fulock *fulock, unsigned value)
+{
+	ftrace ("(%p, %p, %u/%x)\n", vfulock, fulock, value, value);
+	
+	if (fulock->flags & FULOCK_FL_DEAD)
+		value = VFULOCK_DEAD;
+	else if (fulock->flags & FULOCK_FL_NR)
+		value = VFULOCK_NR;
+	vfulock_set (vfulock, value);
+	return;
+}
+
+
+/** @returns true if the @fulock can be made fast-lock */
+static inline
+unsigned __fulock_fast_check (struct fulock *fulock) 
+{
+	if (VFULOCK_FAST == 0)
+		return 0;
+	if (fulock->flags & (FULOCK_FL_DEAD | FULOCK_FL_NR))
+	    return 0;
+	return __fulock_empty (fulock);
+}
+
+
+/** Set an ufulock ownership and increment its use count. */
+static inline
+unsigned __ufulock_op_owner_set (struct fulock *fulock,
+				 struct task_struct *task)
+{
+	unsigned prio_changed;
+	struct ufulock *ufulock;
+	
+	ftrace ("(%p, %p [%d])\n", fulock, task, task->pid);
+	ufulock = container_of (fulock, struct ufulock, fulock);
+	prio_changed = __fulock_op_owner_set (fulock, task);
+	vl_get (&ufulock->vlocator);
+	vl_key_get (&ufulock->vlocator.key);
+	return prio_changed;
+}
+
+
+/** Reset an ufulock ownership and drop its use count. */
+static inline
+unsigned __ufulock_op_owner_reset (struct fulock *fulock)
+{
+	unsigned prio_changed;
+	struct ufulock *ufulock;
+	
+	ufulock = container_of (fulock, struct ufulock, fulock);
+	ftrace ("(%p [ufulock %p])\n", fulock, ufulock);
+	prio_changed = __fulock_op_owner_reset (fulock);
+	vl_key_put (&ufulock->vlocator.key);
+	vl_put (&ufulock->vlocator);
+	return prio_changed;
+}
+
+
+/**
+ * Determine the proper way to unlock a ufulock; update the vfulock
+ * accodingly. 
+ *
+ * @pcode: where to store the wake up code for the waiter
+ * @fulock: fulock being unlocked
+ * @w: waiter that is going to be unblocked to obtain the fulock.
+ * @unlock_type: tentative unlock method selected by the user.
+ * @priv: private pointer for use in an specific way [this is the
+ *        vfulock pointer already kmapped].
+ *        
+ * Note the gimmick: when it is an parallel unlock, we need to declare
+ * the fulock FULOCK_FL_NEEDS_SYNC so the next time somebody gets into
+ * __vfulock_sync_nonkco(), it will properly sync from userspace (as
+ * somebody can, in the meantime, fast-lock it).
+ */
+enum fulock_unlock_type
+ufulock_op_unlock_type (int *pcode, struct fulock *fulock,
+			struct fuqueue_waiter *w,
+			enum fulock_unlock_type unlock_type, void *priv) 
+{
+	volatile unsigned *vfulock = priv;
+
+	ftrace ("(%p, %p, %p, %d, %p)\n",
+		pcode, fulock, w, unlock_type, priv);
+	
+	unlock_type = fulock_op_unlock_type (pcode, fulock, w,
+					     unlock_type, priv);
+	if (unlock_type == FULOCK_UNLOCK_PARALLEL) {
+		*pcode = -EAGAIN;
+		__vfulock_update (vfulock, fulock, VFULOCK_UNLOCKED);
+		fulock->flags |= FULOCK_FL_NEEDS_SYNC;
+	}
+	return unlock_type;
+}
+
+
+/**
+ * Unqueue a waiter and maybe make it owner.
+ *
+ * FIXME: docs
+ * 
+ * As well, takes care of re-enabling fast-path in the ufulock if the
+ * conditions for it are met.
+ */
+void ufulock_op_unqueue (struct fulock *fulock, struct fuqueue_waiter *w,
+			 enum fulock_unlock_type unlock_type, void *priv)
+{
+	volatile unsigned *vfulock = priv;
+	struct fulock_ops *ops =
+		container_of (fulock->fuqueue.ops, struct fulock_ops, fuqueue);
+	struct task_struct *new_owner = w->task;
+
+	ftrace ("(%p, %p, %d, %p)\n", fulock, w, unlock_type, priv);	
+
+	fulock_op_unqueue (fulock, w, unlock_type, NULL);
+	if (unlock_type == FULOCK_UNLOCK_SERIAL) {
+		unsigned new_val;
+		if (!VFULOCK_FAST || fulock->flags & __FULOCK_FL_KCO)
+			new_val = VFULOCK_HEALTHY;
+		else if (__fulock_fast_check (fulock)) { /* enable fast-unlock */
+			new_val = fulock->owner->pid;
+			fulock->flags |= FULOCK_FL_NEEDS_SYNC;
+			_raw_spin_lock (&new_owner->fulock_olist_lock);
+			ops->owner_reset (fulock);
+			_raw_spin_unlock (&new_owner->fulock_olist_lock);
+		}
+		else
+			new_val = VFULOCK_WP;
+		__vfulock_update (vfulock, fulock, new_val);
+	}
+}
+
+
+/** Initialize an @ufulock (for slab object construction). */
+static
+void ufulock_ctor (void *obj, kmem_cache_t *slab, unsigned long flags)
+{
+	struct ufulock *ufulock = obj;
+	__fulock_init (&ufulock->fulock, &ufulock_ops);
+	vlocator_init (&ufulock->vlocator);
+}
+
+
+/** Allocate an ufulock maintaining debug-allocation counts. */
+static inline
+struct vlocator * ufulock_vl_op_alloc (void)
+{
+	struct ufulock *ufulock;
+	ufulock = kmem_cache_alloc (ufulock_slab, GFP_KERNEL);
+	if (DEBUG > 0 && ufulock != NULL)
+		ldebug (2, "ufulock %p allocated, total: %d\n",
+			ufulock, allocated_inc());
+	return &ufulock->vlocator;
+}
+
+
+/**
+ * Create a ufulock that is going to be inserted to the hash
+ * [called from ufu-common.c:ufu_locate()]. Reference its resources
+ * and initialize what is not initialized by the cache constructor.
+ */
+static
+int ufulock_vl_op_create (struct vlocator *vl, const union vl_key *key,
+			  unsigned long priv)
+{
+	struct ufulock *ufulock = container_of (vl, struct ufulock, vlocator);
+
+	ftrace ("(%p, %p, %lx)\n", vl, key, priv);
+	
+	if (!VFULOCK_FAST && (priv & FULOCK_FL_KCO) == 0)
+		return -EINVAL;
+	ufulock->fulock.flags = (priv & FULOCK_FL_USER_MK)
+		| FULOCK_FL_NEEDS_SYNC;
+#warning FIXME: if PP, transform flags from POLICY+PRIO to RAWPRIO.
+	memcpy (&vl->key, key, sizeof (*key));
+	return 0;
+}
+
+
+/** Free an ufulock maintaining debug-allocation counts. */
+static inline
+void ufulock_vl_op_free (struct vlocator *vl)
+{
+	struct ufulock *ufulock = container_of (vl, struct ufulock, vlocator);
+	kmem_cache_free (ufulock_slab, ufulock);
+	if (DEBUG > 0 && ufulock != NULL)
+		ldebug (2, "ufulock %p freed, total: %d\n",
+			ufulock, allocated_dec());
+}
+
+
+struct vlocator_ops ufulock_vl_ops = {
+	.alloc = ufulock_vl_op_alloc,
+	.create = ufulock_vl_op_create,
+	.release = NULL,
+	.free = ufulock_vl_op_free
+};
+
+
+/** @returns expected value of the vfulock given the state of the
+ * @fulock. */ 
+static inline
+unsigned __vfulock_expected_nonkco (struct fulock *fulock)
+{
+	if (fulock->flags & FULOCK_FL_DEAD)
+		return VFULOCK_DEAD;
+	else if (fulock->flags & FULOCK_FL_NR)
+		return VFULOCK_NR;
+	else if (fulock->owner == NULL)
+		return VFULOCK_UNLOCKED;
+	else if (__fulock_empty (fulock))
+		return fulock->owner->pid;
+	else
+		return VFULOCK_WP;
+}
+
+
+/** 
+ * Perform owner identification chores for __vfulock_sync()
+ *
+ * @returns: EBUSY if locked (and the fulock's owner correctly set), 
+ *           -EOWNERDEAD if the owner didn't exist, the current task
+ *           has been made owner and the vfulock/ufulock have been
+ *           marked dead.
+ * 
+ * Probably one of the dirtiest functions I've ever written. The thing
+ * that makes it complex is that after we assign ownership, somebody
+ * the target task might start to exit, and we don't know if it has
+ * gone through exit_fulocks() after we added the fulock to its
+ * ownership list, so we have to be paranoid and check again if the
+ * task is exiting when we take the fulock_olist_lock.
+ *
+ * FIXME: false positives if the PID is reused are the rule. Remedies:
+ *
+ * - The chance of that happening will depend on what the reuse rate is,
+ *   how frequently are we assigning new PIDs and the probability of
+ *   the sucker dying in the middle of it (so a well-coded program
+ *   should be fine, except for the OOM killer, or a crazy process
+ *   killing -9 randomly...).
+ *
+ *   Let's say the probability is P (one in X)
+ *
+ * - Limit PIDs to 64Ki - 3 (to account for _NR, _DEAD and _WP), create
+ *   a 16 bit hash for each task with immutable elements (eg: pointer,
+ *   start time...); compose the hash and the 16 bit pid into a 32 bit
+ *   thing that the user space uses for fast-locking. When id'ing,
+ *   locate the task by PID, hash it out and compare it; if it fails,
+ *   the PID was reused, if not, keep on:
+ *
+ *   (there are still chances of collision, but I think we have cut
+ *   P down by 64Ki)
+ *   
+ * - Check the mm mappings. If the task doesn't have the mapping where
+ *   the fulock is, well, that was a collision (and that was chance,
+ *   probably like shoting up to the sky in the middle of the dessert,
+ *   the bullet falling back to the ground, hitting this man [who
+ *   happened to be wandering around all lost] in the forehead,
+ *   killing him, and it happens he is some rotten-rich guy who had
+ *   randomly chosen somebody on the phone book to pass on all his
+ *   wealth and that one happens to be you).
+ * 
+ * - Now, if the task has the same mapping, we assume it is good.
+ *
+ * I think I cannot be more of a pain in the ass, and probably the
+ * mapping thing is overkill; the hash thing looks like more than
+ * enough, and it is pretty cheap (wasn't computing an exact science?
+ * my flaming bullas).
+ * 
+ * If still not good enough to you, use KCO mode, sacrificing speed.
+ */
+static
+int __fulock_id_owner (struct fulock *fulock, volatile unsigned *vfulock,
+		       unsigned owner_pid, int new_val)
+{
+	int result = EBUSY;
+	struct task_struct *task;
+
+	ftrace ("(%p, %p, %u, %d)\n", fulock, vfulock, owner_pid, new_val);
+	
+	BUG_ON (fulock->owner != NULL);
+	_raw_read_lock (&tasklist_lock);
+	task = find_task_by_pid (owner_pid);
+	if (unlikely (task == NULL || task->flags & PF_EXITING))
+		goto dead_unlock;
+	get_task_struct (task);
+	_raw_read_unlock (&tasklist_lock);
+	
+	_raw_spin_lock (&task->fulock_olist_lock);
+	if (unlikely (task->flags & PF_EXITING)) {
+		_raw_spin_unlock (&task->fulock_olist_lock);
+		put_task_struct (task);
+		goto dead;
+	}
+	__ufulock_op_owner_set (fulock, task);
+	_raw_spin_unlock (&task->fulock_olist_lock);
+	put_task_struct (task);
+	return result;
+
+dead_unlock:
+	_raw_read_unlock (&tasklist_lock);
+dead:
+	result = -EOWNERDEAD;
+	vfulock_set (vfulock, VFULOCK_DEAD);
+	fulock->flags |= FULOCK_FL_DEAD;
+	if (new_val != VFULOCK_UNLOCKED) {
+		_raw_spin_lock (&current->fulock_olist_lock);
+		__ufulock_op_owner_set (fulock, current);
+		_raw_spin_unlock (&current->fulock_olist_lock);
+	}
+	return result;
+}
+
+
+/** 
+ * Sync up a ufulock that supports fast-userspace locking and its associated
+ * vfulock and maybe fast-lock.
+ *
+ * @uf: The ufulock to sync up.
+ * @vfulock: pointer to a kmapped associated value.
+ * @returns: < 0 errno code on error [we did not acquire it]
+ *	     -EOWNERDEAD [previous owner died, we got it]
+ *	     0 if we locked it to a PID (and thus 'current' is owner)
+ *	     > 0 if we didn't lock it, need to proceed to fulock
+ *
+ * Call with uf->fulock.fuqueue.lock held!
+ *
+ * This syncs up the vfulock and the ufulock (if the ufulock is new,
+ * sync from vfulock->ufulock, or the opposite). It tries to leave the
+ * ufulock as it if where a kernel fulock, for the fulock layer to
+ * operate on it.
+ *
+ * When we see VFULOCK_UNLOCKED and move to PID, we don't set the
+ * owner, because there will be nobody coming down to the kernel to
+ * reset it [at any effect, it is like if we had done a user space
+ * fast-lock operation].
+ *
+ * The vfulock can only be modified in the following ways:
+ * - In user space:
+ *   - when fast-locking: VFULOCK_UNLOCKED to PID
+ *   - when fast-unlocking: PID to VFULOCK_UNLOCKED
+ *   - when reinitializing from not-recoverable: VFULOCK_NR to VFULOCK_UNLOCKED
+ *   - Illegally: any other transition [mistake, error, wild pointer]
+ * - In kernel space: When we have the lock over the ufulock
+ *   associated to that vfulock.
+ *
+ * That means that as we are called with the lock held, we can modify
+ * the vfulock at will knowing that nobody is going to touch it as
+ * long as it is not VFULOCK_UNLOCKED (fast-lock), a PID
+ * (fast-unlock)--the not-recoverable case is not of concern because
+ * as soon as anyone sees it, they bail out, so we never get to modify
+ * it.
+ *
+ * Now, for those legal-from-user-space modifications, we operate
+ * atomic; the while(1) loop and vfulock_acas() protect against this.
+ */
+static
+int __vfulock_sync_nonkco (struct ufulock *ufulock, volatile unsigned *vfulock,
+			   unsigned new_val)
+{
+	int result = 0;
+	unsigned val, expected = 0, sync_k2u = 0;
+	struct fulock *fulock = &ufulock->fulock;
+	
+	ftrace ("(%p, %p, %u)\n", ufulock, vfulock, new_val);
+
+	if ((fulock->flags & FULOCK_FL_NEEDS_SYNC) == 0) {
+		sync_k2u = 1;		       /* synch kernel-to-user */
+		expected = __vfulock_expected_nonkco (&ufulock->fulock);
+	}
+	while (1) {
+		val = *vfulock;
+		if (sync_k2u && val != expected) { /* Unexpected changes? */
+			if (expected == VFULOCK_UNLOCKED && val < VFULOCK_WP)
+				goto make_wp;   /* Legal: locked? */
+			if (val == VFULOCK_WP
+			    && expected > VFULOCK_UNLOCKED
+			    && expected < VFULOCK_WP) {
+				result = EBUSY;
+				goto out; 	/* Legal: was cancelled */
+			}
+			if (expected < VFULOCK_WP && val == VFULOCK_UNLOCKED)
+				goto fast_lock; /* Legal: unlocked? */
+			printk (KERN_WARNING "pid %d (%s), ufulock %p: out of "
+				"sync, val %u/0x%x, expected %u/0x%x. "
+				"Fixing.\n", current->pid, current->comm,
+				ufulock, val, val, expected, expected);
+			if (!vfulock_acas (vfulock, val, expected))
+				continue;	/* Illegal: reset it */
+			val = expected;
+		}
+		switch (val) {
+		case VFULOCK_UNLOCKED:	   /* unlocked, fast-lock it */
+fast_lock:
+			if (new_val == VFULOCK_UNLOCKED)
+				goto out;
+			if (__fulock_empty (&ufulock->fulock)) {
+				if (vfulock_acas (vfulock, val, new_val))
+					goto out;
+			}
+			else if (vfulock_acas (vfulock, val, VFULOCK_WP)) {
+				result = EBUSY;
+				goto out_synced;
+			}
+			break;
+		case VFULOCK_DEAD:	       /* idem, but dead owner */
+			fulock->flags |= FULOCK_FL_DEAD;
+		case VFULOCK_WP:	       /* kernel controlled */
+			result = EBUSY;
+			goto out_synced;
+		case VFULOCK_NR:	       /* gee...gone completely */
+			fulock->flags |= FULOCK_FL_NR;
+			result = -ENOTRECOVERABLE;
+			goto out_synced;
+		default:		       /* A PID, locked; no waiters */
+make_wp:
+			if (vfulock_acas (vfulock, val, VFULOCK_WP))
+				goto id_owner;
+		}
+	}
+	
+	/* Id owner, mark as dead if it died */
+id_owner:
+	result = __fulock_id_owner (&ufulock->fulock, vfulock, val, new_val);
+out_synced:
+	fulock->flags &= ~FULOCK_FL_NEEDS_SYNC;
+out:			       /* We are the sole owners of the lock */
+	return result;
+}
+
+
+/**
+ * @returns expected value of the vfulock given the state of the
+ * @fulock for KCO mode fulocks.
+ */ 
+static inline
+unsigned __vfulock_expected_kco (struct fulock *fulock)
+{
+	if (fulock->flags & FULOCK_FL_DEAD)
+		return VFULOCK_DEAD;
+	else if (fulock->flags & FULOCK_FL_NR)
+		return VFULOCK_NR;
+	return VFULOCK_HEALTHY;
+}
+
+
+/**
+ * Synchronize a KCO ufulock with the KCO vfulock in user space.
+ *
+ * KCO ufulocks exist only in kernel space when someone owns them (and
+ * when nobody does, for a while in the cache). When it dissapears, we
+ * need to keep somewhere the state of the fulock (if it was healthy,
+ * dead or not-recoverable). We use the vfulock, and VFULOCK_HEALTHY
+ * (for convenience, the same as VFULOCK_UNLOCKED), VFULOCK_DEAD and
+ * VFULOCK_NR. 
+ *
+ * The checks are just to be a PITA and catch errors; they will also
+ * fix up stuff (being the information in the kernel the authoritative
+ * reference). 
+ */
+static
+int __vfulock_sync_kco (struct ufulock *ufulock, volatile unsigned *vfulock)
+{
+	struct fulock *fulock;
+	int result = EBUSY;
+	unsigned val, new_flags, expected;
+	
+	ftrace ("(%p, %p)\n", ufulock, vfulock);
+
+	fulock = &ufulock->fulock;
+	val = *vfulock;
+	new_flags = fulock->flags & ~FULOCK_FL_NEEDS_SYNC;
+	if ((fulock->flags & FULOCK_FL_NEEDS_SYNC) == 0) {
+		expected = __vfulock_expected_kco (fulock);
+		if (val != expected) {
+			printk (KERN_WARNING "pid %d (%s) (ufulock %p"
+				"): out of sync, val %u/0x%x, "
+				"expected %u/0x%x. Fixing.\n",
+				current->pid, current->comm,
+				ufulock, val, val, expected, expected);
+			__vfulock_update (vfulock, fulock, expected);
+		}
+	}
+	switch (val) {
+	case VFULOCK_HEALTHY:
+		break;
+	case VFULOCK_DEAD:
+		new_flags |= FULOCK_FL_DEAD;
+		break;
+	case VFULOCK_NR:
+		result = -ENOTRECOVERABLE;
+		new_flags |= FULOCK_FL_NR;
+		break;
+		/* Why default to not-recoverable? well somebody
+		 * screwed up the value of this lock, so we can't be
+		 * certain of what was its previous state, so the
+		 * safest thing to do is to kill it left and right.
+		 */
+	default:
+		printk (KERN_WARNING "pid %d (%s) (KCO ufulock %p): "
+			"invalid value 0x%x. Defaulting to not-recoverable.\n",
+			current->pid, current->comm, ufulock, val);
+		__vfulock_update (vfulock, fulock, VFULOCK_NR);
+		__fuqueue_wake (&fulock->fuqueue, (size_t ) ~0,
+				-ENOTRECOVERABLE);
+		__fulock_unlock (fulock, FULOCK_UNLOCK_SERIAL,
+				 (void *) vfulock);
+		new_flags |= FULOCK_FL_NR;
+		result = -ENOTRECOVERABLE;
+	}
+	fulock->flags = new_flags;
+	return result;
+}
+
+
+
+/** @returns expected value of the vfulock given the state of the
+ * @fulock. */ 
+static inline
+unsigned __vfulock_expected (struct fulock *fulock)
+{
+	ftrace ("(%p)\n", fulock);
+
+	return !VFULOCK_FAST || fulock->flags & __FULOCK_FL_KCO?
+		__vfulock_expected_kco (fulock) :
+		__vfulock_expected_nonkco (fulock);
+}
+
+/** 
+ * Sync up a ufulock with the user space vfulock.
+ *
+ * Depending on the type of locking, we go one way or another. In
+ * compile time, wipe out the nonkco path if it is not available for
+ * the architecture (lack of cmpxchg).
+ */
+static inline
+int __vfulock_sync (struct ufulock *ufulock, volatile unsigned *vfulock,
+		    unsigned new_val)
+{
+	ftrace ("(%p, %p, %u)\n", ufulock, vfulock, new_val);
+
+	return !VFULOCK_FAST || ufulock->fulock.flags & __FULOCK_FL_KCO?
+		__vfulock_sync_kco (ufulock, vfulock) :
+		__vfulock_sync_nonkco (ufulock, vfulock, new_val);
+}
+
+
+/** Helper for kmapping the user's vfulock to the kernel. */
+static inline
+volatile unsigned * vfulock_kmap (struct page *page, unsigned long uaddr)
+{
+	ftrace ("(%p, %lx)\n", page, uaddr);
+	return (volatile unsigned *)
+		((unsigned long) kmap_atomic (page, KM_IRQ0)
+		 + uaddr % PAGE_SIZE);
+}
+
+/** Unmap the user's vfulock from the kernel. */
+static inline
+volatile unsigned * vfulock_kunmap (volatile unsigned *vfulock)
+{
+	ftrace ("(%p)\n", vfulock);
+	kunmap_atomic ((void *) (PAGE_MASK & (unsigned long)vfulock), KM_IRQ0);
+}
+	
+
+/**
+ * Lock a ufulock, maybe wait for it to be available.
+ *
+ * @returns: 0 if acquired, < 0 errno code on error.
+ *	     -EAGAIN   Not acquired, try again [change this, conflicst
+ *		       with POSIX]
+ *	     -EBUSY    Not acquired, is locked, didn't block
+ *	     -EBADR    Not acquired, fulock is not recoverable
+ *	     -ESRCH    Acquired, previous owner died, data might be
+ *		       inconsistent
+ *	     *	       Not acquired, error.
+ *
+ * USER CONTEXT ONLY
+ *
+ * What we do is the minimal operations to obtain a fulock that cannot
+ * be distinguished from a kernel-only fulock and then call the fulock
+ * layer for doing the locking.
+ *
+ */
+static
+int ufulock_lock (volatile unsigned __user *_vfulock, unsigned flags,
+		  const struct timeout *timeout)
+{
+	int result;
+	struct ufulock *ufulock;
+	volatile unsigned *vfulock;
+	struct mm_struct *mm = current->mm;
+	struct page *page;
+	union vl_key key;
+	struct vlocator *vl;	
+	struct fuqueue_waiter w = fuqueue_waiter_INIT (current);
+	
+	ftrace ("(%p, %x, %p)\n", _vfulock, flags, timeout);
+	might_sleep();
+
+try_again:
+	/* Generate a key for the _vfulock, find the ufulock for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current, (unsigned long) _vfulock);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find_or_create (&vl, &key, &ufulock_vl_ops, flags);
+	if (unlikely (result < 0))
+		goto error_find_or_create;
+	ufulock = container_of (vl, struct ufulock, vlocator);
+
+	/* Check flags */
+	spin_lock_irq (&ufulock->fulock.fuqueue.lock);
+	result = -EINVAL;
+	if (flags != (ufulock->fulock.flags & FULOCK_FL_USER_MK))
+		goto error_flags;
+	
+	/* sync up kernel and user space, maybe fast-lock */
+	vfulock = vfulock_kmap (page, (unsigned long) _vfulock);
+	result = __vfulock_sync (ufulock, vfulock, current->pid);
+	vfulock_kunmap (vfulock);
+	if (result <= 0)		     /* Error or fast-locked */
+		goto out_unlock;
+	vl_page_put (page);
+	up_read (&mm->mmap_sem);
+	/* This will block, unlock the spinlock and renable IRQs and preempt */
+	result = __fulock_lock (&ufulock->fulock, &w, timeout);
+	vl_put (vl);
+	vl_key_put (&key);
+	if (result == -EAGAIN)
+		goto try_again;
+	return result;
+
+out_unlock:
+error_flags:
+	spin_unlock_irq (&ufulock->fulock.fuqueue.lock);
+	vl_put (vl);
+error_find_or_create:
+	vl_page_put (page);
+	vl_key_put (&key);
+error_key_create:
+	up_read (&mm->mmap_sem);
+	return result;
+}
+
+
+/**
+ * Syscall entry point for ufulock_lock()
+ *
+ * See ufulock_lock() for more info.
+ *
+ * @_vfulock: User space word associated to the ufulock.
+ * @flags: Flags for the fulock (must be constant along its lifetime).
+ * @timeout: Pointer on struct describing how long to wait for the
+ *           timeout. If NULL, just trylock (don't block), if ~0, wait
+ *           for ever, otherwise, wait as specified by the pointed to
+ *           struct. 
+ * @returns: 0 if acquired, < 0 errno code on error.
+ * 
+ * USER CONTEXT ONLY
+ *
+ * This is just a thin shell, gets the timeout information to the
+ * kernel and calls ufulock_lock() who does the hard work.
+ */
+asmlinkage
+int sys_ufulock_lock (volatile unsigned __user *_vfulock, unsigned flags,
+		      const struct timeout __user *_timeout)
+{
+	int result = -EINVAL;
+	struct timeout *timeout, timeout_kernel;
+	
+	ftrace ("(%p, 0x%x, %p)\n", _vfulock, flags, _timeout);
+	might_sleep();
+	
+	/* We might block, so get the timeout first */
+	if (likely ((struct timeout *) _timeout == MAX_SCHEDULE_TIMEOUT_EXT))
+		timeout = MAX_SCHEDULE_TIMEOUT_EXT;
+	else if (_timeout == NULL)
+		timeout = NULL;
+	else {
+		result = -EFAULT;
+		timeout = &timeout_kernel;
+		if (copy_from_user (timeout, _timeout, sizeof (*timeout)))
+			goto out;
+	}
+	result = ufulock_lock (_vfulock, flags, timeout);
+out:
+	return result;
+}
+
+
+/**
+ * Unlock an ufulock, waking up waiter(s)
+ *
+ * @_vfulock:	Address for the fulock (user space).
+ * @howmany: Number of waiters to wake up [see ufulock_unlock()]
+ * @returns: 0 if ok, < 0 errno code on error.
+ *
+ * USER CONTEXT ONLY
+ *
+ * There could be a potential race condition here. We look for a
+ * ufulock associated to _vfulock and if not found, assume there are
+ * no waiters and exit, touching nothing.
+ *
+ * However, if we touch it, setting the vfulock to unlocked
+ * unconditionally (say we are thread A) bad things will happen when
+ * another thread B just comes in, sees it fast-locked (vfulock is
+ * locker's pid), goes into the kernel, sees it unlocked and acquires
+ * it. Then it would set the vfulock to VFULOCK_WP and the original
+ * thread A in this moment sets the vfulock to unlocked -- havoc
+ * happens.
+ *
+ * So that's why we don't do anything. If the vfulock is VFULOCK_WP
+ * and there is no reference to it in the kernel, then that is an
+ * inconsistency, and the next sync() on it will fix it.
+ * 
+ * Last nitpick: if there is fast-paths and the ufulock is empty, that
+ * means somebody is calling the kernel to unlock a fast-locked
+ * vfulock or that somebody cancelled being the only waiter. We update
+ * properly the vfulock to cover that case before unlocking.
+ */
+asmlinkage
+int sys_ufulock_unlock (volatile unsigned __user *_vfulock, unsigned flags,
+			enum fulock_unlock_type unlock_type)
+{
+	struct mm_struct *mm = current->mm;
+	struct vlocator *vl;
+	struct ufulock *ufulock;
+	struct fulock *fulock;
+	struct page *page;
+	union vl_key key;
+	volatile unsigned *vfulock;
+	int result;
+	
+	ftrace ("(%p, 0x%x, %d)\n", _vfulock, flags, unlock_type);
+	
+	/* Generate a key for the _vfulock, find the ufulock for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current,
+				(unsigned long) _vfulock);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find (&vl, &key, &ufulock_vl_ops);
+	if (unlikely (result < 0))
+		goto error_find;
+	ufulock = container_of (vl, struct ufulock, vlocator);
+	fulock = &ufulock->fulock;
+
+	/* Map the vfulock, sync up, perform the unlock */
+	spin_lock_irq (&ufulock->fulock.fuqueue.lock);
+	result = -EINVAL;
+	if (flags != (fulock->flags & FULOCK_FL_USER_MK))
+		goto error_unlock;
+	vfulock = vfulock_kmap (page, (unsigned long) _vfulock);
+	result = __vfulock_sync (ufulock, vfulock, VFULOCK_UNLOCKED);
+	if (unlikely (result < 0))
+		goto error_unmap;
+	
+	/* Unlock */
+	if (VFULOCK_FAST && __fulock_empty (fulock))
+		__vfulock_update (vfulock, fulock, VFULOCK_UNLOCKED);
+	__fulock_unlock (fulock, unlock_type, (void *) vfulock);
+	
+	/* Yalla, done -- release resources and leave */
+	result = 0;
+error_unmap:
+	vfulock_kunmap (vfulock);
+error_unlock:
+	spin_unlock_irq (&ufulock->fulock.fuqueue.lock);
+	vl_put (vl);
+error_find:
+	vl_key_put (&key);
+	vl_page_put (page);
+error_key_create:
+	up_read (&mm->mmap_sem);
+	return result;
+}
+
+
+/**
+ * Requeue all waiters from a ufuqueue to a ufulock.
+ *
+ * @_vfuqueue:  Address for the fuqueue (user space)
+ * @_vfulock:	Address for the fulock (user space).
+ * @fulock_flags: Flags for the fulock.
+ * @returns: 0 if ok, < 0 errno code on error.
+ *
+ * We place all the waiters on the fuqueue in the ufulock's
+ * fuqueue--in such a way that unlock recognizes it is not a fulock
+ * waiter per se.
+ *
+ * If the ufulock is unlocked, wake up the first waiter.
+ *
+ * Tricky thing here: we need to lock the vfulock so while we are
+ * tinkering around nobody can change it. So we tell vfulock_sync() to
+ * lock the vfulock with VFULOCK_WP (any other case will be _DEAD or
+ * _NR and requires the spinlock to operate) and then we do the
+ * requeue op. By virtue of the fulock ops, ufulock_op_unqueue() will
+ * update the vfulock if it has to wake up the first waiter in
+ * fast-path mode, and on the way back, if there are waiters left, it
+ * will makr it _WP.
+ *
+ * This is of course only done if the fuqueue is not empty...no need
+ * to mess things more if it is. 
+ *  
+ * USER CONTEXT ONLY
+ */
+asmlinkage
+int sys_ufulock_requeue (volatile unsigned __user *_vfuqueue,
+			 unsigned val,
+			 volatile unsigned __user *_vfulock,
+			 unsigned fulock_flags)
+{
+	int result;
+	struct mm_struct *mm = current->mm;
+	struct page *page_vfulock, *page_vfuqueue;
+	union vl_key key_vfulock, key_vfuqueue;
+	struct vlocator *vl_vfulock, *vl_vfuqueue;
+	struct ufulock *ufulock;
+	struct ufuqueue *ufuqueue;
+	volatile unsigned *vfulock;
+	unsigned value_vfuqueue;
+	
+	ftrace ("(%p, %u, %p, 0x%x)\n",
+		_vfuqueue, val, _vfulock, fulock_flags);
+
+	down_read (&mm->mmap_sem);
+
+	/* Generate a key for the _vfulock, find the ufulock for it */
+	result = vl_key_create (&page_vfulock, &key_vfulock, current,
+				(unsigned long) _vfulock);
+	if (unlikely (result < 0))
+		goto error_vfulock_key_create;
+	result = vl_find_or_create (&vl_vfulock, &key_vfulock,
+				    &ufulock_vl_ops, fulock_flags);
+	if (unlikely (result < 0))
+		goto error_vfulock_find;
+	ufulock = container_of (vl_vfulock, struct ufulock, vlocator);
+
+	/* Generate a key for the _vfuqueue, find the ufuqueue for it */
+	result = vl_key_create (&page_vfuqueue, &key_vfuqueue, current,
+				(unsigned long) _vfuqueue);
+	if (unlikely (result < 0))
+		goto error_vfuqueue_key_create;
+	result = vl_find (&vl_vfuqueue, &key_vfuqueue, &ufuqueue_vl_ops);
+	if (unlikely (result < 0))
+		goto error_vfuqueue_find;
+	ufuqueue = container_of (vl_vfuqueue, struct ufuqueue, vlocator);
+
+	/* Map the vfulock area and sync the ufulock */
+	spin_lock_irq (&ufulock->fulock.fuqueue.lock);
+	_raw_spin_lock (&ufuqueue->fuqueue.lock);
+	if (__fuqueue_empty (&ufuqueue->fuqueue))
+		goto out_spin_unlock;
+	vfulock = vfulock_kmap (page_vfulock, (unsigned long) _vfulock);
+	result = __vfulock_sync (ufulock, vfulock, VFULOCK_WP);
+	if (unlikely (result < 0))
+		goto error_vfulock_sync;
+	/* The page is pinned in memory, so we can get_user() without
+	 * atomicity issues--as well, we are sure it is mapped, so no
+	 * errors should happen. */
+	if (get_user (value_vfuqueue, _vfuqueue))
+		BUG();
+	result = -EAGAIN;
+	if (value_vfuqueue == val) {
+		result = 0;
+		__fulock_requeue (&ufuqueue->fuqueue, &ufulock->fulock,
+				  (void *) vfulock);
+	}
+error_vfulock_sync:
+	vfulock_kunmap (vfulock);
+out_spin_unlock:
+	_raw_spin_unlock (&ufuqueue->fuqueue.lock);
+	spin_unlock_irq (&ufulock->fulock.fuqueue.lock);
+	vl_put (vl_vfuqueue);
+error_vfuqueue_find:
+	vl_key_put (&key_vfuqueue);
+	vl_page_put (page_vfuqueue);
+error_vfuqueue_key_create:
+	vl_put (vl_vfulock);
+error_vfulock_find:
+	vl_key_put (&key_vfulock);
+	vl_page_put (page_vfulock);
+error_vfulock_key_create:
+	up_read (&mm->mmap_sem);
+	return result;
+}
+
+
+/**
+ * Run a control command on a fulock.
+ *
+ * @_vfulock: Location of the fulock in user space
+ * @flags: flags for the fulock
+ * @ctl: Command to run (enum fulock_ctl).
+ * @returns: >= 0 previous consistency before the change (enum fulock_st).
+ *	     < 0 errno code on error.
+ *
+ * USER CONTEXT ONLY
+ */
+asmlinkage
+int sys_ufulock_ctl (unsigned __user *_vfulock, unsigned flags, unsigned ctl)
+{
+	int result;
+	struct mm_struct *mm = current->mm;
+	struct page *page;
+	union vl_key key;
+	struct vlocator *vl;
+	struct ufulock *ufulock;
+	struct fulock *fulock;
+	unsigned new_value;
+	volatile unsigned *vfulock;
+	
+	ftrace ("(%p, 0x%x, %u)\n", _vfulock, flags, ctl);
+	might_sleep();
+
+	/* Generate a key for the _vfulock, find the ufulock for it */
+	down_read (&mm->mmap_sem);
+	result = vl_key_create (&page, &key, current,
+				(unsigned long) _vfulock);
+	if (unlikely (result < 0))
+		goto error_key_create;
+	result = vl_find_or_create (&vl, &key, &ufulock_vl_ops, flags);
+	if (unlikely (result < 0))
+		goto error_find_or_create;
+	ufulock = container_of (vl, struct ufulock, vlocator);
+	fulock = &ufulock->fulock;
+
+	/* make sure flags are consistent */
+	spin_lock_irq (&fulock->fuqueue.lock);
+	result = -EINVAL;
+	if (flags != (fulock->flags & FULOCK_FL_USER_MK))
+		goto error_unlock;
+	
+	/* Map the user space area and sync */
+	vfulock = vfulock_kmap (page, (unsigned long) _vfulock);
+	result = __vfulock_sync (ufulock, vfulock, VFULOCK_UNLOCKED);
+	if (result < 0)
+		goto error_unlock;
+	
+	/* Ugly special case numero uno: destruction; can't really
+	 * destroy it (somebody might be using it still), but we can
+	 * disconnect it from the hash until the gc destroys it. */
+	if (ctl == FULOCK_CTL_RELEASE) {
+		vl_dispose (vl);
+		result = __fulock_ctl (&ufulock->fulock, ctl,
+				       (void *) vfulock);
+		vfulock_set (vfulock, VFULOCK_UNLOCKED);
+		goto out_kunmap;
+	}	
+	/* Ugly special case numero two: do we have waiters? */
+	if (ctl == FULOCK_CTL_WAITERS) {
+		result = __fulock_empty (fulock)? 0 : 1;
+		goto out_kunmap;
+	}
+	/* Ugly special case number three: is it locked? */
+	if (ctl == FULOCK_CTL_LOCKED) {
+		result = fulock->owner == NULL? 0 : 1;
+		goto out_kunmap;
+	}
+	
+	/* Ok, the command can go down to the fulock layer */
+	result = __fulock_ctl (fulock, ctl, (void *) vfulock);
+	if (result < 0)
+		goto out_kunmap;
+	/* Ok, update the vfulock if so is needed */
+	switch (ctl) {
+	case FULOCK_CTL_HEAL:
+		if (!VFULOCK_FAST || (fulock->flags & __FULOCK_FL_KCO))
+			new_value = VFULOCK_HEALTHY;
+		else if (__fulock_empty (fulock)) {
+			struct task_struct *owner = fulock->owner;
+			new_value = current->pid;
+			fulock->flags |= FULOCK_FL_NEEDS_SYNC;
+			_raw_spin_lock (&owner->fulock_olist_lock);
+			__ufulock_op_owner_reset (fulock);
+			_raw_spin_unlock (&owner->fulock_olist_lock);
+		}
+		else
+			new_value = VFULOCK_WP;
+		vfulock_set (vfulock, new_value);
+		break;
+	case FULOCK_CTL_NR:
+		new_value = VFULOCK_NR;
+		vfulock_set (vfulock, new_value);
+		break;		      
+	default:
+		new_value = 0; /* shut gcc up */
+		result = -ENOSYS;
+	}
+out_kunmap:
+	vfulock_kunmap (vfulock);
+error_unlock:
+	spin_unlock_irq (&fulock->fuqueue.lock);
+	vl_put (vl);
+error_find_or_create:
+	vl_key_put (&key);
+	vl_page_put (page);
+error_key_create:
+	up_read (&mm->mmap_sem);
+	return result;	      
+}
+
+
+/**
+ * Release as dead @ufulock because the owner is exiting.
+ *
+ * This will basically mark the ufulock dead, then set the vfulock to
+ * VFULOCK_DEAD and finally do the proper exit operation. 
+ */
+void ufulock_op_exit (struct fulock *fulock)
+{
+	int result, retry_count = 5;
+	struct ufulock *ufulock;
+	unsigned long flags;
+	union vl_key key;
+	struct page *page = NULL;
+	char *page_kmap;
+	volatile unsigned *vfulock;
+	
+	ftrace ("(%p)\n", fulock);
+
+	/* Fast path: the ufulock is dead already */
+	ufulock = container_of (fulock, struct ufulock, fulock);
+	spin_lock_irqsave (&fulock->fuqueue.lock, flags);
+	__fulock_kill_message (fulock);
+	memcpy (&key, &ufulock->vlocator.key, sizeof (key));
+	vl_key_get (&key);
+	spin_unlock_irqrestore (&fulock->fuqueue.lock, flags);
+retry:
+	result = vl_key_page_get (&page, &key);
+	if (result < 0)
+		goto handle_error;
+
+	spin_lock_irqsave (&fulock->fuqueue.lock, flags);
+	if (fulock->owner != current) /* Okay, somebody did it... */
+		goto out_unlock;
+	fulock->flags |= FULOCK_FL_DEAD;
+	page_kmap = kmap_atomic (page, KM_IRQ0);
+	vfulock = (volatile unsigned *) (page_kmap + (key.both.offset & ~1));
+	__fulock_unlock (fulock, FULOCK_UNLOCK_SERIAL, (void *) vfulock);
+	vfulock_set (vfulock, VFULOCK_DEAD);
+	kunmap_atomic (page_kmap, KM_IRQ0);
+out_unlock:
+	spin_unlock_irqrestore (&fulock->fuqueue.lock, flags);
+	vl_key_page_put (page, &key);
+	vl_key_put (&key);	
+	return;
+
+	/* On memory shortage, we retry a few times, then give up. */
+handle_error:
+	switch (result) {
+	case -EFAULT:
+		printk (KERN_WARNING
+			"Task %d [%s] seems to have removed the memory "
+			"mapping that contained the mutex it owns at 0x%lx; "
+			"this is an application bug. Expect data corruption "
+			"(got error %d)\n", current->pid, current->comm,
+			key.private.uaddr, result);
+		break;
+	case -ENOMEM:
+		shrink_all_memory (4);
+		if (retry_count--)
+			goto retry;
+		/* Fall through */
+	default:
+		printk (KERN_WARNING
+			"Task %d [%s]: error %d while trying to mark fulock "
+			"%p as dead in user space. Expect data corruption.\n",
+			current->pid, current->comm, result, fulock);
+		break;
+	}
+	fulock_ctl (fulock, FULOCK_CTL_NR);
+	vl_key_put (&key);	
+	return;
+}
+
+
+/**
+ * Cancel @task's wait on the ufulock
+ *
+ * We don't re-enable fast-lock. We are under a spinlock and it'd be a
+ * pain--the low ocurrence rate of this case is probably not enough to
+ * justify the bloat that it would incur.
+ */
+unsigned __ufulock_op_waiter_cancel (struct fuqueue *fuqueue,
+				     struct fuqueue_waiter *w)
+{
+	unsigned prio_changed;
+	ftrace ("(%p, %p [%d], %p)\n", fuqueue, w, w->task->pid, w);
+	prio_changed = __fulock_op_waiter_cancel (fuqueue, w);
+	return prio_changed;
+}
+
+
+/* Adaptors for fulock operations */
+static
+void ufulock_op_put (struct fuqueue *fuqueue) 
+{
+	struct fulock *fulock =
+		container_of (fuqueue, struct fulock, fuqueue);
+	struct ufulock *ufulock =
+		container_of (fulock, struct ufulock, fulock);
+	vl_put (&ufulock->vlocator);
+}
+
+
+static
+void ufulock_op_get (struct fuqueue *fuqueue) 
+{
+	struct fulock *fulock =
+		container_of (fuqueue, struct fulock, fuqueue);
+	struct ufulock *ufulock =
+		container_of (fulock, struct ufulock, fulock);
+	vl_get (&ufulock->vlocator);
+}
+
+
+/** ufulock fulock operations */
+struct fulock_ops ufulock_ops = {
+	.fuqueue = {
+		.get = ufulock_op_get,
+		.put = ufulock_op_put,
+		.waiter_cancel = __ufulock_op_waiter_cancel,
+		.waiter_chprio = __fulock_op_waiter_chprio
+	},
+	.owner_set = __ufulock_op_owner_set,
+	.owner_reset = __ufulock_op_owner_reset,
+	.unlock_type = ufulock_op_unlock_type,
+	.unqueue = ufulock_op_unqueue,
+	.exit = ufulock_op_exit,
+};
+
+
+/**
+ * Initialize the ufulock subsystem.
+ */
+static
+int __init subsys_ufulock_init (void)
+{
+	ufulock_slab = kmem_cache_create ("ufulock", sizeof (struct ufulock),
+					  0, 0, ufulock_ctor, NULL);
+	if (ufulock_slab == NULL) 
+		panic ("subsys_ufulock_init(): "
+		       "Unable to initialize ufulock slab allocator.\n");
+	return 0;
+}
+__initcall (subsys_ufulock_init);

[RFC/PATCH] FUSYN 8/11: Arch-specific support

[inaky.perez-gonzalez]

These are the system call hooks of the ufuqueues and ufulocks
for the different architectures we (or somebody else) has
tried this on. So far, the list is i386, ia64, PPC and
PPC64.

The last three ones haven't been tested that much for 2.3, but
nothing should have changed in that matter since release 2.2.


 arch/i386/kernel/entry.S   |    7 +++++++
 arch/ia64/kernel/entry.S   |   14 +++++++-------
 arch/ppc/kernel/misc.S     |    9 ++++++++-
 arch/ppc64/kernel/misc.S   |    7 +++++++
 include/asm-i386/unistd.h  |    9 ++++++++-
 include/asm-ia64/unistd.h  |    9 ++++++++-
 include/asm-ppc/unistd.h   |    9 ++++++++-
 include/asm-ppc64/unistd.h |    9 ++++++++-
 kernel/sys.c               |    6 ++++++
 9 files changed, 67 insertions(+), 12 deletions(-)

--- include/asm-i386/unistd.h:1.1.1.8 Tue Apr 6 01:51:33 2004
+++ include/asm-i386/unistd.h Sat Jul 17 19:34:37 2004
@@ -279,8 +279,15 @@
 #define __NR_utimes		271
 #define __NR_fadvise64_64	272
 #define __NR_vserver		273
+#define __NR_ufulock_lock	274
+#define __NR_ufulock_unlock	275
+#define __NR_ufulock_ctl	276
+#define __NR_ufulock_requeue	277
+#define __NR_ufuqueue_wait	278
+#define __NR_ufuqueue_wake	279
+#define __NR_ufuqueue_ctl	280
 
-#define NR_syscalls 274
+#define NR_syscalls 281
 
 /* user-visible error numbers are in the range -1 - -124: see <asm-i386/errno.h> */
 
--- include/asm-ia64/unistd.h:1.1.1.7 Tue Apr 6 00:22:52 2004
+++ include/asm-ia64/unistd.h Sat Jul 17 19:42:54 2004
@@ -251,10 +251,17 @@
 #define __NR_reserved1			1259	/* reserved for NUMA interface */
 #define __NR_reserved2			1260	/* reserved for NUMA interface */
 #define __NR_reserved3			1261	/* reserved for NUMA interface */
+#define __NR_ufulock_lock		1262
+#define __NR_ufulock_unlock		1263
+#define __NR_ufulock_ctl		1264
+#define __NR_ufulock_requeue		1265
+#define __NR_ufuqueue_wait		1266
+#define __NR_ufuqueue_wake		1267
+#define __NR_ufuqueue_ctl		1268
 
 #ifdef __KERNEL__
 
-#define NR_syscalls			256 /* length of syscall table */
+#define NR_syscalls			263 /* length of syscall table */
 
 #if !defined(__ASSEMBLY__) && !defined(ASSEMBLER)
 
--- include/asm-ppc/unistd.h:1.1.1.4 Tue Apr 6 00:22:57 2004
+++ include/asm-ppc/unistd.h Sat Jul 17 19:42:55 2004
@@ -260,8 +260,15 @@
 #define __NR_fstatfs64		253
 #define __NR_fadvise64_64	254
 #define __NR_rtas		255
+#define __NR_ufulock_lock	256
+#define __NR_ufulock_unlock	257
+#define __NR_ufulock_ctl	258
+#define __NR_ufulock_requeue	259
+#define __NR_ufuqueue_wait	260
+#define __NR_ufuqueue_wake	261
+#define __NR_ufuqueue_ctl	262
 
-#define __NR_syscalls		256
+#define __NR_syscalls		263
 
 #define __NR(n)	#n
 
--- include/asm-ppc64/unistd.h:1.1.1.4 Tue Apr 6 00:22:57 2004
+++ include/asm-ppc64/unistd.h Sat Jul 17 19:42:55 2004
@@ -266,8 +266,15 @@
 #define __NR_fstatfs64		253
 #define __NR_fadvise64_64	254
 #define __NR_rtas		255
+#define __NR_ufulock_lock	256
+#define __NR_ufulock_unlock	257
+#define __NR_ufulock_ctl	258
+#define __NR_ufulock_requeue	259
+#define __NR_ufuqueue_wait	260
+#define __NR_ufuqueue_wake	261
+#define __NR_ufuqueue_ctl	262
 
-#define __NR_syscalls		256
+#define __NR_syscalls		263
 #ifdef __KERNEL__
 #define NR_syscalls	__NR_syscalls
 #endif
--- arch/i386/kernel/entry.S:1.1.1.13 Tue Apr 6 01:51:19 2004
+++ arch/i386/kernel/entry.S Sat Jul 17 19:34:13 2004
@@ -882,5 +882,12 @@
 	.long sys_utimes
  	.long sys_fadvise64_64
 	.long sys_ni_syscall	/* sys_vserver */
+	.long sys_ufulock_lock
+	.long sys_ufulock_unlock	/* 275 */
+	.long sys_ufulock_ctl
+	.long sys_ufulock_requeue     
+	.long sys_ufuqueue_wait
+	.long sys_ufuqueue_wake		/* 279 */  	     
+	.long sys_ufuqueue_ctl
 
 syscall_table_size=(.-sys_call_table)
--- kernel/sys.c:1.1.1.13 Tue Apr 6 01:51:37 2004
+++ kernel/sys.c Wed May 26 22:14:57 2004
@@ -260,6 +260,12 @@
 cond_syscall(sys_shmget)
 cond_syscall(sys_shmdt)
 cond_syscall(sys_shmctl)
+cond_syscall(sys_ufuqueue_wait)
+cond_syscall(sys_ufuqueue_wake)
+cond_syscall(sys_ufulock_lock)
+cond_syscall(sys_ufulock_unlock)
+cond_syscall(sys_ufulock_ctl)
+cond_syscall(sys_ufulock_requeue)
 
 /* arch-specific weak syscall entries */
 cond_syscall(sys_pciconfig_read)
--- arch/ia64/kernel/entry.S:1.1.1.8 Tue Apr 6 00:21:45 2004
+++ arch/ia64/kernel/entry.S Sat Jul 17 19:42:55 2004
@@ -1504,13 +1504,13 @@
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall			// 1260
 	data8 sys_ni_syscall
-	data8 sys_ni_syscall
-	data8 sys_ni_syscall
-	data8 sys_ni_syscall
-	data8 sys_ni_syscall			// 1265
-	data8 sys_ni_syscall
-	data8 sys_ni_syscall
-	data8 sys_ni_syscall
+	data8 sys_ufulock_lock
+	data8 sys_ufulock_unlock
+	data8 sys_ufulock_ctl
+	data8 sys_ufulock_requeue		// 1265
+	data8 sys_ufuqueue_wait
+	data8 sys_ufuqueue_wake
+	data8 sys_ufuqueue_ctl
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall			// 1270
 	data8 sys_ni_syscall
--- arch/ppc/kernel/misc.S:1.1.1.5 Tue Apr 6 00:22:00 2004
+++ arch/ppc/kernel/misc.S Sat Jul 17 19:42:55 2004
@@ -976,7 +976,7 @@
  * R5    has shift count
  * result in R3/R4
  *
- *  ashrdi3: arithmetic right shift (sign propagation)	
+ *  ashrdi3: arithmetic right shift (sign propagation) 
  *  lshrdi3: logical right shift
  *  ashldi3: left shift
  */
@@ -1370,3 +1370,10 @@
 	.long sys_fstatfs64
 	.long ppc_fadvise64_64
 	.long sys_ni_syscall	/* 255 - rtas (used on ppc64) */
+	.long sys_ufulock_lock
+	.long sys_ufulock_unlock
+	.long sys_ufulock_ctl
+	.long sys_ufulock_requeue
+	.long sys_ufuqueue_wait   /* 260 */
+	.long sys_ufuqueue_wake
+	.long sys_ufuqueue_ctl
--- arch/ppc64/kernel/misc.S:1.1.1.5 Tue Apr 6 00:22:01 2004
+++ arch/ppc64/kernel/misc.S Sat Jul 17 19:42:55 2004
@@ -1087,3 +1087,10 @@
 	.llong .sys_fstatfs64
 	.llong .sys_ni_syscall		/* 32bit only fadvise64_64 */
 	.llong .ppc_rtas		/* 255 */
+	.llong .sys_ufulock_lock
+	.llong .sys_ufulock_unlock
+	.llong .sys_ufulock_ctl
+	.llong .sys_ufulock_requeue
+	.llong .sys_ufuqueue_wait	/* 260 */      
+	.llong .sys_ufuqueue_wake
+	.llong .sys_ufuqueue_ctl

[RFC/PATCH] FUSYN 9/11: Modifications to the core: basic

[inaky.perez-gonzalez]

Add list_replace() to list.h. Configuration stuff.


 include/linux/list.h |   27 +++++++++++++++++++++++++++
 init/Kconfig         |   40 ++++++++++++++++++++++++++++++++++++++++
 kernel/Makefile      |    4 ++++
 3 files changed, 71 insertions(+)

--- include/linux/list.h:1.1.1.7 Tue Apr 6 01:51:36 2004
+++ include/linux/list.h Wed May 12 00:28:11 2004
@@ -177,6 +177,33 @@
 }
 
 /**
+ * list_replace - replaces an entry with another one.
+ * @new: entry to replace with.
+ * @old: entry to replace.
+ */
+static inline
+void list_replace (struct list_head *new, struct list_head *old)
+{
+	old->prev->next = new;
+	new->prev = old->prev;
+	old->next->prev = new;
+	new->next = old->next;
+}
+
+/**
+ * list_replace - replaces an entry with another one, reinitializing
+ * the old one. 
+ * @new: entry to replace with.
+ * @old: entry to replace and reinitialize.
+ */
+static inline
+void list_replace_init (struct list_head *new, struct list_head *old)
+{
+	list_replace (new, old);
+	INIT_LIST_HEAD (old);
+}
+
+/**
  * list_move - delete from one list and add as another's head
  * @list: the entry to move
  * @head: the head that will precede our entry
--- init/Kconfig:1.1.1.12 Tue Apr 6 01:51:37 2004
+++ init/Kconfig Wed May 26 22:14:57 2004
@@ -206,6 +206,46 @@
 	  support for "fast userspace mutexes".  The resulting kernel may not
 	  run glibc-based applications correctly.
 
+config FUSYN
+	bool "Enable fusyn support" if EMBEDDED
+	default y
+	help
+	  Disabling this option will cause the kernel to be built without
+	  support for the fusyn synchronization infrastructure. This
+          means no support in the kernel for fuqueues (priority sorted
+          wait queues) nor fulocks (priority sorted, inheriting and/or
+          protected mutexes).
+
+config FULOCK
+	bool "Enable fulock support" if EMBEDDED && FUSYN
+	default y if FUSYN
+        default n
+	help
+	  Disabling this option will cause the kernel to be built without
+	  support for the fulocks of fusyn synchronization
+          infrastructure. This means no support in the kernel for
+          priority sorted, inheriting and/or protected mutexes.
+
+config UFUSYN
+	bool "Enable user-space fusyn support" if EMBEDDED && FUSYN
+	default y if FUSYN
+        default n
+	help
+	  Disabling this option will cause the kernel to be built without
+	  support for the user-space fusyn synchronization
+          infrastructure. This means that neither fuqueues nor fulocks
+          are available for user space to use them.
+
+config UFULOCK
+	bool "Enable user-space fulock support" if EMBEDDED && UFUSYN && FULOCK
+	default y if FULOCK
+        default n
+	help
+	  Disabling this option will cause the kernel to be built without
+	  support for the user-space fulocks of the fusyn
+          synchronization infrastructure. This means fulocks are not
+          available for user-space to use it.  mutexes.
+
 config EPOLL
 	bool "Enable eventpoll support" if EMBEDDED
 	default y
--- kernel/Makefile:1.1.1.10 Tue Apr 6 01:51:37 2004
+++ kernel/Makefile Wed May 26 22:14:57 2004
@@ -21,6 +21,10 @@
 obj-$(CONFIG_IKCONFIG) += configs.o
 obj-$(CONFIG_IKCONFIG_PROC) += configs.o
 obj-$(CONFIG_STOP_MACHINE) += stop_machine.o
+obj-$(CONFIG_FUSYN) += fuqueue.o
+obj-$(CONFIG_FULOCK) += fulock.o 
+obj-$(CONFIG_UFUSYN) += vlocator.o ufuqueue.o
+obj-$(CONFIG_UFULOCK) += ufulock.o
 
 ifneq ($(CONFIG_IA64),y)
 # According to Alan Modra <alan@linuxcare.com.au>, the -fno-omit-frame-pointer is

[RFC/PATCH] FUSYN 10/11: Modifications to the core: struct timeout

[inaky.perez-gonzalez]

Define a generic way to specifcy timeouts, either relative or
absolute, in jiffies or 'struct timespec'. As well, define a
variant of schedule_timeout() that takes this new struct.

This allows userspace to follow POSIX more effectively. Most
POSIX timeouts are absolute, so it is pointless to go to the
kernel, ask for the time, compute a relative sleep and go to
the kernel to block.

aio defines an 'struct timeout' -- as it is specific to it,
inside it's .c file, renamed it to aio_timeout to avoid
conflict with the wider 'struct timeout' we introduce.


 fs/aio.c             |   12 +++---
 include/linux/time.h |   47 +++++++++++++++++++++++++-
 kernel/timer.c       |   91 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 142 insertions(+), 8 deletions(-)

--- include/linux/time.h:1.1.1.4 Tue Apr 6 00:23:00 2004
+++ include/linux/time.h Thu Jun 10 20:40:42 2004
@@ -22,11 +22,38 @@
 	int	tz_dsttime;	/* type of dst correction */
 };
 
+/** Flags for 'struct timeout' */
+enum {
+	/** Time is specified in jiffies, as a timespec otherwise. */
+	TIMEOUT_USE_JIFFIES = 0x1,
+	/** Timeout is relative to the current clock source time. */
+	TIMEOUT_RELATIVE = 0x2,
+};
+
+/**
+ * Generic timeout specification
+ *
+ * FIXME: this is kind of ugly to export to user space, as the jiffies
+ *        should not be in there...however, we want a single
+ *        interface. Reusing ts->tv_sec as jiffies is an option, but
+ *        it is ugly--unions are for that.
+ */
+struct timeout
+{
+	int flags;
+	clockid_t clock_id; /* Currently unused */
+	union {
+		struct timespec ts;
+		unsigned long jiffies;
+	};
+};
+
 #ifdef __KERNEL__
 
 #include <linux/spinlock.h>
 #include <linux/seqlock.h>
 #include <linux/timex.h>
+#include <linux/kernel.h>
 #include <asm/div64.h>
 #ifndef div_long_long_rem
 
@@ -189,7 +216,7 @@
  * value to a scaled second value.
  */
 static __inline__ unsigned long
-timespec_to_jiffies(struct timespec *value)
+timespec_to_jiffies(const struct timespec *value)
 {
 	unsigned long sec = value->tv_sec;
 	long nsec = value->tv_nsec + TICK_NSEC - 1;
@@ -259,6 +286,24 @@
 	return (a->tv_sec == b->tv_sec) && (a->tv_nsec == b->tv_nsec);
 } 
 
+/** Adds @t1 and @t2 into @result, maintaining timespec semantics.
+ *
+ * Should work if any of the tv_sec is negative. Will crap if the
+ * added tv_nsec is negative.
+ */
+static inline
+void timespec_add (struct timespec *result,
+		   const struct timespec *t1, const struct timespec *t2) 
+{
+	result->tv_nsec = t1->tv_nsec + t2->tv_nsec;
+	result->tv_sec = t1->tv_sec + t2->tv_sec;
+	/* Assuming tv_nsec is always > 0 */
+	if (result->tv_nsec >= NSEC_PER_SEC) {
+		result->tv_sec += result->tv_nsec / NSEC_PER_SEC;
+		result->tv_nsec = result->tv_nsec % NSEC_PER_SEC;
+	}
+}
+
 /* Converts Gregorian date to seconds since 1970-01-01 00:00:00.
  * Assumes input in normal date format, i.e. 1980-12-31 23:59:59
  * => year=1980, mon=12, day=31, hour=23, min=59, sec=59.
--- kernel/timer.c:1.1.1.13 Tue Apr 6 01:51:37 2004
+++ kernel/timer.c Wed Jul 7 18:30:29 2004
@@ -31,6 +31,7 @@
 #include <linux/time.h>
 #include <linux/jiffies.h>
 #include <linux/cpu.h>
+#include <linux/fuqueue.h>
 
 #include <asm/uaccess.h>
 #include <asm/div64.h>
@@ -967,7 +968,9 @@
 
 static void process_timeout(unsigned long __data)
 {
-	wake_up_process((task_t *)__data);
+	struct task_struct *task = (task_t *) __data;
+	fuqueue_waiter_cancel(task, -ETIMEDOUT);
+	wake_up_process(task);
 }
 
 /**
@@ -1050,6 +1053,92 @@
 
 EXPORT_SYMBOL(schedule_timeout);
 
+/** @returns the absolute jiffies for a given absolute @timeout. */
+static inline
+unsigned long timeout_to_jiffies_abs (const struct timeout *timeout)
+{
+        unsigned long jiffies_abs, seq;
+        struct timespec oc, now;
+
+        if (timeout->flags & TIMEOUT_USE_JIFFIES)
+                jiffies_abs = timeout->jiffies;
+        else {
+                 do {
+                         seq = read_seqbegin(&xtime_lock);
+                         now = current_kernel_time();
+                         jiffies_abs = get_jiffies_64();
+                 } while (read_seqretry(&xtime_lock, seq));
+                oc = timeout->ts;
+                set_normalized_timespec(&oc, oc.tv_sec - now.tv_sec,
+                                        oc.tv_nsec - now.tv_nsec);
+                if (oc.tv_sec < 0)
+                        oc.tv_sec = oc.tv_nsec = 0;
+                jiffies_abs += timespec_to_jiffies(&oc)
+                        + (oc.tv_sec || oc.tv_nsec);
+        }
+        return jiffies_abs;
+}
+
+/** @returns the relative jiffies for a given relative @timeout. */
+static inline
+unsigned long timeout_to_jiffies_rel (const struct timeout *timeout)
+{
+	return timeout->flags & TIMEOUT_USE_JIFFIES?
+		timeout->jiffies : timespec_to_jiffies (&timeout->ts);
+}
+
+/**
+ * Wait for an amount of time, absolute or relative.
+ *
+ * @timeout: Pointer to an struct that describes the timeout. If it
+ *           equals '(struct timeout *) ~0', then it waits for ever. 
+ *
+ * timeout->flags &
+ *
+ *   TIMEOUT_RELATIVE means the timeout is relative to the current
+ *                    time. Otherwise is absolute.
+ *   TIMEOUT_USE_JIFFIES
+ *                    The timeout is specified as jiffies instead of a
+ *                    'struct timespec'.
+ *
+ * All times are currently based on CLOCK_REALTIME and the whole thing
+ * is not too precise, I am afraid. It doesn't take into account
+ * changes to CLOCK_REALTIME.
+ * 
+ * TODO:
+ *  - Lacks support for recalc of how much did we sleep if we were
+ *    interrupted (only needed for relative mode).
+ *  - Add support for other clock sources.
+ *
+ * Thanks to George Anzinger for coming out with the way to do it and
+ * to Boris Hu for fixing timespec_to_jiffies_abs() for accurate timings.
+ */ 
+void schedule_timeout_ext (const struct timeout *timeout)
+{
+	unsigned long jiffies_abs;
+	struct timer_list timer;
+	
+	if (timeout == (const struct timeout *) ~0) { /* Wait for ever */
+		schedule();
+		goto out;
+	}
+	jiffies_abs = timeout->flags & TIMEOUT_RELATIVE?
+		jiffies + timeout_to_jiffies_rel (timeout) 
+		: timeout_to_jiffies_abs (timeout);
+
+	init_timer (&timer);
+	timer.expires = jiffies_abs;
+	timer.data = (unsigned long) current;
+	timer.function = process_timeout;
+	add_timer (&timer);
+	schedule();
+	del_timer_sync (&timer);
+out:
+	return;
+}
+
+EXPORT_SYMBOL_GPL (schedule_timeout_ext);
+
 /* Thread ID - the internal kernel "pid" */
 asmlinkage long sys_gettid(void)
 {
--- fs/aio.c:1.1.1.7 Tue Apr 6 00:22:44 2004
+++ fs/aio.c Fri Jun 4 01:34:19 2004
@@ -750,7 +750,7 @@
 	return ret;
 }
 
-struct timeout {
+struct aio_timeout {
 	struct timer_list	timer;
 	int			timed_out;
 	struct task_struct	*p;
@@ -758,13 +758,13 @@
 
 static void timeout_func(unsigned long data)
 {
-	struct timeout *to = (struct timeout *)data;
+	struct aio_timeout *to = (struct aio_timeout *)data;
 
 	to->timed_out = 1;
 	wake_up_process(to->p);
 }
 
-static inline void init_timeout(struct timeout *to)
+static inline void init_timeout(struct aio_timeout *to)
 {
 	init_timer(&to->timer);
 	to->timer.data = (unsigned long)to;
@@ -773,7 +773,7 @@
 	to->p = current;
 }
 
-static inline void set_timeout(long start_jiffies, struct timeout *to,
+static inline void set_timeout(long start_jiffies, struct aio_timeout *to,
 			       const struct timespec *ts)
 {
 	unsigned long how_long;
@@ -791,7 +791,7 @@
 	add_timer(&to->timer);
 }
 
-static inline void clear_timeout(struct timeout *to)
+static inline void clear_timeout(struct aio_timeout *to)
 {
 	del_timer_sync(&to->timer);
 }
@@ -807,7 +807,7 @@
 	int			ret;
 	int			i = 0;
 	struct io_event		ent;
-	struct timeout		to;
+	struct aio_timeout	to;
 
 	/* needed to zero any padding within an entry (there shouldn't be 
 	 * any, but C is fun!

[RFC/PATCH] FUSYN 11/11: Modifications to the core: scheduler

[inaky.perez-gonzalez]

Add support for priority boosting, hooks into the scheduling
code.

As we modify the task struct, fix the init_task. Currently
ugly as hell, needs to be improved.


 arch/i386/kernel/init_task.c |    1 
 include/linux/init_task.h    |   31 ++++++++++++
 include/linux/sched.h        |   22 ++++++++-
 kernel/exit.c                |    2 
 kernel/fork.c                |    2 
 kernel/sched.c               |  103 +++++++++++++++++++++++++++++++++++++------
 kernel/signal.c              |   14 +++++
 7 files changed, 160 insertions(+), 15 deletions(-)

--- include/linux/init_task.h:1.1.1.5 Tue Apr 6 01:51:36 2004
+++ include/linux/init_task.h Wed May 26 22:14:47 2004
@@ -60,6 +60,32 @@
 extern struct group_info init_groups;
 
 /*
+ * Initialize the init task fuqueue's and fulock side
+ *
+ * Ugly as hell--any ideas on how to make this look better? The
+ * problem is that we remove stuff from the task struct when we
+ * disable FUSYN or FULOCK.
+ */
+#ifndef CONFIG_FUSYN
+#  define FUQUEUE_INIT_TASK(a) /* Emtpy, nothing to init */
+#else           /* #ifndef CONFIG_FUSYN */
+#  define FUQUEUE_INIT_TASK(task)					\
+	,	/* Grumble, mumble, @od damn it	*/			\
+	.fuqueue_wait_lock = SPIN_LOCK_UNLOCKED,			\
+	.fuqueue_wait = NULL,						\
+	.fuqueue_waiter	= NULL
+#  ifndef CONFIG_FULOCK
+#    define FULOCK_INIT_TASK(a) /* Emtpy, nothing to init */
+#  else         /* #ifndef CONFIG_FULOCK */
+#    define FULOCK_INIT_TASK(task)					\
+	,	/* Grumble, mumble, @od damn it	*/			\
+	.fulock_olist = plist_INIT (&(task).fulock_olist, BOTTOM_PRIO),	\
+	.fulock_olist_lock = SPIN_LOCK_UNLOCKED
+#  endif
+#endif /* #ifndef CONFIG_FUSYN
+ */
+
+/*
  *  INIT_TASK is used to set up the first task table, touch at
  * your own risk!. Base=0, limit=0x1fffff (=2MB)
  */
@@ -72,6 +98,7 @@
 	.lock_depth	= -1,						\
 	.prio		= MAX_PRIO-20,					\
 	.static_prio	= MAX_PRIO-20,					\
+	.boost_prio	= BOTTOM_PRIO,					\
 	.policy		= SCHED_NORMAL,					\
 	.cpus_allowed	= CPU_MASK_ALL,					\
 	.mm		= NULL,						\
@@ -111,7 +138,9 @@
 	.alloc_lock	= SPIN_LOCK_UNLOCKED,				\
 	.proc_lock	= SPIN_LOCK_UNLOCKED,				\
 	.switch_lock	= SPIN_LOCK_UNLOCKED,				\
-	.journal_info	= NULL,						\
+	.journal_info	= NULL						\
+	FUQUEUE_INIT_TASK(tsk)						\
+	FULOCK_INIT_TASK(tsk),						\
 }
 
 
--- include/linux/sched.h:1.1.1.14 Tue Apr 6 01:51:36 2004
+++ include/linux/sched.h Wed Jun 9 23:36:40 2004
@@ -29,6 +29,7 @@
 #include <linux/completion.h>
 #include <linux/pid.h>
 #include <linux/percpu.h>
+#include <linux/plist.h>    /* fulock ownership list */
 
 struct exec_domain;
 
@@ -174,6 +175,9 @@
 
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
+struct timeout;
+#define	MAX_SCHEDULE_TIMEOUT_EXT ((struct timeout *) ~0)
+extern void FASTCALL(schedule_timeout_ext (const struct timeout *timeout));
 asmlinkage void schedule(void);
 
 struct namespace;
@@ -286,6 +290,7 @@
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
 
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
+#define BOTTOM_PRIO		INT_MAX
 
 #define rt_task(p)		((p)->prio < MAX_RT_PRIO)
 
@@ -330,6 +335,8 @@
 };
 
 
+struct fuqueue;
+struct fuqueue_waiter;
 struct io_context;			/* See blkdev.h */
 void exit_io_context(void);
 
@@ -369,7 +376,7 @@
 
 	int lock_depth;		/* Lock depth */
 
-	int prio, static_prio;
+	int prio, static_prio, boost_prio;
 	struct list_head run_list;
 	prio_array_t *array;
 
@@ -493,6 +500,15 @@
 
 	unsigned long ptrace_message;
 	siginfo_t *last_siginfo; /* For ptrace use.  */
+#ifdef CONFIG_FUSYN   /* FIXME: I don't really like this... */
+	struct fuqueue *fuqueue_wait;		/* waiting for this qeueue */
+	struct fuqueue_waiter *fuqueue_waiter;	/* waiting for this qeueue */
+	spinlock_t fuqueue_wait_lock;
+#endif
+#ifdef CONFIG_FULOCK   /* FIXME: I don't really like this... */
+	struct plist fulock_olist;		/* Fulock ownership list */
+	spinlock_t fulock_olist_lock;
+#endif
 };
 
 static inline pid_t process_group(struct task_struct *tsk)
@@ -557,6 +573,9 @@
 extern int task_curr(task_t *p);
 extern int idle_cpu(int cpu);
 
+/* Set the boost priority */
+extern unsigned __prio_boost (task_t *, int);
+
 void yield(void);
 
 /*
@@ -599,6 +618,7 @@
 extern unsigned long itimer_next;
 extern void do_timer(struct pt_regs *);
 
+extern int try_to_wake_up(struct task_struct *p, unsigned int state, int sync);
 extern int FASTCALL(wake_up_state(struct task_struct * tsk, unsigned int state));
 extern int FASTCALL(wake_up_process(struct task_struct * tsk));
 #ifdef CONFIG_SMP
--- kernel/exit.c:1.1.1.11 Tue Apr 6 01:51:37 2004
+++ kernel/exit.c Wed May 26 22:14:57 2004
@@ -22,6 +22,7 @@
 #include <linux/profile.h>
 #include <linux/mount.h>
 #include <linux/proc_fs.h>
+#include <linux/fulock.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -771,6 +772,7 @@
 	}
 
 	acct_process(code);
+	exit_fulocks(tsk);
 	__exit_mm(tsk);
 
 	exit_sem(tsk);
--- kernel/fork.c:1.1.1.14 Tue Apr 6 01:51:37 2004
+++ kernel/fork.c Wed May 26 22:14:57 2004
@@ -31,6 +31,7 @@
 #include <linux/futex.h>
 #include <linux/ptrace.h>
 #include <linux/mount.h>
+#include <linux/fulock.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -964,6 +965,7 @@
 		goto bad_fork_cleanup_signal;
 	if ((retval = copy_namespace(clone_flags, p)))
 		goto bad_fork_cleanup_mm;
+	init_fulocks(p);
 	retval = copy_thread(0, clone_flags, stack_start, stack_size, p, regs);
 	if (retval)
 		goto bad_fork_cleanup_namespace;
--- kernel/sched.c:1.1.1.18 Tue Apr 6 01:51:37 2004
+++ kernel/sched.c Wed Jun 23 00:07:06 2004
@@ -33,6 +33,7 @@
 #include <linux/suspend.h>
 #include <linux/blkdev.h>
 #include <linux/delay.h>
+#include <linux/fuqueue.h>
 #include <linux/smp.h>
 #include <linux/timer.h>
 #include <linux/rcupdate.h>
@@ -356,13 +357,10 @@
  *
  * Both properties are important to certain workloads.
  */
-static int effective_prio(task_t *p)
+static inline int __effective_prio(task_t *p)
 {
 	int bonus, prio;
 
-	if (rt_task(p))
-		return p->prio;
-
 	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
 
 	prio = p->static_prio - bonus;
@@ -372,6 +370,13 @@
 		prio = MAX_PRIO-1;
 	return prio;
 }
+static int effective_prio(task_t *p)
+{
+	int new_prio;
+	new_prio = rt_task(p)? p->prio : __effective_prio(p);
+	return min (new_prio, p->boost_prio);
+}
+
 
 /*
  * __activate_task - move a task to the runqueue.
@@ -647,7 +652,7 @@
  *
  * returns failure only if the task is already active.
  */
-static int try_to_wake_up(task_t * p, unsigned int state, int sync)
+int try_to_wake_up(task_t * p, unsigned int state, int sync)
 {
 	unsigned long flags;
 	int success = 0;
@@ -733,6 +738,8 @@
 	 */
 	p->thread_info->preempt_count = 1;
 #endif
+	/* Initially the task has no priority boosting */
+	p->boost_prio = BOTTOM_PRIO;
 	/*
 	 * Share the timeslice between parent and child, thus the
 	 * total amount of pending timeslices in the system doesn't change,
@@ -1772,6 +1779,9 @@
  * There are circumstances in which we can try to wake a task which has already
  * started to run but is not in state TASK_RUNNING.  try_to_wake_up() returns
  * zero in this (rare) case, and we handle it by continuing to scan the queue.
+ *
+ * fuqueue_wait_cancel needs to hook up here to properly rescheduler
+ * priority inheritance/protected tasks. Check its doc to learn why.
  */
 static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
 			     int nr_exclusive, int sync)
@@ -1783,6 +1793,7 @@
 		unsigned flags;
 		curr = list_entry(tmp, wait_queue_t, task_list);
 		flags = curr->flags;
+		fuqueue_waiter_cancel(curr->task, -EINTR);
 		if (curr->func(curr, mode, sync) &&
 		    (flags & WQ_FLAG_EXCLUSIVE) &&
 		    !--nr_exclusive)
@@ -1965,12 +1976,17 @@
 
 void scheduling_functions_end_here(void) { }
 
+/*
+ * Note the initialization of old_prio and new_dynamic_prio. If we
+ * fall back through 'out_unlock', they will help to skip the call to
+ * fuqueue_waiter_chprio(). 
+ */
 void set_user_nice(task_t *p, long nice)
 {
 	unsigned long flags;
 	prio_array_t *array;
 	runqueue_t *rq;
-	int old_prio, new_prio, delta;
+	int old_prio = p->prio, new_prio, delta;
 
 	if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
 		return;
@@ -1993,11 +2009,12 @@
 	if (array)
 		dequeue_task(p, array);
 
-	old_prio = p->prio;
 	new_prio = NICE_TO_PRIO(nice);
 	delta = new_prio - old_prio;
 	p->static_prio = NICE_TO_PRIO(nice);
 	p->prio += delta;
+	old_prio = p->prio;
+	p->prio = min (p->prio, p->boost_prio);
 
 	if (array) {
 		enqueue_task(p, array);
@@ -2010,6 +2027,7 @@
 	}
 out_unlock:
 	task_rq_unlock(rq, &flags);
+	fuqueue_waiter_chprio(p, old_prio);
 }
 
 EXPORT_SYMBOL(set_user_nice);
@@ -2102,20 +2120,79 @@
 	return pid ? find_task_by_pid(pid) : current;
 }
 
+
+/**
+ * Boost the priority of a task from a new dynamic priority. 
+ *
+ * On SCHED_NORMAL, sets boost_prio in as __effective_prio()
+ * would do to get the same prio when it is reinserted in the list.
+ * 
+ * @p: Pointer to the task in question
+ * @prio: New boost priority to set
+ * @returns: !0 if the final new dynamic priority of the task has
+ * changed, 0 otherwise.
+ *
+ * This does not do fuqueue priority propagation (to avoid infinite
+ * recursion in the fuqueue code).
+ */
+unsigned __prio_boost(task_t *p, int prio)
+{
+	runqueue_t *rq;
+	prio_array_t *array;
+	long flags;
+       int old_prio, new_dynamic_prio, newprio;
+
+	if (p->boost_prio == prio)
+		return 0;
+	
+	rq = task_rq_lock(p, &flags);
+	old_prio = p->prio;
+	array = p->array;
+	if (array)
+		deactivate_task(p, task_rq(p));
+	p->boost_prio = prio;
+	new_dynamic_prio = p->policy != SCHED_NORMAL?
+		MAX_USER_RT_PRIO - 1 - p->rt_priority
+		: __effective_prio(p);
+	newprio = min (new_dynamic_prio, p->boost_prio);
+	p->prio = newprio;
+	if (array) {
+		__activate_task(p, task_rq(p));
+		if (rq->curr == p) {
+			if (p->prio > old_prio)
+				resched_task(rq->curr);
+		}
+		else if (TASK_PREEMPTS_CURR (p, rq))
+			resched_task(rq->curr);
+	}
+	task_rq_unlock (rq, &flags);
+	return old_prio != newprio;
+}
+
+
 /* Actually do priority change: must hold rq lock. */
 static void __setscheduler(struct task_struct *p, int policy, int prio)
 {
+	int newprio, oldprio;
+
 	BUG_ON(p->array);
 	p->policy = policy;
 	p->rt_priority = prio;
 	if (policy != SCHED_NORMAL)
-		p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;
+		newprio = MAX_USER_RT_PRIO-1 - p->rt_priority;
 	else
-		p->prio = p->static_prio;
+		newprio = p->static_prio;
+	oldprio = p->prio;
+	p->prio = min (newprio, p->boost_prio);
 }
 
 /*
  * setscheduler - change the scheduling policy and/or RT priority of a thread.
+ * 
+ * Note the initialization of old_prio. If we fall back through
+ * 'out_unlock*', it will help to skip the call to
+ * fuqueue_waiter_chprio(); this way we avoid the extra check on
+ * 'retval == 0'.
  */
 static int setscheduler(pid_t pid, int policy, struct sched_param __user *param)
 {
@@ -2150,7 +2227,7 @@
 	 * runqueue lock must be held.
 	 */
 	rq = task_rq_lock(p, &flags);
-
+	oldprio = p->prio;
 	if (policy < 0)
 		policy = p->policy;
 	else {
@@ -2186,7 +2263,6 @@
 	if (array)
 		deactivate_task(p, task_rq(p));
 	retval = 0;
-	oldprio = p->prio;
 	__setscheduler(p, policy, lp.sched_priority);
 	if (array) {
 		__activate_task(p, task_rq(p));
@@ -2204,9 +2280,9 @@
 
 out_unlock:
 	task_rq_unlock(rq, &flags);
+	fuqueue_waiter_chprio(p, oldprio);
 out_unlock_tasklist:
 	read_unlock_irq(&tasklist_lock);
-
 out_nounlock:
 	return retval;
 }
@@ -2868,6 +2944,7 @@
 	struct task_struct *p;
 	struct runqueue *rq;
 	unsigned long flags;
+	unsigned old_prio;
 
 	switch (action) {
 	case CPU_UP_PREPARE:
@@ -2877,8 +2954,10 @@
 		kthread_bind(p, cpu);
 		/* Must be high prio: stop_machine expects to yield to it. */
 		rq = task_rq_lock(p, &flags);
+		old_prio = p->prio;
 		__setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1);
 		task_rq_unlock(rq, &flags);
+		fuqueue_waiter_chprio(p, old_prio);
 		cpu_rq(cpu)->migration_thread = p;
 		break;
 	case CPU_ONLINE:
--- kernel/signal.c:1.1.1.12 Tue Apr 6 01:51:37 2004
+++ kernel/signal.c Wed Jun 23 00:06:23 2004
@@ -21,6 +21,7 @@
 #include <linux/binfmts.h>
 #include <linux/security.h>
 #include <linux/ptrace.h>
+#include <linux/fuqueue.h>
 #include <asm/param.h>
 #include <asm/uaccess.h>
 #include <asm/siginfo.h>
@@ -521,6 +522,7 @@
 	return signr;
 }
 
+
 /*
  * Tell a process that it has a new active signal..
  *
@@ -544,12 +546,20 @@
 	 * executing another processor and just now entering stopped state.
 	 * By calling wake_up_process any time resume is set, we ensure
 	 * the process will wake up and handle its stop or death signal.
+	 * 
+	 * fuqueue_waiter_cancel needs to hook up here to properly rescheduler
+	 * priority inheritance/protected tasks. The reason is that
+	 * when we resched a process that has boosted another one, we
+	 * need to kick its butt off the CPU (and lower its priority) ASAP
+	 * so that 't' can run.
 	 */
 	mask = TASK_INTERRUPTIBLE;
 	if (resume)
 		mask |= TASK_STOPPED;
-	if (!wake_up_state(t, mask))
+	fuqueue_waiter_cancel(t, -EINTR);
+	if (!wake_up_state(t, mask)) {
 		kick_process(t);
+	}
 }
 
 /*
@@ -672,6 +682,8 @@
 				set_tsk_thread_flag(t, TIF_SIGPENDING);
 				state |= TASK_INTERRUPTIBLE;
 			}
+			/* FIXME: I am not that sure we need to cancel here */
+			fuqueue_waiter_cancel(t, -EINTR);
 			wake_up_state(t, state);
 
 			t = next_thread(t);
--- arch/i386/kernel/init_task.c:1.1.1.4 Tue Apr 6 00:21:44 2004
+++ arch/i386/kernel/init_task.c Wed May 26 21:14:03 2004
@@ -4,6 +4,7 @@
 #include <linux/init.h>
 #include <linux/init_task.h>
 #include <linux/fs.h>
+#include <linux/fuqueue.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>