File: /usr/src/linux/lib/rwsem-spinlock.c
1 /* rwsem-spinlock.c: R/W semaphores: contention handling functions for generic spinlock
2 * implementation
3 *
4 * Copyright (c) 2001 David Howells (dhowells@redhat.com).
5 * - Derived partially from idea by Andrea Arcangeli <andrea@suse.de>
6 * - Derived also from comments by Linus
7 */
8 #include <linux/rwsem.h>
9 #include <linux/sched.h>
10 #include <linux/module.h>
11
12 struct rwsem_waiter {
13 struct list_head list;
14 struct task_struct *task;
15 unsigned int flags;
16 #define RWSEM_WAITING_FOR_READ 0x00000001
17 #define RWSEM_WAITING_FOR_WRITE 0x00000002
18 };
19
20 #if RWSEM_DEBUG
21 void rwsemtrace(struct rw_semaphore *sem, const char *str)
22 {
23 if (sem->debug)
24 printk("[%d] %s({%d,%d})\n",
25 current->pid,str,sem->activity,list_empty(&sem->wait_list)?0:1);
26 }
27 #endif
28
29 /*
30 * initialise the semaphore
31 */
32 void init_rwsem(struct rw_semaphore *sem)
33 {
34 sem->activity = 0;
35 spin_lock_init(&sem->wait_lock);
36 INIT_LIST_HEAD(&sem->wait_list);
37 #if RWSEM_DEBUG
38 sem->debug = 0;
39 #endif
40 }
41
42 /*
43 * handle the lock being released whilst there are processes blocked on it that can now run
44 * - if we come here, then:
45 * - the 'active count' _reached_ zero
46 * - the 'waiting count' is non-zero
47 * - the spinlock must be held by the caller
48 * - woken process blocks are discarded from the list after having flags zeroised
49 */
50 static inline struct rw_semaphore *__rwsem_do_wake(struct rw_semaphore *sem)
51 {
52 struct rwsem_waiter *waiter;
53 int woken;
54
55 rwsemtrace(sem,"Entering __rwsem_do_wake");
56
57 waiter = list_entry(sem->wait_list.next,struct rwsem_waiter,list);
58
59 /* try to grant a single write lock if there's a writer at the front of the queue
60 * - we leave the 'waiting count' incremented to signify potential contention
61 */
62 if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
63 sem->activity = -1;
64 list_del(&waiter->list);
65 waiter->flags = 0;
66 wake_up_process(waiter->task);
67 goto out;
68 }
69
70 /* grant an infinite number of read locks to the readers at the front of the queue */
71 woken = 0;
72 do {
73 list_del(&waiter->list);
74 waiter->flags = 0;
75 wake_up_process(waiter->task);
76 woken++;
77 if (list_empty(&sem->wait_list))
78 break;
79 waiter = list_entry(sem->wait_list.next,struct rwsem_waiter,list);
80 } while (waiter->flags&RWSEM_WAITING_FOR_READ);
81
82 sem->activity += woken;
83
84 out:
85 rwsemtrace(sem,"Leaving __rwsem_do_wake");
86 return sem;
87 }
88
89 /*
90 * wake a single writer
91 */
92 static inline struct rw_semaphore *__rwsem_wake_one_writer(struct rw_semaphore *sem)
93 {
94 struct rwsem_waiter *waiter;
95
96 sem->activity = -1;
97
98 waiter = list_entry(sem->wait_list.next,struct rwsem_waiter,list);
99 list_del(&waiter->list);
100
101 waiter->flags = 0;
102 wake_up_process(waiter->task);
103 return sem;
104 }
105
106 /*
107 * get a read lock on the semaphore
108 */
109 void __down_read(struct rw_semaphore *sem)
110 {
111 struct rwsem_waiter waiter;
112 struct task_struct *tsk;
113
114 rwsemtrace(sem,"Entering __down_read");
115
116 spin_lock(&sem->wait_lock);
117
118 if (sem->activity>=0 && list_empty(&sem->wait_list)) {
119 /* granted */
120 sem->activity++;
121 spin_unlock(&sem->wait_lock);
122 goto out;
123 }
124
125 tsk = current;
126 set_task_state(tsk,TASK_UNINTERRUPTIBLE);
127
128 /* set up my own style of waitqueue */
129 waiter.task = tsk;
130 waiter.flags = RWSEM_WAITING_FOR_READ;
131
132 list_add_tail(&waiter.list,&sem->wait_list);
133
134 /* we don't need to touch the semaphore struct anymore */
135 spin_unlock(&sem->wait_lock);
136
137 /* wait to be given the lock */
138 for (;;) {
139 if (!waiter.flags)
140 break;
141 schedule();
142 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
143 }
144
145 tsk->state = TASK_RUNNING;
146
147 out:
148 rwsemtrace(sem,"Leaving __down_read");
149 }
150
151 /*
152 * get a write lock on the semaphore
153 * - note that we increment the waiting count anyway to indicate an exclusive lock
154 */
155 void __down_write(struct rw_semaphore *sem)
156 {
157 struct rwsem_waiter waiter;
158 struct task_struct *tsk;
159
160 rwsemtrace(sem,"Entering __down_write");
161
162 spin_lock(&sem->wait_lock);
163
164 if (sem->activity==0 && list_empty(&sem->wait_list)) {
165 /* granted */
166 sem->activity = -1;
167 spin_unlock(&sem->wait_lock);
168 goto out;
169 }
170
171 tsk = current;
172 set_task_state(tsk,TASK_UNINTERRUPTIBLE);
173
174 /* set up my own style of waitqueue */
175 waiter.task = tsk;
176 waiter.flags = RWSEM_WAITING_FOR_WRITE;
177
178 list_add_tail(&waiter.list,&sem->wait_list);
179
180 /* we don't need to touch the semaphore struct anymore */
181 spin_unlock(&sem->wait_lock);
182
183 /* wait to be given the lock */
184 for (;;) {
185 if (!waiter.flags)
186 break;
187 schedule();
188 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
189 }
190
191 tsk->state = TASK_RUNNING;
192
193 out:
194 rwsemtrace(sem,"Leaving __down_write");
195 }
196
197 /*
198 * release a read lock on the semaphore
199 */
200 void __up_read(struct rw_semaphore *sem)
201 {
202 rwsemtrace(sem,"Entering __up_read");
203
204 spin_lock(&sem->wait_lock);
205
206 if (--sem->activity==0 && !list_empty(&sem->wait_list))
207 sem = __rwsem_wake_one_writer(sem);
208
209 spin_unlock(&sem->wait_lock);
210
211 rwsemtrace(sem,"Leaving __up_read");
212 }
213
214 /*
215 * release a write lock on the semaphore
216 */
217 void __up_write(struct rw_semaphore *sem)
218 {
219 rwsemtrace(sem,"Entering __up_write");
220
221 spin_lock(&sem->wait_lock);
222
223 sem->activity = 0;
224 if (!list_empty(&sem->wait_list))
225 sem = __rwsem_do_wake(sem);
226
227 spin_unlock(&sem->wait_lock);
228
229 rwsemtrace(sem,"Leaving __up_write");
230 }
231
232 EXPORT_SYMBOL(init_rwsem);
233 EXPORT_SYMBOL(__down_read);
234 EXPORT_SYMBOL(__down_write);
235 EXPORT_SYMBOL(__up_read);
236 EXPORT_SYMBOL(__up_write);
237 #if RWSEM_DEBUG
238 EXPORT_SYMBOL(rwsemtrace);
239 #endif
240