preface
We know that the essence of an object is an objC_Object structure, and the memory structure is a member variable. The nature of a class is the objC_class structure. There are member variables ISA (structure pointer 8 bytes), superclass(structure pointer 8 bytes), cache, and bits(structure pointer 8 bytes). The nature of ios objects and ISA we explore isa and the relation between class. Supperclasss is the parent of the ios class. We explore bits and their methods, properties, and protocols. What is stored in the cache? It literally means cache, so what do you cache and why do you cache? With that in mind, let’s explore. Objc source objC4-818 source address
cache_t
Cache is a cache_t structure as follows:
struct cache_t {
private:
explicit_atomic<uintptr_t> _bucketsAndMaybeMask;// Uintptr_t is 8 bytes unsigned long
union {
struct {
explicit_atomic<mask_t> _maybeMask;// uint32_t = uint32_t
#if __LP64__
uint16_t _flags;/ / 2 bytes
#endif
uint16_t _occupied;/ / 2 bytes
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache; // Structure pointer 8 bytes
};
/ /... Omit some method bodies for interference analysis
public:
unsigned capacity() const;
struct bucket_t *buckets() const;// Buckets () have methods
Class cls() const;
#if CONFIG_USE_PREOPT_CACHES
const preopt_cache_t *preopt_cache() const;
#endif
mask_t occupied() const;
void initializeToEmpty();
Copy the codeStructural analysis:
8 bytesUnsigned long integer variablebucketsAndMaybeMask8 bytestheA consortium(Union is mutually exclusive, shared memory, size depends on the largest element), _maybeMask,Flags,occupiedcache_tIs aThe structure of the bodyThe total size16 bytes.
From the view of the member variables are some plastic variables, and there is no desire to further explore, so whether there is a method like the structure analysis of the class bit? Buckets () is a pointer to the bucket_t structure that is used frequently in cache_t, so I guess bucket_t is the key to caching.
struct bucket_t *cache_t::buckets() const
{ // The memory load gets the first address of the bucket
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
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;
/* * omit parts of unparsed code */
inline SEL sel() const { return _sel.load(memory_order_relaxed); }
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const{ uintptr_t imp = _imp.load(memory_order_relaxed);
if(! imp)return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
SEL sel = _sel.load(memory_order_relaxed);
return (IMP)
ptrauth_auth_and_resign((const void *)imp,
ptrauth_key_process_dependent_code,
modifierForSEL(base, sel, cls),
ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return(IMP)imp; }Copy the codeAnalysis:
- through
bucketsAndMaybeMaskLoad the memorybucket_tStructure pointer. Bucket_t stores SEL and IMP. And arm64IMP in the former.SEL inOtherwise, SEL is in front and IMP is behind. Since the source code analysis below is for macOS, this is the second case.- Bucket_t can pass
sel()Methods andimp()Method to obtain SEL and IMP IMPThe (IMP)(IMP ^ (Uintptr_t) CLS) will pass such aExclusive or operationReturn to IMP, which is discussed in more detail below.
LLDB explore cache_t
LLDB tests whether the bucket stores IMP and SEL just as it did the bit. First define an object GyPerson and add an object method testFunction. GyPerson * P1 = [GyPerson alloc] initializes the P1 object in the main () entry function, then LLDB debugging.
(lldb) p/x GyPerson.class
(Class) $0 = 0x00000001000084a8 GyPerson Isa / / object
(lldb) p/x 0x00000001000084a8 + 0x10 Isa is offset down by 16 bytes
(long) $1 = 0x00000001000084b8
(lldb) p/x (cache_t*)0x00000001000084b8
(cache_t *) $2 = 0x00000001000084b8
(lldb) p *$2 / / cache_t values
(cache_t) $3 = {
_bucketsAndMaybeMask = {
std::__1::atomic<unsigned long> = {
Value = 4298515312
}
}
= {
= {
_maybeMask = {
std::__1::atomic<unsigned int> = {
Value = 0
}
}
_flags = 32792
_occupied = 0
}
_originalPreoptCache = {
std::__1::atomic<preopt_cache_t *> = {
Value = 0x0000801800000000
}
}
}
}
(lldb) p $3.buckets() / / to get buckets ()
(bucket_t *) $4 = 0x0000000100362370
(lldb) p *$4
(bucket_t) $5 = {
_sel = {
std::__1::atomic<objc_selector *> = (null) {
Value = (null)
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 0
}
}
}
(lldb) p [p testfunction1] // LLDB dynamically invokes methods
(lldb) p *$2
(cache_t) $6 = {
_bucketsAndMaybeMask = {
std::__1::atomic<unsigned long> = {
Value = 4302336176
}
}
= {
= {
_maybeMask = {
std::__1::atomic<unsigned int> = {
Value = 7
}
}
_flags = 32792
_occupied = 1
}
_originalPreoptCache = {
std::__1::atomic<preopt_cache_t *> = {
Value = 0x0001801800000007
}
}
}
}
(lldb) p $6.buckets() / / to get buckets ()
(bucket_t *) $7 = 0x00000001007070b0
(lldb) p $6.buckets()[1] // Pan down to get the second buckers()
(bucket_t) $8 = {
_sel = {
std::__1::atomic<objc_selector *> = "" {
Value = ""
}
}
_imp = {
std::__1::atomic<unsigned long> = {
Value = 48648
}
}
}
(lldb) p $8.sel()
(SEL) $9 = "testfunction1"
(lldb) p $8.imp(nil,$0) / / for imp
(IMP) $10 = 0x0000000100003aa0 (KCObjcBuild'-[GyPerson testfunction1] at main.m:29) (LLDB) p/x 48648 // IMP value hexadecimal display (int) $11 = 0x0000Be08 (LLDB) p/x 0x0000BE08 ^ 0x00000001000084a8 // value^ ISA (long) $12= 0x0000000100003AA0 //$12==$1, Verify xOR operation (LLDB) p/x 4302336176 //_bucketsAndMaybeMask value hexadecimal (long) $13= 0x00000001007070B0 // Find $13=$7?Copy the codeAnalysis:
isaDownward migration16 bytesTo obtaincatch_tbucket()In the storeSEL and IMPAnd there are more than oneIMPIs with theisaThe xOR operation of value^isa
Since bucket stores SEL and IMP, what are the member variables _bucketsAndMaybeMask, _maybeMask, and _occupied? What does it have to do with a bucket? LLDB debugging is against development practice, and retrieving bucket() every time you add a method is cumbersome. Try restoring the LLDB testing process in code.
Code restoration explores cache_t
@interface GyPerson:NSObject
-(void)testfunction1; - (void)testfunction2; - (void)testfunction3; - (void)testfunction4; - (void)testfunction5;
@end
@implementation GyPerson
-(void)testfunction1{}
-(void)testfunction2{}
-(void)testfunction3{}
-(void)testfunction4{}
-(void)testfunction5{}
@end
typedef uint32_t mask_t;
struct gy_bucket_t{
SEL _sel;
IMP _imp;
};
struct gy_cache_t{
struct gy_bucket_t * _buckets;
mask_t _maybeMask;
uint16_t _flags;
uint16_t _occupied;
};
struct gy_class_data_bits_t{
uintptr_t bits;/ / 8 bytes
};
struct gy_objc_class{
Class isa;
Class superclass;
struct gy_cache_t cache; // formerly cache pointer and vtable
struct gy_class_data_bits_t bits;
};
int main(int argc, const char * argv[]) {
@autoreleasepool {
GyPerson *p = [GyPerson alloc];
[p testfunction1];
// [p testfunction2];
// [p testfunction3];
// [p testfunction4];
// [p testfunction5];
Class gyclass=p.class;
struct gy_objc_class * g_class=(__bridge struct gy_objc_class *)gyclass;
NSLog(@"%hu-%u",g_class->cache._occupied,g_class->cache._maybeMask);
for(mask_t i=0; i<g_class->cache._maybeMask; i++){ struct gy_bucket_t bucket=g_class->cache._buckets[i]; NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp); }}return 0;
}
Copy the codeThe output is as follows:
1-3
(null) - 0x0
(null) - 0x0
testfunction1 - 0xbe10
Copy the codeThe code above opens the commented out methods testfunction2, testfunction3, testfunction4, and testfunction5 with the following output:
3-7
(null) - 0x0
(null) - 0x0
testfunction5 - 0xbe20
(null) - 0x0
testfunction4 - 0xbed0
(null) - 0x0
testfunction3 - 0xbec0
Copy the codeAnalysis:
Construct the cache_t structure. Refer to the source code to construct the objc_class structure, i.eobjc_classThe structure containsIsa, Superclass, Cache, bitsMember variables. The cache and bit structures also refer to source code.- structure
bucket_tStructure main instruction environment,SEL is first in MacOSIMP in - In the cache_t construct, the first element should be bucketsAndMaybeMask, but since
bucket()Acquisition needs ofThrough bucketsAndMaybeMask. The load ()“, plus we’re analyzing buckets, so we’ll replace them with Pointers to bucket_t. - As I add methods,
_maybeMaskandThe _occupiedValues have changed, indicating that maybeMask and Occupied are related to the number of cache methods.
Debugging summary:
- Cache_t caches sels and IMPs. Sels and IMPs are stored in buckets
There are many buckets.The value of the bucketsAndMaybeMaskIs the firstPointer address of bucket.
Is it? Testfunction1 is missing and there is no testfunction2? Why are there two empty SEL’s in front of the testFunction5 method?
insert
To solve the puzzle, look at how it inserts into the cache. Try a global insert search. Using GyPerson above, initialize the object and add testFunction1, testfunction2, testfunction3, testfunction4, testfunction5 methods, breakpoint debugging.
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
runtimeLock.assertLocked();
// Never cache before +initialize is done
if(slowpath(! cls()->isInitialized())) {return;
}
if (isConstantOptimizedCache()) {
_objc_fatal("cache_t::insert() called with a preoptimized cache for %s",
cls()->nameForLogging());
}
#if DEBUG_TASK_THREADS
return _collecting_in_critical();
#else
#ifCONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif ASSERT(sel ! =0 && cls()->isInitialized());
// Break time for the first time: occupied=0; newOccupied=1
mask_t newOccupied = occupied() + 1;
// The first time capacity() is 0, that is, oldCapacity=0, capacity=0
unsigned oldCapacity = capacity(), capacity = oldCapacity;
// The cache is empty when first entered
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
//capacity=1左移2，即2^2=4，capacity=4
if(! capacity) capacity = INIT_CACHE_SIZE;OldCapacity =0, capacity=4. FreeOld specifies whether to freeOld memory
reallocate(oldCapacity, capacity, /* freeOld */false);
}
//newOccupied+1<=capacity * 3/4; true CACHE_END_MARKER=1; non-true CACHE_END_MARKER=0
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
// Capacity <=8&&newOccupied+1<= Capacity CACHE_END_MARKER the value is 0 on the true host and 1 on the non-true host
else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
// Allow 100% cache utilization for small buckets. Use it as-is.
// If allowed to store full
}
#endif
else {
// INIT_CACHE_SIZE=4 for the real machine INIT_CACHE_SIZE=2 for the non-real machine
// Capacity Capacity is available. Capacity is expanded twice. Otherwise, capacity=INIT_CACHE_SIZE
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {// If capacity is greater than 2^15 capacity=2^15
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets();
mask_t m = capacity - 1;
// Compute the hash index using sel and capacity
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.
do {
// Set sel at bucket index if sel at bucket index is empty. Fastpath indicates that it is most likely true
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
// if sel exists at index
if (b[i].sel() == sel) {
// The entry was added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
return;
}
// FastPath is most likely true cache_next to resolve hash conflicts
} while(fastpath((i = cache_next(i, m)) ! = begin)); bad_cache(receiver, (SEL)sel); #endif/ /! DEBUG_TASK_THREADS
}
Copy the codeBreakpoint debug analysis (x86 MacOS) :
For the first timeInsert the testfunction1,capacity=4, occupied = 0,reallocateFour bucket memory Spaces are opened up,Insert againmethodsoccupied++.occupiedA value ofApproach number 1, starting at 0- When inserting the third method of testfunction3, capacity is doubled to 8.
Reallocate was relaunchedEight buckets of memory space - SEL,IMP insert is used first
cache_hash(sel, capacity – 1) to calculateThe subscriptAnd then according to theThe subscriptfindThe specifiedBucket, specified for the bucket callset()Method to insert SEL and IMP. That’s why buckets’ methodIt's not in order of insertionThe reason,bucketsIs essentially aHash linked list structureIs stored using the hash index. - When the set() method inserts SEL and IMP,
Check whether sel is under bucket first. If so, return; if not, insert again - Bucket memory opening rules:
For the first timeOpen up4Bucket memory spaceThree quarters ofThe rules,A: We are occupied with preparing for the final exams; b: We are occupied with preparing for the final examsWhen occupied is 1, the second insert method does not open up bucket memory spaceAllow full storage, CACHE_ALLOW_FULL_UTILIZATION=1. When the CACHE_ALLOW_FULL_UTILIZATION variable is 1, it indicates that full memory is allowed. For example, four buckets of memory are opened and the memory is full.Double capacity expansion rules. If the number is greater than 3/4, expand the capacityThird insertion method. Capacity is expanded twice if it has a value. Capacity is expanded twice if it does not. INIT_CACHE_SIZE is 4 on a real machine, and INIT_CACHE_SIZE is 2 on a non-real machine2 ^ 15
reallocate()
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
bucket_t *oldBuckets = buckets();// Get the first address of oldBuckets
bucket_t *newBuckets = allocateBuckets(newCapacity);// Get the first address of newBuckets
ASSERT(newCapacity > 0);
ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
// Set bucketsAndMaybeMask and maybeMask
setBucketsAndMask(newBuckets, newCapacity - 1);
if (freeOld) {// freeOld=truecollect_free(oldBuckets, oldCapacity); }}Copy the codeAnalysis:
AllocateBuckets open up memory, memory sizenewCapacity * bucket_tAdd capacityFreeOld = true,Release the old buckets. Insert testFunction1 and testfunction2 into testfunction1 and testfunction2. Insert testfunction3 into testfunction3 and testfunction3 into testfunction3.Release the oldThe bucket.
allocateBuckets()
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 a newCapacity bucket
bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
// Get the address of the last bucket pointer
bucket_t *end = endMarker(newBuckets, newCapacity);
#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.
// The last bucket sel=1, placeholder
end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
if (PrintCaches) recordNewCache(newCapacity);
return newBuckets;
}
Copy the codeAnalysis:
- Open up
How many bucketsMemory is made up ofCapacity valueThe decision,For the first timeOpen up Capacity for4. endMarker()Locate theThe last bucket, end->set(), put the last bucketSEL is set to 1.IMPSet toThe first bucketThe last bucket isPlaceholder bucket, no actual SEL and IMP are stored.
SetBucketsAndMask ()
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
// ensure other threads see buckets contents before buckets pointer
mega_barrier();
_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);
// ensure other threads see new buckets before new mask
mega_barrier();
_maybeMask.store(newMask, memory_order_relaxed);
_occupied = 0;
#elif __x86_64__ || i386
// ensure other threads see buckets contents before buckets pointer
//_bucketsAndMaybeMask stores the address of the first bucket
_bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);
// ensure other threads see new buckets before new mask
//maybemask=newCapacity-1
_maybeMask.store(newMask, memory_order_release);
_occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
Copy the codeAnalysis:
bucketsAndMaybeMaskstoreThe bucket first addressmaybemaskforCapacity-1Capacity is 4, maybemask is 3.maybemaskThe value of isThe actual number of bucketsBecause the last bucket is a placeholder bucket.
Bucket_t: : set, cache_hash
//mask=capacity-1
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES / / CONFIG_USE_PREOPT_CACHES = 1 real machine
value ^= value >> 7;//value=value^value move 7 bits right
#endif
return (mask_t)(value & mask);//value and mask and operation
}
#if CACHE_END_MARKER / / the real machine
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
#elif __arm64__ / / real machine
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i-1 : mask;
}
void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
ASSERT(_sel.load(memory_order_relaxed) == 0 ||
_sel.load(memory_order_relaxed) == newSel);
static_assert(offsetof(bucket_t,_imp) == 0 &&
offsetof(bucket_t,_sel) == sizeof(void *),
"bucket_t layout doesn't match arm64 bucket_t::set()");
// imp
uintptr_t encodedImp = (impEncoding == Encoded
? encodeImp(base, newImp, newSel, cls)
: (uintptr_t)newImp);
stp(encodedImp, (uintptr_t)newSel, this);
}
uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const {
/* * omit some code */
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
// xor returns IMP
return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
}
Copy the codeAnalysis:
cache_hashIt’s basically generatingThe hash index.cache_nextMainly to solveHash conflictencodeImpMethods toImp coding(uintptr_t) newImp ^ (uintptr_t) CLS namelyExclusive or operation.CLS have valueImp incoding.CLS no valueImp is equivalent toNo coding. CLS is isa, above LLDB last debugging can be seen, IMP encoding value xor ISA, and finally restore the IMP address.
Through the above analysis, we can add another diagram for easy understanding:
Conclusion:
cache_tThe value of bucketsAndMaybeMask in bucket() is the first bucket addresscache_tThe bucket() pointer function caches SEL and IMP- The number of buckets equals maybeMask+1
The last oneBucket is placeholder bucket SEL=1,IMP = bucket first addressbucketOpen up memory space toThree quarters ofFor the bounds, four bucket memory sizes are first opened. If it is larger than 3/4, the capacity needs to be expanded. The capacity needs to be expanded by 2 times for the real machine and 8 times for the non-real machine.The maximum expansion is 2 to the 15th.bucketStorage is done throughHash computes subscript storage, so SEL storage is not continuous, the essence is hash linked list structure.IMPisimp^isaThe result of an xOR operationExclusive or isa againcanRestore IMP pointer.