This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge
Cache Underlying Analysis
Cache Structure Guess
So when we were getting bits, we were getting bits by memory translation, so we can get cache by memory translation as well. Isa and Superclass are both 8 bits, so you need to shift 16 bits to get the cache. We get the address of the LGPerson class in the LLDB, shift it 16 bits, convert it to cache_t *, and print out the contents.
Here we have our cache_t data.
Compare the structure in the source code to prove that it is indeed cache_t data. At this point we don’t know which data we want, so we can look at the methods in the structure and see which data to add or delete.
We see that most of the methods in the structure operate on bucket_t, so let’s click on bucket_t.
Found imp and SEL inside.
LLDB proves the cache structure
Let’s find out where we can get bucket_t. We can use the cache_t we got earlier and print _bucketsAndMaybeMask
We found that we couldn’t get the value inside. Let’s switch targets and try it in _maybeMask.
Discovery is still not what we want. Let’s go to the _originalPreoptCache.
When we find that _originalPreoptCache is not the data we want, we go to the method.
We found buckets() in the struct method and return a pointer to the struct bucket_t. Let’s verify this.
We found that the values of SEL and IMP are null, but they are exactly what we want. Why is sel, IMP empty here? Because this is in the cache, we need to call the method before we can cache the method in the cache. Let’s implement the saySomething method.
And then get the data again.
Buckets are actually stored in a hash array.
The hash array
A Hash table (also called a Hash table) is a data structure that is accessed directly based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. The mapping function is called a hash function, and the array that holds the records is called a hash table. Hash table has the problem of hash conflict, so we use the hash function to get two indices, and the hash function gives us the same indices. So how to solve this problem, one way is the zipper method.
The implementation of the zipper method is relatively simple, the combination of the list and array. That is, create an array of linked lists, and each cell in the array is a linked list. If hash conflicts are encountered, add the conflicting values to the list.
Back to buckets, [1] here is not to take the second element of the array, but to take the memory translation.
Verify the value with memory translation:
Found it was.
We see that we got the bucket_t structure, but our _sel value is empty, so we go to the method area to see if there is a method return _sel.
We found a get method in the method area that looks like sel, so let’s try it out.
And we did get sel, so let’s look at IMP.
An IMP – like GET method has been found. Let’s try it out.
It turns out you did get imp.
Verify the cache structure outside the source environment
Advantages:
- Suitable for situations where the source code cannot be adapted
- Omit the LLDB procedure and the operation just needs to run
- Small scale sampling, more clear to the underlying structure
Create method
First of all, we know that we’re going to get the cache, and we know that the cache is in class, so we’re going to get the data structure for objc_class.
We changed the data structure of the class to include only members, and isolated the name change from the system’s. Next we’ll change the missing data structures cache_t and class_data_bits_t to our own structures in the same way.
Since we know that our system supports __lp64__, we can remove the if. What we need here is _maybeMask, _flags, _occupied, so let’s remove explicit_atomic
Mask_t is missing here, so let’s click on it in the source code.
We find that mask_t is unit32_T, and finally we get the structure. Let’s simplify class_data_bits_t:
Simplified:
Because we’re going to be using bucket_t, so we’re going to take the bucket_t out as well. Original structure:
Since I’m using a MAC, this simplifies:
Next, the code implementation:
So here we’re going to take LGPerson’s class, and we’re going to force it into our own custom class, and we’re going to get the data in there.
It turns out it works, so let’s try printing the occupied and maybemask.
I realized that the numbers printed out were ridiculously large. There is a problem with the data structure we obtained. What went wrong? The reason for this is that our ls_objc_class is missing one member, which is isa inherited from objc_object. Because the data structure is one to one, we now have a structure that assigns the value of isa to superclass. Instead, the superclass value is assigned to cache. Let’s add isa and try to print it again.
Finally printed out what we wanted.
Let’s write a for loop and print out the data that we want. Because we need to get the bucket_t data, we need to find a way to get the bucket_t data out. So, let’s look at how the cache gets bucket_t.
The bucket_t is obtained using _bucketsAndMaybeMask. Uintptr_t _bucketsAndMaybeMask = struct ls_bucket_t *buckets. And then we can write a for loop.
Let’s run it.
Turns out sayNB1 did make it into the cache. Try another sayNB2 method.
Try printing by running an extra sayNB3 method.
We found a problem, we started printing 1 ======= 3, here is 1 =====7, and the cache method is only sayNB3. Let’s try adding a class method.
You get the same result. Let’s go ahead and add an object method, sayNB4.
Class methods are not stored in the class cache. So let’s init that object. Comment out the method you called before.
Run it and find the following print:
We didn’t write the init method, so this prints out the init method, saying that we’re calling the init method in NSObject.
There’s a problem. Why did the occupied and maybemask change from 1 and 3 to 1 and 7? Let’s explore how this works in cache.
Cache insert process
So let’s think about the pointcut, we now have a cache, and there must be an insert in the cache, because there must be a write so that there can be a read, and that’s what we did with sayNB1 and sayNB2. So what we’re going to do is we’re going to find the method of insertion, and we’re going to find in the structure:
Let’s click on this method and see.
When we first come in, our cache is empty, so pay attention to the if function. So let’s see what INIT_CACHE_SIZE is, and click on it.
So let’s click on INIT_CACHE_SIZE_LOG2 and see what that is.
INIT_CACHE_SIZE_LOG2 is found to be 2.(1 << INIT_CACHE_SIZE_LOG2), so this means that 1 is moved two bits left in binary and is equal to 4 in decimal. So INIT_CACHE_SIZE equals 4. So capacity equals 4. Let’s click RealLocate to see what’s going on.
As you can see here, this method creates a new bucket and assigns values to buckets and masks. Click on this method to see if you want to do this.
This method assigns buckets to _bucketsAndMaybeMask and mask to _maybeMask. So why is the occupied set to 0? Because the SEL and IMP haven’t been inserted yet. Now let’s move on to the next part of the method.
We got capacity is equal to 4, so mask_t m is equal to 4 minus 1 is equal to 3. Begin is the location of the occupied index calculated by hashing, and the incrementOccupied method below tells us that the occupied value is occupied. We see that the occupied operation is a do while loop. while (fastpath((i = cache_next(i, m)) ! = begin)) means to look up from the hash table. If the above condition is not true (index conflict), then the new index is calculated using cache_next and then the lookup is inserted. If (b[I].sel() == 0); if (b[I].sel() == 0); if (b[I].sel() == 0);
If (b[I].sel() == sel) == sel; if (b[I].sel() == sel) == sel;
Why did _maybeMask suddenly become 7?
Let’s look at the second entry.
So the condition here is newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity), newOccupied so we’re going to look for the previous assignment and we find that it’s
CACHE_END_MARKER goes in and finds
Cache_fill_ratio looks like
Occupied + 2 <= (capacity * 3/4); Occupied + 2 <= (capacity * 3/4); Why expand at three quarters of capacity (load factor)? This is because the space utilization is better when the load factor is 0.75, and another reason is that the hash conflict can be avoided effectively when the load factor is 0.75.
This condition is when you support 100& buckets, An insert is normal if capacity is less than FULL_UTILIZATION_CACHE_SIZE and newOccupied + CACHE_END_MARKER <= capacity.
Occupied + 2 > (capacity * 3/4); 4*2 = 8; _maybeMask = capacity-1 = 8-1 = 7;
This is why _maybeMask changed from 3 to 7.
So when is the second expansion? Let’s figure out that x plus 2 is greater than 8 times 3/4, and x is equal to 5. So when we add the sixth method, we’re going to expand it.
Let’s start with sayNB2, because when sayNB2 was expanded, it cleared the previous method, so let’s run it.
It was found that the sixth method was added (the second method was expanded, so calculate the first method, sayNB7 is the seventh method), that is, when sayNB7 was expanded.
Why have all the previous methods been emptied?
We noticed that when we expanded,
The reallocate method here is passing true.
This parameter indicates whether or not to free up the old space, because true is passed during expansion, which means that during expansion, all the previous memory addresses will be cleared. Why do we empty instead of just putting the previous method into the newly opened container? That’s because if we were to put the previous method into the new container, it would take a lot of memory and a lot of performance to shift the array, much more than if we were to insert it into the cache, so we’re not going to put the previous method into the new container. In addition, the method that was called before may not be called a second time.
conclusion
1. What’s the occupied?
-
_occupied indicates the number of SEL-IMPs occupied in the final hash table (meaning the number of SEL-IMPs stored in the occupied memory);
-
Init causes occupied changes
-
Attribute assignment, which is also implicitly called, causes the occupied change
-
Method calls, resulting in the occupied change
2. When will the expansion take place
- If _occupied + 2 is > (current occupied size * 3/4), expand the size to twice the size of the occupied area.
- If the current volume size is 4, then it is time to add a third volume (2 + 2 > 3).
3. Why is the previous method cleared after expansion
- That’s because if we were to put the previous method into the new container, it would take a lot of memory and a lot of performance to shift the array, much more than if we were to insert it into the cache, so we’re not going to put the previous method into the new container.
- Methods that were called before may not be called a second time.
4. Why is the method print not continuous
- Because sel-IMP’s storage calculates subscripts through the hash algorithm, the subscripts are random and not fixed.
5. Cache_t Flowchart
