#pragma once
#ifndef __AUTO_SUBZONE__
#define __AUTO_SUBZONE__
#include "AutoAdmin.h"
#include "AutoDefs.h"
#include "AutoBitmap.h"
#include "AutoFreeList.h"
#include "AutoWriteBarrier.h"
#include "AutoRegion.h"
#import "auto_tester/auto_tester.h"
#include "auto_zone.h"
#include <cassert>
namespace Auto {
class Region;
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; usword_t _quantum_bias; void *_allocation_address; usword_t _in_use; unsigned char _side_data[1];
enum {
start_bit_log2 = 7,
start_bit = 0x1 << start_bit_log2,
layout_log2 = 5,
layout_mask = 0x3 << 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_mask = 0x3 << 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), _quantum_bias(quantum_bias), _allocation_address(NULL), _in_use(0)
{
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);
}
usword_t quantum_log2() const { return _quantum_log2; }
Region *region() const { return _region; }
Admin *admin() const { return _admin; }
usword_t quantum_bias() const { return _quantum_bias; }
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 {
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 {
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 void quantum_range(void *block, Range &range) const {
range.set_range(block, size(quantum_index(block)));
}
inline bool is_free(usword_t q) const { return (_side_data[q] & ~start_bit) == 0; }
inline bool is_free(void *address) const { return is_free(quantum_index(address)); }
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) const {
return (is_small() ? is_bit_aligned(address, allocate_quantum_small_log2) :
is_bit_aligned(address, allocate_quantum_medium_log2)) &&
block_is_start(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 {
ASSERTION(_side_data[q + 1] != 0);
result = _side_data[q+1] & quanta_size_mask;
}
return result;
}
inline usword_t length(void *address) const { return length(quantum_index(address)); }
inline usword_t size(usword_t q) const { return quantum_size(length(q)); }
inline usword_t size(void *address) const { return size(quantum_index(address)); }
inline bool is_new(usword_t q) const { return q < allocation_limit() && !is_eldest(_side_data[q]); }
inline bool is_new(void *address) const { return is_new(quantum_index(address)); }
inline bool is_newest(usword_t q) const { return is_youngest(_side_data[q]); }
inline bool is_newest(void *address) const { return is_newest(quantum_index(address)); }
inline usword_t age(usword_t q) const { return (_side_data[q] & age_mask) >> age_mask_log2; }
inline usword_t age(void *address) const { return age(quantum_index(address)); }
inline usword_t refcount(usword_t q) const { return (is_live_thread_local(q)) ? 0 : (_side_data[q] & refcount_mask) >> refcount_log2; }
inline usword_t refcount(void *address) const { return refcount(quantum_index(address)); }
inline usword_t sideData(void *address) const { return _side_data[quantum_index(address)]; }
inline void incr_refcount(usword_t q) {
unsigned char sd = _side_data[q];
unsigned char r = (sd & refcount_mask) >> refcount_log2;
sd &= ~refcount_mask;
_side_data[q] = sd | ((r+1)<<refcount_log2);
}
inline void decr_refcount(usword_t q) {
unsigned char sd = _side_data[q];
unsigned char r = (sd & refcount_mask) >> refcount_log2;
sd &= ~refcount_mask;
_side_data[q] = sd | ((r-1) << refcount_log2);
}
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 void mature(void *address) { mature(quantum_index(address)); }
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_thread_local(void *address) const { usword_t q = quantum_index(address); return is_start(q) && is_thread_local(q); }
inline bool is_thread_local_block(void *address) const { usword_t q = quantum_index_unchecked(address); return q < allocation_limit() && is_start(q) && is_thread_local(q); }
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); }
inline bool is_live_thread_local(void *address) const { return is_live_thread_local(quantum_index(address)); }
inline bool is_live_thread_local_block(void *address) const { usword_t q = quantum_index_unchecked(address); return q < allocation_limit() && is_start(q) &&is_live_thread_local(q); }
inline void make_global(usword_t q) {
assert(!is_garbage(q));
unsigned char data = _side_data[q];
data &= ~(refcount_mask | 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));
}
inline void make_global(void *address) { make_global(quantum_index(address));}
inline void mark_global_garbage(usword_t q) { ASSERTION(!is_thread_local(q)); _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit; }
inline void mark_global_garbage(void *address) { return mark_global_garbage(quantum_index(address)); }
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_garbage(void *address) const { return is_garbage(quantum_index(address)); }
inline void mark_local_garbage(usword_t q) { ASSERTION(is_thread_local(q)); _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit | alloc_local_bit; }
inline void mark_local_garbage(void *address) { return mark_local_garbage(quantum_index(address)); }
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->is_marked(_quantum_bias + q); }
inline bool is_marked(void *address) const { return is_marked(quantum_index(address)); }
inline usword_t layout(usword_t q) const { return (_side_data[q] & layout_mask) >> layout_log2; }
inline usword_t layout(void *address) const { return layout(quantum_index(address)); }
inline bool is_scanned(usword_t q) const { return !(layout(q) & AUTO_UNSCANNED); }
inline bool is_scanned(void *address) const { return is_scanned(quantum_index(address)); }
inline bool has_refcount(usword_t q) const { return !is_thread_local(q) && (_side_data[q] & refcount_mask) != 0; }
inline bool has_refcount(void *address) const { return has_refcount(quantum_index(address)); }
inline void set_mark(usword_t q) { _region->set_mark(_quantum_bias + q); }
inline void set_mark(void *address) { set_mark(quantum_index(address)); }
inline void clear_mark(usword_t q) { _region->clear_mark(_quantum_bias + q); }
inline void clear_mark(void *address) { clear_mark(quantum_index(address)); }
inline bool assert_thread_local(usword_t q) { return is_thread_local(q); }
inline void set_scan_local_block(usword_t q) { ASSERTION(!is_garbage(q)); if (is_scanned(q)) _side_data[q] |= scan_local_bit; }
inline void set_scan_local_block(void *address) { set_scan_local_block(quantum_index(address)); }
inline void clear_scan_local_block(usword_t q) { _side_data[q] &= ~scan_local_bit; }
inline void clear_scan_local_block(void *address) { clear_scan_local_block(quantum_index(address)); }
inline bool should_scan_local_block(usword_t q) { return assert_thread_local(q) && (_side_data[q] & scan_local_bit); }
inline bool should_scan_local_block(void *address) { return should_scan_local_block(quantum_index(address)); }
inline bool test_set_mark(usword_t q) { return _region->test_set_mark(_quantum_bias + q); }
inline bool test_set_mark(void *address) { return test_set_mark(quantum_index(address)); }
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 void set_layout(void *address, usword_t layout) { set_layout(quantum_index(address), layout); }
inline bool is_pending(usword_t q) const { return _region->is_pending(_quantum_bias + q); }
inline bool is_pending(void *address) const { return is_pending(quantum_index(address)); }
inline void set_pending(usword_t q) { _region->set_pending(_quantum_bias + q); }
inline void set_pending(void *address) { set_pending(quantum_index(address)); }
inline void clear_pending(usword_t q) { _region->clear_pending(_quantum_bias + q); }
inline void clear_pending(void *address) { clear_pending(quantum_index(address)); }
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 bool is_used(void *address) const { return is_used(quantum_index(address)); }
bool should_pend(void *address, usword_t q) {
unsigned char *sdq;
if (is_small()) {
if (!is_bit_aligned(address, allocate_quantum_small_log2)) return false;
sdq = _side_data + q;
if (q >= subzone_allocation_limit(allocate_quantum_small_log2)) return false;
} else {
if (!is_bit_aligned(address, allocate_quantum_medium_log2)) return false;
sdq = _side_data + q;
if (q >= subzone_allocation_limit(allocate_quantum_medium_log2)) return false;
}
usword_t sd = *sdq;
if ((sd & start_bit) != start_bit) return false;
if (test_set_mark(q)) return false;
usword_t layout = (sd & layout_mask) >> layout_log2;
return !(layout & AUTO_UNSCANNED);
}
bool should_pend_new(void *address, usword_t q) {
unsigned char *sdq;
if (is_small()) {
if (!is_bit_aligned(address, allocate_quantum_small_log2)) return false;
sdq = _side_data + q;
if (q >= subzone_allocation_limit(allocate_quantum_small_log2)) return false;
} else {
if (!is_bit_aligned(address, allocate_quantum_medium_log2)) return false;
sdq = _side_data + q;
if (q >= subzone_allocation_limit(allocate_quantum_medium_log2)) return false;
}
usword_t sd = *sdq;
if ((sd & start_bit) != start_bit || is_eldest(sd)) return false;
if (test_set_mark(q)) return false;
usword_t layout = (sd & layout_mask) >> layout_log2;
return !(layout & AUTO_UNSCANNED);
}
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 void * block_start(void *address) 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);
return ((q - s) < n) ? quantum_address(s) : 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 ? (1 << refcount_log2) : 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;
}
void malloc_statistics(malloc_statistics_t *stats);
};
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 Subzone *next() {
if (address() < end()) {
Subzone *_next = (Subzone *)address();
set_address(displace(_next, subzone_quantum));
return _next;
}
return NULL;
}
};
};
#endif // __AUTO_SUBZONE__