/* * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in * compliance with the License. Please obtain a copy of the License at * http://www.opensource.apple.com/apsl/ and read it before using this * file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. * Please see the License for the specific language governing rights and * limitations under the License. * * @APPLE_LICENSE_HEADER_END@ */ /*********************************************************************** * objc-class.m * Copyright 1988-1997, Apple Computer, Inc. * Author: s. naroff **********************************************************************/ /*********************************************************************** * Method cache locking (GrP 2001-1-14) * * For speed, objc_msgSend does not acquire any locks when it reads * method caches. Instead, all cache changes are performed so that any * objc_msgSend running concurrently with the cache mutator will not * crash or hang or get an incorrect result from the cache. * * When cache memory becomes unused (e.g. the old cache after cache * expansion), it is not immediately freed, because a concurrent * objc_msgSend could still be using it. Instead, the memory is * disconnected from the data structures and placed on a garbage list. * The memory is now only accessible to instances of objc_msgSend that * were running when the memory was disconnected; any further calls to * objc_msgSend will not see the garbage memory because the other data * structures don't point to it anymore. The collecting_in_critical * function checks the PC of all threads and returns FALSE when all threads * are found to be outside objc_msgSend. This means any call to objc_msgSend * that could have had access to the garbage has finished or moved past the * cache lookup stage, so it is safe to free the memory. * * All functions that modify cache data or structures must acquire the * cacheUpdateLock to prevent interference from concurrent modifications. * The function that frees cache garbage must acquire the cacheUpdateLock * and use collecting_in_critical() to flush out cache readers. * The cacheUpdateLock is also used to protect the custom allocator used * for large method cache blocks. * * Cache readers (PC-checked by collecting_in_critical()) * objc_msgSend* * _cache_getImp * _cache_getMethod * * Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked) * _cache_fill (acquires lock) * _cache_expand (only called from cache_fill) * _cache_create (only called from cache_expand) * bcopy (only called from instrumented cache_expand) * flush_caches (acquires lock) * _cache_flush (only called from cache_fill and flush_caches) * _cache_collect_free (only called from cache_expand and cache_flush) * * UNPROTECTED cache readers (NOT thread-safe; used for debug info only) * _cache_print * _class_printMethodCaches * _class_printDuplicateCacheEntries * _class_printMethodCacheStatistics * * _class_lookupMethodAndLoadCache is a special case. It may read a * method triplet out of one cache and store it in another cache. This * is unsafe if the method triplet is a forward:: entry, because the * triplet itself could be freed unless _class_lookupMethodAndLoadCache * were PC-checked or used a lock. Additionally, storing the method * triplet in both caches would result in double-freeing if both caches * were flushed or expanded. The solution is for _cache_getMethod to * ignore all entries whose implementation is _objc_msgForward, so * _class_lookupMethodAndLoadCache cannot look at a forward:: entry * unsafely or place it in multiple caches. ***********************************************************************/ /*********************************************************************** * Lazy method list arrays and method list locking (2004-10-19) * * cls->methodLists may be in one of three forms: * 1. NULL: The class has no methods. * 2. non-NULL, with CLS_NO_METHOD_ARRAY set: cls->methodLists points * to a single method list, which is the class's only method list. * 3. non-NULL, with CLS_NO_METHOD_ARRAY clear: cls->methodLists points to * an array of method list pointers. The end of the array's block * is set to -1. If the actual number of method lists is smaller * than that, the rest of the array is NULL. * * Attaching categories and adding and removing classes may change * the form of the class list. In addition, individual method lists * may be reallocated when fixed up. * * Classes are initially read as #1 or #2. If a category is attached * or other methods added, the class is changed to #3. Once in form #3, * the class is never downgraded to #1 or #2, even if methods are removed. * Classes added with objc_addClass are initially either #1 or #3. * * Accessing and manipulating a class's method lists are synchronized, * to prevent races when one thread restructures the list. However, * if the class is not yet in use (i.e. not in class_hash), then the * thread loading the class may access its method lists without locking. * * The following functions acquire methodListLock: * class_getInstanceMethod * class_getClassMethod * class_nextMethodList * class_addMethods * class_removeMethods * class_respondsToMethod * _class_lookupMethodAndLoadCache * lookupMethodInClassAndLoadCache * _objc_add_category_flush_caches * * The following functions don't acquire methodListLock because they * only access method lists during class load and unload: * _objc_register_category * _resolve_categories_for_class (calls _objc_add_category) * add_class_to_loadable_list * _objc_addClass * _objc_remove_classes_in_image * * The following functions use method lists without holding methodListLock. * The caller must either hold methodListLock, or be loading the class. * _getMethod (called by class_getInstanceMethod, class_getClassMethod, * and class_respondsToMethod) * _findMethodInClass (called by _class_lookupMethodAndLoadCache, * lookupMethodInClassAndLoadCache, _getMethod) * _findMethodInList (called by _findMethodInClass) * nextMethodList (called by _findMethodInClass and class_nextMethodList * fixupSelectorsInMethodList (called by nextMethodList) * _objc_add_category (called by _objc_add_category_flush_caches, * resolve_categories_for_class and _objc_register_category) * _objc_insertMethods (called by class_addMethods and _objc_add_category) * _objc_removeMethods (called by class_removeMethods) * _objcTweakMethodListPointerForClass (called by _objc_insertMethods) * get_base_method_list (called by add_class_to_loadable_list) * lookupNamedMethodInMethodList (called by add_class_to_loadable_list) ***********************************************************************/ /*********************************************************************** * Thread-safety of class info bits (2004-10-19) * * Some class info bits are used to store mutable runtime state. * Modifications of the info bits at particular times need to be * synchronized to prevent races. * * Three thread-safe modification functions are provided: * _class_setInfo() // atomically sets some bits * _class_clearInfo() // atomically clears some bits * _class_changeInfo() // atomically sets some bits and clears others * These replace CLS_SETINFO() for the multithreaded cases. * * Three modification windows are defined: * - compile time * - class construction or image load (before +load) in one thread * - multi-threaded messaging and method caches * * Info bit modification at compile time and class construction do not * need to be locked, because only one thread is manipulating the class. * Info bit modification during messaging needs to be locked, because * there may be other threads simultaneously messaging or otherwise * manipulating the class. * * Modification windows for each flag: * * CLS_CLASS: compile-time and class load * CLS_META: compile-time and class load * CLS_INITIALIZED: +initialize * CLS_POSING: messaging * CLS_MAPPED: compile-time * CLS_FLUSH_CACHE: messaging * CLS_GROW_CACHE: messaging * CLS_NEED_BIND: unused * CLS_METHOD_ARRAY: unused * CLS_JAVA_HYBRID: JavaBridge only * CLS_JAVA_CLASS: JavaBridge only * CLS_INITIALIZING: messaging * CLS_FROM_BUNDLE: class load * CLS_HAS_CXX_STRUCTORS: compile-time and class load * CLS_NO_METHOD_ARRAY: class load and messaging * CLS_HAS_LOAD_METHOD: class load * * CLS_INITIALIZED and CLS_INITIALIZING have additional thread-safety * constraints to support thread-safe +initialize. See "Thread safety * during class initialization" for details. * * CLS_JAVA_HYBRID and CLS_JAVA_CLASS are set immediately after JavaBridge * calls objc_addClass(). The JavaBridge does not use an atomic update, * but the modification counts as "class construction" unless some other * thread quickly finds the class via the class list. This race is * small and unlikely in well-behaved code. * * Most info bits that may be modified during messaging are also never * read without a lock. There is no general read lock for the info bits. * CLS_INITIALIZED: classInitLock * CLS_FLUSH_CACHE: cacheUpdateLock * CLS_GROW_CACHE: cacheUpdateLock * CLS_NO_METHOD_ARRAY: methodListLock * CLS_INITIALIZING: classInitLock ***********************************************************************/ /*********************************************************************** * Thread-safety during class initialization (GrP 2001-9-24) * * Initial state: CLS_INITIALIZING and CLS_INITIALIZED both clear. * During initialization: CLS_INITIALIZING is set * After initialization: CLS_INITIALIZING clear and CLS_INITIALIZED set. * CLS_INITIALIZING and CLS_INITIALIZED are never set at the same time. * CLS_INITIALIZED is never cleared once set. * * Only one thread is allowed to actually initialize a class and send * +initialize. Enforced by allowing only one thread to set CLS_INITIALIZING. * * Additionally, threads trying to send messages to a class must wait for * +initialize to finish. During initialization of a class, that class's * method cache is kept empty. objc_msgSend will revert to * class_lookupMethodAndLoadCache, which checks CLS_INITIALIZED before * messaging. If CLS_INITIALIZED is clear but CLS_INITIALIZING is set, * the thread must block, unless it is the thread that started * initializing the class in the first place. * * Each thread keeps a list of classes it's initializing. * The global classInitLock is used to synchronize changes to CLS_INITIALIZED * and CLS_INITIALIZING: the transition to CLS_INITIALIZING must be * an atomic test-and-set with respect to itself and the transition * to CLS_INITIALIZED. * The global classInitWaitCond is used to block threads waiting for an * initialization to complete. The classInitLock synchronizes * condition checking and the condition variable. **********************************************************************/ /*********************************************************************** * +initialize deadlock case when a class is marked initializing while * its superclass is initialized. Solved by completely initializing * superclasses before beginning to initialize a class. * * OmniWeb class hierarchy: * OBObject * | ` OBPostLoader * OFObject * / \ * OWAddressEntry OWController * | * OWConsoleController * * Thread 1 (evil testing thread): * initialize OWAddressEntry * super init OFObject * super init OBObject * [OBObject initialize] runs OBPostLoader, which inits lots of classes... * initialize OWConsoleController * super init OWController - wait for Thread 2 to finish OWController init * * Thread 2 (normal OmniWeb thread): * initialize OWController * super init OFObject - wait for Thread 1 to finish OFObject init * * deadlock! * * Solution: fully initialize super classes before beginning to initialize * a subclass. Then the initializing+initialized part of the class hierarchy * will be a contiguous subtree starting at the root, so other threads * can't jump into the middle between two initializing classes, and we won't * get stuck while a superclass waits for its subclass which waits for the * superclass. **********************************************************************/ /*********************************************************************** * Imports. **********************************************************************/ #import #include #include #include #include #include #include #include #import "objc-class.h" #import #import #import "objc-private.h" #import "hashtable2.h" #import "maptable.h" #include // Needed functions not in any header file size_t malloc_size (const void * ptr); // Needed kernel interface #import #import /*********************************************************************** * Conditionals. **********************************************************************/ // Define PRELOAD_SUPERCLASS_CACHES to cause method lookups to add the // method the appropriate superclass caches, in addition to the normal // encaching in the subclass where the method was messaged. Doing so // will speed up messaging the same method from instances of the // superclasses, but also uses up valuable cache space for a speculative // purpose // See radar 2364264 about incorrectly propogating _objc_forward entries // and double freeing them, first, before turning this on! // (Radar 2364264 is now "inactive".) // Double-freeing is also a potential problem when this is off. See // note about _class_lookupMethodAndLoadCache in "Method cache locking". //#define PRELOAD_SUPERCLASS_CACHES /*********************************************************************** * Exports. **********************************************************************/ #ifdef OBJC_INSTRUMENTED enum { CACHE_HISTOGRAM_SIZE = 512 }; unsigned int CacheHitHistogram [CACHE_HISTOGRAM_SIZE]; unsigned int CacheMissHistogram [CACHE_HISTOGRAM_SIZE]; #endif /*********************************************************************** * Constants and macros internal to this module. **********************************************************************/ // INIT_CACHE_SIZE and INIT_META_CACHE_SIZE must be a power of two enum { INIT_CACHE_SIZE_LOG2 = 2, INIT_META_CACHE_SIZE_LOG2 = 2, INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2), INIT_META_CACHE_SIZE = (1 << INIT_META_CACHE_SIZE_LOG2) }; // Amount of space required for count hash table buckets, knowing that // one entry is embedded in the cache structure itself #define TABLE_SIZE(count) ((count - 1) * sizeof(Method)) // A sentinal (magic value) to report bad thread_get_state status #define PC_SENTINAL 0 /*********************************************************************** * Types internal to this module. **********************************************************************/ #ifdef OBJC_INSTRUMENTED struct CacheInstrumentation { unsigned int hitCount; // cache lookup success tally unsigned int hitProbes; // sum entries checked to hit unsigned int maxHitProbes; // max entries checked to hit unsigned int missCount; // cache lookup no-find tally unsigned int missProbes; // sum entries checked to miss unsigned int maxMissProbes; // max entries checked to miss unsigned int flushCount; // cache flush tally unsigned int flushedEntries; // sum cache entries flushed unsigned int maxFlushedEntries; // max cache entries flushed }; typedef struct CacheInstrumentation CacheInstrumentation; // Cache instrumentation data follows table, so it is most compatible #define CACHE_INSTRUMENTATION(cache) (CacheInstrumentation *) &cache->buckets[cache->mask + 1]; #endif /*********************************************************************** * Function prototypes internal to this module. **********************************************************************/ static Ivar class_getVariable (Class cls, const char * name); static void flush_caches (Class cls, BOOL flush_meta); static struct objc_method_list *nextMethodList(struct objc_class *cls, void **it); static void addClassToOriginalClass (Class posingClass, Class originalClass); static void _objc_addOrigClass (Class origClass); static void _freedHandler (id self, SEL sel); static void _nonexistentHandler (id self, SEL sel); static void class_initialize (Class cls); static Cache _cache_expand (Class cls); static int LogObjCMessageSend (BOOL isClassMethod, const char * objectsClass, const char * implementingClass, SEL selector); static BOOL _cache_fill (Class cls, Method smt, SEL sel); static void _cache_addForwardEntry(Class cls, SEL sel); static void _cache_flush (Class cls); static IMP lookupMethodInClassAndLoadCache(Class cls, SEL sel); static int SubtypeUntil (const char * type, char end); static const char * SkipFirstType (const char * type); static unsigned long _get_pc_for_thread (mach_port_t thread); static int _collecting_in_critical (void); static void _garbage_make_room (void); static void _cache_collect_free (void * data, size_t size, BOOL tryCollect); static BOOL cache_allocator_is_block(void *block); static void *cache_allocator_calloc(size_t size); static void cache_allocator_free(void *block); static void _cache_print (Cache cache); static unsigned int log2 (unsigned int x); static void PrintCacheHeader (void); #ifdef OBJC_INSTRUMENTED static void PrintCacheHistogram (char * title, unsigned int * firstEntry, unsigned int entryCount); #endif /*********************************************************************** * Static data internal to this module. **********************************************************************/ // When _class_uncache is non-zero, cache growth copies the existing // entries into the new (larger) cache. When this flag is zero, new // (larger) caches start out empty. static int _class_uncache = 1; // When _class_slow_grow is non-zero, any given cache is actually grown // only on the odd-numbered times it becomes full; on the even-numbered // times, it is simply emptied and re-used. When this flag is zero, // caches are grown every time. static int _class_slow_grow = 1; // Lock for cache access. // Held when modifying a cache in place. // Held when installing a new cache on a class. // Held when adding to the cache garbage list. // Held when disposing cache garbage. // See "Method cache locking" above for notes about cache locking. static OBJC_DECLARE_LOCK(cacheUpdateLock); // classInitLock protects classInitWaitCond and examination and modification // of CLS_INITIALIZED and CLS_INITIALIZING. OBJC_DECLARE_LOCK(classInitLock); // classInitWaitCond is signalled when any class is done initializing. // Threads that are waiting for a class to finish initializing wait on this. pthread_cond_t classInitWaitCond = PTHREAD_COND_INITIALIZER; // Lock for method list access and modification. // Protects methodLists fields, method arrays, and CLS_NO_METHOD_ARRAY bits. // Classes not yet in use do not need to take this lock. OBJC_DECLARE_LOCK(methodListLock); // When traceDuplicates is non-zero, _cacheFill checks whether the method // being encached is already there. The number of times it finds a match // is tallied in cacheFillDuplicates. When traceDuplicatesVerbose is // non-zero, each duplication is logged when found in this way. static int traceDuplicates = 0; static int traceDuplicatesVerbose = 0; static int cacheFillDuplicates = 0; // Custom cache allocator parameters // CACHE_REGION_SIZE must be a multiple of CACHE_QUANTUM. #define CACHE_QUANTUM 520 #define CACHE_REGION_SIZE 131040 // quantized just under 128KB (131072) // #define CACHE_REGION_SIZE 262080 // quantized just under 256KB (262144) #ifdef OBJC_INSTRUMENTED // Instrumentation static unsigned int LinearFlushCachesCount = 0; static unsigned int LinearFlushCachesVisitedCount = 0; static unsigned int MaxLinearFlushCachesVisitedCount = 0; static unsigned int NonlinearFlushCachesCount = 0; static unsigned int NonlinearFlushCachesClassCount = 0; static unsigned int NonlinearFlushCachesVisitedCount = 0; static unsigned int MaxNonlinearFlushCachesVisitedCount = 0; static unsigned int IdealFlushCachesCount = 0; static unsigned int MaxIdealFlushCachesCount = 0; #endif // Method call logging typedef int (*ObjCLogProc)(BOOL, const char *, const char *, SEL); static int totalCacheFills NOBSS = 0; static int objcMsgLogFD = (-1); static ObjCLogProc objcMsgLogProc = &LogObjCMessageSend; static int objcMsgLogEnabled = 0; // Error Messages static const char _errNoMem[] = "failed -- out of memory(%s, %u)", _errAllocNil[] = "allocating nil object", _errFreedObject[] = "message %s sent to freed object=0x%lx", _errNonExistentObject[] = "message %s sent to non-existent object=0x%lx", _errBadSel[] = "invalid selector %s", _errNotSuper[] = "[%s poseAs:%s]: target not immediate superclass", _errNewVars[] = "[%s poseAs:%s]: %s defines new instance variables"; /*********************************************************************** * Information about multi-thread support: * * Since we do not lock many operations which walk the superclass, method * and ivar chains, these chains must remain intact once a class is published * by inserting it into the class hashtable. All modifications must be * atomic so that someone walking these chains will always geta valid * result. ***********************************************************************/ /*********************************************************************** * A static empty cache. All classes initially point at this cache. * When the first message is sent it misses in the cache, and when * the cache is grown it checks for this case and uses malloc rather * than realloc. This avoids the need to check for NULL caches in the * messenger. ***********************************************************************/ #ifndef OBJC_INSTRUMENTED const struct objc_cache emptyCache = { 0, // mask 0, // occupied { NULL } // buckets }; #else // OBJC_INSTRUMENTED requires writable data immediately following emptyCache. struct objc_cache emptyCache = { 0, // mask 0, // occupied { NULL } // buckets }; CacheInstrumentation emptyCacheInstrumentation = {0}; #endif // Freed objects have their isa set to point to this dummy class. // This avoids the need to check for Nil classes in the messenger. static const struct objc_class freedObjectClass = { Nil, // isa Nil, // super_class "FREED(id)", // name 0, // version 0, // info 0, // instance_size NULL, // ivars NULL, // methodLists (Cache) &emptyCache, // cache NULL // protocols }; static const struct objc_class nonexistentObjectClass = { Nil, // isa Nil, // super_class "NONEXISTENT(id)", // name 0, // version 0, // info 0, // instance_size NULL, // ivars NULL, // methodLists (Cache) &emptyCache, // cache NULL // protocols }; /*********************************************************************** * object_getClassName. **********************************************************************/ const char * object_getClassName (id obj) { // Even nil objects have a class name, sort of if (obj == nil) return "nil"; // Retrieve name from object's class return ((struct objc_class *) obj->isa)->name; } /*********************************************************************** * object_getIndexedIvars. **********************************************************************/ void * object_getIndexedIvars (id obj) { // ivars are tacked onto the end of the object return ((char *) obj) + ((struct objc_class *) obj->isa)->instance_size; } /*********************************************************************** * object_cxxDestructFromClass. * Call C++ destructors on obj, starting with cls's * dtor method (if any) followed by superclasses' dtors (if any), * stopping at cls's dtor (if any). * Uses methodListLock and cacheUpdateLock. The caller must hold neither. **********************************************************************/ static void object_cxxDestructFromClass(id obj, Class cls) { void (*dtor)(id); // Call cls's dtor first, then superclasses's dtors. for ( ; cls != NULL; cls = cls->super_class) { if (!(cls->info & CLS_HAS_CXX_STRUCTORS)) continue; dtor = (void(*)(id)) lookupMethodInClassAndLoadCache(cls, cxx_destruct_sel); if (dtor != (void(*)(id))&_objc_msgForward) { if (PrintCxxCtors) { _objc_inform("CXX: calling C++ destructors for class %s", cls->name); } (*dtor)(obj); } } } /*********************************************************************** * object_cxxDestruct. * Call C++ destructors on obj, if any. * Uses methodListLock and cacheUpdateLock. The caller must hold neither. **********************************************************************/ void object_cxxDestruct(id obj) { if (!obj) return; object_cxxDestructFromClass(obj, obj->isa); } /*********************************************************************** * object_cxxConstructFromClass. * Recursively call C++ constructors on obj, starting with base class's * ctor method (if any) followed by subclasses' ctors (if any), stopping * at cls's ctor (if any). * Returns YES if construction succeeded. * Returns NO if some constructor threw an exception. The exception is * caught and discarded. Any partial construction is destructed. * Uses methodListLock and cacheUpdateLock. The caller must hold neither. * * .cxx_construct returns id. This really means: * return self: construction succeeded * return nil: construction failed because a C++ constructor threw an exception **********************************************************************/ static BOOL object_cxxConstructFromClass(id obj, Class cls) { id (*ctor)(id); // Call superclasses' ctors first, if any. if (cls->super_class) { BOOL ok = object_cxxConstructFromClass(obj, cls->super_class); if (!ok) return NO; // some superclass's ctor failed - give up } // Find this class's ctor, if any. if (!(cls->info & CLS_HAS_CXX_STRUCTORS)) return YES; // no ctor - ok ctor = (id(*)(id))lookupMethodInClassAndLoadCache(cls, cxx_construct_sel); if (ctor == (id(*)(id))&_objc_msgForward) return YES; // no ctor - ok // Call this class's ctor. if (PrintCxxCtors) { _objc_inform("CXX: calling C++ constructors for class %s", cls->name); } if ((*ctor)(obj)) return YES; // ctor called and succeeded - ok // This class's ctor was called and failed. // Call superclasses's dtors to clean up. if (cls->super_class) object_cxxDestructFromClass(obj, cls->super_class); return NO; } /*********************************************************************** * object_cxxConstructFromClass. * Call C++ constructors on obj, if any. * Returns YES if construction succeeded. * Returns NO if some constructor threw an exception. The exception is * caught and discarded. Any partial construction is destructed. * Uses methodListLock and cacheUpdateLock. The caller must hold neither. **********************************************************************/ BOOL object_cxxConstruct(id obj) { if (!obj) return YES; return object_cxxConstructFromClass(obj, obj->isa); } /*********************************************************************** * _internal_class_createInstanceFromZone. Allocate an instance of the * specified class with the specified number of bytes for indexed * variables, in the specified zone. The isa field is set to the * class, C++ default constructors are called, and all other fields are zeroed. **********************************************************************/ static id _internal_class_createInstanceFromZone (Class aClass, unsigned nIvarBytes, void * z) { id obj; register unsigned byteCount; // Can't create something for nothing if (aClass == Nil) { __objc_error ((id) aClass, _errAllocNil, 0); return nil; } // Allocate and initialize byteCount = ((struct objc_class *) aClass)->instance_size + nIvarBytes; obj = (id) malloc_zone_calloc (z, 1, byteCount); if (!obj) { __objc_error ((id) aClass, _errNoMem, ((struct objc_class *) aClass)->name, nIvarBytes); return nil; } // Set the isa pointer obj->isa = aClass; // Call C++ constructors, if any. if (!object_cxxConstruct(obj)) { // Some C++ constructor threw an exception. malloc_zone_free(z, obj); return nil; } return obj; } /*********************************************************************** * _internal_class_createInstance. Allocate an instance of the specified * class with the specified number of bytes for indexed variables, in * the default zone, using _internal_class_createInstanceFromZone. **********************************************************************/ static id _internal_class_createInstance (Class aClass, unsigned nIvarBytes) { return _internal_class_createInstanceFromZone (aClass, nIvarBytes, malloc_default_zone ()); } id (*_poseAs)() = (id (*)())class_poseAs; id (*_alloc)(Class, unsigned) = _internal_class_createInstance; id (*_zoneAlloc)(Class, unsigned, void *) = _internal_class_createInstanceFromZone; /*********************************************************************** * class_createInstanceFromZone. Allocate an instance of the specified * class with the specified number of bytes for indexed variables, in * the specified zone, using _zoneAlloc. **********************************************************************/ id class_createInstanceFromZone (Class aClass, unsigned nIvarBytes, void * z) { // _zoneAlloc can be overridden, but is initially set to // _internal_class_createInstanceFromZone return (*_zoneAlloc) (aClass, nIvarBytes, z); } /*********************************************************************** * class_createInstance. Allocate an instance of the specified class with * the specified number of bytes for indexed variables, using _alloc. **********************************************************************/ id class_createInstance (Class aClass, unsigned nIvarBytes) { // _alloc can be overridden, but is initially set to // _internal_class_createInstance return (*_alloc) (aClass, nIvarBytes); } /*********************************************************************** * class_setVersion. Record the specified version with the class. **********************************************************************/ void class_setVersion (Class aClass, int version) { ((struct objc_class *) aClass)->version = version; } /*********************************************************************** * class_getVersion. Return the version recorded with the class. **********************************************************************/ int class_getVersion (Class aClass) { return ((struct objc_class *) aClass)->version; } static inline Method _findNamedMethodInList(struct objc_method_list * mlist, const char *meth_name) { int i; if (!mlist) return NULL; for (i = 0; i < mlist->method_count; i++) { Method m = &mlist->method_list[i]; if (*((const char *)m->method_name) == *meth_name && 0 == strcmp((const char *)(m->method_name), meth_name)) { return m; } } return NULL; } /*********************************************************************** * fixupSelectorsInMethodList * Uniques selectors in the given method list. * The given method list must be non-NULL and not already fixed-up. * If the class was loaded from a bundle: * fixes up the given list in place with heap-allocated selector strings * If the class was not from a bundle: * allocates a copy of the method list, fixes up the copy, and returns * the copy. The given list is unmodified. * * If cls is already in use, methodListLock must be held by the caller. **********************************************************************/ // Fixed-up method lists get mlist->obsolete = _OBJC_FIXED_UP. #define _OBJC_FIXED_UP ((void *)1771) static struct objc_method_list *fixupSelectorsInMethodList(Class cls, struct objc_method_list *mlist) { unsigned i, size; Method method; struct objc_method_list *old_mlist; if ( ! mlist ) return (struct objc_method_list *)0; if ( mlist->obsolete != _OBJC_FIXED_UP ) { BOOL isBundle = CLS_GETINFO(cls, CLS_FROM_BUNDLE) ? YES : NO; if (!isBundle) { old_mlist = mlist; size = sizeof(struct objc_method_list) - sizeof(struct objc_method) + old_mlist->method_count * sizeof(struct objc_method); mlist = _malloc_internal(size); memmove(mlist, old_mlist, size); } else { // Mach-O bundles are fixed up in place. // This prevents leaks when a bundle is unloaded. } sel_lock(); for ( i = 0; i < mlist->method_count; i += 1 ) { method = &mlist->method_list[i]; method->method_name = sel_registerNameNoLock((const char *)method->method_name, isBundle); // Always copy selector data from bundles. } sel_unlock(); mlist->obsolete = _OBJC_FIXED_UP; } return mlist; } /*********************************************************************** * nextMethodList * Returns successive method lists from the given class. * Method lists are returned in method search order (i.e. highest-priority * implementations first). * All necessary method list fixups are performed, so the * returned method list is fully-constructed. * * If cls is already in use, methodListLock must be held by the caller. * For full thread-safety, methodListLock must be continuously held by the * caller across all calls to nextMethodList(). If the lock is released, * the bad results listed in class_nextMethodList() may occur. * * void *iterator = NULL; * struct objc_method_list *mlist; * OBJC_LOCK(&methodListLock); * while ((mlist = nextMethodList(cls, &iterator))) { * // do something with mlist * } * OBJC_UNLOCK(&methodListLock); **********************************************************************/ static struct objc_method_list *nextMethodList(struct objc_class *cls, void **it) { uintptr_t index = *(uintptr_t *)it; struct objc_method_list **resultp; if (index == 0) { // First call to nextMethodList. if (!cls->methodLists) { resultp = NULL; } else if (cls->info & CLS_NO_METHOD_ARRAY) { resultp = (struct objc_method_list **)&cls->methodLists; } else { resultp = &cls->methodLists[0]; if (!*resultp || *resultp == END_OF_METHODS_LIST) { resultp = NULL; } } } else { // Subsequent call to nextMethodList. if (!cls->methodLists) { resultp = NULL; } else if (cls->info & CLS_NO_METHOD_ARRAY) { resultp = NULL; } else { resultp = &cls->methodLists[index]; if (!*resultp || *resultp == END_OF_METHODS_LIST) { resultp = NULL; } } } // resultp now is NULL, meaning there are no more method lists, // OR the address of the method list pointer to fix up and return. if (resultp) { if (*resultp && (*resultp)->obsolete != _OBJC_FIXED_UP) { *resultp = fixupSelectorsInMethodList(cls, *resultp); } *it = (void *)(index + 1); return *resultp; } else { *it = 0; return NULL; } } /* These next three functions are the heart of ObjC method lookup. * If the class is currently in use, methodListLock must be held by the caller. */ static inline Method _findMethodInList(struct objc_method_list * mlist, SEL sel) { int i; if (!mlist) return NULL; for (i = 0; i < mlist->method_count; i++) { Method m = &mlist->method_list[i]; if (m->method_name == sel) { return m; } } return NULL; } static inline Method _findMethodInClass(Class cls, SEL sel) __attribute__((always_inline)); static inline Method _findMethodInClass(Class cls, SEL sel) { // Flattened version of nextMethodList(). The optimizer doesn't // do a good job with hoisting the conditionals out of the loop. // Conceptually, this looks like: // while ((mlist = nextMethodList(cls, &iterator))) { // Method m = _findMethodInList(mlist, sel); // if (m) return m; // } if (!cls->methodLists) { // No method lists. return NULL; } else if (cls->info & CLS_NO_METHOD_ARRAY) { // One method list. struct objc_method_list **mlistp; mlistp = (struct objc_method_list **)&cls->methodLists; if ((*mlistp)->obsolete != _OBJC_FIXED_UP) { *mlistp = fixupSelectorsInMethodList(cls, *mlistp); } return _findMethodInList(*mlistp, sel); } else { // Multiple method lists. struct objc_method_list **mlistp; for (mlistp = cls->methodLists; *mlistp != NULL && *mlistp != END_OF_METHODS_LIST; mlistp++) { Method m; if ((*mlistp)->obsolete != _OBJC_FIXED_UP) { *mlistp = fixupSelectorsInMethodList(cls, *mlistp); } m = _findMethodInList(*mlistp, sel); if (m) return m; } return NULL; } } static inline Method _getMethod(Class cls, SEL sel) { for (; cls; cls = cls->super_class) { Method m; m = _findMethodInClass(cls, sel); if (m) return m; } return NULL; } // fixme for gc debugging temporary use __private_extern__ IMP findIMPInClass(Class cls, SEL sel) { Method m = _findMethodInClass(cls, sel); if (m) return m->method_imp; else return NULL; } /*********************************************************************** * class_getInstanceMethod. Return the instance method for the * specified class and selector. **********************************************************************/ Method class_getInstanceMethod (Class aClass, SEL aSelector) { Method result; // Need both a class and a selector if (!aClass || !aSelector) return NULL; // Go to the class OBJC_LOCK(&methodListLock); result = _getMethod (aClass, aSelector); OBJC_UNLOCK(&methodListLock); return result; } /*********************************************************************** * class_getClassMethod. Return the class method for the specified * class and selector. **********************************************************************/ Method class_getClassMethod (Class aClass, SEL aSelector) { Method result; // Need both a class and a selector if (!aClass || !aSelector) return NULL; // Go to the class or isa OBJC_LOCK(&methodListLock); result = _getMethod (GETMETA(aClass), aSelector); OBJC_UNLOCK(&methodListLock); return result; } /*********************************************************************** * class_getVariable. Return the named instance variable. **********************************************************************/ static Ivar class_getVariable (Class cls, const char * name) { struct objc_class * thisCls; // Outer loop - search the class and its superclasses for (thisCls = cls; thisCls != Nil; thisCls = ((struct objc_class *) thisCls)->super_class) { int index; Ivar thisIvar; // Skip class having no ivars if (!thisCls->ivars) continue; // Inner loop - search the given class thisIvar = &thisCls->ivars->ivar_list[0]; for (index = 0; index < thisCls->ivars->ivar_count; index += 1) { // Check this ivar's name. Be careful because the // compiler generates ivar entries with NULL ivar_name // (e.g. for anonymous bit fields). if ((thisIvar->ivar_name) && (strcmp (name, thisIvar->ivar_name) == 0)) return thisIvar; // Move to next ivar thisIvar += 1; } } // Not found return NULL; } /*********************************************************************** * class_getInstanceVariable. Return the named instance variable. * * Someday add class_getClassVariable (). **********************************************************************/ Ivar class_getInstanceVariable (Class aClass, const char * name) { // Must have a class and a name if (!aClass || !name) return NULL; // Look it up return class_getVariable (aClass, name); } /*********************************************************************** * flush_caches. Flush the instance and optionally class method caches * of cls and all its subclasses. * * Specifying Nil for the class "all classes." **********************************************************************/ static void flush_caches(Class cls, BOOL flush_meta) { int numClasses = 0, newNumClasses; struct objc_class * * classes = NULL; int i; struct objc_class * clsObject; #ifdef OBJC_INSTRUMENTED unsigned int classesVisited; unsigned int subclassCount; #endif // Do nothing if class has no cache // This check is safe to do without any cache locks. if (cls && !((struct objc_class *) cls)->cache) return; newNumClasses = objc_getClassList((Class *)NULL, 0); while (numClasses < newNumClasses) { numClasses = newNumClasses; classes = _realloc_internal(classes, sizeof(Class) * numClasses); newNumClasses = objc_getClassList((Class *)classes, numClasses); } numClasses = newNumClasses; OBJC_LOCK(&cacheUpdateLock); // Handle nil and root instance class specially: flush all // instance and class method caches. Nice that this // loop is linear vs the N-squared loop just below. if (!cls || !((struct objc_class *) cls)->super_class) { #ifdef OBJC_INSTRUMENTED LinearFlushCachesCount += 1; classesVisited = 0; subclassCount = 0; #endif // Traverse all classes in the hash table for (i = 0; i < numClasses; i++) { struct objc_class * metaClsObject; #ifdef OBJC_INSTRUMENTED classesVisited += 1; #endif clsObject = classes[i]; // Skip class that is known not to be a subclass of this root // (the isa pointer of any meta class points to the meta class // of the root). // NOTE: When is an isa pointer of a hash tabled class ever nil? metaClsObject = clsObject->isa; if (cls && metaClsObject && cls->isa != metaClsObject->isa) { continue; } #ifdef OBJC_INSTRUMENTED subclassCount += 1; #endif _cache_flush (clsObject); if (flush_meta && metaClsObject != NULL) { _cache_flush (metaClsObject); } } #ifdef OBJC_INSTRUMENTED LinearFlushCachesVisitedCount += classesVisited; if (classesVisited > MaxLinearFlushCachesVisitedCount) MaxLinearFlushCachesVisitedCount = classesVisited; IdealFlushCachesCount += subclassCount; if (subclassCount > MaxIdealFlushCachesCount) MaxIdealFlushCachesCount = subclassCount; #endif OBJC_UNLOCK(&cacheUpdateLock); _free_internal(classes); return; } // Outer loop - flush any cache that could now get a method from // cls (i.e. the cache associated with cls and any of its subclasses). #ifdef OBJC_INSTRUMENTED NonlinearFlushCachesCount += 1; classesVisited = 0; subclassCount = 0; #endif for (i = 0; i < numClasses; i++) { struct objc_class * clsIter; #ifdef OBJC_INSTRUMENTED NonlinearFlushCachesClassCount += 1; #endif clsObject = classes[i]; // Inner loop - Process a given class clsIter = clsObject; while (clsIter) { #ifdef OBJC_INSTRUMENTED classesVisited += 1; #endif // Flush clsObject instance method cache if // clsObject is a subclass of cls, or is cls itself // Flush the class method cache if that was asked for if (clsIter == cls) { #ifdef OBJC_INSTRUMENTED subclassCount += 1; #endif _cache_flush (clsObject); if (flush_meta) _cache_flush (clsObject->isa); break; } // Flush clsObject class method cache if cls is // the meta class of clsObject or of one // of clsObject's superclasses else if (clsIter->isa == cls) { #ifdef OBJC_INSTRUMENTED subclassCount += 1; #endif _cache_flush (clsObject->isa); break; } // Move up superclass chain else if (ISINITIALIZED(clsIter)) clsIter = clsIter->super_class; // clsIter is not initialized, so its cache // must be empty. This happens only when // clsIter == clsObject, because // superclasses are initialized before // subclasses, and this loop traverses // from sub- to super- classes. else break; } } #ifdef OBJC_INSTRUMENTED NonlinearFlushCachesVisitedCount += classesVisited; if (classesVisited > MaxNonlinearFlushCachesVisitedCount) MaxNonlinearFlushCachesVisitedCount = classesVisited; IdealFlushCachesCount += subclassCount; if (subclassCount > MaxIdealFlushCachesCount) MaxIdealFlushCachesCount = subclassCount; #endif OBJC_UNLOCK(&cacheUpdateLock); _free_internal(classes); } /*********************************************************************** * _objc_flush_caches. Flush the caches of the specified class and any * of its subclasses. If cls is a meta-class, only meta-class (i.e. * class method) caches are flushed. If cls is an instance-class, both * instance-class and meta-class caches are flushed. **********************************************************************/ void _objc_flush_caches (Class cls) { flush_caches (cls, YES); } /*********************************************************************** * do_not_remove_this_dummy_function. **********************************************************************/ void do_not_remove_this_dummy_function (void) { (void) class_nextMethodList (NULL, NULL); } /*********************************************************************** * class_nextMethodList. * External version of nextMethodList(). * * This function is not fully thread-safe. A series of calls to * class_nextMethodList() may fail if methods are added to or removed * from the class between calls. * If methods are added between calls to class_nextMethodList(), it may * return previously-returned method lists again, and may fail to return * newly-added lists. * If methods are removed between calls to class_nextMethodList(), it may * omit surviving method lists or simply crash. **********************************************************************/ OBJC_EXPORT struct objc_method_list * class_nextMethodList (Class cls, void ** it) { struct objc_method_list *result; OBJC_LOCK(&methodListLock); result = nextMethodList(cls, it); OBJC_UNLOCK(&methodListLock); return result; } /*********************************************************************** * _dummy. **********************************************************************/ void _dummy (void) { (void) class_nextMethodList (Nil, NULL); } /*********************************************************************** * class_addMethods. * * Formerly class_addInstanceMethods () **********************************************************************/ void class_addMethods (Class cls, struct objc_method_list * meths) { // Add the methods. OBJC_LOCK(&methodListLock); _objc_insertMethods(cls, meths); OBJC_UNLOCK(&methodListLock); // Must flush when dynamically adding methods. No need to flush // all the class method caches. If cls is a meta class, though, // this will still flush it and any of its sub-meta classes. flush_caches (cls, NO); } /*********************************************************************** * class_addClassMethods. * * Obsolete (for binary compatibility only). **********************************************************************/ void class_addClassMethods (Class cls, struct objc_method_list * meths) { class_addMethods (((struct objc_class *) cls)->isa, meths); } /*********************************************************************** * class_removeMethods. **********************************************************************/ void class_removeMethods (Class cls, struct objc_method_list * meths) { // Remove the methods OBJC_LOCK(&methodListLock); _objc_removeMethods(cls, meths); OBJC_UNLOCK(&methodListLock); // Must flush when dynamically removing methods. No need to flush // all the class method caches. If cls is a meta class, though, // this will still flush it and any of its sub-meta classes. flush_caches (cls, NO); } /*********************************************************************** * addClassToOriginalClass. Add to a hash table of classes involved in * a posing situation. We use this when we need to get to the "original" * class for some particular name through the function objc_getOrigClass. * For instance, the implementation of [super ...] will use this to be * sure that it gets hold of the correct super class, so that no infinite * loops will occur if the class it appears in is involved in posing. * * We use the classLock to guard the hash table. * * See tracker bug #51856. **********************************************************************/ static NXMapTable * posed_class_hash = NULL; static NXMapTable * posed_class_to_original_class_hash = NULL; static void addClassToOriginalClass (Class posingClass, Class originalClass) { // Install hash table when it is first needed if (!posed_class_to_original_class_hash) { posed_class_to_original_class_hash = NXCreateMapTableFromZone (NXPtrValueMapPrototype, 8, _objc_internal_zone ()); } // Add pose to hash table NXMapInsert (posed_class_to_original_class_hash, posingClass, originalClass); } /*********************************************************************** * getOriginalClassForPosingClass. **********************************************************************/ Class getOriginalClassForPosingClass (Class posingClass) { return NXMapGet (posed_class_to_original_class_hash, posingClass); } /*********************************************************************** * objc_getOrigClass. **********************************************************************/ Class objc_getOrigClass (const char * name) { struct objc_class * ret; // Look for class among the posers ret = Nil; OBJC_LOCK(&classLock); if (posed_class_hash) ret = (Class) NXMapGet (posed_class_hash, name); OBJC_UNLOCK(&classLock); if (ret) return ret; // Not a poser. Do a normal lookup. ret = objc_getClass (name); if (!ret) _objc_inform ("class `%s' not linked into application", name); return ret; } /*********************************************************************** * _objc_addOrigClass. This function is only used from class_poseAs. * Registers the original class names, before they get obscured by * posing, so that [super ..] will work correctly from categories * in posing classes and in categories in classes being posed for. **********************************************************************/ static void _objc_addOrigClass (Class origClass) { OBJC_LOCK(&classLock); // Create the poser's hash table on first use if (!posed_class_hash) { posed_class_hash = NXCreateMapTableFromZone (NXStrValueMapPrototype, 8, _objc_internal_zone ()); } // Add the named class iff it is not already there (or collides?) if (NXMapGet (posed_class_hash, ((struct objc_class *)origClass)->name) == 0) NXMapInsert (posed_class_hash, ((struct objc_class *)origClass)->name, origClass); OBJC_UNLOCK(&classLock); } /*********************************************************************** * class_poseAs. * * !!! class_poseAs () does not currently flush any caches. **********************************************************************/ Class class_poseAs (Class imposter, Class original) { struct objc_class * clsObject; char * imposterNamePtr; NXHashTable * class_hash; NXHashState state; struct objc_class * copy; #ifdef OBJC_CLASS_REFS header_info * hInfo; #endif // Trivial case is easy if (imposter == original) return imposter; // Imposter must be an immediate subclass of the original if (((struct objc_class *)imposter)->super_class != original) { __objc_error(imposter, _errNotSuper, ((struct objc_class *)imposter)->name, ((struct objc_class *)original)->name); } // Can't pose when you have instance variables (how could it work?) if (((struct objc_class *)imposter)->ivars) { __objc_error(imposter, _errNewVars, ((struct objc_class *)imposter)->name, ((struct objc_class *)original)->name, ((struct objc_class *)imposter)->name); } // Build a string to use to replace the name of the original class. #define imposterNamePrefix "_%" imposterNamePtr = _malloc_internal(strlen(((struct objc_class *)original)->name) + strlen(imposterNamePrefix) + 1); strcpy(imposterNamePtr, imposterNamePrefix); strcat(imposterNamePtr, ((struct objc_class *)original)->name); #undef imposterNamePrefix // We lock the class hashtable, so we are thread safe with respect to // calls to objc_getClass (). However, the class names are not // changed atomically, nor are all of the subclasses updated // atomically. I have ordered the operations so that you will // never crash, but you may get inconsistent results.... // Register the original class so that [super ..] knows // exactly which classes are the "original" classes. _objc_addOrigClass (original); _objc_addOrigClass (imposter); // Copy the imposter, so that the imposter can continue // its normal life in addition to changing the behavior of // the original. As a hack we don't bother to copy the metaclass. // For some reason we modify the original rather than the copy. copy = (*_zoneAlloc)(imposter->isa, sizeof(struct objc_class), _objc_internal_zone()); memmove(copy, imposter, sizeof(struct objc_class)); OBJC_LOCK(&classLock); class_hash = objc_getClasses (); // Remove both the imposter and the original class. NXHashRemove (class_hash, imposter); NXHashRemove (class_hash, original); NXHashInsert (class_hash, copy); addClassToOriginalClass (imposter, copy); // Mark the imposter as such _class_setInfo(imposter, CLS_POSING); _class_setInfo(imposter->isa, CLS_POSING); // Change the name of the imposter to that of the original class. ((struct objc_class *)imposter)->name = ((struct objc_class *)original)->name; ((struct objc_class *)imposter)->isa->name = ((struct objc_class *)original)->isa->name; // Also copy the version field to avoid archiving problems. ((struct objc_class *)imposter)->version = ((struct objc_class *)original)->version; // Change all subclasses of the original to point to the imposter. state = NXInitHashState (class_hash); while (NXNextHashState (class_hash, &state, (void **) &clsObject)) { while ((clsObject) && (clsObject != imposter) && (clsObject != copy)) { if (clsObject->super_class == original) { clsObject->super_class = imposter; clsObject->isa->super_class = ((struct objc_class *)imposter)->isa; // We must flush caches here! break; } clsObject = clsObject->super_class; } } #ifdef OBJC_CLASS_REFS // Replace the original with the imposter in all class refs // Major loop - process all headers for (hInfo = _objc_headerStart(); hInfo != NULL; hInfo = hInfo->next) { Class * cls_refs; unsigned int refCount; unsigned int index; // Get refs associated with this header cls_refs = (Class *) _getObjcClassRefs ((headerType *) hInfo->mhdr, &refCount); if (!cls_refs || !refCount) continue; // Minor loop - process this header's refs cls_refs = (Class *) ((unsigned long) cls_refs + hInfo->image_slide); for (index = 0; index < refCount; index += 1) { if (cls_refs[index] == original) cls_refs[index] = imposter; } } #endif // OBJC_CLASS_REFS // Change the name of the original class. ((struct objc_class *)original)->name = imposterNamePtr + 1; ((struct objc_class *)original)->isa->name = imposterNamePtr; // Restore the imposter and the original class with their new names. NXHashInsert (class_hash, imposter); NXHashInsert (class_hash, original); OBJC_UNLOCK(&classLock); return imposter; } /*********************************************************************** * _freedHandler. **********************************************************************/ static void _freedHandler (id self, SEL sel) { __objc_error (self, _errFreedObject, SELNAME(sel), self); } /*********************************************************************** * _nonexistentHandler. **********************************************************************/ static void _nonexistentHandler (id self, SEL sel) { __objc_error (self, _errNonExistentObject, SELNAME(sel), self); } /*********************************************************************** * class_respondsToMethod. * * Called from -[Object respondsTo:] and +[Object instancesRespondTo:] **********************************************************************/ BOOL class_respondsToMethod (Class cls, SEL sel) { Method meth; IMP imp; // No one responds to zero! if (!sel) return NO; imp = _cache_getImp(cls, sel); if (imp) { // Found method in cache. // If the cache entry is forward::, the class does not respond to sel. return (imp != &_objc_msgForward); } // Handle cache miss OBJC_LOCK(&methodListLock); meth = _getMethod(cls, sel); OBJC_UNLOCK(&methodListLock); if (meth) { _cache_fill(cls, meth, sel); return YES; } // Not implemented. Use _objc_msgForward. _cache_addForwardEntry(cls, sel); return NO; } /*********************************************************************** * class_lookupMethod. * * Called from -[Object methodFor:] and +[Object instanceMethodFor:] **********************************************************************/ IMP class_lookupMethod (Class cls, SEL sel) { IMP imp; // No one responds to zero! if (!sel) { __objc_error(cls, _errBadSel, sel); } imp = _cache_getImp(cls, sel); if (imp) return imp; // Handle cache miss return _class_lookupMethodAndLoadCache (cls, sel); } /*********************************************************************** * lookupNamedMethodInMethodList * Only called to find +load/-.cxx_construct/-.cxx_destruct methods, * without fixing up the entire method list. * The class is not yet in use, so methodListLock is not taken. **********************************************************************/ __private_extern__ IMP lookupNamedMethodInMethodList(struct objc_method_list *mlist, const char *meth_name) { Method m = meth_name ? _findNamedMethodInList(mlist, meth_name) : NULL; return (m ? m->method_imp : NULL); } /*********************************************************************** * _cache_malloc. * * Called from _cache_create() and cache_expand() * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ static Cache _cache_malloc(int slotCount) { Cache new_cache; size_t size; // Allocate table (why not check for failure?) size = sizeof(struct objc_cache) + TABLE_SIZE(slotCount); #ifdef OBJC_INSTRUMENTED // Custom cache allocator can't handle instrumentation. size += sizeof(CacheInstrumentation); new_cache = _calloc_internal(size, 1); new_cache->mask = slotCount - 1; #else if (size < CACHE_QUANTUM || UseInternalZone) { new_cache = _calloc_internal(size, 1); new_cache->mask = slotCount - 1; // occupied and buckets and instrumentation are all zero } else { new_cache = cache_allocator_calloc(size); // mask is already set // occupied and buckets and instrumentation are all zero } #endif return new_cache; } /*********************************************************************** * _cache_create. * * Called from _cache_expand(). * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ Cache _cache_create (Class cls) { Cache new_cache; int slotCount; // Select appropriate size slotCount = (ISMETA(cls)) ? INIT_META_CACHE_SIZE : INIT_CACHE_SIZE; new_cache = _cache_malloc(slotCount); // Install the cache ((struct objc_class *)cls)->cache = new_cache; // Clear the cache flush flag so that we will not flush this cache // before expanding it for the first time. _class_clearInfo(cls, CLS_FLUSH_CACHE); // Clear the grow flag so that we will re-use the current storage, // rather than actually grow the cache, when expanding the cache // for the first time if (_class_slow_grow) _class_clearInfo(cls, CLS_GROW_CACHE); // Return our creation return new_cache; } /*********************************************************************** * _cache_expand. * * Called from _cache_fill () * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ static Cache _cache_expand (Class cls) { Cache old_cache; Cache new_cache; unsigned int slotCount; unsigned int index; // First growth goes from emptyCache to a real one old_cache = ((struct objc_class *)cls)->cache; if (old_cache == &emptyCache) return _cache_create (cls); // iff _class_slow_grow, trade off actual cache growth with re-using // the current one, so that growth only happens every odd time if (_class_slow_grow) { // CLS_GROW_CACHE controls every-other-time behavior. If it // is non-zero, let the cache grow this time, but clear the // flag so the cache is reused next time if ((((struct objc_class * )cls)->info & CLS_GROW_CACHE) != 0) _class_clearInfo(cls, CLS_GROW_CACHE); // Reuse the current cache storage this time else { // Clear the valid-entry counter old_cache->occupied = 0; // Invalidate all the cache entries for (index = 0; index < old_cache->mask + 1; index += 1) { // Remember what this entry was, so we can possibly // deallocate it after the bucket has been invalidated Method oldEntry = old_cache->buckets[index]; // Skip invalid entry if (!CACHE_BUCKET_VALID(old_cache->buckets[index])) continue; // Invalidate this entry CACHE_BUCKET_VALID(old_cache->buckets[index]) = NULL; // Deallocate "forward::" entry if (CACHE_BUCKET_IMP(oldEntry) == &_objc_msgForward) { _cache_collect_free (oldEntry, sizeof(struct objc_method), NO); } } // Set the slow growth flag so the cache is next grown _class_setInfo(cls, CLS_GROW_CACHE); // Return the same old cache, freshly emptied return old_cache; } } // Double the cache size slotCount = (old_cache->mask + 1) << 1; new_cache = _cache_malloc(slotCount); #ifdef OBJC_INSTRUMENTED // Propagate the instrumentation data { CacheInstrumentation * oldCacheData; CacheInstrumentation * newCacheData; oldCacheData = CACHE_INSTRUMENTATION(old_cache); newCacheData = CACHE_INSTRUMENTATION(new_cache); bcopy ((const char *)oldCacheData, (char *)newCacheData, sizeof(CacheInstrumentation)); } #endif // iff _class_uncache, copy old cache entries into the new cache if (_class_uncache == 0) { int newMask; newMask = new_cache->mask; // Look at all entries in the old cache for (index = 0; index < old_cache->mask + 1; index += 1) { int index2; // Skip invalid entry if (!CACHE_BUCKET_VALID(old_cache->buckets[index])) continue; // Hash the old entry into the new table index2 = CACHE_HASH(CACHE_BUCKET_NAME(old_cache->buckets[index]), newMask); // Find an available spot, at or following the hashed spot; // Guaranteed to not infinite loop, because table has grown for (;;) { if (!CACHE_BUCKET_VALID(new_cache->buckets[index2])) { new_cache->buckets[index2] = old_cache->buckets[index]; break; } index2 += 1; index2 &= newMask; } // Account for the addition new_cache->occupied += 1; } // Set the cache flush flag so that we will flush this cache // before expanding it again. _class_setInfo(cls, CLS_FLUSH_CACHE); } // Deallocate "forward::" entries from the old cache else { for (index = 0; index < old_cache->mask + 1; index += 1) { if (CACHE_BUCKET_VALID(old_cache->buckets[index]) && CACHE_BUCKET_IMP(old_cache->buckets[index]) == &_objc_msgForward) { _cache_collect_free (old_cache->buckets[index], sizeof(struct objc_method), NO); } } } // Install new cache ((struct objc_class *)cls)->cache = new_cache; // Deallocate old cache, try freeing all the garbage _cache_collect_free (old_cache, old_cache->mask * sizeof(Method), YES); return new_cache; } /*********************************************************************** * instrumentObjcMessageSends/logObjcMessageSends. **********************************************************************/ static int LogObjCMessageSend (BOOL isClassMethod, const char * objectsClass, const char * implementingClass, SEL selector) { char buf[ 1024 ]; // Create/open the log file if (objcMsgLogFD == (-1)) { snprintf (buf, sizeof(buf), "/tmp/msgSends-%d", (int) getpid ()); objcMsgLogFD = secure_open (buf, O_WRONLY | O_CREAT, geteuid()); if (objcMsgLogFD < 0) { // no log file - disable logging objcMsgLogEnabled = 0; objcMsgLogFD = -1; return 1; } } // Make the log entry snprintf(buf, sizeof(buf), "%c %s %s %s\n", isClassMethod ? '+' : '-', objectsClass, implementingClass, (char *) selector); write (objcMsgLogFD, buf, strlen(buf)); // Tell caller to not cache the method return 0; } void instrumentObjcMessageSends (BOOL flag) { int enabledValue = (flag) ? 1 : 0; // Shortcut NOP if (objcMsgLogEnabled == enabledValue) return; // If enabling, flush all method caches so we get some traces if (flag) flush_caches (Nil, YES); // Sync our log file if (objcMsgLogFD != (-1)) fsync (objcMsgLogFD); objcMsgLogEnabled = enabledValue; } void logObjcMessageSends (ObjCLogProc logProc) { if (logProc) { objcMsgLogProc = logProc; objcMsgLogEnabled = 1; } else { objcMsgLogProc = logProc; objcMsgLogEnabled = 0; } if (objcMsgLogFD != (-1)) fsync (objcMsgLogFD); } /*********************************************************************** * _cache_fill. Add the specified method to the specified class' cache. * Returns NO if the cache entry wasn't added: cache was busy, * class is still being initialized, new entry is a duplicate. * * Called only from _class_lookupMethodAndLoadCache and * class_respondsToMethod and _cache_addForwardEntry. * * Cache locks: cacheUpdateLock must not be held. **********************************************************************/ static BOOL _cache_fill(Class cls, Method smt, SEL sel) { unsigned int newOccupied; arith_t index; Method *buckets; Cache cache; // Never cache before +initialize is done if (!ISINITIALIZED(cls)) { return NO; } // Keep tally of cache additions totalCacheFills += 1; OBJC_LOCK(&cacheUpdateLock); cache = ((struct objc_class *)cls)->cache; // Check for duplicate entries, if we're in the mode if (traceDuplicates) { int index2; arith_t mask = cache->mask; buckets = cache->buckets; // Scan the cache for (index2 = 0; index2 < mask + 1; index2 += 1) { // Skip invalid or non-duplicate entry if ((!CACHE_BUCKET_VALID(buckets[index2])) || (strcmp ((char *) CACHE_BUCKET_NAME(buckets[index2]), (char *) smt->method_name) != 0)) continue; // Tally duplication, but report iff wanted cacheFillDuplicates += 1; if (traceDuplicatesVerbose) { _objc_inform ("Cache fill duplicate #%d: found %x adding %x: %s\n", cacheFillDuplicates, (unsigned int) CACHE_BUCKET_NAME(buckets[index2]), (unsigned int) smt->method_name, (char *) smt->method_name); } } } // Make sure the entry wasn't added to the cache by some other thread // before we grabbed the cacheUpdateLock. // Don't use _cache_getMethod() because _cache_getMethod() doesn't // return forward:: entries. if (_cache_getImp(cls, sel)) { OBJC_UNLOCK(&cacheUpdateLock); return NO; // entry is already cached, didn't add new one } // Use the cache as-is if it is less than 3/4 full newOccupied = cache->occupied + 1; if ((newOccupied * 4) <= (cache->mask + 1) * 3) { // Cache is less than 3/4 full. cache->occupied = newOccupied; } else { // Cache is too full. Flush it or expand it. if ((((struct objc_class * )cls)->info & CLS_FLUSH_CACHE) != 0) { _cache_flush (cls); } else { cache = _cache_expand (cls); } // Account for the addition cache->occupied += 1; } // Insert the new entry. This can be done by either: // (a) Scanning for the first unused spot. Easy! // (b) Opening up an unused spot by sliding existing // entries down by one. The benefit of this // extra work is that it puts the most recently // loaded entries closest to where the selector // hash starts the search. // // The loop is a little more complicated because there // are two kinds of entries, so there have to be two ways // to slide them. buckets = cache->buckets; index = CACHE_HASH(sel, cache->mask); for (;;) { // Slide existing entries down by one Method saveMethod; // Copy current entry to a local saveMethod = buckets[index]; // Copy previous entry (or new entry) to current slot buckets[index] = smt; // Done if current slot had been invalid if (saveMethod == NULL) break; // Prepare to copy saved value into next slot smt = saveMethod; // Move on to next slot index += 1; index &= cache->mask; } OBJC_UNLOCK(&cacheUpdateLock); return YES; // successfully added new cache entry } /*********************************************************************** * _cache_addForwardEntry * Add a forward:: entry for the given selector to cls's method cache. * Does nothing if the cache addition fails for any reason. * Called from class_respondsToMethod and _class_lookupMethodAndLoadCache. * Cache locks: cacheUpdateLock must not be held. **********************************************************************/ static void _cache_addForwardEntry(Class cls, SEL sel) { Method smt; smt = _malloc_internal(sizeof(struct objc_method)); smt->method_name = sel; smt->method_types = ""; smt->method_imp = &_objc_msgForward; if (! _cache_fill(cls, smt, sel)) { // Entry not added to cache. Don't leak the method struct. _free_internal(smt); } } /*********************************************************************** * _cache_flush. Invalidate all valid entries in the given class' cache, * and clear the CLS_FLUSH_CACHE in the cls->info. * * Called from flush_caches() and _cache_fill() * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ static void _cache_flush (Class cls) { Cache cache; unsigned int index; // Locate cache. Ignore unused cache. cache = ((struct objc_class *)cls)->cache; if (cache == NULL || cache == &emptyCache) return; #ifdef OBJC_INSTRUMENTED { CacheInstrumentation * cacheData; // Tally this flush cacheData = CACHE_INSTRUMENTATION(cache); cacheData->flushCount += 1; cacheData->flushedEntries += cache->occupied; if (cache->occupied > cacheData->maxFlushedEntries) cacheData->maxFlushedEntries = cache->occupied; } #endif // Traverse the cache for (index = 0; index <= cache->mask; index += 1) { // Remember what this entry was, so we can possibly // deallocate it after the bucket has been invalidated Method oldEntry = cache->buckets[index]; // Invalidate this entry CACHE_BUCKET_VALID(cache->buckets[index]) = NULL; // Deallocate "forward::" entry if (oldEntry && oldEntry->method_imp == &_objc_msgForward) _cache_collect_free (oldEntry, sizeof(struct objc_method), NO); } // Clear the valid-entry counter cache->occupied = 0; // Clear the cache flush flag so that we will not flush this cache // before expanding it again. _class_clearInfo(cls, CLS_FLUSH_CACHE); } /*********************************************************************** * _objc_getFreedObjectClass. Return a pointer to the dummy freed * object class. Freed objects get their isa pointers replaced with * a pointer to the freedObjectClass, so that we can catch usages of * the freed object. **********************************************************************/ Class _objc_getFreedObjectClass (void) { return (Class) &freedObjectClass; } /*********************************************************************** * _objc_getNonexistentClass. Return a pointer to the dummy nonexistent * object class. This is used when, for example, mapping the class * refs for an image, and the class can not be found, so that we can * catch later uses of the non-existent class. **********************************************************************/ Class _objc_getNonexistentClass (void) { return (Class) &nonexistentObjectClass; } /*********************************************************************** * struct _objc_initializing_classes * Per-thread list of classes currently being initialized by that thread. * During initialization, that thread is allowed to send messages to that * class, but other threads have to wait. * The list is a simple array of metaclasses (the metaclass stores * the initialization state). **********************************************************************/ typedef struct _objc_initializing_classes { int classesAllocated; struct objc_class** metaclasses; } _objc_initializing_classes; /*********************************************************************** * _fetchInitializingClassList * Return the list of classes being initialized by this thread. * If create == YES, create the list when no classes are being initialized by this thread. * If create == NO, return NULL when no classes are being initialized by this thread. **********************************************************************/ static _objc_initializing_classes *_fetchInitializingClassList(BOOL create) { _objc_pthread_data *data; _objc_initializing_classes *list; struct objc_class **classes; data = pthread_getspecific(_objc_pthread_key); if (data == NULL) { if (!create) { return NULL; } else { data = _calloc_internal(1, sizeof(_objc_pthread_data)); pthread_setspecific(_objc_pthread_key, data); } } list = data->initializingClasses; if (list == NULL) { if (!create) { return NULL; } else { list = _calloc_internal(1, sizeof(_objc_initializing_classes)); data->initializingClasses = list; } } classes = list->metaclasses; if (classes == NULL) { // If _objc_initializing_classes exists, allocate metaclass array, // even if create == NO. // Allow 4 simultaneous class inits on this thread before realloc. list->classesAllocated = 4; classes = _calloc_internal(list->classesAllocated, sizeof(struct objc_class *)); list->metaclasses = classes; } return list; } /*********************************************************************** * _destroyInitializingClassList * Deallocate memory used by the given initialization list. * Any part of the list may be NULL. * Called from _objc_pthread_destroyspecific(). **********************************************************************/ void _destroyInitializingClassList(_objc_initializing_classes *list) { if (list != NULL) { if (list->metaclasses != NULL) { _free_internal(list->metaclasses); } _free_internal(list); } } /*********************************************************************** * _thisThreadIsInitializingClass * Return TRUE if this thread is currently initializing the given class. **********************************************************************/ static BOOL _thisThreadIsInitializingClass(struct objc_class *cls) { int i; _objc_initializing_classes *list = _fetchInitializingClassList(NO); if (list) { cls = GETMETA(cls); for (i = 0; i < list->classesAllocated; i++) { if (cls == list->metaclasses[i]) return YES; } } // no list or not found in list return NO; } /*********************************************************************** * _setThisThreadIsInitializingClass * Record that this thread is currently initializing the given class. * This thread will be allowed to send messages to the class, but * other threads will have to wait. **********************************************************************/ static void _setThisThreadIsInitializingClass(struct objc_class *cls) { int i; _objc_initializing_classes *list = _fetchInitializingClassList(YES); cls = GETMETA(cls); // paranoia: explicitly disallow duplicates for (i = 0; i < list->classesAllocated; i++) { if (cls == list->metaclasses[i]) { _objc_fatal("thread is already initializing this class!"); return; // already the initializer } } for (i = 0; i < list->classesAllocated; i++) { if (0 == list->metaclasses[i]) { list->metaclasses[i] = cls; return; } } // class list is full - reallocate list->classesAllocated = list->classesAllocated * 2 + 1; list->metaclasses = _realloc_internal(list->metaclasses, list->classesAllocated * sizeof(struct objc_class *)); // zero out the new entries list->metaclasses[i++] = cls; for ( ; i < list->classesAllocated; i++) { list->metaclasses[i] = NULL; } } /*********************************************************************** * _setThisThreadIsNotInitializingClass * Record that this thread is no longer initializing the given class. **********************************************************************/ static void _setThisThreadIsNotInitializingClass(struct objc_class *cls) { int i; _objc_initializing_classes *list = _fetchInitializingClassList(NO); if (list) { cls = GETMETA(cls); for (i = 0; i < list->classesAllocated; i++) { if (cls == list->metaclasses[i]) { list->metaclasses[i] = NULL; return; } } } // no list or not found in list _objc_fatal("thread is not initializing this class!"); } /*********************************************************************** * class_initialize. Send the '+initialize' message on demand to any * uninitialized class. Force initialization of superclasses first. * * Called only from _class_lookupMethodAndLoadCache (or itself). **********************************************************************/ static void class_initialize(struct objc_class *cls) { struct objc_class *infoCls = GETMETA(cls); BOOL reallyInitialize = NO; // Get the real class from the metaclass. The superclass chain // hangs off the real class only. // fixme ick if (ISMETA(cls)) { if (strncmp(cls->name, "_%", 2) == 0) { // Posee's meta's name is smashed and isn't in the class_hash, // so objc_getClass doesn't work. char *baseName = strchr(cls->name, '%'); // get posee's real name cls = objc_getClass(baseName); } else { cls = objc_getClass(cls->name); } } // Make sure super is done initializing BEFORE beginning to initialize cls. // See note about deadlock above. if (cls->super_class && !ISINITIALIZED(cls->super_class)) { class_initialize(cls->super_class); } // Try to atomically set CLS_INITIALIZING. pthread_mutex_lock(&classInitLock); if (!ISINITIALIZED(cls) && !ISINITIALIZING(cls)) { _class_setInfo(infoCls, CLS_INITIALIZING); reallyInitialize = YES; } pthread_mutex_unlock(&classInitLock); if (reallyInitialize) { // We successfully set the CLS_INITIALIZING bit. Initialize the class. // Record that we're initializing this class so we can message it. _setThisThreadIsInitializingClass(cls); // Send the +initialize message. // Note that +initialize is sent to the superclass (again) if // this class doesn't implement +initialize. 2157218 [(id)cls initialize]; // Done initializing. Update the info bits and notify waiting threads. pthread_mutex_lock(&classInitLock); _class_changeInfo(infoCls, CLS_INITIALIZED, CLS_INITIALIZING); pthread_cond_broadcast(&classInitWaitCond); pthread_mutex_unlock(&classInitLock); _setThisThreadIsNotInitializingClass(cls); return; } else if (ISINITIALIZING(cls)) { // We couldn't set INITIALIZING because INITIALIZING was already set. // If this thread set it earlier, continue normally. // If some other thread set it, block until initialize is done. // It's ok if INITIALIZING changes to INITIALIZED while we're here, // because we safely check for INITIALIZED inside the lock // before blocking. if (_thisThreadIsInitializingClass(cls)) { return; } else { pthread_mutex_lock(&classInitLock); while (!ISINITIALIZED(cls)) { pthread_cond_wait(&classInitWaitCond, &classInitLock); } pthread_mutex_unlock(&classInitLock); return; } } else if (ISINITIALIZED(cls)) { // Set CLS_INITIALIZING failed because someone else already // initialized the class. Continue normally. // NOTE this check must come AFTER the ISINITIALIZING case. // Otherwise: Another thread is initializing this class. ISINITIALIZED // is false. Skip this clause. Then the other thread finishes // initialization and sets INITIALIZING=no and INITIALIZED=yes. // Skip the ISINITIALIZING clause. Die horribly. return; } else { // We shouldn't be here. _objc_fatal("thread-safe class init in objc runtime is buggy!"); } } /*********************************************************************** * _class_lookupMethodAndLoadCache. * * Called only from objc_msgSend, objc_msgSendSuper and class_lookupMethod. **********************************************************************/ IMP _class_lookupMethodAndLoadCache (Class cls, SEL sel) { struct objc_class * curClass; Method meth; IMP methodPC = NULL; trace(0xb300, 0, 0, 0); // Check for freed class if (cls == &freedObjectClass) return (IMP) _freedHandler; // Check for nonexistent class if (cls == &nonexistentObjectClass) return (IMP) _nonexistentHandler; trace(0xb301, 0, 0, 0); if (!ISINITIALIZED(cls)) { class_initialize ((struct objc_class *)cls); // If sel == initialize, class_initialize will send +initialize and // then the messenger will send +initialize again after this // procedure finishes. Of course, if this is not being called // from the messenger then it won't happen. 2778172 } trace(0xb302, 0, 0, 0); // Outer loop - search the caches and method lists of the // class and its super-classes for (curClass = cls; curClass; curClass = ((struct objc_class * )curClass)->super_class) { #ifdef PRELOAD_SUPERCLASS_CACHES struct objc_class *curClass2; #endif trace(0xb303, 0, 0, 0); // Beware of thread-unsafety and double-freeing of forward:: // entries here! See note in "Method cache locking" above. // The upshot is that _cache_getMethod() will return NULL // instead of returning a forward:: entry. meth = _cache_getMethod(curClass, sel, &_objc_msgForward); if (meth) { // Found the method in this class or a superclass. // Cache the method in this class, unless we just found it in // this class's cache. if (curClass != cls) { #ifdef PRELOAD_SUPERCLASS_CACHES for (curClass2 = cls; curClass2 != curClass; curClass2 = curClass2->super_class) _cache_fill (curClass2, meth, sel); _cache_fill (curClass, meth, sel); #else _cache_fill (cls, meth, sel); #endif } methodPC = meth->method_imp; break; } trace(0xb304, (int)methodPC, 0, 0); // Cache scan failed. Search method list. OBJC_LOCK(&methodListLock); meth = _findMethodInClass(curClass, sel); OBJC_UNLOCK(&methodListLock); if (meth) { // If logging is enabled, log the message send and let // the logger decide whether to encache the method. if ((objcMsgLogEnabled == 0) || (objcMsgLogProc (CLS_GETINFO(((struct objc_class * )curClass), CLS_META) ? YES : NO, ((struct objc_class *)cls)->name, curClass->name, sel))) { // Cache the method implementation #ifdef PRELOAD_SUPERCLASS_CACHES for (curClass2 = cls; curClass2 != curClass; curClass2 = curClass2->super_class) _cache_fill (curClass2, meth, sel); _cache_fill (curClass, meth, sel); #else _cache_fill (cls, meth, sel); #endif } methodPC = meth->method_imp; break; } trace(0xb305, (int)methodPC, 0, 0); } trace(0xb306, (int)methodPC, 0, 0); if (methodPC == NULL) { // Class and superclasses do not respond -- use forwarding _cache_addForwardEntry(cls, sel); methodPC = &_objc_msgForward; } trace(0xb30f, (int)methodPC, 0, 0); return methodPC; } /*********************************************************************** * lookupMethodInClassAndLoadCache. * Like _class_lookupMethodAndLoadCache, but does not search superclasses. * Caches and returns objc_msgForward if the method is not found in the class. **********************************************************************/ static IMP lookupMethodInClassAndLoadCache(Class cls, SEL sel) { Method meth; IMP imp; // Search cache first. imp = _cache_getImp(cls, sel); if (imp) return imp; // Cache miss. Search method list. OBJC_LOCK(&methodListLock); meth = _findMethodInClass(cls, sel); OBJC_UNLOCK(&methodListLock); if (meth) { // Hit in method list. Cache it. _cache_fill(cls, meth, sel); return meth->method_imp; } else { // Miss in method list. Cache objc_msgForward. _cache_addForwardEntry(cls, sel); return &_objc_msgForward; } } /*********************************************************************** * _class_changeInfo * Atomically sets and clears some bits in cls's info field. * set and clear must not overlap. **********************************************************************/ static pthread_mutex_t infoLock = PTHREAD_MUTEX_INITIALIZER; __private_extern__ void _class_changeInfo(struct objc_class *cls, long set, long clear) { pthread_mutex_lock(&infoLock); cls->info = (cls->info | set) & ~clear; pthread_mutex_unlock(&infoLock); } /*********************************************************************** * _class_setInfo * Atomically sets some bits in cls's info field. **********************************************************************/ __private_extern__ void _class_setInfo(struct objc_class *cls, long set) { _class_changeInfo(cls, set, 0); } /*********************************************************************** * _class_clearInfo * Atomically clears some bits in cls's info field. **********************************************************************/ __private_extern__ void _class_clearInfo(struct objc_class *cls, long clear) { _class_changeInfo(cls, 0, clear); } /*********************************************************************** * SubtypeUntil. * * Delegation. **********************************************************************/ static int SubtypeUntil (const char * type, char end) { int level = 0; const char * head = type; // while (*type) { if (!*type || (!level && (*type == end))) return (int)(type - head); switch (*type) { case ']': case '}': case ')': level--; break; case '[': case '{': case '(': level += 1; break; } type += 1; } _objc_fatal ("Object: SubtypeUntil: end of type encountered prematurely\n"); return 0; } /*********************************************************************** * SkipFirstType. **********************************************************************/ static const char * SkipFirstType (const char * type) { while (1) { switch (*type++) { case 'O': /* bycopy */ case 'n': /* in */ case 'o': /* out */ case 'N': /* inout */ case 'r': /* const */ case 'V': /* oneway */ case '^': /* pointers */ break; /* arrays */ case '[': while ((*type >= '0') && (*type <= '9')) type += 1; return type + SubtypeUntil (type, ']') + 1; /* structures */ case '{': return type + SubtypeUntil (type, '}') + 1; /* unions */ case '(': return type + SubtypeUntil (type, ')') + 1; /* basic types */ default: return type; } } } /*********************************************************************** * method_getNumberOfArguments. **********************************************************************/ unsigned method_getNumberOfArguments (Method method) { const char * typedesc; unsigned nargs; // First, skip the return type typedesc = method->method_types; typedesc = SkipFirstType (typedesc); // Next, skip stack size while ((*typedesc >= '0') && (*typedesc <= '9')) typedesc += 1; // Now, we have the arguments - count how many nargs = 0; while (*typedesc) { // Traverse argument type typedesc = SkipFirstType (typedesc); // Skip GNU runtime's register parameter hint if (*typedesc == '+') typedesc++; // Traverse (possibly negative) argument offset if (*typedesc == '-') typedesc += 1; while ((*typedesc >= '0') && (*typedesc <= '9')) typedesc += 1; // Made it past an argument nargs += 1; } return nargs; } /*********************************************************************** * method_getSizeOfArguments. **********************************************************************/ #ifndef __alpha__ unsigned method_getSizeOfArguments (Method method) { const char * typedesc; unsigned stack_size; #if defined(__ppc__) || defined(ppc) unsigned trueBaseOffset; unsigned foundBaseOffset; #endif // Get our starting points stack_size = 0; typedesc = method->method_types; // Skip the return type #if defined (__ppc__) || defined(ppc) // Struct returns cause the parameters to be bumped // by a register, so the offset to the receiver is // 4 instead of the normal 0. trueBaseOffset = (*typedesc == '{') ? 4 : 0; #endif typedesc = SkipFirstType (typedesc); // Convert ASCII number string to integer while ((*typedesc >= '0') && (*typedesc <= '9')) stack_size = (stack_size * 10) + (*typedesc++ - '0'); #if defined (__ppc__) || defined(ppc) // NOTE: This is a temporary measure pending a compiler fix. // Work around PowerPC compiler bug wherein the method argument // string contains an incorrect value for the "stack size." // Generally, the size is reported 4 bytes too small, so we apply // that fudge factor. Unfortunately, there is at least one case // where the error is something other than -4: when the last // parameter is a double, the reported stack is much too high // (about 32 bytes). We do not attempt to detect that case. // The result of returning a too-high value is that objc_msgSendv // can bus error if the destination of the marg_list copying // butts up against excluded memory. // This fix disables itself when it sees a correctly built // type string (i.e. the offset for the Id is correct). This // keeps us out of lockstep with the compiler. // skip the '@' marking the Id field typedesc = SkipFirstType (typedesc); // Skip GNU runtime's register parameter hint if (*typedesc == '+') typedesc++; // pick up the offset for the Id field foundBaseOffset = 0; while ((*typedesc >= '0') && (*typedesc <= '9')) foundBaseOffset = (foundBaseOffset * 10) + (*typedesc++ - '0'); // add fudge factor iff the Id field offset was wrong if (foundBaseOffset != trueBaseOffset) stack_size += 4; #endif return stack_size; } #else // __alpha__ // XXX Getting the size of a type is done all over the place // (Here, Foundation, remote project)! - Should unify unsigned int getSizeOfType (const char * type, unsigned int * alignPtr); unsigned method_getSizeOfArguments (Method method) { const char * type; int size; int index; int align; int offset; unsigned stack_size; int nargs; nargs = method_getNumberOfArguments (method); stack_size = (*method->method_types == '{') ? sizeof(void *) : 0; for (index = 0; index < nargs; index += 1) { (void) method_getArgumentInfo (method, index, &type, &offset); size = getSizeOfType (type, &align); stack_size += ((size + 7) & ~7); } return stack_size; } #endif // __alpha__ /*********************************************************************** * method_getArgumentInfo. **********************************************************************/ unsigned method_getArgumentInfo (Method method, int arg, const char ** type, int * offset) { const char * typedesc = method->method_types; unsigned nargs = 0; unsigned self_offset = 0; BOOL offset_is_negative = NO; // First, skip the return type typedesc = SkipFirstType (typedesc); // Next, skip stack size while ((*typedesc >= '0') && (*typedesc <= '9')) typedesc += 1; // Now, we have the arguments - position typedesc to the appropriate argument while (*typedesc && nargs != arg) { // Skip argument type typedesc = SkipFirstType (typedesc); if (nargs == 0) { // Skip GNU runtime's register parameter hint if (*typedesc == '+') typedesc++; // Skip negative sign in offset if (*typedesc == '-') { offset_is_negative = YES; typedesc += 1; } else offset_is_negative = NO; while ((*typedesc >= '0') && (*typedesc <= '9')) self_offset = self_offset * 10 + (*typedesc++ - '0'); if (offset_is_negative) self_offset = -(self_offset); } else { // Skip GNU runtime's register parameter hint if (*typedesc == '+') typedesc++; // Skip (possibly negative) argument offset if (*typedesc == '-') typedesc += 1; while ((*typedesc >= '0') && (*typedesc <= '9')) typedesc += 1; } nargs += 1; } if (*typedesc) { unsigned arg_offset = 0; *type = typedesc; typedesc = SkipFirstType (typedesc); if (arg == 0) { #ifdef hppa *offset = -sizeof(id); #else *offset = 0; #endif // hppa } else { // Skip GNU register parameter hint if (*typedesc == '+') typedesc++; // Pick up (possibly negative) argument offset if (*typedesc == '-') { offset_is_negative = YES; typedesc += 1; } else offset_is_negative = NO; while ((*typedesc >= '0') && (*typedesc <= '9')) arg_offset = arg_offset * 10 + (*typedesc++ - '0'); if (offset_is_negative) arg_offset = - arg_offset; #ifdef hppa // For stacks which grow up, since margs points // to the top of the stack or the END of the args, // the first offset is at -sizeof(id) rather than 0. self_offset += sizeof(id); #endif *offset = arg_offset - self_offset; } } else { *type = 0; *offset = 0; } return nargs; } /*********************************************************************** * _objc_create_zone. **********************************************************************/ void * _objc_create_zone (void) { return malloc_default_zone(); } /*********************************************************************** * _objc_internal_zone. * Malloc zone for internal runtime data. * By default this is the default malloc zone, but a dedicated zone is * used if environment variable OBJC_USE_INTERNAL_ZONE is set. **********************************************************************/ __private_extern__ malloc_zone_t *_objc_internal_zone(void) { static malloc_zone_t *z = (malloc_zone_t *)-1; if (z == (malloc_zone_t *)-1) { if (UseInternalZone) { z = malloc_create_zone(vm_page_size, 0); malloc_set_zone_name(z, "ObjC"); } else { z = malloc_default_zone(); } } return z; } /*********************************************************************** * _malloc_internal * _calloc_internal * _realloc_internal * _strdup_internal * _free_internal * Convenience functions for the internal malloc zone. **********************************************************************/ __private_extern__ void *_malloc_internal(size_t size) { return malloc_zone_malloc(_objc_internal_zone(), size); } __private_extern__ void *_calloc_internal(size_t count, size_t size) { return malloc_zone_calloc(_objc_internal_zone(), count, size); } __private_extern__ void *_realloc_internal(void *ptr, size_t size) { return malloc_zone_realloc(_objc_internal_zone(), ptr, size); } __private_extern__ char *_strdup_internal(const char *str) { size_t len = strlen(str); char *dup = malloc_zone_malloc(_objc_internal_zone(), len + 1); memcpy(dup, str, len + 1); return dup; } __private_extern__ void _free_internal(void *ptr) { malloc_zone_free(_objc_internal_zone(), ptr); } /*********************************************************************** * cache collection. **********************************************************************/ static unsigned long _get_pc_for_thread (mach_port_t thread) #ifdef hppa { struct hp_pa_frame_thread_state state; unsigned int count = HPPA_FRAME_THREAD_STATE_COUNT; kern_return_t okay = thread_get_state (thread, HPPA_FRAME_THREAD_STATE, (thread_state_t)&state, &count); return (okay == KERN_SUCCESS) ? state.ts_pcoq_front : PC_SENTINAL; } #elif defined(sparc) { struct sparc_thread_state_regs state; unsigned int count = SPARC_THREAD_STATE_REGS_COUNT; kern_return_t okay = thread_get_state (thread, SPARC_THREAD_STATE_REGS, (thread_state_t)&state, &count); return (okay == KERN_SUCCESS) ? state.regs.r_pc : PC_SENTINAL; } #elif defined(__i386__) || defined(i386) { i386_thread_state_t state; unsigned int count = i386_THREAD_STATE_COUNT; kern_return_t okay = thread_get_state (thread, i386_THREAD_STATE, (thread_state_t)&state, &count); return (okay == KERN_SUCCESS) ? state.eip : PC_SENTINAL; } #elif defined(m68k) { struct m68k_thread_state_regs state; unsigned int count = M68K_THREAD_STATE_REGS_COUNT; kern_return_t okay = thread_get_state (thread, M68K_THREAD_STATE_REGS, (thread_state_t)&state, &count); return (okay == KERN_SUCCESS) ? state.pc : PC_SENTINAL; } #elif defined(__ppc__) || defined(ppc) { struct ppc_thread_state state; unsigned int count = PPC_THREAD_STATE_COUNT; kern_return_t okay = thread_get_state (thread, PPC_THREAD_STATE, (thread_state_t)&state, &count); return (okay == KERN_SUCCESS) ? state.srr0 : PC_SENTINAL; } #else { #error _get_pc_for_thread () not implemented for this architecture } #endif /*********************************************************************** * _collecting_in_critical. * Returns TRUE if some thread is currently executing a cache-reading * function. Collection of cache garbage is not allowed when a cache- * reading function is in progress because it might still be using * the garbage memory. **********************************************************************/ OBJC_EXPORT unsigned long objc_entryPoints[]; OBJC_EXPORT unsigned long objc_exitPoints[]; static int _collecting_in_critical (void) { thread_act_port_array_t threads; unsigned number; unsigned count; kern_return_t ret; int result; mach_port_t mythread = pthread_mach_thread_np(pthread_self()); // Get a list of all the threads in the current task ret = task_threads (mach_task_self (), &threads, &number); if (ret != KERN_SUCCESS) { _objc_fatal("task_thread failed (result %d)\n", ret); } // Check whether any thread is in the cache lookup code result = FALSE; for (count = 0; count < number; count++) { int region; unsigned long pc; // Don't bother checking ourselves if (threads[count] == mythread) continue; // Find out where thread is executing pc = _get_pc_for_thread (threads[count]); // Check for bad status, and if so, assume the worse (can't collect) if (pc == PC_SENTINAL) { result = TRUE; goto done; } // Check whether it is in the cache lookup code for (region = 0; objc_entryPoints[region] != 0; region++) { if ((pc >= objc_entryPoints[region]) && (pc <= objc_exitPoints[region])) { result = TRUE; goto done; } } } done: // Deallocate the port rights for the threads for (count = 0; count < number; count++) { mach_port_deallocate(mach_task_self (), threads[count]); } // Deallocate the thread list vm_deallocate (mach_task_self (), (vm_address_t) threads, sizeof(threads) * number); // Return our finding return result; } /*********************************************************************** * _garbage_make_room. Ensure that there is enough room for at least * one more ref in the garbage. **********************************************************************/ // amount of memory represented by all refs in the garbage static int garbage_byte_size = 0; // do not empty the garbage until garbage_byte_size gets at least this big static int garbage_threshold = 1024; // table of refs to free static void **garbage_refs = 0; // current number of refs in garbage_refs static int garbage_count = 0; // capacity of current garbage_refs static int garbage_max = 0; // capacity of initial garbage_refs enum { INIT_GARBAGE_COUNT = 128 }; static void _garbage_make_room (void) { static int first = 1; volatile void * tempGarbage; // Create the collection table the first time it is needed if (first) { first = 0; garbage_refs = _malloc_internal(INIT_GARBAGE_COUNT * sizeof(void *)); garbage_max = INIT_GARBAGE_COUNT; } // Double the table if it is full else if (garbage_count == garbage_max) { tempGarbage = _realloc_internal(garbage_refs, garbage_max * 2 * sizeof(void *)); garbage_refs = (void **) tempGarbage; garbage_max *= 2; } } /*********************************************************************** * _cache_collect_free. Add the specified malloc'd memory to the list * of them to free at some later point. * size is used for the collection threshold. It does not have to be * precisely the block's size. * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ static void _cache_collect_free(void *data, size_t size, BOOL tryCollect) { static char *report_garbage = (char *)0xffffffff; if ((char *)0xffffffff == report_garbage) { // Check whether to log our activity report_garbage = getenv ("OBJC_REPORT_GARBAGE"); } // Insert new element in garbage list // Note that we do this even if we end up free'ing everything _garbage_make_room (); garbage_byte_size += size; garbage_refs[garbage_count++] = data; // Log our progress if (tryCollect && report_garbage) _objc_inform ("total of %d bytes of garbage ...", garbage_byte_size); // Done if caller says not to empty or the garbage is not full if (!tryCollect || (garbage_byte_size < garbage_threshold)) { if (tryCollect && report_garbage) _objc_inform ("couldn't collect cache garbage: below threshold\n"); return; } // tryCollect is guaranteed to be true after this point // Synchronize garbage collection with objc_msgSend and other cache readers if (!_collecting_in_critical ()) { // No cache readers in progress - garbage is now deletable // Log our progress if (report_garbage) _objc_inform ("collecting!\n"); // Dispose all refs now in the garbage while (garbage_count--) { if (cache_allocator_is_block(garbage_refs[garbage_count])) { cache_allocator_free(garbage_refs[garbage_count]); } else { free(garbage_refs[garbage_count]); } } // Clear the garbage count and total size indicator garbage_count = 0; garbage_byte_size = 0; } else { // objc_msgSend (or other cache reader) is currently looking in the // cache and might still be using some garbage. if (report_garbage) { _objc_inform ("couldn't collect cache garbage: objc_msgSend in progress\n"); } } } /*********************************************************************** * Custom method cache allocator. * Method cache block sizes are 2^slots+2 words, which is a pessimal * case for the system allocator. It wastes 504 bytes per cache block * with 128 or more slots, which adds up to tens of KB for an AppKit process. * To save memory, the custom cache allocator below is used. * * The cache allocator uses 128 KB allocation regions. Few processes will * require a second region. Within a region, allocation is address-ordered * first fit. * * The cache allocator uses a quantum of 520. * Cache block ideal sizes: 520, 1032, 2056, 4104 * Cache allocator sizes: 520, 1040, 2080, 4160 * * Because all blocks are known to be genuine method caches, the ordinary * cache->mask and cache->occupied fields are used as block headers. * No out-of-band headers are maintained. The number of blocks will * almost always be fewer than 200, so for simplicity there is no free * list or other optimization. * * Block in use: mask != 0, occupied != -1 (mask indicates block size) * Block free: mask != 0, occupied == -1 (mask is precisely block size) * * No cache allocator functions take any locks. Instead, the caller * must hold the cacheUpdateLock. **********************************************************************/ typedef struct cache_allocator_block { unsigned int size; unsigned int state; struct cache_allocator_block *nextFree; } cache_allocator_block; typedef struct cache_allocator_region { cache_allocator_block *start; cache_allocator_block *end; // first non-block address cache_allocator_block *freeList; struct cache_allocator_region *next; } cache_allocator_region; static cache_allocator_region *cacheRegion = NULL; static unsigned int cache_allocator_mask_for_size(size_t size) { return (size - sizeof(struct objc_cache)) / sizeof(Method); } static size_t cache_allocator_size_for_mask(unsigned int mask) { size_t requested = sizeof(struct objc_cache) + TABLE_SIZE(mask+1); size_t actual = CACHE_QUANTUM; while (actual < requested) actual += CACHE_QUANTUM; return actual; } /*********************************************************************** * cache_allocator_add_region * Allocates and returns a new region that can hold at least size * bytes of large method caches. * The actual size will be rounded up to a CACHE_QUANTUM boundary, * with a minimum of CACHE_REGION_SIZE. * The new region is lowest-priority for new allocations. Callers that * know the other regions are already full should allocate directly * into the returned region. **********************************************************************/ static cache_allocator_region *cache_allocator_add_region(size_t size) { vm_address_t addr; cache_allocator_block *b; cache_allocator_region **rgnP; cache_allocator_region *newRegion = _calloc_internal(1, sizeof(cache_allocator_region)); // Round size up to quantum boundary, and apply the minimum size. size += CACHE_QUANTUM - (size % CACHE_QUANTUM); if (size < CACHE_REGION_SIZE) size = CACHE_REGION_SIZE; // Allocate the region addr = 0; vm_allocate(mach_task_self(), &addr, size, 1); newRegion->start = (cache_allocator_block *)addr; newRegion->end = (cache_allocator_block *)(addr + size); // Mark the first block: free and covers the entire region b = newRegion->start; b->size = size; b->state = (unsigned int)-1; b->nextFree = NULL; newRegion->freeList = b; // Add to end of the linked list of regions. // Other regions should be re-used before this one is touched. newRegion->next = NULL; rgnP = &cacheRegion; while (*rgnP) { rgnP = &(**rgnP).next; } *rgnP = newRegion; return newRegion; } /*********************************************************************** * cache_allocator_coalesce * Attempts to coalesce a free block with the single free block following * it in the free list, if any. **********************************************************************/ static void cache_allocator_coalesce(cache_allocator_block *block) { if (block->size + (uintptr_t)block == (uintptr_t)block->nextFree) { block->size += block->nextFree->size; block->nextFree = block->nextFree->nextFree; } } /*********************************************************************** * cache_region_calloc * Attempt to allocate a size-byte block in the given region. * Allocation is first-fit. The free list is already fully coalesced. * Returns NULL if there is not enough room in the region for the block. **********************************************************************/ static void *cache_region_calloc(cache_allocator_region *rgn, size_t size) { cache_allocator_block **blockP; unsigned int mask; // Save mask for allocated block, then round size // up to CACHE_QUANTUM boundary mask = cache_allocator_mask_for_size(size); size = cache_allocator_size_for_mask(mask); // Search the free list for a sufficiently large free block. for (blockP = &rgn->freeList; *blockP != NULL; blockP = &(**blockP).nextFree) { cache_allocator_block *block = *blockP; if (block->size < size) continue; // not big enough // block is now big enough. Allocate from it. // Slice off unneeded fragment of block, if any, // and reconnect the free list around block. if (block->size - size >= CACHE_QUANTUM) { cache_allocator_block *leftover = (cache_allocator_block *)(size + (uintptr_t)block); leftover->size = block->size - size; leftover->state = (unsigned int)-1; leftover->nextFree = block->nextFree; *blockP = leftover; } else { *blockP = block->nextFree; } // block is now exactly the right size. bzero(block, size); block->size = mask; // Cache->mask block->state = 0; // Cache->occupied return block; } // No room in this region. return NULL; } /*********************************************************************** * cache_allocator_calloc * Custom allocator for large method caches (128+ slots) * The returned cache block already has cache->mask set. * cache->occupied and the cache contents are zero. * Cache locks: cacheUpdateLock must be held by the caller **********************************************************************/ static void *cache_allocator_calloc(size_t size) { cache_allocator_region *rgn; for (rgn = cacheRegion; rgn != NULL; rgn = rgn->next) { void *p = cache_region_calloc(rgn, size); if (p) { return p; } } // No regions or all regions full - make a region and try one more time // In the unlikely case of a cache over 256KB, it will get its own region. return cache_region_calloc(cache_allocator_add_region(size), size); } /*********************************************************************** * cache_allocator_region_for_block * Returns the cache allocator region that ptr points into, or NULL. **********************************************************************/ static cache_allocator_region *cache_allocator_region_for_block(cache_allocator_block *block) { cache_allocator_region *rgn; for (rgn = cacheRegion; rgn != NULL; rgn = rgn->next) { if (block >= rgn->start && block < rgn->end) return rgn; } return NULL; } /*********************************************************************** * cache_allocator_is_block * If ptr is a live block from the cache allocator, return YES * If ptr is a block from some other allocator, return NO. * If ptr is a dead block from the cache allocator, result is undefined. * Cache locks: cacheUpdateLock must be held by the caller **********************************************************************/ static BOOL cache_allocator_is_block(void *ptr) { return (cache_allocator_region_for_block((cache_allocator_block *)ptr) != NULL); } /*********************************************************************** * cache_allocator_free * Frees a block allocated by the cache allocator. * Cache locks: cacheUpdateLock must be held by the caller. **********************************************************************/ static void cache_allocator_free(void *ptr) { cache_allocator_block *dead = (cache_allocator_block *)ptr; cache_allocator_block *cur; cache_allocator_region *rgn; if (! (rgn = cache_allocator_region_for_block(ptr))) { // free of non-pointer _objc_inform("cache_allocator_free of non-pointer %p", ptr); return; } dead->size = cache_allocator_size_for_mask(dead->size); dead->state = (unsigned int)-1; if (!rgn->freeList || rgn->freeList > dead) { // dead block belongs at front of free list dead->nextFree = rgn->freeList; rgn->freeList = dead; cache_allocator_coalesce(dead); return; } // dead block belongs in the middle or end of free list for (cur = rgn->freeList; cur != NULL; cur = cur->nextFree) { cache_allocator_block *ahead = cur->nextFree; if (!ahead || ahead > dead) { // cur and ahead straddle dead, OR dead belongs at end of free list cur->nextFree = dead; dead->nextFree = ahead; // coalesce into dead first in case both succeed cache_allocator_coalesce(dead); cache_allocator_coalesce(cur); return; } } // uh-oh _objc_inform("cache_allocator_free of non-pointer %p", ptr); } /*********************************************************************** * _cache_print. **********************************************************************/ static void _cache_print (Cache cache) { unsigned int index; unsigned int count; count = cache->mask + 1; for (index = 0; index < count; index += 1) if (CACHE_BUCKET_VALID(cache->buckets[index])) { if (CACHE_BUCKET_IMP(cache->buckets[index]) == &_objc_msgForward) printf ("does not recognize: \n"); printf ("%s\n", (const char *) CACHE_BUCKET_NAME(cache->buckets[index])); } } /*********************************************************************** * _class_printMethodCaches. **********************************************************************/ void _class_printMethodCaches (Class cls) { if (((struct objc_class *)cls)->cache == &emptyCache) printf ("no instance-method cache for class %s\n", ((struct objc_class *)cls)->name); else { printf ("instance-method cache for class %s:\n", ((struct objc_class *)cls)->name); _cache_print (((struct objc_class *)cls)->cache); } if (((struct objc_class * )((struct objc_class * )cls)->isa)->cache == &emptyCache) printf ("no class-method cache for class %s\n", ((struct objc_class *)cls)->name); else { printf ("class-method cache for class %s:\n", ((struct objc_class *)cls)->name); _cache_print (((struct objc_class * )((struct objc_class * )cls)->isa)->cache); } } /*********************************************************************** * log2. **********************************************************************/ static unsigned int log2 (unsigned int x) { unsigned int log; log = 0; while (x >>= 1) log += 1; return log; } /*********************************************************************** * _class_printDuplicateCacheEntries. **********************************************************************/ void _class_printDuplicateCacheEntries (BOOL detail) { NXHashTable * class_hash; NXHashState state; struct objc_class * cls; unsigned int duplicates; unsigned int index1; unsigned int index2; unsigned int mask; unsigned int count; unsigned int isMeta; Cache cache; printf ("Checking for duplicate cache entries \n"); // Outermost loop - iterate over all classes class_hash = objc_getClasses (); state = NXInitHashState (class_hash); duplicates = 0; while (NXNextHashState (class_hash, &state, (void **) &cls)) { // Control loop - do given class' cache, then its isa's cache for (isMeta = 0; isMeta <= 1; isMeta += 1) { // Select cache of interest and make sure it exists cache = isMeta ? cls->isa->cache : ((struct objc_class *)cls)->cache; if (cache == &emptyCache) continue; // Middle loop - check each entry in the given cache mask = cache->mask; count = mask + 1; for (index1 = 0; index1 < count; index1 += 1) { // Skip invalid entry if (!CACHE_BUCKET_VALID(cache->buckets[index1])) continue; // Inner loop - check that given entry matches no later entry for (index2 = index1 + 1; index2 < count; index2 += 1) { // Skip invalid entry if (!CACHE_BUCKET_VALID(cache->buckets[index2])) continue; // Check for duplication by method name comparison if (strcmp ((char *) CACHE_BUCKET_NAME(cache->buckets[index1]), (char *) CACHE_BUCKET_NAME(cache->buckets[index2])) == 0) { if (detail) printf ("%s %s\n", ((struct objc_class *)cls)->name, (char *) CACHE_BUCKET_NAME(cache->buckets[index1])); duplicates += 1; break; } } } } } // Log the findings printf ("duplicates = %d\n", duplicates); printf ("total cache fills = %d\n", totalCacheFills); } /*********************************************************************** * PrintCacheHeader. **********************************************************************/ static void PrintCacheHeader (void) { #ifdef OBJC_INSTRUMENTED printf ("Cache Cache Slots Avg Max AvgS MaxS AvgS MaxS TotalD AvgD MaxD TotalD AvgD MaxD TotD AvgD MaxD\n"); printf ("Size Count Used Used Used Hit Hit Miss Miss Hits Prbs Prbs Misses Prbs Prbs Flsh Flsh Flsh\n"); printf ("----- ----- ----- ----- ---- ---- ---- ---- ---- ------- ---- ---- ------- ---- ---- ---- ---- ----\n"); #else printf ("Cache Cache Slots Avg Max AvgS MaxS AvgS MaxS\n"); printf ("Size Count Used Used Used Hit Hit Miss Miss\n"); printf ("----- ----- ----- ----- ---- ---- ---- ---- ----\n"); #endif } /*********************************************************************** * PrintCacheInfo. **********************************************************************/ static void PrintCacheInfo (unsigned int cacheSize, unsigned int cacheCount, unsigned int slotsUsed, float avgUsed, unsigned int maxUsed, float avgSHit, unsigned int maxSHit, float avgSMiss, unsigned int maxSMiss #ifdef OBJC_INSTRUMENTED , unsigned int totDHits, float avgDHit, unsigned int maxDHit, unsigned int totDMisses, float avgDMiss, unsigned int maxDMiss, unsigned int totDFlsh, float avgDFlsh, unsigned int maxDFlsh #endif ) { #ifdef OBJC_INSTRUMENTED printf ("%5u %5u %5u %5.1f %4u %4.1f %4u %4.1f %4u %7u %4.1f %4u %7u %4.1f %4u %4u %4.1f %4u\n", #else printf ("%5u %5u %5u %5.1f %4u %4.1f %4u %4.1f %4u\n", #endif cacheSize, cacheCount, slotsUsed, avgUsed, maxUsed, avgSHit, maxSHit, avgSMiss, maxSMiss #ifdef OBJC_INSTRUMENTED , totDHits, avgDHit, maxDHit, totDMisses, avgDMiss, maxDMiss, totDFlsh, avgDFlsh, maxDFlsh #endif ); } #ifdef OBJC_INSTRUMENTED /*********************************************************************** * PrintCacheHistogram. Show the non-zero entries from the specified * cache histogram. **********************************************************************/ static void PrintCacheHistogram (char * title, unsigned int * firstEntry, unsigned int entryCount) { unsigned int index; unsigned int * thisEntry; printf ("%s\n", title); printf (" Probes Tally\n"); printf (" ------ -----\n"); for (index = 0, thisEntry = firstEntry; index < entryCount; index += 1, thisEntry += 1) { if (*thisEntry == 0) continue; printf (" %6d %5d\n", index, *thisEntry); } } #endif /*********************************************************************** * _class_printMethodCacheStatistics. **********************************************************************/ #define MAX_LOG2_SIZE 32 #define MAX_CHAIN_SIZE 100 void _class_printMethodCacheStatistics (void) { unsigned int isMeta; unsigned int index; NXHashTable * class_hash; NXHashState state; struct objc_class * cls; unsigned int totalChain; unsigned int totalMissChain; unsigned int maxChain; unsigned int maxMissChain; unsigned int classCount; unsigned int negativeEntryCount; unsigned int cacheExpandCount; unsigned int cacheCountBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int totalEntriesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxEntriesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int totalChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int totalMissChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int totalMaxChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int totalMaxMissChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxMissChainBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int chainCount[MAX_CHAIN_SIZE] = {0}; unsigned int missChainCount[MAX_CHAIN_SIZE] = {0}; #ifdef OBJC_INSTRUMENTED unsigned int hitCountBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int hitProbesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxHitProbesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int missCountBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int missProbesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxMissProbesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int flushCountBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int flushedEntriesBySize[2][MAX_LOG2_SIZE] = {{0}}; unsigned int maxFlushedEntriesBySize[2][MAX_LOG2_SIZE] = {{0}}; #endif printf ("Printing cache statistics\n"); // Outermost loop - iterate over all classes class_hash = objc_getClasses (); state = NXInitHashState (class_hash); classCount = 0; negativeEntryCount = 0; cacheExpandCount = 0; while (NXNextHashState (class_hash, &state, (void **) &cls)) { // Tally classes classCount += 1; // Control loop - do given class' cache, then its isa's cache for (isMeta = 0; isMeta <= 1; isMeta += 1) { Cache cache; unsigned int mask; unsigned int log2Size; unsigned int entryCount; // Select cache of interest cache = isMeta ? cls->isa->cache : ((struct objc_class *)cls)->cache; // Ignore empty cache... should we? if (cache == &emptyCache) continue; // Middle loop - do each entry in the given cache mask = cache->mask; entryCount = 0; totalChain = 0; totalMissChain = 0; maxChain = 0; maxMissChain = 0; for (index = 0; index < mask + 1; index += 1) { Method * buckets; Method method; uarith_t hash; uarith_t methodChain; uarith_t methodMissChain; uarith_t index2; // If entry is invalid, the only item of // interest is that future insert hashes // to this entry can use it directly. buckets = cache->buckets; if (!CACHE_BUCKET_VALID(buckets[index])) { missChainCount[0] += 1; continue; } method = buckets[index]; // Tally valid entries entryCount += 1; // Tally "forward::" entries if (CACHE_BUCKET_IMP(method) == &_objc_msgForward) negativeEntryCount += 1; // Calculate search distance (chain length) for this method // The chain may wrap around to the beginning of the table. hash = CACHE_HASH(CACHE_BUCKET_NAME(method), mask); if (index >= hash) methodChain = index - hash; else methodChain = (mask+1) + index - hash; // Tally chains of this length if (methodChain < MAX_CHAIN_SIZE) chainCount[methodChain] += 1; // Keep sum of all chain lengths totalChain += methodChain; // Record greatest chain length if (methodChain > maxChain) maxChain = methodChain; // Calculate search distance for miss that hashes here index2 = index; while (CACHE_BUCKET_VALID(buckets[index2])) { index2 += 1; index2 &= mask; } methodMissChain = ((index2 - index) & mask); // Tally miss chains of this length if (methodMissChain < MAX_CHAIN_SIZE) missChainCount[methodMissChain] += 1; // Keep sum of all miss chain lengths in this class totalMissChain += methodMissChain; // Record greatest miss chain length if (methodMissChain > maxMissChain) maxMissChain = methodMissChain; } // Factor this cache into statistics about caches of the same // type and size (all caches are a power of two in size) log2Size = log2 (mask + 1); cacheCountBySize[isMeta][log2Size] += 1; totalEntriesBySize[isMeta][log2Size] += entryCount; if (entryCount > maxEntriesBySize[isMeta][log2Size]) maxEntriesBySize[isMeta][log2Size] = entryCount; totalChainBySize[isMeta][log2Size] += totalChain; totalMissChainBySize[isMeta][log2Size] += totalMissChain; totalMaxChainBySize[isMeta][log2Size] += maxChain; totalMaxMissChainBySize[isMeta][log2Size] += maxMissChain; if (maxChain > maxChainBySize[isMeta][log2Size]) maxChainBySize[isMeta][log2Size] = maxChain; if (maxMissChain > maxMissChainBySize[isMeta][log2Size]) maxMissChainBySize[isMeta][log2Size] = maxMissChain; #ifdef OBJC_INSTRUMENTED { CacheInstrumentation * cacheData; cacheData = CACHE_INSTRUMENTATION(cache); hitCountBySize[isMeta][log2Size] += cacheData->hitCount; hitProbesBySize[isMeta][log2Size] += cacheData->hitProbes; if (cacheData->maxHitProbes > maxHitProbesBySize[isMeta][log2Size]) maxHitProbesBySize[isMeta][log2Size] = cacheData->maxHitProbes; missCountBySize[isMeta][log2Size] += cacheData->missCount; missProbesBySize[isMeta][log2Size] += cacheData->missProbes; if (cacheData->maxMissProbes > maxMissProbesBySize[isMeta][log2Size]) maxMissProbesBySize[isMeta][log2Size] = cacheData->maxMissProbes; flushCountBySize[isMeta][log2Size] += cacheData->flushCount; flushedEntriesBySize[isMeta][log2Size] += cacheData->flushedEntries; if (cacheData->maxFlushedEntries > maxFlushedEntriesBySize[isMeta][log2Size]) maxFlushedEntriesBySize[isMeta][log2Size] = cacheData->maxFlushedEntries; } #endif // Caches start with a power of two number of entries, and grow by doubling, so // we can calculate the number of times this cache has expanded if (isMeta) cacheExpandCount += log2Size - INIT_META_CACHE_SIZE_LOG2; else cacheExpandCount += log2Size - INIT_CACHE_SIZE_LOG2; } } { unsigned int cacheCountByType[2] = {0}; unsigned int totalCacheCount = 0; unsigned int totalEntries = 0; unsigned int maxEntries = 0; unsigned int totalSlots = 0; #ifdef OBJC_INSTRUMENTED unsigned int totalHitCount = 0; unsigned int totalHitProbes = 0; unsigned int maxHitProbes = 0; unsigned int totalMissCount = 0; unsigned int totalMissProbes = 0; unsigned int maxMissProbes = 0; unsigned int totalFlushCount = 0; unsigned int totalFlushedEntries = 0; unsigned int maxFlushedEntries = 0; #endif totalChain = 0; maxChain = 0; totalMissChain = 0; maxMissChain = 0; // Sum information over all caches for (isMeta = 0; isMeta <= 1; isMeta += 1) { for (index = 0; index < MAX_LOG2_SIZE; index += 1) { cacheCountByType[isMeta] += cacheCountBySize[isMeta][index]; totalEntries += totalEntriesBySize[isMeta][index]; totalSlots += cacheCountBySize[isMeta][index] * (1 << index); totalChain += totalChainBySize[isMeta][index]; if (maxEntriesBySize[isMeta][index] > maxEntries) maxEntries = maxEntriesBySize[isMeta][index]; if (maxChainBySize[isMeta][index] > maxChain) maxChain = maxChainBySize[isMeta][index]; totalMissChain += totalMissChainBySize[isMeta][index]; if (maxMissChainBySize[isMeta][index] > maxMissChain) maxMissChain = maxMissChainBySize[isMeta][index]; #ifdef OBJC_INSTRUMENTED totalHitCount += hitCountBySize[isMeta][index]; totalHitProbes += hitProbesBySize[isMeta][index]; if (maxHitProbesBySize[isMeta][index] > maxHitProbes) maxHitProbes = maxHitProbesBySize[isMeta][index]; totalMissCount += missCountBySize[isMeta][index]; totalMissProbes += missProbesBySize[isMeta][index]; if (maxMissProbesBySize[isMeta][index] > maxMissProbes) maxMissProbes = maxMissProbesBySize[isMeta][index]; totalFlushCount += flushCountBySize[isMeta][index]; totalFlushedEntries += flushedEntriesBySize[isMeta][index]; if (maxFlushedEntriesBySize[isMeta][index] > maxFlushedEntries) maxFlushedEntries = maxFlushedEntriesBySize[isMeta][index]; #endif } totalCacheCount += cacheCountByType[isMeta]; } // Log our findings printf ("There are %u classes\n", classCount); for (isMeta = 0; isMeta <= 1; isMeta += 1) { // Number of this type of class printf ("\nThere are %u %s-method caches, broken down by size (slot count):\n", cacheCountByType[isMeta], isMeta ? "class" : "instance"); // Print header PrintCacheHeader (); // Keep format consistent even if there are caches of this kind if (cacheCountByType[isMeta] == 0) { printf ("(none)\n"); continue; } // Usage information by cache size for (index = 0; index < MAX_LOG2_SIZE; index += 1) { unsigned int cacheCount; unsigned int cacheSlotCount; unsigned int cacheEntryCount; // Get number of caches of this type and size cacheCount = cacheCountBySize[isMeta][index]; if (cacheCount == 0) continue; // Get the cache slot count and the total number of valid entries cacheSlotCount = (1 << index); cacheEntryCount = totalEntriesBySize[isMeta][index]; // Give the analysis PrintCacheInfo (cacheSlotCount, cacheCount, cacheEntryCount, (float) cacheEntryCount / (float) cacheCount, maxEntriesBySize[isMeta][index], (float) totalChainBySize[isMeta][index] / (float) cacheEntryCount, maxChainBySize[isMeta][index], (float) totalMissChainBySize[isMeta][index] / (float) (cacheCount * cacheSlotCount), maxMissChainBySize[isMeta][index] #ifdef OBJC_INSTRUMENTED , hitCountBySize[isMeta][index], hitCountBySize[isMeta][index] ? (float) hitProbesBySize[isMeta][index] / (float) hitCountBySize[isMeta][index] : 0.0, maxHitProbesBySize[isMeta][index], missCountBySize[isMeta][index], missCountBySize[isMeta][index] ? (float) missProbesBySize[isMeta][index] / (float) missCountBySize[isMeta][index] : 0.0, maxMissProbesBySize[isMeta][index], flushCountBySize[isMeta][index], flushCountBySize[isMeta][index] ? (float) flushedEntriesBySize[isMeta][index] / (float) flushCountBySize[isMeta][index] : 0.0, maxFlushedEntriesBySize[isMeta][index] #endif ); } } // Give overall numbers printf ("\nCumulative:\n"); PrintCacheHeader (); PrintCacheInfo (totalSlots, totalCacheCount, totalEntries, (float) totalEntries / (float) totalCacheCount, maxEntries, (float) totalChain / (float) totalEntries, maxChain, (float) totalMissChain / (float) totalSlots, maxMissChain #ifdef OBJC_INSTRUMENTED , totalHitCount, totalHitCount ? (float) totalHitProbes / (float) totalHitCount : 0.0, maxHitProbes, totalMissCount, totalMissCount ? (float) totalMissProbes / (float) totalMissCount : 0.0, maxMissProbes, totalFlushCount, totalFlushCount ? (float) totalFlushedEntries / (float) totalFlushCount : 0.0, maxFlushedEntries #endif ); printf ("\nNumber of \"forward::\" entries: %d\n", negativeEntryCount); printf ("Number of cache expansions: %d\n", cacheExpandCount); #ifdef OBJC_INSTRUMENTED printf ("flush_caches: total calls total visits average visits max visits total classes visits/class\n"); printf (" ----------- ------------ -------------- ---------- ------------- -------------\n"); printf (" linear %11u %12u %14.1f %10u %13u %12.2f\n", LinearFlushCachesCount, LinearFlushCachesVisitedCount, LinearFlushCachesCount ? (float) LinearFlushCachesVisitedCount / (float) LinearFlushCachesCount : 0.0, MaxLinearFlushCachesVisitedCount, LinearFlushCachesVisitedCount, 1.0); printf (" nonlinear %11u %12u %14.1f %10u %13u %12.2f\n", NonlinearFlushCachesCount, NonlinearFlushCachesVisitedCount, NonlinearFlushCachesCount ? (float) NonlinearFlushCachesVisitedCount / (float) NonlinearFlushCachesCount : 0.0, MaxNonlinearFlushCachesVisitedCount, NonlinearFlushCachesClassCount, NonlinearFlushCachesClassCount ? (float) NonlinearFlushCachesVisitedCount / (float) NonlinearFlushCachesClassCount : 0.0); printf (" ideal %11u %12u %14.1f %10u %13u %12.2f\n", LinearFlushCachesCount + NonlinearFlushCachesCount, IdealFlushCachesCount, LinearFlushCachesCount + NonlinearFlushCachesCount ? (float) IdealFlushCachesCount / (float) (LinearFlushCachesCount + NonlinearFlushCachesCount) : 0.0, MaxIdealFlushCachesCount, LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount, LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount ? (float) IdealFlushCachesCount / (float) (LinearFlushCachesVisitedCount + NonlinearFlushCachesClassCount) : 0.0); PrintCacheHistogram ("\nCache hit histogram:", &CacheHitHistogram[0], CACHE_HISTOGRAM_SIZE); PrintCacheHistogram ("\nCache miss histogram:", &CacheMissHistogram[0], CACHE_HISTOGRAM_SIZE); #endif #if 0 printf ("\nLookup chains:"); for (index = 0; index < MAX_CHAIN_SIZE; index += 1) { if (chainCount[index] != 0) printf (" %u:%u", index, chainCount[index]); } printf ("\nMiss chains:"); for (index = 0; index < MAX_CHAIN_SIZE; index += 1) { if (missChainCount[index] != 0) printf (" %u:%u", index, missChainCount[index]); } printf ("\nTotal memory usage for cache data structures: %lu bytes\n", totalCacheCount * (sizeof(struct objc_cache) - sizeof(Method)) + totalSlots * sizeof(Method) + negativeEntryCount * sizeof(struct objc_method)); #endif } } /*********************************************************************** * checkUniqueness. **********************************************************************/ void checkUniqueness (SEL s1, SEL s2) { if (s1 == s2) return; if (s1 && s2 && (strcmp ((const char *) s1, (const char *) s2) == 0)) _objc_inform ("%p != %p but !strcmp (%s, %s)\n", s1, s2, (char *) s1, (char *) s2); }