/*
* Copyright (c) 2010-2011 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
#import "objc-weak.h"
#import "objc-os.h"
#import "objc-private.h"
#import <stdint.h>
#import <stdbool.h>
#import <sys/types.h>
#import <libkern/OSAtomic.h>
template <typename T> struct WeakAllocator {
typedef T value_type;
typedef value_type* pointer;
typedef const value_type *const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template <typename U> struct rebind { typedef WeakAllocator<U> other; };
template <typename U> WeakAllocator(const WeakAllocator<U>&) {}
WeakAllocator() {}
WeakAllocator(const WeakAllocator&) {}
~WeakAllocator() {}
pointer address(reference x) const { return &x; }
const_pointer address(const_reference x) const {
return x;
}
pointer allocate(size_type n, const_pointer = 0) {
return static_cast<pointer>(::_malloc_internal(n * sizeof(T)));
}
void deallocate(pointer p, size_type) { ::_free_internal(p); }
size_type max_size() const {
return static_cast<size_type>(-1) / sizeof(T);
}
void construct(pointer p, const value_type& x) {
new(p) value_type(x);
}
void destroy(pointer p) { p->~value_type(); }
void operator=(const WeakAllocator&);
};
class Range {
private:
void *_address; // start of range
void *_end; // end of the range (one byte beyond last usable space)
public:
static void *displace(void *address, ptrdiff_t offset) { return (void *)((char *)address + offset); }
//
// Constructors
//
Range() : _address(NULL), _end(NULL) {}
Range(void *address) : _address(address), _end(address) {}
Range(void *address, void *end) : _address(address), _end(end) {}
Range(void *address, size_t size) : _address(address), _end(displace(address, size)) {}
//
// Accessors
//
inline Range& range() { return *this; }
inline void *address() const { return _address; }
inline void *end() const { return _end; }
inline const size_t size() const { return (uintptr_t)_end - (uintptr_t)_address; }
inline void set_address(void *address) { _address = address; }
inline void set_end(void *end) { _end = end; }
inline void set_size(size_t size) { _end = displace(_address, size); }
inline void set_range(void *address, void *end) { _address = address; _end = end; }
inline void set_range(void *address, size_t size) { _address = address; _end = displace(address, size); }
inline void set_range(Range range) { _address = range.address(); _end = range.end(); }
inline void adjust_address(intptr_t delta) { _address = displace(_address, delta); }
inline void adjust_end(intptr_t delta) { _end = displace(_end, delta); }
inline void adjust(intptr_t delta) { _address = displace(_address, delta), _end = displace(_end, delta); }
//
// is_empty
//
// Returns true if the range is empty.
//
inline bool is_empty() { return _address == _end; }
//
// in_range
//
// Returns true if the specified address is in range.
// This form reduces the number of branches. Works well with invariant lo and hi.
//
static inline const bool in_range(void *lo, void *hi, void *address) {
uintptr_t lo_as_int = (uintptr_t)lo;
uintptr_t hi_as_int = (uintptr_t)hi;
uintptr_t diff = hi_as_int - lo_as_int;
uintptr_t address_as_int = (uintptr_t)address;
return (address_as_int - lo_as_int) < diff;
}
inline const bool in_range(void *address) const { return in_range(_address, _end, address); }
//
// operator ==
//
// Used to locate entry in list or hash table (use is_range for exaxt match.)
inline const bool operator==(const Range *range) const { return _address == range->_address; }
inline const bool operator==(const Range &range) const { return _address == range._address; }
//
// is_range
//
// Return true if the ranges are equivalent.
//
inline const bool is_range(const Range& range) const { return _address == range._address && _end == range._end; }
//
// clear
//
// Initialize the range to zero.
//
inline void clear() { bzero(address(), size()); }
//
// expand_range
//
// Expand the bounds with the specified range.
//
inline void expand_range(void *address) {
if (_address > address) _address = address;
if (_end < address) _end = address;
}
inline void expand_range(Range& range) {
expand_range(range.address());
expand_range(range.end());
}
//
// relative_address
//
// Converts an absolute address to an address relative to this address.
//
inline void *relative_address(void *address) const { return (void *)((uintptr_t)address - (uintptr_t)_address); }
//
// absolute_address
//
// Converts an address relative to this address to an absolute address.
//
inline void *absolute_address(void *address) const { return (void *)((uintptr_t)address + (uintptr_t)_address); }
};
template<> struct WeakAllocator<void> {
typedef void value_type;
typedef void* pointer;
typedef const void *const_pointer;
template <typename U> struct rebind { typedef WeakAllocator<U> other; };
};
typedef std::pair<id, id *> WeakPair;
typedef std::vector<WeakPair, WeakAllocator<WeakPair> > WeakPairVector;
typedef std::vector<weak_referrer_t, WeakAllocator<WeakPair> > WeakReferrerVector;
static void append_referrer_no_lock(weak_referrer_array_t *list, id *new_referrer);
static inline uintptr_t hash_pointer(void *key) {
uintptr_t k = (uintptr_t)key;
// Code from CFSet.c
#if __LP64__
uintptr_t a = 0x4368726973746F70ULL;
uintptr_t b = 0x686572204B616E65ULL;
#else
uintptr_t a = 0x4B616E65UL;
uintptr_t b = 0x4B616E65UL;
#endif
uintptr_t c = 1;
a += k;
#if __LP64__
a -= b; a -= c; a ^= (c >> 43);
b -= c; b -= a; b ^= (a << 9);
c -= a; c -= b; c ^= (b >> 8);
a -= b; a -= c; a ^= (c >> 38);
b -= c; b -= a; b ^= (a << 23);
c -= a; c -= b; c ^= (b >> 5);
a -= b; a -= c; a ^= (c >> 35);
b -= c; b -= a; b ^= (a << 49);
c -= a; c -= b; c ^= (b >> 11);
a -= b; a -= c; a ^= (c >> 12);
b -= c; b -= a; b ^= (a << 18);
c -= a; c -= b; c ^= (b >> 22);
#else
a -= b; a -= c; a ^= (c >> 13);
b -= c; b -= a; b ^= (a << 8);
c -= a; c -= b; c ^= (b >> 13);
a -= b; a -= c; a ^= (c >> 12);
b -= c; b -= a; b ^= (a << 16);
c -= a; c -= b; c ^= (b >> 5);
a -= b; a -= c; a ^= (c >> 3);
b -= c; b -= a; b ^= (a << 10);
c -= a; c -= b; c ^= (b >> 15);
#endif
return c;
}
// Up until this size the weak referrer array grows one slot at a time. Above this size it grows by doubling.
#define WEAK_TABLE_DOUBLE_SIZE 8
// Grow the refs list. Rehashes the entries.
static void grow_refs(weak_referrer_array_t *list)
{
size_t old_num_allocated = list->num_allocated;
size_t num_refs = list->num_refs;
weak_referrer_t *old_refs = list->refs;
size_t new_allocated = old_num_allocated < WEAK_TABLE_DOUBLE_SIZE ? old_num_allocated + 1 : old_num_allocated + old_num_allocated;
list->refs = (weak_referrer_t *)_malloc_internal(new_allocated * sizeof(weak_referrer_t));
list->num_allocated = _malloc_size_internal(list->refs)/sizeof(weak_referrer_t);
bzero(list->refs, list->num_allocated * sizeof(weak_referrer_t));
// for larger tables drop one entry from the end to give an odd number of hash buckets for better hashing
if ((list->num_allocated > WEAK_TABLE_DOUBLE_SIZE) && !(list->num_allocated & 1)) list->num_allocated--;
list->num_refs = 0;
list->max_hash_displacement = 0;
size_t i;
for (i=0; i < old_num_allocated && num_refs > 0; i++) {
if (old_refs[i].referrer != NULL) {
append_referrer_no_lock(list, old_refs[i].referrer);
num_refs--;
}
}
if (old_refs)
_free_internal(old_refs);
}
// Add the given referrer to list
// Does not perform duplicate checking.
static void append_referrer_no_lock(weak_referrer_array_t *list, id *new_referrer)
{
if ((list->num_refs == list->num_allocated) || ((list->num_refs >= WEAK_TABLE_DOUBLE_SIZE) && (list->num_refs >= list->num_allocated * 2 / 3))) {
grow_refs(list);
}
size_t index = hash_pointer(new_referrer) % list->num_allocated, hash_displacement = 0;
while (list->refs[index].referrer != NULL) {
index++;
hash_displacement++;
if (index == list->num_allocated)
index = 0;
}
if (list->max_hash_displacement < hash_displacement) {
list->max_hash_displacement = hash_displacement;
//malloc_printf("max_hash_displacement: %d allocated: %d\n", list->max_hash_displacement, list->num_allocated);
}
weak_referrer_t &ref = list->refs[index];
ref.referrer = new_referrer;
list->num_refs++;
}
// Remove old_referrer from list, if it's present.
// Does not remove duplicates.
// fixme this is slow if old_referrer is not present.
static void remove_referrer_no_lock(weak_referrer_array_t *list, id *old_referrer)
{
size_t index = hash_pointer(old_referrer) % list->num_allocated;
size_t start_index = index, hash_displacement = 0;
while (list->refs[index].referrer != old_referrer) {
index++;
hash_displacement++;
if (index == list->num_allocated)
index = 0;
if (index == start_index || hash_displacement > list->max_hash_displacement) {
malloc_printf("attempted to remove unregistered weak referrer %p\n", old_referrer);
return;
}
}
list->refs[index].referrer = NULL;
list->num_refs--;
}
// Add new_entry to the zone's table of weak references.
// Does not check whether the referent is already in the table.
// Does not update num_weak_refs.
static void weak_entry_insert_no_lock(weak_table_t *weak_table, weak_entry_t *new_entry)
{
weak_entry_t *weak_entries = weak_table->weak_entries;
assert(weak_entries != NULL);
size_t table_size = weak_table->max_weak_refs;
size_t hash_index = hash_pointer(new_entry->referent) % table_size;
size_t index = hash_index;
do {
weak_entry_t *entry = weak_entries + index;
if (entry->referent == NULL) {
*entry = *new_entry;
return;
}
index++; if (index == table_size) index = 0;
} while (index != hash_index);
malloc_printf("no room for new entry in auto weak ref table!\n");
}
// Remove entry from the zone's table of weak references, and rehash
// Does not update num_weak_refs.
static void weak_entry_remove_no_lock(weak_table_t *weak_table, weak_entry_t *entry)
{
// remove entry
entry->referent = NULL;
if (entry->referrers.refs) _free_internal(entry->referrers.refs);
entry->referrers.refs = NULL;
entry->referrers.num_refs = 0;
entry->referrers.num_allocated = 0;
// rehash after entry
weak_entry_t *weak_entries = weak_table->weak_entries;
size_t table_size = weak_table->max_weak_refs;
size_t hash_index = entry - weak_entries;
size_t index = hash_index;
if (!weak_entries) return;
do {
index++; if (index == table_size) index = 0;
if (!weak_entries[index].referent) return;
weak_entry_t entry = weak_entries[index];
weak_entries[index].referent = NULL;
weak_entry_insert_no_lock(weak_table, &entry);
} while (index != hash_index);
}
// Grow the given zone's table of weak references if it is full.
static void weak_grow_maybe_no_lock(weak_table_t *weak_table)
{
if (weak_table->num_weak_refs >= weak_table->max_weak_refs * 3 / 4) {
// grow table
size_t old_max = weak_table->max_weak_refs;
size_t new_max = old_max ? old_max * 2 + 1 : 15;
weak_entry_t *old_entries = weak_table->weak_entries;
weak_entry_t *new_entries = (weak_entry_t *)_calloc_internal(new_max, sizeof(weak_entry_t));
weak_table->max_weak_refs = new_max;
weak_table->weak_entries = new_entries;
if (old_entries) {
weak_entry_t *entry;
weak_entry_t *end = old_entries + old_max;
for (entry = old_entries; entry < end; entry++) {
weak_entry_insert_no_lock(weak_table, entry);
}
_free_internal(old_entries);
}
}
}
// Return the weak reference table entry for the given referent.
// If there is no entry for referent, return NULL.
static weak_entry_t *weak_entry_for_referent(weak_table_t *weak_table, id referent)
{
weak_entry_t *weak_entries = weak_table->weak_entries;
if (!weak_entries) return NULL;
size_t table_size = weak_table->max_weak_refs;
size_t hash_index = hash_pointer(referent) % table_size;
size_t index = hash_index;
do {
weak_entry_t *entry = weak_entries + index;
if (entry->referent == referent) return entry;
if (entry->referent == NULL) return NULL;
index++; if (index == table_size) index = 0;
} while (index != hash_index);
return NULL;
}
// Unregister an already-registered weak reference.
// This is used when referrer's storage is about to go away, but referent
// isn't dead yet. (Otherwise, zeroing referrer later would be a
// bad memory access.)
// Does nothing if referent/referrer is not a currently active weak reference.
// Does not zero referrer.
// fixme currently requires old referent value to be passed in (lame)
// fixme unregistration should be automatic if referrer is collected
PRIVATE_EXTERN void weak_unregister_no_lock(weak_table_t *weak_table, id referent, id *referrer)
{
weak_entry_t *entry;
if ((entry = weak_entry_for_referent(weak_table, referent))) {
remove_referrer_no_lock(&entry->referrers, referrer);
if (entry->referrers.num_refs == 0) {
weak_entry_remove_no_lock(weak_table, entry);
weak_table->num_weak_refs--;
}
}
// Do not set *referrer = NULL. objc_storeWeak() requires that the
// value not change.
}
PRIVATE_EXTERN void
arr_clear_deallocating(weak_table_t *weak_table, id referent) {
{
weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
if (entry == NULL) {
/// XXX shouldn't happen, but does with mismatched CF/objc
//printf("XXX no entry for clear deallocating %p\n", referent);
return;
}
// zero out references
for (int i = 0; i < entry->referrers.num_allocated; ++i) {
id *referrer = entry->referrers.refs[i].referrer;
if (referrer) {
if (*referrer == referent) {
*referrer = nil;
}
else if (*referrer) {
_objc_inform("__weak variable @ %p holds %p instead of %p\n", referrer, *referrer, referent);
}
}
}
weak_entry_remove_no_lock(weak_table, entry);
weak_table->num_weak_refs--;
}
}
PRIVATE_EXTERN id weak_register_no_lock(weak_table_t *weak_table, id referent, id *referrer) {
if (referent) {
// ensure that the referenced object is viable
BOOL (*allowsWeakReference)(id, SEL) = (BOOL(*)(id, SEL))
class_getMethodImplementation(object_getClass(referent),
@selector(allowsWeakReference));
if ((IMP)allowsWeakReference != _objc_msgForward) {
if (! (*allowsWeakReference)(referent, @selector(allowsWeakReference))) {
_objc_fatal("cannot form weak reference to instance (%p) of class %s", referent, object_getClassName(referent));
}
}
else {
return NULL;
}
// now remember it and where it is being stored
weak_entry_t *entry;
if ((entry = weak_entry_for_referent(weak_table, referent))) {
append_referrer_no_lock(&entry->referrers, referrer);
}
else {
weak_entry_t new_entry;
new_entry.referent = referent;
new_entry.referrers.refs = NULL;
new_entry.referrers.num_refs = 0;
new_entry.referrers.num_allocated = 0;
append_referrer_no_lock(&new_entry.referrers, referrer);
weak_table->num_weak_refs++;
weak_grow_maybe_no_lock(weak_table);
weak_entry_insert_no_lock(weak_table, &new_entry);
}
}
// Do not set *referrer. objc_storeWeak() requires that the
// value not change.
return referent;
}
// Automated Retain Release (ARR) support
PRIVATE_EXTERN id
arr_read_weak_reference(weak_table_t *weak_table, id *referrer) {
id referent;
// find entry and mark that it needs retaining
{
referent = *referrer;
weak_entry_t *entry;
if (referent == NULL || !(entry = weak_entry_for_referent(weak_table, referent))) {
*referrer = NULL;
return NULL;
}
BOOL (*tryRetain)(id, SEL) = (BOOL(*)(id, SEL))
class_getMethodImplementation(object_getClass(referent),
@selector(retainWeakReference));
if ((IMP)tryRetain != _objc_msgForward) {
//printf("sending _tryRetain for %p\n", referent);
if (! (*tryRetain)(referent, @selector(retainWeakReference))) {
//printf("_tryRetain(%p) tried and failed!\n", referent);
return NULL;
}
//else printf("_tryRetain(%p) succeeded\n", referent);
}
else {
*referrer = NULL;
return NULL;
}
}
return referent;
}