AutoReferenceIterator.h [plain text]
#pragma once
#ifndef __AUTO_REFERENCE_ITERATOR__
#define __AUTO_REFERENCE_ITERATOR__
#include "AutoAdmin.h"
#include "AutoDefs.h"
#include "AutoLarge.h"
#include "AutoRegion.h"
#include "AutoZone.h"
#include "AutoBlockIterator.h"
namespace Auto {
enum ReferenceKind {
kRootReference = 0,
kRetainedReference,
kThreadLocalReference,
kRegistersReference,
kStackReference,
kConservativeHeapReference,
kExactHeapReference,
kAssociativeReference
};
class ReferenceInfo {
ReferenceKind _kind;
union {
WriteBarrier *_wb; Thread *_thread; void *_key; };
public:
ReferenceInfo(ReferenceKind kind) : _kind(kind), _wb(NULL) {}
ReferenceInfo(ReferenceKind kind, WriteBarrier *wb) : _kind(kind), _wb(wb) {}
ReferenceInfo(ReferenceKind kind, Thread *thread) : _kind(kind), _thread(thread) {}
ReferenceInfo(void *key) : _kind(kAssociativeReference), _key(key) {}
ReferenceKind kind() { return _kind; }
WriteBarrier &wb() { return *_wb; }
Thread &thread() { return *_thread; }
void *key() { return _key; }
};
template <class Configuration> class ReferenceIterator {
private:
typedef typename Configuration::ReferenceVisitor ReferenceVisitor;
typedef typename Configuration::PendingStack PendingStack;
Zone *_zone; ReferenceVisitor &_visitor; PendingStack &_pending_stack; usword_t _bytes_scanned; usword_t _blocks_scanned; void *_stack_bottom;
public:
template <typename U> struct rebind { typedef ReferenceIterator<U> other; };
ReferenceIterator(Zone *zone, ReferenceVisitor &visitor, PendingStack &stack, void *stack_bottom = (void *)auto_get_sp())
: _zone(zone), _visitor(visitor), _pending_stack(stack), _bytes_scanned(0), _blocks_scanned(0), _stack_bottom(stack_bottom)
{
}
inline void scan_reference(ReferenceInfo &info, void **reference) {
void *pointer = *reference;
if (pointer == NULL) return;
if (_zone->in_subzone_memory(pointer)) {
Subzone *subzone = Subzone::subzone(pointer);
usword_t q = subzone->quantum_index_unchecked(pointer);
if (subzone->block_is_start(q)) {
_visitor.visit(info, reference, subzone, q);
if (!subzone->test_set_mark(q) && Configuration::ScanningStrategy::should_scan(subzone, q)) {
_pending_stack.push(subzone, q);
}
}
} else if (_zone->in_large_memory(pointer) && Large::is_start(pointer)) {
Large *large = Large::large(pointer);
_visitor.visit(info, reference, large);
if (!large->test_set_mark() && Configuration::ScanningStrategy::should_scan(large)) {
_pending_stack.push(large);
}
}
}
inline void scan_range(ReferenceInfo &info, Range &range) {
void **slots = (void **)range.address();
void **last = (void **)displace(slots, range.size() - sizeof(void*));
while (slots <= last)
scan_reference(info, slots++);
}
static void scan_thread_range(Thread *thread, Range &range, void *arg) {
ReferenceIterator *scanner = (ReferenceIterator*)arg;
ReferenceKind kind = (range.end() == thread->stack_base() ? kStackReference : kRegistersReference);
ReferenceInfo info(kind, thread);
scanner->scan_range(info, range);
}
static void scan_exact_range(Range &range, WriteBarrier *wb, void *arg) {
ReferenceIterator *scanner = (ReferenceIterator*)arg;
ReferenceInfo info(kExactHeapReference, wb);
scanner->scan_range(info, range);
}
static void scan_conservative_range(Range &range, WriteBarrier *wb, void *arg) {
ReferenceIterator *scanner = (ReferenceIterator*)arg;
ReferenceInfo info(kConservativeHeapReference, wb);
scanner->scan_range(info, range);
}
inline void scan(Subzone *subzone, usword_t q) {
void *block = subzone->quantum_address(q);
usword_t size = subzone->size(q);
usword_t layout = subzone->layout(q);
WriteBarrier *wb = &subzone->write_barrier();
if (layout & AUTO_OBJECT) {
Configuration::ScanningStrategy::scan_object(*this, block, size, _zone->layout_map_for_block(block), wb);
} else {
Configuration::ScanningStrategy::scan_block(*this, block, size, wb);
}
}
inline void scan(Large *large) {
void *block = large->address();
usword_t size = large->size();
usword_t layout = large->layout();
WriteBarrier *wb = &large->write_barrier();
if (layout & AUTO_OBJECT) {
Configuration::ScanningStrategy::scan_object(*this, block, size, _zone->layout_map_for_block(block), wb);
} else {
Configuration::ScanningStrategy::scan_block(*this, block, size, wb);
}
}
class retained_or_local_blocks_visitor {
ReferenceIterator &_scanner;
ReferenceVisitor &_visitor;
public:
retained_or_local_blocks_visitor(ReferenceIterator &scanner) : _scanner(scanner), _visitor(scanner._visitor) {}
inline bool visit(Zone *zone, Subzone *subzone, usword_t q) {
bool has_refcount = subzone->has_refcount(q);
if ((has_refcount || subzone->is_thread_local(q))) {
ReferenceInfo info(has_refcount ? kRetainedReference : kThreadLocalReference);
_visitor.visit(info, NULL, subzone, q);
if (!subzone->test_set_mark(q) && Configuration::ScanningStrategy::should_scan(subzone, q)) {
_scanner.scan(subzone, q);
}
}
return true;
}
inline bool visit(Zone *zone, Large *large) {
if (large->refcount()) {
ReferenceInfo info(kRetainedReference);
_scanner._visitor.visit(info, NULL, large);
if (!large->test_set_mark() && Configuration::ScanningStrategy::should_scan(large)) {
_scanner.scan(large);
}
}
return true;
}
};
inline void scan_roots() {
retained_or_local_blocks_visitor visitor(*this);
visitAllocatedBlocks(_zone, visitor);
_pending_stack.scan(*this);
PtrVector roots;
_zone->copy_roots(roots);
ReferenceInfo info(kRootReference);
for (usword_t i = 0, count = roots.size(); i < count; i++) {
scan_reference(info, (void**)roots[i]);
_pending_stack.scan(*this);
}
}
static void scan_one_thread(Thread *thread, void *arg) {
ReferenceIterator* scanner = (ReferenceIterator *)arg;
if (thread->is_current_thread()) {
thread->scan_current_thread(&ReferenceIterator::scan_thread_range, arg, scanner->_stack_bottom);
} else {
thread->scan_other_thread(&ReferenceIterator::scan_thread_range, arg, true);
}
}
inline void scan_threads() {
_zone->scan_registered_threads(&ReferenceIterator::scan_one_thread, this);
}
inline void push_associations(void *block) {
AssocationsHashMap &associations(_zone->assocations());
AssocationsHashMap::iterator i = associations.find(block);
if (i != associations.end()) {
ObjectAssocationHashMap *refs = i->second;
for (ObjectAssocationHashMap::iterator j = refs->begin(); j != refs->end(); j++) {
void *key = j->first;
void *value = j->second;
ReferenceInfo info(key);
if (_zone->in_subzone_memory(value)) {
Subzone *subzone = Subzone::subzone(value);
usword_t q = subzone->quantum_index(value);
_visitor.visit(info, (void**)block, subzone, q);
if (!subzone->test_set_mark(q) && Configuration::ScanningStrategy::should_scan(subzone, q)) {
_pending_stack.push(subzone, q);
}
} else {
Large *large = Large::large(value);
_visitor.visit(info, (void**)block, large);
if (!large->test_set_mark() && Configuration::ScanningStrategy::should_scan(large)) {
_pending_stack.push(large);
}
}
}
}
}
class AssociationScanningStrategy;
struct AssociationScanningConfiguration;
typedef typename rebind<AssociationScanningConfiguration>::other AssociationReferenceIterator;
struct AssociationScanningConfiguration {
typedef typename ReferenceIterator::ReferenceVisitor ReferenceVisitor;
typedef typename PendingStack::template rebind<AssociationReferenceIterator>::other PendingStack;
typedef typename AssociationReferenceIterator::AssociationScanningStrategy ScanningStrategy;
typedef typename Configuration::ScanningStrategy::template rebind<AssociationReferenceIterator>::other OriginalScanningStrategy;
};
class AssociationScanningStrategy {
public:
inline static bool should_scan(Subzone *subzone, usword_t q) { return Configuration::OriginalScanningStrategy::should_scan(subzone, q); }
inline static bool should_scan(Large *large) { return Configuration::OriginalScanningStrategy::should_scan(large); }
inline static void scan_block(ReferenceIterator &scanner, void *block, usword_t size, WriteBarrier *wb) {
Configuration::OriginalScanningStrategy::scan_block(scanner, block, size, wb);
scanner.push_associations(block);
}
inline static void scan_object(ReferenceIterator &scanner, void *object, usword_t size, const unsigned char* map, WriteBarrier *wb) {
Configuration::OriginalScanningStrategy::scan_object(scanner, object, size, map, wb);
scanner.push_associations(object);
}
};
inline bool associations_should_be_scanned(void *block) {
if (_zone->in_subzone_memory(block)) {
Subzone *subzone = Subzone::subzone(block);
return subzone->block_is_start(block) && subzone->is_marked(block);
} else if (_zone->in_large_memory(block) && Large::is_start(block)) {
return Large::large(block)->is_marked();
}
return true;
}
inline void scan_associations() {
typename AssociationScanningConfiguration::PendingStack pendingStack;
AssociationReferenceIterator associationScanner(_zone, _visitor, pendingStack);
SpinLock lock(_zone->associations_lock());
AssocationsHashMap &associations(_zone->assocations());
for (AssocationsHashMap::iterator i = associations.begin(), end = associations.end(); i != end; i++) {
void *block = i->first;
if (associations_should_be_scanned(block)) {
ObjectAssocationHashMap *refs = i->second;
for (ObjectAssocationHashMap::iterator j = refs->begin(); j != refs->end(); j++) {
void *key = j->first;
void *value = j->second;
ReferenceInfo info(key);
if (_zone->in_subzone_memory(value)) {
Subzone *subzone = Subzone::subzone(value);
usword_t q = subzone->quantum_index(value);
_visitor.visit(info, (void**)block, subzone, q);
if (!subzone->test_set_mark(q) && Configuration::ScanningStrategy::should_scan(subzone, q)) {
pendingStack.push(subzone, q);
}
} else {
Large *large = Large::large(value);
_visitor.visit(info, (void**)block, large);
if (!large->test_set_mark() && Configuration::ScanningStrategy::should_scan(large)) {
pendingStack.push(large);
}
}
}
pendingStack.scan(associationScanner);
}
}
}
inline void scan() {
scan_roots();
scan_threads();
scan_associations();
}
};
template <typename ReferenceIterator> class FullScanningStrategy {
public:
template <typename U> struct rebind { typedef FullScanningStrategy<U> other; };
inline static bool should_scan(Subzone *subzone, usword_t q) {
return subzone->is_scanned(q);
}
inline static bool should_scan(Large *large) {
return large->is_scanned();
}
inline static void scan_block(ReferenceIterator &scanner, void *block, usword_t size, WriteBarrier *wb) {
void **slots = (void **)block;
void **last = (void **)displace(slots, size - sizeof(void*));
ReferenceInfo info(kConservativeHeapReference, wb);
while (slots <= last) {
scanner.scan_reference(info, slots);
++slots;
}
}
inline static void scan_object(ReferenceIterator &scanner, void *object, usword_t size, const unsigned char* map, WriteBarrier *wb) {
ReferenceInfo exactInfo(kExactHeapReference, wb);
void **slots = (void **)object;
void **last = (void **)displace(slots, size - sizeof(void*));
if (map == NULL) {
while (slots <= last) scanner.scan_reference(exactInfo, slots++);
return;
}
while (unsigned data = *map++) {
unsigned skip = data >> 4;
unsigned run = data & 0xf;
slots += skip;
while (run--) scanner.scan_reference(exactInfo, slots++);
}
ReferenceInfo conservativeInfo(kConservativeHeapReference, wb);
while (slots <= last) scanner.scan_reference(conservativeInfo, slots++);
}
};
template <typename ReferenceIterator> class GenerationalScanningStrategy {
public:
template <typename U> struct rebind { typedef GenerationalScanningStrategy<U> other; };
inline static bool should_scan(Subzone *subzone, usword_t q) {
return subzone->is_scanned(q) && subzone->write_barrier().range_has_marked_cards(subzone->quantum_address(q), subzone->size(q));
}
inline static bool should_scan(Large *large) {
return large->is_scanned() && large->write_barrier().range_has_marked_cards(large->address(), large->size());
}
inline static void scan_block(ReferenceIterator &scanner, void *block, usword_t size, WriteBarrier *wb) {
wb->scan_marked_ranges(block, size, &ReferenceIterator::scan_conservative_range, &scanner);
}
inline static void scan_object(ReferenceIterator &scanner, void *object, usword_t size, const unsigned char* map, WriteBarrier *wb) {
if (map == NULL) {
wb->scan_marked_ranges(object, size, &ReferenceIterator::scan_exact_range, &scanner);
return;
}
void **slots = (void **)object;
void **last = (void **)displace(slots, size - sizeof(void*));
while (unsigned data = *map++) {
unsigned skip = data >> 4;
unsigned run = data & 0xf;
slots += skip;
wb->scan_marked_ranges(slots, run, &ReferenceIterator::scan_exact_range, &scanner);
slots += run;
}
if (slots < last) wb->scan_marked_ranges(slots, (1 + last - slots) * sizeof(void*), &ReferenceIterator::scan_conservative_range, &scanner);
}
};
};
#endif // __AUTO_REFERENCE_ITERATOR__