|
111
|
1 /* GNU Objective C Runtime @synchronized implementation
|
|
145
|
2 Copyright (C) 2010-2020 Free Software Foundation, Inc.
|
|
111
|
3 Contributed by Nicola Pero <nicola.pero@meta-innovation.com>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under the
|
|
|
8 terms of the GNU General Public License as published by the Free Software
|
|
|
9 Foundation; either version 3, or (at your option) any later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
|
|
13 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
|
|
|
14 details.
|
|
|
15
|
|
|
16 Under Section 7 of GPL version 3, you are granted additional
|
|
|
17 permissions described in the GCC Runtime Library Exception, version
|
|
|
18 3.1, as published by the Free Software Foundation.
|
|
|
19
|
|
|
20 You should have received a copy of the GNU General Public License and
|
|
|
21 a copy of the GCC Runtime Library Exception along with this program;
|
|
|
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
|
|
23 <http://www.gnu.org/licenses/>. */
|
|
|
24
|
|
|
25 /* This file implements objc_sync_enter() and objc_sync_exit(), the
|
|
|
26 two functions required to support @synchronized().
|
|
|
27
|
|
|
28 objc_sync_enter(object) needs to get a recursive lock associated
|
|
|
29 with 'object', and lock it.
|
|
|
30
|
|
|
31 objc_sync_exit(object) needs to get the recursive lock associated
|
|
|
32 with 'object', and unlock it. */
|
|
|
33
|
|
|
34 /* To avoid the overhead of continuously allocating and deallocating
|
|
|
35 locks, we implement a pool of locks. When a lock is needed for an
|
|
|
36 object, we get a lock from the pool and associate it with the
|
|
|
37 object.
|
|
|
38
|
|
|
39 The lock pool need to be protected by its own lock (the
|
|
|
40 "protection" lock), which has to be locked then unlocked each time
|
|
|
41 objc_sync_enter() and objc_sync_exit() are called. To reduce the
|
|
|
42 contention on the protection lock, instead of a single pool with a
|
|
|
43 single (global) protection lock we use a number of smaller pools,
|
|
|
44 each with its own pool protection lock. To decide which lock pool
|
|
|
45 to use for each object, we compute a hash from the object pointer.
|
|
|
46
|
|
|
47 The implementation of each lock pool uses a linked list of all the
|
|
|
48 locks in the pool (both unlocked, and locked); this works in the
|
|
|
49 assumption that the number of locks concurrently required is very
|
|
|
50 low. In practice, it seems that you rarely see more than a few
|
|
|
51 locks ever concurrently required.
|
|
|
52
|
|
|
53 A standard case is a thread acquiring a lock recursively, over and
|
|
|
54 over again: for example when most methods of a class are protected
|
|
|
55 by @synchronized(self) but they also call each other. We use
|
|
|
56 thread-local storage to implement a cache and optimize this case.
|
|
|
57 The cache stores locks that the thread successfully acquired,
|
|
|
58 allowing objc_sync_enter() and objc_sync_exit() to locate a lock
|
|
|
59 which is already held by the current thread without having to use
|
|
|
60 any protection lock or synchronization mechanism. It can so detect
|
|
|
61 recursive locks/unlocks, and transform them into no-ops that
|
|
|
62 require no actual locking or synchronization mechanisms at all. */
|
|
|
63
|
|
|
64 /* You can disable the thread-local cache (most likely to benchmark
|
|
|
65 the code with and without it) by compiling with
|
|
|
66 -DSYNC_CACHE_DISABLE, or commenting out the following line. */
|
|
|
67 /* #define SYNC_CACHE_DISABLE */
|
|
|
68
|
|
|
69 /* If thread-local storage is not available, automatically disable the
|
|
|
70 cache. */
|
|
|
71 #ifndef HAVE_TLS
|
|
|
72 # define SYNC_CACHE_DISABLE
|
|
|
73 #endif
|
|
|
74
|
|
|
75 #include "objc-private/common.h"
|
|
|
76 #include "objc/objc-sync.h" /* For objc_sync_enter(), objc_sync_exit() */
|
|
|
77 #include "objc/runtime.h" /* For objc_malloc() */
|
|
|
78 #include "objc/thr.h" /* For objc_mutex_loc() and similar */
|
|
|
79 #include "objc-private/objc-sync.h" /* For __objc_sync_init() */
|
|
|
80
|
|
|
81 /* We have 32 pools of locks, each of them protected by its own
|
|
|
82 protection lock. It's tempting to increase this number to reduce
|
|
|
83 contention; but in our tests it is high enough. */
|
|
|
84 #define SYNC_NUMBER_OF_POOLS 32
|
|
|
85
|
|
|
86 /* Given an object, it determines which pool contains the associated
|
|
|
87 lock. */
|
|
|
88 #define SYNC_OBJECT_HASH(OBJECT) ((((size_t)OBJECT >> 8) ^ (size_t)OBJECT) & (SYNC_NUMBER_OF_POOLS - 1))
|
|
|
89
|
|
|
90 /* The locks protecting each pool. */
|
|
|
91 static objc_mutex_t sync_pool_protection_locks[SYNC_NUMBER_OF_POOLS];
|
|
|
92
|
|
|
93 /* The data structure (linked list) holding the locks. */
|
|
|
94 typedef struct lock_node
|
|
|
95 {
|
|
|
96 /* Pointer to next entry on the list. NULL indicates end of list.
|
|
|
97 You need to hold the appropriate sync_pool_protection_locks[N] to
|
|
|
98 read or write this variable. */
|
|
|
99 struct lock_node *next;
|
|
|
100
|
|
|
101 /* The (recursive) lock. Allocated when the node is created, and
|
|
|
102 always not-NULL, and unchangeable, after that. */
|
|
|
103 objc_mutex_t lock;
|
|
|
104
|
|
|
105 /* This is how many times the objc_mutex_lock() has been called on
|
|
|
106 the lock (it is 0 when the lock is unused). Used to track when
|
|
|
107 the lock is no longer associated with an object and can be reused
|
|
|
108 for another object. It records "real" locks, potentially (but
|
|
|
109 not necessarily) by multiple threads. You need to hold the
|
|
|
110 appropriate sync_pool_protection_locks[N] to read or write this
|
|
|
111 variable. */
|
|
|
112 unsigned int usage_count;
|
|
|
113
|
|
|
114 /* The object that the lock is associated with. This variable can
|
|
|
115 only be written when holding the sync_pool_protection_locks[N]
|
|
|
116 and when node->usage_count == 0, ie, the lock is not being used.
|
|
|
117 You can read this variable either when you hold the
|
|
|
118 sync_pool_protection_locks[N] or when you hold node->lock,
|
|
|
119 because in that case you know that node->usage_count can't get to
|
|
|
120 zero until you release the lock. It is valid to have usage_count
|
|
|
121 == 0 and object != nil; in that case, the lock is not currently
|
|
|
122 being used, but is still currently associated with the
|
|
|
123 object. */
|
|
|
124 id object;
|
|
|
125
|
|
|
126 /* This is a counter reserved for use by the thread currently
|
|
|
127 holding the lock. So, you need to hold node->lock to read or
|
|
|
128 write this variable. It is normally 0, and if the cache is not
|
|
|
129 being used, it is kept at 0 (even if recursive locks are being
|
|
|
130 done; in that case, no difference is made between recursive and
|
|
|
131 non-recursive locks: they all increase usage_count, and call
|
|
|
132 objc_mutex_lock()). When the cache is being used, a thread may
|
|
|
133 be able to find a lock that it already holds using the cache; in
|
|
|
134 that case, to perform additional locks/unlocks it can
|
|
|
135 increase/decrease the recursive_usage_count (which does not
|
|
|
136 require any synchronization with other threads, since it's
|
|
|
137 protected by the node->lock itself) instead of the usage_count
|
|
|
138 (which requires locking the pool protection lock). And it can
|
|
|
139 skip the call to objc_mutex_lock/unlock too. */
|
|
|
140 unsigned int recursive_usage_count;
|
|
|
141 } *lock_node_ptr;
|
|
|
142
|
|
|
143
|
|
|
144 /* The pools of locks. Each of them is a linked list of lock_nodes.
|
|
|
145 In the list we keep both unlocked and locked nodes. */
|
|
|
146 static lock_node_ptr sync_pool_array[SYNC_NUMBER_OF_POOLS];
|
|
|
147
|
|
|
148 #ifndef SYNC_CACHE_DISABLE
|
|
|
149 /* We store a cache of locks acquired by each thread in thread-local
|
|
|
150 storage. */
|
|
|
151 static __thread lock_node_ptr *lock_cache = NULL;
|
|
|
152
|
|
|
153 /* This is a conservative implementation that uses a static array of
|
|
|
154 fixed size as cache. Because the cache is an array that we scan
|
|
|
155 linearly, the bigger it is, the slower it gets. This does not
|
|
|
156 matter much at small sizes (eg, the overhead of checking 8 cache
|
|
|
157 slots instead of 4 is very small compared to the other overheads
|
|
|
158 involved such as function calls and lock/unlock operations), but at
|
|
|
159 large sizes it becomes important as obviously there is a size over
|
|
|
160 which using the cache backfires: the lookup is so slow that the
|
|
|
161 cache slows down the software instead of speeding it up. In
|
|
|
162 practice, it seems that most threads use a small number of
|
|
|
163 concurrent locks, so we have a conservative implementation with a
|
|
|
164 fixed-size cache of 8 locks which gives a very predictable
|
|
|
165 behaviour. If a thread locks lots of different locks, only the
|
|
|
166 first 8 get the speed benefits of the cache, but the cache remains
|
|
|
167 always small, fast and predictable.
|
|
|
168
|
|
|
169 SYNC_CACHE_SIZE is the size of the lock cache for each thread. */
|
|
|
170 #define SYNC_CACHE_SIZE 8
|
|
|
171 #endif /* SYNC_CACHE_DISABLE */
|
|
|
172
|
|
|
173 /* Called at startup by init.c. */
|
|
|
174 void
|
|
|
175 __objc_sync_init (void)
|
|
|
176 {
|
|
|
177 int i;
|
|
|
178
|
|
|
179 for (i = 0; i < SYNC_NUMBER_OF_POOLS; i++)
|
|
|
180 {
|
|
|
181 lock_node_ptr new_node;
|
|
|
182
|
|
|
183 /* Create a protection lock for each pool. */
|
|
|
184 sync_pool_protection_locks[i] = objc_mutex_allocate ();
|
|
|
185
|
|
|
186 /* Preallocate a lock per pool. */
|
|
|
187 new_node = objc_malloc (sizeof (struct lock_node));
|
|
|
188 new_node->lock = objc_mutex_allocate ();
|
|
|
189 new_node->object = nil;
|
|
|
190 new_node->usage_count = 0;
|
|
|
191 new_node->recursive_usage_count = 0;
|
|
|
192 new_node->next = NULL;
|
|
|
193
|
|
|
194 sync_pool_array[i] = new_node;
|
|
|
195 }
|
|
|
196 }
|
|
|
197
|
|
|
198 int
|
|
|
199 objc_sync_enter (id object)
|
|
|
200 {
|
|
|
201 #ifndef SYNC_CACHE_DISABLE
|
|
|
202 int free_cache_slot;
|
|
|
203 #endif
|
|
|
204 int hash;
|
|
|
205 lock_node_ptr node;
|
|
|
206 lock_node_ptr unused_node;
|
|
|
207
|
|
|
208 if (object == nil)
|
|
|
209 return OBJC_SYNC_SUCCESS;
|
|
|
210
|
|
|
211 #ifndef SYNC_CACHE_DISABLE
|
|
|
212 if (lock_cache == NULL)
|
|
|
213 {
|
|
|
214 /* Note that this calloc only happen only once per thread, the
|
|
|
215 very first time a thread does a objc_sync_enter(). */
|
|
|
216 lock_cache = objc_calloc (SYNC_CACHE_SIZE, sizeof (lock_node_ptr));
|
|
|
217 }
|
|
|
218
|
|
|
219 /* Check the cache to see if we have a record of having already
|
|
|
220 locked the lock corresponding to this object. While doing so,
|
|
|
221 keep track of the first free cache node in case we need it
|
|
|
222 later. */
|
|
|
223 node = NULL;
|
|
|
224 free_cache_slot = -1;
|
|
|
225
|
|
|
226 {
|
|
|
227 int i;
|
|
|
228 for (i = 0; i < SYNC_CACHE_SIZE; i++)
|
|
|
229 {
|
|
|
230 lock_node_ptr locked_node = lock_cache[i];
|
|
|
231
|
|
|
232 if (locked_node == NULL)
|
|
|
233 {
|
|
|
234 if (free_cache_slot == -1)
|
|
|
235 free_cache_slot = i;
|
|
|
236 }
|
|
|
237 else if (locked_node->object == object)
|
|
|
238 {
|
|
|
239 node = locked_node;
|
|
|
240 break;
|
|
|
241 }
|
|
|
242 }
|
|
|
243 }
|
|
|
244
|
|
|
245 if (node != NULL)
|
|
|
246 {
|
|
|
247 /* We found the lock. Increase recursive_usage_count, which is
|
|
|
248 protected by node->lock, which we already hold. */
|
|
|
249 node->recursive_usage_count++;
|
|
|
250
|
|
|
251 /* There is no need to actually lock anything, since we already
|
|
|
252 hold the lock. Correspondingly, objc_sync_exit() will just
|
|
|
253 decrease recursive_usage_count and do nothing to unlock. */
|
|
|
254 return OBJC_SYNC_SUCCESS;
|
|
|
255 }
|
|
|
256 #endif /* SYNC_CACHE_DISABLE */
|
|
|
257
|
|
|
258 /* The following is the standard lookup for the lock in the standard
|
|
|
259 pool lock. It requires a pool protection lock. */
|
|
|
260 hash = SYNC_OBJECT_HASH(object);
|
|
|
261
|
|
|
262 /* Search for an existing lock for 'object'. While searching, make
|
|
|
263 note of any unused lock if we find any. */
|
|
|
264 unused_node = NULL;
|
|
|
265
|
|
|
266 objc_mutex_lock (sync_pool_protection_locks[hash]);
|
|
|
267
|
|
|
268 node = sync_pool_array[hash];
|
|
|
269
|
|
|
270 while (node != NULL)
|
|
|
271 {
|
|
|
272 if (node->object == object)
|
|
|
273 {
|
|
|
274 /* We found the lock. */
|
|
|
275 node->usage_count++;
|
|
|
276 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
277
|
|
|
278 #ifndef SYNC_CACHE_DISABLE
|
|
|
279 /* Put it in the cache. */
|
|
|
280 if (free_cache_slot != -1)
|
|
|
281 lock_cache[free_cache_slot] = node;
|
|
|
282 #endif
|
|
|
283
|
|
|
284 /* Lock it. */
|
|
|
285 objc_mutex_lock (node->lock);
|
|
|
286
|
|
|
287 return OBJC_SYNC_SUCCESS;
|
|
|
288 }
|
|
|
289
|
|
|
290 if (unused_node == NULL && node->usage_count == 0)
|
|
|
291 {
|
|
|
292 /* We found the first unused node. Record it. */
|
|
|
293 unused_node = node;
|
|
|
294 }
|
|
|
295
|
|
|
296 node = node->next;
|
|
|
297 }
|
|
|
298
|
|
|
299 /* An existing lock for 'object' could not be found. */
|
|
|
300 if (unused_node != NULL)
|
|
|
301 {
|
|
|
302 /* But we found a unused lock; use it. */
|
|
|
303 unused_node->object = object;
|
|
|
304 unused_node->usage_count = 1;
|
|
|
305 unused_node->recursive_usage_count = 0;
|
|
|
306 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
307
|
|
|
308 #ifndef SYNC_CACHE_DISABLE
|
|
|
309 if (free_cache_slot != -1)
|
|
|
310 lock_cache[free_cache_slot] = unused_node;
|
|
|
311 #endif
|
|
|
312
|
|
|
313 objc_mutex_lock (unused_node->lock);
|
|
|
314
|
|
|
315 return OBJC_SYNC_SUCCESS;
|
|
|
316 }
|
|
|
317 else
|
|
|
318 {
|
|
|
319 /* There are no unused nodes; allocate a new node. */
|
|
|
320 lock_node_ptr new_node;
|
|
|
321
|
|
|
322 /* Create the node. */
|
|
|
323 new_node = objc_malloc (sizeof (struct lock_node));
|
|
|
324 new_node->lock = objc_mutex_allocate ();
|
|
|
325 new_node->object = object;
|
|
|
326 new_node->usage_count = 1;
|
|
|
327 new_node->recursive_usage_count = 0;
|
|
|
328
|
|
|
329 /* Attach it at the beginning of the pool. */
|
|
|
330 new_node->next = sync_pool_array[hash];
|
|
|
331 sync_pool_array[hash] = new_node;
|
|
|
332 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
333
|
|
|
334 #ifndef SYNC_CACHE_DISABLE
|
|
|
335 if (free_cache_slot != -1)
|
|
|
336 lock_cache[free_cache_slot] = new_node;
|
|
|
337 #endif
|
|
|
338
|
|
|
339 objc_mutex_lock (new_node->lock);
|
|
|
340
|
|
|
341 return OBJC_SYNC_SUCCESS;
|
|
|
342 }
|
|
|
343 }
|
|
|
344
|
|
|
345 int
|
|
|
346 objc_sync_exit (id object)
|
|
|
347 {
|
|
|
348 int hash;
|
|
|
349 lock_node_ptr node;
|
|
|
350
|
|
|
351 if (object == nil)
|
|
|
352 return OBJC_SYNC_SUCCESS;
|
|
|
353
|
|
|
354 #ifndef SYNC_CACHE_DISABLE
|
|
|
355 if (lock_cache != NULL)
|
|
|
356 {
|
|
|
357 int i;
|
|
|
358
|
|
|
359 /* Find the lock in the cache. */
|
|
|
360 node = NULL;
|
|
|
361 for (i = 0; i < SYNC_CACHE_SIZE; i++)
|
|
|
362 {
|
|
|
363 lock_node_ptr locked_node = lock_cache[i];
|
|
|
364
|
|
|
365 if (locked_node != NULL && locked_node->object == object)
|
|
|
366 {
|
|
|
367 node = locked_node;
|
|
|
368 break;
|
|
|
369 }
|
|
|
370 }
|
|
|
371 /* Note that, if a node was found in the cache, the variable i
|
|
|
372 now holds the index where it was found, which will be used to
|
|
|
373 remove it from the cache. */
|
|
|
374 if (node != NULL)
|
|
|
375 {
|
|
|
376 if (node->recursive_usage_count > 0)
|
|
|
377 {
|
|
|
378 node->recursive_usage_count--;
|
|
|
379 return OBJC_SYNC_SUCCESS;
|
|
|
380 }
|
|
|
381 else
|
|
|
382 {
|
|
|
383 /* We need to do a real unlock. */
|
|
|
384 hash = SYNC_OBJECT_HASH(object);
|
|
|
385
|
|
|
386 /* TODO: If we had atomic increase/decrease operations
|
|
|
387 with memory barriers, we could avoid the lock
|
|
|
388 here! */
|
|
|
389 objc_mutex_lock (sync_pool_protection_locks[hash]);
|
|
|
390 node->usage_count--;
|
|
|
391 /* Normally, we do not reset object to nil here. We'll
|
|
|
392 leave the lock associated with that object, at zero
|
|
|
393 usage count. This makes it slightly more efficient to
|
|
|
394 provide a lock for that object if (as likely)
|
|
|
395 requested again. If the object is deallocated, we
|
|
|
396 don't care. It will never match a new lock that is
|
|
|
397 requested, and the node will be reused at some point.
|
|
|
398
|
|
|
399 But, if garbage collection is enabled, leaving a
|
|
|
400 pointer to the object in memory might prevent the
|
|
|
401 object from being released. In that case, we remove
|
|
|
402 it (TODO: maybe we should avoid using the garbage
|
|
|
403 collector at all ? Nothing is ever deallocated in
|
|
|
404 this file). */
|
|
|
405 #if OBJC_WITH_GC
|
|
|
406 node->object = nil;
|
|
|
407 #endif
|
|
|
408 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
409
|
|
|
410 /* PS: Between objc_mutex_unlock
|
|
|
411 (sync_pool_protection_locks[hash]) and
|
|
|
412 objc_mutex_unlock (node->lock), the pool is unlocked
|
|
|
413 so other threads may allocate this same lock to
|
|
|
414 another object (!). This is not a problem, but it is
|
|
|
415 curious. */
|
|
|
416 objc_mutex_unlock (node->lock);
|
|
|
417
|
|
|
418 /* Remove the node from the cache. */
|
|
|
419 lock_cache[i] = NULL;
|
|
|
420
|
|
|
421 return OBJC_SYNC_SUCCESS;
|
|
|
422 }
|
|
|
423 }
|
|
|
424 }
|
|
|
425 #endif
|
|
|
426
|
|
|
427 /* The cache either wasn't there, or didn't work (eg, we overflowed
|
|
|
428 it at some point and stopped recording new locks in the cache).
|
|
|
429 Proceed with a full search of the lock pool. */
|
|
|
430 hash = SYNC_OBJECT_HASH(object);
|
|
|
431
|
|
|
432 objc_mutex_lock (sync_pool_protection_locks[hash]);
|
|
|
433
|
|
|
434 /* Search for an existing lock for 'object'. */
|
|
|
435 node = sync_pool_array[hash];
|
|
|
436
|
|
|
437 while (node != NULL)
|
|
|
438 {
|
|
|
439 if (node->object == object)
|
|
|
440 {
|
|
|
441 /* We found the lock. */
|
|
|
442 node->usage_count--;
|
|
|
443 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
444
|
|
|
445 objc_mutex_unlock (node->lock);
|
|
|
446
|
|
|
447 /* No need to remove the node from the cache, since it
|
|
|
448 wasn't found in the cache when we looked for it! */
|
|
|
449 return OBJC_SYNC_SUCCESS;
|
|
|
450 }
|
|
|
451
|
|
|
452 node = node->next;
|
|
|
453 }
|
|
|
454
|
|
|
455 objc_mutex_unlock (sync_pool_protection_locks[hash]);
|
|
|
456
|
|
|
457 /* A lock for 'object' to unlock could not be found (!!). */
|
|
|
458 return OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
|
|
|
459 }
|
