preface

This document explores the data structure of the member variable cache in objC_class and the flow of method caching.

struct objc_class { Class isa; Class superclass; cache_t cache; class_data_bits_t bits; . }Copy the code

Data structure for cache_T

To find the definition of cache_t in the source code, take a look at the cache_t member variables.

typedef uint32_t mask_t;  

struct cache_t {
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;
#if__LP64__ uint16_t _flags; #endif uint16_t _occupied; }; explicit_atomic<preopt_cache_t *> _originalPreoptCache; }; .void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    void insert(SEL sel, IMP imp, id receiver);
}
Copy the code

__LP64__ indicates on a 64-bit system

Cache_t has two member variables. There are no comments in the source code for the related fields, so it’s hard to know what each field holds. The bucket_t *buckets() method returns a pointer to bucket_t

struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
......
}
Copy the code

Bucket_t stores SEL and IMP for the method.

Debug and print SEL and IMP with LLDB

Define a Person class and define multiple methods, as follows

@interface Person : NSObject

-(void)func1; - (void)func2; - (void)func3; - (void)func4; - (void)func5; - (void)func6;

@end

Copy the code

int main() {
    @autoreleasepool {
        Person *p = [Person alloc];
        [p func1];
        [p func2];
        [p func3];
        [p func4];
        [p func5];
    }
    return 0;
}
Copy the code

Set the breakpoint at [p func2], at which point the func1 method has been called, and print the cache through LLDB

(lldb) p/x [Person class] -> get the address of the class object (Class) $1 = 0x0000000100008370 Person
(lldb) p (cache_t *)0x0000000100008380-> Address offset0x10
(cache_t *) $2 = 0x0000000100008380
(lldb) p *$2-> Prints the current cache (cache_t) $3 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4301326736
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 3
        }
      }
      _flags = 32784
      _occupied = 1
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0001801000000003}}}}Copy the code

Call buckets()

(lldb) p $3.buckets() / / call buckets ()
(bucket_t *) $4 = 0x0000000100610990
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 48656
    }
  }
}
(lldb) p $5.sel() // call bucket_t sel()
(SEL) $6 = "func1"
(lldb) p $5.imp(nil, [Person class) / / callsbucket_ttheimp()
(IMP) $7 = 0x0000000100003d60 (KCObjcBuild`-[Person func1])
Copy the code

At this point, the structure diagram shown in the figure below can probably be obtained, butcache_tHow is it storedbucket_tWe don’t know yet.

Insert the process

First cache method

Locate the key method insert and then analyze the flow of that method. Re-run the code and set a breakpoint before insert, before calling func1, when no method is cached in the cache

mask_t cache_t::occupied() const
{
    return _occupied;
}

mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}

unsigned cache_t::capacity() const
{
    return mask() ? mask()+1 : 0; 
}

bool cache_t::isConstantEmptyCache() const
{
    return occupied() == 0  &&
        buckets() == emptyBucketsForCapacity(capacity(), false);
}

void cache_t::insert(SEL sel, IMP imp, id receiver){ runtimeLock.assertLocked(); .; // Get _occupied; the initial value is 0, representing the number of current cache methods;
    mask_t newOccupied = occupied() + 1;  / / 1
    // Get _maybeMask, not 0: _maybeMask + 1, otherwise 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;/ / 0. }Copy the code

At this point, the cache has not cached the method, and enters the if branch below

void cache_t::insert(SEL sel, IMP imp, id receiver){...if (slowpath(isConstantEmptyCache())) {
        //INIT_CACHE_SIZE = 1 << 2 = 4
        if(! capacity) capacity = INIT_CACHE_SIZE;// Call realLocate to open up memory
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true); }... }Copy the code

Create a memory

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    // Open up memory
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    // buckets and mask are set to 4-1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // drop the oldBuckets, no caching, freeOld is false
    if(freeOld) { collect_free(oldBuckets, oldCapacity); }}Copy the code

The source code notes that the last position will be placeholder to mark the end of the list, so _maybeMask is capacity-1, indicating the maximum number of methods currently stored

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    
    // Create memory space that is the size of bucket_t (newCapacity = 4)
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
    // Memory pan to get the address of the last bucket_t
    bucket_t *end = endMarker(newBuckets, newCapacity);

// Set the end flag
#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}
Copy the code

Methods the cache

The INSERT process continues down the road

static constexpr uintptr_t bucketsMask = ~0ul;
struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
//------------------------
// hash function
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    return (mask_t)(value & mask);
}
//------------------------
void cache_t::incrementOccupied() 
{
    _occupied++;
}
//------------------------
// In MAC x86 environment
// hash conflict handling,
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
void cache_t::insert(SEL sel, IMP imp, id receiver){... bucket_t *b = buckets(); mask_t m = capacity -1; // 4-1 = 3
    // Get the hash function where it is stored
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    // Scan an empty location to store methods
    do {
        //sel() == 0
        if (fastpath(b[i].sel() == 0)) {
            //occupied + 1
            incrementOccupied();
            // Save the method to that location
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        //sel() == sel method is cached
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return; }}while(fastpath((i = cache_next(i, m)) ! = begin));// cache_next fetches the next location until I == begin to exit the loop

    bad_cache(receiver, (SEL)sel);
}
Copy the code

Buckets capacity

Buckets only opened four Spaces at the first time, so they are bound to run out of space

#define CACHE_END_MARKER 1

// Historical fill ratio of 75% (since the new objc runtime was introduced).
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
void cache_t::insert(SEL sel, IMP imp, id receiver){...if (slowpath(isConstantEmptyCache())) {
        ......
    }
    //cache_fill_ratio(capacity) = 4 * 3 / 4 = 3
    // newOccupied + 1 <= 3
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    // Need to be expanded
    else {
        // Double capacity. The maximum size is 1<<16
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // Re-create space and free up the previous space, discarding the previous cached method for efficiency
        reallocate(oldCapacity, capacity, true); }... }Copy the code

conclusion

The method is to cache it in a hash table
Occupied is the number of current cache methods
_maybeMask + 1 is the size of the current hash table
Occupied + 2 > Capacity * 3/4

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Cache_t analysis for iOS low-level exploration

preface

Data structure for cache_T

Debug and print SEL and IMP with LLDB

Insert the process

First cache method

Create a memory

Methods the cache

Buckets capacity

conclusion

Cache_t analysis for iOS low-level exploration

preface

Data structure for cache_T

Debug and print SEL and IMP with LLDB

Insert the process

First cache method

Create a memory

Methods the cache

Buckets capacity

conclusion

Related Posts

IOS Advanced — Object and structure body alignment

Swift Advanced (ix) protocol and meta type

Swift progression (iv) Structures and classes