In the process of studying Hash tables, the most well-known thing to see what scenarios are applied in iOS is probably the underlying principle of the weak keyword. I made a deep study of the information on the Internet and further learned the knowledge of iOS memory management. Therefore, I hope I can keep this memory and record it.
Hash
Notes – Hash of Data Structures (rough implementation of OC)
Hash, or Hash table, is one of the basic data structures, and why it’s here, because I feel that understanding Hash helps a lot in understanding the underlying weak keyword.
Hash tables are special data structures that differ from arrays, linked lists, and binary trees, but they evolve from arrays and linked lists.
The essence of a Hash table is an array, and each element in the array is called a bin, which holds elements. The stored procedure is as follows:
- Compute its hash value h based on the key.
- Given n boxes, the key-value pair should be placed in the (h % n) box.
- If the box already has a key-value pair, use methods to resolve the conflict (here the value says split chaining to resolve the conflict, and another method is open addressing).
The Hash table uses a mapping function f: Key ->address maps the keyword to the location where the record is stored in the table. Then, when you want to search for the record, you can directly calculate the location of the record in the table based on the keyword and the mapping relationship. Usually, this mapping relationship is called the Hash function. The storage location calculated using the Hash function and keywords (the storage location here is only the storage location in the table, not the actual physical address) is called the Hash address.
Example: If contact information is stored in a Hash table, to find lisi information, directly calculate the Hash address based on lisi and the Hash function. Because we are modulating the hash by array size, it is possible that different key values will produce the same index value, which is called collision.
When the split chaining method is used to solve the Hash conflict, each box is actually a linked list, and the elements belonging to the same box are stored in a linear table, and the serial number of the table head of each table is the Hash address calculated. The left side of the figure below is the array structure, and the elements in the array are linked list structure.
Hash table Hash table Hash table Hash table Hash table Hash table Hash table Hash
Memory management thinking
ARC’s core ideas:
- Self generated objects, own
- Objects that are not generated by themselves can be held by themselves
- You need to release the objects that you hold when they are not needed
- Objects that are not owned by you cannot be released
Both ARC and MRC follow this approach, but in ARC mode the compiler does the work
Reference counting
Retain, Release, etainCount
Apple implementation :(this part is based on objective-c advanced programming iOS and OS X multithreading and memory management)
- retainCount
__CFDoExternRefOperation
CFBasicHashGetCountOfKey
Copy the code- retain
__CFDoExternRefOperation
CFBasicHashAddValue
Copy the code-release __CFDoExternRefOperation CFBasicHashRemoveValue (when CFBasicHashRemoveValue returns 0, -release calls dealloc)Copy the codeEach method uses the same call to the __CFDoExternRefOperation function, which calls a series of functions with similar names. As indicated by the prefix “CF” to these function names, they are included in the Core Foundation framework source code as the __CFDoExternRefOperation function for cfruntime. c.
__CFDoExternRefOperation function according to the retainCount/retain/release for distribution operation, different function calls, NSObject class retainCount/retain/release instance method may be as shown in the following code:
- (NSUInteger)retainCount {
return (NSUInteger)__CFDoExternRefOperation(OPERATION_retainCount,self);
}
- (id)retain {
return (id)__CFDoExternRefOperation(OPERATION_retain,self);
}
- (void)release {
return __CFDoExternRefOperation(OPERATION_release,self);
}
Copy the codeInt __CFDoExternRefOperation(uintptr_r op,id obj) {cfbasichashTable = fetch object hash (obj); int count; switch(op) {case OPERATION_retainCount:
count = CFBasicHashGetCountOfKey(table,obj);
return count;
case OPERATION_retain:
CFBasicHashAddValue(table,obj);
return obj;
case OPERATION_release:
count = CFBasicHashRemoveValue(table,obj):
return0 == count; }}Copy the codeAs you can see from the code above, Apple probably uses hash tables to manage reference counts. When we call retain, retainCount, release, Call _CFDoExternRefOperation() to get the memory address of the reference count table and the memory address of the object, and then query the table to get the reference count value based on the memory address of the object.
Add 1 for retain, return value directly for retainCount, and subtract 1 for release. (Dealloc obsolete objects are called when CFBasechashRemoveValue reduces the reference count to 0)
Autorelease
Function: The autorelease function is to put an object into the autorelease pool. Each object in the autorelease pool is released once after the autorelease pool is destroyed.
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
id obj = [[NSObject alloc] init];
[obj autorelease];
[pool drain];
Copy the codeIn ARC, use @Autoreleasepool {} to use an Autoreleasepool, and the compiler will look like this:
void *context = objc_autoreleasePoolPush(); // Execute the code objc_autoreleasePoolPop(context);Copy the codeBoth functions are simple wrappers around AutoreleasePoolPage, so the core of the auto-release mechanism lies in this class. AutoreleasePoolPage is a C++ implemented class
AutoreleasePoolThere is no single structure, there are severalAutoreleasePoolPageCombined in the form of a double linked list (respectively corresponding to the structureparentPointers andchildPointer)AutoreleasePoolIs thread-by-thread correspondence (in the structurethreadPointer to current thread)AutoreleasePoolPageEach object is allocated a page of virtual memory, except for the space taken up by instance variables, the rest of the space is used for storageautoreleaseObject address- The above
id *nextThe pointer acts as a cursor to the latest addition to the stackautoreleaseObject at the next location - a
AutoreleasePoolPageWhen the space is full, a new one is createdAutoreleasePoolPageObject, linked list, laterautoreleaseObject is added to the new page
So, if there is only one AutoreleasePoolPage object in the current thread and many autoRelease object addresses are recorded, the memory is as follows:
autorelease
next
next
begin
So, send to an object- autoreleaseMessage, which adds this object to the currentAutoreleasePoolPageThe stacknextThe position to which the pointer points
Whenever an objc_autoreleasePoolPush call is made, the Runtime adds a sentinel object to the current AutoreleasePoolPage with a value of 0 (nil), and the page looks like this:
objc_autoreleasePoolPush
Objc_autoreleasePoolPop (Sentinel object)
- Find the page of the sentinel object based on the address of the sentinel object passed in
- All that will be inserted later than the sentinel object in the current page
autoreleaseObjects are sent once- releaseMessage and move backnextPointer to correct position - Clean up from the most recently added object all the way forward, across several pages, to know where the sentinel is
The objc_autoreleasePoolPop will look like this:
The keyword
__strong
__strong stands for a strong reference, pointing to and holding the object. The object will not be destroyed as long as the reference count is not zero. If a reference is declared without a modifier, it defaults to a strong reference.
- Object through
Alloc, new, copy, mutableCopyTo allocate memory
id __strong obj = [[NSObject alloc] init];
Copy the codeThe compiler converts to the following code:
id obj = objc_msgSend(NSObject, @selector(alloc));
objc_msgSend(obj, @selector(init));
// ...
objc_release(obj);
Copy the codeWhen allocating object memory using alloc, new, copy, or mutableCopy, a strong pointer points directly to an object with a reference count of 1
- Objects are not generated by themselves, but are held by themselves
id __strong obj = [NSMutableArray array];
Copy the codeIn this case, obj also points to an object memory with a reference count of 1. The compiler converts to the following code:
id obj = objc_msgSend(NSMutableArray, @selector(array)); / / replacement we call retain method, is to hold the object obj objc_retainAutoreleaseReturnValue (obj); objc_release(obj);Copy the codeMaking obj pointed to a reference count to 1, however, objc_autoreleaseReturnValue objc_retainAutoreleaseReturnValue has a pairs of functions, these two functions can be used for the operation of the optimization program, the code is as follows:
+ (id)array {
return [[NSMutableArray alloc] init];
}
Copy the codeThe compiler conversion is as follows:
+ (id)array { id obj = objc_msgSend(NSMutableArray,@selector(alloc)); objc_msgSend(obj,@selector(init)); // Call the autoRelease method insteadreturn objc_autoreleaseReturnValue(obj);
}
Copy the codeAutorelease is actually quite expensive, but the Runtime mechanism solves this problem.
To optimize the
Thread Local Storage (TLS) Thread Local Storage (TLS) is used to store a block of memory exclusively for a Thread. For example, in the non-ARM architecture, the method provided by pthreads is used:
void *pthread_getspecific(pthread_key_t);
int pthread_setspecific(pthread_key_t, const void *);
Copy the codeWhen the objc_autoreleaseReturnValue method is called on the return value, the Runtime stores the return value object in TLS and returns the object directly (without calling autoRelease). In external receive this return value objc_retainAutoreleaseReturnValue, found the TLS just exist in the object, then return to this object directly (not call retain). As a result, the caller and the called are mediated by TLS, which implicitly eliminates memory management of the return value. The diagram is as follows:
__weak
__weak means weak references, weak references do not affect the object’s release, and when an object is released, all weak references to it are automatically set to nil, which prevents wild Pointers.
id __weak obj = [[NSObject alloc] init];
Copy the codeAs we know, obj objects are freed immediately after they are generated, mainly because the __weak pointer does not cause the reference count inside the object to change.
Several usage scenarios for __weak:
- Prevent circular references in the Delegate relationship
- Prevent circular references in blocks
- Decorates a control that points to a control that has been created by the Interface Builder
The Runtime maintains a weak table that stores all Pointers to an object’s weak. The weak table is actually a Hash table (which is why I’ll cover Hash tables briefly at the beginning of this article), where Key is the address of the pointed object and Value is an array of addresses of the weak pointer (the Value of which is the address of the pointed object).
The realization principle of weak can be summarized into three steps:
- At initialization,
runtimeWill be calledobjc_initWeakFunction to initialize a new oneweakPointer to the address of an object. - When adding a reference,
objc_initWeakThe function will callobjc_storeWeak()The function,objc_storeWeak()Update pointer pointer to create the corresponding weak reference table. - Release when called
clearDeallocatingFunction.clearDeallocatingThe function first retrieves all objects based on their addressweakArray of pointer addresses, and then iterate through that array and set the data in that array tonilAnd finally put thisentryfromweakDelete from table, and finally clean up the object’s record.
Weak table
Weak table is a weak reference table, which is implemented as a Weak_table structure
struct weak_table_t { weak_entry_t *weak_entries; Weak_entries object size_t num_entries; // Save all weak Pointers to weak_entries of the specified object. // Weak object storage space uintptr_t mask; // Uintptr_t max_hash_displacement; //hashKey maximum offset};Copy the codeThis is a globally weak reference Hash table. Weak_entry_t struct object is used as value, where weak_entries members, literally, are the entry points to the weak reference table.
Weak_entry_t. Weak_entry_t is an internal structure stored in weak-reference tables. Weak_entry_t is responsible for maintaining and storing all weak-reference Hash tables that point to an object. The definition is as follows:
typedef objc_object ** weak_referrer_t; struct weak_entry_t { DisguisedPtr<objc_object> referent; // struct {weak_referrer_t *referrers; uintptr_t out_of_line : 1; uintptr_t num_refs : PTR_MINUS_1; uintptr_t mask; uintptr_t max_hash_displacement; }; struct { // out_of_line=0 is LSB of one of these (don't care which) weak_referrer_t inline_referrers[WEAK_INLINE_COUNT]; }; }};Copy the codeThat is:
weak_table_t(weakGlobal table) : Hash all tablesweakObject that stores all referencesweakObject.weak_entry_t(weak_table_tIndicates the Hash table in the tablevalueValue,weakObject body: used to record the Hash tableweakObject.objc_objct(weak_entry_tObject, used to mark objectsweakObject): Used to identifyweakReference object.
The underlying implementation principle of weak is as follows:
id __weak obj = [[NSObject alloc] init];
Copy the codeThe compiler converts the code as follows:
id obj;
id tmp = objc_msgSend(NSObject, @selector(alloc));
objc_msgSend(tmp,@selector(init));
objc_initWeak(&obj,tmp);
objc_release(tmp);
objc_destroyWeak(&obj);
Copy the codeFor the implementation of objc_initWeak() :
Id objc_initWeak(id *location, id newObj) {// Check whether the object instance is valid. If the object is invalid, the pointer will be releasedif(! newObj) { *location = nil;returnnil; } // Store the weak objectreturn storeWeak(location, newObj);
}
Copy the codeMethod for storing weak objects:
/**
* This functionstores a new value into a __weak variable. It would * be used anywhere a __weak variable is the target of an assignment. * * @param location The address of the weak pointer itself * @param newObj The new object this weak ptr should now point to * * @return\e newObj */ id objc_storeWeak(id *location, id newObj) {// Update the weak reference pointer to id oldObj; SideTable *oldTable; SideTable *newTable; spinlock_t *lock1;#if SIDE_TABLE_STRIPE > 1
spinlock_t *lock2;
#endif
// Acquire locks for old and new values.
// Order by lock address to prevent lock ordering problems.
// Retry ifThe old value changes indexed by the address, preventing the bucket from repeating the following operations which would change the old value */ retry: OldObj = *location; oldTable = SideTable::tableForPointer(oldObj); / / change the pointer to the new value, obtained by newObj index value of the stored address newTable = SideTable: : tableForPointer (newObj); Lock1 = &newtable ->slock;#if SIDE_TABLE_STRIPE > 1
lock2 = &oldTable->slock;
if (lock1 > lock2) {
spinlock_t *temp = lock1;
lock1 = lock2;
lock2 = temp;
}
if(lock1 ! = lock2) spinlock_lock(lock2);#endif
spinlock_lock(lock1);
if(*location ! = oldObj) { spinlock_unlock(lock1);#if SIDE_TABLE_STRIPE > 1
if(lock1 ! = lock2) spinlock_unlock(lock2);#endifgoto retry; Weak_unregister_no_lock (&oldTable-> Weak_table, oldObj, location); // newObj = Weak_register_no_lock (&newTable-> Weak_table, newObj, location); // weak_register_no_lock returns nilif weak store should be rejected
// Set is-weakly-referenced bit in refcount table.
if(newObj && ! NewObj ->isTaggedPointer() {// weak reference bit initialization operation // reference countsetWeaklyReferenced_nolock();
}
// Do not set* Location anywhere else. That would introduce a race. // Don't set the location object, change the pointer to *location = newObj; spinlock_unlock(lock1);#if SIDE_TABLE_STRIPE > 1
if(lock1 ! = lock2) spinlock_unlock(lock2);#endif
return newObj;
}
Copy the codeHere is also a more intuitive flow chart for initializing weak reference objects:
In summary, according to the above stored procedure for weak, you can use the following flowchart to help understand:
Weak The process of releasing weak to nil
The basic process of releasing objects is as follows:
- call
objc_release - Executes because the reference count for the object is 0
dealloc - in
dealloc, call to_objc_rootDeallocfunction - in
_objc_rootDealloc, call toobject_disposefunction - call
objc_destructInstance - The last call
objc_clear_deallocating
The clearDeallocating function first fetches an array of weak pointer addresses based on the object’s address, then iterates through the array to set it to nil, deletes the entry from the Weak table, and clears the object’s record.
void objc_clear_deallocating(id obj) { assert(obj); assert(! UseGC);if (obj->isTaggedPointer()) return; obj->clearDeallocating(); } // Execute the clearDeallocating method inline void objc_object::clearDeallocating() { sidetable_clearDeallocating(); } sidetable_clearDeallocating, locate the weak table, void objc_object::sidetable_clearDeallocating() {
SideTable *table = SideTable::tableForPointer(this);
// clear any weak table items
// clear extra retain count and deallocating bit
// (fixme warn or abort if extra retain count == 0 ?)
spinlock_lock(&table->slock);
RefcountMap::iterator it = table->refcnts.find(this);
if(it ! = table->refcnts.end()) {if (it->second & SIDE_TABLE_WEAKLY_REFERENCED) {
weak_clear_no_lock(&table->weak_table, (id)this);
}
table->refcnts.erase(it);
}
spinlock_unlock(&table->slock);
}
Copy the codeFinally, weak_clear_NO_lock method is called to empty the weak pointer, and the function is implemented as follows:
/** * Called by dealloc; 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 should not 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) {
*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();
}
}
}
weak_entry_remove(weak_table, entry);
}
Copy the codeThe objc_clear_deallocating function does the following:
- from
weakTable to get the address of discarded objects as key values of the record - All annexations to be included in the record
weakThe address of the modifier variable, set tonil - will
weakDelete the record from the table - Removes the record of discarded objects whose addresses are key values from the reference count table
The Runtime maintains a weak table that stores all Pointers to an object’s weak points. The weak table is actually a Hash table, where Key is the address of the specified object and Value is an array of addresses of the specified object.
__unsafe_unretained
__unsafe_unretained does not change the internal reference count of an object. However, the __unsafe_unretained pointer does not set to nil when the object it points to is destroyed. Is an unsafe ownership modifier that does not incorporate ARC memory management.
__autoreleasing
Assigning an object to a variable with the __autoreleasing modifier is the same as calling the object’s autorelease method in MRC.
Id __autoreleasing obj = [[NSObject alloc] init]; }Copy the codeThe compiler converts the following code:
id pool = objc_autoreleasePoolPush();
id obj = objc_msgSend(NSObject,@selector(alloc));
objc_msgSend(obj,@selector(init));
objc_autorelease(obj);
objc_autoreleasePoolPop(pool);
@autoreleasepool {
id __autoreleasing obj = [NSMutableArray array];
}
Copy the codeThe compiler converts the above code as follows:
id pool = objc_autoreleasePoolPush();
id obj = objc_msgSend(NSMutableArray,@selector(array));
objc_retainAutoreleasedReturnValue(obj);
objc_autorelease(obj);
objc_autoreleasePoolPop(pool);
Copy the codeThe above two ways, although the second holding the object’s methods from the alloc method into objc_retainAutoreleasedReturnValue functions, is through objc_autorelease, registered in the autoreleasePool.
Length is too long, a lot of the bottom of the above things, have relevant information online, before is not very good, now come back to read carefully, feel and understand, so the reference on the network data sorting out, increase its impression, hope my understanding will also help to friends, if there are any errors, hope to point out, make progress together, thanks
Weak object initialization, reference, and Autorelease; weak object initialization, reference, and Autorelease