/* * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * Portions Copyright (c) 1999 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 1.1 (the "License"). You may not use this file * except in compliance with the License. Please obtain a copy of the * License at http://www.apple.com/publicsource 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 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 **********************************************************************/ /*********************************************************************** * Imports. **********************************************************************/ #ifdef __MACH__ #import #include #include #endif #ifdef WIN32 #include #include #include #else #include #include #include #include #ifdef __svr4__ #include #else #include #endif #endif #if defined(__svr4__) || defined(__hpux__) || defined(hpux) #import #endif #import #import #import "objc-private.h" #import "hashtable2.h" #import "maptable.h" #include #include // Needed functions not in any header file size_t malloc_size (const void * ptr); // Needed kernel interface #import #ifdef __MACH__ #import #endif // This is currently disabled in this file, because it is called a LOT here; turn it on when needed. #if 0 && defined(__MACH__) extern int ptrace(int, int, int, int); // ObjC is assigned the range 0xb000 - 0xbfff for first parameter; this file 0xb300-0xb3ff #else #define ptrace(a, b, c, d) do {} while (0) #endif /*********************************************************************** * 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 //#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)) // Class state #define ISCLASS(cls) ((((struct objc_class *) cls)->info & CLS_CLASS) != 0) #define ISMETA(cls) ((((struct objc_class *) cls)->info & CLS_META) != 0) #define GETMETA(cls) (ISMETA(cls) ? ((struct objc_class *) cls) : ((struct objc_class *) cls)->isa) #define ISINITIALIZED(cls) ((GETMETA(cls)->info & CLS_INITIALIZED) != 0) #define MARKINITIALIZED(cls) (GETMETA(cls)->info |= CLS_INITIALIZED) /*********************************************************************** * 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 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 clsDesc); static void * objc_malloc (int byteCount); static Cache _cache_expand (Class cls); static int LogObjCMessageSend (BOOL isClassMethod, const char * objectsClass, const char * implementingClass, SEL selector); static void _cache_fill (Class cls, Method smt, SEL sel); static void _cache_flush (Class cls); static Method _class_lookupMethod (Class cls, SEL sel); static int SubtypeUntil (const char * type, char end); static const char * SkipFirstType (const char * type); #ifdef OBJC_COLLECTING_CACHE 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, BOOL tryCollect); #endif 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; // Locks for cache access #ifdef OBJC_COLLECTING_CACHE // Held when adding an entry to the cache static OBJC_DECLARE_LOCK(cacheUpdateLock); // Held when freeing memory from garbage static OBJC_DECLARE_LOCK(cacheCollectionLock); #endif // Held when looking in, adding to, or freeing the cache. #ifdef OBJC_COLLECTING_CACHE // For speed, messageLock is not held by the method dispatch code. // Instead the cache freeing code checks thread PCs to ensure no // one is dispatching. messageLock is held, though, during less // time critical operations. #endif OBJC_DECLARE_LOCK(messageLock); CFMutableDictionaryRef _classIMPTables = NULL; // 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. #ifdef OBJC_COLLECTING_CACHE static int traceDuplicates = 0; static int traceDuplicatesVerbose = 0; static int cacheFillDuplicates = 0; #endif #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 = 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. ***********************************************************************/ const struct objc_cache emptyCache = { 0, // mask 0, // occupied { NULL } // buckets }; // 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; } /*********************************************************************** * _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, 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; 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 void _addListIMPsToTable(CFMutableDictionaryRef table, struct objc_method_list *mlist, Class cls, void **iterator) { int i; struct objc_method_list *new_mlist; if (!mlist) return; /* Work from end of list so that categories override */ new_mlist = _class_inlinedNextMethodList(cls, iterator); _addListIMPsToTable(table, new_mlist, cls, iterator); for (i = 0; i < mlist->method_count; i++) { CFDictionarySetValue(table, mlist->method_list[i].method_name, mlist->method_list[i].method_imp); } } static void _addClassIMPsToTable(CFMutableDictionaryRef table, Class cls) { struct objc_method_list *mlist; void *iterator = 0; #ifdef INCLUDE_SUPER_IMPS_IN_IMP_TABLE if (cls->super_class) { /* Do superclass first so subclass overrides */ CFMutableDictionaryRef super_table = CFDictionaryGetValue(_classIMPTables, cls->super_class); if (super_table) { CFIndex cnt; const void **keys, **values, *buffer1[128], *buffer2[128]; cnt = CFDictionaryGetCount(super_table); keys = (cnt <= 128) ? buffer1 : CFAllocatorAllocate(NULL, cnt * sizeof(void *), 0); values = (cnt <= 128) ? buffer2 : CFAllocatorAllocate(NULL, cnt * sizeof(void *), 0); CFDictionaryGetKeysAndValues(super_table, keys, values); while (cnt--) { CFDictionarySetValue(table, keys[cnt], values[cnt]); } if (keys != buffer1) CFAllocatorDeallocate(NULL, keys); if (values != buffer2) CFAllocatorDeallocate(NULL, values); } else { _addClassIMPsToTable(table, cls->super_class); } } #endif mlist = _class_inlinedNextMethodList(cls, &iterator); _addListIMPsToTable(table, mlist, cls, &iterator); } CFMutableDictionaryRef _getClassIMPTable(Class cls) { CFMutableDictionaryRef table; if (NULL == _classIMPTables) { // maps Classes to mutable dictionaries _classIMPTables = CFDictionaryCreateMutable(NULL, 0, NULL, NULL); } table = (CFMutableDictionaryRef)CFDictionaryGetValue(_classIMPTables, cls); // IMP table maps SELs to IMPS if (NULL == table) { table = CFDictionaryCreateMutable(NULL, 0, NULL, NULL); _addClassIMPsToTable(table, cls); CFDictionaryAddValue(_classIMPTables, cls, table); } return table; } 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; } /* These next three functions are the heart of ObjC method lookup. */ 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) { struct objc_method_list *mlist; void *iterator = 0; while ((mlist = _class_inlinedNextMethodList(cls, &iterator))) { Method m = _findMethodInList(mlist, sel); if (m) return m; } return NULL; } static inline Method _getMethod(Class cls, SEL sel) { for (; cls; cls = cls->super_class) { Method m = _findMethodInClass(cls, sel); if (m) return m; } return NULL; } /*********************************************************************** * class_getInstanceMethod. Return the instance method for the * specified class and selector. **********************************************************************/ Method class_getInstanceMethod (Class aClass, SEL aSelector) { // Need both a class and a selector if (!aClass || !aSelector) return NULL; // Go to the class return _getMethod (aClass, aSelector); } /*********************************************************************** * class_getClassMethod. Return the class method for the specified * class and selector. **********************************************************************/ Method class_getClassMethod (Class aClass, SEL aSelector) { // Need both a class and a selector if (!aClass || !aSelector) return NULL; // Go to the class or isa return _getMethod (GETMETA(aClass), aSelector); } /*********************************************************************** * 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 if (cls && !((struct objc_class *) cls)->cache) return; newNumClasses = objc_getClassList((Class *)NULL, 0); while (numClasses < newNumClasses) { numClasses = newNumClasses; classes = realloc(classes, sizeof(Class) * numClasses); newNumClasses = objc_getClassList((Class *)classes, numClasses); } numClasses = newNumClasses; // 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 = ((struct objc_class *) clsObject)->isa; if (cls && metaClsObject && (((struct objc_class *) metaClsObject)->isa != ((struct objc_class *) metaClsObject)->isa)) continue; #ifdef OBJC_INSTRUMENTED subclassCount += 1; #endif // Be careful of classes that do not yet have caches if (((struct objc_class *) clsObject)->cache) _cache_flush (clsObject); if (flush_meta && metaClsObject && ((struct objc_class *) metaClsObject)->cache) _cache_flush (((struct objc_class *) clsObject)->isa); } #ifdef OBJC_INSTRUMENTED LinearFlushCachesVisitedCount += classesVisited; if (classesVisited > MaxLinearFlushCachesVisitedCount) MaxLinearFlushCachesVisitedCount = classesVisited; IdealFlushCachesCount += subclassCount; if (subclassCount > MaxIdealFlushCachesCount) MaxIdealFlushCachesCount = subclassCount; #endif free(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 // Relinquish access to class hash table free(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. * * usage: * void * iterator = 0; * while (class_nextMethodList (cls, &iterator)) {...} **********************************************************************/ OBJC_EXPORT struct objc_method_list * class_nextMethodList (Class cls, void ** it) { return _class_inlinedNextMethodList(cls, it); } /*********************************************************************** * _dummy. **********************************************************************/ void _dummy (void) { (void) class_nextMethodList (Nil, NULL); } /*********************************************************************** * class_addMethods. * * Formerly class_addInstanceMethods () **********************************************************************/ void class_addMethods (Class cls, struct objc_method_list * meths) { // Insert atomically. _objc_insertMethods (meths, &((struct objc_class *) cls)->methodLists); // 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 atomically. _objc_removeMethods (meths, &((struct objc_class *) cls)->methodLists); // 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_create_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_create_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 imposterName[256]; char * imposterNamePtr; NXHashTable * class_hash; NXHashState state; struct objc_class * copy; #ifdef OBJC_CLASS_REFS unsigned int hidx; unsigned int hdrCount; header_info * hdrVector; // Get these now before locking, to minimize impact hdrCount = _objc_headerCount (); hdrVector = _objc_headerVector (NULL); #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) return (Class) [(id) imposter error:_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) return (Class) [(id) imposter error:_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. strcpy (imposterName, "_%"); strcat (imposterName, ((struct objc_class *)original)->name); imposterNamePtr = objc_malloc (strlen (imposterName)+1); strcpy (imposterNamePtr, imposterName); // 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); OBJC_LOCK(&classLock); class_hash = objc_getClasses (); // Remove both the imposter and the original class. NXHashRemove (class_hash, imposter); NXHashRemove (class_hash, original); // 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_create_zone()); memmove(copy, imposter, sizeof(struct objc_class)); NXHashInsert (class_hash, copy); addClassToOriginalClass (imposter, copy); // Mark the imposter as such CLS_SETINFO(((struct objc_class *)imposter), CLS_POSING); CLS_SETINFO(((struct objc_class *)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 (hidx = 0; hidx < hdrCount; hidx += 1) { Class * cls_refs; unsigned int refCount; unsigned int index; // Get refs associated with this header cls_refs = (Class *) _getObjcClassRefs ((headerType *) hdrVector[hidx].mhdr, &refCount); if (!cls_refs || !refCount) continue; // Minor loop - process this header's refs cls_refs = (Class *) ((unsigned long) cls_refs + hdrVector[hidx].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_initialize. Send the 'initialize' message on demand to any * uninitialized class. Force initialization of superclasses first. * * Called only from _class_lookupMethodAndLoadCache (or itself). * * #ifdef OBJC_COLLECTING_CACHE * The messageLock can be in either state. * #else * The messageLock is already assumed to be taken out. * It is temporarily released while the initialize method is sent. * #endif **********************************************************************/ static void class_initialize (Class clsDesc) { struct objc_class * super; // Skip if someone else beat us to it if (ISINITIALIZED(((struct objc_class *)clsDesc))) return; // Force initialization of superclasses first super = ((struct objc_class *)clsDesc)->super_class; if ((super != Nil) && (!ISINITIALIZED(super))) class_initialize (super); // Initializing the super class might have initialized us, // or another thread might have initialized us during this time. if (ISINITIALIZED(((struct objc_class *)clsDesc))) return; // Mark the class initialized so it can receive the "initialize" // message. This solution to the catch-22 is the source of a // bug: the class is able to receive messages *from anyone* now // that it is marked, even though initialization is not complete. MARKINITIALIZED(((struct objc_class *)clsDesc)); #ifndef OBJC_COLLECTING_CACHE // Release the message lock so that messages can be sent. OBJC_UNLOCK(&messageLock); #endif // Send the initialize method. [(id)clsDesc initialize]; #ifndef OBJC_COLLECTING_CACHE // Re-acquire the lock OBJC_LOCK(&messageLock); #endif return; } /*********************************************************************** * _class_install_relationships. Fill in the class pointers of a class * that was loaded before some or all of the classes it needs to point to. * The deal here is that the class pointer fields have been usurped to * hold the string name of the pertinent class. Our job is to look up * the real thing based on those stored names. **********************************************************************/ void _class_install_relationships (Class cls, long version) { struct objc_class * meta; struct objc_class * clstmp; // Get easy access to meta class structure meta = ((struct objc_class *)cls)->isa; // Set version in meta class strucure meta->version = version; // Install superclass based on stored name. No name iff // cls is a root class. if (((struct objc_class *)cls)->super_class) { clstmp = objc_getClass ((const char *) ((struct objc_class *)cls)->super_class); if (!clstmp) { _objc_inform("failed objc_getClass(%s) for %s->super_class", (const char *)((struct objc_class *)cls)->super_class, ((struct objc_class *)cls)->name); goto Error; } ((struct objc_class *)cls)->super_class = clstmp; } // Install meta's isa based on stored name. Meta class isa // pointers always point to the meta class of the root class // (root meta class, too, it points to itself!). clstmp = objc_getClass ((const char *) meta->isa); if (!clstmp) { _objc_inform("failed objc_getClass(%s) for %s->isa->isa", (const char *) meta->isa, ((struct objc_class *)cls)->name); goto Error; } meta->isa = clstmp->isa; // Install meta's superclass based on stored name. No name iff // cls is a root class. if (meta->super_class) { // Locate instance class of super class clstmp = objc_getClass ((const char *) meta->super_class); if (!clstmp) { _objc_inform("failed objc_getClass(%s) for %s->isa->super_class", (const char *)meta->super_class, ((struct objc_class *)cls)->name); goto Error; } // Store meta class of super class meta->super_class = clstmp->isa; } // cls is root, so `tie' the (root) meta class down to its // instance class. This way, class methods can come from // the root instance class. else ((struct objc_class *)meta)->super_class = cls; // Use common static empty cache instead of NULL if (((struct objc_class *)cls)->cache == NULL) ((struct objc_class *)cls)->cache = (Cache) &emptyCache; if (((struct objc_class *)meta)->cache == NULL) ((struct objc_class *)meta)->cache = (Cache) &emptyCache; return; Error: _objc_fatal ("please link appropriate classes in your program"); } /*********************************************************************** * objc_malloc. **********************************************************************/ static void * objc_malloc (int byteCount) { void * space; space = malloc_zone_malloc (_objc_create_zone (), byteCount); if (!space && byteCount) _objc_fatal ("unable to allocate space"); #ifdef WIN32 bzero (space, byteCount); #endif return space; } /*********************************************************************** * class_respondsToMethod. * * Called from -[Object respondsTo:] and +[Object instancesRespondTo:] **********************************************************************/ BOOL class_respondsToMethod (Class cls, SEL sel) { struct objc_class * thisCls; arith_t index; arith_t mask; Method * buckets; Method meth; // No one responds to zero! if (!sel) return NO; // Synchronize access to caches OBJC_LOCK(&messageLock); // Look in the cache of the specified class mask = ((struct objc_class *)cls)->cache->mask; buckets = ((struct objc_class *)cls)->cache->buckets; index = ((uarith_t) sel & mask); while (CACHE_BUCKET_VALID(buckets[index])) { if (CACHE_BUCKET_NAME(buckets[index]) == sel) { if (CACHE_BUCKET_IMP(buckets[index]) == &_objc_msgForward) { OBJC_UNLOCK(&messageLock); return NO; } else { OBJC_UNLOCK(&messageLock); return YES; } } index += 1; index &= mask; } // Handle cache miss meth = _getMethod(cls, sel); if (meth) { OBJC_UNLOCK(&messageLock); _cache_fill (cls, meth, sel); return YES; } // Not implememted. Use _objc_msgForward. { Method smt; smt = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_method)); smt->method_name = sel; smt->method_types = ""; smt->method_imp = &_objc_msgForward; _cache_fill (cls, smt, sel); } OBJC_UNLOCK(&messageLock); return NO; } /*********************************************************************** * class_lookupMethod. * * Called from -[Object methodFor:] and +[Object instanceMethodFor:] **********************************************************************/ IMP class_lookupMethod (Class cls, SEL sel) { Method * buckets; arith_t index; arith_t mask; IMP result; // No one responds to zero! if (!sel) [(id) cls error:_errBadSel, sel]; // Synchronize access to caches OBJC_LOCK(&messageLock); // Scan the cache mask = ((struct objc_class *)cls)->cache->mask; buckets = ((struct objc_class *)cls)->cache->buckets; index = ((unsigned int) sel & mask); while (CACHE_BUCKET_VALID(buckets[index])) { if (CACHE_BUCKET_NAME(buckets[index]) == sel) { result = CACHE_BUCKET_IMP(buckets[index]); OBJC_UNLOCK(&messageLock); return result; } index += 1; index &= mask; } // Handle cache miss result = _class_lookupMethodAndLoadCache (cls, sel); OBJC_UNLOCK(&messageLock); return result; } /*********************************************************************** * class_lookupMethodInMethodList. * * Called from objc-load.m and _objc_callLoads () **********************************************************************/ IMP class_lookupMethodInMethodList (struct objc_method_list * mlist, SEL sel) { Method m = _findMethodInList(mlist, sel); return (m ? m->method_imp : NULL); } IMP class_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_create. * * Called from _cache_expand () and objc_addClass () **********************************************************************/ Cache _cache_create (Class cls) { Cache new_cache; int slotCount; int index; // Select appropriate size slotCount = (ISMETA(cls)) ? INIT_META_CACHE_SIZE : INIT_CACHE_SIZE; // Allocate table (why not check for failure?) #ifdef OBJC_INSTRUMENTED new_cache = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_cache) + TABLE_SIZE(slotCount) + sizeof(CacheInstrumentation)); #else new_cache = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_cache) + TABLE_SIZE(slotCount)); #endif // Invalidate all the buckets for (index = 0; index < slotCount; index += 1) CACHE_BUCKET_VALID(new_cache->buckets[index]) = NULL; // Zero the valid-entry counter new_cache->occupied = 0; // Set the mask so indexing wraps at the end-of-table new_cache->mask = slotCount - 1; #ifdef OBJC_INSTRUMENTED { CacheInstrumentation * cacheData; // Zero out the cache dynamic instrumention data cacheData = CACHE_INSTRUMENTATION(new_cache); bzero ((char *) cacheData, sizeof(CacheInstrumentation)); } #endif // 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. ((struct objc_class * )cls)->info &= ~(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) ((struct objc_class * )cls)->info &= ~(CLS_GROW_CACHE); // Return our creation return new_cache; } /*********************************************************************** * _cache_expand. * * #ifdef OBJC_COLLECTING_CACHE * The cacheUpdateLock is assumed to be taken at this point. * #endif * * Called from _cache_fill () **********************************************************************/ 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) ((struct objc_class * )cls)->info &= ~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) { #ifdef OBJC_COLLECTING_CACHE _cache_collect_free (oldEntry, NO); #else malloc_zone_free (_objc_create_zone(), oldEntry); #endif } } // Set the slow growth flag so the cache is next grown ((struct objc_class * )cls)->info |= CLS_GROW_CACHE; // Return the same old cache, freshly emptied return old_cache; } } // Double the cache size slotCount = (old_cache->mask + 1) << 1; // Allocate a new cache table #ifdef OBJC_INSTRUMENTED new_cache = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_cache) + TABLE_SIZE(slotCount) + sizeof(CacheInstrumentation)); #else new_cache = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_cache) + TABLE_SIZE(slotCount)); #endif // Zero out the new cache new_cache->mask = slotCount - 1; new_cache->occupied = 0; for (index = 0; index < slotCount; index += 1) CACHE_BUCKET_VALID(new_cache->buckets[index]) = NULL; #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 = ((unsigned int) 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. ((struct objc_class * )cls)->info |= 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) { #ifdef OBJC_COLLECTING_CACHE _cache_collect_free (old_cache->buckets[index], NO); #else malloc_zone_free (_objc_create_zone(), old_cache->buckets[index]); #endif } } } // Install new cache ((struct objc_class *)cls)->cache = new_cache; // Deallocate old cache, try freeing all the garbage #ifdef OBJC_COLLECTING_CACHE _cache_collect_free (old_cache, YES); #else malloc_zone_free (_objc_create_zone(), old_cache); #endif 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)) { sprintf (buf, "/tmp/msgSends-%d", (int) getpid ()); objcMsgLogFD = open (buf, O_WRONLY | O_CREAT, 0666); } // Make the log entry sprintf(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. * * Called only from _class_lookupMethodAndLoadCache and * class_respondsToMethod. * * #ifdef OBJC_COLLECTING_CACHE * It doesn't matter if someone has the messageLock when we enter this * function. This function will fail to do the update if someone else * is already updating the cache, i.e. they have the cacheUpdateLock. * #else * The messageLock is already assumed to be taken out. * #endif **********************************************************************/ static void _cache_fill (Class cls, Method smt, SEL sel) { Cache cache; Method * buckets; arith_t index; arith_t mask; unsigned int newOccupied; // Keep tally of cache additions totalCacheFills += 1; #ifdef OBJC_COLLECTING_CACHE // Make sure only one thread is updating the cache at a time, but don't // wait for concurrent updater to finish, because it might be a while, or // a deadlock! Instead, just leave the method out of the cache until // next time. This is nasty given that cacheUpdateLock is per task! if (!OBJC_TRYLOCK(&cacheUpdateLock)) return; // Set up invariants for cache traversals cache = ((struct objc_class *)cls)->cache; mask = cache->mask; buckets = cache->buckets; // Check for duplicate entries, if we're in the mode if (traceDuplicates) { int index2; // 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); } } } // Do nothing if entry is already placed. This re-check is needed // only in the OBJC_COLLECTING_CACHE code, because the probe is // done un-sync'd. index = ((unsigned int) sel & mask); while (CACHE_BUCKET_VALID(buckets[index])) { if (CACHE_BUCKET_NAME(buckets[index]) == sel) { OBJC_UNLOCK(&cacheUpdateLock); return; } index += 1; index &= mask; } #else // not OBJC_COLLECTING_CACHE cache = ((struct objc_class *)cls)->cache; mask = cache->mask; #endif // Use the cache as-is if it is less than 3/4 full newOccupied = cache->occupied + 1; if ((newOccupied * 4) <= (mask + 1) * 3) cache->occupied = newOccupied; // Cache is getting full else { // Flush the cache if ((((struct objc_class * )cls)->info & CLS_FLUSH_CACHE) != 0) _cache_flush (cls); // Expand the cache else { cache = _cache_expand (cls); mask = cache->mask; } // 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 = ((unsigned int) sel & 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 &= mask; } #ifdef OBJC_COLLECTING_CACHE OBJC_UNLOCK(&cacheUpdateLock); #endif } /*********************************************************************** * _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 (). **********************************************************************/ static void _cache_flush (Class cls) { Cache cache; unsigned int index; // Locate cache. Ignore unused cache. cache = ((struct objc_class *)cls)->cache; if (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) #ifdef OBJC_COLLECTING_CACHE _cache_collect_free (oldEntry, NO); #else malloc_zone_free (_objc_create_zone(), oldEntry); #endif } // 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. ((struct objc_class * )cls)->info &= ~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; } /*********************************************************************** * _class_lookupMethodAndLoadCache. * * Called only from objc_msgSend, objc_msgSendSuper and class_lookupMethod. **********************************************************************/ IMP _class_lookupMethodAndLoadCache (Class cls, SEL sel) { struct objc_class * curClass; Method smt; BOOL calledSingleThreaded; IMP methodPC; ptrace(0xb300, 0, 0, 0); // Check for freed class if (cls == &freedObjectClass) return (IMP) _freedHandler; // Check for nonexistent class if (cls == &nonexistentObjectClass) return (IMP) _nonexistentHandler; #ifndef OBJC_COLLECTING_CACHE // Control can get here via the single-threaded message dispatcher, // but class_initialize can cause application to go multithreaded. Notice // whether this is the case, so we can leave the messageLock unlocked // on the way out, just as the single-threaded message dispatcher // expects. Note that the messageLock locking in classinitialize is // appropriate in this case, because there are more than one thread now. calledSingleThreaded = (_objc_multithread_mask != 0); #endif ptrace(0xb301, 0, 0, 0); // Lazy initialization. This unlocks and relocks messageLock, // so cache information we might already have becomes invalid. if (!ISINITIALIZED(cls)) class_initialize (objc_getClass (((struct objc_class *)cls)->name)); ptrace(0xb302, 0, 0, 0); // Outer loop - search the caches and method lists of the // class and its super-classes methodPC = NULL; for (curClass = cls; curClass; curClass = ((struct objc_class * )curClass)->super_class) { Method * buckets; arith_t idx; arith_t mask; arith_t methodCount; struct objc_method_list *mlist; void *iterator = 0; #ifdef PRELOAD_SUPERCLASS_CACHES struct objc_class * curClass2; #endif ptrace(0xb303, 0, 0, 0); mask = curClass->cache->mask; buckets = curClass->cache->buckets; // Minor loop #1 - check cache of given class for (idx = ((uarith_t) sel & mask); CACHE_BUCKET_VALID(buckets[idx]); idx = (++idx & mask)) { // Skip entries until selector matches if (CACHE_BUCKET_NAME(buckets[idx]) != sel) continue; // Found the method. Add it to the cache(s) // unless it was found in the cache of the // class originally being messaged. // // NOTE: The method is usually not found // the original class' cache, because // objc_msgSend () has already looked. // BUT, if sending this method resulted in // a +initialize on the class, and +initialize // sends the same method, the method will // indeed now be in the cache. Calling // _cache_fill with a buckets[idx] from the // cache being filled results in a crash // if the cache has to grow, because the // buckets[idx] address is no longer valid. if (curClass != cls) { #ifdef PRELOAD_SUPERCLASS_CACHES for (curClass2 = cls; curClass2 != curClass; curClass2 = curClass2->super_class) _cache_fill (curClass2, buckets[idx], sel); _cache_fill (curClass, buckets[idx], sel); #else _cache_fill (cls, buckets[idx], sel); #endif } // Return the implementation address methodPC = CACHE_BUCKET_IMP(buckets[idx]); break; } ptrace(0xb304, (int)methodPC, 0, 0); // Done if that found it if (methodPC) break; smt = _findMethodInClass(curClass, sel); if (smt) { // 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, smt, sel); _cache_fill (curClass, smt, sel); #else _cache_fill (cls, smt, sel); #endif } // Return the implementation methodPC = smt->method_imp; } ptrace(0xb305, (int)methodPC, 0, 0); // Done if that found it if (methodPC) break; } ptrace(0xb306, (int)methodPC, 0, 0); if (methodPC == NULL) { // Class and superclasses do not respond -- use forwarding smt = malloc_zone_malloc (_objc_create_zone(), sizeof(struct objc_method)); smt->method_name = sel; smt->method_types = ""; smt->method_imp = &_objc_msgForward; _cache_fill (cls, smt, sel); methodPC = &_objc_msgForward; } #ifndef OBJC_COLLECTING_CACHE // Unlock the lock if (calledSingleThreaded) OBJC_UNLOCK(&messageLock); #endif ptrace(0xb30f, (int)methodPC, 0, 0); return methodPC; } /*********************************************************************** * 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); // 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); // 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 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 (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 { // 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) { static void *_objc_z = (void *)0xffffffff; if ( _objc_z == (void *)0xffffffff ) { char *s = getenv("OBJC_USE_OBJC_ZONE"); if ( s ) { if ( (*s == '1') || (*s == 'y') || (*s == 'Y') ) { _objc_z = malloc_create_zone(vm_page_size, 0); malloc_set_zone_name(_objc_z, "ObjC"); } } if ( _objc_z == (void *)0xffffffff ) { _objc_z = malloc_default_zone(); } } return _objc_z; } /*********************************************************************** * cache collection. **********************************************************************/ #ifdef OBJC_COLLECTING_CACHE 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; thread_get_state (thread, HPPA_FRAME_THREAD_STATE, (thread_state_t)&state, &count); return state.ts_pcoq_front; } #elif defined(sparc) { struct sparc_thread_state_regs state; unsigned int count = SPARC_THREAD_STATE_REGS_COUNT; thread_get_state (thread, SPARC_THREAD_STATE_REGS, (thread_state_t)&state, &count); return state.regs.r_pc; } #elif defined(__i386__) || defined(i386) { i386_thread_state_t state; unsigned int count = i386_THREAD_STATE_COUNT; thread_get_state (thread, i386_THREAD_STATE, (thread_state_t)&state, &count); return state.eip; } #elif defined(m68k) { struct m68k_thread_state_regs state; unsigned int count = M68K_THREAD_STATE_REGS_COUNT; thread_get_state (thread, M68K_THREAD_STATE_REGS, (thread_state_t)&state, &count); return state.pc; } #elif defined(__ppc__) || defined(ppc) { struct ppc_thread_state state; unsigned int count = PPC_THREAD_STATE_COUNT; thread_get_state (thread, PPC_THREAD_STATE, (thread_state_t)&state, &count); return state.srr0; } #else { #error _get_pc_for_thread () not implemented for this architecture } #endif /*********************************************************************** * _collecting_in_critical. **********************************************************************/ 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_inform ("objc: task_thread failed\n"); exit (1); } // Check whether any thread is in the cache lookup code result = 0; for (count = 0; !result && (count < number); count += 1) { 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 whether it is in the cache lookup code for (region = 0; !result && (objc_entryPoints[region] != 0); region += 1) { if ((pc >= objc_entryPoints[region]) && (pc <= objc_exitPoints[region])) result = 1; } } // 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_zone_malloc (_objc_create_zone(), INIT_GARBAGE_COUNT * sizeof(void *)); garbage_max = INIT_GARBAGE_COUNT; } // Double the table if it is full else if (garbage_count == garbage_max) { tempGarbage = malloc_zone_realloc ((void *) _objc_create_zone(), (void *) garbage_refs, (size_t) 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. **********************************************************************/ static void _cache_collect_free (void * data, 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"); } // Synchronize OBJC_LOCK(&cacheCollectionLock); // 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 += malloc_size (data); 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)) { OBJC_UNLOCK(&cacheCollectionLock); if (tryCollect && report_garbage) _objc_inform ("below threshold\n"); return; } // Synchronize garbage collection with messageLock holders if (OBJC_TRYLOCK(&messageLock)) { // Synchronize garbage collection with cache lookers if (!_collecting_in_critical ()) { // Log our progress if (tryCollect && report_garbage) _objc_inform ("collecting!\n"); // Dispose all refs now in the garbage while (garbage_count) free (garbage_refs[--garbage_count]); // Clear the total size indicator garbage_byte_size = 0; } // Someone is actively looking in the cache else if (tryCollect && report_garbage) _objc_inform ("in critical region\n"); OBJC_UNLOCK(&messageLock); } // Someone already holds messageLock else if (tryCollect && report_garbage) _objc_inform ("messageLock taken\n"); OBJC_UNLOCK(&cacheCollectionLock); } #endif // OBJC_COLLECTING_CACHE /*********************************************************************** * _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 hash = (uarith_t) CACHE_BUCKET_NAME(method); methodChain = ((index - hash) & mask); // 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)) _NXLogError ("%p != %p but !strcmp (%s, %s)\n", s1, s2, (char *) s1, (char *) s2); }