[RFC] Upgradeable read locks for USB (Try #2)

Inaky Perez Gonzalez (inaky@peloncho.fis.ucm.es)
Mon, 19 Jan 1998 14:52:34 +0100


Hi

After my novice-typical screw up with the upgradeable read locks,
I've come with another implementation. Following Linus' guides and
some thinking :) I've come with this implementation:

- Read locks are as always
- So are write locks
- Upgradeable read locks may only be held by one process at the
time
- An upgradeable read lock may only be upgraded to write lock if
there's only a reader (the process doing the upgrade)

Sooo, I had to change some code in the read_lock() to make it detect
the upgradeable lock case; however, I've done this in a Windows
Notepad, as now I can't use my machine for doing tests (I'm not at my
house). I'd like to hear comments, flames from people. I plan to
stress test it as soon as I finish exams.

Anyhow note I've done some tests and the basic behavious works,
however, I may be screwing something more up (something conceptual,
something in the code...).

Here's the code, patch against 2.1.79:

diff -urN linux.orig/include/asm-i386/spinlock.h linux/include/asm-i386/spinlock.h
--- linux.orig/include/asm-i386/spinlock.h Mon Jan 19 14:38:58 1998
+++ linux/include/asm-i386/spinlock.h Mon Jan 19 14:41:11 1998
@@ -35,23 +35,39 @@
typedef struct { } rwlock_t;
#define RW_LOCK_UNLOCKED { }

-#define read_lock(lock) do { } while(0)
-#define read_unlock(lock) do { } while(0)
-#define write_lock(lock) do { } while(0)
-#define write_unlock(lock) do { } while(0)
-#define read_lock_irq(lock) cli()
-#define read_unlock_irq(lock) sti()
-#define write_lock_irq(lock) cli()
-#define write_unlock_irq(lock) sti()
+#define read_lock(lock) do { } while(0)
+#define read_unlock(lock) do { } while(0)
+#define write_lock(lock) do { } while(0)
+#define write_unlock(lock) do { } while(0)
+#define upgr_lock(lock) do { } while(0)
+#define upgr_unlock(lock) do { } while(0)
+#define up2wr_lock(lock) do { } while(0)
+#define dn2rd_lock(lock) do { } while(0)
+#define read_lock_irq(lock) cli()
+#define read_unlock_irq(lock) sti()
+#define write_lock_irq(lock) cli()
+#define write_unlock_irq(lock) sti()
+#define upgr_lock_irq(lock) cli()
+#define upgr_unlock_irq(lock) sti()
+#define up2wr_lock_irq(lock) cli()
+#define dn2rd_lock_irq(lock) sti()

-#define read_lock_irqsave(lock, flags) \
- do { save_flags(flags); cli(); } while (0)
+#define read_lock_irqsave(lock, flags) \
+ do { save_flags(flags); cli(); } while (0)
#define read_unlock_irqrestore(lock, flags) \
- restore_flags(flags)
-#define write_lock_irqsave(lock, flags) \
- do { save_flags(flags); cli(); } while (0)
+ restore_flags(flags)
+#define write_lock_irqsave(lock, flags) \
+ do { save_flags(flags); cli(); } while (0)
#define write_unlock_irqrestore(lock, flags) \
- restore_flags(flags)
+ restore_flags(flags)
+#define upgr_lock_irqsave(lock, flags) \
+ do { save_flags(flags); cli(); } while (0)
+#define upgr_unlock_irqrestore(lock, flags) \
+ restore_flags(flags)
+#define up2wr_lock_irqsave(lock, flags) \
+ do { save_flags(flags); cli(); } while (0)
+#define dn2rd_lock_irqrestore(lock, flags) \
+ restore_flags(flags)

#else

@@ -126,55 +142,295 @@
/*
* On x86, we implement read-write locks as a 32-bit counter
* with the high bit (sign) being the "write" bit.
+ *
+ * The inline assembly is not obvious. Think about it.
*
- * The inline assembly is non-obvious. Think about it.
+ * Lock states and counter values
+ * ------------------------------
+ *
+ * Code Lock State Lock Value
+ * ---- -------------------- -----------------------
+ * U Unlocked 0x00000000
+ * NR Read locked (N readers) [0x00000001,0x7fffffff]
+ * NRG Read/upgrade locked [0x80000001,0xffffffff]
+ * (N readers, 1 upgrader)
+ * W Write locked 0x80000000
+ * WG Write/upgrade locked 0x80000000
+ * (1 reader, 1 upgrader,
+ * 1 writer)
+ *
+ * Notes:
+ * U == 0R (N == 0)
+ *
+ *
+ * State transitions
+ * -----------------
+ *
+ * Prev Wait Final
+ * Function State For State
+ * --------------- ----- ---- -----
+ *
+ * read_lock() U 1R
+ * NR N+1R
+ * W NR N+1R
+ * NRG N+1RG
+ * NRG N+1RG
+ *
+ * read_unlock() 1R U
+ * NR N-1R
+ *
+ * write_lock() U W
+ * NR U W
+ * NRG U W
+ * W U W
+ *
+ * write_unlock() W U
+ *
+ * upgr_lock() U 1RG
+ * NR N+1RG
+ * NRG N-1R NRG
+ * W NR N+1RG
+ *
+ * upgr_unlock() 1RG U
+ * NRG N-1R
+ *
+ * up2wr_lock() 1RG WG
+ * NRG 1RG WG
+ *
+ * dn2rd_lock() WG 1RG
*/
-#define read_lock(rw) \
- asm volatile("\n1:\t" \
- "lock ; incl %0\n\t" \
- "js 2f\n" \
- ".section .text.lock,\"ax\"\n" \
- "2:\tlock ; decl %0\n" \
- "3:\tcmpl $0,%0\n\t" \
- "js 3b\n\t" \
- "jmp 1b\n" \
- ".previous" \
- :"=m" (__dummy_lock(&(rw)->lock)))
-
-#define read_unlock(rw) \
- asm volatile("lock ; decl %0" \
- :"=m" (__dummy_lock(&(rw)->lock)))
-
-#define write_lock(rw) \
- asm volatile("\n1:\t" \
- "lock ; btsl $31,%0\n\t" \
- "jc 4f\n" \
- "2:\ttestl $0x7fffffff,%0\n\t" \
- "jne 3f\n" \
- ".section .text.lock,\"ax\"\n" \
- "3:\tlock ; btrl $31,%0\n" \
- "4:\tcmp $0,%0\n\t" \
- "jne 4b\n\t" \
- "jmp 1b\n" \
- ".previous" \
- :"=m" (__dummy_lock(&(rw)->lock)))
-
-#define write_unlock(rw) \
- asm volatile("lock ; btrl $31,%0":"=m" (__dummy_lock(&(rw)->lock)))
-
-#define read_lock_irq(lock) do { __cli(); read_lock(lock); } while (0)
-#define read_unlock_irq(lock) do { read_unlock(lock); __sti(); } while (0)
-#define write_lock_irq(lock) do { __cli(); write_lock(lock); } while (0)
-#define write_unlock_irq(lock) do { write_unlock(lock); __sti(); } while (0)

-#define read_lock_irqsave(lock, flags) \
- do { __save_flags(flags); __cli(); read_lock(lock); } while (0)
-#define read_unlock_irqrestore(lock, flags) \
- do { read_unlock(lock); __restore_flags(flags); } while (0)
-#define write_lock_irqsave(lock, flags) \
- do { __save_flags(flags); __cli(); write_lock(lock); } while (0)
-#define write_unlock_irqrestore(lock, flags) \
- do { write_unlock(lock); __restore_flags(flags); } while (0)
+
+/* Read-lock a rwlock_t or block until able to.
+ *
+ * This function will take a read-write lock and increment
+ * it's read count if it is not write-locked, in which case
+ * it will enter a busy-loop, waiting for it to be released
+ * and do the read-lock.
+ *
+ * You must call read_unlock() to unlock it, as no writers
+ * will be allowed until all readers are out. Note that you
+ * can upgrade a lock from read to write using the upgradeable
+ * read locks (See upgr_lock()).
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the read-write lock to lock. If
+ * NULL, it will crash.
+ */
+
+#define read_lock(rw) \
+ asm volatile ( \
+ "\n1: lock; incl %0" \
+ "\n jc 3f" \
+ "\n2:" \
+ "\n.section .text.lock,\"ax\"" \
+ "\n3: testl $0x7fffffe,%0" \
+ "\n jnz 2b" \
+ "\n lock; decl %0" \
+ "\n4: cmpl $0, %0" \
+ "\n js 4b" \
+ "\n jmp 1b" \
+ "\n.previous" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Read unlock a read-locked rwlock_t.
+ *
+ * This macro will take a read-locked lock and decrement
+ * it's readers count. When this count drops to zero, writers
+ * are allowed to adquire write locks.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock. It must be in the NR
+ * state, otherwise results are undefined (and
+ * likely to be *bad*). If NULL, it will crash.
+ */
+
+#define read_unlock(rw) \
+ asm volatile ( \
+ "lock; decl %0" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Write-lock a rwlock_t or block until able to.
+ *
+ * This function will write-lock a lock by setting to one
+ * the 31st bit of the lock count. However, it can only be
+ * done if the lock is unlocked. In case of the lock being
+ * read, upgrade or write locked, it'll do a busy loop until
+ * the lock is unlocked, and then will lock.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock to write-lock. If NULL
+ * it will crash.
+ */
+
+#define write_lock(rw) \
+ asm volatile ( \
+ "\n1: lock; btsl $31,%0" \
+ "\n jc 4f" \
+ "\n2: testl $0x7fffffff,%0" \
+ "\n jnz 3f" \
+ "\n.section .text.lock,\"ax\"" \
+ "\n3: lock; btrl $31,%0" \
+ "\n4: cmp $0,%0" \
+ "\n jne 4b" \
+ "\n jmp 1b" \
+ "\n.previous" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Write unlock a write-locked rwlock_t
+ *
+ * This function will unlock a write-locked rwlock_t by clearing
+ * it's high bit. No blocking is done, as nothing has to be awaited
+ * for.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock structure to unlock. It must be
+ * in any of the W or WG states, otherwise result is
+ * undefined. If NULL, it will crash.
+ */
+
+#define write_unlock(rw) \
+ asm volatile ( \
+ "lock; btrl $31,%0" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Read lock upgradeably a rwlock_t or block until able to.
+ *
+ * This function read-locks a lock in such a fashion it allows
+ * it to be upgraded to a write lock later. Note, however, that
+ * only ONE holder of upgradeable read locks is allowed at one
+ * time, in order to avoid deadlocks. Thus, if you request an
+ * upgradeable read lock, it will grant it directly if unlocked
+ * or only read locked. If upgradeably read locked, then it'll
+ * block until unlocked or read-only locked. If write-locked,
+ * it'll also wait as before. Refer to the state transition table
+ * above.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock structure. If NULL it'll
+ * crash.
+ */
+
+#define upgr_lock(rw) \
+ asm volatile ( \
+ "\n1: lock; btsl $31,%0" \
+ "\n jc 2f" \
+ "\n lock; incl %0" \
+ "\n.section .text.lock,\"ax\"" \
+ "\n2: testl $0x80000000,%0" \
+ "\n jnz 2b" \
+ "\n jmp 1b" \
+ "\n.previous" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Unlock an upgradeable-read lock.
+ *
+ * This will unlock an upgradeable read lock (*NOT* a write
+ * upgraded-read lock).
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock structure to unlock. it
+ * MUST be in the NRG state, otherwise the results
+ * are undefined. If NULL, it'll crash.
+ */
+
+#define upgr_unlock(rw) \
+ asm volatile ( \
+ "lock; decl %0; lock; btrl $31,%0" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Upgrade an upgradeable read lock to write lock
+ *
+ * This will take an upgradeable read lock and upgrade it to
+ * a write lock. Note that for this to be done, the only reader
+ * must be the current process which holds the read lock and
+ * which wants to upgrade, thus, it'll block until the lock
+ * state is 1RG.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock structure to upgrade. It
+ * *must* be in the NRG state, otherwise results
+ * are undefined. If NULL, it'll crash.
+ */
+
+#define up2wr_lock(rw) \
+ asm volatile ( \
+ "\n1: lock; decl %0" \
+ "\n cmpl $0x80000000,%0" \
+ "\n jne 2f" \
+ "\n.section .text.lock,\"ax\"" \
+ "\n2: lock; incl %0" \
+ "\n3: testl $0x80000001,%0" \
+ "\n je 1b" \
+ "\n jmp 3b" \
+ "\n.previous" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/* Downgrade a upgraded-write lock to upgradeable read lock
+ *
+ * This function will downgrade an upgraded-write lock to
+ * upgradeable-read lock.
+ *
+ * Arguments:
+ *
+ * rwlock_t* Pointer to the lock structure to downgrade.
+ * It *must* be in the WG state, otherwise results
+ * are undefined. If NULL it'll crash.
+ */
+
+#define dn2rd_lock(rw) \
+ asm volatile ( \
+ "lock; incl %0" \
+ : "=m" (__dummy_lock (&(rw)->lock)))
+
+
+/*
+ * Use these different flavours to disable IRQs/disable and save CPU
+ * flags while locking, restore IRQs/state while unlocking.
+ */
+
+#define read_lock_irq(lock) do { __cli(); read_lock (lock); } while (0)
+#define read_unlock_irq(lock) do { read_unlock (lock); __sti(); } while (0)
+#define write_lock_irq(lock) do { __cli(); write_lock (lock); } while (0)
+#define write_unlock_irq(lock) do { write_unlock (lock); __sti(); } while (0)
+#define upgr_lock_irq(lock) do { __cli(); upgr_lock (lock); } while (0)
+#define upgr_unlock_irq(lock) do { upgr_unlock (lock); __sti(); } while (0)
+#define up2wr_lock_irq(lock) do { __cli(); up2wr_lock (lock); } while (0)
+#define dn2rd_lock_irq(lock) do { dn2rd_lock (lock); __sti(); } while (0)
+
+#define read_lock_irqsave(lock, flags) \
+ do { __save_flags (flags); __cli(); read_lock (lock); } while (0)
+#define read_unlock_irqrestore(lock, flags) \
+ do { read_unlock (lock); __restore_flags (flags); } while (0)
+
+#define write_lock_irqsave(lock, flags) \
+ do { __save_flags (flags); __cli(); write_lock (lock); } while (0)
+#define write_unlock_irqrestore(lock, flags) \
+ do { write_unlock (lock); __restore_flags (flags); } while (0)
+
+#define upgr_lock_irqsave(lock, flags) \
+ do { __save_flags (flags); __cli(); upgr_lock (lock); } while (0)
+#define upgr_unlock_irqrestore(lock, flags) \
+ do { upgr_unlock (lock); __restore_flags (flags); } while (0)
+
+#define up2wr_lock_irqsave(lock, flags) \
+ do { __save_flags (flags); __cli(); up2wr_lock (lock); } while (0)
+#define dn2rd_lock_irqrestore(lock, flags) \
+ do { dn2rd_lock (lock); __restore_flags (flags); } while (0)

#endif /* SMP */
#endif /* __ASM_SPINLOCK_H */

Linux USB! -- http://peloncho.fis.ucm.es/~inaky/USB.html -
-
Inaky Perez Gonzalez -- PGP pubkey fingerprint -
inaky@peloncho.fis.ucm.es -- 8E 34 3A 62 64 99 E2 44 -
http://peloncho.fis.ucm.es/~inaky -- AD 7B 30 D9 DD FF 3E 4C -
-----------------------------------------------------------------
The loneliness of the long distance runner .....