preface
Recently, I occasionally went out for an interview to understand the current iOS market and interview questions. One of the questions that gets asked a lot is the principle of reference counting. Back to check the data found that the answer was very bad, so I wrote a separate article here to record. There is only one question in this article: where are the numbers of reference counts? Other questions mentioned at the end of this article will be addressed separately.
Preliminary knowledge
To answer this question, we need to understand three things.
Tagged Pointer
This is explained in detail here, briefly, on 64-bit systems, for values small (how small? The pointer to an object already stores the value itself, rather than pointing to an address and fetching the value of the object. As you probably know, if it’s Tagged Pointer then you don’t have to create an object.
We can also see apple's introduction to Tagged Pointer features in WWDC2013's Session 404 Advanced in Objective-C video: Tagged Pointer is used to store small objects, such as NSNumber and NSDate 2: The Tagged Pointer is no longer an address, but a real value. So, it's not really an object anymore, it's just a normal variable in an object's skin. Therefore, its memory is not stored in the heap and does not require malloc and free. 3:3 times more efficient in memory reading, creating 106 times faster than before.Copy the code
So let’s test that out.
NSLog(@"%p",@(@(1).intValue)); //0x127 NSLog(@"%p",@(@(2).intValue)); // tag = 0, 0, x2 = 2; // tag = 0, 0, x2 = 2 NSLog(@"%p",@(@(1).doubleValue)); //0x157 NSLog(@"%p",@(@(2).doubleValue)); // double tag = 1,0, x2 = 2 Obviously 0x127 and 0x257 are not addresses, so @(1) and @(2) are not objects, but ordinary variables.Copy the codeSince it is Tagged Pointer, there must be a tag. After testing, it is found that different value types have different tags.
The unsigned long and long long have the same tag value 37. Of course other types have the same.Copy the codeWhen does the NSNumber object Tagged Pointer become invalid? If the value and tag take up more bytes than the address length (8 bytes 64-bit), it will expire:
Why to say, rather than exceed, I also struggle with this, specifically look at the following example.Copy the codeAs an example, for double, the results for other types may be slightly different, since the tag has different values and takes up different bits.
Int 17:1001, 5 bits; Long long 37:100101, 6 bits; Double 57:11101, 6 digits. .Copy the codeSo 64 minus the occupied tag bits, the remaining bits to represent the value, can represent the range of the same.
Double pow(double, double) returns a value of type double. NSLog(@"%p",@(pow(2, 55) - 3)); //0x7ffffffffffffc57 is a double tag, 0x7ffffffffffffc57 is a double tag, 0x7ffffffffffffffc57 is a double tag. Binary is 0... 0 (9) 1... 1(53)00(2). And that's why I'm kind of struggling with the negative 3 here, because the binary representation has two zeros behind it, and you can have more than three; The system must have its own considerations for doing so. Maybe I misunderstood, and I hope you can correct me. NSLog(@"%p",@(pow(2, 55) - 2)); // 0x6030002C50c0 is simply an address, there is no 57 tag in it, so Tagged Pointer is invalid. We can see from this example that the tag takes up 8 bits, 64-55 = 9, 9-1 = 8, because the first bit is used to represent positive and negative numbers. Above we tested that 57 takes up 6 bits, why this value takes up the longest 56 bits, I don't know. To check whether Tagged Pointer is enabled, you can print the following statement in the Runtime source code. NSNumber *number = @(pow(2, 55) - 3); NSLog(@"%d",((uintptr_t)number & 1UL) == 1UL); //true number = @(pow(2, 55) - 2); NSLog(@"%d",((uintptr_t)number & 1UL) == 1UL); //falseCopy the codeSo far, I know that Tagged Pointer can be enabled on the following classes: NSDate, NSNumber, and NSString. The above examples are just NSNumber.
Tagged Pointer is not enabled
This is the result of the above example when not enabled, indicating successful shutdown.
NSLog(@"%p",@(pow(2, 55) - 3)); //0x6030002ccbc0 NSLog(@"%p",@(pow(2, 55) - 2)); //0x6030002ccc50 NSNumber *number = @(pow(2, 55) - 3); NSLog(@"%d",((uintptr_t)number & 1UL) == 1UL); //false number = @(pow(2, 55) - 2); NSLog(@"%d",((uintptr_t)number & 1UL) == 1UL); //falseCopy the codeNon-pointer isa
We’ve always thought of instance objects’ ISA as pointing to class objects, and we’ve even seen the source code for this.
typedef struct objc_object *id
struct objc_object {
Class _Nonnull isa;
}
Copy the codeIn fact, this is the previous version of the code, the current version of the code has long changed.
struct objc_object { private: isa_t isa; . }Copy the codeSo it is not true that instance isAs refer to class objects. Now the isa of the instance object is an ISA_T union, which stores a lot of other things, including reference counting, as you might have guessed; If non-pointer is enabled on the instance object, assignment is made to other members of ISA, otherwise only to CLS.
union isa_t { Class cls; . (There are many other members, including reference count counts)}Copy the codeObjc-runtime-new. m; / / Disable non-pointer; / / disable non-pointer; / / disable non-pointer; / / disable non-pointer; / / disable non-pointer;
1: contains swift code; 2: The SDK version is earlier than 10.11. 3: The runtime reads the image and finds that the image contains __objc_rawisa. OBJC_DISABLE_NONPOINTER_ISA=YES added by the developer to the environment variable; 5: Some classes that cannot use non-pointer, GCD, etc. 6: Parent class is closed.Copy the codeCreate a new Person class and check out the ISA structure with OBJC_DISABLE_NONPOINTER_ISA=YES/NO.
OBJC_DISABLE_NONPOINTER_ISA does not necessarily use non-pointer because it states that there are other conditions that turn non-pointer off. So we create our own Person class that inherits from NSObject so that we can control whether or not we use non-pointer simply by setting OBJC_DISABLE_NONPOINTER_ISA in the environment variable because we exclude conditions other than 4.Copy the codeDo not use non-pointer ISA
isa_t isa = { Class class = Person; uintptr_t bits = 4294976320; struct { uintptr_t nonpointer = 0; uintptr_t has_assoc = 0; uintptr_t has_cxx_dtor = 0; uintptr_t shiftcls = 536872040; uintptr_t magic = 0; uintptr_t weakly_referenced = 0; uintptr_t deallocating = 0; uintptr_t has_sidetable_rc = 0; uintptr_t extra_rc = 0; Is_t isa = {Class Class = Person; }} the source code does not use a non-pointer to the class of isa. The rest of the values are the default values and are not used in the source code.Copy the codeUse a non-pointer ISA
isa_t isa = { Class class = Person; uintptr_t bits = 8303516107940673; struct { uintptr_t nonpointer = 1; uintptr_t has_assoc = 0; uintptr_t has_cxx_dtor = 0; uintptr_t shiftcls = 536872040; uintptr_t magic = 59; uintptr_t weakly_referenced = 0; uintptr_t deallocating = 0; uintptr_t has_sidetable_rc = 0; uintptr_t extra_rc = 0; }} extra_rc is a reference count with nonpointer = 1 enabled.Copy the codeThe assignment to ISA is when the alloc method is called, and the initIsa() method is entered internally, so you can go inside and see what the difference is.
objc_object::initIsa(Class cls, bool nonpointer, bool hasCxxDtor) { if (! nonpointer) { isa.cls = cls; } else { isa_t newisa(0); . (Member assignment)...... isa = newisa; }}Copy the codeSideTable
Hash tables, one of the more important data structures, as you might have guessed, have to do with object reference counting; If the object is not Tagged Pointer and non-Pointer is turned off, the reference count for the object is stored using SideTable. Let’s take a look at the structure definition, and let me talk about what’s used.
Struct SideTable {// lock spinlock_t slock; // refcnts; // Weak_table_t weak_table; . }Copy the codeAfter starting the application, the first time we see the SideTable is when the Runtime reads the Image.
void map_images_nolock(unsigned mhCount, const char* const mhPaths[], const struct mach_header *const mhdrs[]) { ... static bool firstTime = YES; if (firstTime) { AutoreleasePoolPage::init(); SideTableInit(); }... } static void SideTableInit() { new (SideTableBuf)StripedMap<SideTable>(); }Copy the codeMap_images_nolock is called multiple times, because ImageLoader loads a bunch of images into memory, and then tells the Runtime to read a bunch of images, and yes the Runtime starts processing classes from the image; The SideTableInit() method is executed only once. SideTableInit uses the inside of SideTableBuf, and SideTableBuf is defined as follows.
alignas(StripedMap<SideTable>) static uint8_t SideTableBuf[sizeof(StripedMap<SideTable>)]; The sizeof (StripedMap < SideTable >) = 4096; Alignas (StripedMap<SideTable>) stands for byte alignment and aligns the starting position of each element in the array to a multiple of 4096. It also aligns each element in the array to size 4096. So this sentence is reduced to static uint8_t SideTableBuf[4096], that is, define an array of 4096 uint8_t size type, each element is 4096 size, name is SideTableBuf; New (SideTableBuf)StripedMap<SideTable>() in SideTableInit(). You'll find that this sentence doesn't mean anything, and it will work just as well after you comment it. SideTableBuf is initialized by SideTableBuf. See below. Above the definition of SideTableBuf is a comment like this. We cannot use a C++ static initializer to initialize SideTables because libc calls us before our C++ initializers run. We also don't want a global pointer to this struct because of the extra indirection. Do it the hard way. SideTables can't be initialized using C++ static initializers because libc calls us before the C++ static initializers run. We also don't want to use a global pointer to point to SideTables because of the extra cost. But we have to do this. Don't worry, here's the answer. What is C++ static initializer? You can find it in the runtime source code. There is such code in objC-os.mm. size_t count; Initializer *inits = getLibobjcInitializers(&_mh_dylib_header, &count); for (size_t i = 0; i < count; i++) { inits[i](); } SideTableInit() is executed before map_images_nolock. Let's print out one of the method names. . libobjc.A.dylib`defineLockOrder() at objc-os.mm:674 ...... We then make a breakpoint in the defineLockOrder() method to trace a wave. __attribute__((constructor)) static void defineLockOrder() { ...... SideTableLocksPrecedeLock(&crashlog_lock); . } void SideTableLocksPrecedeLock(const void *newlock) { SideTables().precedeLock(newlock); } will then enter this method. static StripedMap<SideTable>& SideTables() { return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf); } You can see that SideTableBuf is already used here, so SideTableBuf must have been assigned ahead of time. The SideTableInit() method is called after the initializer call in C++, and that's what the comment says. Translate it into Plain English: SideTableInit() is a bad way to initialize SideTable, because initializer for C++ is executed before SideTableInit(), and SideTable is already used at that point. That's why we use static global variables to initialize SideTable as soon as the file is loaded.Copy the codeYou’ll often see this code in the Runtime source code, but it’s also used in the INITIalizer call phase.
SideTable &table = SideTables()[this];
static StripedMap<SideTable>& SideTables() {
return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}
Copy the codeSo it’s important to understand what this means. StripedMap is a template class. Those familiar with C++ should be familiar with this. Let’s see what StripedMap<SideTable> will generate.
Struct PaddedT {SideTable value; struct PaddedT {SideTable value; }; PaddedT array[64]; // get the hash of p, Static unsigned int indexForPointer(const void *p) {uintptr_t addr = reinterpret_cast<uintptr_t>(p); return ((addr >> 4) ^ (addr >> 9)) % 64; } public: T& operator[] (const void *p) { return array[indexForPointer(p)].value; } const T& operator[] (const void *p) const { return const_cast<StripedMap< SideTable >>(this)[p]; }... }Copy the codeThe StripedMap contains a PaddedT array. The StripedMap overloads the [] symbol, and takes the PaddedT array based on the hash value of the parameter. The array contains the SideTable. Now understand what reinterpret_cast means.
Reinterpret_cast: Converts a pointer to another type of pointer, etc., which we don't need to dig into.Copy the codeso
SideTable &table = SideTables()[this]; static StripedMap<SideTable>& SideTables() { return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf); } means: To convert SideTableBuf to StripedMap<SideTable>* and return, you use SideTableBuf as a StripedMap. That's why you write alignas(StripedMap<SideTable>). So each element of the SideTableBuf array corresponds exactly to a StripedMap<SideTable> object.Copy the codeNow, you have to pay special attention here, is there a hash collision?
We create two different classes Person and Car and print out the hash value obtained by indexForPointer. (addr >> 4) ^ (addr >> 9)) % 64; Addr is the address of the instance object. This formula is written haphazardly, but it doesn't show anything. Person *one = [[Person alloc] init]; NSLog(@"%p",one); //0x60200000bf30 105690555268912 indexForPointer(105690555268912) = 44; Car *two = [[Car alloc] init]; NSLog(@"%p",two); //0x6030002c9710 105759277618960 indexForPointer(105759277618960) = 58; It's going to be a different hash, so we can manually change the hash algorithm and set all the hashes to 1, and see if it works. Which is to change this method. static unsigned int indexForPointer(const void *p) { return 1; } then we print the retainCount for one and two to see if it's correct. [one retain]; NSLog(@"%d",[one retainCount]); //2 [two retain]; NSLog(@"%d",[two retainCount]); // how does the system resolve hash conflicts and successfully store values? Let's move on.Copy the codeGet into the business
Let’s start by looking at where reference counts are stored. So let me write down my judgment priority.
1: Indicates whether the object is Tagged Pointer. 2: Indicates whether non-pointer is enabled on the object. 3: Non-pointer is not enabled on the object.Copy the codeIf 1 is satisfied, 2 is not judged, and so on.
Tagged Pointer object
Retain.
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) { if (isTaggedPointer()) return (id)this; . }Copy the codeWhen the release.
bool objc_object::rootRelease(bool performDealloc, bool handleUnderflow) { if (isTaggedPointer()) return false; . }Copy the codeWhen the retainCount.
uintptr_t objc_object::rootRetainCount() { if (isTaggedPointer()) return (uintptr_t)this; . }Copy the codeThis shows that there is no reference counting operation on Tagged Pointer and the reference count simply returns its own address.
Opens the Non – pointer
Retain.
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) { ... Addc (newISa.bits, 1, 0, &carry); . }Copy the codeWhen the release.
bool objc_object::rootRelease(bool performDealloc, bool handleUnderflow) { ... The extra_rc value of isa is subc(newISa.bits, 1, 0, &carry); . }Copy the codeWhen the retainCount.
uintptr_t objc_object::rootRetainCount() { ... Bits. Extra_rc is 0, not 1, when alloc creates a new object. uintptr_t rc = 1 + bits.extra_rc; . }Copy the codeIf non-pointer is enabled on an object, reference counting is stored in isa.
Non-pointer ISA is not enabled
This is the most troublesome, because you’re using SideTable, which has a lot of logic in it; Taking the Person example above, remember the address of the object. Retain.
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) { ... sidetable_retain(); . } id objc_object::sidetable_retain() { SideTable& table = SideTables()[this]; }Copy the codeThe internal implementation of SideTable has to be clarified at this point, so there is no way to continue to look at the code without clarifying it.
SideTable has three structures. Spinlock_t: lock, not to mention, a library that supports a multithreaded environment must consider this; Weak_table_t: weak form is this, which is used to deal with weak references, but this article does not speak; RefcountMap: Reference table, reference count is stored in this table. Typedefs objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap; Smelly and long, originally wanted to expand out the class, but found that the class will be very large, and difficult to understand; So I'm just going to do a little bit of logic here, if you want to go into it. When we first retrieved the table from SideTables()[this], the refcnts content in the table was empty. (we omitted spinlock_t and weak_table_t) : SideTable table = {... RefcountMap refcnts = { BucketT *Buckets = NULL; unsigned NumEntries = 0; unsigned NumTombstones = 0; unsigned NumBuckets = 0; }... } then size_t &refcntStorage = table.refcnts[this]; What does this sentence mean? RefcountMap inherits from DenseMapBase, DenseMapBase overloads the [] operator, so it will enter []. The following code is part of my expanded code for easy understanding. class DenseMapBase { ... // The purpose is clear, Is to get a pair<DisguisedPtr<objc_object>, size_t> size_t &operator[](DisguisedPtr<objc_object> &&Key) { pair<DisguisedPtr<objc_object>, size_t> &reslut = FindAndConstruct(Key); return reslut.second; }... } One detail needs to be noticed here, because we pass in this and the DisguisedPtr<objc_object> is received here. So the initialization method of the DisguisedPtr is triggered, so this is transformed into the following object. class DisguisedPtr Key = { uintptr_t value = 18446638383154282704; } Let's see what FindAndConstruct() does. Pair <DisguisedPtr<objc_object>, size_t>& FindAndConstruct(const DisguisedPtr<objc_object> &Key) {// First define a pair object used to receive the result, We must be familiar with the pair, which is equivalent to a key-value pair in the dictionary. // pga. first is the instance object address transformed into DisguisedPtr< objc_object > class, and pga. second is the reference count number of the object. pair<DisguisedPtr<objc_object>, size_t> *TheBucket = nil; If (LookupBucketFor(Key, TheBucket)) return *TheBucket; if (LookupBucketFor(Key, TheBucket)); Return *InsertIntoBucket(Key, ValueT(), TheBucket); <DisguisedPtr<objc_object>, size_t> bool LookupBucketFor(const LookupKeyT &Val, DisguisedPtr<objc_object>, size_t> bool LookupBucketFor const BucketT *&FoundBucket) const { const pair<DisguisedPtr<objc_object>, size_t> *BucketsPtr = getBuckets(); const unsigned NumBuckets = getNumBuckets(); . DisguisedPtr<objc_object>, size_t> = DisguisedPtr< object> When we took a table we knew that the hash of the object could be the same, if the hash was the same then we would get the same table; 2: The same table is used according to the DisguisedPtr< objC_object > object in buckets to get pair< OBJC_object <DisguisedPtr, size_t> pair. If not, one is inserted; Where do you put them to buckets? The hash algorithm is as follows. static inline uint32_t ptr_hash(uint64_t key) { key ^= key >> 4; key *= 0x8a970be7488fda55; Key ^= __builtin_bswap64(key); return (uint32_t)key; } I still do a test for this, where I return all ptr_hash values to 1 to simulate hash collisions. static inline uint32_t ptr_hash(uint64_t key) { return (uint32_t)1; } then we print the retainCount for one and two to see if it's correct. [one retain]; NSLog(@"%d",[one retainCount]); //2 [two retain]; NSLog(@"%d",[two retainCount]); //2 is still correct after testing, indicating that internal hash conflicts are resolved, and indicating that the hash algorithm cannot produce unique values. This is a common way to resolve a hash conflict. If you want to find the next available location for a table, you need to find the next available location for a pair. Another way is to use a linked list to store the same value in all hashes, but the system doesn't use that method here. RefcountMap refcnts = {BucketT * buckets = NULL; unsigned NumEntries = 0; unsigned NumTombstones = 0; unsigned NumBuckets = 0; } function of the last three variables; The idea of forcing points is to make the array scalable and deal with some threshold cases ahead of time.Copy the codeTherefore, we can regard Buckets in refcnts as an array, and the hash value and hash collision algorithm generated according to the object address can definitely find their corresponding pair in Buckets. Let’s keep going down.
id objc_object::sidetable_retain() { ... // Get the reference to size_t in the pair<DisguisedPtr<objc_object> in the table corresponding to the instance object. The default value is 0. size_t &refcntStorage = table.refcnts[this]; //SIDE_TABLE_RC_PINNED value is 1<<63 on 64-bit systems, Pow (2, 50) if ((refcntStorage & SIDE_TABLE_RC_PINNED) == false) {//SIDE_TABLE_RC_ONE is pinned to 4, I don't know, The value that controls the maximum reference count. refcntStorage += SIDE_TABLE_RC_ONE; } return (id)this; } we know that the maximum value of refcntStorage is pow(2,63)-4, because if we add refcntStorage & SIDE_TABLE_RC_PINNED, it is false. Pow (2,61) = 2305843009213693952 It will say later. You still need data to speak for yourself, or someone won't believe you. unsigned long number = SIDE_TABLE_RC_PINNED; //pow(2,63) unsigned long first = (unsigned long)pow(2, 63) -4; unsigned long second = (unsigned long)pow(2, 63); unsigned long max = first >> 2; unsigned long max111 = (unsigned long)pow(2, 61); (lldb) po second & number 9223372036854775808 (lldb) po first & number 0 (lldb) po max 2305843009213693951 (lldb) po max111 2305843009213693952Copy the codeSo we are done with retain, actually release is the same logic. When the release.
Same logic as before, get the pair of instance object. uintptr_t objc_object::sidetable_release(bool performDealloc) { ... // Iterator, it refers to pair<DisguisedPtr<objc_object>, size_t> RefcountMap::iterator it = table.refcnt.find (this); . //SIDE_TABLE_RC_ONE = 4 it->second -= SIDE_TABLE_RC_ONE; . }Copy the codeWhen the retainCount.
uintptr_t objc_object::sidetable_retainCount() { SideTable& table = SideTables()[this]; Size_t refcnt_result = 1; // Iterator, it refers to pair<DisguisedPtr<objc_object>, size_t> RefcountMap::iterator it = table.refcnt.find (this); if (it ! = table.refcnts.end()) { //SIDE_TABLE_RC_SHIFT = 2 refcnt_result += it->second >> SIDE_TABLE_RC_SHIFT; }... }Copy the codeconclusion
This article focuses on where reference counting exists, which is just a small detail in the larger context of reference counting management; Reference count management has other problems, such as.
1: How does the system store the weak variable and when does the weak variable set to nil? 2: How do AutoRelease, Autoreleasepool and RunLoop work together? 3: What is more about ARC than MRC? .Copy the codeI’ll write an article later when I have time.
Afterword.
It took me two days to finish this article, and I have read it carefully for three times. I am a rookie. If you find any impreciseness or mistakes in the reading process, please point them out. Thank you very much.