2 * Copyright (c) 2010-2011 Apple Inc. All rights reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
21 * @APPLE_LICENSE_HEADER_END@
24 #include "objc-private.h"
26 #include "objc-weak.h"
30 #include <sys/types.h>
31 #include <libkern/OSAtomic.h>
33 #define TABLE_SIZE(entry) (entry->mask ? entry->mask + 1 : 0)
35 static void append_referrer(weak_entry_t *entry, objc_object **new_referrer);
38 void objc_weak_error(void)
42 * Unique hash function for object pointers only.
44 * @param key The object pointer
46 * @return Size unrestricted hash of pointer.
48 static inline uintptr_t hash_pointer(objc_object *key) {
49 return ptr_hash((uintptr_t)key);
53 * Unique hash function for weak object pointers only.
55 * @param key The weak object pointer.
57 * @return Size unrestricted hash of pointer.
59 static inline uintptr_t w_hash_pointer(objc_object **key) {
60 return ptr_hash((uintptr_t)key);
64 * Grow the entry's hash table of referrers. Rehashes each
67 * @param entry Weak pointer hash set for a particular object.
69 __attribute__((noinline, used))
70 static void grow_refs_and_insert(weak_entry_t *entry,
71 objc_object **new_referrer)
73 assert(entry->out_of_line);
75 size_t old_size = TABLE_SIZE(entry);
76 size_t new_size = old_size ? old_size * 2 : 8;
78 size_t num_refs = entry->num_refs;
79 weak_referrer_t *old_refs = entry->referrers;
80 entry->mask = new_size - 1;
82 entry->referrers = (weak_referrer_t *)
83 _calloc_internal(TABLE_SIZE(entry), sizeof(weak_referrer_t));
85 entry->max_hash_displacement = 0;
87 for (size_t i = 0; i < old_size && num_refs > 0; i++) {
88 if (old_refs[i] != nil) {
89 append_referrer(entry, old_refs[i]);
94 append_referrer(entry, new_referrer);
95 if (old_refs) _free_internal(old_refs);
99 * Add the given referrer to set of weak pointers in this entry.
100 * Does not perform duplicate checking (b/c weak pointers are never
101 * added to a set twice).
103 * @param entry The entry holding the set of weak pointers.
104 * @param new_referrer The new weak pointer to be added.
106 static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
108 if (! entry->out_of_line) {
109 // Try to insert inline.
110 for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
111 if (entry->inline_referrers[i] == nil) {
112 entry->inline_referrers[i] = new_referrer;
117 // Couldn't insert inline. Allocate out of line.
118 weak_referrer_t *new_referrers = (weak_referrer_t *)
119 _calloc_internal(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
120 // This constructed table is invalid, but grow_refs_and_insert
121 // will fix it and rehash it.
122 for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
123 new_referrers[i] = entry->inline_referrers[i];
125 entry->referrers = new_referrers;
126 entry->num_refs = WEAK_INLINE_COUNT;
127 entry->out_of_line = 1;
128 entry->mask = WEAK_INLINE_COUNT-1;
129 entry->max_hash_displacement = 0;
132 assert(entry->out_of_line);
134 if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
135 return grow_refs_and_insert(entry, new_referrer);
137 size_t index = w_hash_pointer(new_referrer) & (entry->mask);
138 size_t hash_displacement = 0;
139 while (entry->referrers[index] != NULL) {
140 index = (index+1) & entry->mask;
143 if (hash_displacement > entry->max_hash_displacement) {
144 entry->max_hash_displacement = hash_displacement;
146 weak_referrer_t &ref = entry->referrers[index];
152 * Remove old_referrer from set of referrers, if it's present.
153 * Does not remove duplicates, because duplicates should not exist.
155 * @todo this is slow if old_referrer is not present. Is this ever the case?
157 * @param entry The entry holding the referrers.
158 * @param old_referrer The referrer to remove.
160 static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
162 if (! entry->out_of_line) {
163 for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
164 if (entry->inline_referrers[i] == old_referrer) {
165 entry->inline_referrers[i] = nil;
169 _objc_inform("Attempted to unregister unknown __weak variable "
170 "at %p. This is probably incorrect use of "
171 "objc_storeWeak() and objc_loadWeak(). "
172 "Break on objc_weak_error to debug.\n",
178 size_t index = w_hash_pointer(old_referrer) & (entry->mask);
179 size_t hash_displacement = 0;
180 while (entry->referrers[index] != old_referrer) {
181 index = (index+1) & entry->mask;
183 if (hash_displacement > entry->max_hash_displacement) {
184 _objc_inform("Attempted to unregister unknown __weak variable "
185 "at %p. This is probably incorrect use of "
186 "objc_storeWeak() and objc_loadWeak(). "
187 "Break on objc_weak_error to debug.\n",
193 entry->referrers[index] = nil;
198 * Add new_entry to the object's table of weak references.
199 * Does not check whether the referent is already in the table.
201 static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry)
203 weak_entry_t *weak_entries = weak_table->weak_entries;
204 assert(weak_entries != nil);
206 size_t index = hash_pointer(new_entry->referent) & (weak_table->mask);
207 size_t hash_displacement = 0;
208 while (weak_entries[index].referent != nil) {
209 index = (index+1) & weak_table->mask;
213 weak_entries[index] = *new_entry;
214 weak_table->num_entries++;
216 if (hash_displacement > weak_table->max_hash_displacement) {
217 weak_table->max_hash_displacement = hash_displacement;
222 static void weak_resize(weak_table_t *weak_table, size_t new_size)
224 size_t old_size = TABLE_SIZE(weak_table);
226 weak_entry_t *old_entries = weak_table->weak_entries;
227 weak_entry_t *new_entries = (weak_entry_t *)
228 _calloc_internal(new_size, sizeof(weak_entry_t));
230 weak_table->mask = new_size - 1;
231 weak_table->weak_entries = new_entries;
232 weak_table->max_hash_displacement = 0;
233 weak_table->num_entries = 0; // restored by weak_entry_insert below
237 weak_entry_t *end = old_entries + old_size;
238 for (entry = old_entries; entry < end; entry++) {
239 if (entry->referent) {
240 weak_entry_insert(weak_table, entry);
243 _free_internal(old_entries);
247 // Grow the given zone's table of weak references if it is full.
248 static void weak_grow_maybe(weak_table_t *weak_table)
250 size_t old_size = TABLE_SIZE(weak_table);
252 // Grow if at least 3/4 full.
253 if (weak_table->num_entries >= old_size * 3 / 4) {
254 weak_resize(weak_table, old_size ? old_size*2 : 64);
258 // Shrink the table if it is mostly empty.
259 static void weak_compact_maybe(weak_table_t *weak_table)
261 size_t old_size = TABLE_SIZE(weak_table);
263 // Shrink if larger than 1024 buckets and at most 1/16 full.
264 if (old_size >= 1024 && old_size / 16 >= weak_table->num_entries) {
265 weak_resize(weak_table, old_size / 8);
266 // leaves new table no more than 1/2 full
272 * Remove entry from the zone's table of weak references.
274 static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
277 if (entry->out_of_line) _free_internal(entry->referrers);
278 bzero(entry, sizeof(*entry));
280 weak_table->num_entries--;
282 weak_compact_maybe(weak_table);
287 * Return the weak reference table entry for the given referent.
288 * If there is no entry for referent, return NULL.
292 * @param referent The object. Must not be nil.
294 * @return The table of weak referrers to this object.
296 static weak_entry_t *
297 weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
301 weak_entry_t *weak_entries = weak_table->weak_entries;
303 if (!weak_entries) return nil;
305 size_t index = hash_pointer(referent) & weak_table->mask;
306 size_t hash_displacement = 0;
307 while (weak_table->weak_entries[index].referent != referent) {
308 index = (index+1) & weak_table->mask;
310 if (hash_displacement > weak_table->max_hash_displacement) {
315 return &weak_table->weak_entries[index];
319 * Unregister an already-registered weak reference.
320 * This is used when referrer's storage is about to go away, but referent
321 * isn't dead yet. (Otherwise, zeroing referrer later would be a
322 * bad memory access.)
323 * Does nothing if referent/referrer is not a currently active weak reference.
324 * Does not zero referrer.
326 * FIXME currently requires old referent value to be passed in (lame)
327 * FIXME unregistration should be automatic if referrer is collected
329 * @param weak_table The global weak table.
330 * @param referent The object.
331 * @param referrer The weak reference.
334 weak_unregister_no_lock(weak_table_t *weak_table, id referent_id,
337 objc_object *referent = (objc_object *)referent_id;
338 objc_object **referrer = (objc_object **)referrer_id;
342 if (!referent) return;
344 if ((entry = weak_entry_for_referent(weak_table, referent))) {
345 remove_referrer(entry, referrer);
347 if (entry->out_of_line && entry->num_refs != 0) {
351 for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
352 if (entry->inline_referrers[i]) {
360 weak_entry_remove(weak_table, entry);
364 // Do not set *referrer = nil. objc_storeWeak() requires that the
369 * Registers a new (object, weak pointer) pair. Creates a new weak
370 * object entry if it does not exist.
372 * @param weak_table The global weak table.
373 * @param referent The object pointed to by the weak reference.
374 * @param referrer The weak pointer address.
377 weak_register_no_lock(weak_table_t *weak_table, id referent_id, id *referrer_id)
379 objc_object *referent = (objc_object *)referent_id;
380 objc_object **referrer = (objc_object **)referrer_id;
382 if (!referent || referent->isTaggedPointer()) return referent_id;
384 // ensure that the referenced object is viable
386 if (!referent->ISA()->hasCustomRR()) {
387 deallocating = referent->rootIsDeallocating();
390 BOOL (*allowsWeakReference)(objc_object *, SEL) =
391 (BOOL(*)(objc_object *, SEL))
392 object_getMethodImplementation((id)referent,
393 SEL_allowsWeakReference);
394 if ((IMP)allowsWeakReference == _objc_msgForward) {
398 ! (*allowsWeakReference)(referent, SEL_allowsWeakReference);
402 _objc_fatal("Cannot form weak reference to instance (%p) of "
403 "class %s. It is possible that this object was "
404 "over-released, or is in the process of deallocation.",
405 (void*)referent, object_getClassName((id)referent));
408 // now remember it and where it is being stored
410 if ((entry = weak_entry_for_referent(weak_table, referent))) {
411 append_referrer(entry, referrer);
414 weak_entry_t new_entry;
415 new_entry.referent = referent;
416 new_entry.out_of_line = 0;
417 new_entry.inline_referrers[0] = referrer;
418 for (size_t i = 1; i < WEAK_INLINE_COUNT; i++) {
419 new_entry.inline_referrers[i] = nil;
422 weak_grow_maybe(weak_table);
423 weak_entry_insert(weak_table, &new_entry);
426 // Do not set *referrer. objc_storeWeak() requires that the
435 weak_is_registered_no_lock(weak_table_t *weak_table, id referent_id)
437 return weak_entry_for_referent(weak_table, (objc_object *)referent_id);
443 * Called by dealloc; nils out all weak pointers that point to the
444 * provided object so that they can no longer be used.
447 * @param referent The object being deallocated.
450 weak_clear_no_lock(weak_table_t *weak_table, id referent_id)
452 objc_object *referent = (objc_object *)referent_id;
454 weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
456 /// XXX shouldn't happen, but does with mismatched CF/objc
457 //printf("XXX no entry for clear deallocating %p\n", referent);
461 // zero out references
462 weak_referrer_t *referrers;
465 if (entry->out_of_line) {
466 referrers = entry->referrers;
467 count = TABLE_SIZE(entry);
470 referrers = entry->inline_referrers;
471 count = WEAK_INLINE_COUNT;
474 for (size_t i = 0; i < count; ++i) {
475 objc_object **referrer = referrers[i];
477 if (*referrer == referent) {
480 else if (*referrer) {
481 _objc_inform("__weak variable at %p holds %p instead of %p. "
482 "This is probably incorrect use of "
483 "objc_storeWeak() and objc_loadWeak(). "
484 "Break on objc_weak_error to debug.\n",
485 referrer, (void*)*referrer, (void*)referent);
491 weak_entry_remove(weak_table, entry);
496 * This function gets called when the value of a weak pointer is being
497 * used in an expression. Called by objc_loadWeakRetained() which is
498 * ultimately called by objc_loadWeak(). The objective is to assert that
499 * there is in fact a weak pointer(s) entry for this particular object being
500 * stored in the weak-table, and to retain that object so it is not deallocated
501 * during the weak pointer's usage.
504 * @param referrer The weak pointer address.
507 Once upon a time we eagerly cleared *referrer if we saw the referent
508 was deallocating. This confuses code like NSPointerFunctions which
509 tries to pre-flight the raw storage and assumes if the storage is
510 zero then the weak system is done interfering. That is false: the
511 weak system is still going to check and clear the storage later.
512 This can cause objc_weak_error complaints and crashes.
513 So we now don't touch the storage until deallocation completes.
516 weak_read_no_lock(weak_table_t *weak_table, id *referrer_id)
518 objc_object **referrer = (objc_object **)referrer_id;
519 objc_object *referent = *referrer;
520 if (referent->isTaggedPointer()) return (id)referent;
523 if (referent == nil ||
524 !(entry = weak_entry_for_referent(weak_table, referent)))
529 if (! referent->ISA()->hasCustomRR()) {
530 if (! referent->rootTryRetain()) {
535 BOOL (*tryRetain)(objc_object *, SEL) = (BOOL(*)(objc_object *, SEL))
536 object_getMethodImplementation((id)referent,
537 SEL_retainWeakReference);
538 if ((IMP)tryRetain == _objc_msgForward) {
541 if (! (*tryRetain)(referent, SEL_retainWeakReference)) {