AutoMemoryScanner.cpp [plain text]
#include "AutoAdmin.h"
#include "AutoBlockIterator.h"
#include "AutoDefs.h"
#include "AutoEnvironment.h"
#include "AutoLarge.h"
#include "AutoRange.h"
#include "AutoMemoryScanner.h"
#include "AutoSubzone.h"
#include "AutoThread.h"
#include "AutoWriteBarrier.h"
#include "AutoZone.h"
namespace Auto {
MemoryScanner::MemoryScanner(Zone *zone, void *current_stack_bottom, bool does_check_block)
: _zone(zone), _current_stack_bottom(current_stack_bottom),
_use_pending(false),
_some_pending(false),
_is_partial(false),
_is_collector(false),
_does_check_block(does_check_block),
_should_coalesce(false),
_use_exact_scanning(Environment::use_exact_scanning),
_coalesced_range(),
_amount_scanned(0),
_blocks_scanned(0)
{
#if defined(__ppc__)
#endif
}
void MemoryScanner::scan_for_unmarked_blocks(Subzone *subzone, usword_t q, void *block) {
Range range(block, subzone->size(q));
ASSERTION(subzone->block_is_start(q));
if (subzone->layout(q) == AUTO_OBJECT_SCANNED) {
scan_object_range(range, &subzone->write_barrier());
} else {
WriteBarrier *wb = &subzone->write_barrier();
if (_is_partial && range.size() >= 256)
wb->scan_marked_ranges(range, *this);
else
scan_range(range, wb);
}
if (_zone->_scanning_associations) _zone->pend_associations(block, *this);
}
void MemoryScanner::scan_for_unmarked_blocks(Large *large, void *block) {
Range range(block, large->size());
if (large->layout() == AUTO_OBJECT_SCANNED) {
scan_object_range(range, &large->write_barrier());
} else {
WriteBarrier *wb = &large->write_barrier();
if (_is_partial)
wb->scan_marked_ranges(range, *this);
else
scan_range(range, wb);
}
if (_zone->_scanning_associations) _zone->pend_associations(block, *this);
}
void MemoryScanner::scan_object_range(Range &block, WriteBarrier *wb) {
if (_use_exact_scanning) {
const unsigned char *map = _zone->layout_map_for_block(block.address());
if (map) {
scan_with_layout(block, map, wb);
return;
}
} else {
const unsigned char *map = _zone->weak_layout_map_for_block(block.address());
if (map) {
scan_with_weak_layout(block, map, wb);
return;
}
}
if (_is_partial)
wb->scan_marked_ranges(block, *this);
else
scan_range(block, wb);
}
void MemoryScanner::scan_with_layout(Range &block, const unsigned char* map, WriteBarrier *wb) {
AUTO_PROBE(auto_probe_scan_with_layout((void *)block.address(), (void *)block.end(), map));
void **reference = (void **)block.address();
void **end = (void **)block.end();
Range subrange;
while (unsigned data = *map++) {
unsigned skip = data >> 4;
unsigned run = data & 0xf;
reference += skip;
subrange.set_range(reference, reference + run);
if (subrange.address() < end && subrange.end() <= end) {
scan_range(subrange, wb);
} else {
break;
}
reference += run;
}
if (reference < end) {
subrange.set_range((void *)reference, end);
scan_range(subrange, wb);
}
AUTO_PROBE(auto_probe_did_scan_with_layout((void *)block.address(), (void *)block.end(), map));
}
void MemoryScanner::scan_with_weak_layout(Range &block, const unsigned char* map, WriteBarrier *wb) {
AUTO_PROBE(auto_probe_scan_with_weak_layout((void *)block.address(), (void *)block.end(), map));
void **reference = (void **)block.address();
Range subrange;
while (unsigned data = *map++) {
unsigned run = data >> 4;
unsigned skip = data & 0xf;
subrange.set_range(reference, reference + run);
scan_range(subrange, wb);
reference += run;
reference += skip;
}
subrange.set_range((void *)reference, block.end());
scan_range(subrange, wb);
}
void MemoryScanner::set_pending(void *block) {
#if defined(DEBUG)
_blocks_checked++;
#endif
if (!block) return;
if (_zone->in_subzone_memory(block)) {
Subzone *subzone = Subzone::subzone(block);
usword_t q = subzone->quantum_index_unchecked(block);
if (!subzone->block_is_start(q)) return;
AUTO_PROBE(auto_probe_set_pending(block));
if (is_partial()) {
if (!subzone->should_pend_new(block, q)) return;
} else {
if (!subzone->should_pend(block, q)) return;
}
if (_use_pending) {
subzone->set_pending(q);
set_some_pending();
} else {
_zone->scan_stack_push_block(block);
}
#if defined(DEBUG)
_blocks_scanned++;
#endif
} else if (_zone->in_large_memory(block)) {
if (!Large::is_start(block)) return;
AUTO_PROBE(auto_probe_set_pending(block));
Large *large = Large::large(block);
if (is_partial() && !large->is_new()) return;
if (large->test_set_mark()) return;
if (large->layout() & AUTO_UNSCANNED) return;
if (_use_pending) {
large->set_pending();
set_some_pending();
} else {
_zone->scan_stack_push_block(block);
}
#if defined(DEBUG)
_blocks_scanned++;
#endif
}
}
void MemoryScanner::repend(void *block) {
if (_zone->in_subzone_memory(block)) {
Subzone *subzone = Subzone::subzone(block);
if (!subzone->block_is_start(block)) return;
usword_t q = subzone->quantum_index(block);
if (subzone->test_set_mark(q)) return;
if (subzone->layout(q) & AUTO_UNSCANNED) return;
if (_use_pending) {
subzone->set_pending(q);
set_some_pending();
} else {
_zone->scan_stack_push_block(block);
}
} else if (_zone->in_large_memory(block)) {
if (!Large::is_start(block)) return;
Large *large = Large::large(block);
if (large->test_set_mark()) return;
if (large->layout() & AUTO_UNSCANNED) return;
if (_use_pending) {
large->set_pending();
set_some_pending();
} else {
_zone->scan_stack_push_block(block);
}
}
}
void MemoryScanner::check_block(void **reference, void *block) {
set_pending(block);
}
void MemoryScanner::associate_block(void **reference, void *key, void *block) {
set_pending(block);
}
#if defined(__ppc__)
inline vector unsigned int MemoryScanner::isolate_altivec_vector(vector unsigned int data_vector, vector unsigned int lo_vector, vector unsigned int diff_vector) {
vector unsigned int biased_vector = vec_sub(data_vector, lo_vector);
vector unsigned int compare_vector = vec_cmpgt(diff_vector, biased_vector);
return vec_and(data_vector, compare_vector);
}
inline void MemoryScanner::check_altivec_vector(void **isolated_vector) {
void *result0 = isolated_vector[0];
void *result1 = isolated_vector[1];
void *result2 = isolated_vector[2];
void *result3 = isolated_vector[3];
if (result0) set_pending(result0);
if (result1) set_pending(result1);
if (result2) set_pending(result2);
if (result3) set_pending(result3);
}
void MemoryScanner::scan_range_altivec(void **reference, void **end) {
typedef union {
vector unsigned int _as_vector;
void *_as_pointer[4];
} ConvertBuffer;
vector unsigned int *reference_vector = (vector unsigned int *)reference;
vector unsigned int *end_vector = (vector unsigned int *)end;
vector unsigned int data_vector0 = *reference_vector++; vector unsigned int data_vector1;
vector unsigned int *near_end_vector = end_vector - 1;
vector unsigned int lo_vector = _lo_vector;
vector unsigned int diff_vector = _diff_vector;
ConvertBuffer buffer0 = {{ NULL, NULL, NULL, NULL }};
ConvertBuffer buffer1 = {{ NULL, NULL, NULL, NULL }};
while (reference_vector < near_end_vector) {
data_vector1 = *reference_vector++;
buffer1._as_vector = isolate_altivec_vector(data_vector0, lo_vector, diff_vector);
check_altivec_vector(buffer0._as_pointer);
data_vector0 = *reference_vector++;
buffer0._as_vector = isolate_altivec_vector(data_vector1, lo_vector, diff_vector);
check_altivec_vector(buffer1._as_pointer);
}
buffer1._as_vector = isolate_altivec_vector(data_vector0, lo_vector, diff_vector);
check_altivec_vector(buffer0._as_pointer);
if (reference_vector < end_vector) {
buffer0._as_vector = isolate_altivec_vector(*reference_vector, lo_vector, diff_vector);
check_altivec_vector(buffer1._as_pointer);
check_altivec_vector(buffer0._as_pointer);
} else {
check_altivec_vector(buffer1._as_pointer);
}
}
#endif
inline bool is_block_aligned_range(void **start, void **end) {
return (((uintptr_t)start | (uintptr_t)end) & mask(block_alignment)) == 0;
}
void MemoryScanner::scan_range(const Range &range, WriteBarrier *wb) {
AUTO_PROBE(auto_probe_scan_range((void *)range.address(), (void *)range.end()));
void **reference = (void **)range.address();
void **end = (void **)range.end();
ASSERTION(reference <= end);
if (!is_pointer_aligned(reference) || !is_pointer_aligned(end)) {
static char buffer[256];
snprintf(buffer, sizeof(buffer), "scan_range: non-pointer aligned range = { %p, %p }\n", reference, end);
__crashreporter_info__ = buffer;
__builtin_trap();
}
const bool repair_write_barrier = (wb && _zone->repair_write_barrier());
if (_should_coalesce && !repair_write_barrier) {
if (_coalesced_range.end() == (void *)reference) {
_coalesced_range.set_end(end);
return;
}
reference = (void **)_coalesced_range.address();
end = (void **)_coalesced_range.end();
_coalesced_range = range;
}
if (reference == end) return;
if (!use_pending()) {
const usword_t scan_maximum = 1024;
usword_t size = (uintptr_t)end - (uintptr_t)reference;
if (size > scan_maximum) {
end = (void **)displace((void *)reference, scan_maximum);
Range tail(end, size - scan_maximum);
if (repair_write_barrier) {
_zone->scan_stack_push_write_barrier(wb);
}
_zone->scan_stack_push_range(tail);
}
}
_amount_scanned += (char *)end - (char *)reference;
__builtin_prefetch(reference);
uintptr_t valid_lowest = (uintptr_t)_zone->coverage().address();
uintptr_t valid_size = (uintptr_t)_zone->coverage().end() - valid_lowest;
if (repair_write_barrier || _does_check_block || !is_block_aligned_range(reference, end)) {
void *last_valid_pointer = end - 1;
for ( ; reference <= last_valid_pointer; ++reference) {
void *referent = *reference;
if (((intptr_t)referent - valid_lowest) < valid_size && _zone->block_is_start(referent)) {
check_block(reference, referent);
if (repair_write_barrier && _zone->is_new(referent))
wb->mark_card(reference);
}
}
} else
#if defined(__ppc__)
if (has_altivec()) {
scan_range_altivec(reference, end);
} else
#endif
{
while (reference < end) {
void *referent0 = reference[0];
void *referent1 = reference[1];
void *referent2 = reference[2];
void *referent3 = reference[3];
reference += 4; __builtin_prefetch(reference);
if (((intptr_t)referent0 - valid_lowest) < valid_size) set_pending(referent0);
if (((intptr_t)referent1 - valid_lowest) < valid_size) set_pending(referent1);
if (((intptr_t)referent2 - valid_lowest) < valid_size) set_pending(referent2);
if (((intptr_t)referent3 - valid_lowest) < valid_size) set_pending(referent3);
}
}
}
extern "C" {
void scanMemory(void *context, void *start, void *end) {
MemoryScanner *scanner = (MemoryScanner *)context;
Range r(start, end);
scanner->scan_range(r);
}
}
void MemoryScanner::scan_external() {
if (_zone->control.scan_external_callout) _zone->control.scan_external_callout((void *)this, scanMemory);
}
void MemoryScanner::scan_range_from_thread(Range &range, Thread &thread) {
scan_range(range);
}
void MemoryScanner::scan_range_from_registers(Range &range, Thread &thread, int first_register) {
scan_range(range);
}
struct scan_retained_blocks_visitor {
MemoryScanner &_scanner;
scan_retained_blocks_visitor(MemoryScanner &scanner) : _scanner(scanner) {}
inline bool visit(Zone *zone, Subzone *subzone, usword_t q) {
if ((subzone->has_refcount(q) || subzone->is_thread_local(q)) && !subzone->test_set_mark(q)) {
if (subzone->layout(q) & AUTO_UNSCANNED) return true;
if (_scanner.use_pending()) {
subzone->set_pending(q);
} else {
zone->scan_stack_push_block(subzone->quantum_address(q));
}
}
return true;
}
inline bool visit(Zone *zone, Large *large) {
if (large->refcount() && !large->test_set_mark()) {
if (large->layout() & AUTO_UNSCANNED) return true;
if (_scanner.use_pending()) {
large->set_pending();
} else {
zone->scan_stack_push_block(large->address());
}
}
return true;
}
};
void MemoryScanner::scan_retained_blocks() {
scan_retained_blocks_visitor visitor(*this);
visitAllocatedBlocks(_zone, visitor);
set_some_pending();
}
struct scan_retained_and_old_blocks_visitor {
MemoryScanner &_scanner; const bool _use_pending;
scan_retained_and_old_blocks_visitor(MemoryScanner &scanner) : _scanner(scanner), _use_pending(scanner.use_pending()) {}
inline bool visit(Zone *zone, Subzone *subzone, usword_t q) {
if (!subzone->is_thread_local(q) && subzone->is_new(q)) {
if (subzone->has_refcount(q) && !subzone->test_set_mark(q) && subzone->is_scanned(q)) {
if (_use_pending) {
subzone->set_pending(q);
} else {
zone->scan_stack_push_block(subzone->quantum_address(q));
}
}
} else {
if (!subzone->test_set_mark(q) && subzone->is_scanned(q)) {
void *address = subzone->quantum_address(q);
usword_t size = subzone->size(q);
if (subzone->write_barrier().range_has_marked_cards(address, size)) {
if (_use_pending) {
subzone->set_pending(q);
} else {
zone->scan_stack_push_block(address);
}
}
}
}
return true;
}
inline bool visit(Zone *zone, Large *large) {
if (large->is_new()) {
if (large->refcount() && !large->test_set_mark() && large->is_scanned()) {
if (_use_pending) {
large->set_pending();
} else {
zone->scan_stack_push_block(large->address());
}
}
} else {
if (!large->test_set_mark() && large->is_scanned()) {
void *address = large->address();
usword_t size = large->size();
if (large->write_barrier().range_has_marked_cards(address, size)) {
if (_use_pending) {
large->set_pending();
} else {
zone->scan_stack_push_block(large->address());
}
}
}
}
return true;
}
};
void MemoryScanner::scan_retained_and_old_blocks() {
scan_retained_and_old_blocks_visitor visitor(*this);
visitAllocatedBlocks(_zone, visitor);
set_some_pending();
}
void MemoryScanner::scan_root_ranges() {
PointerList &list = _zone->garbage_list();
_zone->copy_roots(list);
void **roots = (void **)list.buffer();
for (usword_t i = 0, count = list.count(); i < count; i++) {
Range range(roots[i], sizeof(void*));
scan_range(range);
}
}
void MemoryScanner::scan_thread_ranges(bool withSuspend, bool includeCurrentThread) {
Zone::thread_scanner_t scanner = includeCurrentThread ?
^(Thread *thread) {
thread->scan_thread(*this, withSuspend);
}
:
^(Thread *thread) {
if (!thread->is_current_thread()) {
thread->scan_thread(*this, withSuspend);
}
};
_zone->scan_registered_threads(scanner);
}
void MemoryScanner::check_roots() {
scan_retained_blocks();
scan_root_ranges();
}
struct scan_pending_blocks_visitor {
MemoryScanner &_scanner;
scan_pending_blocks_visitor(MemoryScanner &scanner) : _scanner(scanner) {}
inline bool visit(Zone *zone, Subzone *subzone, usword_t q) {
if (subzone->is_pending(q)) {
subzone->clear_pending(q);
_scanner.scan_for_unmarked_blocks(subzone, q, subzone->quantum_address(q));
}
return true;
}
inline bool visit(Zone *zone, Large *large) {
if (large->is_pending()) {
large->clear_pending();
_scanner.scan_for_unmarked_blocks(large, large->address());
}
return true;
}
};
void MemoryScanner::scan_pending_blocks() {
scan_pending_blocks_visitor visitor(*this);
_should_coalesce = true;
visitAllocatedBlocks(_zone, visitor);
scan_range((void *)NULL, (void *)NULL);
_should_coalesce = false;
}
void MemoryScanner::scan_pending_until_done() {
if (use_pending()) {
while (is_some_pending()) {
clear_some_pending();
scan_pending_blocks();
}
} else {
while (!_zone->scan_stack_is_empty()) {
if (_zone->scan_stack_is_range()) {
Range range = _zone->scan_stack_pop_range();
WriteBarrier *wb = _zone->scan_stack_is_write_barrier() ? _zone->scan_stack_pop_write_barrier() : NULL;
scan_range(range, wb);
} else {
void *block = _zone->scan_stack_pop_block();
if (_zone->in_subzone_memory(block)) {
Subzone *subzone = Subzone::subzone(block);
usword_t q = subzone->quantum_index(block);
scan_for_unmarked_blocks(subzone, q, block);
} else {
Large *large = Large::large(block);
scan_for_unmarked_blocks(large, block);
}
}
}
}
}
void MemoryScanner::scan() {
_amount_scanned = 0;
_blocks_scanned = 0;
#if defined(DEBUG)
_blocks_checked = 0;
uint64_t start_time = micro_time();
#endif
check_roots();
scan_pending_until_done();
const bool includeCurrentThread = !_zone->multithreaded;
scan_thread_ranges(false, includeCurrentThread);
scan_external();
scan_pending_until_done();
AUTO_PROBE(auto_scan_barrier());
scan_barrier();
#if defined(DEBUG)
uint64_t suspend_start_time = micro_time();
#endif
scan_thread_ranges(true, includeCurrentThread);
scan_pending_until_done();
AUTO_PROBE(auto_probe_end_thread_scan());
#if defined(DEBUG)
unsigned suspend_end_time = (unsigned)(micro_time() - suspend_start_time);
#endif
_zone->scan_associations(*this);
#if defined(DEBUG)
unsigned end_time = (unsigned)(micro_time() - start_time);
unsigned thread_count = 0;
for (Thread *thread = _zone->threads(); thread; thread = thread->next()) thread_count++;
if (Environment::print_scan_stats) {
printf("%s scan %10u (%3lu%%) bytes in %5u usecs, %6u blocks checked, %6u (%3lu%%) blocks scanned, %4u usecs per %3u threads, scan stack max %lu\n",
is_partial() ? "Partial" : "Full ",
(unsigned)_amount_scanned, (unsigned)_amount_scanned * 100 / _zone->statistics().size(),
end_time,
(unsigned)_blocks_checked,
(unsigned)_blocks_scanned, (unsigned)_blocks_scanned * 100 / _zone->statistics().count(),
suspend_end_time/thread_count, thread_count,
_zone->scan_stack_max());
}
#endif
}
void MemoryScanner::scan_barrier() {}
};