x86: Panic if there is no x2APIC
[akaros.git] / kern / src / rwlock.c
1 /* Copyright (c) 2013 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Reader-writer queue locks (sleeping locks).
6  *
7  * We favor readers when reading, meaning new readers can move ahead of writers.
8  * Ex: If i have some readers, then a writer, clearly the writer blocks.  If
9  * more readers come in, they can just come in and the presence of the writer
10  * doesn't stop them.
11  *
12  * You get potential writer starvation, but you also get the property that
13  * if a thread holds a read-lock, that thread can grab the same reader
14  * lock again.  A more general statement would be "if some reader holds
15  * a rwlock, then any other thread (including itself) can get an rlock".
16  *
17  * Similarly, writers favor other writers.  So if a writer is unlocking, it'll
18  * pass the lock to another writer first.  Here, there is potential reader
19  * starvation.
20  *
21  * We also pass locks, instead of letting recently woken threads fight for it.
22  * In the case of a reader wakeup, we know that they all will wake up and read.
23  * Instead of having them fight for a lock and then incref, the waker (the last
24  * writer) will up the count and just wake everyone.
25  *
26  * This also helps when a writer wants to favor another writer.  If we didn't
27  * pass the lock, then a new reader could squeeze in after our old writer
28  * signalled the new writer.  Even worse, in this case, the readers that we
29  * didn't wake up are still sleeping, even though a reader now holds the lock.
30  * It won't deadlock, (since eventually the reader will wake the writer, who
31  * wakes the old readers) but it breaks the notion of a RW lock a bit. */
32
33 #include <rwlock.h>
34 #include <atomic.h>
35 #include <kthread.h>
36
37 void rwinit(struct rwlock *rw_lock)
38 {
39         spinlock_init(&rw_lock->lock);
40         atomic_init(&rw_lock->nr_readers, 0);
41         rw_lock->writing = FALSE;
42         cv_init_with_lock(&rw_lock->readers, &rw_lock->lock);
43         cv_init_with_lock(&rw_lock->writers, &rw_lock->lock);
44 }
45
46 void rlock(struct rwlock *rw_lock)
47 {
48         /* If we already have a reader, we can just increment and return.  This is
49          * the only access to nr_readers outside the lock.  All locked uses need to
50          * be aware that the nr could be concurrently increffed (unless it is 0). */
51         if (atomic_add_not_zero(&rw_lock->nr_readers, 1))
52                 return;
53         /* Here's an alternate style: the broadcaster (a writer) will up the readers
54          * count and just wake us.  All readers just proceed, instead of fighting to
55          * lock and up the count.  The writer 'passed' the rlock to us. */
56         spin_lock(&rw_lock->lock);
57         if (rw_lock->writing) {
58                 cv_wait_and_unlock(&rw_lock->readers);
59                 return;
60         }
61         atomic_inc(&rw_lock->nr_readers);
62         spin_unlock(&rw_lock->lock);
63 }
64
65 bool canrlock(struct rwlock *rw_lock)
66 {
67         if (atomic_add_not_zero(&rw_lock->nr_readers, 1))
68                 return TRUE;
69         spin_lock(&rw_lock->lock);
70         if (rw_lock->writing) {
71                 spin_unlock(&rw_lock->lock);
72                 return FALSE;
73         }
74         atomic_inc(&rw_lock->nr_readers);
75         spin_unlock(&rw_lock->lock);
76         return TRUE;
77 }
78
79 void runlock(struct rwlock *rw_lock)
80 {
81         spin_lock(&rw_lock->lock);
82         /* sub and test will tell us if we got the refcnt to 0, atomically.  syncing
83          * with the atomic_add_not_zero of new readers.  Since we're passing the
84          * lock, we need to make sure someone is sleeping.  Contrast to the wunlock,
85          * where we can just blindly broadcast and add (potentially == 0). */
86         if (atomic_sub_and_test(&rw_lock->nr_readers, 1) &&
87                 rw_lock->writers.nr_waiters) {
88                 /* passing the lock to the one writer we signal. */
89                 rw_lock->writing = TRUE;
90                 __cv_signal(&rw_lock->writers);
91         }
92         spin_unlock(&rw_lock->lock);
93 }
94
95 void wlock(struct rwlock *rw_lock)
96 {
97         spin_lock(&rw_lock->lock);
98         if (atomic_read(&rw_lock->nr_readers) || rw_lock->writing) {
99                 /* If we slept, the lock was passed to us */
100                 cv_wait_and_unlock(&rw_lock->writers);
101                 return;
102         }
103         rw_lock->writing = TRUE;
104         spin_unlock(&rw_lock->lock);
105 }
106
107 void wunlock(struct rwlock *rw_lock)
108 {
109         /* Pass the lock to another writer (we leave writing = TRUE) */
110         spin_lock(&rw_lock->lock);
111         if (rw_lock->writers.nr_waiters) {
112                 /* Just waking one */
113                 __cv_signal(&rw_lock->writers);
114                 spin_unlock(&rw_lock->lock);
115                 return;
116         }
117         rw_lock->writing = FALSE;
118         atomic_set(&rw_lock->nr_readers, rw_lock->readers.nr_waiters);
119         __cv_broadcast(&rw_lock->readers);
120         spin_unlock(&rw_lock->lock);
121 }