runtime/objc-sync.mm

   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 "objc-private.h"
  25 #include "objc-sync.h"
  26
  27 //
  28 // Allocate a lock only when needed.  Since few locks are needed at any point
  29 // in time, keep them on a single list.
  30 //
  31
  32
  33 typedef struct SyncData {
  34     struct SyncData* nextData;
  35     DisguisedPtr<objc_object> object;
  36     int32_t threadCount;  // number of THREADS using this block
  37     recursive_mutex_t mutex;
  38 } SyncData;
  39
  40 typedef struct {
  41     SyncData *data;
  42     unsigned int lockCount;  // number of times THIS THREAD locked this block
  43 } SyncCacheItem;
  44
  45 typedef struct SyncCache {
  46     unsigned int allocated;
  47     unsigned int used;
  48     SyncCacheItem list[0];
  49 } SyncCache;
  50
  51 /*
  52   Fast cache: two fixed pthread keys store a single SyncCacheItem.
  53   This avoids malloc of the SyncCache for threads that only synchronize
  54   a single object at a time.
  55   SYNC_DATA_DIRECT_KEY  == SyncCacheItem.data
  56   SYNC_COUNT_DIRECT_KEY == SyncCacheItem.lockCount
  57  */
  58
  59 struct SyncList {
  60     SyncData *data;
  61     spinlock_t lock;
  62
  63     SyncList() : data(nil) { }
  64 };
  65
  66 // Use multiple parallel lists to decrease contention among unrelated objects.
  67 #define LOCK_FOR_OBJ(obj) sDataLists[obj].lock
  68 #define LIST_FOR_OBJ(obj) sDataLists[obj].data
  69 static StripedMap<SyncList> sDataLists;
  70
  71
  72 enum usage { ACQUIRE, RELEASE, CHECK };
  73
  74 static SyncCache *fetch_cache(bool create)
  75 {
  76     _objc_pthread_data *data;
  77
  78     data = _objc_fetch_pthread_data(create);
  79     if (!data) return NULL;
  80
  81     if (!data->syncCache) {
  82         if (!create) {
  83             return NULL;
  84         } else {
  85             int count = 4;
  86             data->syncCache = (SyncCache *)
  87                 calloc(1, sizeof(SyncCache) + count*sizeof(SyncCacheItem));
  88             data->syncCache->allocated = count;
  89         }
  90     }
  91
  92     // Make sure there's at least one open slot in the list.
  93     if (data->syncCache->allocated == data->syncCache->used) {
  94         data->syncCache->allocated *= 2;
  95         data->syncCache = (SyncCache *)
  96             realloc(data->syncCache, sizeof(SyncCache)
  97                     + data->syncCache->allocated * sizeof(SyncCacheItem));
  98     }
  99
 100     return data->syncCache;
 101 }
 102
 103
 104 void _destroySyncCache(struct SyncCache *cache)
 105 {
 106     if (cache) free(cache);
 107 }
 108
 109
 110 static SyncData* id2data(id object, enum usage why)
 111 {
 112     spinlock_t *lockp = &LOCK_FOR_OBJ(object);
 113     SyncData **listp = &LIST_FOR_OBJ(object);
 114     SyncData* result = NULL;
 115
 116 #if SUPPORT_DIRECT_THREAD_KEYS
 117     // Check per-thread single-entry fast cache for matching object
 118     bool fastCacheOccupied = NO;
 119     SyncData *data = (SyncData *)tls_get_direct(SYNC_DATA_DIRECT_KEY);
 120     if (data) {
 121         fastCacheOccupied = YES;
 122
 123         if (data->object == object) {
 124             // Found a match in fast cache.
 125             uintptr_t lockCount;
 126
 127             result = data;
 128             lockCount = (uintptr_t)tls_get_direct(SYNC_COUNT_DIRECT_KEY);
 129             if (result->threadCount <= 0  ||  lockCount <= 0) {
 130                 _objc_fatal("id2data fastcache is buggy");
 131             }
 132
 133             switch(why) {
 134             case ACQUIRE: {
 135                 lockCount++;
 136                 tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)lockCount);
 137                 break;
 138             }
 139             case RELEASE:
 140                 lockCount--;
 141                 tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)lockCount);
 142                 if (lockCount == 0) {
 143                     // remove from fast cache
 144                     tls_set_direct(SYNC_DATA_DIRECT_KEY, NULL);
 145                     // atomic because may collide with concurrent ACQUIRE
 146                     OSAtomicDecrement32Barrier(&result->threadCount);
 147                 }
 148                 break;
 149             case CHECK:
 150                 // do nothing
 151                 break;
 152             }
 153
 154             return result;
 155         }
 156     }
 157 #endif
 158
 159     // Check per-thread cache of already-owned locks for matching object
 160     SyncCache *cache = fetch_cache(NO);
 161     if (cache) {
 162         unsigned int i;
 163         for (i = 0; i < cache->used; i++) {
 164             SyncCacheItem *item = &cache->list[i];
 165             if (item->data->object != object) continue;
 166
 167             // Found a match.
 168             result = item->data;
 169             if (result->threadCount <= 0  ||  item->lockCount <= 0) {
 170                 _objc_fatal("id2data cache is buggy");
 171             }
 172
 173             switch(why) {
 174             case ACQUIRE:
 175                 item->lockCount++;
 176                 break;
 177             case RELEASE:
 178                 item->lockCount--;
 179                 if (item->lockCount == 0) {
 180                     // remove from per-thread cache
 181                     cache->list[i] = cache->list[--cache->used];
 182                     // atomic because may collide with concurrent ACQUIRE
 183                     OSAtomicDecrement32Barrier(&result->threadCount);
 184                 }
 185                 break;
 186             case CHECK:
 187                 // do nothing
 188                 break;
 189             }
 190
 191             return result;
 192         }
 193     }
 194
 195     // Thread cache didn't find anything.
 196     // Walk in-use list looking for matching object
 197     // Spinlock prevents multiple threads from creating multiple
 198     // locks for the same new object.
 199     // We could keep the nodes in some hash table if we find that there are
 200     // more than 20 or so distinct locks active, but we don't do that now.
 201
 202     lockp->lock();
 203
 204     {
 205         SyncData* p;
 206         SyncData* firstUnused = NULL;
 207         for (p = *listp; p != NULL; p = p->nextData) {
 208             if ( p->object == object ) {
 209                 result = p;
 210                 // atomic because may collide with concurrent RELEASE
 211                 OSAtomicIncrement32Barrier(&result->threadCount);
 212                 goto done;
 213             }
 214             if ( (firstUnused == NULL) && (p->threadCount == 0) )
 215                 firstUnused = p;
 216         }
 217
 218         // no SyncData currently associated with object
 219         if ( (why == RELEASE) || (why == CHECK) )
 220             goto done;
 221
 222         // an unused one was found, use it
 223         if ( firstUnused != NULL ) {
 224             result = firstUnused;
 225             result->object = (objc_object *)object;
 226             result->threadCount = 1;
 227             goto done;
 228         }
 229     }
 230
 231     // malloc a new SyncData and add to list.
 232     // XXX calling malloc with a global lock held is bad practice,
 233     // might be worth releasing the lock, mallocing, and searching again.
 234     // But since we never free these guys we won't be stuck in malloc very often.
 235     result = (SyncData*)calloc(sizeof(SyncData), 1);
 236     result->object = (objc_object *)object;
 237     result->threadCount = 1;
 238     new (&result->mutex) recursive_mutex_t();
 239     result->nextData = *listp;
 240     *listp = result;
 241
 242  done:
 243     lockp->unlock();
 244     if (result) {
 245         // Only new ACQUIRE should get here.
 246         // All RELEASE and CHECK and recursive ACQUIRE are
 247         // handled by the per-thread caches above.
 248         if (why == RELEASE) {
 249             // Probably some thread is incorrectly exiting
 250             // while the object is held by another thread.
 251             return nil;
 252         }
 253         if (why != ACQUIRE) _objc_fatal("id2data is buggy");
 254         if (result->object != object) _objc_fatal("id2data is buggy");
 255
 256 #if SUPPORT_DIRECT_THREAD_KEYS
 257         if (!fastCacheOccupied) {
 258             // Save in fast thread cache
 259             tls_set_direct(SYNC_DATA_DIRECT_KEY, result);
 260             tls_set_direct(SYNC_COUNT_DIRECT_KEY, (void*)1);
 261         } else
 262 #endif
 263         {
 264             // Save in thread cache
 265             if (!cache) cache = fetch_cache(YES);
 266             cache->list[cache->used].data = result;
 267             cache->list[cache->used].lockCount = 1;
 268             cache->used++;
 269         }
 270     }
 271
 272     return result;
 273 }
 274
 275
 276 BREAKPOINT_FUNCTION(
 277     void objc_sync_nil(void)
 278 );
 279
 280
 281 // Begin synchronizing on 'obj'.
 282 // Allocates recursive mutex associated with 'obj' if needed.
 283 // Returns OBJC_SYNC_SUCCESS once lock is acquired.
 284 int objc_sync_enter(id obj)
 285 {
 286     int result = OBJC_SYNC_SUCCESS;
 287
 288     if (obj) {
 289         SyncData* data = id2data(obj, ACQUIRE);
 290         assert(data);
 291         data->mutex.lock();
 292     } else {
 293         // @synchronized(nil) does nothing
 294         if (DebugNilSync) {
 295             _objc_inform("NIL SYNC DEBUG: @synchronized(nil); set a breakpoint on objc_sync_nil to debug");
 296         }
 297         objc_sync_nil();
 298     }
 299
 300     return result;
 301 }
 302
 303
 304 // End synchronizing on 'obj'.
 305 // Returns OBJC_SYNC_SUCCESS or OBJC_SYNC_NOT_OWNING_THREAD_ERROR
 306 int objc_sync_exit(id obj)
 307 {
 308     int result = OBJC_SYNC_SUCCESS;
 309
 310     if (obj) {
 311         SyncData* data = id2data(obj, RELEASE);
 312         if (!data) {
 313             result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 314         } else {
 315             bool okay = data->mutex.tryUnlock();
 316             if (!okay) {
 317                 result = OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
 318             }
 319         }
 320     } else {
 321         // @synchronized(nil) does nothing
 322     }
 323
 324
 325     return result;
 326 }
 327