IOS management object memory data structure and operation algorithm –SideTables, RefcountMap, weak_table_t-

First written language expression ability is poor. If there is not clear enough to comment directly to reply to me, I would like to modify. This article tries to break away from the characteristics of language. Even if you do not understand iOS development, do not understand Objective-C language can also see this article.
by reading this article, you can understand the data structure of iOS memory management object is what kind of, and the operation logic. The object of the reatin, release, dealloc operation is how to achieve the algorithm, weak pointer is how to automatically change the nil.
this part of the code content in Apple’s open source project objc4-706.

This paper process:
a, the concept of reference count
two, throw the problem
three, data structure analysis (SideTables, RefcountMap, weak_table_t)

The concept of reference counting

This part is for non iOS engineers, easy to understand the concept of reference counting, circular references, weak references. If you already know the concepts you can skip the first part.

We all know that occupied a block of memory is very easy to new an object, we’re done. But when to recycle? No recovery is not natural, and then the memory can not be completely recycled. Recycling as early as possible, when the real use of the wild pointer problem. Recycling late and wasting valuable memory resources. We have to come up with a way to manage memory. In this paper, we only discuss the reference count method of iOS management object memory.
in memory of each object has one reference counter. When an object A is referenced by another guy, A’s reference counter is +1, and if another guy references to A, then A’s reference counter is +1. When one of these guys no longer references A, A’s reference counter will -1. Until the reference count of A is reduced to 0, no one needs it anymore, and it’s time to release it.

In the reference count, each object is responsible for maintaining the count of all references to the object. When a new reference points to an object, the reference counter is incremented, and when the reference is removed, the reference count is decreased. When the reference counts to zero, the object will release the occupied resources.

The mechanism seems to know when to release the object should be in memory, but there is a problem we need to solve the circular reference.

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
9F4E7963-0B4B-4153-A9FD-C3E9689B545B.png

now has two objects in memory, A and B.

A.x = B; B.y = A;
  • If A is doing video processing, B is to deal with audio.
  • The reference count for A is now 1 (quoted by B.y).
  • The reference count for B is now 1 (quoted by A.x).
  • So when A finished his video work, he found that his reference count was 1 or not, and he thought, “Oh, there are people who need me, and I can’t be released.” “” “” “” “”. “
  • When B finished the audio operation, he noticed that his reference count was 1, and he felt, “I can’t be released. “

That two objects each other with each other who have circular references will not be released to cause memory leaks. In order to solve this problem, we introduce the concept of weak reference.
weak references pointing to object references, but does not increase the reference count of the object. Like the following figure. The dashed line is a weak reference (Elmar’s ugly painting)

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
EFDCA2C8-4E42-48EF-AE5F-3D4607B6CF68.png
A.x = B; __weak = A = B.y;

Here we let B y is a weak reference, it can also point to A but A does not increase the reference count.

  • So the reference count of A is 0, and the reference count of B is 1 (quoted by A.x).
  • When A finishes his video operation, he finds that his reference count is 0, and OK can release it.
  • Then A.x was released. (A.x is a variable within the object A)
  • A.x was released and the reference count of B was 0.
  • B can then be released after his audio operation is processed.

Circular reference problem solved. We may wish to think about this program will not have other problems?
thinking…
there is a wild pointer problem waiting for us to solve.

  • If A finishes his video task, he is released.
  • B is still in the process.
  • But in the process of B need to access A (B.y) to get some data.
  • Because the A has been released, it causes a wild pointer error to be accessed again.

So we need a mechanism that allows the release of A, I will visit all the pointers to the A (such as B.y) when they are friendly that A does not exist, so as to avoid mistakes.
we assume here with an array of all weak references pointing to A are kept up, and when A was released to an array of all the weak references are set to nil (equivalent to NULL in other languages). So when B visit B.y again will return to nil. By way of null space can avoid the wrong pointer. Of course, it is easy to say, let’s look at how Apple is achieved.

Two, throws the question

Ramble in front said a lot, really now throw this discussion problem.

  • 1, how to achieve the reference count management, control plus one minus one and release?
  • 2, why maintain the weak pointer to prevent wild pointer error?

Three, data structure analysis (SideTables, RefcountMap, weak_table_t)

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
9BE315AE-E25E-41D1-99FD-883EDC5884F6.png

a lot of people see this article after the reaction of SideTables, SideTable, RefcountMap three relationship is not clear. Maybe I’m not very good in this article. You can see my second article in a university dormitory example, combined with this example may be helpful to understand the relationship between the three.
let’s talk about the top SideTables
first

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
EA251BCE-F990-4CA6-B66E-8822D8089D61.png

for reference counting and weak pointer management of all objects, apple created a global SideTables, although the name has a “s” but he is actually a global Hash table, the contents are all equipped with SideTable structure. It uses the memory address of the object when it’s key. Manage reference counts and weak pointers on it.
because the object reference counting related operation should be atomicity. Otherwise, if more than one thread to write a reference count of the object, it will cause data confusion, lost the meaning of memory management. At the same time, because the number of objects in the memory is very very large, the need for very frequent operation of the SideTables, it can not lock the entire Hash table. Apple uses a separate lock technology.

Lock and lock the partition of separation between
another way to reduce lock contention is to reduce the frequency of the thread requesting the lock. Split lock (lock splitting) and split lock (lock striping) are two ways to achieve this purpose. Independent state variables should be protected using separate locks. Sometimes developers mistakenly use a lock to protect all state variables. These techniques reduce the granularity of the lock and achieve better scalability. However, these locks need to be carefully assigned to reduce the risk of deadlock.
if a lock to protect multiple independent state variables, you may be able to spin through the lock, so that each lock guard different variables, thereby improving scalability. With this change, the frequency of each lock is reduced. The split lock can be used to transform most of them into non competitive locks, which can improve the performance and scalability.
split lock can sometimes be extended into several sets with lock block, and they belong to the object independent of each other, such a situation is the separation of the lock.

Because memory addresses the use of object when the key Hash segment is so mean. Assuming that the Hash table has n elements, you can reduce the conflict of Hash to N, support for concurrent write operations n.

SideTable

When we use SideTables[key] to get the SideTable, the structure of SideTable are as follows:

1, a spin lock. Spinlock_t slock;

The spin lock is more suitable for the user to keep the lock time short. It is because the spin lock users generally keep the lock time is very short, so it is very necessary to choose spin rather than sleep. Read and write semaphore signal adapted to maintain a long time the situation, they will cause the caller sleep, and can be used in the process context, while the spin lock adapted to maintain a very short time, it can be used in any context.

Effect of it is time for SideTable lock is cited in the operation, to avoid data errors.
apple on the lock option can be said to be better. Apple knows that the operation of the reference count is very fast. So the choice of the spin lock is not so high, but indeed efficient, I can only say here, “double click 666, the old iron! No problem! “

2, the reference counter RefcountMap refcnts;

Object specific reference counting number is recorded here.
here RefcountMap is C++ Map. Why does Hash need a Map later? In fact, apple is using the block method.
for example
now suppose there are 16 objects in memory.
0x0000, 0x0001, 0x000e,
… 0x000f… We create a SideTables[8] to store the 16 objects, then the search occurred when the conflict probability is 1/8 Hash.
hypothesis SideTables[0x0000] and SideTables[0x0x000f] conflict, mapped to the same result.

SideTables[0x0000] = = SideTables[0x0x000f] ==> point to the same SideTable

Apple to memory management two objects are placed in the same SideTable. You need to call table.refcnts.find (0x0000) or table.refcnts.find (0x000f) again in this SideTable to find their real reference counter.
here is a diversion. The number of objects in memory is too large by the first Hash form was filtered first, then we also need to re positioning through the Map in order to accurate references to the object we want to find the counter.
reference counter storage structure is as follows:
note discussed here is table.refcnts.find (this) structure of value, as RefcountMap is what we discussed in the next article

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
77490066-7101-4F70-BF50-604D3658F7C4.png

The data type of the reference counter is:

Typedef __darwin_size_t size_t;

A further look at its definition is actually unsigned long, in the 32 and 64 bit operating system, which takes up to 32 and 64 bit.
Apple often uses bit mask technology. Here is no exception. Take 32 for example, can be understood as there are 32 boxes in a row across the table in front of you. The box can hold 0 or 1 numbers two. We stipulate that the box at the end is low, and the box on the left is high.

  • (1UL< < 0) means to put a “1” in the box on the right side, and then the “1” to the left to move the position of the 0 (): 0b0000 0000000000000000
  • (1UL< < 1) means to put a “1” in the box on the right side, and then move the “1” to the left: 0b0000, 0000000000000000, 000000000010

To analyze the structure of the reference counter (right side of the diagram) from low to high.

  • (1UL< < 0) WEAKLY_REFERENCED
    said if there are weak references pointing to this object, if any (= 1) when the object to release the need to put all the weak references pointing to it into nil (equivalent to other language NULL), avoid wild pointer errors.
  • (1UL< < 1) DEALLOCATING
    indicates whether the object is being released. 1 is released, no 0.
  • The part of the REAL COUNT in the REAL COUNT
    diagram is the true reference count storage area of the object. So we say that the reference count plus one or minus one, in fact, the entire unsigned long plus four or minus four, because the true count is from the beginning of the 2^2.
  • (1UL< < (WORD_BITS-1)) SIDE_TABLE_RC_PINNED
    WORD_BITS in the 32 and 64 bit systems respectively equal to 32 and 64. In fact, this one does not have any specific meaning, that is, with the object’s reference count continues to grow. If this bit is 1, the reference count is already the largest and can no longer be added.

3, to maintain the weak pointer structure weak_table_t weak_table;

IOS management object memory data structure and operation algorithm --SideTables, RefcountMap, weak_table_t-
9BE315AE-E25E-41D1-99FD-883EDC5884F6.png

above RefcountMap refcnts; is a layer structure, can directly find the corresponding value by key. Here is a two story structure.
contains two elements first layer structure.
first element of weak_entry_t *weak_entries; is an array, the above RefcountMap is through find (key) to find the exact elements. Weak_entries is to find the corresponding entry through the cycle.
(top management reference counter apple is using Map, here is the use of Apple management weak pointer array, interested friends can think about why Apple is using the two kinds of different structure)
second element num_entries is used to maintain the array always have a suitable size. For example, when the number of elements in the array exceeds 3/4, the size of the array is multiplied by 2.

Second layer weak_entry_t structure contains 3 parts

  • 1, the address of the object referred to by the referent:
    . In front of the loop traversal search is to determine whether the target address is equal to him.
  • 2, a variable array of referrers
    , which holds the address of all weak references to this object. When this object is released, all pointers in the referrers will be set to nil.
  • 3, the inline_referrers
    has only an array of 4 elements, which is used to store a pointer to a weak reference by default. Use referrers to store pointers when more than 4.

OK we look at the map to see the pseudo code go through the process

1, alloc

At this time, in fact, does not operate SideTable, specific reference:

Easy to understand ARC (on)
Objc uses a similar list structure to record the reference count. And at the time of initialization.

2, retain: NSObject.mm line:1402-1417

//1, the object memory address, find the corresponding SideTable SideTable& in SideTables; table = SideTables (//2, [this]); the object memory address in refcnts take the reference count / / here is table SideTable, refcnts RefcountMap size_t& refcntStorage = table.refcnts[this]; //3 PINNED, a judge is not 1, then +4 (if! (refcntStorage & PINNED)) {refcntStorage = (1UL< < 2);}

3, release NSObject.mm line:1524-1551

Table.lock (= table.refcnts.find); reference counter (this); (//table.refcnts.end) says the use of a iterator iterator reached end () if (reference counter () = = table.refcnts.end) {/ / marker object is the release of table.refcnts[this] = SIDE_TABLE_DEALLOCATING;} else if (reference counter < SIDE_TABLE_DEALLOCATING) {/ / here is very interesting. When Xiao Yu (1UL< < 1) when the situation is in front of / / reference meter digital is 0, behind the weak reference mark WEAKLY_REFERENCED may have a weak reference or not weak reference 1 / / 0 / / in order not to affect the state of the WEAKLY_REFERENCED reference counter |= SIDE_TABLE_DEALLOCATING;} else if (SIDE_TABLE_RC_PINNED for the 0) {SIDE_TABLE_RC_ONE} = reference counter; (table.unlock); if done on If the object is to be released after the operation, the dealloc is called

4, dealloc NSObject.mm line:1555-1571

Dealloc operation have also done a lot of logical judgment and other treatment, we here put aside the logic is only discussed in the following section (sidetable_clearDeallocating)

SideTable& table = SideTables ([this]); (table.lock); table.refcnts.find = reference counter (this); if (table.refcnts.end) (reference counter! = {if (SIDE_TABLE_WEAKLY_REFERENCED) reference mark counter is 1) {weak_clear_no_lock (& table.weak_table, this (ID));} / / deleted from the refcnts reference counter table.refcnts.erase (it);} (table.unlock);

Weak_clear_no_lock () is the key, it is when the object is destroyed when dealing with all weak reference pointer method.

Weak_clear_no_lock objc-weak.mm line:461-504 void weak_clear_no_lock (weak_table_t *weak_table, ID //1, referent_id) {get destroyed object pointer objc_object *referent = (objc_object * referent_id); //2, find out through a pointer corresponding to the entry weak_entry_t *entry = weak_entry_for_referent in weak_table (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 //3;}, all reference set to nil weak_referrer_t *referrers; size_t count; if (entry-> out_of_line) {//3.1 (), if more than 4 weak references will be referrers within the array are weak references the Cheng nil. Referrers = entry-> count = referrers; TABLE_SIZE (entry);} else {//3.2, no more than 4 will be inline_referrers in an array of weak references are set to nil inline_referrers; referrers = entry-> count = WEAK_INLINE_COUNT;} / / cycle set all the references for nil 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 "(void*), referrer, *referrer, referent (void*)); (objc_weak_error);}}}, //4 removed from the weak_table entry weak_entry_remove (weak_table, entry);}

Here we have the SideTables process over again, I hope you look happy.
welcome to add my micro-blog http://weibo.com/xuyang186
reprint please indicate the source, thank you.

Reference

Advanced iOS iOS (Objective-C) memory management – two simple ARC (on) our object will experience what Objective-C refers to the first day of hospital admission to the Runtime counting principle of neural Objective-C ISA and Class Pointer Why is weak_table_t understand Tagged a member of SideTable in Objective-C runtime How can the Objective-C runtime? Know whether a weakly referenced object is still alive?