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 /* 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 slighly 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 } 460