(6) In-depth understanding of weak and weak references

Weak pointer, also known as weak reference, is a very important concept in OC. Compared with alloc, retain,release, dealloc and other memory management knowledge points of OC objects, weak reference pointer is more difficult to understand. So here is a summary of weak references in OC through runtime source code analysis

1. Lifecycle function of weak pointer (weak reference

Objc-runtime: objC-Runtime: objC-Runtime: objC-Runtime: objC-Runtime: objC-Runtime: objC-Runtime

1. Weak reference weak initializationobjc_initWeak
2. Weak reference weak is assignedobjc_storeWeak
3. Weak references weak are releasedobjc_destroyWeak
4. And those used with weak reference Pointersobjc_loadWeak

The following explains how to initialize weak references in two common scenarios:

// The first scenario initializes a weak reference pointer to nil
__weak id weakPtr;

// In the second scenario, initialize a weak reference pointer to non-nil
NSObject *o = [NSObject new];
__weak id weakPtr = o;
Copy the code

They all trigger the following methods, in which

1. The first argument is the address of the weak reference pointer!! It must be the address
2. The second argument is the OC object to which the weak reference pointer points!!

/* Parameter 1: location Address of __weak PTR. Parameter 2: newObj Object PTR. */ id objc_initWeak(id *location, id newObj);Copy the code

The specific code logic of this method is only used in two steps, and there are my annotations in the source code:

1. Check if the OC object assigned or initialized to a weak-reference pointer is nil. If nil, the weak-reference pointer points directly to nil.
2. Otherwise, call directlystoreWeakMethod, this is a c++ template method, so here we initialize a weak reference pointer, which is used by the template parameterDontHaveOld.DoHaveNew.DoCrashIfDeallocating

/** * Initialize a fresh weak pointer to some object location. * It would be used for code like: * * (The nil case) * __weak id weakPtr; * (The non-nil case) * NSObject *o = ... ; * __weak id weakPtr = o; * * This function IS NOT thread-safe with respect to concurrent * modifications to the weak variable. (Concurrent weak clear is safe.) * * @param location Address of __weak ptr. * @param newObj Object ptr. */
id objc_initWeak(id *location, id newObj) {
		// Check if the OC object to which the weak-reference pointer points is null, if nil
		// Then weak reference pointer to nil!!
		// This method returns nil
    if(! newObj) { *location = nil;return nil;
    }

    // location is the address of the __weak PTR pointer.
    // Force newObj to objc_object *
    return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
        (location, (objc_object*)newObj);
}

// Modify the weak reference pointer to point to a new OC object
id objc_storeWeak(id *location, id newObj) {
    return storeWeak<DoHaveOld, DoHaveNew, DoCrashIfDeallocating>
        (location, (objc_object *)newObj);
}

// Weak reference pointer cleanup method, i.e
// __weak NSObject *weakObj = oc object;
// weakObj = nil;
void objc_destroyWeak(id *location) {
    // The objc_destoryWeak method is called only after it has been freed
    (void)storeWeak<DoHaveOld, DontHaveNew, DontCrashIfDeallocating>
        (location, nil);
}
Copy the code

The above methods will eventually trigger a c++ template method called storeWeak<… >, the template method essentially updates the value of a weak reference pointer itself, where the template parameters are as follows:

1. HaveOld, indicating whether the weak reference pointer currently points to an old OC object, called the old Object. If so, the information of the local weak reference pointer in the weak reference table of the old object needs to be processed first
2. HaveNewIndicates whether a weak reference pointer will point to a new OC object, called a New Object
3. DoCrashIfDeallocatingIndicates that the new object to which the weak reference pointer is pointing isdeallocating, then crash!! The following method would crash, and therefore crash the objectdeallocMethod when the OC objectisa.deallocating == true .

-(void)dealloc{
	__weak typeof(self) weakself = self;
}
Copy the code

The key way to update weak reference variables is as follows:

// Update a weak variable.
// If HaveOld is true, the variable has an existing value 
// that needs to be cleaned up. This value might be nil.
// If HaveNew is true, there is a new value that needs to be 
// assigned into the variable. This value might be nil.
// If CrashIfDeallocating is true, the process is halted if newObj is 
// deallocating or newObj's class does not support weak references.
// If CrashIfDeallocating is false, nil is stored instead.
enum CrashIfDeallocating {
    DontCrashIfDeallocating = false, DoCrashIfDeallocating = true
};
template <HaveOld haveOld, HaveNew haveNew,
          enum CrashIfDeallocating crashIfDeallocating>
static id 
storeWeak(id *location, objc_object *newObj)
{
    ASSERT(haveOld  ||  haveNew);
    if(! haveNew)ASSERT(newObj == nil);

    // We need to get the weak reference table of old new OC
    Weak_table -> Weak_entry [oc object, weak reference pointer address]
    Class previouslyInitializedClass = nil;
    id oldObj;
    SideTable *oldTable;
    SideTable *newTable;

    // Acquire locks for old and new values.
    // Order by lock address to prevent lock ordering problems. 
    // Retry if the old value changes underneath us.
 retry:
    if (haveOld) {
        oldObj = *location;
        oldTable = &SideTables()[oldObj];
    } else {
        oldTable = nil;
    }
    if (haveNew) {
        newTable = &SideTables()[newObj];
    } else {
        newTable = nil;
    }

    SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);

    if(haveOld && *location ! = oldObj) { SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);goto retry;
    }

    // If the new OC object is not initialized, initialize it first.// All sidetables of old new OC are locked
    
    Weak_entry_t, which is associated with the weak reference pointer, is removed from the weak_table of the old OC object
    // Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
    }

    // Then, construct weak_entry_t with [new OC object, address of weak reference pointer] and add it to Weak_table of sidetable of new OC object
    // Assign new value, if any.
    if (haveNew) {
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating ? CrashIfDeallocating : ReturnNilIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected

        // If the new OC object is not a taggedPointer object
        // Set the weaklyReference flag bit in the ISA of this object
        // Set is-weakly-referenced bit in refcount table.
        if(! newObj->isTaggedPointerOrNil()) {
            newObj->setWeaklyReferenced_nolock(a); }// Point a weak reference pointer to a new OC object!!
        // Do not set *location anywhere else. That would introduce a race.
        *location = (id)newObj;
    } else {
        // No new value. The storage is not changed.
    }
    
    SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);

    // Force new obj to have a weaklyReference flag bit to which a weak reference pointer points
    // After the flag bit is marked, when the new OBj object is released, the flag bit is used to determine whether there is a weak reference pointer to the new OBj. If so, weak_table needs to be processed
    
    // This must be called without the locks held, as it can invoke
    // arbitrary code. In particular, even if _setWeaklyReferenced
    // is not implemented, resolveInstanceMethod: may be, and may
    // call back into the weak reference machinery.
    callSetWeaklyReferenced((id)newObj);

    // Return a pointer to the oc object with a weak reference pointer!!
    return (id)newObj;
}
Copy the code

In fact, there is also a scenario where strongA = weakB is used in a block, or where a weak reference pointer is used, the following method will be called:

/** * This loads the object referenced by a weak pointer and returns it, after * retaining and autoreleasing the object to ensure that it stays alive * long enough for the caller to use it. This function would be used * anywhere a __weak variable is used in an expression. * * @param location The weak pointer address * * @return The object pointed to by \e location, or \c nil if \e location is \c nil. */
id objc_loadWeak(id *location) {
	  // The weak-reference pointer to oc is nil. Just return nil
    if(! *location)return nil;
  	// Otherwise weak reference to the OC object, then add it to the Auto Release pool and return!
    return objc_autorelease(objc_loadWeakRetained(location));
}
Copy the code

As you can see from the above code, the biggest difference between weak-reference Pointers/strong-reference Pointers in oc and C++ Pointers is the memory management aspect of oc objects!

In addition, weak/strong reference Pointers and C++ ordinary Pointers are not fundamentally different, they all point to a heap of address space!!

When we use weak-reference/strong-reference Pointers to OC, the compiler and runtime secretly maintain reference count information and weak-reference tables for OC objects underneath!!

Key methods in the above are as follows:

1. SideTable API
2. weak_unregister_no_lock
3. weak_register_no_lock

2. SideTable structure

Sidetable = oc; sidetable = oc; sideTable = oc; sideTable = OC;

SideTable *table = &SideTables()[obj];
Copy the code

And the key is:

This involves the SideTables global static method:

// For quick initialization of a SideTablesMap static object in runtime, use the ExplicitInit class template
static objc::ExplicitInit<StripedMap<SideTable>> SideTablesMap;

// A static StripedMap
      
        object
      
static StripedMap<SideTable>& SideTables(a) {
		The get() method is the square in the ExplicitInit template
    return SideTablesMap.get(a); }// StripedMap<T> is a map of void* -> T, sized appropriately 
// for cache-friendly lock striping. 
// For example, this may be used as StripedMap<spinlock_t>
// or as StripedMap<SomeStruct> where SomeStruct stores a spin lock.
template<typename T>
class StripedMap {
    enum { CacheLineSize = 64 };

    struct PaddedT {
        T value alignas(CacheLineSize);
    };
    enum { StripeCount = 8 };
    PaddedT array[StripeCount];

    static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
    }
 public:
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    const T& operator[] (const void *p) const { 
        return const_cast<StripedMap<T>>(this)[p]; 
    }
    constexpr StripedMap(a) {}};Copy the code

It is clear from the above source code:

See from the source:

1. StripedMap<T>Is a class template, it is essentially a hash table!! The underlying data container uses a contiguous array of memory space, and it contains eight elements that are usedhash()The hash function depends on oneconst void *Pointer, the underlying hash function will directly get the pointer to the address used as the basis of the calculation, add some arithmetic to get index!!
2. StripedMap<T>Rewrite the following table operators[]By passing in the address of the OC object, the hash function can be used to calculate the specific associatedTobject
3. The Runtime uses a global static StripedMap<SideTable>Object to manage all oc objectsSideTableAs long asAddress of the oc objectThe hash function evaluates the index of the array to get the corresponding value of the OC objectsideTable

The Runtime uses the following methods to obtain the sidetable of objC_Object:

SideTable& table = SideTables()[this];

Global SideTables hash table

1. Data structure:sideTablesIs the underlying data structure ofHashTable hash
2. The underlying container: has 8 elements in the static data areaImmutable array Array, the member isSideTable
3. The hash functionUse:objc_object*Object address combined with a certain algorithm asThe hash function, calculate the index
4. KV information:key is the index calculated above, value is the oc objectsideTable
5. Hash conflict: indicates that different OC objects will be sharedSideTable!!!!!!!!!
6. Hash extension factor: None (array of fixed length)

For the SideTable structure:

struct SideTable {
    spinlock_t slock; // Spin lock, used to protect the fine-grained lock of refcnts and Weak_table
    RefcountMap refcnts; // Additional reference counting table -- hash Map
    weak_table_t weak_table; // Weak reference table member -- hash table.// some c++ constructors, destructors, locking methods, etc
}
Copy the code

The weak_table in sideTable is operated by weak_table in sideTable. In simple terms, it is registered and removed, which will involve the structure of weak reference table!!

// Register the address information of the weak reference pointer from the weak reference table of the OC object
weak_register_no_lock(&newTable->weak_table, (id)newObj, location, CrashIfDeallocating);
// Remove the address information of the weak reference pointer from the weak reference table of the OC object
weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
Copy the code

3. Weak_table_t Weak reference table structure

In essence, The Runtime will perform a series of low-level operations on the weak reference table and ISA of the OC object to which the weak pointer points. When understanding these operations, it is necessary to have a clear understanding of the data structure of weak_table.

/** * The global weak references table. Stores object ids as keys, * and weak_entry_t structs as their values. */
struct weak_table_t {
    weak_entry_t *weak_entries; 				// Store the actual key-value pairs. The underlying container is mutable array
    size_t    		num_entries;      		// The number of entities currently stored
    uintptr_t 		mask;								  // Maximum hash table capacity
    uintptr_t 		max_hash_displacement;// Maximum number of hash collisions
};

// Weak reference the actual key-value information stored in the table
// Weak pointer (object, weak pointer)
struct weak_entry_t {
  // key --> oc object pointer
  DisguisedPtr<objc_object> referent;
  
  // value -> use an array to store weak Pointers.
  // Use unions to save memory
  union {
    struct {
      weak_referrer_t *referrers; // HashTable stores a mutable array of weak reference Pointers!!
      uintptr_t        out_of_line_ness : 2; // Determine whether to use a fixed array or HashTable
      uintptr_t        num_refs : PTR_MINUS_2;
      uintptr_t        mask;
      uintptr_t        max_hash_displacement;
    };
    
    struct {
      // out_of_line_ness field is low bits of inline_referrers[1]
      weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT]; // A fixed array of weak reference Pointers}; }; .// Other methods
};

// The address of a __weak variable. --> address of a __weak variable!! The address of a weak reference pointer
// Obfuscating is used here to reduce the impact on Memory Analysis Tools
typedef DisguisedPtr<objc_object *> weak_referrer_t;
Copy the code

Weak_table is summarized as follows:

1. Data structure:weak_table_tIs the underlying data structure ofHashTable hashAnd it will besideTablethespinlockTo protect
2. The underlying container: It’s distributed on the heaptheVariable loop array arrayEach member isweak_entry_tThe structure of the body
3. The hash function: rely onweak_entry_tthereferent, that is,Oc objectA calculated index!!
4. KV information: Key is the index calculated above, value isOc objecttheweak_entry_tStructure!!!!!!
5. Hash conflict: Looks for the next empty location store of an array, similar to open addressing, when a hash conflict occursweak_entry_t
6. Hash extension factorHashTable = 64; HashTable = 0.75; And as I decrease,1/16Is reduced to 1/2

Where the hash function of weak_table is:

size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask);
Copy the code

Treatment of hash conflict of weak_table:

size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask); // hash function
size_t index = begin; 
size_t hash_displacement = 0;
Weak_table -> Weak_entries!! Not to be confused with the latter
// Start at array index and find the first empty array!! (Loop array)
while(weak_entries[index].referent ! = nil) { index = (index+1) & weak_table->mask; // loop search!!
  if (index == begin)
  	bad_weak_table(weak_entries); // If no, crash!
  hash_displacement++; // Record the maximum number of hash conflicts
}
Copy the code

Another complication is that weak_entry_t’s internal weak reference pointer stores relevant content, and Runtime uses a union to optimize memory. When the number of weak reference Pointers to oc objects is less than 4, use a fixed array to store weak Pointers. If the number exceeds 4, use HashTable.

Weak_entry_t is summarized as follows:

1. Data structure:weak_entry_tIt’s a Pair!!
2. Pair structure: (OC object: weak Pointers) and Pointers are scrambled!!
3. weak pointersUsing union implementations,
   1. ifweak pointersIf the number is less than 4, use a fixed-length array to store weak reference Pointers
   2. If the number is greater than 4, it will be usedHashTablestorage

When the number of weak Pointers exceeds 4, runtime uses HashTable to store them!! Its message is as follows:

1. The data structure is a HashTable HashTable
2. The underlying container: It’s distributed on the heaptheVariable loop array arrayEvery member isweak pointerConfounding results of
3. The hash function: rely onWeak Pointer address!!That isnew_referrerA calculated index!!
4. KV information: key is the index calculated above, value is the point toOc objecttheweak pointerPointer!
5. Hash conflict: Looks for the next empty location store of an array, similar to open addressing, when a hash conflict occursweak pointer
6. Hash extension factor: The initial capacity of the HashTable is 8. When the HashTable increases to 0.75, it is doubled

Note: All of the above weak Pointers are shorthand for confusing results

Where the hash function storing weak Pointers,

//new_referrer is the address of weak pointer
size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
Copy the code

Treatment of hash conflict of Weak_entry:

 // new_referrer is the new __weak NSObject *xx; The address of xx for this weak reference pointer
size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
		Referrers = referrers = referrers; Do not be confused with the front weak_table
		// Start at array index and find the first empty array!! (Loop array)
    while(entry->referrers[index] ! = nil) { hash_displacement++; index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
    }
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
Copy the code

We’ll take a closer look at adding, deleting, and cleaning methods to the weakly referenced HashTable

1. weak_register_no_lock: Inserts into the weak reference table(object, weak pointer) theweak_entry_tThe structure of the body
2. weak_unregister_no_lock: Removed from the weak reference table(object, weak pointer) theweak_entry_tThe structure of the body
3. weak_clear_no_lock: in the OC objectCalled when it is destructed, set allweak pointerIs nil

4. Weak_table_t Increase operation of weak reference table

To create a new __weak NSObject* pointing to an object, from the previous article, the process is as follows:

1. objc_initWeak
2. objc_storeWeak
3. weak_register_no_lock
4. New OC object and weak Pointer address.
5. Constructor of (oc object, weak Pointer)weak_entry_t, added to the weak_table_tIn the

/** * Registers a new (object, weak pointer) pair. Creates a new weak * object entry if it does not exist. * * @param weak_table The global weak table.  * @param referent The object pointed to by the weak reference. * @param referrer The weak pointer address. */
id weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, WeakRegisterDeallocatingOptions deallocatingOptions) {
    objc_object *referent = (objc_object *)referent_id; / / oc object
    objc_object **referrer = (objc_object **)referrer_id; // weak pointer
    // If it is taggedPointer, it is not affected by weak Pointer
    if (referent->isTaggedPointerOrNil()) 
    		return referent_id;

    // If the oc object is dealloc, it will crash.// now remember it and where it is being stored
    // Two cases:
    // 1. If the OC object already has an weak pointer, add it to the Weak_entry
    // 2. If there is no weak pointer, create a weak_entry (OC object, weak Pointer) and insert it into the Weak_table
    weak_entry_t *entry;
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        append_referrer(entry, referrer);
    } else {
        weak_entry_t new_entry(referent, referrer);
        // If you want to insert weak_entry_t, you need to determine whether the hashtable needs to grow
        weak_grow_maybe(weak_table);  
        weak_entry_insert(weak_table, &new_entry);
    }
    
    return referent_id;
}
Copy the code

There are two very common situations where the two roads are different:

NSObject *obj = [NSObject new];
__weak NSObject* weakObj1 = obj; / / 1
__weak NSObject* weakObj2 = obj; / / 2
Copy the code

1. If the current__weak NSObject* The oc object pointed to does not have a weak reference pointer to point to and may need a reference toweak_tableProceed to expand the table and then put the newweak_entryinsertweak_tableIn the.
2. If the current__weak NSObject* The oc object pointed to had a weak reference pointer pointed to before, when itsweak_tableIn theweak_entry_tIt must exist. So you need to find it firstweak_entry_t, and then speakweak pointeruseappend_referrerTo join in

So let’s analyze the first one and insert the new oneweak_entry_t 到weak_tableIn the

In this case:

__weak NSObject* weakObj = [NSObject new];
Copy the code

The code is as follows, with internal comments:

// The length of the table is mask
#define TABLE_SIZE(weak_table) (weak_table->mask ? weak_table->mask + 1 : 0)

// Grow the given zone's table of weak references if it is full.
static void weak_grow_maybe(weak_table_t *weak_table) {
		// Get the old value
    size_t old_size = TABLE_SIZE(weak_table);

		// The HashTable extension factor threshold is 0.75
    if (weak_table->num_entries >= old_size * 3 / 4) {
        // The size of the expansion is *2, initially 64!!!!
        weak_resize(weak_table, old_size ? old_size * 2 : 64); }}// expand the table
static void weak_resize(weak_table_t *weak_table, size_t new_size) {
    size_t old_size = TABLE_SIZE(weak_table);
    / / the old data
    weak_entry_t *old_entries = weak_table->weak_entries;
    // reallocate the heap space of new_size
    weak_entry_t *new_entries = (weak_entry_t *)
        calloc(new_size, sizeof(weak_entry_t));

    weak_table->mask = new_size - 1;
    weak_table->weak_entries = new_entries;
    weak_table->max_hash_displacement = 0;
    weak_table->num_entries = 0;  // restored by weak_entry_insert below
    // Insert old Weak_entry structure into new space one by one
    if (old_entries) {
        weak_entry_t *entry;
        weak_entry_t *end = old_entries + old_size;
        for (entry = old_entries; entry < end; entry++) {
            // Note that when resize, if the OC object in weak_entry does not exist (it may be released), then the new object is not inserted
            if (entry->referent) {
                weak_entry_insert(weak_table, entry); }}free(old_entries); }}/** * Add new_entry to the object's table of weak references. * Does not check whether the referent is already in the table. */
static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry) {
    weak_entry_t *weak_entries = weak_table->weak_entries;
    ASSERT(weak_entries ! = nil);// Use hash function!! Calculate the index of the looping array array.
		// The hash function is computed using the address of the OC object!!
    size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    while(weak_entries[index].referent ! = nil) { index = (index+1) & weak_table->mask;
        if (index == begin)
            bad_weak_table(weak_entries);
        hash_displacement++; // The hash is in conflict. Keep looking for seats
    }

		// Insert formally!!
    weak_entries[index] = *new_entry; // Use copy constructor!!
    Weak_entry_t number of weak_entry_t inserts, use weak_table->num_entries to store
    weak_table->num_entries++;
    // Update the maximum number of hash function collisions
    if(hash_displacement > weak_table->max_hash_displacement) { weak_table->max_hash_displacement = hash_displacement; }}Copy the code

As you can see from the above code, if a fully initialized weak_table is inserted for the first time when a weak_entry_t is inserted, the HashTable will be constructed, and a variable-length cyclic array of initial length 64 will be constructed underneath as the HashTable container. The contents of other Weak_table hash tables are summarized above.

Let’s do the second one, insertionalweak_entry_tIn theOc objectWe already have weak references pointing at us

Content of Case 2:

NSObject *obj = [NSObject new];
__weak NSObject* weakObj1 = obj; / / 1
__weak NSObject* weakObj2 = obj; / / 2
Copy the code

The key codes are as follows:

weak_entry_t *entry;
if ((entry = weak_entry_for_referent(weak_table, referent))) {
		append_referrer(entry, referrer);
}
Copy the code

Weak_entry_for_referent is to find the WEAK_entry_t oc object weak_entry_t source code is as follows, the code is relatively simple, direct reference notes:

/** * Return the weak reference table entry for the given referent. * If there is no entry for referent, return NULL. * Performs a lookup. * * @param weak_table * @param referent The object. Must not be nil. * * @return The table of weak referrers to this object. */
static 
weak_entry_t* weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent) {
    ASSERT(referent);
		/ / get the HashTable
    weak_entry_t *weak_entries = weak_table->weak_entries;

    if(! weak_entries)return nil;

  	// Use the Hash function to get index
    size_t begin = hash_pointer(referent) & weak_table->mask;
    size_t index = begin;
    size_t hash_displacement = 0;
    // Combine index to determine whether a hash collision has occurred and find the queried index
    while(weak_table->weak_entries[index].referent ! = referent) { index = (index+1) & weak_table->mask;
        if (index == begin)
            bad_weak_table(weak_table->weak_entries);
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) {
            returnnil; }}// Return weak_entry associated with oc object!!
    return &weak_table->weak_entries[index];
}
Copy the code

Weak_entry_t = weak_entry_t; weak_entry_t = weak_entry_t; weak_entry_t = weak_entry_t; weak_entry_t = weak_entry_t; weak_entry_t = weak_entry_t;

// The address of a __weak variable.
// These pointers are stored disguised so memory analysis tools
// don't see lots of interior pointers from the weak table into objects.
typedef DisguisedPtr<objc_object *> weak_referrer_t; // 


/** * Add the given referrer to set of weak pointers in this entry. * Does not perform duplicate checking (b/c weak pointers are never * added to a set twice). * * @param entry The entry holding the set of weak pointers. * @param new_referrer The new weak pointer to be added. The two key input parameters of the function are weak_entry of oc object respectively!! The other argument is the address of the new weak reference pointer to the OC object */
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer) {
		// The out_of_line() function determines whether weak_entry manages weak reference Pointers using HashTable or fixed-length array!!
    if(! entry->out_of_line()) {
				If there is room in the fixed length array, the address of the weak reference pointer is stored in the empty space of the fixed length array
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) {
                entry->inline_referrers[i] = new_referrer;
                return; }}// There is no space left in the array to store the address of the new weak reference pointer.
				// We need to change the underlying container, change the fixed length array storage, change the HashTable storage

        // Couldn't insert inline. Allocate out of line.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i];
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT- 1;
        entry->max_hash_displacement = 0;
    }

		// Specify that weak Pointers are stored using HashTable
    ASSERT(entry->out_of_line());

		// If it is the first change to HashTable storage or has exceeded the volume factor 0.75
		// Add 2 * oldSize to HashTable. Then re-call append_referrer to insert new_referrer
    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        return grow_refs_and_insert(entry, new_referrer);
    }
    // Hash function!! The address - associated function left - right hash function is used
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    // Hash down to the first empty position (note that it is a looping array of variable length)
    while(entry->referrers[index] ! = nil) { hash_displacement++; index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
    }
    // Record the maximum hash collisions
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
    // Store the first empty position after the index found, and then store it
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

/** * Grow the entry's hash table of referrers. Rehashes each * of the referrers. * * @param entry Weak pointer hash set  for a particular object. */
__attribute__((noinline, used))
static void grow_refs_and_insert(weak_entry_t *entry, 
                                 objc_object **new_referrer)
{
		Weak_entry_t uses a cyclic variable-length array to store the weak Pointer's address for the container's HashTable
    ASSERT(entry->out_of_line());

    size_t old_size = TABLE_SIZE(entry);
    size_t new_size = old_size ? old_size * 2 : 8;

    size_t num_refs = entry->num_refs;
    weak_referrer_t *old_refs = entry->referrers;
    entry->mask = new_size - 1;
    
    entry->referrers = (weak_referrer_t *)
        calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));
    entry->num_refs = 0;
    entry->max_hash_displacement = 0;
    
    // All are recalculated by the Hash function and inserted into the new HashTable
    for (size_t i = 0; i < old_size && num_refs > 0; i++) {
        if(old_refs[i] ! = nil) {append_referrer(entry, old_refs[i]); num_refs--; }}// Insert the new address of weak ponter
    append_referrer(entry, new_referrer);
    if (old_refs) free(old_refs);
}
Copy the code

For the key information of the HashTable where the weak Pointers address is stored, post again:

Weak_entry_t is summarized as follows:

1. Data structure:weak_entry_tIt’s a Pair!!
2. Pair structure: (OC object: weak Pointers) and Pointers are scrambled!!
3. weak pointersUsing union implementations,
   1. ifweak pointersIf the number is less than 4, use a fixed-length array to store weak reference Pointers
   2. If the number is greater than 4, it will be usedHashTablestorage

When the number of weak Pointers exceeds 4, runtime uses HashTable to store them!! Its message is as follows:

1. The data structure is a HashTable HashTable
2. The underlying container: It’s distributed on the heaptheVariable loop array arrayEvery member isweak pointerConfounding results of
3. The hash function: rely onWeak Pointer address!!That isnew_referrerA calculated index!!
4. KV information: key is the index calculated above, value is the point toOc objecttheweak pointerPointer!
5. Hash conflict: Looks for the next empty location store of an array, similar to open addressing, when a hash conflict occursweak pointer
6. Hash extension factor: The initial capacity of the HashTable is 8. When the HashTable increases to 0.75, it is doubled

Note: All of the above weak Pointers are shorthand for confusing results

5. Weak_table_t Delete operation of weak reference table

The above known weak reference table increase operation, similar code, delete operation will not expand in detail.

/** * Unregister an already-registered weak reference. * / * This is used when the referrer's storage is about to go away, but referent * isn't dead yet. (Otherwise, zeroing referrer later would be a * bad memory access.) * Does nothing if referent/referrer is not a currently active weak reference. * Does not zero referrer. * * FIXME currently requires old referent value to be passed in (lame) * FIXME  unregistration should be automatic if referrer is collected * * @param weak_table The global weak table. * @param referent The object. * @param referrer The weak reference. */
void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 
                        id *referrer_id) // Address of the new weak pointer
{
    objc_object *referent = (objc_object *)referent_id;
    objc_object **referrer = (objc_object **)referrer_id;

    // Weak reference entity pointer
    weak_entry_t *entry;

    if(! referent)return;

    // The old entity object needs to be passed in the referent
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        // Remove the weak reference pointer from the entity
        remove_referrer(entry, referrer);
        
        bool empty = true;
        if (entry->out_of_line() && entry->num_refs ! =0) {
            empty = false;
        } else {
            for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
                if (entry->inline_referrers[i]) {
                    empty = false; 
                    break; }}}// Determine if the weak reference entity is empty
        if (empty) {
            weak_entry_remove(weak_table, entry); }}// Do not set *referrer = nil. objc_storeWeak() requires that the 
    // value not change.
}


/** * Remove old_referrer from set of referrers, if it's present. * Does not remove duplicates, because duplicates should not exist. * * @todo this is slow if old_referrer is not present. Is this ever the case? * * @param entry The entry holding the referrers. * @param old_referrer The referrer to remove. */
static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
{
    if (! entry->out_of_line()) {
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == old_referrer) {
                entry->inline_referrers[i] = nil;
                return;
            }
        }
        _objc_inform("Attempted to unregister unknown __weak variable "
                     "at %p. This is probably incorrect use of "
                     "objc_storeWeak() and objc_loadWeak(). "
                     "Break on objc_weak_error to debug.\n", 
                     old_referrer);
        objc_weak_error(a);return;
    }

    size_t begin = w_hash_pointer(old_referrer) & (entry->mask);
    size_t index = begin;
    size_t hash_displacement = 0;
    while(entry->referrers[index] ! = old_referrer) { index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
        hash_displacement++;
        if (hash_displacement > entry->max_hash_displacement) {
            _objc_inform("Attempted to unregister unknown __weak variable "
                         "at %p. This is probably incorrect use of "
                         "objc_storeWeak() and objc_loadWeak(). "
                         "Break on objc_weak_error to debug.\n", 
                         old_referrer);
            objc_weak_error(a);return;
        }
    }
    entry->referrers[index] = nil;
    entry->num_refs--;
}
Copy the code

6. Cleaning operation of weak_table_t weak reference table

When the reference count of the OC object pointed to by the weak reference pointer is 0, the release method will call the dealloc method, and the Weak_clear_NO_lock method will be called in dealloc

1. You need to point all weak reference Pointers in weak reference tables to nil!!
2. Remove the WEAK_entry_t structure of the OC object from the weak reference table!!
3. Possible to weak_table HashTable shrink table!!

/** 1. Called by dealloc; 2. nils out all weak pointers that point to the provided object so that they can no longer be used. * * @param weak_table * @param referent The object being deallocated. */
void 
weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 
{
    objc_object *referent = (objc_object *)referent_id;

    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) {
        /// XXX shouldn't happen, but does with mismatched CF/objc
        //printf("XXX no entry for clear deallocating %p\n", referent);
        return;
    }

    // zero out references
    weak_referrer_t *referrers;
    size_t count;
    
    if (entry->out_of_line()) {
        referrers = entry->referrers;
        count = TABLE_SIZE(entry);
    } else {
        referrers = entry->inline_referrers;
        count = WEAK_INLINE_COUNT;
    }
    
    for (size_t i = 0; i < count; ++i) {
        objc_object **referrer = referrers[i];
        if (referrer) {
            if (*referrer == referent) {
            		// Get the address of the weak reference pointer, then get the value of the weak reference pointer from the address and set it to nil!!
                *referrer = nil;
            } else if (*referrer) {
                _objc_inform("__weak variable at %p holds %p instead of %p. "
                             "This is probably incorrect use of "
                             "objc_storeWeak() and objc_loadWeak(). "
                             "Break on objc_weak_error to debug.\n", 
                             referrer, (void*)*referrer, (void*)referent);
                objc_weak_error(a); }}}// Remove weak_entry_t from the weak reference table
    // Determine whether the weakly referenced table HashTable should be shrunk
    weak_entry_remove(weak_table, entry);
}
Copy the code

conclusion

1. Using fixed length arrays globally, SideTables is maintained through HashTable
2. Get the corresponding SideTable using the Hash function associated with the ADDRESS of the OC object
3. Protect the weak reference table of the OC object with spinLock in SideTableweak_table
4. A weak reference tableweak_tableUse the HashTable data structure for maintenanceweak_entry_tthe(OC object, weak Pointers) pairdata
5. A weak reference tableweak_tableThe Hash function used is the Hash function associated with the address of the OC objectweak_entry_t
6. weak_entry_tAccording to internal managementweak pointersQuantity, managed in two waysweak pointer
   1. If the number of weak Pointers is less than or equal to 4, the fixed length array is used for traversal management
   2. Weak Pointers have a value greater than 4 and are managed using HashTable with a looping variable-length array at the bottom
      1. It calculates index using the address correlation function of weak Pointer
      2. Then use open addressing to resolve Hash conflicts

Summary in a word!!

1. Weak pointer management uses 3 hashtables!!
2. Two of them use oc objects as indexes!! There is also an address that uses a weak reference pointer as the index calculation
3. In addition to the global SideTables(), the other two hashtables use open addressing as a Hash collision solution!!