1/* 2 * Copyright (c) 2010-2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 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 11 * file. 12 * 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. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24#include "objc-private.h" 25 26#include "objc-weak.h" 27 28#include <stdint.h> 29#include <stdbool.h> 30#include <sys/types.h> 31#include <libkern/OSAtomic.h> 32 33#define TABLE_SIZE(entry) (entry->mask ? entry->mask + 1 : 0) 34 35static void append_referrer(weak_entry_t *entry, objc_object **new_referrer); 36 37BREAKPOINT_FUNCTION( 38 void objc_weak_error(void) 39); 40 41/** 42 * Unique hash function for object pointers only. 43 * 44 * @param key The object pointer 45 * 46 * @return Size unrestricted hash of pointer. 47 */ 48static inline uintptr_t hash_pointer(objc_object *key) { 49 return ptr_hash((uintptr_t)key); 50} 51 52/** 53 * Unique hash function for weak object pointers only. 54 * 55 * @param key The weak object pointer. 56 * 57 * @return Size unrestricted hash of pointer. 58 */ 59static inline uintptr_t w_hash_pointer(objc_object **key) { 60 return ptr_hash((uintptr_t)key); 61} 62 63/** 64 * Grow the entry's hash table of referrers. Rehashes each 65 * of the referrers. 66 * 67 * @param entry Weak pointer hash set for a particular object. 68 */ 69__attribute__((noinline, used)) 70static void grow_refs_and_insert(weak_entry_t *entry, 71 objc_object **new_referrer) 72{ 73 assert(entry->out_of_line); 74 75 size_t old_size = TABLE_SIZE(entry); 76 size_t new_size = old_size ? old_size * 2 : 8; 77 78 size_t num_refs = entry->num_refs; 79 weak_referrer_t *old_refs = entry->referrers; 80 entry->mask = new_size - 1; 81 82 entry->referrers = (weak_referrer_t *) 83 _calloc_internal(TABLE_SIZE(entry), sizeof(weak_referrer_t)); 84 entry->num_refs = 0; 85 entry->max_hash_displacement = 0; 86 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]); 90 num_refs--; 91 } 92 } 93 // Insert 94 append_referrer(entry, new_referrer); 95 if (old_refs) _free_internal(old_refs); 96} 97 98/** 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). 102 * 103 * @param entry The entry holding the set of weak pointers. 104 * @param new_referrer The new weak pointer to be added. 105 */ 106static void append_referrer(weak_entry_t *entry, objc_object **new_referrer) 107{ 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; 113 return; 114 } 115 } 116 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]; 124 } 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; 130 } 131 132 assert(entry->out_of_line); 133 134 if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { 135 return grow_refs_and_insert(entry, new_referrer); 136 } 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; 141 hash_displacement++; 142 } 143 if (hash_displacement > entry->max_hash_displacement) { 144 entry->max_hash_displacement = hash_displacement; 145 } 146 weak_referrer_t &ref = entry->referrers[index]; 147 ref = new_referrer; 148 entry->num_refs++; 149} 150 151/** 152 * Remove old_referrer from set of referrers, if it's present. 153 * Does not remove duplicates, because duplicates should not exist. 154 * 155 * @todo this is slow if old_referrer is not present. Is this ever the case? 156 * 157 * @param entry The entry holding the referrers. 158 * @param old_referrer The referrer to remove. 159 */ 160static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer) 161{ 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; 166 return; 167 } 168 } 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", 173 old_referrer); 174 objc_weak_error(); 175 return; 176 } 177 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; 182 hash_displacement++; 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", 188 old_referrer); 189 objc_weak_error(); 190 return; 191 } 192 } 193 entry->referrers[index] = nil; 194 entry->num_refs--; 195} 196 197/** 198 * Add new_entry to the object's table of weak references. 199 * Does not check whether the referent is already in the table. 200 */ 201static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry) 202{ 203 weak_entry_t *weak_entries = weak_table->weak_entries; 204 assert(weak_entries != nil); 205 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; 210 hash_displacement++; 211 } 212 213 weak_entries[index] = *new_entry; 214 weak_table->num_entries++; 215 216 if (hash_displacement > weak_table->max_hash_displacement) { 217 weak_table->max_hash_displacement = hash_displacement; 218 } 219} 220 221 222static void weak_resize(weak_table_t *weak_table, size_t new_size) 223{ 224 size_t old_size = TABLE_SIZE(weak_table); 225 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)); 229 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 234 235 if (old_entries) { 236 weak_entry_t *entry; 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); 241 } 242 } 243 _free_internal(old_entries); 244 } 245} 246 247// Grow the given zone's table of weak references if it is full. 248static void weak_grow_maybe(weak_table_t *weak_table) 249{ 250 size_t old_size = TABLE_SIZE(weak_table); 251 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); 255 } 256} 257 258// Shrink the table if it is mostly empty. 259static void weak_compact_maybe(weak_table_t *weak_table) 260{ 261 size_t old_size = TABLE_SIZE(weak_table); 262 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 267 } 268} 269 270 271/** 272 * Remove entry from the zone's table of weak references. 273 */ 274static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry) 275{ 276 // remove entry 277 if (entry->out_of_line) _free_internal(entry->referrers); 278 bzero(entry, sizeof(*entry)); 279 280 weak_table->num_entries--; 281 282 weak_compact_maybe(weak_table); 283} 284 285 286/** 287 * Return the weak reference table entry for the given referent. 288 * If there is no entry for referent, return NULL. 289 * Performs a lookup. 290 * 291 * @param weak_table 292 * @param referent The object. Must not be nil. 293 * 294 * @return The table of weak referrers to this object. 295 */ 296static weak_entry_t * 297weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent) 298{ 299 assert(referent); 300 301 weak_entry_t *weak_entries = weak_table->weak_entries; 302 303 if (!weak_entries) return nil; 304 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; 309 hash_displacement++; 310 if (hash_displacement > weak_table->max_hash_displacement) { 311 return nil; 312 } 313 } 314 315 return &weak_table->weak_entries[index]; 316} 317 318/** 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. 325 * 326 * FIXME currently requires old referent value to be passed in (lame) 327 * FIXME unregistration should be automatic if referrer is collected 328 * 329 * @param weak_table The global weak table. 330 * @param referent The object. 331 * @param referrer The weak reference. 332 */ 333void 334weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 335 id *referrer_id) 336{ 337 objc_object *referent = (objc_object *)referent_id; 338 objc_object **referrer = (objc_object **)referrer_id; 339 340 weak_entry_t *entry; 341 342 if (!referent) return; 343 344 if ((entry = weak_entry_for_referent(weak_table, referent))) { 345 remove_referrer(entry, referrer); 346 bool empty = true; 347 if (entry->out_of_line && entry->num_refs != 0) { 348 empty = false; 349 } 350 else { 351 for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) { 352 if (entry->inline_referrers[i]) { 353 empty = false; 354 break; 355 } 356 } 357 } 358 359 if (empty) { 360 weak_entry_remove(weak_table, entry); 361 } 362 } 363 364 // Do not set *referrer = nil. objc_storeWeak() requires that the 365 // value not change. 366} 367 368/** 369 * Registers a new (object, weak pointer) pair. Creates a new weak 370 * object entry if it does not exist. 371 * 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. 375 */ 376id 377weak_register_no_lock(weak_table_t *weak_table, id referent_id, id *referrer_id) 378{ 379 objc_object *referent = (objc_object *)referent_id; 380 objc_object **referrer = (objc_object **)referrer_id; 381 382 if (!referent || referent->isTaggedPointer()) return referent_id; 383 384 // ensure that the referenced object is viable 385 bool deallocating; 386 if (!referent->ISA()->hasCustomRR()) { 387 deallocating = referent->rootIsDeallocating(); 388 } 389 else { 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) { 395 return nil; 396 } 397 deallocating = 398 ! (*allowsWeakReference)(referent, SEL_allowsWeakReference); 399 } 400 401 if (deallocating) { 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)); 406 } 407 408 // now remember it and where it is being stored 409 weak_entry_t *entry; 410 if ((entry = weak_entry_for_referent(weak_table, referent))) { 411 append_referrer(entry, referrer); 412 } 413 else { 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; 420 } 421 422 weak_grow_maybe(weak_table); 423 weak_entry_insert(weak_table, &new_entry); 424 } 425 426 // Do not set *referrer. objc_storeWeak() requires that the 427 // value not change. 428 429 return referent_id; 430} 431 432 433#if !NDEBUG 434bool 435weak_is_registered_no_lock(weak_table_t *weak_table, id referent_id) 436{ 437 return weak_entry_for_referent(weak_table, (objc_object *)referent_id); 438} 439#endif 440 441 442/** 443 * Called by dealloc; nils out all weak pointers that point to the 444 * provided object so that they can no longer be used. 445 * 446 * @param weak_table 447 * @param referent The object being deallocated. 448 */ 449void 450weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 451{ 452 objc_object *referent = (objc_object *)referent_id; 453 454 weak_entry_t *entry = weak_entry_for_referent(weak_table, referent); 455 if (entry == nil) { 456 /// XXX shouldn't happen, but does with mismatched CF/objc 457 //printf("XXX no entry for clear deallocating %p\n", referent); 458 return; 459 } 460 461 // zero out references 462 weak_referrer_t *referrers; 463 size_t count; 464 465 if (entry->out_of_line) { 466 referrers = entry->referrers; 467 count = TABLE_SIZE(entry); 468 } 469 else { 470 referrers = entry->inline_referrers; 471 count = WEAK_INLINE_COUNT; 472 } 473 474 for (size_t i = 0; i < count; ++i) { 475 objc_object **referrer = referrers[i]; 476 if (referrer) { 477 if (*referrer == referent) { 478 *referrer = nil; 479 } 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); 486 objc_weak_error(); 487 } 488 } 489 } 490 491 weak_entry_remove(weak_table, entry); 492} 493 494 495/** 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. 502 * 503 * @param weak_table 504 * @param referrer The weak pointer address. 505 */ 506/* 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. 514*/ 515id 516weak_read_no_lock(weak_table_t *weak_table, id *referrer_id) 517{ 518 objc_object **referrer = (objc_object **)referrer_id; 519 objc_object *referent = *referrer; 520 if (referent->isTaggedPointer()) return (id)referent; 521 522 weak_entry_t *entry; 523 if (referent == nil || 524 !(entry = weak_entry_for_referent(weak_table, referent))) 525 { 526 return nil; 527 } 528 529 if (! referent->ISA()->hasCustomRR()) { 530 if (! referent->rootTryRetain()) { 531 return nil; 532 } 533 } 534 else { 535 BOOL (*tryRetain)(objc_object *, SEL) = (BOOL(*)(objc_object *, SEL)) 536 object_getMethodImplementation((id)referent, 537 SEL_retainWeakReference); 538 if ((IMP)tryRetain == _objc_msgForward) { 539 return nil; 540 } 541 if (! (*tryRetain)(referent, SEL_retainWeakReference)) { 542 return nil; 543 } 544 } 545 546 return (id)referent; 547} 548 549