/* * Copyright (c) 2011 Apple Inc. All rights reserved. * * @APPLE_APACHE_LICENSE_HEADER_START@ * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * @APPLE_APACHE_LICENSE_HEADER_END@ */ /* Definitions.h Global Definitions Copyright (c) 2004-2011 Apple Inc. All rights reserved. */ #pragma once #ifndef __AUTO_DEFS__ #define __AUTO_DEFS__ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "Environment.h" #include "auto_impl_utilities.h" // // utilities and definitions used throughout the Auto namespace // #ifdef DEBUG extern "C" void* WatchPoint; #endif extern "C" malloc_zone_t *aux_zone; extern "C" const char *auto_prelude(void); extern "C" char *__crashreporter_info__; namespace Auto { // // auto_prelude // // Generate the prelude used for error reporting // inline const char *prelude(void) { return auto_prelude(); } #if defined(DEBUG) #define ASSERTION(expression) if(!(expression)) { \ malloc_printf("*** %s: Assertion %s %s.%d\n", prelude(), #expression, __FILE__, __LINE__); \ __builtin_trap(); \ } #else #define ASSERTION(expression) (void)(expression) #endif // // Workaround for declaration problems // typedef kern_return_t (*auto_memory_reader_t)(task_t remote_task, vm_address_t remote_address, vm_size_t size, void **local_memory); typedef void (*auto_vm_range_recorder_t)(task_t, void *, unsigned type, vm_range_t *, unsigned); typedef unsigned long usword_t; // computational word guaranteed to be unsigned // assumed to be either 32 or 64 bit typedef signed long sword_t; // computational word guaranteed to be signed // assumed to be either 32 or 64 bit inline usword_t auto_atomic_compare_and_swap(usword_t old_value, usword_t new_value, volatile usword_t *addr) { #if defined(__x86_64__) return OSAtomicCompareAndSwap64(old_value, new_value, (volatile int64_t *)addr); #elif defined(__i386__) return OSAtomicCompareAndSwap32(old_value, new_value, (volatile int32_t *)addr); #else #error unknown architecture #endif } inline usword_t auto_atomic_add(sword_t amount, volatile usword_t *addr) { usword_t old_value, new_value; do { old_value = *addr; new_value = old_value + amount; } while (!auto_atomic_compare_and_swap(old_value, new_value, addr)); return new_value; } // // Useful constants (descriptives for self commenting) // enum { page_size = 0x1000u, // vm_page_size but faster since we don't have to load global page_size_log2 = 12, // ilog2 of page_size bits_per_byte = 8, // standard bits per byte bits_per_byte_log2 = 3, // ilog2 of bits_per_byte is_64BitWord = sizeof(usword_t) == 8u, // true if 64-bit computational word is_32BitWord = sizeof(usword_t) == 4u, // true if 32-bit computational word bytes_per_word = is_64BitWord ? 8u : 4u, // number of bytes in an unsigned long word bytes_per_word_log2 = is_64BitWord ? 3u : 2u, // ilog2 of bytes_per_word bits_per_word = is_64BitWord ? 64u : 32u , // number of bits in an unsigned long word bits_per_word_log2 = is_64BitWord ? 6u : 5u, // ilog2 of bits_per_word bytes_per_quad = 16, // bytes in a quad word (vector) bytes_per_quad_log2 = 4, // ilog2 of bytes_per_quad bits_per_quad = 128, // bits in a quad word (vector) bits_per_quad_log2 = 7, // ilog2 of bits_per_quad bits_mask = (usword_t)(bits_per_word - 1), // mask to get the bit index (shift) in a word all_zeros = (usword_t)0, // a word of all 0 bits all_ones = ~all_zeros, // a word of all 1 bits not_found = all_ones, // a negative result of search methods pointer_alignment = is_64BitWord ? 3u : 2u, // bit alignment required for pointers block_alignment = is_64BitWord ? 5u : 4u, // bit alignment required for allocated blocks }; // // Useful functions // // // is_all_ones // // Returns true if the value 'x' contains all 1s. // inline const bool is_all_ones(usword_t x) { return !(~x); } // // is_all_zeros // // Returns true if the value 'x' contains all 0s. // inline const bool is_all_zeros(usword_t x) { return !x; } // // is_some_ones // // Returns true if the value 'x' contains some 1s. // inline const bool is_some_ones(usword_t x) { return x != 0; } // // is_some_zeros // // Returns true if the value 'x' contains some 0s. // inline const bool is_some_zeros(usword_t x) { return ~x != 0; } // // displace // // Adjust an address by specified number of bytes. // inline void *displace(void *address, const intptr_t offset) { return (void *)((char *)address + offset); } // // min // // Return the minumum of two usword_t values. // static inline const usword_t min(usword_t a, usword_t b) { return a < b ? a : b; } // // max // // Return the maximum of two usword_t values. // static inline const usword_t max(usword_t a, usword_t b) { return a > b ? a : b; } // // mask // // Generate a sequence of n one bits beginning with the least significant bit. // static inline const usword_t mask(usword_t n) { ASSERTION(0 < n && n <= bits_per_word); return (2L << (n - 1)) - 1; } // // is_power_of_2 // // Returns true if x is an exact power of 2. // static inline const bool is_power_of_2(usword_t x) { return ((x - 1) & x) == 0; } // // count_leading_zeros // // Count the number of leading zeroes // static inline const usword_t count_leading_zeros(register usword_t value) { #if __LP64__ return value ? __builtin_clzll(value) : bits_per_word; #else return value ? __builtin_clz(value) : bits_per_word; #endif } // // rotate_bits_left // // Rotates bits to the left 'n' bits // inline usword_t rotate_bits_left(usword_t value, usword_t n) { ASSERTION(0 < n && n < bits_per_word); return (value << n) | (value >> (bits_per_word - n)); } // // rotate_bits_right // // Rotates bits to the right 'n' bits // inline usword_t rotate_bits_right(usword_t value, usword_t n) { ASSERTION(0 < n && n < bits_per_word); return (value << (bits_per_word - n)) | (value >> n); } // // ilog2 // // Compute the integer log2 of x such that (x >> ilog2(x)) == 1, ilog2(0) == -1. // static inline const usword_t ilog2(register usword_t value) { return (bits_per_word - 1) - count_leading_zeros(value); } // // partition // // Determine the partition of 'x' in sets of size 'y'. // static inline const usword_t partition(usword_t x, usword_t y) { return (x + y - 1) / y; } // // partition2 // // Determine the partition of 'x' in sets of size 2^'y'. // static inline const usword_t partition2(usword_t x, usword_t y) { return (x + mask(y)) >> y; } // // align // // Align 'x' up to nearest multiple of alignment 'y'. // static inline const usword_t align(usword_t x, usword_t y) { return partition(x, y) * y; } // // align2 // // Align 'x' up to nearest multiple of alignment specified by 2^'y'. // static inline const usword_t align2(usword_t x, usword_t y) { usword_t m = mask(y); return (x + m) & ~m; } // // align_down // // Align and address down to nearest address where the 'n' bits are zero. // static inline void *align_down(void *address, usword_t n = page_size_log2) { usword_t m = mask(n); return (void *)((uintptr_t)address & ~m); } // // align_up // // Align and address up to nearest address where the 'n' bits are zero. // static inline void *align_up(void *address, usword_t n = page_size_log2) { usword_t m = mask(n); return (void *)(((uintptr_t)address + m) & ~m); } // // count_trailing_bits // // Count the number of trailing bits, that is, the number of bits following the leading zeroes. // Or, out by one ilog2. // static inline const usword_t count_trailing_bits(register usword_t value) { return bits_per_word - count_leading_zeros(value); } // // trailing_zeros // // Return a mask of ones for each consecutive zero starting at the least significant bit. // static inline const usword_t trailing_zeros(usword_t x) { return (x - 1) & ~ x; } // // trailing_ones // // Return a mask of ones for each consecutive one starting at the least significant bit. // static inline const usword_t trailing_ones(usword_t x) { return x & ~(x + 1); } // // count_trailing_zeros // // Return a count of consecutive zeros starting at the least significant bit. // static inline const usword_t count_trailing_zeros(usword_t x) { return count_trailing_bits(trailing_zeros(x)); } // // count_trailing_ones // // Return a count of consecutive ones starting at the least significant bit. // static inline const usword_t count_trailing_ones(usword_t x) { return count_trailing_bits(trailing_ones(x)); } // // is_bit_aligned // // Returns true if the specified address is aligned in a specific bit alignment. // inline bool is_bit_aligned(void *address, usword_t n) { return !((uintptr_t)address & mask(n)); } // // is_pointer_aligned // // Returns true if the specified address is aligned on a word boundary. // inline bool is_pointer_aligned(void *address) { return is_bit_aligned(address, pointer_alignment); } // // is_block_aligned // // Returns true if the specified address is aligned on a block boundary (16/32 bytes.) // inline bool is_block_aligned(void *address) { return is_bit_aligned(address, block_alignment); } // // is_equal // // String equality. // inline bool is_equal(const char *x, const char *y) { return strcmp(x, y) == 0; } // // error // // Report an error. // inline void error(const char *msg, const void *address = NULL) { if (address) malloc_printf("*** %s: agc error for object %p: %s\n", prelude(), address, msg); else malloc_printf("*** %s: agc error: %s\n", prelude(), msg); #if 0 && defined(DEBUG) __builtin_trap(); #endif } // // allocate_memory // // Allocate vm memory aligned to specified alignment. // inline void *allocate_memory(usword_t size, usword_t alignment = page_size, signed label = VM_MEMORY_MALLOC) { // start search at address zero vm_address_t address = 0; #if 0 switch (label) { default: case VM_MEMORY_MALLOC: label = VM_MEMORY_APPLICATION_SPECIFIC_1; break; // 240 admin case VM_MEMORY_MALLOC_SMALL: label = VM_MEMORY_APPLICATION_SPECIFIC_1 + 1; break; // 241 small/med case VM_MEMORY_MALLOC_LARGE: label = VM_MEMORY_APPLICATION_SPECIFIC_1 + 2; break; // 242 large } #endif // vm allocate space kern_return_t err = vm_map(mach_task_self(), &address, size, alignment - 1, VM_FLAGS_ANYWHERE | VM_MAKE_TAG(label), // first available space MACH_PORT_NULL, // NULL object, so dynamically allocated 0, // offset into object FALSE, // no need to copy the object VM_PROT_DEFAULT, // current protection VM_PROT_ALL, // maximum protection must be VM_PROT_ALL for madvise() to work. VM_INHERIT_DEFAULT); // standard copy-on-write at fork() // verify allocation if (err != KERN_SUCCESS) { malloc_printf("*** %s: Zone::Can not allocate 0x%lx bytes\n", prelude(), size); return NULL; } #if defined(DEBUG) if (Environment::print_allocs) malloc_printf("vm_map @%p %d\n", address, size); #endif // return result return (void *)address; } // // deallocate_memory // // Deallocate vm memory. // inline void deallocate_memory(void *address, usword_t size) { #if defined(DEBUG) if (Environment::print_allocs) malloc_printf("vm_deallocate @%p %d\n", address, size); #endif kern_return_t err = vm_deallocate(mach_task_self(), (vm_address_t)address, size); ASSERTION(err == KERN_SUCCESS); } // // copy_memory // // Copy vm pages. // inline void copy_memory(void *dest, void *source, usword_t size) { kern_return_t err = vm_copy(mach_task_self(), (vm_address_t)source, size, (vm_address_t)dest); ASSERTION(err == KERN_SUCCESS); } // // uncommit_memory // // Give memory back to the system. // void uncommit_memory(void *address, usword_t size); // // commit_memory // // Get uncommitted memory back from the system. // void commit_memory(void *address, usword_t size); // // guard_page // // Guards one page of memory from all access // inline void guard_page(void *address) { vm_protect(mach_task_self(), (vm_address_t)address, page_size, false, VM_PROT_NONE); } // // unguard_page // // Removes guard from page. // inline void unguard_page(void *address) { vm_protect(mach_task_self(), (vm_address_t)address, page_size, false, VM_PROT_DEFAULT); } // // allocate_guarded_memory // // Allocate vm memory bounded by guard pages at either end. // inline void *allocate_guarded_memory(usword_t size) { usword_t needed = align2(size, page_size_log2); // allocate two extra pages, one for either end void * allocation = allocate_memory(needed + 2 * page_size, page_size, VM_MEMORY_MALLOC); if (allocation) { // front guard guard_page(allocation); // rear guard guard_page(displace(allocation, page_size + needed)); // return allocation skipping front guard return displace(allocation, page_size); } // return NULL return allocation; } // // deallocate_guarded_memory // // Deallocate vm memory and surrounding guard pages. // inline void deallocate_guarded_memory(void *address, usword_t size) { usword_t needed = align2(size, page_size_log2); deallocate_memory(displace(address, -page_size), needed + 2 * page_size); } // // watchpoint // // Trap if the address matches the specified trigger. // inline void watchpoint(void *address) { #if DEBUG if (address == WatchPoint) __builtin_trap(); #endif } // // micro_time // // Returns execution time in microseconds (not real time.) // uint64_t micro_time(); // // MicroTimer // // Execution timer convenience class. // class MicroTimer { uint64_t _start, _stop; public: MicroTimer() : _start(0), _stop(0) {} void start() { _start = micro_time(); } void stop() { _stop = micro_time(); } uint64_t elapsed() { return _stop - _start; } }; // // nano_time // // Returns machine time in nanoseconds (rolls over rapidly.) // double nano_time(); // // NanoTimer // // Wall clock execution timer. // class NanoTimer { uint64_t _start, _stop; mach_timebase_info_data_t &_timebase; static mach_timebase_info_data_t &cached_timebase_info(); public: NanoTimer() : _start(0), _stop(0), _timebase(cached_timebase_info()) {} void start() { _start = mach_absolute_time(); } void stop() { _stop = mach_absolute_time(); } uint64_t elapsed() { return ((_stop - _start) * _timebase.numer) / _timebase.denom; } }; // // zone locks // extern "C" void auto_gc_lock(malloc_zone_t *zone); extern "C" void auto_gc_unlock(malloc_zone_t *zone); //----- MemoryReader -----// // // Used to read another task's memory. // class MemoryReader { task_t _task; // task being probed auto_memory_reader_t _reader; // reader used to laod task memory public: MemoryReader(task_t task, auto_memory_reader_t reader) : _task(task), _reader(reader) {} // // read // // Read memory from the task into current memory. // inline void *read(void *task_address, usword_t size) { void *local_address; // location where memory was read kern_return_t err = _reader(_task, (vm_address_t)task_address, (vm_size_t)size, &local_address); if (err) return NULL; return local_address; } }; //----- Preallocated -----// // // Used in classes where memory is presupplied. // class Preallocated { public: // prevent incorrect use of new void *operator new(size_t size) { error("Must use alternate form of new operator."); return aux_malloc(size); } // must supply an address void *operator new(size_t size, void *address) { return address; } // do not delete void operator delete(void *x) { } }; //----- AuxAllocated -----// // // Used in classes where memory needs to be allocated from aux malloc. // class AuxAllocated { public: // // allocator // inline void *operator new(const size_t size) { void *memory = aux_malloc(size); if (!memory) error("Failed of allocate memory for auto internal use."); return memory; } inline void *operator new(const size_t size, const size_t extra) { void *memory = aux_malloc(size+extra); if (!memory) error("Failed of allocate memory for auto internal use."); return memory; } // // deallocator // inline void operator delete(void *address) { if (address) aux_free(address); } }; //----- AuxAllocator -----// // // Support for STL allocation in aux malloc. // template struct AuxAllocator { 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 struct rebind { typedef AuxAllocator other; }; template AuxAllocator(const AuxAllocator&) {} AuxAllocator() {} AuxAllocator(const AuxAllocator&) {} ~AuxAllocator() {} 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(aux_calloc(n, sizeof(T))); } void deallocate(pointer p, size_type) { ::aux_free(p); } size_type max_size() const { return static_cast(-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 AuxAllocator&); }; template<> struct AuxAllocator { typedef void value_type; typedef void* pointer; typedef const void *const_pointer; template struct rebind { typedef AuxAllocator other; }; }; template inline bool operator==(const AuxAllocator&, const AuxAllocator&) { return true; } template inline bool operator!=(const AuxAllocator&, const AuxAllocator&) { return false; } struct AuxPointerLess { bool operator()(const void *p1, const void *p2) const { return p1 < p2; } }; struct AuxPointerEqual { bool operator()(void *p1, void *p2) const { return p1 == p2; } }; struct AuxPointerHash { uintptr_t operator()(void *p) const { return (uintptr_t)p; } }; typedef std::vector > PtrVector; typedef std::map > > PtrIntMap; typedef std::map > > PtrPtrMap; typedef __gnu_cxx::hash_map > PtrPtrHashMap; typedef __gnu_cxx::hash_map > PtrAssocHashMap; typedef __gnu_cxx::hash_map > PtrIntHashMap; typedef __gnu_cxx::hash_map > PtrSizeHashMap; typedef __gnu_cxx::hash_set > PtrHashSet; // // PointerArray // Stores a contiguous array of pointers, which is resized by amortized doubling. // Uses a MemoryAllocator template parameter which must implement the methods: // void *allocator_memory(size_t size); // void deallocator_memory(void *pointer, size_t size); // void uncommit_memory(void *pointer, size_t size); // void copy_memory(void *dest, void *source, size_t size); // template class PointerArray : AuxAllocated { usword_t _count; usword_t _capacity; void **_buffer; MemoryAllocator _allocator; public: PointerArray() : _count(0), _capacity(0), _buffer(NULL) {} PointerArray(MemoryAllocator allocator) : _count(0), _capacity(0), _buffer(NULL), _allocator(allocator) {} ~PointerArray() { if (_buffer) _allocator.deallocate_memory(_buffer, _capacity * sizeof(void *)); } usword_t count() const { return _count; } void clear_count() { _count = 0; } void set_count(usword_t n) { _count = n; } void **buffer() { return _buffer; } usword_t size() { return _capacity * sizeof(void*); } void uncommit() { if (_buffer) uncommit_memory(_buffer, _capacity * sizeof(void*)); } void commit() { if (_buffer) commit_memory(_buffer, _capacity * sizeof(void*)); } void grow() { if (!_buffer) { // start off with 1 page. _capacity = page_size / sizeof(void*); _buffer = (void **) _allocator.allocate_memory(page_size); } else { // double the capacity. vm_size_t old_size = _capacity * sizeof(void *); void **new_buffer = (void **) _allocator.allocate_memory(old_size * 2); if (!new_buffer) { auto_fatal("PointerArray::grow() _capacity=%lu failed.\n", _capacity * 2); } _capacity *= 2; _allocator.copy_memory(new_buffer, _buffer, old_size); _allocator.deallocate_memory(_buffer, old_size); _buffer = new_buffer; } } void grow(usword_t count) { if (count > _capacity) { usword_t old_size = _capacity * sizeof(void *); if (_capacity == 0L) _capacity = page_size / sizeof(void *); while (count > _capacity) _capacity *= 2; void **new_buffer = (void **) _allocator.allocate_memory(_capacity * sizeof(void*)); if (!new_buffer) { auto_fatal("PointerArray::grow(count=%lu) failed.\n", _capacity); } if (_buffer) { // only copy contents if _count != 0. if (new_buffer && _count) { _allocator.copy_memory(new_buffer, _buffer, old_size); } _allocator.deallocate_memory(_buffer, old_size); } _buffer = new_buffer; } } void add(void *pointer) { if (_count == _capacity) grow(); _buffer[_count++] = pointer; } }; // // PointerQueue // Manages a set of pointers as a queue of discontinguous page-sized chunks. This uses memory more efficiently // since it never has to copy the buffers themselves, and grows mores slowly than a PointerArray. Also parametrized // with a MemoryAllocator type. // struct PointerChunk : Preallocated { PointerChunk *_next; enum { chunk_size = (Auto::page_size / sizeof(void*)) - 1 }; void *_pointers[chunk_size]; void **pointers() { return _pointers; } void **limit() { return _pointers + chunk_size; } PointerChunk *next() { return _next; } }; template inline void visitPointerChunks(PointerChunk *chunks, usword_t count, Visitor& visitor) { PointerChunk *chunk = chunks; while (chunk != NULL) { PointerChunk *next = chunk->next(); void **pointers = chunk->pointers(); void **limit = pointers + (count > PointerChunk::chunk_size ? PointerChunk::chunk_size : count); visitor(pointers, limit); count -= (limit - pointers); chunk = next; } } template class PointerQueue : AuxAllocated { MemoryAllocator _allocator; PointerChunk *_head; PointerChunk *_tail; PointerChunk *_current; void **_cursor, **_limit; usword_t _count; void next_chunk() { if (_current == NULL) { // reset() pointed back to the beginning. _current = _head; } else { _current = _current->_next; } if (_current == NULL) { _current = (PointerChunk *)_allocator.allocate_memory(sizeof(PointerChunk)); if (_head == NULL) { _head = _tail = _current; } else { _tail->_next = _current; _tail = _current; } } _cursor = _current->pointers(); _limit = _current->limit(); } public: PointerQueue() : _head(NULL), _tail(NULL), _current(NULL), _cursor(NULL), _limit(NULL), _count(0) {} PointerQueue(MemoryAllocator allocator) : _allocator(allocator), _head(NULL), _tail(NULL), _current(NULL), _cursor(NULL), _limit(NULL), _count(0) {} ~PointerQueue() { PointerChunk *chunk = _head; while (chunk != NULL) { PointerChunk *next = chunk->_next; _allocator.deallocate_memory(chunk, sizeof(PointerChunk)); chunk = next; } } void add(void *pointer) { if (_cursor == _limit) next_chunk(); *_cursor++ = pointer; ++_count; } void reset() { _current = NULL; _cursor = _limit = NULL; _count = 0; } PointerChunk *chunks() { return _head; } usword_t count() { return _count; } usword_t size() { usword_t size = 0; PointerChunk *chunk = _head; while (chunk != NULL) { size += Auto::page_size; chunk = chunk->_next; } return size; } }; class VMMemoryAllocator { public: inline void *allocate_memory(usword_t size) { return Auto::allocate_memory(size); } inline void deallocate_memory(void *address, usword_t size) { Auto::deallocate_memory(address, size); } inline void uncommit_memory(void *address, usword_t size) { Auto::uncommit_memory(address, size); } inline void copy_memory(void *dest, void *source, usword_t size) { Auto::copy_memory(dest, source, size); } }; }; #endif // __AUTO_DEFS__