#pragma once
#ifndef __AUTO_SUBZONE__
#define __AUTO_SUBZONE__
#include "Admin.h"
#include "Definitions.h"
#include "Bitmap.h"
#include "FreeList.h"
#include "WriteBarrier.h"
#include "Region.h"
#import "auto_tester/auto_tester.h"
#include "auto_zone.h"
#include "auto_trace.h"
#include "auto_dtrace.h"
#include <cassert>
namespace Auto {
class Region;
class Thread;
class Subzone : public Preallocated {
private:
unsigned char _write_barrier_cards[subzone_write_barrier_max];
WriteBarrier _write_barrier;
usword_t _quantum_log2; Region *_region; Admin *_admin; Subzone *_nextSubzone; bool _is_purgeable; bool _is_purged; usword_t _quantum_bias; void *_allocation_address; usword_t _in_use; unsigned char * volatile _checking_counts; volatile int32_t _pending_count;
bool _is_being_scanned;
unsigned char _side_data[1];
enum {
start_bit_log2 = 7,
start_bit = 0x1 << start_bit_log2,
layout_log2 = 4,
layout_mask = 0x7 << layout_log2,
global_bit_log2 = 0,
global_bit = 0x1 << global_bit_log2,
garbage_bit_log2 = 2,
garbage_bit = 0x1 << garbage_bit_log2,
alloc_local_bit_log2 = 1,
alloc_local_bit = 0x1 << alloc_local_bit_log2,
scan_local_bit_log2 = 3,
scan_local_bit = 0x1 << scan_local_bit_log2,
refcount_log2 = 3,
refcount_bit = 0x1 << refcount_log2,
age_mask_log2 = 1,
age_mask = 0x3 << age_mask_log2,
youngest_age = 3,
eldest_age = 0,
quanta_size_mask = 0x7f, };
static inline bool is_youngest(unsigned char sd) { return ((sd & age_mask)>>age_mask_log2) == youngest_age; }
static inline bool is_eldest(unsigned char sd) { return ((sd & age_mask)>>age_mask_log2) == eldest_age; }
static inline usword_t subzone_side_data_max(usword_t quantum_log2) {
usword_t header_size = sizeof(Subzone) - sizeof(unsigned char);
usword_t bytes_per_quantum = (1LL << quantum_log2) + 1;
return (subzone_quantum - header_size + bytes_per_quantum - 1) / bytes_per_quantum;
}
static inline usword_t subzone_base_data_size(usword_t quantum_log2) {
return align2(sizeof(Subzone) - sizeof(unsigned char) + subzone_side_data_max(quantum_log2), quantum_log2);
}
static inline usword_t subzone_allocation_size(usword_t quantum_log2) {
return subzone_quantum - subzone_base_data_size(quantum_log2);
}
static inline usword_t subzone_allocation_limit(usword_t quantum_log2) {
return partition2(subzone_allocation_size(quantum_log2), quantum_log2);
}
public:
Subzone(Region *region, Admin *admin, usword_t quantum_log2, usword_t quantum_bias)
: _write_barrier(_write_barrier_cards, _write_barrier_cards, WriteBarrier::bytes_needed(subzone_quantum)),
_quantum_log2(quantum_log2), _region(region), _admin(admin), _nextSubzone(NULL), _is_purgeable(false), _is_purged(false),
_quantum_bias(quantum_bias), _allocation_address(NULL), _in_use(0), _pending_count(0), _is_being_scanned(false)
{
usword_t base_data_size = is_small() ?
subzone_base_data_size(allocate_quantum_small_log2) :
subzone_base_data_size(allocate_quantum_medium_log2);
_allocation_address = (void *)displace(this, base_data_size);
}
~Subzone();
inline uintptr_t pack(usword_t q) {
assert(q <= 65536);
assert(uintptr_t(this) == (uintptr_t(this) & ~0x1FFFF));
return (uintptr_t)this | q;
}
static Subzone *unpack(uintptr_t packed, usword_t &q) {
q = ((usword_t)packed & 0x1FFFF);
return (reinterpret_cast<Subzone *>(packed & ~0x1FFFF));
}
usword_t quantum_log2() const { return _quantum_log2; }
Region *region() const { return _region; }
Admin *admin() const { return _admin; }
Subzone *nextSubzone() const { return _nextSubzone; }
void setNextSubzone(Subzone *subzone) { _nextSubzone = subzone; }
bool is_purgeable() const { return _is_purgeable; }
void set_purgeable(bool purgeable) { _is_purgeable = purgeable; }
bool is_purged() const { return _is_purged; }
void set_purged(bool purged) { _is_purged = purged; }
Range purgeable_range() const {
usword_t unused = allocation_limit() - _in_use;
usword_t size = quantum_size(unused);
if (size >= page_size) {
void *address = quantum_address(_in_use);
return Range(align_up(address, page_size_log2), align_down(displace(address, size), page_size_log2));
} else {
return Range();
}
}
usword_t quantum_bias() const { return _quantum_bias; }
bool has_pending() const { return _pending_count != 0; }
int32_t add_pending_count(int32_t count) { return OSAtomicAdd32(count, &_pending_count); }
int32_t pending_count() const { return _pending_count; } bool is_being_scanned() const { return _is_being_scanned; }
void set_is_being_scanned(bool p) { _is_being_scanned = p; }
static inline Subzone *subzone(void *address) { return (Subzone *)((uintptr_t)address & ~mask(subzone_quantum_log2)); }
inline bool is_small() const { return _quantum_log2 == allocate_quantum_small_log2; }
inline bool is_medium() const { return _quantum_log2 == allocate_quantum_medium_log2; }
inline void *allocation_address() const { return _allocation_address; }
inline void *allocation_end() { return displace(this, subzone_quantum); }
inline usword_t base_data_size() const {
return is_small() ? subzone_base_data_size(allocate_quantum_small_log2):
subzone_base_data_size(allocate_quantum_medium_log2);
}
inline usword_t base_data_quantum_count(usword_t quantum_log2) const {
return subzone_base_data_size(quantum_log2) >> quantum_log2;
}
inline usword_t allocation_size() const {
return is_small() ? subzone_allocation_size(allocate_quantum_small_log2) :
subzone_allocation_size(allocate_quantum_medium_log2);
}
inline usword_t allocation_limit() const {
return is_small() ? subzone_allocation_limit(allocate_quantum_small_log2) :
subzone_allocation_limit(allocate_quantum_medium_log2);
}
inline usword_t quantum_index(void *address, usword_t quantum_log2) const {
ASSERTION(quantum_log2 == _quantum_log2);
usword_t result = (((uintptr_t)address & mask(subzone_quantum_log2)) >> quantum_log2) - base_data_quantum_count(quantum_log2);
#if DEBUG
if (result > allocation_limit()) { printf("bad quantum index\n"); __builtin_trap(); }
#endif
return result;
}
inline usword_t quantum_index(void *address) const {
return is_small() ? quantum_index(address, allocate_quantum_small_log2) :
quantum_index(address, allocate_quantum_medium_log2);
}
inline usword_t quantum_index_unchecked(void *address, usword_t quantum_log2) const {
ASSERTION(quantum_log2 == _quantum_log2);
return (((uintptr_t)address & mask(subzone_quantum_log2)) >> quantum_log2) - base_data_quantum_count(quantum_log2);
}
inline usword_t quantum_index_unchecked(void *address) const {
return is_small() ? quantum_index_unchecked(address, allocate_quantum_small_log2) :
quantum_index_unchecked(address, allocate_quantum_medium_log2);
}
inline usword_t allocation_count() const { return _in_use; }
inline void raise_allocation_count(usword_t q) { _in_use += q; }
inline void lower_allocation_count(usword_t q) { _in_use -= q; }
inline const usword_t quantum_count(const size_t size) const {
return partition2(size, _quantum_log2);
}
inline const usword_t quantum_size(const usword_t n) const { return n << _quantum_log2; }
inline void *quantum_address(const usword_t q) const { return displace(_allocation_address, quantum_size(q)); }
inline void quantum_range(const usword_t q, Range &range) const {
range.set_range(quantum_address(q), size(q));
}
inline bool is_free(usword_t q) const { return (_side_data[q] & ~start_bit) == 0; }
inline bool is_start(usword_t q) const { return (_side_data[q] & start_bit) != 0 && !is_free(q); }
inline bool block_is_start(usword_t q) const { return q < allocation_limit() && (_side_data[q] & start_bit) != 0 && !is_free(q); }
inline bool block_is_start(void *address, usword_t *q) const {
return (is_small() ? is_bit_aligned(address, allocate_quantum_small_log2) :
is_bit_aligned(address, allocate_quantum_medium_log2)) &&
block_is_start(*q = quantum_index_unchecked(address));
}
inline usword_t length(usword_t q) const {
usword_t result;
if (q == allocation_limit()-1 || (_side_data[q+1] & start_bit))
result = 1;
else {
result = _side_data[q+1] & quanta_size_mask;
}
return result;
}
inline usword_t size(usword_t q) const { return quantum_size(length(q)); }
inline bool is_new(usword_t q) const { ASSERTION(!is_thread_local(q)); return !is_eldest(_side_data[q]); }
inline bool is_newest(usword_t q) const { ASSERTION(!is_thread_local(q)); return is_youngest(_side_data[q]); }
inline usword_t age(usword_t q) const { ASSERTION(!is_thread_local(q)); return (_side_data[q] & age_mask) >> age_mask_log2; }
inline void set_age(usword_t q, usword_t age) {
ASSERTION(!is_thread_local(q));
unsigned char data = _side_data[q];
data &= ~age_mask;
data |= (age << age_mask_log2);
_side_data[q] = data;
}
inline usword_t sideData(void *address) const { return _side_data[quantum_index(address)]; }
inline void mature(usword_t q) {
if (!is_thread_local(q)) {
unsigned char data = _side_data[q];
unsigned char current = (data & age_mask) >> age_mask_log2;
if (current > eldest_age) {
data &= ~age_mask;
data |= ((current-1) << age_mask_log2);
_side_data[q] = data;
AUTO_PROBE(auto_probe_mature(quantum_address(q), current-1));
}
}
}
inline bool is_thread_local(usword_t q) const { return (_side_data[q] & (start_bit|alloc_local_bit|global_bit)) == (start_bit|alloc_local_bit); }
inline bool is_live_thread_local(usword_t q) const { return (_side_data[q] & (start_bit | alloc_local_bit | global_bit|garbage_bit)) == (start_bit|alloc_local_bit); }
#ifdef MEASURE_TLC_STATS
void update_block_escaped_stats();
#endif
inline void make_global(usword_t q) {
ASSERTION(is_live_thread_local(q));
unsigned char data = _side_data[q];
data &= ~(refcount_bit | age_mask);
data |= global_bit | (youngest_age << age_mask_log2);
_side_data[q] = data;
AUTO_PROBE(auto_probe_make_global(quantum_address(q), youngest_age));
GARBAGE_COLLECTION_AUTO_BLOCK_LOST_THREAD_LOCALITY(quantum_address(q), size(q));
#ifdef MEASURE_TLC_STATS
update_block_escaped_stats();
#endif
}
inline void mark_global_garbage(usword_t q) { _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit; }
inline bool is_garbage(usword_t q) const { return (_side_data[q] & (start_bit|garbage_bit|global_bit)) == (start_bit|garbage_bit); }
inline bool is_global_garbage(usword_t q) const { return !is_thread_local(q) && is_garbage(q); }
inline void mark_local_garbage(usword_t q) { ASSERTION(is_live_thread_local(q)); _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit | alloc_local_bit; }
inline bool is_local_garbage(usword_t q) const { return (_side_data[q] & (start_bit|garbage_bit|alloc_local_bit)) == (start_bit|garbage_bit|alloc_local_bit); }
inline bool is_marked(usword_t q) const { return q < allocation_limit() && _region->marks().bit(_quantum_bias + q); }
inline usword_t layout(usword_t q) const { return (_side_data[q] & layout_mask) >> layout_log2; }
inline bool is_scanned(usword_t q) const { return !(layout(q) & AUTO_UNSCANNED); }
inline bool has_refcount(usword_t q) const { return !is_live_thread_local(q) && (_side_data[q] & refcount_bit) != 0; }
inline void set_has_refcount(usword_t q) { ASSERTION(!is_live_thread_local(q)); _side_data[q] |= refcount_bit; }
inline void clear_has_refcount(usword_t q) { ASSERTION(!is_live_thread_local(q)); _side_data[q] &= ~refcount_bit; }
inline void set_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); if (is_scanned(q)) _side_data[q] |= scan_local_bit; }
inline void clear_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); _side_data[q] &= ~scan_local_bit; }
inline bool should_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); return (_side_data[q] & scan_local_bit); }
inline bool test_and_set_mark(usword_t q) { return _region->test_and_set_mark(_quantum_bias + q); }
inline bool test_and_set_pinned(usword_t q) { return _region->pinned().test_set_bit_atomic(_quantum_bias + q); }
inline void mark_pinned(usword_t q) { _region->pinned().set_bit_atomic(_quantum_bias + q); }
inline bool is_pinned(usword_t q) { return _region->pinned().bit(_quantum_bias + q); }
inline bool is_compactable(usword_t q) const {
usword_t biased_q = q + _quantum_bias;
return _region->marks().bit(biased_q) && !_region->pinned().bit(biased_q);
}
inline void mark_forwarded(usword_t q) { _region->pending().set_bit(_quantum_bias + q); }
inline void clear_forwarded(usword_t q) { _region->pending().clear_bit(_quantum_bias + q); }
inline bool is_forwarded(usword_t q) { return _region->pending().bit(_quantum_bias + q); }
inline bool test_and_clear_mark(usword_t q) { return _region->test_and_clear_mark(_quantum_bias + q); }
inline void set_layout(usword_t q, usword_t layout) {
unsigned d = _side_data[q];
d &= ~layout_mask;
d |= (layout << layout_log2);
_side_data[q] = d;
}
inline bool test_and_set_pending(usword_t q, bool adjust_pending_count) {
bool result = _region->pending().test_set_bit_atomic(_quantum_bias + q);
if (!result && adjust_pending_count) add_pending_count(1);
return result;
}
inline bool test_and_clear_pending(usword_t q) { return _region->pending().test_clear_bit_atomic(_quantum_bias + q); }
inline Bitmap::AtomicCursor pending_cursor() { return Bitmap::AtomicCursor(_region->pending(), _quantum_bias, allocation_limit()); }
inline bool is_used(usword_t q) const {
if (!is_free(q)) return true;
for (usword_t s = q; true; s--) {
if (is_start(s)) {
usword_t n = length(s);
return (q - s) < n;
}
if (!s) break;
}
return false;
}
inline usword_t next_quantum(usword_t q = 0) const {
usword_t nq;
if (is_start(q)) {
nq = q + length(q);
} else {
usword_t n = allocation_limit();
nq = q + 1;
while (nq < n && !is_start(nq)) ++nq;
}
ASSERTION(nq >= q);
return nq;
}
inline usword_t next_quantum(usword_t q, MemoryReader & reader) const {
return next_quantum(q);
}
inline usword_t previous_quantum(usword_t q) {
ASSERTION(q <= allocation_limit());
while (q--) {
if (is_start(q))
return q;
}
return not_found;
}
inline void * block_start(void *address, usword_t &startq) const {
usword_t q = quantum_index_unchecked(address), s = q;
if (q > allocation_limit()) return NULL;
do {
if (is_start(s)) {
usword_t n = length(s);
if ((q - s) < n) {
startq = s;
return quantum_address(s);
}
return NULL;
}
} while (s--);
return NULL;
}
inline void allocate(usword_t q, const usword_t n, const usword_t layout, const bool refcount_is_one, const bool is_local) {
ASSERTION(n <= maximum_quanta && n > 0);
unsigned char sd;
sd = start_bit
| (layout << layout_log2)
| (is_local ? alloc_local_bit : (global_bit | (youngest_age << age_mask_log2)))
| (refcount_is_one ? refcount_bit : 0);
_side_data[q] = sd;
if (n > 1) {
_side_data[q + 1] = n;
_side_data[q + n - 1] = n;
}
if (q+n < allocation_limit() && _side_data[q + n] == 0)
_side_data[q + n] |= start_bit;
}
inline void cache(usword_t q, const usword_t n) {
ASSERTION(n <= maximum_quanta && n > 0);
_side_data[q] = (start_bit | alloc_local_bit | (AUTO_MEMORY_UNSCANNED << layout_log2) | garbage_bit);
if (n > 1) {
_side_data[q + 1] = n;
_side_data[q + n - 1] = n;
}
if (q+n < allocation_limit() && _side_data[q + n] == 0)
_side_data[q + n] |= start_bit;
}
inline void deallocate(usword_t q, usword_t len) {
bool prev_quanta_allocated = (q > 0 ? (_side_data[q-1] != 0) : false);
_side_data[q] = prev_quanta_allocated ? start_bit : 0;
if (len > 1) {
_side_data[q+1] = 0;
_side_data[q+len-1] = 0;
}
if (q+len < allocation_limit()) {
if (_side_data[q+len] == start_bit)
_side_data[q+len] = 0;
}
}
inline void deallocate(usword_t q) { deallocate(q, length(q)); }
inline WriteBarrier& write_barrier() {
return _write_barrier;
}
inline uint32_t collection_checking_count(usword_t q) const {
unsigned char *counts = _checking_counts;
return counts ? counts[q] : 0;
}
inline void set_collection_checking_count(usword_t q, uint32_t count) {
if (_checking_counts == NULL && count != 0) {
void *tmp = auto_zone_allocate_object((auto_zone_t *)_admin->zone(), allocation_limit() * sizeof(unsigned char), AUTO_UNSCANNED, true, true);
if (!OSAtomicCompareAndSwapPtrBarrier(NULL, tmp, (void * volatile *)(void *)&_checking_counts))
auto_zone_release((auto_zone_t *)_admin->zone(), tmp);
}
unsigned char *counts = _checking_counts;
if (counts != NULL) {
counts[q] = count < 255 ? count : 255;
}
}
inline void reset_collection_checking() {
unsigned char *counts = _checking_counts;
if (OSAtomicCompareAndSwapPtrBarrier(counts, NULL, (void * volatile *)(void *)&_checking_counts))
auto_zone_release((auto_zone_t *)_admin->zone(), counts);
}
class PendingCountAccumulator {
Thread &_thread;
Subzone *_last_pended_subzone;
usword_t _pended_count;
public:
PendingCountAccumulator(Thread &thread);
~PendingCountAccumulator();
inline void flush_count() {
if (_last_pended_subzone && _pended_count) {
_last_pended_subzone->add_pending_count(_pended_count);
_pended_count = 0;
}
}
inline void pended_in_subzone(Subzone *sz) {
if (_last_pended_subzone != sz) {
if (_pended_count) {
flush_count();
}
_last_pended_subzone = sz;
}
_pended_count++;
}
};
};
class SubzoneRangeIterator : public Range {
public:
SubzoneRangeIterator(void *address, const usword_t size) : Range(address, size) {}
SubzoneRangeIterator(void *address, void *end) : Range(address, end) {}
SubzoneRangeIterator(Range range) : Range(range) {}
inline boolean_t iteration_complete() { return !(address() < end()); }
inline Subzone *next() {
if (address() < end()) {
Subzone *subzone = (Subzone *)address();
set_address(displace(subzone, subzone_quantum));
return subzone;
}
return NULL;
}
inline Subzone *previous() {
if (end() > address()) {
Subzone *prev = (Subzone *)displace(end(), -subzone_quantum);
set_end(prev);
return prev;
}
return NULL;
}
};
};
#endif // __AUTO_SUBZONE__