preface

In the structural analysis of classes, we explored the class_datA_bitS_t bits class; Member, this article explores another member of the class, cache_t cache; , this article mainly explores the following points:

• Structural analysis of cache_t
• Analysis of bucket_T structure and buckets() storage mode
• insert()Function analysis
  • Method Cache step – Cache expansion
  • Procedure analysis to find the storage location – hash analysis

First, explore cache_t’s underlying storage structure

1.1 Analysis of cache source code structure definition

Cache, as we can guess from the name, is for caching, but what exactly is it for caching? We still use source code and LLDB debugging for analysis. Start by looking at the definitions in the source code. Find cache_t cache from objc_class and click on it to see the definition of cache_t. Here are the definitions of the members of cache_t:

struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; Union {struct {explicit_atomic<mask_t> _maybeMask; Mask #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; // 2 bytes, indicating the current cache usage}; explicit_atomic<preopt_cache_t *> _originalPreoptCache; / / 8}; / * * behind also contains other functions, and some of the large number of definition and initialize static variables, here did not show, can see in the source * /};Copy the code

In this part of the source code definition, we only see buckets, maybyMask, occupied and so on. We can only guess at their meanings, but we can’t really determine their meanings and usage. We don’t have to get caught up in this, though, because there are many more functions to cache_t, and we can see what they do to members to determine exactly what cache_t is caching.

There are many cache_t functions, but we can find a few key ones, which are defined as follows:

    mask_t mask() const; // 获取mask，mask_t其实是一个 uint32_t 类型
    void incrementOccupied(); // _occupied自增
    
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
    static bucket_t *emptyBuckets();
    static bucket_t *allocateBuckets(mask_t newCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
Copy the code

In each of the above methods, we find that they all operate on a structure, bucket_t. What does that structure do? Click to enter the definition, you can find the following code:

The members of bucket_t include sel and IMP, which represent the method name and method implementation, respectively. Therefore, cache_t is used to cache methods, and we can find them by simply visiting the corresponding bucket_t.

1.2 buckets analysis

1.2.1 Method for obtaining the LLDB Cache

We know from the last section that once you get a bucket_t, you can get a caching method, but cache_t doesn’t have a member that contains a bucket, so how do we explore that?

As you explore the underlying principles of classes, class_rw_t provides functions such as properties(), methods(), and so on to get corresponding properties, methods, and so on. Similarly, we can find a function buckets() in cache_t, which returns a pointer to bucket_t, and its function is implemented as follows:

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
Copy the code

As well as exploring the properties of the class, we also use LLDB debugging to get the methods cached in cache_t. The cache_t cache is the third member of objC_class, so the first address offsets the size of isa and superclass by 16 bytes. We’ll still use BPPerson as an example, but we’ll add a few more methods for testing. The code definition looks like this:

Let’s explore both cases and see what happens to cache_t when we don’t call a method versus when we call a method

• 1. The result of not calling the method is shown in the figure below:

As you can see, the _maybeMask and _occupied of the resulting caceh_t are both empty if the method is not called, meaning that cache_t does not cache the method if the method has not been called. It makes sense here, too, that there are no methods called, and there is certainly no caching required.

• 2. Let’s focus on how cache_t is cached in the case of method calls. Task1 = task1; task2 = task1;

Comparing the two results, we find that the change in the value of _occupied from 1 to 2 corresponds to the change in the number of method calls from 1 to 2, while the result of _maybeMask is always 3. We can guess that _occupied holds the number of cached methods, and _maybeMask holds the total number of values, i.e. the number of methods that can be cached. This will be verified later in the exploration.

Following the results in Figure 2, verify the method of obtaining the cache through LLDB. The steps and results are as follows:

The first call to buckets() uses $2(cache_t) to get a pointer to bucket_t *, where buckets() obtains a list of data and therefore values it according to the index. In the figure, a and C take the values of subscript 0 and 2, respectively, to get task2 and task1, which correspond to the two methods called, and no results at subscript 1.

From this, we can debug LLDB to get the cache method. It also shows that the invoked method is cached in cache_t, which stores the sel and IMP of the different methods in the corresponding bucket_t.

1.2.2 Buckets storage Analysis

The method of caching is obtained through LLDB, but what data structure does Buckets use for storage? An array? A linked list? Or any other data structure, which we’ll look at in this section.

First, let’s introduce the storage properties of arrays and lists:

• An array of
  • An array is a contiguous piece of memory. When an array is created, a fixed size of space is opened up, and the elements are closely connected
  • The characteristic of array is easy to query and can be obtained directly by subscript, but the number of elements need to be moved when inserting or deleting, so the efficiency is not high

• Linked list (here, singly linked list)
  • The memory space of the linked list is discontinuous. Each element is a node. The current node saves the address pointing to the next node
  • The characteristic of linked list is easy to insert or delete, only need to change the node point, but in the query, can not directly find the corresponding node according to the subscript, only from the first node to search backwards, so the query efficiency is low

Comparing these two data structures, we find that:

Buckets () can be taken according to the subindex, i.e. the memory space is continuous, so we can exclude the structure of a linked list.

Buckets () also exclude array data structures because they do not store values at index 1 but directly at index 2. Buckets () also exclude array data structures because they do not store values at index 1 but at index 2.

Since Buckets are not a linked list or an array, what other data structure can have spatial continuity but discontinuity in the storage of elements? There is actually a data structure called a hash.

A hash table, named after the English transliteration of hash, is also known as a hash table. A hash is a direct access to its in-memory data based on the key value, which is computed by a function called a hash function. Its storage features are as follows:

As we can see, buckets() are stored in a hash table, and we can guess that buckets() are stored in a hash table. To verify this, we can look for relevant methods in the source code. The following code can be found in the cache_t insert() function:

bucket_t *b = buckets(); mask_t m = capacity - 1; // 4-1=3 mask_t begin = cache_hash(sel, m); Mask_t I = begin; mask_t I = begin; // Scan for the first unused slot and insert there. // There is guaranteed to be an empty slot. do { if (fastpath(b[i].sel() == 0)) { incrementOccupied(); b[i].set<Atomic, Encoded>(b, sel, imp, cls()); return; } 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)); // If not, hash again to find the next locationCopy the code

From this code, we find two cache_hash() and cache_next() functions whose code is defined as follows:

According to the source code and comments, we can see that the cache_hash() function functions SEL as a key and cache buckets to store SEL+IMP. SEL gets the stored key by displacement, which is essentially a hash function. It also shows that buckets are actually stored in the structure of hash table. The following figure shows a schematic of the cache_t caching method:

Each bucket_t stores an SEL and IMP to cache methods that have been called, but those bucket_ts are not stored in a cache_T, because if you put them in a cache_t, Will make objC_class take up more and more space. Therefore, Apple sets up another piece of memory to store the bucket_t of the cache. The cache_T obtains the pointer of this area through buckets and then obtains the corresponding bucket_T by the subscript, which is the method of caching.

This section mainly introduces cache_t and bucket_t. The following figure summarizes the relationship between cache_t, buckets(), and bucket_t:Summary:

• Bucket_t is a structure that contains two members, SEL and IMP, which hold information about the methods used to cache
• Bucket_t is stored as an element in a hash table, and the cache_t obtains the beginning address of the hash table through the buckets() function
• Cache_t is a member variable of objc_class, so objc_calss has methods for caching

Two, methods cache process source analysis

The insert() function was mentioned in the last section of exploration, but why the sudden mention of this function? Because we want to explore how buckets are stored, we need to find where to start storing them, and by adding, deleting, and modifying, we find insert() right in cache_t. In this section, we explore the method caching process using the insert() function as a starting point.

2.1 Insert process

Insert () function source code can be divided into two parts, that is, capacity judgment and allocation and storage bucket, the following analysis of the two parts of the source code.

2.1.1 Determining whether to Expand the capacity

The occupied function changes from 1 to 2, but _maybeMask is always 3. So we assume that _maybeMask means the occupied function is occupied.

Just looking at a piece of code, which can be confusing, let’s break it down step by step:

• The value ranges from 850 to 851
  • newOccupied = _occupied + 1; That is, the current occupied number + 1, that is, the total occupied number after the current method is saved. The variable is used to determine whether to expand the capacity
  • OldCapacity == oldCapacity; oldCapacity == oldCapacity; oldCapacity == oldCapacity; So if you look at the occupied() and the capacity() function

Mask_t cache_t::occupied() const {return _occupied; Unsigned cache_t::capacity() const {return mask()? mask()+1 : 0; } // mask() is taken from _maybeMask or _bucketsAndMaybeMask. Mask_t cache_t::mask() const {return _maybemask.load (memory_order_relaxed); } mask_t cache_t::mask() const { uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed); return maskAndBuckets >> maskShift; }Copy the code

• Lines 852 through 856: the condition for caching the first method, where the occupied number is 0 and the capacity is 0, so an initial value is assigned to the capacityINIT_CACHE_SIZEIn the source code, the macro is defined as 4. And then it callsreallocateFunction to open up storage space.

  INIT_CACHE_SIZE_LOG2 = 2, INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2) // Move 1 2 bits left to get 4Copy the code

• Lines 857 to 863: No more operations are required to determine that capacity is not exceeded.
  • Here we call the cache_fill_ratio function to get 3/4 of the load factor, and no expansion is needed beyond that range

  // 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;
    }
  Copy the code

• Line 865 to 871: The capacity needs to be expanded. Double the capacity. Reallocate: Reallocate: reallocate: Reallocate: Reallocate: Reallocate: Reallocate: Reallocate: Reallocate: Reallocate: Reallocate: Reallocate

This function does the following:

Obtain the buckets of the current cache

2. Open memory for the new buckets according to the new capacity

3. Set buckets and mask

4. Decide whether to release the old space according to freeOld

A comparison of this is that when you cache the first method, there’s no old space, so you don’t need to free it; When expanding capacity, after newly opened up space, old space does not need, want to release so. As you can see here, after the expansion, the methods that were originally cached will be cleared and will be re-cached in the newly opened memory when called again.

2.1.2 Procedure for storing buckets

After capacity development or expansion, storage is required. This part of the code is shown in the figure below:

• Lines 873 to 876: These lines are to prepare the data, to obtain the current buckets, and to obtain the storage location through the hash function
• Line 880 ~ 893: These lines are being stored. The following steps are analyzed
  • First, check whether there is no value in the current position, that is, b[I].sel() == 0. If there is no value, increase the number of occupied values by 1, and store bucket_t
  • If there is a value in the current position, then check whether it is the same method as the one saved. If so, return directly
  • If no, the system performs a hash to calculate the next storage location and repeats until the final storage location is the same as begin. That is, the memory is full. In this case, the system does not store the memory and directly calls the bad_cache function.

2.2 Verifying the cache process

To verify this process, create a new target in the objc source code and debug it as follows:

When task1 is called for the first time, check cache_t from LLDB as follows:

Step to [Person Task2], check the result again as follows:

In the command output, the total capacity is 3, and the occupied capacity is 1.

Select * from LLDB where task3 is executed and select * from LLDB where task3 is executed.

The result shows that the total capacity before the call is 3 and the occupancy is 2(task1 and task2); After calling Task3, the total capacity is 7 and the occupancy is 1. It is clear that the capacity was expanded when task3 was called, and the previously cached task1 and Task2 have been cleared. In this case, only Task3 is stored.

When task1 is called the second time, the LLDB debug result is as follows:

After task1 is called, it is found that the _occupied changes to 3, that is, task3, TASK4 and TASK1 are called after capacity expansion, and sel can also be fetched according to the subscript. Therefore, it can be verified that the cached methods will be cleared during capacity expansion and will be cached again when the next call is made.

Third, summary

The above is a preliminary exploration of the caching process of the method, but there is some confusion along the way:

• Why do we subtract 1 when we open up space, and what does CACHE_END_MARKER mean
• What is the difference between _maybeMask and _bucketsAndMaybeMask? How to use it?
• What does IMP do when storing and reading?

These questions are still explored in this article, and will continue to be explored in the following chapters, welcome to continue to pay attention.