Always Processing

Objective-C Internals: Associated References

Photo of Brian T. KelleyBrian T. Kelley 11 min read
Two children, each at a computer workstation, creating associations between objects on the screen.

A comparison of Apple’s Associated References implementation and one I wrote for historical context, with additional notes about use with tagged pointer objects and what the assign association policy actually does.

I remember eagerly awaiting the day we changed the minimum deployment target in what would become Microsoft Office 2016 for Mac to Mac OS X 10.6[1]. Snow Leopard introduced a lot of new APIs, including Grand Central Dispatch and blocks. But, I was most excited to start using Objective-C Associative References to replace some terrible code.

The Old Way

Objective-C’s greatest strength (and weakness) is its dynamic method binding. Virtually all major third-party apps (ab)use this feature to fill a functionality gap or mitigate app/system architecture impedance mismatches.

The ability to tie an object’s lifetime to the lifetime of an object instantiated and controlled by a third party (i.e., Apple) was one such functionality gap. Before the runtime provided this feature, an app could implement this functionality by, in part, pre-patching the implementation of -[NSObject dealloc]. The following code sample shows how a third party may have implemented Associative References using this approach.

#import <Foundation/Foundation.h>
#import <objc/runtime.h>

static OSSpinLock s_lock;               // for main side table
static NSMapTable *s_associatedObjects; // main side table
static IMP s_NSObject_dealloc;          // original implementation

void APAssociatedObjectSet(id object, id association) {
  id previousAssociation = nil;

  // retain does not require the lock, so do it outside of the
  // lock to minimize time spent holding the lock
  [association retain];

  OSSpinLockLock(&s_lock);
  previousAssociation = [s_associatedObjects objectForKey:object];
  if (association != nil) {
    [s_associatedObjects setObject:association forKey:object];
  } else {
    [s_associatedObjects removeObjectForKey:object];
  }
  OSSpinLockUnlock(&s_lock);

  // release outside of the lock in case this is the last
  // release, as the dealloc implementation acquires the lock
  [previousAssociation release];
}

id APAssociatedObjectGet(id object) {
  OSSpinLockLock(&s_lock);
  id association = [s_associatedObjects objectForKey:object];
  // retain the associated object to ensure it's not deallocated
  // while in use by the caller in case another thread changes the
  // associated object between now and then
  [association retain];
  OSSpinLockUnlock(&s_lock);

  return [association autorelease];
}

static void APAssociatedObject_dealloc(id self, SEL _cmd) {
  // release any associated object and remove the side table entry
  APAssociatedObjectSet(self, nil);
  (*s_NSObject_dealloc)(self, _cmd);
}

void APAssociatedObjectInitialize(void) {
  s_lock = OS_SPINLOCK_INIT;
  // The key is weak to prevent the object from becoming immortal.
  // The value is weak to explicitly control the retain count to
  // prevent dealloc reentrancy deadlocks.
  s_associatedObjects=[NSMapTable mapTableWithWeakToWeakObjects];

  // Pre-patch -[NSObject dealloc] to clean up s_associatedObjects
  Method m = class_getInstanceMethod([NSObject class],
                                     @selector(dealloc));
  s_NSObject_dealloc = method_getImplementation(m);
  method_setImplementation(m, (IMP)&APAssociatedObject_dealloc);
}

Although the implementation is only 59 lines, including white space and comments, there are a few things I want to call out:

  • This implementation supports 0 or 1 object associations but could support an arbitrary number of associations, like objc_setAssociatedObject(), with minor revisions. Alternatively, the client could use an NSMutableDictionary to associate an arbitrary number of objects.

  • Every -dealloc needs to acquire a lock to perform bookkeeping (in addition to the runtime and allocator lock acquisition(s)). We saw in a previous post that the runtime has a fast deallocation path for object instances that do not have an associated reference (in addition to other criteria), enabling it to avoid locking overhead for most cases.

  • Removing an association may cause the associated object to deallocate, which, in turn, may cause its associated objects to deallocate. So, the implementation must avoid recursion while holding the lock, as OSSpinLock is not reentrant.

  • Pre-patching -dealloc on the class of the object gaining an association is not a viable approach for two reasons:

    1. A class hierarchy may have multiple patches. For example, after setting an associated object on an NSObject and another on NSView, all NSView instances, including subclasses, call into the patch twice during deallocation. An implementation could handle this case but at the cost of additional complexity.

    2. Calling into the correct -dealloc from the patch becomes more challenging. Continuing with the above example, if an NSTableView is deallocating, how does the patch know whether it should call the -[NSView dealloc] implementation or the -[NSObject dealloc] implementation? (The class identity of self is always NSTableView.) A significant amount of bookkeeping would be required to track where an object is in its dealloc chain and to handle additional deallocations that occur as part of its deallocation.

  • Objective-C Automatic Reference Counting (ARC) didn’t debut until OS X 10.7 Lion. So I want to highlight two things that are no longer relevant to the modern Objective-C programmer:

    • The retain and autorelease calls in APAssociatedObjectGet() guarantee the returned object lives through the current autorelease scope. Without this, another thread may cause the object to deallocate between its retrieval from the map table and its return to the caller.

    • The use of weak in the map table’s mapTableWithWeakToWeakObjects factory method does not have ARC’s zeroing weak reference semantics. Instead, it’s the equivalent of ARC’s unsafe_unretained.

  • APAssociatedObjectInitialize() could have an __attribute__((constructor)) to initialize the feature before main() is called. I left that out as major apps usually have a sophisticated initialization system that would call this function.

Next, let’s see how Apple’s Objective-C runtime implements this feature.

The Apple Way

The above third-party implementation and commentary align shockingly well with Apple’s implementation. (I say shocking because I wrote it before looking up Apple’s implementation[2].)

First, let’s look at objc_setAssociatedObject(), which simply calls _object_set_associative_reference().

runtime/objc-references.mm lines 170-219
DisguisedPtr<objc_object> disguised{(objc_object *)object};
ObjcAssociation association{policy, value};

// retain the new value (if any) outside the lock.
association.acquireValue();

bool isFirstAssociation = false;
{
  AssociationsManager manager;
  AssociationsHashMap &associations(manager.get());

  if (value) {
    auto refs_result = associations.try_emplace(disguised, ObjectAssociationMap{});
    if (refs_result.second) {
      /* it's the first association we make */
      isFirstAssociation = true;
    }

    /* establish or replace the association */
    auto &refs = refs_result.first->second;
    auto result = refs.try_emplace(key, std::move(association));
    if (!result.second) {
      association.swap(result.first->second);
    }
  } else {
    auto refs_it = associations.find(disguised);
    if (refs_it != associations.end()) {
      auto &refs = refs_it->second;
      auto it = refs.find(key);
      if (it != refs.end()) {
        association.swap(it->second);
        refs.erase(it);
        if (refs.size() == 0) {
          associations.erase(refs_it);
        }
      }
    }
  }
}

if (isFirstAssociation)
  object->setHasAssociatedObjects();

// release the old value (outside of the lock).
association.releaseHeldValue();

Given the alignment with the previous section, I’ll simply highlight key similarities and differences relative to my implementation.

  • DisguisedPtr is used to inhibit heap tracing in tools like leaks.

  • The ObjcAssociation helper object implements the association policy (storage with assign, retain, or copy semantics, and whether reads are atomic or nonatomic).

  • The AssociationsManager is an RAII convenience object to lock and unlock the associations spinlock (now an unfair lock).

  • Object associations are stored using a hash map (specifically LLVM’s DenseMap). A top-level hash map maps object pointers to an associations hash map, which maps keys to ObjcAssociations (the object and its retain policy).

  • Associating a nil value removes any previously associated object.

  • When an object gains its first association, the runtime updates its state to turn off the fast deallocation path.

  • The release of any previously associated object takes place outside of the lock.

Like the setter, objc_getAssociatedObject() simply calls _object_get_associative_reference(). The get path is straightforward, so there’s nothing for me to comment on! 🙊

Apple’s implementation provides a curious function, objc_removeAssociatedObjects(). I’m honestly not sure why this is a public API—the comment in runtime.h advises against using it (and for a good reason):

The main purpose of this function is to make it easy to return an object to a "pristine state”. You should not use this function for general removal of associations from objects, since it also removes associations that other clients may have added to the object. Typically you should use objc_setAssociatedObject with a nil value to clear an association.

Like the getter and setter functions, objc_removeAssociatedObjects() calls _object_remove_associations(). But, this internal function takes one additional parameter: bool deallocating, which is false when called by objc_removeAssociatedObjects(). This internal function has only one other caller, objc_destructInstance(), which, unsurprisingly, passes true for deallocating.

So, what does the deallocating flag do? A comment in the function explains its purpose:

If we are not deallocating, then SYSTEM_OBJECT associations are preserved.

Apple has an internal policy flag, OBJC_ASSOCIATION_SYSTEM_OBJECT, which prevents its associated objects from being removed by objc_removeAssociatedObjects(). You can shoot yourself in the foot using this function, but Apple will prevent you from violating their assumptions.

I suspect this is why the association key has a type of void *: pointer keys are hard to identify in Apple’s frameworks and subsequently (ab)use in third party-apps vs., for example, string keys which are easy-ish to find and use (e.g., NSNotificationName).

Tagged Pointer Objects

What happens when setting an associated object on a tagged pointer object? The effect is the same as assigning the object to a global variable with the same storage policy: the object remains until a new value is assigned. So, setting an associated object on a tagged pointer object will effectively leak the associated object.

The associated object implementation has no code paths to handle tagged pointers (not even to log a warning in the console). So, the runtime stores the tagged pointer in the associations hash map where it lives indefinitely because tagged pointer objects never deallocate.

Another side effect of tagged pointer objects is that they effectively intern all values. While some types like NSNumber are known to implement some form of interning, NSString did not have such behavior. But, the NSString tagged pointer code path is aggressive enough that localized strings loaded from disk may yield a tagged pointer object! Thus, any code setting associated objects on types of NSString may find associated objects stomping on each other if the string instances are tagged pointer objects instead of discrete instances.

Although the use of tagged pointer objects is considered an internal implementation detail, take a look at the classes that use tagged pointers and avoid using associated objects with any objects with those types.

A Closer Look At assign Storage

In writing the post, I realized I’ve been misusing this API for over a decade 🤦‍♂️. The comment next to the OBJC_ASSOCIATION_ASSIGN policy says:

Specifies a weak reference to the associated object.

As mentioned in The Old Way section, before ARC, the term weak is equivalent to ARC’s unsafe_unretained; this flag does not use ARC zeroing weak reference semantics. Take a look through the implementation for any use of weak. There isn’t any!

I have a lot of grepping and code reviewing to do this week…​

Conclusion

A third-party implementation of Associated References can nearly match what Apple can do with a first-party implementation, with the main first-party advantage being the availability of a fast deallocation path for objects without associated objects. New runtime optimizations (i.e., tagged pointer objects) may cause unexpected behavior for code associating objects with objects whose uniqueness and lifetime may change across OS versions. And, historical context is essential—the assumptions underlying documentation may change over time, warping its meaning.

1. By the time Office 2016 launched, macOS 10.12 Sierra was the current release. So, following the n-2 pattern, Office’s minimum deployment target was OS X 10.10 Yosemite.
2. I did make one revision after reading through Apple’s implementation, which was to perform the associated object’s retain outside of the lock.