#include "AutoAdmin.h"
#include "AutoBitmap.h"
#include "AutoConfiguration.h"
#include "AutoDefs.h"
#include "AutoZone.h"
#include "AutoLock.h"
#include <stdio.h>
#include <sys/mman.h>
namespace Auto {
void Admin::initialize(Zone *zone, const usword_t quantum_log2) {
_zone = zone;
_quantum_log2 = quantum_log2;
_active_subzone = NULL;
bzero(&_cache[0], sizeof(_cache));
_admin_lock = 0;
_freelist_search_cap = 0;
}
usword_t Admin::unused_count() {
return _active_subzone->allocation_limit() - _active_subzone->allocation_count();
}
usword_t Admin::free_space() {
SpinLock lock(&_admin_lock);
usword_t empty_space = 0;
for (usword_t m = 0; m < cache_size; m++) {
for (FreeListNode *node = _cache[m].head(); node != NULL; node = node->next()) {
empty_space += node->size();
}
}
return empty_space;
}
void Admin::purge_free_space() {
SpinLock lock(&_admin_lock);
const usword_t min_purgeable_size = 2 * Auto::page_size;
const usword_t quantum_size = (1 << _quantum_log2);
for (usword_t m = maximum_quanta, block_size = quantum_size * maximum_quanta; m > 0 && block_size > min_purgeable_size; --m, block_size -= quantum_size) {
for (FreeListNode *node = _cache[m].head(); node != NULL; node = node->next()) {
if (!node->purged()) {
Range r(node->purgeable_range());
if (r.size() >= min_purgeable_size) {
madvise(r.address(), r.size(), MADV_FREE);
}
node->set_purged(); }
}
}
for (FreeListNode *node = _cache[0].head(); node != NULL; node = node->next()) {
if (node->size() > min_purgeable_size && !node->purged()) {
Range r(node->purgeable_range());
if (r.size() >= min_purgeable_size) {
madvise(r.address(), r.size(), MADV_FREE);
}
node->set_purged(); }
}
}
usword_t Admin::empty_space() {
SpinLock lock(&_admin_lock);
usword_t empty_space = 0;
for (FreeListNode *node = _cache[0].head(); node != NULL; node = node->next()) {
empty_space += node->size();
}
return empty_space;
}
#if DEBUG
bool Admin::test_node_integrity(FreeListNode *node) {
bool node_is_valid = false;
const Range &coverage = _zone->coverage();
do {
if (!coverage.in_range(node)) break;
Subzone *subzone = Subzone::subzone((void *)node);
usword_t q = subzone->quantum_index(node->address());
if (q >= subzone->allocation_limit()) break;
if (subzone->quantum_address(q) != node->address()) break;
if (!subzone->is_free(q)) break;
FreeListNode *next = node->next();
if (next && !coverage.in_range(next)) break;
FreeListNode *prev = node->prev();
if (prev && !coverage.in_range(prev)) break;
if (node->size() != node->size_again()) break;
node_is_valid = true;
} while (0);
if (!node_is_valid) {
static char buffer[256];
if (coverage.in_range(node)) {
snprintf(buffer, sizeof(buffer), "test_node_integrity: FreeListNode %p { _prev = %p, _next = %p, _size = %lu } failed integrity check.\n",
node, node->prev(), node->next(), node->size());
} else {
snprintf(buffer, sizeof(buffer), "test_node_integrity: FreeListNode %p failed integrity check.\n", node);
}
__crashreporter_info__ = buffer;
malloc_printf("%s", buffer);
__builtin_trap();
}
return node_is_valid;
}
#else
bool Admin::test_node_integrity(FreeListNode *node) { return true; }
#endif
bool Admin::test_freelist_integrity() {
SpinLock lock(&_admin_lock);
for (usword_t m = 0; m < cache_size; m++) {
for (FreeListNode *node = _cache[m].head(), *prev_node = NULL; node; node = node->next()) {
Subzone *subzone = Subzone::subzone((void *)node);
usword_t q = subzone->quantum_index(node->address());
if (q >= subzone->allocation_limit()) return false;
if (subzone->quantum_address(q) != node->address()) return false;
if (subzone->is_used(q)) return false;
if (node->prev() != prev_node) return false;
if (node->size() != node->size_again()) return false;
prev_node = node;
}
}
return true;
}
inline FreeListNode *Admin::pop_node(usword_t index) {
FreeListNode *head = _cache[index].head();
return (head && test_node_integrity(head) ? _cache[index].pop() : NULL);
}
inline void Admin::push_node(usword_t index, void *address, usword_t size) {
_cache[index].push(address, size);
if (index > _freelist_search_cap || _freelist_search_cap == 0)
_freelist_search_cap = index;
}
void Admin::mark_allocated(void *address, const usword_t n, const unsigned layout, const bool refcount_is_one, const bool is_local) {
Subzone *subzone = Subzone::subzone(address);
*(void **)address = NULL;
subzone->allocate(subzone->quantum_index(address), n, layout, refcount_is_one, is_local);
}
void Admin::mark_cached(void *address, const usword_t n) {
Subzone *subzone = Subzone::subzone(address);
subzone->cache(subzone->quantum_index(address), n);
}
void Admin::mark_cached_range(void *address, usword_t n) {
Subzone *subzone = Subzone::subzone(address);
const usword_t maximum_block_size = maximum_quanta << _quantum_log2;
while (n >= maximum_quanta) {
subzone->cache(subzone->quantum_index(address), maximum_quanta);
address = displace(address, maximum_block_size);
n -= maximum_quanta;
}
if (n) subzone->cache(subzone->quantum_index(address), n);
}
inline void *Admin::find_allocation_no_lock(usword_t n, bool &did_grow) {
FreeListNode *node = pop_node(n);
if (node) {
return node->address();
}
if (Environment::guard_pages) {
if (_active_subzone == NULL) return NULL;
const usword_t quantum_size = (1 << _quantum_log2);
Subzone *subzone = _active_subzone;
usword_t first_quantum = subzone->allocation_count(), last_quantum = subzone->allocation_limit();
usword_t available_size = (last_quantum - first_quantum) * quantum_size;
void *slop_address = subzone->quantum_address(first_quantum);
void *guard_address = align_up(slop_address);
usword_t block_size = n << _quantum_log2;
usword_t slop_size = (uintptr_t)guard_address - (uintptr_t)slop_address;
while (block_size > slop_size) {
guard_address = displace(guard_address, page_size);
slop_size += page_size;
}
void *end_address = displace(guard_address, page_size);
usword_t total_size = (uintptr_t)end_address - (uintptr_t)slop_address;
if (available_size < total_size) {
set_active_subzone(NULL);
return NULL;
}
subzone->raise_allocation_count(total_size >> _quantum_log2);
usword_t slop_count = ((slop_size - block_size) >> _quantum_log2);
if (slop_count) mark_cached_range(slop_address, slop_count);
guard_page(guard_address);
mark_cached_range(guard_address, (page_size >> _quantum_log2));
usword_t remainder_size = available_size - total_size;
if (remainder_size < (2 * page_size)) {
set_active_subzone(NULL);
}
return displace(guard_address, -block_size);
}
void *address = NULL;
for (usword_t i = n + 1; node == NULL && i <= _freelist_search_cap; i++) {
node = pop_node(i);
}
if (!node) {
node = pop_node(0);
_freelist_search_cap = 0; }
if (node) {
address = node->address();
Subzone *subzone = Subzone::subzone(address);
usword_t allocation_size = subzone->quantum_size(n);
ASSERTION(node->size() >= allocation_size);
usword_t remainder_size = node->size() - allocation_size;
if (remainder_size) {
void *remainder_address = displace(address, allocation_size);
usword_t m = cache_slot(remainder_size);
push_node(m, remainder_address, remainder_size);
}
}
else if (_active_subzone) {
did_grow = true;
usword_t top = _active_subzone->allocation_count();
usword_t unused = _active_subzone->allocation_limit() - top;
ASSERTION(unused >= n);
address = _active_subzone->quantum_address(top);
*(void **)address = NULL;
_active_subzone->raise_allocation_count(n);
_zone->statistics().add_dirty(_active_subzone->quantum_size(n));
unused -= n;
if (unused == 0) {
set_active_subzone(NULL);
}
else if (unused < cache_size) {
push_node(unused, _active_subzone->quantum_address(top+n), _active_subzone->quantum_size(unused));
_active_subzone->raise_allocation_count(unused);
set_active_subzone(NULL);
}
}
else {
return NULL;
}
return address;
}
void *Admin::thread_cache_allocate(Thread &thread, usword_t &size, const unsigned layout, const bool refcount_is_one, bool &did_grow) {
usword_t n = partition2(size, allocate_quantum_small_log2);
FreeList &list = thread.allocation_cache(n);
if (!list.head()) {
SpinLock lock(&_admin_lock);
usword_t node_size = (n << allocate_quantum_small_log2);
EnliveningHelper<ConditionBarrier> barrier(thread);
for (int i = 0; i < cached_list_node_initial_count; ++i) {
void *node = find_allocation_no_lock(n, did_grow);
if (!node) break; mark_cached(node, n);
list.push(node, node_size);
if (barrier) barrier.enliven_block(node);
}
}
void *address = list.pop()->address();
if (!address) return NULL;
size = n << allocate_quantum_small_log2; if (refcount_is_one || !Environment::thread_collections) {
mark_allocated(address, n, layout, refcount_is_one, false);
}
else {
mark_allocated(address, n, layout, false, true);
thread.add_local_allocation(address);
}
return address;
}
void *Admin::find_allocation(Thread &thread, usword_t &size, const unsigned layout, const bool refcount_is_one, bool &did_grow) {
SpinLock lock(&_admin_lock);
usword_t n = quantum_count(size);
ASSERTION(n < cache_size);
void *address = find_allocation_no_lock(n, did_grow);
if (address) {
size = n << _quantum_log2;
EnliveningHelper<ConditionBarrier> barrier(thread);
mark_allocated(address, n, layout, refcount_is_one, false);
if (barrier) barrier.enliven_block(address);
}
return address;
}
void Admin::deallocate(void *address) {
SpinLock lock(&_admin_lock);
deallocate_no_lock(address);
}
void Admin::deallocate_no_lock(void *address) {
Subzone *subzone = Subzone::subzone(address);
usword_t q = subzone->quantum_index(address);
usword_t n = subzone->length(q);
ASSERTION(!subzone->is_free(q));
if (subzone->is_free(q)) {
malloc_printf("Admin::deallocate: attempting to free already freed block %p\n", address);
return;
}
void *free_address = address;
usword_t free_size = subzone->quantum_size(n);
Statistics &zone_stats = _zone->statistics();
zone_stats.add_count(-1);
zone_stats.add_size(-free_size);
usword_t next_q = q + n;
usword_t highwater = subzone->allocation_count();
if (!Environment::guard_pages) {
if (next_q < highwater && subzone->is_free(next_q)) {
FreeListNode *next_node = (FreeListNode *)displace(free_address, free_size);
if (test_node_integrity(next_node)) {
usword_t next_size = next_node->size();
usword_t m = cache_slot(next_size);
_cache[m].remove(next_node);
free_size += next_size;
}
}
if (q && subzone->is_free(q - 1)) {
FreeListNode *this_node = (FreeListNode *)address;
FreeListNode *prev_node = this_node->prior_node();
if (test_node_integrity(prev_node)) {
free_address = prev_node->address();
usword_t prev_size = prev_node->size();
free_size += prev_size;
usword_t m = cache_slot(prev_size);
_cache[m].remove(prev_node);
}
}
}
if (Environment::dirty_all_deleted) {
memset(free_address, 0x55, free_size);
}
if (next_q == highwater && highwater < subzone->allocation_limit()) {
subzone->lower_allocation_count(quantum_count(free_size));
_zone->statistics().add_dirty(-free_size); } else {
usword_t m = cache_slot(free_size);
push_node(m, free_address, free_size);
}
subzone->deallocate(q, n);
}
};