preface
This article continues to explore some of the issues that we left unexplored in our previous exploration of cache_t, including the following:
- Cache_t principle
- _bucketsAndMaybeMask explore
- Why increment mask by 1 when calculating capacity
- Access imp codec
1, _bucketsAndMaybeMask
The main uses of cache_t are _maybeMask and _occupied. This article will explore the use of _bucketsAndMaybeMask.
First, use BPPerson as an example for LLDB debugging. The code and result are as follows:
You only get the address of _bucketsAndMaybeMask from the diagram, and nothing else. There are a lot of calls to _bucketsAndMaybeMask globally, but you can see that setBucketsAndMask and buckets are used as follows:
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask) { uintptr_t buckets = (uintptr_t)newBuckets; uintptr_t mask = (uintptr_t)newMask; ASSERT(buckets <= bucketsMask); ASSERT(mask <= maxMask); _bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed); // newBuckets _occupied = 0; } struct bucket_t *cache_t::buckets() const { uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed); return (bucket_t *)(addr & bucketsMask); _bucketsAndMaybeMask = buckets}Copy the codeIn both pieces of code, the use of _bucketsAndMaybeMask is associated with buckets. Check buckets() to see if the starting address is the same as _bucketsAndMaybeMask.
It turns out that buckets’ first address and _bucketsAndMaybeMask are 0x00000001003623D0, which proves our conclusion. _bucketsAndMaybeMask represents buckets’ first address.
But is _bucketsAndMaybeMask all there is to it? Apparently not. In fact, _bucketsAndMaybeMask is a combination of bucket and maybeMask. When used, the value of _bucketsAndMaybeMask will be calculated with a mask to obtain the corresponding value.
When we explored mask() in the last article, we found that this function has multiple local definitions, which are actually functions in different schemas, for example:
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
mask_t cache_t::mask() const
{
return _maybeMask.load(memory_order_relaxed);
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
mask_t cache_t::mask() const
{
uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
return maskAndBuckets >> maskShift;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
mask_t cache_t::mask() const
{
uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
uintptr_t maskShift = (maskAndBuckets & maskMask);
return 0xffff >> maskShift;
}
#else
#error Unknown cache mask storage type.
#endif
Copy the codeFrom the mask() function in these different architectures, we can find that the value of mask is different. Some only use _maybeMask, while others need _bucketsAndMaybeMask. The Mac OS used in this test will follow a branch under Cache_mask_storage_may bank directly.
You can see maskShift and maskMask used in other architectures, which are static members defined in the cache_T structure. As shown below:
For example, in CACHE_MASK_STORAGE_HIGH_16, maskShift=48 indicates that if you want to take a mask, you simply move _bucketsAndMaybeMask 48 bits to the right, which corresponds to the implementation of mask() in this architecture.
For CACHE_MASK_STORAGE_OUTLINED in this test, it simply defines bucketMask (_maybeMask), which measures the value of mask; bucket, which may include: Add and to _bucketsAndMaybeMask and bucketMask.
2, access to IMP codec
When you cache a method, you actually cache SEL and IMP, both of which reside in the bucket_t structure. The previous article mentioned IMP access, but also do other operations, this section we will explore.
Bucket_t imp access source, respectively corresponding to set and IMP function, code as shown below:
Inline IMP imp imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, 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; #else #error Unknown method cache IMP encoding. #endif }Copy the codeThe set function is called to store imp, which first calls an encodeImp function as follows:
// Sign newImp, with &_imp, newSel, and cls as modifiers. uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const { if (! newImp) return 0; #if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH return (uintptr_t) ptrauth_auth_and_resign(newImp, ptrauth_key_function_pointer, 0, ptrauth_key_process_dependent_code, modifierForSEL(base, newSel, cls)); #elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR 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 codeA comparison of the code shows that xOR operations are performed both when stored and when read.
Store: imp ^ CLS
Read imp ^ CLS read imp ^ CLS
This is actually using the xor property of a = a ^ b ^ a, where CLS plays the role of B, in order to salt the stored value. The above code can be verified by LLDB debugging as follows:
Figure 1 shows the results stored when the method is cached for the first invocation, and Figure 2 shows the values read from the cache through the LLDB after the second invocation. The first storage value is 47472, the second time to read the value, the use of the value or class, the result is just the first storage newImp value, which can verify the Imp storage codec operation.
3. Why mask should be added 1 for capacity calculation
Before caching the method, we get the current capacity of cache_t, but when we look at the capacity() function, we see that mask + 1 is used every time. The code is as follows:
unsigned cache_t::capacity() const
{
return mask() ? mask()+1 : 0;
}
Copy the codeIn addition, there is a strange phenomenon in the LLDB debugging process, the code and debugging results are as follows:
When person prints cache_t in code before a method has been called, _maybeMask is 0 because no method has been called and no cache space has been created. However, when you call task2 with the LLDB directive, you see that _maybeMask has changed to 7 instead of 3 as mentioned in the previous article. This series of mysterious operation, what is the reason?
Why is the first call to method _maybeMask changed to 7 when debugging with LLDB? First verify that debugging with LLDB will not use our compiled debuggable source code. Write the following code in the insert function of the cache method:
As can be seen from the execution result, LLDB debugging will also go to this source code. Add the following code to your code:
The execution result is shown as follows:
After executing [person task2] in LLDB, the value is changed to:
- NewOccupied changes to 3 and Capacity to 4
- NewOccupied + CACHE_END_MARKER <= cache_FILL_ratio (capacity);
- CACHE_END_MARKER is defined as 1
Therefore, if the judgment condition is 4 <= 3, it is obvious that the capacity needs to be expanded. After the expansion, the capacity becomes 8, _maybeMask naturally becomes 7, and the number of cached methods becomes 1.
Why is it expanding here? Looking at the printed methods, you can see that when task2 is called, there are already two methods. Print the method name according to its SEL, and the result is as follows:
You can see that we’re calling respondsToSelector and the class methods, so we’re calling occupied 2 and newOccupied 3.
If _maybeMask is 7, why do we need to add 1 to capacity? In the print above, we can see that 0x1 is printed at the end and the bucket pointer points to the first one. You can also find the following code definition in the allocateBuckets function:
By default, a 1 is inserted at the end of the bucket, with the IMP pointing to the first bucket. This explains why we increment capacity by one. The purpose of adding 1 is to set a boundary between the bucket and whether the end has been reached.
That completes our exploration of cache_t, and I welcome your comments on the shortcomings of this article, as well as your continued exploration.