IOS Low-level - Memory Management solutions (TaggedPointer& NONPOINTER_ISA& Hash table)

preface

When it comes to memory management schemes, we first think of ARC and MRC, but in ARC and MRC are common TaggedPointer, NONPOINTER_ISA and hash table. This article will carry out a detailed analysis of these three schemes

TaggedPointer

Introduction to the

TaggedPointer is explained in WWDC2020.
1. TaggedPointerIt’s literallyPointer to tagWe know that normal Pointers point to memory, but for some types such asNSNumberIt doesn’t need a generic objectcache_tandmethod_listAnd so on, it is just a value can completely exist in the pointer, which also greatly optimize the access speed and memory, and thus producedTaggedPointer. As for optimization, see the following figure:
- In the official explanation:
  1. TaggedPointerFor small object types such asNSNUmber.NSDate.NSIndexPath, etc.
  2. Small objects store values in their own Pointers and are not called otherwiseMallocOpen up orfreeFree up memory,
  3. TaggedPointerThere areThree timesOptimization of memory space
  4. Compared to theallocate/destory.TaggedPointerThe speed should be fast106 times

Case analysis

The following is an NSString case for analysis:

Case as follows

In this case, three strings of different lengths were printed directly,copyAfter printing,[NSString stringWithFormat:]Post print and[[NSString alloc] initWithFormat:]The result is as follows:

Three types of processing can be observed in the printed resultsstringthetype:__NSCFConstantString,__NSTaggedPointerStringand__NSCFString. Let’s focus on the analysisNSTaggedPointerString

Relevant features

The simulator

Nsstrings type

Use p/t to view the binary address of ws:

在WWDC2020, we know that under the simulator, the high first is to determine whetherTaggedPointer, other bits are analyzed as follows:

As for the type of judgment, can be comparedObjc4-818.2 -The source codeobjc-internalIn the fileThe tag enumerationTo locate the

Note: 1. For strings created by the types [[NSString alloc] initWithFormat:] and [NSString stringWithFormat:], they are TaggedPointerString if the length is less than 9 bits. When the length is greater than 9, the value is NSCFString. 2. When the length of a TaggedPointerString is less than 7, the value can be read directly from the address. The rules for reading content change when the length is greater than 7

TaggedPointerString length of 8 or 9, save is six encoded characters, and coding for the alphabet eilotrm. ApdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P – B79AFKEWV_zGJ/HYX
If the character string is longer than 10 characters, the five encoded characters are saved and the encoded alphabet is eilotrM. apdnsIc ufkMShjTRxgC4013
The format for NSNumber, NSIndexPath, and NSDate is similar, but the lower four bits are not length

A:

Greater than WS in real case

At this time saidType and digitThere’s a change in position
OBJC_DISABLE_TAG_OBFUSCATION = YES; OBJC_DISABLE_TAG_OBFUSCATION = YES; This eliminates the need to print the address directly

The interview questions

@property (nonatomic.strong) dispatch_queue_t  queue;
@property (nonatomic.strong) NSString *nameStr;
// viewDidLoad
self.queue = dispatch_queue_create("com.wushuang.cn", DISPATCH_QUEUE_CONCURRENT);

- (void)taggedPointerDemo {
    for (int i = 0; i<10000; i++) {
        dispatch_async(self.queue, ^{
            self.nameStr = [NSString stringWithFormat:@"wushuang"];
             NSLog(@ "% @".self.nameStr); }); }} - (void)cfStringDemo {
    for (int i = 0; i<10000; i++) {
        dispatch_async(self.queue, ^{
            self.nameStr = [NSString stringWithFormat:@"wushuangWelcome~"];
            NSLog(@ "% @".self.nameStr); }); }}Copy the code

In the case of cfStringDemo, the main reason is that nameStr assignment will perform the release of the old value and the retain of the new value. Since it is multi-thread access, multiple releases will occur at a certain moment. Hence the wild pointer. The only difference is that __NSCFString is one and __NSTaggedPointerString is the other. In this case, you need to check the retain and release principle in objC4-818.2.

Retain:
- In the source code according to the order of search:retain->_objc_rootRetain->objc_object::rootRetain()->objc_object::rootRetain(bool tryRetain, objc_object::RRVariant variant)
- The core code is as follows:
- If it istaggedPointerType, without reference counting or any other processing
Release:
- releaseThe search order is as follows:release->_objc_rootRelease->objc_object::rootRelease()->objc_object::rootRelease(bool performDealloc, objc_object::RRVariant variant)
- The core code is as follows:
- If it istaggedPointerType, which is returned directly, without doing anything else

So taggedPointer does not cause the reference count to change and does not cause wild Pointers to crash

Tagged Pointer is used to store small objects, such as NSNumber and NSDate. 2. The value of Tagged Pointer is not an address, but a real value. It’s not really an object anymore, just a normal variable in an object’s skin. So its memory is not stored in the heap and does not require malloc and free 3. Three times more efficient at memory reads and 106 times faster at creation.

NONPOINTER_ISA

When it comes totaggedPointerOften associated withNONPOINTER_ISAIn the previous articleIOS low-level – The essence of objectsWe have explainedisaThe type and structure of.
- NONPOINTER_ISAIs it true or notisaPointer on pointer optimization:
  - 0: pure ISA pointer
  - 1: Not only class object address, ISA contains class information, object reference count, etc
- NONPOINTER_ISAIt also optimized the storage so thatisaIn theA 64 - bitGet full use of one of themshiftclsandtaggedPointerIn thePayloadSimilarly, used to store valid data
NONPOINTER_ISAIn theextra_rcIt stores reference counting data.

We know that reference counts are related to retain, release, etc. What about retainCount

Retain, Release, retainCount, hash

objc_object::rootRetain

// tryRetain: false, variant: Fast
ALWAYS_INLINE id
objc_object::rootRetain(bool tryRetain, objc_object::RRVariant variant)
{
    if (slowpath(isTaggedPointer())) return (id)this;
    
    bool sideTableLocked = false;
    bool transcribeToSideTable = false;
    isa_t oldisa;
    isa_t newisa;

    oldisa = LoadExclusive(&isa.bits);

    if (variant == RRVariant::FastOrMsgSend) { ... }  // Operation of type FastOrMsgSend
    if (slowpath(! oldisa.nonpointer)) { ... }// Non-nonpointer operations

    do {
        transcribeToSideTable = false;
        newisa = oldisa;
        if (slowpath(! newisa.nonpointer)) {ClearExclusive(&isa.bits);
            if (tryRetain) return sidetable_tryRetain()? (id)this : nil;
            else return sidetable_retain(sideTableLocked);
        }
        // don't check newisa.fast_rr; we already called any RR overrides
        if (slowpath(newisa.isDeallocating())) {... }// Destructing
        uintptr_t carry;
        newisa.bits = addc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc++

        if (slowpath(carry)) {
            // newisa.extra_rc++ overflowed
            if(variant ! = RRVariant::Full) {ClearExclusive(&isa.bits);
                return rootRetain_overflow(tryRetain);
            }
            // Leave half of the retain counts inline and 
            // prepare to copy the other half to the side table.
            if(! tryRetain && ! sideTableLocked)sidetable_lock(a); sideTableLocked =true;
            transcribeToSideTable = true;
            newisa.extra_rc = RC_HALF;
            newisa.has_sidetable_rc = true; }}while (slowpath(!StoreExclusive(&isa.bits, &oldisa.bits, newisa.bits)));

    if (variant == RRVariant::Full) { // extra_rc is full
        if (slowpath(transcribeToSideTable)) {
            // Copy the other half of the retain counts to the side table.
            sidetable_addExtraRC_nolock(RC_HALF);
        }

        if (slowpath(! tryRetain && sideTableLocked))sidetable_unlock(a); }else {
        ASSERT(! transcribeToSideTable);ASSERT(! sideTableLocked); }return (id)this;
}
Copy the code

From the source can be analyzed, the core code in the do-while loop, and VARIANT == RRVariant::Full, first to analyze the do-while loop code

The do-while loop first assigns oldisa to newisa. If newISA is of non-nonpointer type, the sidetable_tryRetain or sidetable_retain methods are used as determined. If extra_rc is full, the carry judgment is used to perform the extra_RC half-save, half-save operation on the loop outside the hash table. Let’s start with the sidetable_tryRetain method:

sidetable_tryRetain:

bool
objc_object::sidetable_tryRetain(a)
{
#if SUPPORT_NONPOINTER_ISA
    ASSERT(! isa.nonpointer);#endif
    SideTable& table = SideTables(to)this]; // Get the hash table of the current object

    bool result = true;
    auto it = table.refcnts.try_emplace(this, SIDE_TABLE_RC_ONE); // Get the reference count table 'RefcountMap' in SideTable
    auto &refcnt = it.first->second; // reference size_t in the count table
    if (it.second) {
        // there was no entry
    } else if (refcnt & SIDE_TABLE_DEALLOCATING) { // Destructing
        result = false;
    } else if (! (refcnt & SIDE_TABLE_RC_PINNED)) { // The stock is not full
        refcnt += SIDE_TABLE_RC_ONE; // The reference count increases
    }
  
    return result;
}
Copy the code

SideTable (SideTable); SideTable (SideTable); SideTable (SideTable); SideTable (SideTable)
Question: why is the reference count incremented(1UL<<2)
- Let’s start with the macro definitions mentioned
```
#define SIDE_TABLE_WEAKLY_REFERENCED (1UL<<0) // Whether there are any weak objects
#define SIDE_TABLE_DEALLOCATING      (1UL<<1) // Indicates whether the object is being destructed
#define SIDE_TABLE_RC_ONE            (1UL<<2)  // The third bit is where the reference count value is stored
#define SIDE_TABLE_RC_PINNED         (1UL<<(WORD_BITS-1)) / / top
Copy the code
```
A. to be b. to be C. to be D. to be
- First macro: Whether there are weak objects
- Second macro: indicates whether the object is being destructed
- Third macro: The start of the third bit is where the reference count value is stored
- The fourth macro: indicates that the highest bit is full, which is used to determine whether the storage is full
So the reference count needs to be SIDE_TABLE_RC_ONE

sidetable_retain:

id
objc_object::sidetable_retain(bool locked)
{
#if SUPPORT_NONPOINTER_ISA
    ASSERT(! isa.nonpointer);#endif
    SideTable& table = SideTables(to)this]; // Get the hash table of the object
  
    if(! locked) table.lock(a);// If not, the mutex of the hash table is called to lock
    size_t& refcntStorage = table.refcnts[this]; // Get the current reference count
    if (! (refcntStorage & SIDE_TABLE_RC_PINNED)) { // Check whether the storage is full
        refcntStorage += SIDE_TABLE_RC_ONE; // The reference count increases
    }
    table.unlock(a);/ / unlock
    return (id)this;
}
Copy the code

The process also fetches the hash table of the object and then increments the reference count.

Bits = addC (newISa.bits, RC_ONE, 0, &carry). RC_ONE is where the EXTRA_RC is stored to begin. The addC function adds newisa.bits to RC_ONE and stores it to newisa.bits. If it is full, the reference count is stored half way in extra_RC and labeled accordingly, then the sidetable_addExtraRC_nolock method is called

sidetable_addExtraRC_nolock:

bool 
objc_object::sidetable_addExtraRC_nolock(size_t delta_rc)
{
    ASSERT(isa.nonpointer);
    SideTable& table = SideTables(to)this]; // Get the hash table of the object

    size_t& refcntStorage = table.refcnts[this]; Get the reference count from the reference count table
    size_t oldRefcnt = refcntStorage;
    // isa-side bits should not be set here
    ASSERT((oldRefcnt & SIDE_TABLE_DEALLOCATING) == 0);
    ASSERT((oldRefcnt & SIDE_TABLE_WEAKLY_REFERENCED) == 0);

    if (oldRefcnt & SIDE_TABLE_RC_PINNED) return true; // Return if the memory is full

    uintptr_t carry;
    size_t newRefcnt = 
        addc(oldRefcnt, delta_rc << SIDE_TABLE_RC_SHIFT, 0, &carry); // delta_rc << SIDE_TABLE_RC_SHIFT is saved from the second position
    if (carry) {
        refcntStorage =
            SIDE_TABLE_RC_PINNED | (oldRefcnt & SIDE_TABLE_FLAG_MASK); // refcntStorage is the maximum value that can be stored
        return true;
    }
    else {
        refcntStorage = newRefcnt;
        return false; }}Copy the code

After the reference count is retrieved from the reference count table, the other half of the reference count is stored in the appropriate location

Retain the flow chart

The entire process after retain is as follows:

objc_object::rootRelease

Through the aboveRetainAnalysis of processes,releaseAnalysis is much easier, the main source code is as follows:

ALWAYS_INLINE bool
objc_object::rootRelease(bool performDealloc, objc_object::RRVariant variant)
{
    if (slowpath(isTaggedPointer())) return false;

    bool sideTableLocked = false;
    isa_t newisa, oldisa;
    oldisa = LoadExclusive(&isa.bits);

    if (variant == RRVariant::FastOrMsgSend) { ... }
    if (slowpath(! oldisa.nonpointer)) { ... } retry:do {
        newisa = oldisa;
        if (slowpath(! newisa.nonpointer)) {ClearExclusive(&isa.bits);
            return sidetable_release(sideTableLocked, performDealloc);
        }
        if (slowpath(newisa.isDeallocating())) {... }// don't check newisa.fast_rr; we already called any RR overrides
        uintptr_t carry;
        newisa.bits = subc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc--
        if (slowpath(carry)) {
            // don't ClearExclusive()
            gotounderflow; }}while (slowpath(!StoreReleaseExclusive(&isa.bits, &oldisa.bits, newisa.bits)));

    if (slowpath(newisa.isDeallocating()))
        gotodeallocate; .return false;
 underflow:
    newisa = oldisa;
    if (slowpath(newisa.has_sidetable_rc)) {
        if(variant ! = RRVariant::Full) {ClearExclusive(&isa.bits);
            return rootRelease_underflow(performDealloc);
        }
        if(! sideTableLocked) {// Retry without lockrelated assignment
            ClearExclusive(&isa.bits);
            sidetable_lock(a); sideTableLocked =true;
            // Need to start over to avoid a race against 
            // the nonpointer -> raw pointer transition.
            oldisa = LoadExclusive(&isa.bits);
            goto retry;
        }
        auto borrow = sidetable_subExtraRC_nolock(RC_HALF); // Borrow half from the hash table
        bool emptySideTable = borrow.remaining == 0; // we'll clear the side table if no refcounts remain there

        if (borrow.borrowed > 0) {
            bool didTransitionToDeallocating = false;
            newisa.extra_rc = borrow.borrowed - 1;  // redo the original decrement toonewisa.has_sidetable_rc = ! emptySideTable;bool stored = StoreReleaseExclusive(&isa.bits, &oldisa.bits, newisa.bits); .if(! stored) {// Inline update failed.
                // Put the retains back in the side table.
                ClearExclusive(&isa.bits);
                sidetable_addExtraRC_nolock(borrow.borrowed);
                oldisa = LoadExclusive(&isa.bits);
                goto retry;
            }

            // Decrement successful after borrowing from side table.
            if (emptySideTable)
                sidetable_clearExtraRC_nolock(a);if(! didTransitionToDeallocating) {if (slowpath(sideTableLocked)) sidetable_unlock(a);return false; }}else {
            // Side table is empty after all. Fall-through to the dealloc path.
        }
    }

deallocate:
    ...
    if (performDealloc) {
        ((void(*)(objc_object *, SEL))objc_msgSend)(thisThe @selector(dealloc));
    }
    return true;
}
Copy the code

Check whether it is a small object first, if not, then check whether it is nonpointer

If it is notnonpointerJust callsidetable_releaseMethod to perform the reference count reduction operation as follows

objc_object::sidetable_release(bool locked, bool performDealloc)
{
#if SUPPORT_NONPOINTER_ISA
    ASSERT(! isa.nonpointer);#endif
    SideTable& table = SideTables(to)this];

    bool do_dealloc = false;

    if(! locked) table.lock(a);auto it = table.refcnts.try_emplace(this, SIDE_TABLE_DEALLOCATING);
    auto &refcnt = it.first->second;
    if (it.second) {
        do_dealloc = true;
    } else if (refcnt < SIDE_TABLE_DEALLOCATING) { // If it is a week object
        // SIDE_TABLE_WEAKLY_REFERENCED may be set. Don't change it.
        do_dealloc = true;
        refcnt |= SIDE_TABLE_DEALLOCATING;
    } else if (! (refcnt & SIDE_TABLE_RC_PINNED)) { // Check whether the storage is full
        refcnt -= SIDE_TABLE_RC_ONE; // The reference count is reduced by 1
    }
    table.unlock(a);if (do_dealloc  &&  performDealloc) {
        ((void(*)(objc_object *, SEL))objc_msgSend)(thisThe @selector(dealloc)); / / invoke dealloc
    }
    return do_dealloc;
}
Copy the code

When do_dealloc is true and performDealloc is true, the dealloc message is sent.

Call subc to extra_rc–. If subtracted too much, call sidetable_subExtraRC_nolock to borrow half of the hash and assign to extra_rc as follows:

uintptr_t
objc_object::sidetable_subExtraRC_nolock(size_t delta_rc)
{
    ASSERT(isa.nonpointer);
    SideTable& table = SideTables(to)this]; // Get the hash table

    RefcountMap::iterator it = table.refcnts.find(this);
    if (it == table.refcnts.end()  ||  it->second == 0) { // Hash table does not exist
        // Side table retain count is zero. Can't borrow.
        return { 0.0 };
    }
    size_t oldRefcnt = it->second;

    // isa-side bits should not be set here
    ASSERT((oldRefcnt & SIDE_TABLE_DEALLOCATING) == 0);
    ASSERT((oldRefcnt & SIDE_TABLE_WEAKLY_REFERENCED) == 0);

    size_t newRefcnt = oldRefcnt - (delta_rc << SIDE_TABLE_RC_SHIFT); // Borrow half and deposit the rest
    ASSERT(oldRefcnt > newRefcnt);  // shouldn't underflow
    it->second = newRefcnt;
    return { delta_rc, newRefcnt >> SIDE_TABLE_RC_SHIFT };
}
Copy the code

If the hash does not return to send a dealloc message, if it does borrow half

The flow chart of the release

retainCount

retainCountThe main call process is as follows:retainCount -> _objc_rootRetainCount -> rootRetainCount, the core code is as follows:

inline uintptr_t 
objc_object::rootRetainCount(a)
{
    if (isTaggedPointer()) return (uintptr_t)this;

    sidetable_lock(a);isa_t bits = __c11_atomic_load((_Atomic uintptr_t *)&isa.bits, __ATOMIC_RELAXED);
    if (bits.nonpointer) { 
        uintptr_t rc = bits.extra_rc;
        if (bits.has_sidetable_rc) { // If there is a hash table, the retainCount value is extra_rc plus the values in the reference count table
            rc += sidetable_getExtraRC_nolock(a); }sidetable_unlock(a);return rc;
    }

    sidetable_unlock(a);return sidetable_retainCount(a);// If it is not 'nonpointer', the hash table is taken directly
}
Copy the code

If it isisTaggedPointerReturn directly, if yesnonpointerType, then fetchextra_rcIf it exists in the hash table, the hash table values andextra_rcAnd of the
Whether it issidetable_getExtraRC_nolockorsidetable_retainCountIt’s all in the methodReference count values >> SIDE_TABLE_RC_SHIFTThe operation, mainly because from the time to save from the second save, so calculateretainCountThe need whenMoves to the right SIDE_TABLE_RC_SHIFT.

Hash table

SideTable is a structure consisting of mutex, RefcountMap reference count table, weak_table_t weak reference table and weak_table_t weak reference table. Destructors and lock methods are also related:

We have analyzed RefcountMap reference count table operations in Retain and Release, and weak_table_t weak reference table will be analyzed in the next article

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

IOS Low-level – Memory Management solutions (TaggedPointer& NONPOINTER_ISA& Hash table)

preface

TaggedPointer

Introduction to the

Case analysis

Relevant features

The simulator

A:

The interview questions

NONPOINTER_ISA

Retain, Release, retainCount, hash

objc_object::rootRetain

Retain the flow chart

objc_object::rootRelease

The flow chart of the release

retainCount

Hash table

IOS Low-level – Memory Management solutions (TaggedPointer& NONPOINTER_ISA& Hash table)

preface

TaggedPointer

Introduction to the

Case analysis

Relevant features

The simulator

A:

The interview questions

NONPOINTER_ISA

Retain, Release, retainCount, hash

objc_object::rootRetain

Retain the flow chart

objc_object::rootRelease

The flow chart of the release

retainCount

Hash table

Related Posts

IOS UIButton automatically calculates the width based on the text content

React Native – a copy of meituan iOS client

Responsive programming and MVVM Architecture — Theory