objc4-217.tar.gz

[apple/objc4.git] / runtime / objc-class.m

/*
 * 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.
**********************************************************************/

#import <mach/mach_interface.h>
#include <mach-o/ldsyms.h>
#include <mach-o/dyld.h>

#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/uio.h>
#include <sys/fcntl.h>

#import "objc-class.h"

#import <objc/Object.h>
#import <objc/objc-runtime.h>
#import "objc-private.h"
#import "hashtable2.h"
#import "maptable.h"

#include <sys/types.h>

#include <CoreFoundation/CFDictionary.h>

// Needed functions not in any header file
size_t malloc_size (const void * ptr);

// Needed kernel interface
#import <mach/mach.h>
#import <mach/thread_status.h>


/***********************************************************************
* Conditionals.
**********************************************************************/

// Define PRELOAD_SUPERCLASS_CACHES to cause method lookups to add the
// method the appropriate superclass caches, in addition to the normal
// encaching in the subclass where the method was messaged.  Doing so
// will speed up messaging the same method from instances of the
// superclasses, but also uses up valuable cache space for a speculative
// purpose
// See radar 2364264 about incorrectly propogating _objc_forward entries
// and double freeing them, first, before turning this on!
//#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
    header_info *               hInfo;
#endif

    // Trivial case is easy
    if (imposter == original)
        return imposter;

    // Imposter must be an immediate subclass of the original
    if (((struct objc_class *)imposter)->super_class != original) {
        // radar 2203635
        __objc_error(imposter, _errNotSuper, ((struct objc_class *)imposter)->name, ((struct objc_class *)original)->name);
    }

    // Can't pose when you have instance variables (how could it work?)
    if (((struct objc_class *)imposter)->ivars) {
        // radar 2203635
        __objc_error(imposter, _errNewVars, ((struct objc_class *)imposter)->name, ((struct objc_class *)original)->name, ((struct objc_class *)imposter)->name);
    }

    // Build a string to use to replace the name of the original class.
    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 (hInfo = _objc_headerStart(); hInfo != NULL; hInfo = hInfo->next)
    {
        Class *         cls_refs;
        unsigned int    refCount;
        unsigned int    index;

        // Get refs associated with this header
        cls_refs = (Class *) _getObjcClassRefs ((headerType *) hInfo->mhdr, &refCount);
        if (!cls_refs || !refCount)
            continue;

        // Minor loop - process this header's refs
        cls_refs = (Class *) ((unsigned long) cls_refs + hInfo->image_slide);
        for (index = 0; index < refCount; index += 1)
        {
            if (cls_refs[index] == original)
                cls_refs[index] = imposter;
        }
    }
#endif // OBJC_CLASS_REFS

    // Change the name of the original class.
    ((struct objc_class *)original)->name           = imposterNamePtr + 1;
    ((struct objc_class *)original)->isa->name = imposterNamePtr;

    // Restore the imposter and the original class with their new names.
    NXHashInsert (class_hash, imposter);
    NXHashInsert (class_hash, original);

    OBJC_UNLOCK(&classLock);

    return imposter;
}

/***********************************************************************
* _freedHandler.
**********************************************************************/
static void     _freedHandler          (id              self,
                                  SEL           sel)
{
    __objc_error (self, _errFreedObject, SELNAME(sel), self);
}

/***********************************************************************
* _nonexistentHandler.
**********************************************************************/
static void     _nonexistentHandler    (id              self,
                                    SEL         sel)
{
    __objc_error (self, _errNonExistentObject, SELNAME(sel), self);
}

/***********************************************************************
* class_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;


    // bind the module in - if it came from a bundle or dynamic library
    if (((struct objc_class *)clsDesc)->info & CLS_NEED_BIND) {
        ((struct objc_class *)clsDesc)->info &= ~CLS_NEED_BIND;
        _objc_bindModuleContainingClass(clsDesc);
    }

    // by loading things we might get initialized (maybe) ((paranoia))
    if (ISINITIALIZED(((struct objc_class *)clsDesc)))
        return;

    // chain on the categories and bind them if necessary
    _objc_resolve_categories_for_class(clsDesc);

    // by loading things we might get initialized (maybe) ((paranoia))
    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));
    // But the simple solution is to ask if this class itself implements
    // initialize (!) and only send it then!!

#ifndef OBJC_COLLECTING_CACHE
    // Release the message lock so that messages can be sent.
    OBJC_UNLOCK(&messageLock);
#endif

    // Send the initialize method.
    // Of course, if this class doesn't implement initialize but
    // the super class does, we send initialize to the super class
    // twice, thrice...
    [(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");

    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) {
        // radar 2203635
        __objc_error(cls, _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;

    trace(0xb300, 0, 0, 0);

    // Check for freed class
    if (cls == &freedObjectClass)
        return (IMP) _freedHandler;

    // Check for nonexistent class
    if (cls == &nonexistentObjectClass)
        return (IMP) _nonexistentHandler;

#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

    trace(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));

    trace(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

        trace(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;
        }

        trace(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;
        }

        trace(0xb305, (int)methodPC, 0, 0);

        // Done if that found it
        if (methodPC)
            break;
    }

    trace(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

    trace(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))
        _objc_inform ("%p != %p but !strcmp (%s, %s)\n", s1, s2, (char *) s1, (char *) s2);
}