Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2013, 2014 Nicira, Inc.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : #include <config.h>
18 : :
19 : : #include "fat-rwlock.h"
20 : :
21 : : #include <errno.h>
22 : :
23 : : #include "openvswitch/hmap.h"
24 : : #include "openvswitch/list.h"
25 : : #include "ovs-thread.h"
26 : : #include "random.h"
27 : :
28 : : struct fat_rwlock_slot {
29 : : /* Membership in rwlock's list of "struct fat_rwlock_slot"s.
30 : : *
31 : : * fat_rwlock_destroy() sets 'rwlock' to NULL to indicate that this
32 : : * slot may be destroyed. */
33 : : struct ovs_list list_node; /* In struct rwlock's 'threads' list. */
34 : : struct fat_rwlock *rwlock; /* Owner. */
35 : :
36 : : /* Mutex.
37 : : *
38 : : * A thread holding the read-lock holds its own mutex.
39 : : *
40 : : * A thread holding the write-lock holds every thread's mutex, plus
41 : : * 'rwlock->mutex'. */
42 : : struct ovs_mutex mutex;
43 : :
44 : : /* This thread's locking status for 'rwlock':
45 : : *
46 : : * - 0: This thread does not have any lock on 'rwlock'. This thread
47 : : * does not have 'mutex' locked.
48 : : *
49 : : * - 1: This thread has a read-lock on 'rwlock' and holds 'mutex'.
50 : : *
51 : : * - 2...UINT_MAX-1: This thread has recursively taken the read-lock on
52 : : * 'rwlock' to the level of 'depth'. This thread holds 'mutex'.
53 : : *
54 : : * - UINT_MAX: This thread has the write-lock on 'rwlock' and holds
55 : : * 'mutex' (plus the 'mutex' of all of 'rwlock''s other slots).
56 : : *
57 : : * Accessed only by the slot's own thread, so no synchronization is
58 : : * needed. */
59 : : unsigned int depth;
60 : : };
61 : :
62 : : static void
63 : 329 : free_slot(struct fat_rwlock_slot *slot)
64 : : {
65 [ - + ]: 329 : if (slot->depth) {
66 : 0 : abort();
67 : : }
68 : :
69 : 329 : ovs_list_remove(&slot->list_node);
70 : 329 : free_cacheline(slot);
71 : 329 : }
72 : :
73 : : static void
74 : 141 : slot_destructor(void *slot_)
75 : : {
76 : 141 : struct fat_rwlock_slot *slot = slot_;
77 : 141 : struct fat_rwlock *rwlock = slot->rwlock;
78 : :
79 : 141 : ovs_mutex_lock(&rwlock->mutex);
80 : 141 : free_slot(slot);
81 : 141 : ovs_mutex_unlock(&rwlock->mutex);
82 : 141 : }
83 : :
84 : : /* Initialize 'rwlock' as a new fat_rwlock. */
85 : : void
86 : 1353 : fat_rwlock_init(struct fat_rwlock *rwlock)
87 : : {
88 : 1353 : ovsthread_key_create(&rwlock->key, slot_destructor);
89 : 1353 : ovs_mutex_init(&rwlock->mutex);
90 : 1353 : ovs_mutex_lock(&rwlock->mutex);
91 : 1353 : ovs_list_init(&rwlock->threads);
92 : 1353 : ovs_mutex_unlock(&rwlock->mutex);
93 : 1353 : }
94 : :
95 : : /* Destroys 'rwlock', which must not be locked or otherwise in use by any
96 : : * thread. */
97 : : void
98 : 188 : fat_rwlock_destroy(struct fat_rwlock *rwlock)
99 : : {
100 : : struct fat_rwlock_slot *slot, *next;
101 : :
102 : : /* Order is important here. By destroying the thread-specific data first,
103 : : * before we destroy the slots, we ensure that the thread-specific
104 : : * data destructor can't race with our loop below. */
105 : 188 : ovsthread_key_delete(rwlock->key);
106 : :
107 [ + + ][ + + ]: 376 : LIST_FOR_EACH_SAFE (slot, next, list_node, &rwlock->threads) {
108 : 188 : free_slot(slot);
109 : : }
110 : 188 : ovs_mutex_destroy(&rwlock->mutex);
111 : 188 : }
112 : :
113 : : static struct fat_rwlock_slot *
114 : 111283 : fat_rwlock_get_slot__(struct fat_rwlock *rwlock)
115 : : {
116 : : struct fat_rwlock_slot *slot;
117 : :
118 : : /* Fast path. */
119 : 111283 : slot = ovsthread_getspecific(rwlock->key);
120 [ + + ]: 111283 : if (slot) {
121 : 109793 : return slot;
122 : : }
123 : :
124 : : /* Slow path: create a new slot for 'rwlock' in this thread. */
125 : :
126 : 1490 : slot = xmalloc_cacheline(sizeof *slot);
127 : 1490 : slot->rwlock = rwlock;
128 : 1490 : ovs_mutex_init(&slot->mutex);
129 : 1490 : slot->depth = 0;
130 : :
131 : 1490 : ovs_mutex_lock(&rwlock->mutex);
132 : 1490 : ovs_list_push_back(&rwlock->threads, &slot->list_node);
133 : 1490 : ovs_mutex_unlock(&rwlock->mutex);
134 : :
135 : 1490 : ovsthread_setspecific(rwlock->key, slot);
136 : :
137 : 1490 : return slot;
138 : : }
139 : :
140 : : /* Locks 'rwlock' for reading. The read-lock is recursive: it may be acquired
141 : : * any number of times by a single thread (which must then release it the same
142 : : * number of times for it to truly be released). */
143 : : void
144 : 22675 : fat_rwlock_rdlock(const struct fat_rwlock *rwlock_)
145 : : OVS_ACQ_RDLOCK(rwlock_)
146 : : OVS_NO_THREAD_SAFETY_ANALYSIS
147 : : {
148 : 22675 : struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
149 : 22675 : struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
150 : :
151 [ - + - ]: 22675 : switch (this->depth) {
152 : : case UINT_MAX:
153 : : /* This thread already holds the write-lock. */
154 : 0 : abort();
155 : :
156 : : case 0:
157 : 22675 : ovs_mutex_lock(&this->mutex);
158 : : /* fall through */
159 : : default:
160 : 22675 : this->depth++;
161 : 22675 : break;
162 : : }
163 : 22675 : }
164 : :
165 : : static struct fat_rwlock_slot *
166 : 6185 : fat_rwlock_try_get_slot__(struct fat_rwlock *rwlock)
167 : : {
168 : : struct fat_rwlock_slot *slot;
169 : :
170 : : /* Fast path. */
171 : 6185 : slot = ovsthread_getspecific(rwlock->key);
172 [ + + ]: 6185 : if (slot) {
173 : 6165 : return slot;
174 : : }
175 : :
176 : : /* Slow path: create a new slot for 'rwlock' in this thread. */
177 : :
178 [ + - ]: 20 : if (!ovs_mutex_trylock(&rwlock->mutex)) {
179 : 20 : slot = xmalloc_cacheline(sizeof *slot);
180 : 20 : slot->rwlock = rwlock;
181 : 20 : ovs_mutex_init(&slot->mutex);
182 : 20 : slot->depth = 0;
183 : :
184 : 20 : ovs_list_push_back(&rwlock->threads, &slot->list_node);
185 : 20 : ovs_mutex_unlock(&rwlock->mutex);
186 : 20 : ovsthread_setspecific(rwlock->key, slot);
187 : : }
188 : :
189 : 20 : return slot;
190 : : }
191 : :
192 : : /* Tries to lock 'rwlock' for reading. If successful, returns 0. If taking
193 : : * the lock would require blocking, returns EBUSY (without blocking). */
194 : : int
195 : 6185 : fat_rwlock_tryrdlock(const struct fat_rwlock *rwlock_)
196 : : OVS_TRY_RDLOCK(0, rwlock_)
197 : : OVS_NO_THREAD_SAFETY_ANALYSIS
198 : : {
199 : 6185 : struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
200 : 6185 : struct fat_rwlock_slot *this = fat_rwlock_try_get_slot__(rwlock);
201 : : int error;
202 : :
203 [ - + ]: 6185 : if (!this) {
204 : 0 : return EBUSY;
205 : : }
206 : :
207 [ + + + ]: 6185 : switch (this->depth) {
208 : : case UINT_MAX:
209 : 3 : return EBUSY;
210 : :
211 : : case 0:
212 : 5727 : error = ovs_mutex_trylock(&this->mutex);
213 [ - + ]: 5727 : if (error) {
214 : 0 : return error;
215 : : }
216 : : /* fall through */
217 : : default:
218 : 6182 : this->depth++;
219 : 6182 : break;
220 : : }
221 : :
222 : 6182 : return 0;
223 : : }
224 : :
225 : : /* Locks 'rwlock' for writing.
226 : : *
227 : : * The write lock is not recursive. */
228 : : void
229 : 30151 : fat_rwlock_wrlock(const struct fat_rwlock *rwlock_)
230 : : OVS_ACQ_WRLOCK(rwlock_)
231 : : OVS_NO_THREAD_SAFETY_ANALYSIS
232 : : {
233 : 30151 : struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
234 : 30151 : struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
235 : : struct fat_rwlock_slot *slot;
236 : :
237 [ - + ]: 30151 : ovs_assert(!this->depth);
238 : 30151 : this->depth = UINT_MAX;
239 : :
240 : 30151 : ovs_mutex_lock(&rwlock->mutex);
241 [ + + ]: 82912 : LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
242 : 52761 : ovs_mutex_lock(&slot->mutex);
243 : : }
244 : 30151 : }
245 : :
246 : : /* Unlocks 'rwlock', which the current thread must have locked for reading or
247 : : * for writing. If the read lock has been taken recursively, it must be
248 : : * released the same number of times to be truly released. */
249 : : void
250 : 58457 : fat_rwlock_unlock(const struct fat_rwlock *rwlock_)
251 : : OVS_RELEASES(rwlock_)
252 : : OVS_NO_THREAD_SAFETY_ANALYSIS
253 : : {
254 : 58457 : struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
255 : 58457 : struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
256 : : struct fat_rwlock_slot *slot;
257 : :
258 [ + - + + ]: 58457 : switch (this->depth) {
259 : : case UINT_MAX:
260 [ + + ]: 81794 : LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
261 : 52194 : ovs_mutex_unlock(&slot->mutex);
262 : : }
263 : 29600 : ovs_mutex_unlock(&rwlock->mutex);
264 : 29600 : this->depth = 0;
265 : 29600 : break;
266 : :
267 : : case 0:
268 : : /* This thread doesn't hold any lock. */
269 : 0 : abort();
270 : :
271 : : case 1:
272 : 28402 : ovs_mutex_unlock(&this->mutex);
273 : : default:
274 : 28857 : this->depth--;
275 : 28857 : break;
276 : : }
277 : 58457 : }
|
