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