Why is weak_table_t a member of SideTable in Objective-C runtime?

Question

I am reading code of objc from https://github.com/opensource-apple/objc4.

In the code, there is a struct SideTable, which contains reference count of corresponding object and a weak_table_t.

struct SideTable {
    spinlock_t slock;
    RefcountMap refcnts;
    weak_table_t weak_table;

    SideTable() {
        memset(&weak_table, 0, sizeof(weak_table));
    }

    ~SideTable() {
        _objc_fatal("Do not delete SideTable.");
    }

    void lock() { slock.lock(); }
    void unlock() { slock.unlock(); }
    bool trylock() { return slock.trylock(); }

    // Address-ordered lock discipline for a pair of side tables.

    template<bool HaveOld, bool HaveNew>
    static void lockTwo(SideTable *lock1, SideTable *lock2);
    template<bool HaveOld, bool HaveNew>
    static void unlockTwo(SideTable *lock1, SideTable *lock2);
};

And the SideTable of an object can be retrieved by SideTables()[obj] as the SideTable of every object is stored in a StripedMap, which is actually an array using the hash value of an object's address as index.

But according to the code of weak_entry_for_referent, the runtime gets the weak_entry_t of a referent through checking weak_table->weak_entries[index].referent.

static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);

    weak_entry_t *weak_entries = weak_table->weak_entries;

    if (!weak_entries) return nil;

    size_t index = hash_pointer(referent) & weak_table->mask;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {
        index = (index+1) & weak_table->mask;
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) {
            return nil;
        }
    }

    return &weak_table->weak_entries[index];
}

It means the weak_table contains more than the weak entries for a single object. Then why is weak_table_t a member of SideTable instead of a global data?

As I can't find code which really initialize SideTable of object (storeStrong just use the SideTable without initializing it at first) and weak_table, I can't quite understand how things work in the background.

Can anybody give me a hint?

Answer 1

why is weak_table_t a member of SideTable

There are two cases should be solved if use a global weak_table_t.(refcnts has the same cases)

• case 1: Maintaining the weak_table_t should be thread safe, so we need lock
• case 2: lock means slow, but the developer want the system run as fast as possible

Only one global weak_table_t can't solved the two cases above.

Actuactly, class StripedMap solves the two cases by using lock striping, by wrapping weak_table_t and refcnts together inside SideTable.

Let's take a look at the code below, copied from objc-private.h.

// 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 {
    // ... code for StripedMap
    PaddedT array[StripeCount]; // There are 8 SideTables if define TARGET_OS_IPHONE
    // ... code for StripedMap
}

8 SideTables store 8 weak_table_t and 8 spinlock_t slock. The system can maintain 8 weak_table_t cocurrently at most for 8 thread. I think this is fast enought on a iOS device.

SideTable init

SideTablesMap.init(); called from arr_init(). You can use "Find Call Hierarchy" on init of class ExplicitInit to find the call hierarchy

Answer 2

The only reasonable reason I can figure out is:

The SideTableBuf for all SideTable instances is actually a bucket array. Different objects may be put in the same bucket. So a single SideTable may serve for different pointers according to the hash algorithm. And then, the weak_table actually contains weak_entry_t for different referents. That's why we need check the referent by:

while (weak_table->weak_entries[index].referent != referent)

And the weak_table serves for the current SideTable only, so it can't be a global data.

Answer 3

Weak table is a shared resource which allows access from multiple threads. Thus, we need a lock to avoid data inconsistency. So weak_table_t is wrapped in SideTable along with spinlock_t.

However, it's inefficient to have the whole table locked for each access. Considering the case, Thread A has acquired the lock, and is modifying the weak table. Meanwhile, Thread B wants to modify the weak table, so it tries to acquire the lock. However, only one thread can own the lock at a time. So Thread B blocks. If this happens all the time, access to weak table would be very slow.

Then developers came up with the pattern, "Lock Striping", dividing the table into multiple buckets, each of which can be locked independently. Upon that modifying bucket 1 doesn't block the modifying of bucket 2. So SideTable is wrapped in StripedMap for partition purpose.