objc-weak.mm 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505
  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. #include "objc-private.h"
  24. #include "objc-weak.h"
  25. #include <stdint.h>
  26. #include <stdbool.h>
  27. #include <sys/types.h>
  28. #include <libkern/OSAtomic.h>
  29. #define TABLE_SIZE(entry) (entry->mask ? entry->mask + 1 : 0)
  30. static void append_referrer(weak_entry_t *entry, objc_object **new_referrer);
  31. BREAKPOINT_FUNCTION(
  32. void objc_weak_error(void)
  33. );
  34. static void bad_weak_table(weak_entry_t *entries)
  35. {
  36. _objc_fatal("bad weak table at %p. This may be a runtime bug or a "
  37. "memory error somewhere else.", entries);
  38. }
  39. /**
  40. * Unique hash function for object pointers only.
  41. *
  42. * @param key The object pointer
  43. *
  44. * @return Size unrestricted hash of pointer.
  45. */
  46. static inline uintptr_t hash_pointer(objc_object *key) {
  47. return ptr_hash((uintptr_t)key);
  48. }
  49. /**
  50. * Unique hash function for weak object pointers only.
  51. *
  52. * @param key The weak object pointer.
  53. *
  54. * @return Size unrestricted hash of pointer.
  55. */
  56. static inline uintptr_t w_hash_pointer(objc_object **key) {
  57. return ptr_hash((uintptr_t)key);
  58. }
  59. /**
  60. * Grow the entry's hash table of referrers. Rehashes each
  61. * of the referrers.
  62. *
  63. * @param entry Weak pointer hash set for a particular object.
  64. */
  65. __attribute__((noinline, used))
  66. static void grow_refs_and_insert(weak_entry_t *entry,
  67. objc_object **new_referrer)
  68. {
  69. ASSERT(entry->out_of_line());
  70. size_t old_size = TABLE_SIZE(entry);
  71. size_t new_size = old_size ? old_size * 2 : 8;
  72. size_t num_refs = entry->num_refs;
  73. weak_referrer_t *old_refs = entry->referrers;
  74. entry->mask = new_size - 1;
  75. entry->referrers = (weak_referrer_t *)
  76. calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));
  77. entry->num_refs = 0;
  78. entry->max_hash_displacement = 0;
  79. for (size_t i = 0; i < old_size && num_refs > 0; i++) {
  80. if (old_refs[i] != nil) {
  81. append_referrer(entry, old_refs[i]);
  82. num_refs--;
  83. }
  84. }
  85. // Insert
  86. append_referrer(entry, new_referrer);
  87. if (old_refs) free(old_refs);
  88. }
  89. /**
  90. * Add the given referrer to set of weak pointers in this entry.
  91. * Does not perform duplicate checking (b/c weak pointers are never
  92. * added to a set twice).
  93. *
  94. * @param entry The entry holding the set of weak pointers.
  95. * @param new_referrer The new weak pointer to be added.
  96. */
  97. static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
  98. {
  99. if (! entry->out_of_line()) {
  100. // Try to insert inline.
  101. for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
  102. if (entry->inline_referrers[i] == nil) {
  103. entry->inline_referrers[i] = new_referrer;
  104. return;
  105. }
  106. }
  107. // Couldn't insert inline. Allocate out of line.
  108. weak_referrer_t *new_referrers = (weak_referrer_t *)
  109. calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
  110. // This constructed table is invalid, but grow_refs_and_insert
  111. // will fix it and rehash it.
  112. for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
  113. new_referrers[i] = entry->inline_referrers[i];
  114. }
  115. entry->referrers = new_referrers;
  116. entry->num_refs = WEAK_INLINE_COUNT;
  117. entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
  118. entry->mask = WEAK_INLINE_COUNT-1;
  119. entry->max_hash_displacement = 0;
  120. }
  121. ASSERT(entry->out_of_line());
  122. if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
  123. return grow_refs_and_insert(entry, new_referrer);
  124. }
  125. size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
  126. size_t index = begin;
  127. size_t hash_displacement = 0;
  128. while (entry->referrers[index] != nil) {
  129. hash_displacement++;
  130. index = (index+1) & entry->mask;
  131. if (index == begin) bad_weak_table(entry);
  132. }
  133. if (hash_displacement > entry->max_hash_displacement) {
  134. entry->max_hash_displacement = hash_displacement;
  135. }
  136. weak_referrer_t &ref = entry->referrers[index];
  137. ref = new_referrer;
  138. entry->num_refs++;
  139. }
  140. /**
  141. * Remove old_referrer from set of referrers, if it's present.
  142. * Does not remove duplicates, because duplicates should not exist.
  143. *
  144. * @todo this is slow if old_referrer is not present. Is this ever the case?
  145. *
  146. * @param entry The entry holding the referrers.
  147. * @param old_referrer The referrer to remove.
  148. */
  149. static void remove_referrer(weak_entry_t *entry, objc_object **old_referrer)
  150. {
  151. if (! entry->out_of_line()) {
  152. for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
  153. if (entry->inline_referrers[i] == old_referrer) {
  154. entry->inline_referrers[i] = nil;
  155. return;
  156. }
  157. }
  158. _objc_inform("Attempted to unregister unknown __weak variable "
  159. "at %p. This is probably incorrect use of "
  160. "objc_storeWeak() and objc_loadWeak(). "
  161. "Break on objc_weak_error to debug.\n",
  162. old_referrer);
  163. objc_weak_error();
  164. return;
  165. }
  166. size_t begin = w_hash_pointer(old_referrer) & (entry->mask);
  167. size_t index = begin;
  168. size_t hash_displacement = 0;
  169. while (entry->referrers[index] != old_referrer) {
  170. index = (index+1) & entry->mask;
  171. if (index == begin) bad_weak_table(entry);
  172. hash_displacement++;
  173. if (hash_displacement > entry->max_hash_displacement) {
  174. _objc_inform("Attempted to unregister unknown __weak variable "
  175. "at %p. This is probably incorrect use of "
  176. "objc_storeWeak() and objc_loadWeak(). "
  177. "Break on objc_weak_error to debug.\n",
  178. old_referrer);
  179. objc_weak_error();
  180. return;
  181. }
  182. }
  183. entry->referrers[index] = nil;
  184. entry->num_refs--;
  185. }
  186. /**
  187. * Add new_entry to the object's table of weak references.
  188. * Does not check whether the referent is already in the table.
  189. */
  190. static void weak_entry_insert(weak_table_t *weak_table, weak_entry_t *new_entry)
  191. {
  192. weak_entry_t *weak_entries = weak_table->weak_entries;
  193. ASSERT(weak_entries != nil);
  194. size_t begin = hash_pointer(new_entry->referent) & (weak_table->mask);
  195. size_t index = begin;
  196. size_t hash_displacement = 0;
  197. while (weak_entries[index].referent != nil) {
  198. index = (index+1) & weak_table->mask;
  199. if (index == begin) bad_weak_table(weak_entries);
  200. hash_displacement++;
  201. }
  202. weak_entries[index] = *new_entry;
  203. weak_table->num_entries++;
  204. if (hash_displacement > weak_table->max_hash_displacement) {
  205. weak_table->max_hash_displacement = hash_displacement;
  206. }
  207. }
  208. static void weak_resize(weak_table_t *weak_table, size_t new_size)
  209. {
  210. size_t old_size = TABLE_SIZE(weak_table);
  211. weak_entry_t *old_entries = weak_table->weak_entries;
  212. weak_entry_t *new_entries = (weak_entry_t *)
  213. calloc(new_size, sizeof(weak_entry_t));
  214. weak_table->mask = new_size - 1;
  215. weak_table->weak_entries = new_entries;
  216. weak_table->max_hash_displacement = 0;
  217. weak_table->num_entries = 0; // restored by weak_entry_insert below
  218. if (old_entries) {
  219. weak_entry_t *entry;
  220. weak_entry_t *end = old_entries + old_size;
  221. for (entry = old_entries; entry < end; entry++) {
  222. if (entry->referent) {
  223. weak_entry_insert(weak_table, entry);
  224. }
  225. }
  226. free(old_entries);
  227. }
  228. }
  229. // Grow the given zone's table of weak references if it is full.
  230. static void weak_grow_maybe(weak_table_t *weak_table)
  231. {
  232. size_t old_size = TABLE_SIZE(weak_table);
  233. // Grow if at least 3/4 full.
  234. if (weak_table->num_entries >= old_size * 3 / 4) {
  235. weak_resize(weak_table, old_size ? old_size*2 : 64);
  236. }
  237. }
  238. // Shrink the table if it is mostly empty.
  239. static void weak_compact_maybe(weak_table_t *weak_table)
  240. {
  241. size_t old_size = TABLE_SIZE(weak_table);
  242. // Shrink if larger than 1024 buckets and at most 1/16 full.
  243. if (old_size >= 1024 && old_size / 16 >= weak_table->num_entries) {
  244. weak_resize(weak_table, old_size / 8);
  245. // leaves new table no more than 1/2 full
  246. }
  247. }
  248. /**
  249. * Remove entry from the zone's table of weak references.
  250. */
  251. static void weak_entry_remove(weak_table_t *weak_table, weak_entry_t *entry)
  252. {
  253. // remove entry
  254. if (entry->out_of_line()) free(entry->referrers);
  255. bzero(entry, sizeof(*entry));
  256. weak_table->num_entries--;
  257. weak_compact_maybe(weak_table);
  258. }
  259. /**
  260. * Return the weak reference table entry for the given referent.
  261. * If there is no entry for referent, return NULL.
  262. * Performs a lookup.
  263. *
  264. * @param weak_table
  265. * @param referent The object. Must not be nil.
  266. *
  267. * @return The table of weak referrers to this object.
  268. */
  269. static weak_entry_t *
  270. weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
  271. {
  272. ASSERT(referent);
  273. weak_entry_t *weak_entries = weak_table->weak_entries;
  274. if (!weak_entries) return nil;
  275. size_t begin = hash_pointer(referent) & weak_table->mask;
  276. size_t index = begin;
  277. size_t hash_displacement = 0;
  278. while (weak_table->weak_entries[index].referent != referent) {
  279. index = (index+1) & weak_table->mask;
  280. if (index == begin) bad_weak_table(weak_table->weak_entries);
  281. hash_displacement++;
  282. if (hash_displacement > weak_table->max_hash_displacement) {
  283. return nil;
  284. }
  285. }
  286. return &weak_table->weak_entries[index];
  287. }
  288. /**
  289. * Unregister an already-registered weak reference.
  290. * This is used when referrer's storage is about to go away, but referent
  291. * isn't dead yet. (Otherwise, zeroing referrer later would be a
  292. * bad memory access.)
  293. * Does nothing if referent/referrer is not a currently active weak reference.
  294. * Does not zero referrer.
  295. *
  296. * FIXME currently requires old referent value to be passed in (lame)
  297. * FIXME unregistration should be automatic if referrer is collected
  298. *
  299. * @param weak_table The global weak table.
  300. * @param referent The object.
  301. * @param referrer The weak reference.
  302. */
  303. void
  304. weak_unregister_no_lock(weak_table_t *weak_table, id referent_id,
  305. id *referrer_id)
  306. {
  307. objc_object *referent = (objc_object *)referent_id;
  308. objc_object **referrer = (objc_object **)referrer_id;
  309. weak_entry_t *entry;
  310. if (!referent) return;
  311. if ((entry = weak_entry_for_referent(weak_table, referent))) {
  312. remove_referrer(entry, referrer);
  313. bool empty = true;
  314. if (entry->out_of_line() && entry->num_refs != 0) {
  315. empty = false;
  316. }
  317. else {
  318. for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
  319. if (entry->inline_referrers[i]) {
  320. empty = false;
  321. break;
  322. }
  323. }
  324. }
  325. if (empty) {
  326. weak_entry_remove(weak_table, entry);
  327. }
  328. }
  329. // Do not set *referrer = nil. objc_storeWeak() requires that the
  330. // value not change.
  331. }
  332. /**
  333. * Registers a new (object, weak pointer) pair. Creates a new weak
  334. * object entry if it does not exist.
  335. *
  336. * @param weak_table The global weak table.
  337. * @param referent The object pointed to by the weak reference.
  338. * @param referrer The weak pointer address.
  339. */
  340. id
  341. weak_register_no_lock(weak_table_t *weak_table, id referent_id,
  342. id *referrer_id, bool crashIfDeallocating)
  343. {
  344. objc_object *referent = (objc_object *)referent_id;
  345. objc_object **referrer = (objc_object **)referrer_id;
  346. if (!referent || referent->isTaggedPointer()) return referent_id;
  347. // ensure that the referenced object is viable
  348. bool deallocating;
  349. if (!referent->ISA()->hasCustomRR()) {
  350. deallocating = referent->rootIsDeallocating();
  351. }
  352. else {
  353. BOOL (*allowsWeakReference)(objc_object *, SEL) =
  354. (BOOL(*)(objc_object *, SEL))
  355. object_getMethodImplementation((id)referent,
  356. @selector(allowsWeakReference));
  357. if ((IMP)allowsWeakReference == _objc_msgForward) {
  358. return nil;
  359. }
  360. deallocating =
  361. ! (*allowsWeakReference)(referent, @selector(allowsWeakReference));
  362. }
  363. if (deallocating) {
  364. if (crashIfDeallocating) {
  365. _objc_fatal("Cannot form weak reference to instance (%p) of "
  366. "class %s. It is possible that this object was "
  367. "over-released, or is in the process of deallocation.",
  368. (void*)referent, object_getClassName((id)referent));
  369. } else {
  370. return nil;
  371. }
  372. }
  373. // now remember it and where it is being stored
  374. weak_entry_t *entry;
  375. if ((entry = weak_entry_for_referent(weak_table, referent))) {
  376. append_referrer(entry, referrer);
  377. }
  378. else {
  379. weak_entry_t new_entry(referent, referrer);
  380. weak_grow_maybe(weak_table);
  381. weak_entry_insert(weak_table, &new_entry);
  382. }
  383. // Do not set *referrer. objc_storeWeak() requires that the
  384. // value not change.
  385. return referent_id;
  386. }
  387. #if DEBUG
  388. bool
  389. weak_is_registered_no_lock(weak_table_t *weak_table, id referent_id)
  390. {
  391. return weak_entry_for_referent(weak_table, (objc_object *)referent_id);
  392. }
  393. #endif
  394. /**
  395. * Called by dealloc; nils out all weak pointers that point to the
  396. * provided object so that they can no longer be used.
  397. *
  398. * @param weak_table
  399. * @param referent The object being deallocated.
  400. */
  401. void
  402. weak_clear_no_lock(weak_table_t *weak_table, id referent_id)
  403. {
  404. objc_object *referent = (objc_object *)referent_id;
  405. weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
  406. if (entry == nil) {
  407. /// XXX shouldn't happen, but does with mismatched CF/objc
  408. //printf("XXX no entry for clear deallocating %p\n", referent);
  409. return;
  410. }
  411. // zero out references
  412. weak_referrer_t *referrers;
  413. size_t count;
  414. if (entry->out_of_line()) {
  415. referrers = entry->referrers;
  416. count = TABLE_SIZE(entry);
  417. }
  418. else {
  419. referrers = entry->inline_referrers;
  420. count = WEAK_INLINE_COUNT;
  421. }
  422. for (size_t i = 0; i < count; ++i) {
  423. objc_object **referrer = referrers[i];
  424. if (referrer) {
  425. if (*referrer == referent) {
  426. *referrer = nil;
  427. }
  428. else if (*referrer) {
  429. _objc_inform("__weak variable at %p holds %p instead of %p. "
  430. "This is probably incorrect use of "
  431. "objc_storeWeak() and objc_loadWeak(). "
  432. "Break on objc_weak_error to debug.\n",
  433. referrer, (void*)*referrer, (void*)referent);
  434. objc_weak_error();
  435. }
  436. }
  437. }
  438. weak_entry_remove(weak_table, entry);
  439. }