runtime/objc-sync.m

   1 /*
   2  * Copyright (c) 1999-2007 Apple Inc.  All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #include <stdbool.h>
  25 #include <stdlib.h>
  26 #include <sys/time.h>
  27 #include <pthread.h>
  28 #include <errno.h>
  29 #include <AssertMacros.h>
  30 #include <libkern/OSAtomic.h>
  31
  32 #include "objc-sync.h"
  33 #include "objc-private.h"
  34
  35 //
  36 // Allocate a lock only when needed.  Since few locks are needed at any point
  37 // in time, keep them on a single list.
  38 //
  39
  40 static pthread_mutexattr_t      sRecursiveLockAttr;
  41 static bool                     sRecursiveLockAttrIntialized = false;
  42
  43 static pthread_mutexattr_t* recursiveAttributes()
  44 {
  45     if ( !sRecursiveLockAttrIntialized ) {
  46         int err = pthread_mutexattr_init(&sRecursiveLockAttr);
  47         require_noerr_string(err, done, "pthread_mutexattr_init failed");
  48
  49         err = pthread_mutexattr_settype(&sRecursiveLockAttr, PTHREAD_MUTEX_RECURSIVE);
  50         require_noerr_string(err, done, "pthread_mutexattr_settype failed");
  51
  52         sRecursiveLockAttrIntialized = true;
  53    }
  54
  55 done:
  56     return &sRecursiveLockAttr;
  57 }
  58
  59
  60 typedef uintptr_t spin_lock_t;
  61 extern void _spin_lock(spin_lock_t *lockp);
  62 extern int  _spin_lock_try(spin_lock_t *lockp);
  63 extern void _spin_unlock(spin_lock_t *lockp);
  64
  65 typedef struct SyncData {
  66     struct SyncData* nextData;
  67     id               object;
  68     int              threadCount;  // number of THREADS using this block
  69     pthread_mutex_t  mutex;
  70     pthread_cond_t   conditionVariable;
  71 } SyncData;
  72
  73 typedef struct {
  74     SyncData *data;
  75     unsigned int lockCount;  // number of times THIS THREAD locked this block
  76 } SyncCacheItem;
  77
  78 typedef struct SyncCache {
  79     unsigned int allocated;
  80     unsigned int used;
  81     SyncCacheItem list[0];
  82 } SyncCache;
  83
  84 typedef struct {
  85     spin_lock_t lock;
  86     SyncData *data;
  87 } SyncList __attribute__((aligned(64)));
  88 // aligned to put locks on separate cache lines
  89
  90 // Use multiple parallel lists to decrease contention among unrelated objects.
  91 #define COUNT 16
  92 #define HASH(obj) ((((uintptr_t)(obj)) >> 5) & (COUNT - 1))
  93 #define LOCK_FOR_OBJ(obj) sDataLists[HASH(obj)].lock
  94 #define LIST_FOR_OBJ(obj) sDataLists[HASH(obj)].data
  95 static SyncList sDataLists[COUNT];
  96
  97
  98 enum usage { ACQUIRE, RELEASE, CHECK };
  99
 100 static SyncCache *fetch_cache(BOOL create)
 101 {
 102     _objc_pthread_data *data;
 103
 104     data = _objc_fetch_pthread_data(create);
 105     if (!data  &&  !create) return NULL;
 106
 107     if (!data->syncCache) {
 108         if (!create) {
 109             return NULL;
 110         } else {
 111             int count = 4;
 112             data->syncCache = calloc(1, sizeof(SyncCache) +
 113                                      count*sizeof(SyncCacheItem));
 114             data->syncCache->allocated = count;
 115         }
 116     }
 117
 118     // Make sure there's at least one open slot in the list.
 119     if (data->syncCache->allocated == data->syncCache->used) {
 120         data->syncCache->allocated *= 2;
 121         data->syncCache =
 122             realloc(data->syncCache, sizeof(SyncCache)
 123                     + data->syncCache->allocated * sizeof(SyncCacheItem));
 124     }
 125
 126     return data->syncCache;
 127 }
 128
 129
 130 __private_extern__ void _destroySyncCache(struct SyncCache *cache)
 131 {
 132     if (cache) free(cache);
 133 }
 134
 135
 136 static SyncData* id2data(id object, enum usage why)
 137 {
 138     spin_lock_t *lockp = &LOCK_FOR_OBJ(object);
 139     SyncData **listp = &LIST_FOR_OBJ(object);
 140     SyncData* result = NULL;
 141     int err;
 142
 143     // Check per-thread cache of already-owned locks for matching object
 144     SyncCache *cache = fetch_cache(NO);
 145     if (cache) {
 146         int i;
 147         for (i = 0; i < cache->used; i++) {
 148             SyncCacheItem *item = &cache->list[i];
 149             if (item->data->object != object) continue;
 150
 151             // Found a match.
 152             result = item->data;
 153             require_action_string(result->threadCount > 0, cache_done,
 154                                   result = NULL, "id2data cache is buggy");
 155             require_action_string(item->lockCount > 0, cache_done,
 156                                   result = NULL, "id2data cache is buggy");
 157
 158             switch(why) {
 159             case ACQUIRE:
 160                 item->lockCount++;
 161                 break;
 162             case RELEASE:
 163                 item->lockCount--;
 164                 if (item->lockCount == 0) {
 165                     // remove from per-thread cache
 166                     cache->list[i] = cache->list[--cache->used];
 167                     // atomic because may collide with concurrent ACQUIRE
 168                     OSAtomicDecrement32Barrier(&result->threadCount);
 169                 }
 170                 break;
 171             case CHECK:
 172                 // do nothing
 173                 break;
 174             }
 175
 176         cache_done:
 177             return result;
 178         }
 179     }
 180
 181     // Thread cache didn't find anything.
 182     // Walk in-use list looking for matching object
 183     // Spinlock prevents multiple threads from creating multiple
 184     // locks for the same new object.
 185     // We could keep the nodes in some hash table if we find that there are
 186     // more than 20 or so distinct locks active, but we don't do that now.
 187
 188     _spin_lock(lockp);
 189
 190     SyncData* p;
 191     SyncData* firstUnused = NULL;
 192     for (p = *listp; p != NULL; p = p->nextData) {
 193         if ( p->object == object ) {
 194             result = p;
 195             // atomic because may collide with concurrent RELEASE
 196             OSAtomicIncrement32Barrier(&result->threadCount);
 197             goto done;
 198         }
 199         if ( (firstUnused == NULL) && (p->threadCount == 0) )
 200             firstUnused = p;
 201     }
 202
 203     // no SyncData currently associated with object
 204     if ( (why == RELEASE) || (why == CHECK) )
 205         goto done;
 206
 207     // an unused one was found, use it
 208     if ( firstUnused != NULL ) {
 209         result = firstUnused;
 210         result->object = object;
 211         result->threadCount = 1;
 212         goto done;
 213     }
 214
 215     // malloc a new SyncData and add to list.
 216     // XXX calling malloc with a global lock held is bad practice,
 217     // might be worth releasing the lock, mallocing, and searching again.
 218     // But since we never free these guys we won't be stuck in malloc very often.
 219     result = (SyncData*)malloc(sizeof(SyncData));
 220     result->object = object;
 221     result->threadCount = 1;
 222     err = pthread_mutex_init(&result->mutex, recursiveAttributes());
 223     require_noerr_string(err, done, "pthread_mutex_init failed");
 224     err = pthread_cond_init(&result->conditionVariable, NULL);
 225     require_noerr_string(err, done, "pthread_cond_init failed");
 226     result->nextData = *listp;
 227     *listp = result;
 228
 229  done:
 230     _spin_unlock(lockp);
 231     if (result) {
 232         // Only new ACQUIRE should get here.
 233         // All RELEASE and CHECK and recursive ACQUIRE are
 234         // handled by the per-thread cache above.
 235
 236         require_string(result != NULL, really_done, "id2data is buggy");
 237         require_action_string(why == ACQUIRE, really_done,
 238                               result = NULL, "id2data is buggy");
 239         require_action_string(result->object == object, really_done,
 240                               result = NULL, "id2data is buggy");
 241
 242         if (!cache) cache = fetch_cache(YES);
 243         cache->list[cache->used++] = (SyncCacheItem){result, 1};
 244     }
 245
 246  really_done:
 247     return result;
 248 }
 249
 250
 251 __private_extern__ __attribute__((noinline))
 252 int objc_sync_nil(void)
 253 {
 254     return OBJC_SYNC_SUCCESS;  // something to foil the optimizer
 255 }
 256
 257
 258 // Begin synchronizing on 'obj'.
 259 // Allocates recursive pthread_mutex associated with 'obj' if needed.
 260 // Returns OBJC_SYNC_SUCCESS once lock is acquired.
 261 int objc_sync_enter(id obj)
 262 {
 263     int result = OBJC_SYNC_SUCCESS;
 264
 265     if (obj) {
 266         SyncData* data = id2data(obj, ACQUIRE);
 267         require_action_string(data != NULL, done, result = OBJC_SYNC_NOT_INITIALIZED, "id2data failed");
 268
 269         result = pthread_mutex_lock(&data->mutex);
 270         require_noerr_string(result, done, "pthread_mutex_lock failed");
 271     } else {
 272         // @synchronized(nil) does nothing
 273         if (DebugNilSync) {
 274             _objc_inform("NIL SYNC DEBUG: @synchronized(nil); set a breakpoint on objc_sync_nil to debug");
 275         }
 276         result = objc_sync_nil();
 277     }
 278
 279 done:
 280     return result;
 281 }
 282
 283
 284 // End synchronizing on 'obj'.
 285 // Returns OBJC_SYNC_SUCCESS or OBJC_SYNC_NOT_OWNING_THREAD_ERROR
 286 int objc_sync_exit(id obj)
 287 {
 288     int result = OBJC_SYNC_SUCCESS;
 289
 290     if (obj) {
 291         SyncData* data = id2data(obj, RELEASE);
 292         require_action_string(data != NULL, done, result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR, "id2data failed");
 293
 294         result = pthread_mutex_unlock(&data->mutex);
 295         require_noerr_string(result, done, "pthread_mutex_unlock failed");
 296     } else {
 297         // @synchronized(nil) does nothing
 298     }
 299
 300 done:
 301     if ( result == EPERM )
 302         result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 303
 304     return result;
 305 }
 306
 307
 308 // Temporarily release lock on 'obj' and wait for another thread to notify on 'obj'
 309 // Return OBJC_SYNC_SUCCESS, OBJC_SYNC_NOT_OWNING_THREAD_ERROR, OBJC_SYNC_TIMED_OUT, OBJC_SYNC_INTERRUPTED
 310 int objc_sync_wait(id obj, long long milliSecondsMaxWait)
 311 {
 312     int result = OBJC_SYNC_SUCCESS;
 313
 314     SyncData* data = id2data(obj, CHECK);
 315     require_action_string(data != NULL, done, result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR, "id2data failed");
 316
 317
 318     // XXX need to retry cond_wait under out-of-our-control failures
 319     if ( milliSecondsMaxWait == 0 ) {
 320         result = pthread_cond_wait(&data->conditionVariable, &data->mutex);
 321         require_noerr_string(result, done, "pthread_cond_wait failed");
 322     }
 323     else {
 324         struct timespec maxWait;
 325         maxWait.tv_sec  = (time_t)(milliSecondsMaxWait / 1000);
 326         maxWait.tv_nsec = (long)((milliSecondsMaxWait - (maxWait.tv_sec * 1000)) * 1000000);
 327         result = pthread_cond_timedwait_relative_np(&data->conditionVariable, &data->mutex, &maxWait);
 328         require_noerr_string(result, done, "pthread_cond_timedwait_relative_np failed");
 329     }
 330     // no-op to keep compiler from complaining about branch to next instruction
 331     data = NULL;
 332
 333 done:
 334     if ( result == EPERM )
 335         result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 336     else if ( result == ETIMEDOUT )
 337         result = OBJC_SYNC_TIMED_OUT;
 338
 339     return result;
 340 }
 341
 342
 343 // Wake up another thread waiting on 'obj'
 344 // Return OBJC_SYNC_SUCCESS, OBJC_SYNC_NOT_OWNING_THREAD_ERROR
 345 int objc_sync_notify(id obj)
 346 {
 347     int result = OBJC_SYNC_SUCCESS;
 348
 349     SyncData* data = id2data(obj, CHECK);
 350     require_action_string(data != NULL, done, result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR, "id2data failed");
 351
 352     result = pthread_cond_signal(&data->conditionVariable);
 353     require_noerr_string(result, done, "pthread_cond_signal failed");
 354
 355 done:
 356     if ( result == EPERM )
 357         result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 358
 359     return result;
 360 }
 361
 362
 363 // Wake up all threads waiting on 'obj'
 364 // Return OBJC_SYNC_SUCCESS, OBJC_SYNC_NOT_OWNING_THREAD_ERROR
 365 int objc_sync_notifyAll(id obj)
 366 {
 367     int result = OBJC_SYNC_SUCCESS;
 368
 369     SyncData* data = id2data(obj, CHECK);
 370     require_action_string(data != NULL, done, result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR, "id2data failed");
 371
 372     result = pthread_cond_broadcast(&data->conditionVariable);
 373     require_noerr_string(result, done, "pthread_cond_broadcast failed");
 374
 375 done:
 376     if ( result == EPERM )
 377         result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 378
 379     return result;
 380 }
 381
 382
 383
 384
 385
 386