ZoneCompaction.cpp [plain text]
#include "ReferenceIterator.h"
#include "Zone.h"
extern "C" {
void *CompactionWatchPoint = NULL;
char CompactionObserverKey;
}
#define NON_OBJECT_WEAK_REFERENCES_SHOULD_PIN 1
namespace Auto {
static malloc_zone_t *_compaction_zone = NULL;
static malloc_logger_t *_old_malloc_logger = NULL;
static void _disabled_malloc_logger(uint32_t, uintptr_t, uintptr_t, uintptr_t, uintptr_t, uint32_t) {}
class CompactionZone {
public:
CompactionZone() {
_compaction_zone = malloc_create_zone(4096, 0);
malloc_set_zone_name(_compaction_zone, "compaction_zone");
if (malloc_logger) {
_old_malloc_logger = malloc_logger;
malloc_logger = _disabled_malloc_logger;
}
}
~CompactionZone() {
if (_old_malloc_logger) {
malloc_logger = _old_malloc_logger;
_old_malloc_logger = NULL;
}
malloc_destroy_zone(_compaction_zone);
_compaction_zone = NULL;
}
};
template <typename T> struct CompactionZoneAllocator {
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 CompactionZoneAllocator<U> other; };
template <typename U> CompactionZoneAllocator(const CompactionZoneAllocator<U>&) {}
CompactionZoneAllocator() {}
CompactionZoneAllocator(const CompactionZoneAllocator&) {}
~CompactionZoneAllocator() {}
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_zone_calloc(_compaction_zone, n, sizeof(T)));
}
void deallocate(pointer p, size_type) { ::malloc_zone_free(_compaction_zone, 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 CompactionZoneAllocator&);
};
template<> struct CompactionZoneAllocator<void> {
typedef void value_type;
typedef void* pointer;
typedef const void *const_pointer;
template <typename U> struct rebind { typedef CompactionZoneAllocator<U> other; };
};
template <typename T>
inline bool operator==(const CompactionZoneAllocator<T>&,
const CompactionZoneAllocator<T>&) {
return true;
}
template <typename T>
inline bool operator!=(const CompactionZoneAllocator<T>&,
const CompactionZoneAllocator<T>&) {
return false;
}
template <typename ReferenceIterator> class ZonePendingStack {
typedef std::vector<uintptr_t, CompactionZoneAllocator<uintptr_t> > uintptr_vector;
uintptr_vector _small_stack, _large_stack;
public:
void push(Subzone *subzone, usword_t q) {
_small_stack.push_back(subzone->pack(q));
}
void push(Large *large) {
_large_stack.push_back(uintptr_t(large));
}
static bool mark(Subzone *subzone, usword_t q) { return subzone->test_and_set_mark(q); }
static bool mark(Large *large) { return large->test_and_set_mark(); }
static bool is_marked(Subzone *subzone, usword_t q) { return subzone->is_marked(q); }
static bool is_marked(Large *large) { return large->is_marked(); }
void scan(ReferenceIterator &scanner) {
for (;;) {
if (_small_stack.size()) {
uintptr_t back = _small_stack.back();
_small_stack.pop_back();
usword_t q;
Subzone *subzone = Subzone::unpack(back, q);
scanner.scan(subzone, q);
} else if (_large_stack.size()) {
Large *large = reinterpret_cast<Large*>(_large_stack.back());
_large_stack.pop_back();
scanner.scan(large);
} else {
return;
}
}
}
const PendingStackHint hints() { return PendingStackWantsEagerScanning; }
template <typename U> struct rebind { typedef ZonePendingStack<U> other; };
};
template <typename ReferenceIterator> class EmptyPendingStack {
public:
void push(Subzone *subzone, usword_t q) {}
void push(Large *large) {}
static bool mark(Subzone *subzone, usword_t q) { return false; }
static bool mark(Large *large) { return false; }
static bool is_marked(Subzone *subzone, usword_t q) { return false; }
static bool is_marked(Large *large) { return false; }
void scan(ReferenceIterator &scanner) {}
template <typename U> struct rebind { typedef EmptyPendingStack<U> other; };
};
typedef void (^mark_pinned_t) (void **slot, Subzone *subzone, usword_t q, ReferenceKind kind);
class CompactionClassifier {
size_t _kindCounts[kReferenceKindCount];
Zone *_zone;
mark_pinned_t _marker;
struct Configuration;
typedef ReferenceIterator<Configuration> CompactingReferenceIterator;
class CompactionScanningStrategy : public FullScanningStrategy<CompactingReferenceIterator> {
public:
inline static bool visit_interior_pointers() { return true; }
inline static bool scan_threads_suspended() { return false; }
inline static pthread_rwlock_t *associations_lock(Zone *zone) { return NULL; } };
struct Configuration {
typedef CompactionClassifier ReferenceVisitor;
typedef ZonePendingStack<CompactingReferenceIterator> PendingStack;
typedef CompactionScanningStrategy ScanningStrategy;
};
public:
CompactionClassifier(Zone *zone, mark_pinned_t marker) : _zone(zone), _marker(marker) { bzero(_kindCounts, sizeof(_kindCounts)); }
inline void mark_pinned(void **slot, Subzone *subzone, usword_t q, ReferenceKind kind) { _marker(slot, subzone, q, kind); }
bool is_weak_slot_ivar(void *slot, void *slot_base, usword_t slot_layout) {
if (slot_layout & AUTO_OBJECT) {
const unsigned char *weak_layout = _zone->weak_layout_map_for_block(slot_base);
if (weak_layout) {
void **slots = (void **)slot_base;
while (unsigned char byte = *weak_layout++) {
uint8_t skips = (byte >> 4);
slots += skips;
uint8_t weaks = (byte & 0x0F);
while (weaks--) {
if (slot == (void *)slots++)
return true;
}
}
}
}
return false;
}
void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {
if (subzone->quantum_address(q) == CompactionWatchPoint) {
printf("visiting a reference to CompactionWatchPoint = %p\n", CompactionWatchPoint);
}
ReferenceKind kind = info.kind();
_kindCounts[kind]++;
switch (kind) {
case kAllPointersHeapReference:
case kAssociativeReference:
case kExactHeapReference:
case kRootReference:
break;
case kWeakReference:
{
__block void *slot_block = NULL;
__block usword_t slot_layout = 0;
blockStartNoLockDo(_zone, slot, ^(Subzone *slot_subzone, usword_t slot_q) {
slot_block = slot_subzone->quantum_address(slot_q);
slot_layout = slot_subzone->layout(slot_q);
if (!is_weak_slot_ivar(slot, slot_block, slot_layout)) {
if (slot_layout != AUTO_MEMORY_ALL_WEAK_POINTERS) {
mark_pinned(NULL, slot_subzone, slot_q, kWeakSlotReference);
mark_pinned(slot, subzone, q, kWeakReference);
} else if (slot == slot_block) {
mark_pinned(NULL, slot_subzone, slot_q, kWeakSlotReference);
}
}
}, ^(Large *slot_large) {
slot_block = slot_large->address();
slot_layout = slot_large->layout();
if (!is_weak_slot_ivar(slot, slot_block, slot_layout)) {
if (slot_layout != AUTO_MEMORY_ALL_WEAK_POINTERS)
mark_pinned(slot, subzone, q, kWeakReference);
}
});
if (!slot_block) {
if (!_zone->is_global_address_nolock(slot)) {
mark_pinned(slot, subzone, q, kWeakReference);
}
}
}
break;
default:
mark_pinned(slot, subzone, q, kind);
break;
}
}
void visit(const ReferenceInfo &info, void **slot, Large *large) {
if (info.kind() == kWeakReference) {
if (_zone->in_subzone_memory(slot)) {
usword_t slot_q;
Subzone *slot_subzone = Subzone::subzone(slot);
void *slot_block = slot_subzone->block_start(slot, slot_q);
if (slot_block) {
usword_t slot_layout = slot_subzone->layout(slot_q);
if (!is_weak_slot_ivar(slot, slot_block, slot_layout)) {
if (slot_layout != AUTO_MEMORY_ALL_WEAK_POINTERS || slot == slot_block) {
mark_pinned(NULL, slot_subzone, slot_q, kWeakSlotReference);
}
}
}
}
}
}
void visit_weak_callback(auto_weak_callback_block_t *callback) {
if (_zone->in_subzone_memory(callback)) {
usword_t q;
Subzone *subzone = Subzone::subzone(callback);
void *callback_start = subzone->block_start(callback, q);
if (callback_start) {
if (!subzone->is_pinned(q)) {
mark_pinned(NULL, subzone, q, kWeakReference);
}
}
}
}
void visit_weak_slot(void **slot) {
if (_zone->in_subzone_memory(slot)) {
usword_t slot_q;
Subzone *slot_subzone = Subzone::subzone(slot);
void *slot_block = slot_subzone->block_start(slot, slot_q);
if (slot_block) {
usword_t slot_layout = slot_subzone->layout(slot_q);
if (!is_weak_slot_ivar(slot, slot_block, slot_layout)) {
if (slot_layout != AUTO_MEMORY_ALL_WEAK_POINTERS || slot == slot_block)
mark_pinned(NULL, slot_subzone, slot_q, kWeakSlotReference);
}
}
}
}
void classify_weak_reference(weak_referrer_t &ref) {
void **slot = ref.referrer;
blockDo(_zone, (void*)*slot,
^(Subzone *subzone, usword_t q) { visit(kWeakReference, slot, subzone, q); },
^(Large *large) { visit(kWeakReference, slot, large); },
^(void *block) { visit_weak_slot(slot); });
if (uintptr_t(ref.block) & 1) {
visit_weak_callback((auto_weak_callback_block_t *)displace(ref.block, -1));
}
}
void scan_garbage(CompactingReferenceIterator &scanner) {
for (Region *region = _zone->region_list(); region != NULL; region = region->next()) {
SubzoneRangeIterator iterator(region->subzone_range());
while (Subzone *subzone = iterator.next()) {
usword_t n = subzone->allocation_count();
for (usword_t q = 0; q < n; q = subzone->next_quantum(q)) {
if (!subzone->is_free(q) && !subzone->test_and_set_mark(q)) {
usword_t layout = subzone->layout(q);
if (layout & AUTO_OBJECT_UNSCANNED) {
mark_pinned(NULL, subzone, q, kGarbageReference);
} else if (::is_scanned(layout)) {
scanner.scan(subzone, q);
scanner.flush();
}
}
}
}
}
for (Large *large = _zone->large_list(); large != NULL; large = large->next()) {
if (!large->test_and_set_mark() && large->is_scanned()) {
scanner.scan(large);
scanner.flush();
}
}
}
void scan(void *stack_bottom) {
Configuration::PendingStack stack;
CompactingReferenceIterator scanner(_zone, *this, stack, stack_bottom, false, false);
scanner.scan();
#if NON_OBJECT_WEAK_REFERENCES_SHOULD_PIN
weak_enumerate_table_fixup(_zone, ^(weak_referrer_t &ref) {
classify_weak_reference(ref);
});
#endif
scan_garbage(scanner);
}
void printKindCounts() {
for (int i = 0; i < kReferenceKindCount; ++i) {
printf("<%s> : %lu\n", ReferenceInfo::name(ReferenceKind(i)), _kindCounts[i]);
}
}
};
struct page_statistics_visitor {
size_t _pageIndex, _prevUnpinnedPageIndex;
size_t _blocksPerPage, _pinnedBlocksPerPage;
size_t _pinnedPages, _unpinnedPages;
size_t _pinnedBlocks, _unpinnedBlocks;
size_t _pinnedBytes, _unpinnedBytes;
page_statistics_visitor()
: _pageIndex(0), _prevUnpinnedPageIndex(0), _blocksPerPage(0), _pinnedBlocksPerPage(0),
_pinnedPages(0), _unpinnedPages(0), _pinnedBlocks(0), _unpinnedBlocks(0),
_pinnedBytes(0), _unpinnedBytes(0)
{
}
inline bool visit(Zone *zone, Subzone *subzone, usword_t q) {
size_t page = (uintptr_t(subzone->quantum_address(q)) >> page_size_log2);
if (page != _pageIndex) {
if (_pageIndex) {
if (_pinnedBlocksPerPage == 0) {
_prevUnpinnedPageIndex = _pageIndex;
++_unpinnedPages;
} else {
++_pinnedPages;
_pinnedBlocksPerPage = 0;
}
}
_pageIndex = page;
_blocksPerPage = 0;
}
++_blocksPerPage;
if (subzone->is_pinned(q)) {
++_pinnedBlocksPerPage;
++_pinnedBlocks;
_pinnedBytes += subzone->size(q);
} else {
++_unpinnedBlocks;
_unpinnedBytes += subzone->size(q);
}
return true;
}
inline bool visit(Zone *zone, Large *large) { return false; }
};
static void examine_heap_fragmentation(Zone *zone) {
zone->suspend_all_registered_threads();
struct quantum_counts {
size_t subzones;
size_t total;
size_t holes;
size_t allocs;
size_t unscanned_allocs;
size_t unused;
};
quantum_counts small_counts = { 0 }, medium_counts = { 0 };
for (Region *region = zone->region_list(); region != NULL; region = region->next()) {
SubzoneRangeIterator iterator(region->subzone_range());
while (Subzone *subzone = iterator.next()) {
quantum_counts &counts = subzone->is_small() ? small_counts : medium_counts;
bool unscanned = (subzone->admin()->layout() & AUTO_UNSCANNED);
++counts.subzones;
usword_t q = 0, n = subzone->allocation_count(); while (q < n) {
usword_t nq = subzone->next_quantum(q);
usword_t count = nq - q;
if (subzone->is_free(q))
counts.holes += count;
else {
counts.allocs += count;
if (unscanned) counts.unscanned_allocs += count;
}
q = nq;
}
counts.unused += (subzone->allocation_limit() - n);
counts.total += n;
}
}
size_t largeSize = 0;
for (Large *large = zone->large_list(); large != NULL; large = large->next()) {
largeSize += large->size();
}
printf("largeSize = %ld\n", largeSize);
printf("subzones = { %lu, %lu }\n", small_counts.subzones, medium_counts.subzones);
printf("q total = { %lu, %lu }\n", small_counts.total, medium_counts.total);
printf("q allocs = { %lu, %lu }\n", small_counts.allocs, medium_counts.allocs);
printf("q uallocs= { %lu, %lu }\n", small_counts.unscanned_allocs, medium_counts.unscanned_allocs);
printf("q holes = { %lu, %lu }\n", small_counts.holes, medium_counts.holes);
printf("q unused = { %lu, %lu }\n", small_counts.unused, medium_counts.unused);
zone->resume_all_registered_threads();
}
typedef struct { size_t counts[kReferenceKindCount]; } KindCounts;
typedef std::map<void *, KindCounts, AuxPointerLess, CompactionZoneAllocator<std::pair<void * const, KindCounts> > > PtrKindCountsMap;
typedef __gnu_cxx::hash_set<void *, AuxPointerHash, AuxPointerEqual, CompactionZoneAllocator<void *> > PtrSet;
static void printPinnedReference(FILE *out, void *address, KindCounts &kind) {
fprintf(out, "%p", address);
for (int i = 1; i < kReferenceKindCount; ++i) {
if (kind.counts[i]) fprintf(out, " <%s>[%lu]", ReferenceInfo::name(ReferenceKind(i)), kind.counts[i]);
}
fprintf(out, "\n");
}
static void printPinnedReference(FILE *out, Zone *zone, void *slot_base, void **slot, void *address, const char *name, ReferenceKind kind) {
if (slot_base) {
if (zone->block_layout(slot_base) & AUTO_OBJECT)
fprintf(out, "%p + %ld (%s) -> %p (%s) <%s>\n", slot_base, (long)((char*)slot - (char*)slot_base), zone->name_for_object(slot_base), address, name, ReferenceInfo::name(kind));
else
fprintf(out, "%p + %lu -> %p (%s) <%s>\n", slot_base, (long)((char*)slot - (char*)slot_base), address, name, ReferenceInfo::name(kind));
} else {
switch (kind) {
case kRetainedReference:
case kWeakSlotReference:
case kGarbageReference:
fprintf(out, "%p -> %p (%s) <%s>\n", (void*)NULL, address, name, ReferenceInfo::name(kind)); break;
default:
fprintf(out, "%p -> %p (%s) <%s>\n", slot, address, name, ReferenceInfo::name(kind));
}
}
}
void Zone::analyze_heap(const char *path) {
CompactionZone compactionZone;
if (true) examine_heap_fragmentation(this);
__block struct { char buffer[36]; } name;
FILE *out = fopen(path, "w");
PtrKindCountsMap pinMap;
__block PtrKindCountsMap &pinMapRef = pinMap;
mark_pinned_t marker = ^(void **slot, Subzone *subzone, usword_t q, ReferenceKind kind) {
subzone->mark_pinned(q);
pinMapRef[subzone->quantum_address(q)].counts[kind]++;
printPinnedReference(out, this, block_start(slot), slot, subzone->quantum_address(q),
(subzone->layout(q) & AUTO_OBJECT) ?
name_for_object(subzone->quantum_address(q)) :
(snprintf(name.buffer, sizeof(name.buffer), "%lu bytes", subzone->size(q)), name.buffer),
kind);
};
Mutex marksLock(&_mark_bits_mutex);
ReadLock assocLock(&_associations_lock);
SpinLock weakLock(&weak_refs_table_lock);
reset_all_pinned();
suspend_all_registered_threads();
CompactionClassifier classifier(this, marker);
classifier.scan((void *)auto_get_sp());
page_statistics_visitor visitor;
visitAllocatedBlocks(this, visitor);
printf("unpinned { pages = %lu, blocks = %lu, bytes = %lu }\n", visitor._unpinnedPages, visitor._unpinnedBlocks, visitor._unpinnedBytes);
printf(" pinned { pages = %lu, blocks = %lu, bytes = %lu }\n", visitor._pinnedPages, visitor._pinnedBlocks, visitor._pinnedBytes);
reset_all_marks();
resume_all_registered_threads();
if (false) {
classifier.printKindCounts();
std::for_each(pinMap.begin(), pinMap.end(), ^(PtrKindCountsMap::value_type &pair) {
printPinnedReference(out, pair.first, pair.second);
});
}
fclose(out);
}
template <class Visitor> void visitAllocatedSubzoneBlocksInReverse(Zone *zone, Visitor& visitor) {
for (Region *region = zone->region_list(); region != NULL; region = region->next()) {
SubzoneRangeIterator iterator(region->subzone_range());
while (Subzone *subzone = iterator.previous()) {
usword_t q = subzone->allocation_count();
while ((q = subzone->previous_quantum(q)) != not_found) {
if (!subzone->is_free(q)) {
visitor(zone, subzone, q);
}
}
}
}
}
template <class Visitor> void visitAllocatedBlocksForCompaction(Zone *zone, Visitor& visitor) {
for (Region *region = zone->region_list(); region != NULL; region = region->next()) {
SubzoneRangeIterator iterator(region->subzone_range());
while (Subzone *subzone = iterator.next()) {
usword_t n = subzone->allocation_count();
for (usword_t q = 0; q < n; q = subzone->next_quantum(q)) {
if (!subzone->is_free(q)) {
visitor(zone, subzone, q);
}
}
}
}
for (Large *large = zone->large_list(); large != NULL; large = large->next()) {
visitor(zone, large);
}
}
#pragma mark class forwarding_phase
struct forwarding_phase {
size_t _objectsMoved, _bytesMoved;
size_t _pagesCompacted;
void *_currentPage;
bool _currentPagePinned;
bool _pinnedPagesOnly;
forwarding_phase() : _objectsMoved(0), _bytesMoved(0), _pagesCompacted(0), _currentPage(NULL), _currentPagePinned(false), _pinnedPagesOnly(false) {}
void setPinnedPagesOnly(bool pinnedPagesOnly) { _pinnedPagesOnly = pinnedPagesOnly; }
bool is_page_pinned(Subzone *subzone, void *block_page) {
Range page_range(block_page, page_size);
void *q_zero_address = subzone->quantum_address(0);
if (page_range.in_range(q_zero_address) && q_zero_address > block_page) return true;
usword_t q_page = subzone->quantum_index(block_page);
usword_t q_prev = subzone->previous_quantum(q_page);
if (q_prev != not_found && !subzone->is_free(q_prev)) {
Range r(subzone->quantum_address(q_prev), subzone->quantum_size(q_prev));
if (r.in_range(block_page) && subzone->is_pinned(q_prev)) return true;
}
usword_t n = subzone->allocation_limit();
usword_t q_start = q_prev != not_found ? subzone->next_quantum(q_prev) : q_page;
for (usword_t q = q_start; q < n && page_range.in_range(subzone->quantum_address(q)); q = subzone->next_quantum(q)) {
if (subzone->is_start(q) && !subzone->is_free(q) && subzone->is_pinned(q)) return true;
}
return false;
}
inline void forward_block(Zone *zone, Subzone *subzone, usword_t q, void *block) {
if (subzone->layout(q) & AUTO_OBJECT) {
if (zone->layout_map_for_block(block) == NULL) return;
}
void *newBlock = zone->forward_block(subzone, q, block);
if (newBlock != block) {
++_objectsMoved;
_bytesMoved += subzone->quantum_size(q);
}
}
inline void operator() (Zone *zone, Subzone *subzone, usword_t q) {
if (_pinnedPagesOnly) {
void *block = subzone->quantum_address(q);
void *block_page = align_down(block);
if (block_page != _currentPage) {
_currentPage = block_page;
_currentPagePinned = is_page_pinned(subzone, block_page);
if (!_currentPagePinned) ++_pagesCompacted;
}
if (!_currentPagePinned && subzone->is_compactable(q)) {
forward_block(zone, subzone, q, block);
}
} else if (subzone->is_compactable(q)) {
if (!subzone->is_forwarded(q))
forward_block(zone, subzone, q, subzone->quantum_address(q));
}
}
size_t objectsMoved() { return _objectsMoved; }
size_t pagesCompacted() { return _pagesCompacted; }
};
#pragma mark class fixup_phase
struct fixup_phase {
struct Configuration;
typedef ReferenceIterator<Configuration> FixupReferenceIterator;
class CompactionScanningStrategy : public FullScanningStrategy<FixupReferenceIterator> {
public:
inline static const unsigned char *layout_map_for_block(Zone *zone, void *block) {
if (zone->in_subzone_memory(block)) {
Subzone *subzone = Subzone::subzone(block);
usword_t q = subzone->quantum_index_unchecked(block);
if (subzone->is_forwarded(q)) {
block = *(void **)block;
}
}
return zone->layout_map_for_block(block);
}
};
struct Configuration {
typedef fixup_phase ReferenceVisitor;
typedef EmptyPendingStack<FixupReferenceIterator> PendingStack;
typedef CompactionScanningStrategy ScanningStrategy;
};
Configuration::PendingStack _stack;
FixupReferenceIterator _scanner;
PtrSet _observers;
fixup_phase(Zone *zone) : _scanner(zone, *this, _stack, (void *)auto_get_sp()) {}
inline bool is_compacted_pointer(Zone *zone, void *address) {
if (zone->in_subzone_memory(address)) {
usword_t q;
Subzone *subzone = Subzone::subzone(address);
if (subzone->block_is_start(address, &q) && subzone->is_forwarded(q)) return true;
}
return false;
}
void check_slot_for_observations(void **slot) {
__block void *slot_block = NULL;
Zone *zone = _scanner.zone();
blockStartNoLockDo(zone, slot, ^(Subzone *slot_subzone, usword_t slot_q) {
slot_block = slot_subzone->quantum_address(slot_q);
},^(Large *slot_large) {
slot_block = slot_large->address();
});
if (slot_block) {
AssociationsHashMap &associations = zone->associations();
AssociationsHashMap::iterator i = associations.find(slot_block);
if (i != associations.end()) {
ObjectAssociationMap *refs = i->second;
ObjectAssociationMap::iterator j = refs->find(&CompactionObserverKey);
if (j != refs->end()) {
void *observer = j->second;
if (is_compacted_pointer(zone, observer)) {
j->second = observer = *(void **)observer;
}
_observers.insert(observer);
}
}
}
}
void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {
if (subzone->is_forwarded(q)) {
void *address = *slot;
if (address == CompactionWatchPoint) {
printf("fixing up a reference to CompactionWatchPoint = %p\n", CompactionWatchPoint);
}
*slot = *(void**)address;
check_slot_for_observations(slot);
}
}
void visit(const ReferenceInfo &info, void **slot, Large *large) {}
inline void operator() (Zone *zone, Subzone *subzone, usword_t q) {
usword_t layout = subzone->layout(q);
if ((layout & AUTO_UNSCANNED) == 0) {
if (layout & AUTO_OBJECT) {
_scanner.scan(subzone, q);
} else if (layout == AUTO_POINTERS_ONLY) {
ReferenceInfo all_pointers_info(kAllPointersHeapReference, &subzone->write_barrier());
_scanner.scan_range(all_pointers_info, Range(subzone->quantum_address(q), subzone->size(q)));
}
}
}
inline void operator() (Zone *zone, Large *large) {
usword_t layout = large->layout();
if ((layout & AUTO_UNSCANNED) == 0) {
if (layout & AUTO_OBJECT) {
_scanner.scan(large);
} else if (layout == AUTO_POINTERS_ONLY) {
ReferenceInfo all_pointers_info(kAllPointersHeapReference, &large->write_barrier());
_scanner.scan_range(all_pointers_info, Range(large->address(), large->size()));
}
}
}
inline bool operator() (Zone *zone, void *object, void *key, void *&value) {
void *address = value;
if (is_compacted_pointer(zone, address)) {
value = *(void **)address;
}
return true;
}
inline void operator() (Zone *zone, void **root) {
void *address = *root;
if (is_compacted_pointer(zone, address)) {
*root = *(void **)address;
}
}
inline void operator () (Zone *zone, weak_referrer_t &ref) {
void *referent = *ref.referrer;
ASSERTION(!is_compacted_pointer(zone, referent));
if (ref.block && is_compacted_pointer(zone, ref.block)) {
ref.block = (auto_weak_callback_block_t *)*(void **)ref.block;
}
}
};
#pragma mark class move_object_phase
struct move_object_phase {
inline void operator() (Zone *zone, Subzone *subzone, usword_t q) {
if (subzone->is_forwarded(q)) {
zone->move_block(subzone, q, subzone->quantum_address(q));
}
}
inline void operator() (Zone *zone, Large *large) {}
};
#pragma mark class deallocate_phase
struct relocation {
size_t _size;
void *_old_block;
void *_new_block;
relocation(size_t size, void *old_block, void *new_block) : _size(size), _old_block(old_block), _new_block(new_block) {}
};
typedef std::vector<relocation, CompactionZoneAllocator<relocation> > relocation_vector;
struct deallocate_phase {
size_t _objectsDeallocated;
relocation_vector &_logVector;
deallocate_phase(relocation_vector &logVector) : _objectsDeallocated(0), _logVector(logVector) {}
inline void operator() (Zone *zone, Subzone *subzone, usword_t q) {
if (subzone->is_forwarded(q)) {
++_objectsDeallocated;
void *block = subzone->quantum_address(q);
void *copied_block = ((void **)block)[0];
if (subzone->layout(q) & AUTO_OBJECT) {
if (Environment::log_compactions) printf("moved %p -> %p (%s)\n", block, copied_block, zone->name_for_object(copied_block));
} else {
if (Environment::log_compactions) printf("moved %p -> %p (%lu bytes)\n", block, copied_block, subzone->size(q));
}
if (_old_malloc_logger) _logVector.push_back(relocation(subzone->size(q), block, copied_block));
#if DEBUG
weak_enumerate_weak_references(zone, subzone->quantum_address(q), ^(const weak_referrer_t &ref) {
printf("slot = %p, *slot == %p\n", ref.referrer, *ref.referrer);
__builtin_trap();
});
#endif
subzone->admin()->deallocate_no_lock(subzone, q, block);
subzone->clear_forwarded(q);
}
}
inline void operator() (Zone *zone, Large *large) {}
size_t objectsDeallocated() { return _objectsDeallocated; }
};
void *Zone::forward_block(Subzone *subzone, usword_t q, void *block) {
void *forwarded_block = block;
if (subzone->is_forwarded(q)) {
forwarded_block = ((void **)block)[0];
} else {
usword_t size = subzone->size(q);
Admin *block_admin = subzone->admin();
forwarded_block = block_admin->allocate_destination_block_no_lock(subzone, q, block);
if (forwarded_block != block) {
if (subzone->is_scanned(q)) bzero(forwarded_block, size);
((void **)forwarded_block)[0] = ((void **)block)[0];
((void **)block)[0] = forwarded_block;
subzone->mark_forwarded(q);
AssociationsHashMap::iterator i = _associations.find(block);
if (i != _associations.end()) {
ObjectAssociationMap* refs = i->second;
_associations.erase(i);
_associations[forwarded_block] = refs;
}
PtrSizeHashMap::iterator h = _hashes.find(block);
if (h != _hashes.end()) {
size_t hashValue = h->second;
_hashes.erase(h);
_hashes[forwarded_block] = hashValue;
}
weak_transfer_weak_referents(this, block, forwarded_block);
}
}
return forwarded_block;
}
void Zone::move_block(Subzone *subzone, usword_t q, void *block) {
ASSERTION(subzone->is_forwarded(q));
void *copied_block = ((void **)block)[0];
ASSERTION(in_subzone_memory(copied_block));
usword_t size = subzone->size(q);
memmove(displace(copied_block, sizeof(void*)), displace(block, sizeof(void*)), size - sizeof(void*));
usword_t layout = subzone->layout(q);
if (is_scanned(layout)) {
if (subzone->write_barrier().range_has_marked_cards(block, size)) {
Subzone::subzone(copied_block)->write_barrier().mark_cards(copied_block, size);
}
}
if (layout & AUTO_OBJECT) {
const unsigned char *weak_map = weak_layout_map_for_block(copied_block);
if (weak_map != NULL) weak_transfer_weak_contents(this, (void **)block, (void **)copied_block, weak_map);
} else if (layout == AUTO_MEMORY_ALL_WEAK_POINTERS) {
weak_transfer_weak_contents_unscanned(this, (void **)block, (void **)copied_block, size, true);
}
Subzone *copied_subzone = Subzone::subzone(copied_block);
usword_t copied_q = copied_subzone->quantum_index_unchecked(copied_block);
copied_subzone->set_age(copied_q, subzone->age(q));
}
typedef void (^compaction_observer_t) (void);
inline void region_apply(Zone *zone, void (^block) (Region *region)) {
for (Region *region = zone->region_list(); region != NULL; region = region->next()) {
block(region);
}
}
void Zone::compact_heap() {
if (_compaction_disabled) return;
pthread_mutex_lock(&_compaction_lock);
if (_compaction_disabled) {
pthread_mutex_unlock(&_compaction_lock);
return;
}
CompactionZone compactionZone;
relocation_vector logVector;
pthread_mutex_lock(&_mark_bits_mutex);
pthread_rwlock_wrlock(&_associations_lock);
spin_lock(&_datasegments_lock);
spin_lock(&weak_refs_table_lock);
pthread_mutex_lock(&_roots_lock);
_partition.lock();
suspend_all_registered_threads();
region_apply(this, ^(Region *region) {
region->pinned().commit();
region->pinned().clear();
region->clear_marks();
});
if (!Environment::scramble_heap) sort_free_lists();
__block usword_t initial_purgeable_bytes = 0;
_partition.for_each(^(Admin &admin) {
initial_purgeable_bytes += admin.purgeable_free_space_no_lock();
});
__block size_t objectsPinned = 0;
mark_pinned_t marker = ^(void **slot, Subzone *subzone, usword_t q, ReferenceKind kind) {
if (!subzone->test_and_set_pinned(q)) ++objectsPinned;
};
CompactionClassifier classifier(this, marker);
classifier.scan((void *)auto_get_sp());
forwarding_phase forwarder;
forwarder.setPinnedPagesOnly(true);
visitAllocatedSubzoneBlocksInReverse(this, forwarder);
forwarder.setPinnedPagesOnly(false);
visitAllocatedSubzoneBlocksInReverse(this, forwarder);
fixup_phase fixer(this);
visitAllocatedBlocksForCompaction(this, fixer);
visitAssociationsNoLock(this, fixer);
__block fixup_phase &fixer_ref = fixer;
visitRootsNoLock(this, ^(void **root) { fixer_ref(this, root); return true; });
weak_enumerate_table_fixup(this, ^(weak_referrer_t &ref) { fixer_ref(this, ref); });
move_object_phase mover;
visitAllocatedBlocksForCompaction(this, mover);
deallocate_phase deallocator(logVector);
visitAllocatedBlocksForCompaction(this, deallocator);
ASSERTION(deallocator.objectsDeallocated() == forwarder.objectsMoved());
if (Environment::log_compactions) {
printf("pinned %ld objects.\n", objectsPinned);
size_t objectsMoved = forwarder.objectsMoved();
if (objectsMoved) printf("compacted %ld objects, %ld pages\n", objectsMoved, forwarder.pagesCompacted());
usword_t bytes_purged = _partition.purge_free_space_no_lock();
printf("purgeable before compaction %lu bytes (%lu pages).\n", initial_purgeable_bytes, initial_purgeable_bytes / page_size);
printf("purged %lu bytes (%lu pages)\n", bytes_purged, bytes_purged / page_size);
}
region_apply(this, ^(Region *region) {
region->pinned().uncommit();
});
reset_all_marks();
resume_all_registered_threads();
std::for_each(logVector.begin(), logVector.end(), ^(const relocation& r) {
_old_malloc_logger(MALLOC_LOG_TYPE_ALLOCATE | MALLOC_LOG_TYPE_DEALLOCATE | MALLOC_LOG_TYPE_HAS_ZONE, (uintptr_t)this, (uintptr_t)r._old_block, (uintptr_t)r._size, (uintptr_t)r._new_block, 0);
});
_partition.unlock();
pthread_mutex_unlock(&_roots_lock);
spin_unlock(&weak_refs_table_lock);
spin_unlock(&_datasegments_lock);
pthread_rwlock_unlock(&_associations_lock);
pthread_mutex_unlock(&_mark_bits_mutex);
pthread_mutex_unlock(&_compaction_lock);
}
void Zone::disable_compaction() {
if (!_compaction_disabled) {
Mutex compaction_lock(&_compaction_lock);
_compaction_disabled = true;
}
}
void Zone::set_in_compaction() {
Mutex mutex(&_registered_threads_mutex);
for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) {
if (thread->is_current_thread()) continue;
LockedBoolean &in_compaction = thread->in_compaction();
assert(in_compaction.state == false);
SpinLock lock(&in_compaction.lock);
in_compaction.state = true;
}
}
void Zone::compaction_barrier() {
pthread_mutex_lock(&_registered_threads_mutex);
for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) {
if (thread->is_current_thread()) continue;
LockedBoolean &needs_enlivening = thread->needs_enlivening();
spin_lock(&needs_enlivening.lock);
}
_enlivening_complete = true;
}
void Zone::clear_in_compaction() {
for (Thread *thread = _registered_threads; thread != NULL; thread = thread->next()) {
if (thread->is_current_thread()) continue;
LockedBoolean &in_compaction = thread->in_compaction();
assert(in_compaction.state == true);
SpinLock lock(&in_compaction.lock);
in_compaction.state = false;
}
pthread_mutex_unlock(&_registered_threads_mutex);
}
}