Messages in this thread Patch in this message | | | Date | Mon, 19 Jan 1998 14:52:34 +0100 | From | Inaky Perez Gonzalez <> | Subject | [RFC] Upgradeable read locks for USB (Try #2) |
| |
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 .....
| |