preface

In the previous exploration, we explored the structure of the class, which we can see from the source perspective

One of theClass isa,Class superclass,class_data_bits_t bitsWe’ve done that analysis before, and today we’re going to explore the rest of itcache_t cache.

Preliminary study on the structure of cache_t

Cache_t cache is, as the name suggests, a place to store a cache. So what exactly is he caching? Continue our exploration from the source perspective

As we can see,cache_tIs a structure that contains auintptr_tOf the generic type_bucketsAndMaybeMaskAnd a union, which in turn contains a structure and apreopt_cache_t *Of the generic type_originalPreoptCache.

_bucketsAndMaybeMask

As you can see from the source code, _bucketsAndMaybeMask is a uintPtr_t generic data structure, which can be simply interpreted as the uintPtr_t type

#ifndef _UINTPTR_T
#define _UINTPTR_T
typedef unsigned long           uintptr_t;
#endif /* _UINTPTR_T */
Copy the code

In fact, we can roughly think of it as just a bunch of numbers, and what’s stored in that bunch of numbers? Continue to look at the source below

In different architectures,_bucketsAndMaybeMaskThe things stored are not the same as in CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINEDWhen,_bucketsAndMaybeMaskIt’s actually abuckets_tThe pointer to theCACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRSWhen,_bucketsAndMaybeMaskThere is a mix of data in which the lower 48 bits are storedbuckets_tWhile the high 16 bits store is_maybeMaskThe value of the.

1. Architecture distinction

See so manyif-elseWe wanted to explore what they were referring to. After looking in the source code, it turns out that they represent different machine architectures, as follows

2. _bucketsAndMaybeMask in different architectures

In the source code, we see that under different architectures,_bucketsAndMaybeMaskThe relationship between them can be roughly summarized in the following diagram

Buket_t

As we see in the _bucketsAndMaybeMask above, its primary function is to store buckets. So what is this buckets? Find source discovery

It’s actually a pointbucket_tPointer to theta. Let’s seebucket_t

We were pleasantly surprised to find something familiarSELandimpThe existence of.

LLDB explore cache_t

At the source level, we basically found what we were looking for, which is the SEL and IMP stored in cache_t. Let’s continue the exploration from the LLDB perspective and continue to pull out our DMPeron

And before the method call, put a breakpoint on each, and then we’re going to start

Breakpoint analysis

  • So let’s go to the first break point, and we haven’t called any methods yet, okay

  • And then we go to the second break point, at this point[p1 say1],[p1 say2]Now that we’re done, let’s look at the data in memory

Two methods were called and found_occupied = 2,_maybeMask = 3(I used an Inter chip computer here). And then go ahead and get itbucketsAt the first address, which is zero, we print out empty, because it’s zerobucketsSo, moving on to get positions 1 and 2, we find the method we’re callingsay1,say2.

  • Let’s look at the third break point[p1 say1],[p1 say2],[p1 say3],[p1 say4]We’re all done, so I guess we’ll be able tobucketsFind them inside. Keep tuning

And we found, we didn’t find ourssay1andsay2And,_maybeMask = 7,_occupiedOr equal to2.

The problem summary

In the above experiment, we found several problems

  1. _maybeMaskand_occupiedWhat is the function of?
  2. Why is the storage of methods not sequential?
  3. Why callsay3,say4I don’t knowsay1,say2?

Take a look at the cache_t structure

By looking at what cache_t stores in the LLDB, we’ve found some questions, and with these questions in mind, we’ll go to the source code to find the answers. Since these questions are related to the cache_t structure, we’ll go there to find the answers we want. Cacht_t, we know it’s a cache, and since it’s a cache, it’s going to read and write, so we went into the source code and started looking for ways to do that.

The insert method

In the source code, we found one calledinsertAnd the parameters are respectivelysel,imp,receiver. It looks like this is the way to write to the cache that we’re looking for. Look at its implementation

Initializing a container

The method is a long one, so let’s look at the first part, so once we get into the method, let’s get itoccupiedAnd add to him1, because we are in the project first callDMPersonMethod, thereforeoccupied = 0The resultingnewOccupied = 1. And then getcapacityLet’s click on this method

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

mask_t cache_t::mask(a) const
{
    return _maybeMask.load(memory_order_relaxed);
}
Copy the code

It turns out that it actually gets the value of _maybeMask, or +1 if it’s not 0. Again, since no method was called before, oldCapacity = 0 here, and the reallocate method will be executed in the if-else below, where capacity is a constant, as we can see INIT_CACHE_SIZE = 4. Take a look at the reallocate method

Obviously, the purpose of this method is to initialize a newbucketsAnd in thefreeOld = trueTime to release the old onesbuckets. The most important way is tosetBucketsAndMaskAnd keep tracking it,

Since the MAC uses the Inter chip, so just look at the red box, here is thenewBucketsSet into the_bucketsAndMaybeMaskAnd at the same time willnewMaskThat is4-1 = 3Set into the_maybeMask._occupied = 0.The obvious part of this is to initialize the container we created. This also answers our question number one above,_occupiedIt’s essentiallycacheThe number of cache methods in_maybeMaskIs the maximum size of the cache container.

Insert data into

Looking at the code below, after the container has been initialized, the insert process naturally occursFirst of all, it gets the one that we initializedbucketsPointer to the first address of. Then through thecache_hashFunction to figure out the initial index that our data needs to be inserted, which we figured out herebegin = 1 It’s an algorithmmask ^ sel. So once we have the initial subscript, we go down to thedo-whileIn a loop.

  1. To obtainbucketsIn the memory space corresponding to the subscript position, see whether sel occupies the position, if not, directly insert data into the position, and_occupiedThe value of the add1
  2. If there is, this goes directly intowhileThe conditions,ithroughcache_nextI’m going to re-hash the function, and I’m going to get something that doesn’t equalbenginThe cycle continues.

Let’s look at the cache_next function

If it is our current Inter chip MAC environment, then directlyi+1 &mask, or yes in a real machine environmenti ? i-1 : mask. So that explains our problem number two,Because the storage is subscripted by the hash function, the data stored is unnecessary and discontinuous.

capacity

We have finished the process of say1 so far. We can see that the maximum number of containers is 3, so when the storage space is insufficient, there must be expansion. So let’s see what happens when we insert again

So what we see is, when the new data is inserted and meets a certain condition, we do nothing, we just insert it, otherwise the capacity will be doubled, so the condition, we see that it looks like this, right

  • On an Inter chip MAC,newOccupied + 1Less than or equal to the full capacityThree quarters of, the system does not expand the capacity.
  • In a real /M1 computer environment,newOccupiedLess than or equal to the full capacity7/8, the system does not expand the capacity.

We are using an Inter chip MAC, so when we insert the third data, that is say3, it will be expanded.

As you can see, the expansion process actually creates a new memory space, twice the size of the previous memory space, and frees the old memory space, so we have the answer to question 3,When callingsay3, the capacity expansion process will be performed and the previous cache will be released, so it cannot be foundsay1,say2Method is cached.

Summary of cache_T structure

We’ve basically explored the cache_t structure through a combination of source code and LLDB code debugging

  • _bucketsAndMaybeMaskIs mainly used for storagebucketsThis is the address of our storage container, and in different architectures, it might be stored_maybeMaskThis data.
  • _maybeMaskIs the maximum value that our container can store
  • _occupiedIs the number of methods cached in the cache

We also looked at the data insertion process. When the data inserted is more than 3/4 of the full capacity (the actual machine is 7/8), the container will be expanded and the old cache will be released. Here we have only studied the process of insertion, so the process of reading will continue to be explored in the next chapter.