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/*********************************************************************** 25* objc-initialize.m 26* +initialize support 27**********************************************************************/ 28 29/*********************************************************************** 30 * Thread-safety during class initialization (GrP 2001-9-24) 31 * 32 * Initial state: CLS_INITIALIZING and CLS_INITIALIZED both clear. 33 * During initialization: CLS_INITIALIZING is set 34 * After initialization: CLS_INITIALIZING clear and CLS_INITIALIZED set. 35 * CLS_INITIALIZING and CLS_INITIALIZED are never set at the same time. 36 * CLS_INITIALIZED is never cleared once set. 37 * 38 * Only one thread is allowed to actually initialize a class and send 39 * +initialize. Enforced by allowing only one thread to set CLS_INITIALIZING. 40 * 41 * Additionally, threads trying to send messages to a class must wait for 42 * +initialize to finish. During initialization of a class, that class's 43 * method cache is kept empty. objc_msgSend will revert to 44 * class_lookupMethodAndLoadCache, which checks CLS_INITIALIZED before 45 * messaging. If CLS_INITIALIZED is clear but CLS_INITIALIZING is set, 46 * the thread must block, unless it is the thread that started 47 * initializing the class in the first place. 48 * 49 * Each thread keeps a list of classes it's initializing. 50 * The global classInitLock is used to synchronize changes to CLS_INITIALIZED 51 * and CLS_INITIALIZING: the transition to CLS_INITIALIZING must be 52 * an atomic test-and-set with respect to itself and the transition 53 * to CLS_INITIALIZED. 54 * The global classInitWaitCond is used to block threads waiting for an 55 * initialization to complete. The classInitLock synchronizes 56 * condition checking and the condition variable. 57 **********************************************************************/ 58 59/*********************************************************************** 60 * +initialize deadlock case when a class is marked initializing while 61 * its superclass is initialized. Solved by completely initializing 62 * superclasses before beginning to initialize a class. 63 * 64 * OmniWeb class hierarchy: 65 * OBObject 66 * | ` OBPostLoader 67 * OFObject 68 * / \ 69 * OWAddressEntry OWController 70 * | 71 * OWConsoleController 72 * 73 * Thread 1 (evil testing thread): 74 * initialize OWAddressEntry 75 * super init OFObject 76 * super init OBObject 77 * [OBObject initialize] runs OBPostLoader, which inits lots of classes... 78 * initialize OWConsoleController 79 * super init OWController - wait for Thread 2 to finish OWController init 80 * 81 * Thread 2 (normal OmniWeb thread): 82 * initialize OWController 83 * super init OFObject - wait for Thread 1 to finish OFObject init 84 * 85 * deadlock! 86 * 87 * Solution: fully initialize super classes before beginning to initialize 88 * a subclass. Then the initializing+initialized part of the class hierarchy 89 * will be a contiguous subtree starting at the root, so other threads 90 * can't jump into the middle between two initializing classes, and we won't 91 * get stuck while a superclass waits for its subclass which waits for the 92 * superclass. 93 **********************************************************************/ 94 95#include "objc-private.h" 96#include "message.h" 97#include "objc-initialize.h" 98 99/* classInitLock protects CLS_INITIALIZED and CLS_INITIALIZING, and 100 * is signalled when any class is done initializing. 101 * Threads that are waiting for a class to finish initializing wait on this. */ 102static monitor_t classInitLock = MONITOR_INITIALIZER; 103 104 105/*********************************************************************** 106* struct _objc_initializing_classes 107* Per-thread list of classes currently being initialized by that thread. 108* During initialization, that thread is allowed to send messages to that 109* class, but other threads have to wait. 110* The list is a simple array of metaclasses (the metaclass stores 111* the initialization state). 112**********************************************************************/ 113typedef struct _objc_initializing_classes { 114 int classesAllocated; 115 Class *metaclasses; 116} _objc_initializing_classes; 117 118 119/*********************************************************************** 120* _fetchInitializingClassList 121* Return the list of classes being initialized by this thread. 122* If create == YES, create the list when no classes are being initialized by this thread. 123* If create == NO, return nil when no classes are being initialized by this thread. 124**********************************************************************/ 125static _objc_initializing_classes *_fetchInitializingClassList(BOOL create) 126{ 127 _objc_pthread_data *data; 128 _objc_initializing_classes *list; 129 Class *classes; 130 131 data = _objc_fetch_pthread_data(create); 132 if (data == nil) return nil; 133 134 list = data->initializingClasses; 135 if (list == nil) { 136 if (!create) { 137 return nil; 138 } else { 139 list = (_objc_initializing_classes *) 140 _calloc_internal(1, sizeof(_objc_initializing_classes)); 141 data->initializingClasses = list; 142 } 143 } 144 145 classes = list->metaclasses; 146 if (classes == nil) { 147 // If _objc_initializing_classes exists, allocate metaclass array, 148 // even if create == NO. 149 // Allow 4 simultaneous class inits on this thread before realloc. 150 list->classesAllocated = 4; 151 classes = (Class *) 152 _calloc_internal(list->classesAllocated, sizeof(Class)); 153 list->metaclasses = classes; 154 } 155 return list; 156} 157 158 159/*********************************************************************** 160* _destroyInitializingClassList 161* Deallocate memory used by the given initialization list. 162* Any part of the list may be nil. 163* Called from _objc_pthread_destroyspecific(). 164**********************************************************************/ 165 166void _destroyInitializingClassList(struct _objc_initializing_classes *list) 167{ 168 if (list != nil) { 169 if (list->metaclasses != nil) { 170 _free_internal(list->metaclasses); 171 } 172 _free_internal(list); 173 } 174} 175 176 177/*********************************************************************** 178* _thisThreadIsInitializingClass 179* Return TRUE if this thread is currently initializing the given class. 180**********************************************************************/ 181static BOOL _thisThreadIsInitializingClass(Class cls) 182{ 183 int i; 184 185 _objc_initializing_classes *list = _fetchInitializingClassList(NO); 186 if (list) { 187 cls = cls->getMeta(); 188 for (i = 0; i < list->classesAllocated; i++) { 189 if (cls == list->metaclasses[i]) return YES; 190 } 191 } 192 193 // no list or not found in list 194 return NO; 195} 196 197 198/*********************************************************************** 199* _setThisThreadIsInitializingClass 200* Record that this thread is currently initializing the given class. 201* This thread will be allowed to send messages to the class, but 202* other threads will have to wait. 203**********************************************************************/ 204static void _setThisThreadIsInitializingClass(Class cls) 205{ 206 int i; 207 _objc_initializing_classes *list = _fetchInitializingClassList(YES); 208 cls = cls->getMeta(); 209 210 // paranoia: explicitly disallow duplicates 211 for (i = 0; i < list->classesAllocated; i++) { 212 if (cls == list->metaclasses[i]) { 213 _objc_fatal("thread is already initializing this class!"); 214 return; // already the initializer 215 } 216 } 217 218 for (i = 0; i < list->classesAllocated; i++) { 219 if (! list->metaclasses[i]) { 220 list->metaclasses[i] = cls; 221 return; 222 } 223 } 224 225 // class list is full - reallocate 226 list->classesAllocated = list->classesAllocated * 2 + 1; 227 list->metaclasses = (Class *) 228 _realloc_internal(list->metaclasses, 229 list->classesAllocated * sizeof(Class)); 230 // zero out the new entries 231 list->metaclasses[i++] = cls; 232 for ( ; i < list->classesAllocated; i++) { 233 list->metaclasses[i] = nil; 234 } 235} 236 237 238/*********************************************************************** 239* _setThisThreadIsNotInitializingClass 240* Record that this thread is no longer initializing the given class. 241**********************************************************************/ 242static void _setThisThreadIsNotInitializingClass(Class cls) 243{ 244 int i; 245 246 _objc_initializing_classes *list = _fetchInitializingClassList(NO); 247 if (list) { 248 cls = cls->getMeta(); 249 for (i = 0; i < list->classesAllocated; i++) { 250 if (cls == list->metaclasses[i]) { 251 list->metaclasses[i] = nil; 252 return; 253 } 254 } 255 } 256 257 // no list or not found in list 258 _objc_fatal("thread is not initializing this class!"); 259} 260 261 262typedef struct PendingInitialize { 263 Class subclass; 264 struct PendingInitialize *next; 265} PendingInitialize; 266 267static NXMapTable *pendingInitializeMap; 268 269/*********************************************************************** 270* _finishInitializing 271* cls has completed its +initialize method, and so has its superclass. 272* Mark cls as initialized as well, then mark any of cls's subclasses 273* that have already finished their own +initialize methods. 274**********************************************************************/ 275static void _finishInitializing(Class cls, Class supercls) 276{ 277 PendingInitialize *pending; 278 279 monitor_assert_locked(&classInitLock); 280 assert(!supercls || supercls->isInitialized()); 281 282 if (PrintInitializing) { 283 _objc_inform("INITIALIZE: %s is fully +initialized", 284 cls->nameForLogging()); 285 } 286 287 // propagate finalization affinity. 288 if (UseGC && supercls && supercls->shouldFinalizeOnMainThread()) { 289 cls->setShouldFinalizeOnMainThread(); 290 } 291 292 // mark this class as fully +initialized 293 cls->setInitialized(); 294 monitor_notifyAll(&classInitLock); 295 _setThisThreadIsNotInitializingClass(cls); 296 297 // mark any subclasses that were merely waiting for this class 298 if (!pendingInitializeMap) return; 299 pending = (PendingInitialize *)NXMapGet(pendingInitializeMap, cls); 300 if (!pending) return; 301 302 NXMapRemove(pendingInitializeMap, cls); 303 304 // Destroy the pending table if it's now empty, to save memory. 305 if (NXCountMapTable(pendingInitializeMap) == 0) { 306 NXFreeMapTable(pendingInitializeMap); 307 pendingInitializeMap = nil; 308 } 309 310 while (pending) { 311 PendingInitialize *next = pending->next; 312 if (pending->subclass) _finishInitializing(pending->subclass, cls); 313 _free_internal(pending); 314 pending = next; 315 } 316} 317 318 319/*********************************************************************** 320* _finishInitializingAfter 321* cls has completed its +initialize method, but its superclass has not. 322* Wait until supercls finishes before marking cls as initialized. 323**********************************************************************/ 324static void _finishInitializingAfter(Class cls, Class supercls) 325{ 326 PendingInitialize *pending; 327 328 monitor_assert_locked(&classInitLock); 329 330 if (PrintInitializing) { 331 _objc_inform("INITIALIZE: %s waiting for superclass +[%s initialize]", 332 cls->nameForLogging(), supercls->nameForLogging()); 333 } 334 335 if (!pendingInitializeMap) { 336 pendingInitializeMap = 337 NXCreateMapTableFromZone(NXPtrValueMapPrototype, 338 10, _objc_internal_zone()); 339 // fixme pre-size this table for CF/NSObject +initialize 340 } 341 342 pending = (PendingInitialize *)_malloc_internal(sizeof(*pending)); 343 pending->subclass = cls; 344 pending->next = (PendingInitialize *) 345 NXMapGet(pendingInitializeMap, supercls); 346 NXMapInsert(pendingInitializeMap, supercls, pending); 347} 348 349 350/*********************************************************************** 351* class_initialize. Send the '+initialize' message on demand to any 352* uninitialized class. Force initialization of superclasses first. 353* 354* Called only from _class_lookupMethodAndLoadCache (or itself). 355**********************************************************************/ 356void _class_initialize(Class cls) 357{ 358 assert(!cls->isMetaClass()); 359 360 Class supercls; 361 BOOL reallyInitialize = NO; 362 363 // Make sure super is done initializing BEFORE beginning to initialize cls. 364 // See note about deadlock above. 365 supercls = cls->superclass; 366 if (supercls && !supercls->isInitialized()) { 367 _class_initialize(supercls); 368 } 369 370 // Try to atomically set CLS_INITIALIZING. 371 monitor_enter(&classInitLock); 372 if (!cls->isInitialized() && !cls->isInitializing()) { 373 cls->setInitializing(); 374 reallyInitialize = YES; 375 } 376 monitor_exit(&classInitLock); 377 378 if (reallyInitialize) { 379 // We successfully set the CLS_INITIALIZING bit. Initialize the class. 380 381 // Record that we're initializing this class so we can message it. 382 _setThisThreadIsInitializingClass(cls); 383 384 // Send the +initialize message. 385 // Note that +initialize is sent to the superclass (again) if 386 // this class doesn't implement +initialize. 2157218 387 if (PrintInitializing) { 388 _objc_inform("INITIALIZE: calling +[%s initialize]", 389 cls->nameForLogging()); 390 } 391 392 ((void(*)(Class, SEL))objc_msgSend)(cls, SEL_initialize); 393 394 if (PrintInitializing) { 395 _objc_inform("INITIALIZE: finished +[%s initialize]", 396 cls->nameForLogging()); 397 } 398 399 // Done initializing. 400 // If the superclass is also done initializing, then update 401 // the info bits and notify waiting threads. 402 // If not, update them later. (This can happen if this +initialize 403 // was itself triggered from inside a superclass +initialize.) 404 405 monitor_enter(&classInitLock); 406 if (!supercls || supercls->isInitialized()) { 407 _finishInitializing(cls, supercls); 408 } else { 409 _finishInitializingAfter(cls, supercls); 410 } 411 monitor_exit(&classInitLock); 412 return; 413 } 414 415 else if (cls->isInitializing()) { 416 // We couldn't set INITIALIZING because INITIALIZING was already set. 417 // If this thread set it earlier, continue normally. 418 // If some other thread set it, block until initialize is done. 419 // It's ok if INITIALIZING changes to INITIALIZED while we're here, 420 // because we safely check for INITIALIZED inside the lock 421 // before blocking. 422 if (_thisThreadIsInitializingClass(cls)) { 423 return; 424 } else { 425 monitor_enter(&classInitLock); 426 while (!cls->isInitialized()) { 427 monitor_wait(&classInitLock); 428 } 429 monitor_exit(&classInitLock); 430 return; 431 } 432 } 433 434 else if (cls->isInitialized()) { 435 // Set CLS_INITIALIZING failed because someone else already 436 // initialized the class. Continue normally. 437 // NOTE this check must come AFTER the ISINITIALIZING case. 438 // Otherwise: Another thread is initializing this class. ISINITIALIZED 439 // is false. Skip this clause. Then the other thread finishes 440 // initialization and sets INITIALIZING=no and INITIALIZED=yes. 441 // Skip the ISINITIALIZING clause. Die horribly. 442 return; 443 } 444 445 else { 446 // We shouldn't be here. 447 _objc_fatal("thread-safe class init in objc runtime is buggy!"); 448 } 449} 450