DPQueue is now a two-lock concurrent queue.

[hom.git] / Source / DPMessage.m

//
//  DPMessage.m
//  HigherOrderMessaging
//
//  Created by Ofri Wolfus on 09/05/07.
//  Copyright 2007 Ofri Wolfus. All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met:
//  
//  1. Redistributions of source code must retain the above copyright
//  notice, this list of conditions and the following disclaimer.
//  2. Redistributions in binary form must reproduce the above copyright
//  notice, this list of conditions and the following disclaimer in the
//  documentation and/or other materials provided with the distribution.
//  3. Neither the name of Ofri Wolfus nor the names of his contributors
//  may be used to endorse or promote products derived from this software
//  without specific prior written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
//  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
//  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
//  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
//  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
//  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
//  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
//  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
//  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//

#import "DPMessage.h"
#import "DPObjCRuntime.h"
#import <Foundation/Foundation.h>
#include <libkern/OSAtomic.h>


struct _dp_msg {
        Class isa;
        struct _dp_message_content content;
};

Class _dp_uninitialized_msg_cls = Nil;
Class _dp_msg_cls = Nil;
static Class _dp_refCounted_msg_cls = Nil;

@class _DPUninitializedMessage, DPRefCountedMessage;

#define MAX_CACHED_MESSAGES 50
static struct _dp_msg _messages_cache[MAX_CACHED_MESSAGES];
static id _unused_messages_cache[MAX_CACHED_MESSAGES] = { NULL };
static int32_t _messages_cache_size = MAX_CACHED_MESSAGES;
static OSSpinLock _messages_cache_lock = OS_SPINLOCK_INIT;

/*
 * Before the main() is entered (but after all libraries are loaded),
 * we keep pointers to the DPMessage and _DPUninitializedMessage classes.
 * This way we can skip the repeated calls to objc_getClass() in MSG(),
 * MSGV() and -[_DPUninitializedMessage forward::], which gives us a nice
 * speed boost.
 * Internally, objc_getClass() uses a pthread mutex to make sure the class
 * table is thread safe, which slows us down for no good reason.
 */
static void __attribute__((constructor)) _dp_init_DPMessage(void) {
        _dp_uninitialized_msg_cls = (Class)objc_getClass("_DPUninitializedMessage");
        _dp_msg_cls = [DPMessage class];
        _dp_refCounted_msg_cls = [DPRefCountedMessage class];
        
        // Initialize our unused messages cache
        int i;
        for (i = 0; i < MAX_CACHED_MESSAGES; i++)
                _unused_messages_cache[i] = (id)&(_messages_cache[i]);
}

// Returns a cached message from our pool of messages.
// If the pool is empty, nil is returned.
id _dp_getCachedMessage(void) {
        id msg = nil;
        
        // Try to get the lock.
        // If we can't, don't waste any time and just return nil.
        if (__builtin_expect(OSSpinLockTry(&_messages_cache_lock), true)) {
                int32_t index = _messages_cache_size - 1;
                
                // Be sure we got any objects
                if (index >= 0) {
                        --_messages_cache_size;
                        // Grab the message from the cache
                        msg = _unused_messages_cache[index];
                        _unused_messages_cache[index] = nil;
                }
                
                // We're good to go
                OSSpinLockUnlock(&_messages_cache_lock);
                        
                // Initialize our message and autorelease it
                if (msg) {
                        // MSG() and MSGV() remember the class of the message
                        // and set it back when needed.
                        msg->isa = _dp_refCounted_msg_cls;
                        [msg autorelease];
                }
        }
        
        return msg;
}

@implementation DPMessage

// Every base class must implement +initialize
+ (void)initialize {
}

+ (id)messageWithSelector:(SEL)sel frame:(void *)frame {
        id m = class_createInstance(_dp_uninitialized_msg_cls, 0);
        [m forward:sel :frame];
        m->isa = _dp_refCounted_msg_cls;
        return [m autorelease];
}

- (id)forward:(SEL)sel :(marg_list)args {
#if defined(__APPLE__)  // GNUStep doesn't support @throw
        @throw [NSException exceptionWithName:@"Unknown message"
                                                                   reason:[NSString stringWithFormat:@"Selector %@ not recognized",
                                                                                                                        NSStringFromSelector(sel)]
                                                                 userInfo:nil];
#endif
        
        return self;
}

- (SEL)selector {
        return content._sel;
}

- (marg_list)arguments {
        return (marg_list)(content._frame);
}

- (unsigned)sizeOfArguments {
        return content._frameSize;
}

@end


/*
 * This class is used to convert from the Objective-C
 * runtime's marg_list structure to a structure compatible
 * with GCC's __builtin_apply() function.
 *
 * The logic behind this class is very simple. If we have
 * a marg_list we can use it to message our class, and if our
 * class responds to it the result will be a method being invoked.
 * Now ObjC methods are simply C functions under the hood, so calling
 * __builtin_apply_args() from within this method will give us a new
 * structure we can safely pass to __builtin_apply() and that contain
 * all the information of our original marg_list.
 *
 * In order to use this class two steps are needed:
 *
 * 1) Invoke +[_DPMargListConvertor _prepareForSelector:] with the
 * selector that matches the marg_list you wish to convert.
 * This method will make sure _DPMargListConvertor can repond to a
 * message with this selector and will register a new method if needed.
 *
 * 2) Use objc_msgSendv() to message _DPMargListConvertor with the
 * marg_list you wish to convert. The result objc_msgSendv() will return
 * is a newly allocated (using malloc) block with a GCC compatible frame.
 * The returned block must be manually freed.
 *
 * This technique works *ONLY* with methods returning integral types.
 * It might also work with floating points (depending on the architecture),
 * but will definitly *NOT* work for struct return types.
 *
 * Warning: This class is *NOT* intended to be instantiated. Don't attempt
 * to instantiate it as the first message sent to an instance will crash
 * the process.
 */
@interface _DPMargListConvertor {
        Class isa;
}

+ (void)_prepareForSelector:(SEL)sel;

@end

@implementation _DPMargListConvertor

// Every base class must implement +initialize
+ (void)initialize {
}

// We must also implement forward::
// Note that we implement it as a class method as this class
// is not designed to be instantiated. Any attempt to message
// an instance of this class will crash the process due to missing
// implementation of -forward::
+ (id)forward:(SEL)sel :(marg_list)args {
        return self;
}

// This is the implementation we put in newly added methods.
// It does exactly one thing: generates a GCC compatible arguments
// frame and copies it to a malloc() allocated block.
static void * _dp_captureArguments(id self, SEL sel) {
        // Since marg_list and GCC's frame structure are pretty much the same
        // (I have no idea why simply passing marg_list to __builtin_apply() doesn't
        // work. Apparently they are just structured differently), the same size
        // calculation applies to both:
        // frame size = dp_maxArgSizeForSelector() + dp_marg_prearg_size
        // Note that the structure of GCC's frame struct is documented
        // (http://developer.apple.com/documentation/DeveloperTools/gcc-4.0.1/gcc/Constructing-Calls.html#Constructing-Calls )
        // to contain the same info as marg_list, and the calculation is based on this assumption.
        // If this fail to work for some reason, we should just use a 1024 bytes size
        // like DPMessage uses.
        unsigned int s = dp_maxArgSizeForSelector(sel) + dp_marg_prearg_size;
        return memcpy(malloc(s), __builtin_apply_args(), s);
}

+ (void)_prepareForSelector:(SEL)sel {
        if (__builtin_expect(!class_getClassMethod(self, sel), 0))
                class_addMethod(self, sel, (IMP)_dp_captureArguments,
                                                // Since the types don't really matter, we'll just reuse the
                                                // types of a well known existing method like -[NSObject self].
                                                method_getTypeEncoding(class_getInstanceMethod([NSObject class],
                                                                                                                                           @selector(self))));  
}

@end


@implementation DPMessage (Extensions)

- (BOOL)returnsStruct {
        // Struct returning methods begin with a pointer to
        // the memory to which the result will be written
        // while non-struct returns begin with a pointer
        // to self.
        return marg_getValue([self arguments], 0, void *) != self;
}

- (unsigned)numberOfArguments {
        return sel_getNumberOfArguments([self selector]);
}

- (id)sendTo:(id)receiver {
        return objc_msgSendv(receiver, [self selector], [self sizeOfArguments], [self arguments]);
}

+ (Class)class {
        return self;
}

- (Class)class {
        return [object_getClass(self) class];
}

- (NSString *)description {
        return [NSString stringWithFormat:@"%@ %p <%@>", NSStringFromClass([self class]),
                self, NSStringFromSelector([self selector])];
}

- (BOOL)respondsToSelector:(SEL)aSelector {
        return dp_getMethod(self, aSelector) != NULL;
}

- (void *)gccArgumentsFrame {
        static id convertor = nil;
        
        // Find our convertor class
        if (__builtin_expect(!convertor, 0))
                convertor = objc_getClass("_DPMargListConvertor");
        
        // Make sure it responds to our method
        [convertor _prepareForSelector:[self selector]];
        
        // Send ourself to the convertor which in turn,
        // returns us a fresh new arguments frame.
        return [self sendTo:convertor];
}

- (unsigned)realFrameSize {
        return [self sizeOfArguments] + dp_marg_prearg_size;
}

@end

/*
 * A private subclass for ref-counted messages.
 * DPMessage is designed to be allocated on stack
 * and therefor completely ignores reference counting.
 * The returned object from -[DPMessage copy] is actually
 * a DPRefCountedMessage instance.
 *
 * IMPORTANT!! DPRefCountedMessage must not define any instance
 * variables so that it can be interchangeable with DPMessage
 * by simply swapping the isa pointer. If you must define new
 * ivars, add them to the _dp_message_content struct and use from
 * there.
 */
@interface DPRefCountedMessage : DPMessage <NSCopying>
@end

@implementation DPRefCountedMessage

- (id)copyWithZone:(NSZone *)zone {
        return NSCopyObject((id)self, 0, zone);
}

- (id)copy {
        return [self copyWithZone:NULL];
}

- (id)retain {
        NSIncrementExtraRefCount(self);
        return self;
}

- (void)release {
        if (NSDecrementExtraRefCountWasZero(self)) {
                // If we're a message from the pool of messages
                // &(_messages_cache[0]) <= self <= &(_messages_cache[MAX_CACHED_MESSAGES - 1])
                if ((void *)self >= (void *)&(_messages_cache[0]) &&
                        (void *)self <= (void *)&(_messages_cache[MAX_CACHED_MESSAGES - 1]))
                {
                        // Acquire the lock
                        OSSpinLockLock(&_messages_cache_lock);
                        // Put us back in the cache
                        _unused_messages_cache[_messages_cache_size] = self;
                        // We added a message, right?
                        ++_messages_cache_size;
                        // Free to go
                        OSSpinLockUnlock(&_messages_cache_lock);
                } else {
                        // We're just a regular dynamically allocated instance
                        // so deallocate normally.
                        NSDeallocateObject((id)self);
                }
        }
}

- (id)autorelease {
        [NSAutoreleasePool addObject:self];
        return self;
}

@end


@implementation DPMessage (MemoryManagement)

- (id)copyWithZone:(NSZone *)zone {
        DPMessage *o = (id)NSCopyObject((id)self, 0, zone);
        o->isa = [DPRefCountedMessage class];
        return o;
}

- (id)copy {
        return [self copyWithZone:NULL];
}

- (id)retain {
        return self;
}

- (void)release {
}

- (id)autorelease {
        return self;
}

@end

@interface NSObject (StopGCCFromWhining)
- (const char *)typeEncodingForMessage:(id)msg;
+ (const char *)typeEncodingForMessage:(id)msg;
@end

/************************************************************
 * * * * * * * * * * * VERY IMPORTANT!! * * * * * * * * * * *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * _DPUninitializedMessage must be defined *EXACTLY* like
 * DPMessage so both can be exchangeable.
 ************************************************************/
@interface _DPUninitializedMessage {
        Class isa;
        struct _dp_message_content content;
}

@end

@implementation _DPUninitializedMessage

+ (void)initialize {
}

- (id)forward:(SEL)sel :(marg_list)args {
        // Save the selector
        content._sel = sel;
        
        // Get the frame's size
        content._frameSize = dp_maxArgSizeForSelector(content._sel);
        
        // Copy the marg list
        // Note the size returned by dp_maxArgSizeForSelector() is the same
        // as the size returned by method_getSizeOfArguments(), which is *NOT*
        // the real size of the frame in PPC. The true size is always
        // method_getSizeOfArguments() + dp_marg_prearg_size.
        memcpy(content._frame, args, content._frameSize + dp_marg_prearg_size);
        
        // We're good to go. Set our class back to DPMessage
        self->isa = _dp_msg_cls;
        
        // Get the frame's size
        if (__builtin_expect(sel == @selector(initWithFormat:) ||
                                                 sel == @selector(stringByAppendingFormat:) ||
                                                 sel == @selector(initWithFormat:locale:) ||
                                                 sel == @selector(appendFormat:) ||
                                                 sel == @selector(stringWithFormat:), 0))
        {
                const char *t = [NSString typeEncodingForMessage:self];
                unsigned size = dp_getSizeOfArguments(t);
                if (size > content._frameSize) {
                        memcpy((void *)(content._frame) + content._frameSize + dp_marg_prearg_size,
                                   args + content._frameSize + dp_marg_prearg_size,
                                   size - content._frameSize);
                        content._frameSize = size;
                }
        }
        
        return self;
}

+ (id)forward:(SEL)sel :(marg_list)args {
        return self;
}

@end
        

//=========================================================//
//=========================================================//
#pragma mark -
#pragma mark Frame size lookup functions

#ifdef __LP64__
// Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
CFHashCode DPIntHash(uint64_t key)
{
        key += ~(key << 32);
        key ^= (key >> 22);
        key += ~(key << 13);
        key ^= (key >> 8);
        key += (key << 3);
        key ^= (key >> 15);
        key += ~(key << 27);
        key ^= (key >> 31);
        return (CFHashCode)key;
}
#else
// Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
CFHashCode DPIntHash(uint32_t key) 
{
        key += ~(key << 15);
        key ^= (key >> 10);
        key += (key << 3);
        key ^= (key >> 6);
        key += ~(key << 11);
        key ^= (key >> 16);
        return (CFHashCode)key;
}
#endif

// Static variables (thread safe)
static CFMutableDictionaryRef _hash_cache = NULL;
static OSSpinLock _hash_cache_lock = OS_SPINLOCK_INIT;

/*
 * The first call to this function searches the entire class
 * list, and caches the arguments size of the method with the
 * largest arguments frame for every available selector.
 * Subsequent calls simply return results from the cache.
 * Thanks to Andre Pang for suggesting this approach, and the
 * double-cache algorithm (see below).
 *
 * OSSpinLock is used to ensure thread-safety as contention is expected
 * to be very very low.
 *
 * For the possibility of future porting to GNUStep, NSHashMap is used
 * for the cache.
 */
unsigned int _dp_lookupMaxArgSizeForSelector(SEL sel, BOOL rebuildCache) {
        unsigned int result = 0U;
        
        // Like in the ObjC runtime, thread synchronization is always active
        OSSpinLockLock(&_hash_cache_lock);
        
        // Make sure our cache is initialized
        if (__builtin_expect(_hash_cache == NULL, 0)) {
                CFDictionaryKeyCallBacks keyCallbacks = { 0, NULL, NULL, NULL, NULL, (void *)DPIntHash };
                
                rebuildCache = YES;
                // According to the runtime sources, libobjc, CoreText, Foundation, HIToolbox, CoreData,
                // QuartzCore, AppKit and WebKit have 16371 selectors. The runtime also says that most
                // apps use 2000..7000 extra sels, so we'll add ~3500 as a compromise.
                _hash_cache = CFDictionaryCreateMutable(NULL, 19000, &keyCallbacks, NULL);
        }
        
        
        if (__builtin_expect(!rebuildCache, 1)) {
                result = (unsigned int)CFDictionaryGetValue(_hash_cache, sel); // Returns NULL (== 0) if not found
        } else {
                // Rebuild the cache if needed
                unsigned        count = objc_getClassList(NULL, 0);
                Class           *classes = calloc(count, sizeof(Class));
                int32_t         i;
                
                // Get all available classes
                objc_getClassList(classes, count);
                
                // NOTE: Since CFDictionarySetValue() replaces existing values
                // there's no need to call CFDictionaryRemoveAllValues(). The new
                // values will override the existing ones.
                
                // Loop though all classes
                for (i = 0; i < count; i++) {
                        Class cls = classes[i];
                        
                        // Get all methods of this class (and its super classes')
                        unsigned int c, j;
                        // Does this include super classes in ObjC 2?
                        Method *methods = class_copyMethodList(cls, &c);
                        
                        // Loop through all instance methods and store them in our cache
                        for (j = 0; j < c; j++) {
                                unsigned int size = method_getSizeOfArguments(methods[j]);
                                SEL s = method_getName(methods[j]);
                                
                                if (s == sel && size > result)
                                        result = size;
                                
                                if (size > (unsigned int)CFDictionaryGetValue(_hash_cache, s))
                                        CFDictionarySetValue(_hash_cache, s, (const void *)size);
                        }
                        
                        // Clean up
                        free(methods);
                        
                        // And now class methods
                        methods = class_copyMethodList(object_getClass(cls), &c);
                        for (j = 0; j < c; j++) {
                                unsigned int size = method_getSizeOfArguments(methods[j]);
                                SEL s = method_getName(methods[j]);
                                
                                if (s == sel && size > result)
                                        result = size;
                                
                                if (size > (unsigned int)CFDictionaryGetValue(_hash_cache, s))
                                        CFDictionarySetValue(_hash_cache, s, (const void *)size);
                        }
                        
                        free(methods);
                }
                
                // Clean up
                free(classes);
        }
        
        OSSpinLockUnlock(&_hash_cache_lock);

        return result;
}

unsigned dp_getCacheSize(void) {
        unsigned count = 0;
        OSSpinLockLock(&_hash_cache_lock);
        count = CFDictionaryGetCount(_hash_cache);
        OSSpinLockUnlock(&_hash_cache_lock);
        return count;
}
        

// This is the internal class cout of dp_maxArgSizeForSelector()
// It's not declared inside it to enable acces for
// dp_flushArgSizeCache() to it.
static volatile int32_t _classCount = -1;


/*
 * dp_maxArgSizeForSelector() is the function that gets invoked by
 * _DPUninitializedMessage in order to find a matching method for
 * a given selector.
 * 
 * It builds on top of _dp_lookupMaxArgSizeForSelector() but implements
 * a second cache. Real world experience shows only seveal tens of
 * methods are actually being used with HOM, and searching a tiny
 * cache of this size is going to be much faster than the cache used
 * by _dp_lookupMaxArgSizeForSelector() (which may hold ~23,000 entries in
 * a large Cocoa app). Again, thanks to Andre Pang for suggesting this
 * two levels cache algorithm.
 *
 * Unlike the cache used by _dp_lookupMaxArgSizeForSelector() the cache
 * used in this function is simply two fixed size C arrays. The selectors
 * array is sotred by the selctors' pointer values, from the lowest to the
 * highest. A binary search is then used to find the index of a selector
 * and match it with its value in the values array. If at some later point
 * selectors are not guaranteed to be unique, we can still store their names
 * and search according to that.
 * NOTE: The current implementation does not handle the case of the cache
 * getting larger than its max size. When the cache is full selectors will
 * no longer be cached.
 *
 * In order to keep up with classes being registerd/unregisterd,
 * the total class count is also cached and is checked in each call.
 * If the total count suddenly changes, the entire cache gets rebuilt.
 * This catches most cases (currently all, as class unloading is not
 * supported in 10.4), except if you load some classes, unload some
 * others, but the total amount is left the same. Of course this applies
 * only if no call to this function is made between loading and unloading.
 * The dp_flushMethodsCache() function is provided for forcing the cache(s)
 * to be rebuilt the next time a lookup is done.
 *
 * OSSpinLock is used to ensure thread-safety as contention is expected
 * to be very very low.
 */

/*
 * When our array reaches 200 items, it takes ~7.5 steps
 * to find a selector. Meanwhile, searching our hash-table cache
 * with ~23000 items takes at most ~14 steps (and Apple says it'll
 * usually be better). This means that when our array is full, there's
 * no point in searching it before searching the hash table, so we
 * simply skip it and ignore it.
 */
#define MAX_ARRAY_CACHE_SIZE 200

// The binary search implementation
DP_STATIC_INLINE int _DPFindPtrInArray(void *ptr, void **arr, int count) {
        register int low = 0;
        register int high = count - 1;
        
        while (low <= high) {
                int mid = (low + high) / 2;
                
                if (arr[mid] > ptr)
                        high = mid - 1;
                else if (arr[mid] < ptr)
                        low = mid + 1;
                else
                        return mid;
        }
        
        return -1;
}

// Inserts a given pointer to a pointers array, sorted from the lowest
// to up.
DP_STATIC_INLINE int _DPInsertPtrToArray(void *ptr, void **arr, int count) {
        register int i;
        int j;
        
        // Find the place for out new pointer
        for (i = 0; i < count; i++) {
                if (arr[i] > ptr)
                        break;
        }
        
        // Remember it
        j = i;
        
        // Now make space for it by pushing
        // everything else down
        for (i = count - 1; i >= j; i--)
                arr[i + 1] = arr[i];
        
        arr[j] = ptr;
        return j;
}

unsigned int dp_maxArgSizeForSelector(SEL sel) {
        // Static variables (thread safe)
        static SEL cachedSels[MAX_ARRAY_CACHE_SIZE];
        static unsigned int cachedSizes[MAX_ARRAY_CACHE_SIZE];
        static unsigned cacheCount = 0;
        static OSSpinLock cacheLock = OS_SPINLOCK_INIT;
        
        // Local variables
        unsigned int r = 0U;
#if DP_NSBUNEL_DETECTION_ONLY
        int32_t count = 1;
#else
        int32_t count = objc_getClassList(NULL, 0);
#endif
        BOOL insertToCache = NO;
        
        // We're always thread-safe, just like the runtime
        OSSpinLockLock(&cacheLock);
        
        // The total number of classes has changed,
        // let's rebuild our cache.
        if (__builtin_expect(_classCount != count, 0)) {
#if DP_NSBUNEL_DETECTION_ONLY
                // If we got here it means _classCount == 0 so we just set it to 1.
                OSAtomicCompareAndSwap32Barrier(_classCount, 1, (int32_t *)&_classCount);
#else
                // Remember the class count.
                // This is an equivalent to "_classCount = count;" but thread safe.
                OSAtomicCompareAndSwap32Barrier(_classCount, count, (int32_t *)&_classCount);
#endif
                
                // Reset the cache
                cacheCount = 0;
                
                // Let's find a method
                r = _dp_lookupMaxArgSizeForSelector(sel, YES);
                
                // Cache the result;
                if (r)
                        insertToCache = YES;
        } else {
                // Below MAX_ARRAY_CACHE_SIZE we try to search in our array
                // cache before falling back to the dictionary cache, which
                // assuming we have a method in the array cache, will be faster.
                if (__builtin_expect(cacheCount < MAX_ARRAY_CACHE_SIZE, 1)) {
                        // First, attempt to search our internal cache for a method
                        int index = _DPFindPtrInArray(sel, (void **)cachedSels, cacheCount);
                        
                        if (__builtin_expect(index > -1, 1))
                                r = cachedSizes[index];
                        else {
                                // If the first search failed, use the larger cache
                                // containing all methods.
                                r = _dp_lookupMaxArgSizeForSelector(sel, NO);
                                if (r)
                                        insertToCache = YES;
                        }
                } else {
                        // When we reached MAX_ARRAY_CACHE_SIZE, the time it takes
                        // to search the array cache is almost identical to the time
                        // needed for the dictionary lookup, so we just skip the array.
                        r = _dp_lookupMaxArgSizeForSelector(sel, NO);
                }
        }
        
        // Should we cache the result of this method?
        if (__builtin_expect((insertToCache && cacheCount < MAX_ARRAY_CACHE_SIZE), 0)) {
                // Insert the new selector and remember its index
                int index = _DPInsertPtrToArray(sel, (void **)cachedSels, cacheCount);
                int j;
                // Push all cached sizes and make space for the new size
                for (j = cacheCount - 1; j >= index; j--)
                        cachedSizes[j + 1] = cachedSizes[j];
                
                cachedSizes[index] = r;
                ++cacheCount;
        }
        
        // Release the lock
        OSSpinLockUnlock(&cacheLock);
        
        return r;
}

// In order to reset the cache we just set the class count to 0
void dp_flushArgSizeCache(void) {
        OSAtomicCompareAndSwap32Barrier(_classCount, 0, (int32_t *)&_classCount);
}

#if DP_NSBUNEL_DETECTION_ONLY
// If NSBundle is the only way classes are added/removed
// we can use its NSBundleDidLoadNotification notification to flush
// our caches and save the locking overhead of objc_getClassList().
@interface DPMessage (_DPLookupCallback)
- (void)_bundleLoaded:(NSNotification *)notif;
@end

@implementation DPMessage (_DPLookupCallback)

- (void)_bundleLoaded:(NSNotification *)notif {
        if (_classCount > -1)   // Ignore notifications before the cache is first built
                dp_flushArgSizeCache();
}

@end

static void __attribute__((constructor)) _dp_setUpNSBundleCallback(void) {
        [[NSNotificationCenter defaultCenter] addObserver:[DPMessage class]
                                                                                         selector:@selector(_bundleLoaded:)
                                                                                                 name:NSBundleDidLoadNotification
                                                                                           object:nil];
}
#endif