+ if (getenv("MallocErrorSleep")) {
+ malloc_printf("*** sleeping to help debug\n");
+ sleep(3600); // to help debug
+ }
+}
+#endif
+
+static void
+szone_error(szone_t *szone, const char *msg, const void *ptr)
+{
+
+ if (szone) SZONE_UNLOCK(szone);
+ if (ptr) {
+ malloc_printf("*** error for object %p: %s\n", ptr, msg);
+ } else {
+ malloc_printf("*** error: %s\n", msg);
+ }
+ malloc_printf("*** set a breakpoint in szone_error to debug\n");
+#if DEBUG_MALLOC
+ szone_print(szone, 1);
+ szone_sleep();
+#endif
+#if DEBUG_CLIENT
+ szone_sleep();
+#endif
+}
+
+static void
+protect(szone_t *szone, void *address, size_t size, unsigned protection, unsigned debug_flags)
+{
+ kern_return_t err;
+
+ if (!(debug_flags & SCALABLE_MALLOC_DONT_PROTECT_PRELUDE)) {
+ err = vm_protect(mach_task_self(), (vm_address_t)(uintptr_t)address - vm_page_size, vm_page_size, 0, protection);
+ if (err) {
+ malloc_printf("*** can't protect(%p) region for prelude guard page at %p\n",
+ protection,address - (1 << vm_page_shift));
+ }
+ }
+ if (!(debug_flags & SCALABLE_MALLOC_DONT_PROTECT_POSTLUDE)) {
+ err = vm_protect(mach_task_self(), (vm_address_t)(uintptr_t)address + size, vm_page_size, 0, protection);
+ if (err) {
+ malloc_printf("*** can't protect(%p) region for postlude guard page at %p\n",
+ protection, address + size);
+ }
+ }
+}
+
+static void *
+allocate_pages(szone_t *szone, size_t size, unsigned char align, unsigned debug_flags, int vm_page_label)
+{
+ // align specifies a desired alignment (as a log) or 0 if no alignment requested
+ kern_return_t err;
+ vm_address_t vm_addr;
+ uintptr_t addr, aligned_address;
+ boolean_t add_guard_pages = debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES;
+ size_t allocation_size = round_page(size);
+ size_t delta;
+
+ if (align) add_guard_pages = 0; // too cumbersome to deal with that
+ if (!allocation_size) allocation_size = 1 << vm_page_shift;
+ if (add_guard_pages) allocation_size += 2 * (1 << vm_page_shift);
+ if (align) allocation_size += (size_t)1 << align;
+ err = vm_allocate(mach_task_self(), &vm_addr, allocation_size, vm_page_label | 1);
+ if (err) {
+ malloc_printf("*** vm_allocate(size=%lld) failed (error code=%d)\n", (long long)size, err);
+ szone_error(szone, "can't allocate region", NULL);
+ return NULL;
+ }
+ addr = (uintptr_t)vm_addr;
+ if (align) {
+ aligned_address = (addr + ((uintptr_t)1 << align) - 1) & ~ (((uintptr_t)1 << align) - 1);
+ if (aligned_address != addr) {
+ delta = aligned_address - addr;
+ err = vm_deallocate(mach_task_self(), (vm_address_t)addr, delta);
+ if (err)
+ malloc_printf("*** freeing unaligned header failed with %d\n", err);
+ addr = aligned_address;
+ allocation_size -= delta;
+ }
+ if (allocation_size > size) {
+ err = vm_deallocate(mach_task_self(), (vm_address_t)addr + size, allocation_size - size);
+ if (err)
+ malloc_printf("*** freeing unaligned footer failed with %d\n", err);
+ }
+ }
+ if (add_guard_pages) {
+ addr += (uintptr_t)1 << vm_page_shift;
+ protect(szone, (void *)addr, size, 0, debug_flags);
+ }
+ return (void *)addr;
+}
+
+static void
+deallocate_pages(szone_t *szone, void *addr, size_t size, unsigned debug_flags)
+{
+ kern_return_t err;
+ boolean_t add_guard_pages = debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES;
+
+ if (add_guard_pages) {
+ addr -= 1 << vm_page_shift;
+ size += 2 * (1 << vm_page_shift);
+ }
+ err = vm_deallocate(mach_task_self(), (vm_address_t)addr, size);
+ if (err && szone)
+ szone_error(szone, "Can't deallocate_pages region", addr);
+}
+
+static kern_return_t
+_szone_default_reader(task_t task, vm_address_t address, vm_size_t size, void **ptr)
+{
+ *ptr = (void *)address;
+ return 0;
+}
+
+static INLINE void
+free_list_checksum(szone_t *szone, free_list_t *ptr, const char *msg)
+{
+ // We always checksum, as testing whether to do it (based on szone->debug_flags) is as fast as
+ // doing it
+ // XXX not necessarily true for LP64 case
+ if (ptr->checksum != (((uintptr_t)ptr->previous) ^ ((uintptr_t)ptr->next) ^ CHECKSUM_MAGIC)) {
+#if DEBUG_MALLOC
+ malloc_printf("*** incorrect checksum: %s\n", msg);
+#endif
+ szone_error(szone, "incorrect checksum for freed object "
+ "- object was probably modified after being freed, break at szone_error to debug", ptr);
+ }
+}
+
+static INLINE void
+free_list_set_checksum(szone_t *szone, free_list_t *ptr)
+{
+ // We always set checksum, as testing whether to do it (based on
+ // szone->debug_flags) is slower than just doing it
+ // XXX not necessarily true for LP64 case
+ ptr->checksum = ((uintptr_t)ptr->previous) ^ ((uintptr_t)ptr->next) ^ CHECKSUM_MAGIC;
+}
+
+static unsigned
+free_list_count(const free_list_t *ptr)
+{
+ unsigned count = 0;
+
+ while (ptr) {
+ count++;
+ ptr = ptr->next;
+ }
+ return count;
+}
+
+/* XXX inconsistent use of BITMAP32 and BITARRAY operations could be cleaned up */
+
+#define BITMAP32_SET(bitmap,bit) (bitmap |= 1 << (bit))
+#define BITMAP32_CLR(bitmap,bit) (bitmap &= ~ (1 << (bit)))
+#define BITMAP32_BIT(bitmap,bit) ((bitmap >> (bit)) & 1)
+
+#define BITMAP32_FFS(bitmap) (ffs(bitmap))
+ // returns bit # of first bit that's one, starting at 1 (returns 0 if !bitmap)
+
+/********************* TINY FREE LIST UTILITIES ************************/
+
+// We encode the meta-headers as follows:
+// Each quantum has an associated set of 2 bits:
+// block_header when 1 says this block is the beginning of a block
+// in_use when 1 says this block is in use
+// so a block in use of size 3 is 1-1 0-X 0-X
+// for a free block TINY_FREE_SIZE(ptr) carries the size and the bits are 1-0 X-X X-X
+// for a block middle the bits are 0-0
+
+// Attention double evaluation for these
+#define BITARRAY_SET(bits,index) (bits[index>>3] |= (1 << (index & 7)))
+#define BITARRAY_CLR(bits,index) (bits[index>>3] &= ~(1 << (index & 7)))
+#define BITARRAY_BIT(bits,index) (((bits[index>>3]) >> (index & 7)) & 1)
+
+// Following is for start<8 and end<=start+32
+#define BITARRAY_MCLR_LESS_32(bits,start,end) \
+do { \
+ unsigned char *_bits = (bits); \
+ unsigned _end = (end); \
+ switch (_end >> 3) { \
+ case 4: _bits[4] &= ~ ((1 << (_end - 32)) - 1); _end = 32; \
+ case 3: _bits[3] &= ~ ((1 << (_end - 24)) - 1); _end = 24; \
+ case 2: _bits[2] &= ~ ((1 << (_end - 16)) - 1); _end = 16; \
+ case 1: _bits[1] &= ~ ((1 << (_end - 8)) - 1); _end = 8; \
+ case 0: _bits[0] &= ~ ((1 << _end) - (1 << (start))); \
+ } \
+} while (0)
+
+#if 0 // Simple but slow version
+#warning Slow version in effect
+#define BITARRAY_MCLR(bits,index,num) \
+do { \
+ unsigned _ctr = (num); \
+ unsigned _cur = (index); \
+ \
+ while (_ctr--) {BITARRAY_CLR(bits,_cur); _cur++; } \
+} while (0)
+#else
+
+// Following is for num <= 32
+#define BITARRAY_MCLR(bits,index,num) \
+do { \
+ unsigned _index = (index); \
+ unsigned char *_rebased = (bits) + (_index >> 3); \
+ \
+ _index &= 7; \
+ BITARRAY_MCLR_LESS_32(_rebased, _index, _index + (num)); \
+} while (0)
+#endif
+
+static INLINE msize_t
+get_tiny_meta_header(const void *ptr, boolean_t *is_free)
+{
+ // returns msize and is_free
+ // may return 0 for the msize component (meaning 65536)
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+ unsigned byte_index;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ index = TINY_INDEX_FOR_PTR(ptr);
+ byte_index = index >> 3;
+
+ block_header += byte_index;
+ index &= 7;
+ *is_free = 0;
+ if (!BITMAP32_BIT(*block_header, index))
+ return 0;
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ if (!BITMAP32_BIT(*in_use, index)) {
+ *is_free = 1;
+ return TINY_FREE_SIZE(ptr);
+ }
+ uint32_t *addr = (uint32_t *)((uintptr_t)block_header & ~3);
+ uint32_t word0 = OSReadLittleInt32(addr, 0) >> index;
+ uint32_t word1 = OSReadLittleInt32(addr, 4) << (8 - index);
+ uint32_t bits = (((uintptr_t)block_header & 3) * 8); // precision loss on LP64 OK here
+ uint32_t word = (word0 >> bits) | (word1 << (24 - bits));
+ uint32_t result = ffs(word >> 1);
+ return result;
+}
+
+static INLINE void
+set_tiny_meta_header_in_use(const void *ptr, msize_t msize)
+{
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+ unsigned byte_index;
+ msize_t clr_msize;
+ unsigned end_bit;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ index = TINY_INDEX_FOR_PTR(ptr);
+ byte_index = index >> 3;
+
+#if DEBUG_MALLOC
+ if (msize >= 32)
+ malloc_printf("set_tiny_meta_header_in_use() invariant broken %p %d\n", ptr, msize);
+ if ((unsigned)index + (unsigned)msize > 0x10000)
+ malloc_printf("set_tiny_meta_header_in_use() invariant broken (2) %p %d\n", ptr, msize);
+#endif
+ block_header += byte_index;
+ index &= 7;
+ BITMAP32_SET(*block_header, index);
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ BITMAP32_SET(*in_use, index);
+ index++;
+ clr_msize = msize-1;
+ if (clr_msize) {
+ byte_index = index >> 3;
+ block_header += byte_index; in_use += byte_index;
+ index &= 7;
+ end_bit = index + clr_msize;
+ BITARRAY_MCLR_LESS_32(block_header, index, end_bit);
+ BITARRAY_MCLR_LESS_32(in_use, index, end_bit);
+ }
+ BITARRAY_SET(block_header, index+clr_msize); // we set the block_header bit for the following block to reaffirm next block is a block
+#if DEBUG_MALLOC
+ {
+ boolean_t ff;
+ msize_t mf;
+
+ mf = get_tiny_meta_header(ptr, &ff);
+ if (msize != mf) {
+ malloc_printf("setting header for tiny in_use %p : %d\n", ptr, msize);
+ malloc_printf("reading header for tiny %p : %d %d\n", ptr, mf, ff);
+ }
+ }
+#endif
+}
+
+static INLINE void
+set_tiny_meta_header_middle(const void *ptr)
+{
+ // indicates this block is in the middle of an in use block
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ index = TINY_INDEX_FOR_PTR(ptr);
+
+ BITARRAY_CLR(block_header, index);
+ BITARRAY_CLR(in_use, index);
+ TINY_FREE_SIZE(ptr) = 0;
+}
+
+static INLINE void
+set_tiny_meta_header_free(const void *ptr, msize_t msize)
+{
+ // !msize is acceptable and means 65536
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ index = TINY_INDEX_FOR_PTR(ptr);
+
+#if DEBUG_MALLOC
+ if ((unsigned)index + (unsigned)msize > 0x10000) {
+ malloc_printf("setting header for tiny free %p msize too large: %d\n", ptr, msize);
+ }
+#endif
+ BITARRAY_SET(block_header, index); BITARRAY_CLR(in_use, index);
+ TINY_FREE_SIZE(ptr) = msize;
+ // mark the end of this block
+ if (msize) { // msize==0 => the whole region is free
+ void *follower = FOLLOWING_TINY_PTR(ptr, msize);
+ TINY_PREVIOUS_MSIZE(follower) = msize;
+ }
+#if DEBUG_MALLOC
+ boolean_t ff;
+ msize_t mf = get_tiny_meta_header(ptr, &ff);
+ if ((msize != mf) || !ff) {
+ malloc_printf("setting header for tiny free %p : %d\n", ptr, msize);
+ malloc_printf("reading header for tiny %p : %d %d\n", ptr, mf, ff);
+ }
+#endif
+}
+
+static INLINE boolean_t
+tiny_meta_header_is_free(const void *ptr)
+{
+ // returns msize and is_free shifted by 16
+ // may return 0 for the msize component (meaning 65536)
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ index = TINY_INDEX_FOR_PTR(ptr);
+ if (!BITARRAY_BIT(block_header, index))
+ return 0;
+ return !BITARRAY_BIT(in_use, index);
+}
+
+static INLINE void *
+tiny_previous_preceding_free(void *ptr, msize_t *prev_msize)
+{
+ // returns the previous block, assuming and verifying it's free
+ unsigned char *block_header;
+ unsigned char *in_use;
+ msize_t index;
+ msize_t previous_msize;
+ msize_t previous_index;
+ void *previous_ptr;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ index = TINY_INDEX_FOR_PTR(ptr);
+
+ if (!index)
+ return NULL;
+ if ((previous_msize = TINY_PREVIOUS_MSIZE(ptr)) > index)
+ return NULL;
+
+ previous_index = index - previous_msize;
+ previous_ptr = (void *)(TINY_REGION_FOR_PTR(ptr) + TINY_BYTES_FOR_MSIZE(previous_index));
+ if (TINY_FREE_SIZE(previous_ptr) != previous_msize)
+ return NULL;
+
+ if (!BITARRAY_BIT(block_header, previous_index))
+ return NULL;
+ if (BITARRAY_BIT(in_use, previous_index))
+ return NULL;
+
+ // conservative check did match true check
+ *prev_msize = previous_msize;
+ return previous_ptr;
+}
+
+static INLINE void
+tiny_free_list_add_ptr(szone_t *szone, void *ptr, msize_t msize)
+{
+ // Adds an item to the proper free list
+ // Also marks the meta-header of the block properly
+ // Assumes szone has been locked
+ grain_t slot = (!msize || (msize >= NUM_TINY_SLOTS)) ? NUM_TINY_SLOTS - 1 : msize - 1;
+ free_list_t *free_ptr = ptr;
+ free_list_t *free_head = szone->tiny_free_list[slot];
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_free_list_add_ptr(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+ if (((unsigned)ptr) & (TINY_QUANTUM - 1)) {
+ szone_error(szone, "tiny_free_list_add_ptr: Unaligned ptr", ptr);
+ }
+#endif
+ set_tiny_meta_header_free(ptr, msize);
+ if (free_head) {
+ free_list_checksum(szone, free_head, __PRETTY_FUNCTION__);
+#if DEBUG_MALLOC
+ if (free_head->previous) {
+ malloc_printf("ptr=%p slot=%d free_head=%p previous=%p\n", ptr, slot, free_head, free_head->previous);
+ szone_error(szone, "tiny_free_list_add_ptr: Internal invariant broken (free_head->previous)", ptr);
+ }
+ if (! tiny_meta_header_is_free(free_head)) {
+ malloc_printf("ptr=%p slot=%d free_head=%p\n", ptr, slot, free_head);
+ szone_error(szone, "tiny_free_list_add_ptr: Internal invariant broken (free_head is not a free pointer)", ptr);
+ }
+#endif
+ free_head->previous = free_ptr;
+ free_list_set_checksum(szone, free_head);
+ } else {
+ BITMAP32_SET(szone->tiny_bitmap, slot);
+ }
+ free_ptr->previous = NULL;
+ free_ptr->next = free_head;
+ free_list_set_checksum(szone, free_ptr);
+ szone->tiny_free_list[slot] = free_ptr;
+}
+
+static INLINE void
+tiny_free_list_remove_ptr(szone_t *szone, void *ptr, msize_t msize)
+{
+ // Removes item in the proper free list
+ // msize could be read, but all callers have it so we pass it in
+ // Assumes szone has been locked
+ grain_t slot = (!msize || (msize >= NUM_TINY_SLOTS)) ? NUM_TINY_SLOTS - 1 : msize - 1;
+ free_list_t *free_ptr = ptr;
+ free_list_t *next = free_ptr->next;
+ free_list_t *previous = free_ptr->previous;
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("In tiny_free_list_remove_ptr(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+#endif
+ free_list_checksum(szone, free_ptr, __PRETTY_FUNCTION__);
+ if (!previous) {
+ // The block to remove is the head of the free list
+#if DEBUG_MALLOC
+ if (szone->tiny_free_list[slot] != ptr) {
+ malloc_printf("ptr=%p slot=%d msize=%d szone->tiny_free_list[slot]=%p\n",
+ ptr, slot, msize, szone->tiny_free_list[slot]);
+ szone_error(szone, "tiny_free_list_remove_ptr: Internal invariant broken (szone->tiny_free_list[slot])", ptr);
+ return;
+ }
+#endif
+ szone->tiny_free_list[slot] = next;
+ if (!next) BITMAP32_CLR(szone->tiny_bitmap, slot);
+ } else {
+ previous->next = next;
+ free_list_set_checksum(szone, previous);
+ }
+ if (next) {
+ next->previous = previous;
+ free_list_set_checksum(szone, next);
+ }
+}
+
+/*
+ * Find the tiny region containing (ptr) (if any).
+ *
+ * We take advantage of the knowledge that tiny regions are always (1 << TINY_BLOCKS_ALIGN) aligned.
+ */
+static INLINE tiny_region_t *
+tiny_region_for_ptr_no_lock(szone_t *szone, const void *ptr)
+{
+ tiny_region_t *region;
+ tiny_region_t rbase;
+ int i;
+
+ /* mask off irrelevant lower bits */
+ rbase = TINY_REGION_FOR_PTR(ptr);
+ /* iterate over allocated regions - XXX not terribly efficient for large number of regions */
+ for (i = szone->num_tiny_regions, region = szone->tiny_regions; i > 0; i--, region++)
+ if (rbase == *region)
+ return(region);
+ return(NULL);
+}
+
+static INLINE void
+tiny_free_no_lock(szone_t *szone, tiny_region_t *region, void *ptr, msize_t msize)
+{
+ size_t original_size = TINY_BYTES_FOR_MSIZE(msize);
+ void *next_block = ((char *)ptr + original_size);
+ msize_t previous_msize;
+ void *previous;
+ msize_t next_msize;
+ free_list_t *big_free_block;
+ free_list_t *after_next_block;
+ free_list_t *before_next_block;
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+ if (! msize) {
+ malloc_printf("in tiny_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ szone_error(szone, "trying to free tiny block that is too small", ptr);
+ }
+#endif
+ // We try to coalesce this block with the preceeding one
+ previous = tiny_previous_preceding_free(ptr, &previous_msize);
+ if (previous) {
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr) || LOG(szone,previous)) {
+ malloc_printf("in tiny_free_no_lock(), coalesced backwards for %p previous=%p\n", ptr, previous);
+ }
+#endif
+ tiny_free_list_remove_ptr(szone, previous, previous_msize);
+ ptr = previous;
+ msize += previous_msize;
+ }
+ // We try to coalesce with the next block
+ if ((next_block < TINY_REGION_END(*region)) && tiny_meta_header_is_free(next_block)) {
+ // The next block is free, we coalesce
+ next_msize = TINY_FREE_SIZE(next_block);
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr) || LOG(szone, next_block)) {
+ malloc_printf("in tiny_free_no_lock(), for ptr=%p, msize=%d coalesced forward=%p next_msize=%d\n",
+ ptr, msize, next_block, next_msize);
+ }
+#endif
+ if (next_msize >= NUM_TINY_SLOTS) {
+ // we take a short cut here to avoid removing next_block from the slot 31 freelist and then adding ptr back to slot 31
+ msize += next_msize;
+ big_free_block = (free_list_t *)next_block;
+ after_next_block = big_free_block->next;
+ before_next_block = big_free_block->previous;
+ free_list_checksum(szone, big_free_block, __PRETTY_FUNCTION__);
+ if (!before_next_block) {
+ szone->tiny_free_list[NUM_TINY_SLOTS-1] = ptr;
+ } else {
+ before_next_block->next = ptr;
+ free_list_set_checksum(szone, before_next_block);
+ }
+ if (after_next_block) {
+ after_next_block->previous = ptr;
+ free_list_set_checksum(szone, after_next_block);
+ }
+ ((free_list_t *)ptr)->previous = before_next_block;
+ ((free_list_t *)ptr)->next = after_next_block;
+ free_list_set_checksum(szone, ptr);
+ set_tiny_meta_header_free(ptr, msize);
+ set_tiny_meta_header_middle(big_free_block); // clear the meta_header to enable coalescing backwards
+ goto tiny_free_ending;
+ }
+ tiny_free_list_remove_ptr(szone, next_block, next_msize);
+ set_tiny_meta_header_middle(next_block); // clear the meta_header to enable coalescing backwards
+ msize += next_msize;
+ }
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) && msize) {
+ memset(ptr, 0x55, TINY_BYTES_FOR_MSIZE(msize));
+ }
+ tiny_free_list_add_ptr(szone, ptr, msize);
+ tiny_free_ending:
+ // When in proper debug mode we write on the memory to help debug memory smashers
+ szone->num_tiny_objects--;
+ szone->num_bytes_in_tiny_objects -= original_size; // we use original_size and not msize to avoid double counting the coalesced blocks
+}
+
+static void *
+tiny_malloc_from_region_no_lock(szone_t *szone, msize_t msize)
+{
+ tiny_region_t last_region, *new_regions;
+ void *last_block, *ptr, *aligned_address;
+
+ // Allocates from the last region or a freshly allocated region
+ // Before anything we transform the tiny_bytes_free_at_end - if any - to a regular free block
+ if (szone->tiny_bytes_free_at_end) {
+ last_region = szone->tiny_regions[szone->num_tiny_regions-1];
+ last_block = TINY_REGION_END(last_region) - szone->tiny_bytes_free_at_end;
+ tiny_free_list_add_ptr(szone, last_block, TINY_MSIZE_FOR_BYTES(szone->tiny_bytes_free_at_end));
+ szone->tiny_bytes_free_at_end = 0;
+ }
+ // time to create a new region
+ aligned_address = allocate_pages(szone, TINY_REGION_SIZE, TINY_BLOCKS_ALIGN, 0, VM_MAKE_TAG(VM_MEMORY_MALLOC_TINY));
+ if (!aligned_address) {
+ // out of memory!
+ return NULL;
+ }
+ // We set the padding after block_header to be all 1
+ ((uint32_t *)(aligned_address + (1 << TINY_BLOCKS_ALIGN) + (NUM_TINY_BLOCKS >> 3)))[0] = ~0;
+ if (szone->num_tiny_regions == INITIAL_NUM_TINY_REGIONS) {
+ // XXX logic here fails after initial reallocation of tiny regions is exhausted (approx 4GB of
+ // tiny allocations)
+ new_regions = small_malloc_from_region_no_lock(szone, 16); // 16 * 512 bytes is plenty of tiny regions (more than 4,000)
+ if (!new_regions) return NULL;
+ memcpy(new_regions, szone->tiny_regions, INITIAL_NUM_TINY_REGIONS * sizeof(tiny_region_t));
+ szone->tiny_regions = new_regions; // we set the pointer after it's all ready to enable enumeration from another thread without locking
+ }
+ szone->tiny_regions[szone->num_tiny_regions] = aligned_address;
+ szone->num_tiny_regions ++; // we set the number after the pointer is all ready to enable enumeration from another thread without taking the lock
+ ptr = aligned_address;
+ set_tiny_meta_header_in_use(ptr, msize);
+ szone->num_tiny_objects++;
+ szone->num_bytes_in_tiny_objects += TINY_BYTES_FOR_MSIZE(msize);
+ // We put a header on the last block so that it appears in use (for coalescing, etc...)
+ set_tiny_meta_header_in_use(ptr + TINY_BYTES_FOR_MSIZE(msize), 1);
+ szone->tiny_bytes_free_at_end = TINY_BYTES_FOR_MSIZE(NUM_TINY_BLOCKS - msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_malloc_from_region_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+#endif
+ return ptr;
+}
+
+static INLINE boolean_t
+try_realloc_tiny_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size)
+{
+ // returns 1 on success
+ msize_t index;
+ msize_t old_msize;
+ unsigned next_index;
+ void *next_block;
+ boolean_t is_free;
+ msize_t next_msize, coalesced_msize, leftover_msize;
+ void *leftover;
+
+ index = TINY_INDEX_FOR_PTR(ptr);
+ old_msize = TINY_MSIZE_FOR_BYTES(old_size);
+ next_index = index + old_msize;
+
+ if (next_index >= NUM_TINY_BLOCKS) {
+ return 0;
+ }
+ next_block = (char *)ptr + old_size;
+ SZONE_LOCK(szone);
+ is_free = tiny_meta_header_is_free(next_block);
+ if (!is_free) {
+ SZONE_UNLOCK(szone);
+ return 0; // next_block is in use;
+ }
+ next_msize = TINY_FREE_SIZE(next_block);
+ if (old_size + TINY_MSIZE_FOR_BYTES(next_msize) < new_size) {
+ SZONE_UNLOCK(szone);
+ return 0; // even with next block, not enough
+ }
+ tiny_free_list_remove_ptr(szone, next_block, next_msize);
+ set_tiny_meta_header_middle(next_block); // clear the meta_header to enable coalescing backwards
+ coalesced_msize = TINY_MSIZE_FOR_BYTES(new_size - old_size + TINY_QUANTUM - 1);
+ leftover_msize = next_msize - coalesced_msize;
+ if (leftover_msize) {
+ leftover = next_block + TINY_BYTES_FOR_MSIZE(coalesced_msize);
+ tiny_free_list_add_ptr(szone, leftover, leftover_msize);
+ }
+ set_tiny_meta_header_in_use(ptr, old_msize + coalesced_msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in try_realloc_tiny_in_place(), ptr=%p, msize=%d\n", ptr, old_msize + coalesced_msize);
+ }
+#endif
+ szone->num_bytes_in_tiny_objects += TINY_BYTES_FOR_MSIZE(coalesced_msize);
+ SZONE_UNLOCK(szone);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return 1;
+}
+
+static boolean_t
+tiny_check_region(szone_t *szone, tiny_region_t *region)
+{
+ uintptr_t start, ptr, region_end, follower;
+ boolean_t prev_free = 0;
+ boolean_t is_free;
+ msize_t msize;
+ free_list_t *free_head;
+
+ /* establish region limits */
+ start = (uintptr_t)TINY_REGION_ADDRESS(*region);
+ ptr = start;
+ region_end = (uintptr_t)TINY_REGION_END(*region);
+
+ /*
+ * The last region may have a trailing chunk which has not been converted into inuse/freelist
+ * blocks yet.
+ */
+ if (region == szone->tiny_regions + szone->num_tiny_regions - 1)
+ region_end -= szone->tiny_bytes_free_at_end;
+
+
+ /*
+ * Scan blocks within the region.
+ */
+ while (ptr < region_end) {
+ /*
+ * If the first block is free, and its size is 65536 (msize = 0) then the entire region is
+ * free.
+ */
+ msize = get_tiny_meta_header((void *)ptr, &is_free);
+ if (is_free && !msize && (ptr == start)) {
+ return 1;
+ }
+
+ /*
+ * If the block's size is 65536 (msize = 0) then since we're not the first entry the size is
+ * corrupt.
+ */
+ if (!msize) {
+ malloc_printf("*** invariant broken for tiny block %p this msize=%d - size is too small\n",
+ ptr, msize);
+ return 0;
+ }
+
+ if (!is_free) {
+ /*
+ * In use blocks cannot be more than 31 quanta large.
+ */
+ prev_free = 0;
+ if (msize > 31 * TINY_QUANTUM) {
+ malloc_printf("*** invariant broken for %p this tiny msize=%d[%p] - size is too large\n",
+ ptr, msize, msize);
+ return 0;
+ }
+ /* move to next block */
+ ptr += TINY_BYTES_FOR_MSIZE(msize);
+ } else {
+ /*
+ * Free blocks must have been coalesced, we cannot have a free block following another
+ * free block.
+ */
+ if (prev_free) {
+ malloc_printf("*** invariant broken for free block %p this tiny msize=%d: two free blocks in a row\n",
+ ptr, msize);
+ return 0;
+ }
+ prev_free = 1;
+ /*
+ * Check the integrity of this block's entry in its freelist.
+ */
+ free_head = (free_list_t *)ptr;
+ free_list_checksum(szone, free_head, __PRETTY_FUNCTION__);
+ if (free_head->previous && !tiny_meta_header_is_free(free_head->previous)) {
+ malloc_printf("*** invariant broken for %p (previous %p is not a free pointer)\n",
+ ptr, free_head->previous);
+ return 0;
+ }
+ if (free_head->next && !tiny_meta_header_is_free(free_head->next)) {
+ malloc_printf("*** invariant broken for %p (next in free list %p is not a free pointer)\n",
+ ptr, free_head->next);
+ return 0;
+ }
+ /*
+ * Check the free block's trailing size value.
+ */
+ follower = (uintptr_t)FOLLOWING_TINY_PTR(ptr, msize);
+ if ((follower != region_end) && (TINY_PREVIOUS_MSIZE(follower) != msize)) {
+ malloc_printf("*** invariant broken for tiny free %p followed by %p in region [%p-%p] "
+ "(end marker incorrect) should be %d; in fact %d\n",
+ ptr, follower, TINY_REGION_ADDRESS(*region), region_end, msize, TINY_PREVIOUS_MSIZE(follower));
+ return 0;
+ }
+ /* move to next block */
+ ptr = follower;
+ }
+ }
+ /*
+ * Ensure that we scanned the entire region
+ */
+ if (ptr != region_end) {
+ malloc_printf("*** invariant broken for region end %p - %p\n", ptr, region_end);
+ return 0;
+ }
+ /*
+ * Check the trailing block's integrity.
+ */
+ if (region == szone->tiny_regions + szone->num_tiny_regions - 1) {
+ if (szone->tiny_bytes_free_at_end) {
+ msize = get_tiny_meta_header((void *)ptr, &is_free);
+ if (is_free || (msize != 1)) {
+ malloc_printf("*** invariant broken for blocker block %p - %d %d\n", ptr, msize, is_free);
+ }
+ }
+ }
+ return 1;
+}
+
+static kern_return_t
+tiny_in_use_enumerator(task_t task, void *context, unsigned type_mask, vm_address_t region_address, unsigned short num_regions, size_t tiny_bytes_free_at_end, memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ tiny_region_t *regions;
+ unsigned index = 0;
+ vm_range_t buffer[MAX_RECORDER_BUFFER];
+ unsigned count = 0;
+ kern_return_t err;
+ tiny_region_t region;
+ vm_range_t range;
+ vm_range_t admin_range;
+ vm_range_t ptr_range;
+ unsigned char *mapped_region;
+ unsigned char *block_header;
+ unsigned char *in_use;
+ unsigned block_index;
+ unsigned block_limit;
+ boolean_t is_free;
+ msize_t msize;
+ void *mapped_ptr;
+ unsigned bit;
+
+ err = reader(task, region_address, sizeof(tiny_region_t) * num_regions, (void **)®ions);
+ if (err) return err;
+ while (index < num_regions) {
+ // unsigned num_in_use = 0;
+ // unsigned num_free = 0;
+ region = regions[index];
+ range.address = (vm_address_t)TINY_REGION_ADDRESS(region);
+ range.size = (vm_size_t)TINY_REGION_SIZE;
+ if (type_mask & MALLOC_ADMIN_REGION_RANGE_TYPE) {
+ admin_range.address = range.address + (1 << TINY_BLOCKS_ALIGN);
+ admin_range.size = range.size - (1 << TINY_BLOCKS_ALIGN);
+ recorder(task, context, MALLOC_ADMIN_REGION_RANGE_TYPE, &admin_range, 1);
+ }
+ if (type_mask & (MALLOC_PTR_REGION_RANGE_TYPE | MALLOC_ADMIN_REGION_RANGE_TYPE)) {
+ ptr_range.address = range.address;
+ ptr_range.size = 1 << TINY_BLOCKS_ALIGN;
+ recorder(task, context, MALLOC_PTR_REGION_RANGE_TYPE, &ptr_range, 1);
+ }
+ if (type_mask & MALLOC_PTR_IN_USE_RANGE_TYPE) {
+ err = reader(task, range.address, range.size, (void **)&mapped_region);
+ if (err)
+ return err;
+ block_header = (unsigned char *)(mapped_region + (1 << TINY_BLOCKS_ALIGN));
+ in_use = block_header + (NUM_TINY_BLOCKS >> 3) + 4;
+ block_index = 0;
+ block_limit = NUM_TINY_BLOCKS;
+ if (index == num_regions - 1)
+ block_limit -= TINY_MSIZE_FOR_BYTES(tiny_bytes_free_at_end);
+ while (block_index < block_limit) {
+ is_free = !BITARRAY_BIT(in_use, block_index);
+ if (is_free) {
+ mapped_ptr = mapped_region + TINY_BYTES_FOR_MSIZE(block_index);
+ msize = TINY_FREE_SIZE(mapped_ptr);
+ if (!msize)
+ break;
+ } else {
+ msize = 1;
+ bit = block_index + 1;
+ while (! BITARRAY_BIT(block_header, bit)) {
+ bit++;
+ msize ++;
+ }
+ buffer[count].address = range.address + TINY_BYTES_FOR_MSIZE(block_index);
+ buffer[count].size = TINY_BYTES_FOR_MSIZE(msize);
+ count++;
+ if (count >= MAX_RECORDER_BUFFER) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE, buffer, count);
+ count = 0;
+ }
+ }
+ block_index += msize;
+ }
+ }
+ index++;
+ }
+ if (count) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE, buffer, count);
+ }
+ return 0;
+}
+
+static INLINE void *
+tiny_malloc_from_free_list(szone_t *szone, msize_t msize)
+{
+ // Assumes we've locked the region
+ free_list_t *ptr;
+ msize_t this_msize;
+ grain_t slot = msize - 1;
+ free_list_t **free_list = szone->tiny_free_list;
+ free_list_t **the_slot = free_list + slot;
+ free_list_t *next;
+ free_list_t **limit;
+ unsigned bitmap;
+ msize_t leftover_msize;
+ free_list_t *leftover_ptr;
+
+ /*
+ * Look for an exact match by checking the freelist for this msize.
+ */
+ ptr = *the_slot;
+ if (ptr) {
+ next = ptr->next;
+ if (next) {
+ next->previous = NULL;
+ free_list_set_checksum(szone, next);
+ }
+ *the_slot = next;
+ this_msize = msize;
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), exact match ptr=%p, this_msize=%d\n", ptr, this_msize);
+ }
+#endif
+ goto return_tiny_alloc;
+ }
+
+ /*
+ * Iterate over freelists for larger blocks looking for the next-largest block.
+ */
+ bitmap = szone->tiny_bitmap & ~ ((1 << slot) - 1);
+ if (!bitmap)
+ goto try_tiny_malloc_from_end;
+ slot = BITMAP32_FFS(bitmap) - 1;
+ limit = free_list + NUM_TINY_SLOTS - 1;
+ free_list += slot;
+ while (free_list < limit) {
+ // try bigger grains
+ ptr = *free_list;
+ if (ptr) {
+ next = ptr->next;
+ if (next) {
+ next->previous = NULL;
+ free_list_set_checksum(szone, next);
+ }
+ *free_list = next;
+ this_msize = TINY_FREE_SIZE(ptr);
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), bigger grain ptr=%p, msize=%d this_msize=%d\n", ptr, msize, this_msize);
+ }
+#endif
+ goto add_leftover_and_proceed;
+ }
+ free_list++;
+ }
+ // we are now looking at the last slot (31)
+ ptr = *limit;
+ if (ptr) {
+ this_msize = TINY_FREE_SIZE(ptr);
+ next = ptr->next;
+ if (this_msize - msize >= NUM_TINY_SLOTS) {
+ // the leftover will go back to the free list, so we optimize by modifying the free list rather than removing the head and then adding back
+ leftover_msize = this_msize - msize;
+ leftover_ptr = (free_list_t *)((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
+ *limit = leftover_ptr;
+ if (next) {
+ next->previous = leftover_ptr;
+ free_list_set_checksum(szone, next);
+ }
+ leftover_ptr->next = next;
+ leftover_ptr->previous = NULL;
+ free_list_set_checksum(szone, leftover_ptr);
+ set_tiny_meta_header_free(leftover_ptr, leftover_msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), last slot ptr=%p, msize=%d this_msize=%d\n", ptr, msize, this_msize);
+ }
+#endif
+ this_msize = msize;
+ goto return_tiny_alloc;
+ }
+ *limit = next;
+ if (next) {
+ next->previous = NULL;
+ free_list_set_checksum(szone, next);
+ }
+ goto add_leftover_and_proceed;
+ }
+try_tiny_malloc_from_end:
+ // Let's see if we can use szone->tiny_bytes_free_at_end
+ if (szone->tiny_bytes_free_at_end >= TINY_BYTES_FOR_MSIZE(msize)) {
+ ptr = (free_list_t *)(TINY_REGION_END(szone->tiny_regions[szone->num_tiny_regions-1]) - szone->tiny_bytes_free_at_end);
+ szone->tiny_bytes_free_at_end -= TINY_BYTES_FOR_MSIZE(msize);
+ if (szone->tiny_bytes_free_at_end) {
+ // let's add an in use block after ptr to serve as boundary
+ set_tiny_meta_header_in_use((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize), 1);
+ }
+ this_msize = msize;
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), from end ptr=%p, msize=%d\n", ptr, msize);
+ }
+#endif
+ goto return_tiny_alloc;
+ }
+ return NULL;
+add_leftover_and_proceed:
+ if (!this_msize || (this_msize > msize)) {
+ leftover_msize = this_msize - msize;
+ leftover_ptr = (free_list_t *)((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), adding leftover ptr=%p, this_msize=%d\n", ptr, this_msize);
+ }
+#endif
+ tiny_free_list_add_ptr(szone, leftover_ptr, leftover_msize);
+ this_msize = msize;
+ }
+return_tiny_alloc:
+ szone->num_tiny_objects++;
+ szone->num_bytes_in_tiny_objects += TINY_BYTES_FOR_MSIZE(this_msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_malloc_from_free_list(), ptr=%p, this_msize=%d, msize=%d\n", ptr, this_msize, msize);
+ }
+#endif
+ set_tiny_meta_header_in_use(ptr, this_msize);
+ return ptr;
+}
projects / apple / libc.git / blobdiff