+/*
+ * Copyright (c) 1999, 2006, 2008 Apple Inc. All rights reserved.
+ *
+ * @APPLE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_LICENSE_HEADER_END@
+ */
+
+/* Author: Bertrand Serlet, August 1999 */
+
+/*
+ Multithread enhancements for "tiny" allocations introduced February 2008.
+ These are in the spirit of "Hoard". See:
+ Berger, E.D.; McKinley, K.S.; Blumofe, R.D.; Wilson, P.R. (2000).
+ "Hoard: a scalable memory allocator for multithreaded applications".
+ ACM SIGPLAN Notices 35 (11): 117-128. Berger2000.
+ <http://portal.acm.org/citation.cfm?id=356989.357000>
+ Retrieved on 2008-02-22.
+*/
+
+/* gcc -g -O3 magazine_malloc.c malloc.c -o libmagmalloc.dylib -I. \
+ -I/System/Library/Frameworks/System.framework/PrivateHeaders/ -funit-at-a-time \
+ -dynamiclib -Wall -arch x86_64 -arch i386 -arch ppc */
+
+#include "scalable_malloc.h"
+#include "malloc_printf.h"
+#include "_simple.h"
+#include "magmallocProvider.h"
+
+#include <pthread_internals.h> /* for pthread_lock_t SPI */
+#include <pthread.h> /* for pthread API */
+
+#include <stdint.h>
+#include <unistd.h>
+#include <mach/vm_statistics.h>
+#include <mach/mach_init.h>
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <sys/sysctl.h>
+#include <libkern/OSAtomic.h>
+#include <mach-o/dyld.h> /* for NSVersionOfLinkTimeLibrary() */
+
+/********************* DEFINITIONS ************************/
+
+#define DEBUG_MALLOC 0 // set to one to debug malloc itself
+
+#define DEBUG_CLIENT 0 // set to one to debug malloc client
+
+#if DEBUG_MALLOC
+#warning DEBUG_MALLOC ENABLED
+# define INLINE
+# define ALWAYSINLINE
+# define CHECK_MAGAZINE_PTR_LOCKED(szone, mag_ptr, fun) \
+do { \
+ if (__is_threaded && TRY_LOCK(mag_ptr->magazine_lock)) { \
+ malloc_printf("*** magazine_lock was not set %p in %s\n", \
+ mag_ptr->magazine_lock, fun); \
+ } \
+} while (0)
+#else
+# define INLINE __inline__
+# define ALWAYSINLINE __attribute__((always_inline))
+# define CHECK_MAGAZINE_PTR_LOCKED(szone, mag_ptr, fun) {}
+#endif
+
+# define NOINLINE __attribute__((noinline))
+
+#if defined(__i386__) || defined(__x86_64__)
+#define CACHE_ALIGN __attribute__ ((aligned (128) )) /* Future-proofing at 128B */
+#elif defined(__ppc__) || defined(__ppc64__)
+#define CACHE_ALIGN __attribute__ ((aligned (128) ))
+#else
+#define CACHE_ALIGN
+#endif
+
+/*
+ * Access to global variables is slow, so optimise our handling of vm_page_size
+ * and vm_page_shift.
+ */
+#define _vm_page_size vm_page_size /* to get to the originals */
+#define _vm_page_shift vm_page_shift
+#define vm_page_size 4096 /* our normal working sizes */
+#define vm_page_shift 12
+
+/*
+ * msize - a type to refer to the number of quanta of a tiny or small
+ * allocation. A tiny block with an msize of 3 would be 3 << SHIFT_TINY_QUANTUM
+ * bytes in size.
+ */
+typedef unsigned short msize_t;
+
+typedef union {
+ void *p;
+ uintptr_t u;
+} ptr_union;
+
+typedef struct {
+ ptr_union previous;
+ ptr_union next;
+} free_list_t;
+
+typedef unsigned int grain_t; // N.B. wide enough to index all free slots
+
+typedef int mag_index_t;
+
+#define CHECK_REGIONS (1 << 31)
+
+#define MAX_RECORDER_BUFFER 256
+
+/********************* DEFINITIONS for tiny ************************/
+
+/*
+ * Memory in the Tiny range is allocated from regions (heaps) pointed to by the
+ * szone's hashed_regions pointer.
+ *
+ * Each region is laid out as a heap, followed by a header block, all within
+ * a 1MB (2^20) block. This means there are 64520 16-byte blocks and the header
+ * is 16138 bytes, making the total 1048458 bytes, leaving 118 bytes unused.
+ *
+ * The header block is arranged as in struct tiny_region defined just below, and
+ * consists of two bitfields (or bit arrays) interleaved 32 bits by 32 bits.
+ *
+ * Each bitfield comprises NUM_TINY_BLOCKS bits, and refers to the corresponding
+ * TINY_QUANTUM block within the heap.
+ *
+ * The bitfields are used to encode the state of memory within the heap. The header bit indicates
+ * that the corresponding quantum is the first quantum in a block (either in use or free). The
+ * in-use bit is set for the header if the block has been handed out (allocated). If the header
+ * bit is not set, the in-use bit is invalid.
+ *
+ * The szone maintains an array of NUM_TINY_SLOTS freelists, each of which is used to hold
+ * free objects of the corresponding quantum size.
+ *
+ * A free block is laid out depending on its size, in order to fit all free
+ * blocks in 16 bytes, on both 32 and 64 bit platforms. One quantum blocks do
+ * not store their size in the block, instead relying on the header information
+ * to determine their size. Blocks of two or more quanta have room to store
+ * their size in the block, and store it both after the 'next' pointer, and in
+ * the last 2 bytes of the block.
+ *
+ * 1-quantum block
+ * Offset (32-bit mode) (64-bit mode)
+ * 0x0 0x0 : previous
+ * 0x4 0x08 : next
+ * end end
+ *
+ * >1-quantum block
+ * Offset (32-bit mode) (64-bit mode)
+ * 0x0 0x0 : previous
+ * 0x4 0x08 : next
+ * 0x8 0x10 : size (in quantum counts)
+ * end - 2 end - 2 : size (in quantum counts)
+ * end end
+ *
+ * All fields are pointer-sized, except for the size which is an unsigned short.
+ *
+ */
+
+#define SHIFT_TINY_QUANTUM 4 // Required for AltiVec
+#define TINY_QUANTUM (1 << SHIFT_TINY_QUANTUM)
+
+#define FOLLOWING_TINY_PTR(ptr,msize) (((unsigned char *)(ptr)) + ((msize) << SHIFT_TINY_QUANTUM))
+
+#ifdef __LP64__
+#define NUM_TINY_SLOTS 64 // number of slots for free-lists
+#else
+#define NUM_TINY_SLOTS 32 // number of slots for free-lists
+#endif
+
+#define NUM_TINY_BLOCKS 64520
+#define SHIFT_TINY_CEIL_BLOCKS 16 // ceil(log2(NUM_TINY_BLOCKS))
+#define NUM_TINY_CEIL_BLOCKS (1 << SHIFT_TINY_CEIL_BLOCKS)
+#define TINY_BLOCKS_ALIGN (SHIFT_TINY_CEIL_BLOCKS + SHIFT_TINY_QUANTUM) // 20
+
+/*
+ * Enough room for the data, followed by the bit arrays (2-bits per block)
+ * plus rounding to the nearest page.
+ */
+#define CEIL_NUM_TINY_BLOCKS_WORDS (((NUM_TINY_BLOCKS + 31) & ~31) >> 5)
+#define TINY_METADATA_SIZE (sizeof(region_trailer_t) + sizeof(tiny_header_inuse_pair_t) * CEIL_NUM_TINY_BLOCKS_WORDS)
+#define TINY_REGION_SIZE \
+ ((NUM_TINY_BLOCKS * TINY_QUANTUM + TINY_METADATA_SIZE + vm_page_size - 1) & ~ (vm_page_size - 1))
+
+#define TINY_METADATA_START (NUM_TINY_BLOCKS * TINY_QUANTUM)
+
+/*
+ * Beginning and end pointers for a region's heap.
+ */
+#define TINY_REGION_ADDRESS(region) ((void *)(region))
+#define TINY_REGION_END(region) ((void *)(((uintptr_t)(region)) + (NUM_TINY_BLOCKS * TINY_QUANTUM)))
+
+/*
+ * Locate the heap base for a pointer known to be within a tiny region.
+ */
+#define TINY_REGION_FOR_PTR(_p) ((void *)((uintptr_t)(_p) & ~((1 << TINY_BLOCKS_ALIGN) - 1)))
+
+/*
+ * Convert between byte and msize units.
+ */
+#define TINY_BYTES_FOR_MSIZE(_m) ((_m) << SHIFT_TINY_QUANTUM)
+#define TINY_MSIZE_FOR_BYTES(_b) ((_b) >> SHIFT_TINY_QUANTUM)
+
+#ifdef __LP64__
+# define TINY_FREE_SIZE(ptr) (((msize_t *)(ptr))[8])
+#else
+# define TINY_FREE_SIZE(ptr) (((msize_t *)(ptr))[4])
+#endif
+#define TINY_PREVIOUS_MSIZE(ptr) ((msize_t *)(ptr))[-1]
+
+/*
+ * Layout of a tiny region
+ */
+typedef uint32_t tiny_block_t[4]; // assert(TINY_QUANTUM == sizeof(tiny_block_t))
+
+typedef struct tiny_header_inuse_pair
+{
+ uint32_t header;
+ uint32_t inuse;
+} tiny_header_inuse_pair_t;
+
+typedef struct region_trailer
+{
+ struct region_trailer *prev;
+ struct region_trailer *next;
+ boolean_t recirc_suitable;
+ unsigned bytes_used;
+ mag_index_t mag_index;
+} region_trailer_t;
+
+typedef struct tiny_region
+{
+ tiny_block_t blocks[NUM_TINY_BLOCKS];
+
+ region_trailer_t trailer;
+
+ // The interleaved bit arrays comprising the header and inuse bitfields.
+ // The unused bits of each component in the last pair will be initialized to sentinel values.
+ tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS];
+
+ uint8_t pad[TINY_REGION_SIZE - (NUM_TINY_BLOCKS * sizeof(tiny_block_t)) - TINY_METADATA_SIZE];
+} *tiny_region_t;
+
+/*
+ * Per-region meta data for tiny allocator
+ */
+#define REGION_TRAILER_FOR_TINY_REGION(r) (&(((tiny_region_t)(r))->trailer))
+#define MAGAZINE_INDEX_FOR_TINY_REGION(r) (REGION_TRAILER_FOR_TINY_REGION(r)->mag_index)
+#define BYTES_USED_FOR_TINY_REGION(r) (REGION_TRAILER_FOR_TINY_REGION(r)->bytes_used)
+
+/*
+ * Locate the block header for a pointer known to be within a tiny region.
+ */
+#define TINY_BLOCK_HEADER_FOR_PTR(_p) ((void *)&(((tiny_region_t)TINY_REGION_FOR_PTR(_p))->pairs))
+
+/*
+ * Locate the inuse map for a given block header pointer.
+ */
+#define TINY_INUSE_FOR_HEADER(_h) ((void *)&(((tiny_header_inuse_pair_t *)(_h))->inuse))
+
+/*
+ * Compute the bitmap index for a pointer known to be within a tiny region.
+ */
+#define TINY_INDEX_FOR_PTR(_p) (((uintptr_t)(_p) >> SHIFT_TINY_QUANTUM) & (NUM_TINY_CEIL_BLOCKS - 1))
+
+#define TINY_CACHE 1 // This governs a last-free cache of 1 that bypasses the free-list
+
+#if ! TINY_CACHE
+#warning TINY_CACHE turned off
+#endif
+
+#define TINY_REGION_PAYLOAD_BYTES (NUM_TINY_BLOCKS * TINY_QUANTUM)
+
+/********************* DEFINITIONS for small ************************/
+
+/*
+ * Memory in the Small range is allocated from regions (heaps) pointed to by the szone's hashed_regions
+ * pointer.
+ *
+ * Each region is laid out as a heap, followed by the metadata array, all within an 8MB (2^23) block.
+ * The array is arranged as an array of shorts, one for each SMALL_QUANTUM in the heap.
+ * This means there are 16320 512-blocks and the array is 16320*2 bytes, which totals 8388480, leaving
+ * 128 bytes unused.
+ *
+ * The MSB of each short is set for the first quantum in a free block. The low 15 bits encode the
+ * block size (in SMALL_QUANTUM units), or are zero if the quantum is not the first in a block.
+ *
+ * The szone maintains an array of 32 freelists, each of which is used to hold free objects
+ * of the corresponding quantum size.
+ *
+ * A free block is laid out as:
+ *
+ * Offset (32-bit mode) (64-bit mode)
+ * 0x0 0x0 : previous
+ * 0x4 0x08 : next
+ * 0x8 0x10 : size (in quantum counts)
+ * end - 2 end - 2 : size (in quantum counts)
+ * end end
+ *
+ * All fields are pointer-sized, except for the size which is an unsigned short.
+ *
+ */
+
+#define SMALL_IS_FREE (1 << 15)
+
+#define SHIFT_SMALL_QUANTUM (SHIFT_TINY_QUANTUM + 5) // 9
+#define SMALL_QUANTUM (1 << SHIFT_SMALL_QUANTUM) // 512 bytes
+
+#define FOLLOWING_SMALL_PTR(ptr,msize) (((unsigned char *)(ptr)) + ((msize) << SHIFT_SMALL_QUANTUM))
+
+/*
+ * The number of slots in the free-list for small blocks. To avoid going to
+ * vm system as often on large memory machines, increase the number of free list
+ * spots above some amount of RAM installed in the system.
+ */
+#define NUM_SMALL_SLOTS 32
+#define NUM_SMALL_SLOTS_LARGEMEM 256
+#define SMALL_BITMAP_WORDS 8
+
+/*
+ * We can only represent up to 1<<15 for msize; but we choose to stay even below that to avoid the
+ * convention msize=0 => msize = (1<<15)
+ */
+#define NUM_SMALL_BLOCKS 16320
+#define SHIFT_SMALL_CEIL_BLOCKS 14 // ceil(log2(NUM_SMALL_BLOCKs))
+#define NUM_SMALL_CEIL_BLOCKS (1 << SHIFT_SMALL_CEIL_BLOCKS)
+#define SMALL_BLOCKS_ALIGN (SHIFT_SMALL_CEIL_BLOCKS + SHIFT_SMALL_QUANTUM) // 23
+
+#define SMALL_METADATA_SIZE (sizeof(region_trailer_t) + NUM_SMALL_BLOCKS * sizeof(msize_t))
+#define SMALL_REGION_SIZE \
+ ((NUM_SMALL_BLOCKS * SMALL_QUANTUM + SMALL_METADATA_SIZE + vm_page_size - 1) & ~ (vm_page_size - 1))
+
+#define SMALL_METADATA_START (NUM_SMALL_BLOCKS * SMALL_QUANTUM)
+
+/*
+ * Beginning and end pointers for a region's heap.
+ */
+#define SMALL_REGION_ADDRESS(region) ((unsigned char *)region)
+#define SMALL_REGION_END(region) (SMALL_REGION_ADDRESS(region) + (NUM_SMALL_BLOCKS * SMALL_QUANTUM))
+
+/*
+ * Locate the heap base for a pointer known to be within a small region.
+ */
+#define SMALL_REGION_FOR_PTR(_p) ((void *)((uintptr_t)(_p) & ~((1 << SMALL_BLOCKS_ALIGN) - 1)))
+
+/*
+ * Convert between byte and msize units.
+ */
+#define SMALL_BYTES_FOR_MSIZE(_m) ((_m) << SHIFT_SMALL_QUANTUM)
+#define SMALL_MSIZE_FOR_BYTES(_b) ((_b) >> SHIFT_SMALL_QUANTUM)
+
+#define SMALL_PREVIOUS_MSIZE(ptr) ((msize_t *)(ptr))[-1]
+
+/*
+ * Layout of a small region
+ */
+typedef uint32_t small_block_t[SMALL_QUANTUM/sizeof(uint32_t)];
+
+typedef struct small_region
+{
+ small_block_t blocks[NUM_SMALL_BLOCKS];
+
+ region_trailer_t trailer;
+
+ msize_t small_meta_words[NUM_SMALL_BLOCKS];
+
+ uint8_t pad[SMALL_REGION_SIZE - (NUM_SMALL_BLOCKS * sizeof(small_block_t)) - SMALL_METADATA_SIZE];
+} *small_region_t;
+
+/*
+ * Per-region meta data for small allocator
+ */
+#define REGION_TRAILER_FOR_SMALL_REGION(r) (&(((small_region_t)(r))->trailer))
+#define MAGAZINE_INDEX_FOR_SMALL_REGION(r) (REGION_TRAILER_FOR_SMALL_REGION(r)->mag_index)
+#define BYTES_USED_FOR_SMALL_REGION(r) (REGION_TRAILER_FOR_SMALL_REGION(r)->bytes_used)
+
+/*
+ * Locate the metadata base for a pointer known to be within a small region.
+ */
+#define SMALL_META_HEADER_FOR_PTR(_p) (((small_region_t)SMALL_REGION_FOR_PTR(_p))->small_meta_words)
+
+/*
+ * Compute the metadata index for a pointer known to be within a small region.
+ */
+#define SMALL_META_INDEX_FOR_PTR(_p) (((uintptr_t)(_p) >> SHIFT_SMALL_QUANTUM) & (NUM_SMALL_CEIL_BLOCKS - 1))
+
+/*
+ * Find the metadata word for a pointer known to be within a small region.
+ */
+#define SMALL_METADATA_FOR_PTR(_p) (SMALL_META_HEADER_FOR_PTR(_p) + SMALL_META_INDEX_FOR_PTR(_p))
+
+/*
+ * Determine whether a pointer known to be within a small region points to memory which is free.
+ */
+#define SMALL_PTR_IS_FREE(_p) (*SMALL_METADATA_FOR_PTR(_p) & SMALL_IS_FREE)
+
+/*
+ * Extract the msize value for a pointer known to be within a small region.
+ */
+#define SMALL_PTR_SIZE(_p) (*SMALL_METADATA_FOR_PTR(_p) & ~SMALL_IS_FREE)
+
+#define PROTECT_SMALL 0 // Should be 0: 1 is too slow for normal use
+
+#define SMALL_CACHE 1
+#if !SMALL_CACHE
+#warning SMALL_CACHE turned off
+#endif
+
+#define SMALL_REGION_PAYLOAD_BYTES (NUM_SMALL_BLOCKS * SMALL_QUANTUM)
+
+/************************* DEFINITIONS for large ****************************/
+
+#define LARGE_THRESHOLD (15 * 1024) // strictly above this use "large"
+#define LARGE_THRESHOLD_LARGEMEM (127 * 1024)
+
+#if (LARGE_THRESHOLD > NUM_SMALL_SLOTS * SMALL_QUANTUM)
+#error LARGE_THRESHOLD should always be less than NUM_SMALL_SLOTS * SMALL_QUANTUM
+#endif
+
+#if (LARGE_THRESHOLD_LARGEMEM > NUM_SMALL_SLOTS_LARGEMEM * SMALL_QUANTUM)
+#error LARGE_THRESHOLD_LARGEMEM should always be less than NUM_SMALL_SLOTS * SMALL_QUANTUM
+#endif
+
+/*
+ * When all memory is touched after a copy, vm_copy() is always a lose
+ * But if the memory is only read, vm_copy() wins over memmove() at 3 or 4 pages
+ * (on a G3/300MHz)
+ *
+ * This must be larger than LARGE_THRESHOLD
+ */
+#define VM_COPY_THRESHOLD (40 * 1024)
+#define VM_COPY_THRESHOLD_LARGEMEM (128 * 1024)
+
+typedef struct {
+ vm_address_t address;
+ vm_size_t size;
+ boolean_t did_madvise_reusable;
+} large_entry_t;
+
+#define LARGE_CACHE 1
+#if !LARGE_CACHE
+#warning LARGE_CACHE turned off
+#endif
+#if defined(__LP64__)
+#define LARGE_ENTRY_CACHE_SIZE 16
+#define LARGE_CACHE_SIZE_LIMIT ((vm_size_t)0x80000000) /* 2Gb */
+#else
+#define LARGE_ENTRY_CACHE_SIZE 8
+#define LARGE_CACHE_SIZE_LIMIT ((vm_size_t)0x02000000) /* 32Mb */
+#endif
+#define LARGE_CACHE_SIZE_ENTRY_LIMIT (LARGE_CACHE_SIZE_LIMIT/LARGE_ENTRY_CACHE_SIZE)
+
+/*******************************************************************************
+ * Definitions for region hash
+ ******************************************************************************/
+
+typedef void * region_t;
+typedef region_t * rgnhdl_t; /* A pointer into hashed_regions array. */
+
+#define INITIAL_NUM_REGIONS_SHIFT 6 // log2(INITIAL_NUM_REGIONS)
+#define INITIAL_NUM_REGIONS (1 << INITIAL_NUM_REGIONS_SHIFT) // Must be a power of 2!
+#define HASHRING_OPEN_ENTRY ((region_t) 0) // Initial value and sentinel marking end of collision chain
+#define HASHRING_REGION_DEALLOCATED ((region_t)-1) // Region at this slot reclaimed by OS
+#define HASH_BLOCKS_ALIGN TINY_BLOCKS_ALIGN // MIN( TINY_BLOCKS_ALIGN, SMALL_BLOCKS_ALIGN, ... )
+
+typedef struct region_hash_generation {
+ size_t num_regions_allocated;
+ size_t num_regions_allocated_shift; // log2(num_regions_allocated)
+ region_t *hashed_regions; // hashed by location
+ struct region_hash_generation *nextgen;
+} region_hash_generation_t;
+
+/*******************************************************************************
+ * Per-processor magazine for tiny and small allocators
+ ******************************************************************************/
+
+typedef struct { // vm_allocate()'d, so the array of magazines is page-aligned to begin with.
+ // Take magazine_lock first, Depot lock when needed for recirc, then szone->{tiny,small}_regions_lock when needed for alloc
+ pthread_lock_t magazine_lock CACHE_ALIGN;
+
+ // One element deep "death row", optimizes malloc/free/malloc for identical size.
+ void *mag_last_free; // low SHIFT_{TINY,SMALL}_QUANTUM bits indicate the msize
+ region_t mag_last_free_rgn; // holds the region for mag_last_free
+
+ free_list_t *mag_free_list[256]; // assert( 256 >= MAX( NUM_TINY_SLOTS, NUM_SMALL_SLOTS_LARGEMEM ))
+ unsigned mag_bitmap[8]; // assert( sizeof(mag_bitmap) << 3 >= sizeof(mag_free_list)/sizeof(free_list_t) )
+
+ // the last free region in the last block is treated as a big block in use that is not accounted for
+ size_t mag_bytes_free_at_end;
+ region_t mag_last_region; // Valid iff mag_bytes_free_at_end > 0
+
+ // bean counting ...
+ unsigned mag_num_objects;
+ size_t mag_num_bytes_in_objects;
+ size_t num_bytes_in_magazine;
+
+ // recirculation list -- invariant: all regions owned by this magazine that meet the emptiness criteria
+ // are located nearer to the head of the list than any region that doesn't satisfy that criteria.
+ // Doubly linked list for efficient extraction.
+ unsigned recirculation_entries;
+ region_trailer_t *firstNode;
+ region_trailer_t *lastNode;
+
+#if __LP64__
+ uint64_t pad[49]; // So sizeof(magazine_t) is 2560 bytes. FIXME: assert this at compile time
+#else
+ uint32_t pad[45]; // So sizeof(magazine_t) is 1280 bytes. FIXME: assert this at compile time
+#endif
+} magazine_t;
+
+#define TINY_MAX_MAGAZINES 16 /* MUST BE A POWER OF 2! */
+#define TINY_MAGAZINE_PAGED_SIZE \
+ (((sizeof(magazine_t) * (TINY_MAX_MAGAZINES + 1)) + vm_page_size - 1) &\
+ ~ (vm_page_size - 1)) /* + 1 for the Depot */
+
+#define SMALL_MAX_MAGAZINES 16 /* MUST BE A POWER OF 2! */
+#define SMALL_MAGAZINE_PAGED_SIZE \
+ (((sizeof(magazine_t) * (SMALL_MAX_MAGAZINES + 1)) + vm_page_size - 1) &\
+ ~ (vm_page_size - 1)) /* + 1 for the Depot */
+
+#define DEPOT_MAGAZINE_INDEX -1
+
+/****************************** zone itself ***********************************/
+
+/*
+ * Note that objects whose adddress are held in pointers here must be pursued
+ * individually in the {tiny,small}_in_use_enumeration() routines. See for
+ * example the treatment of region_hash_generation and tiny_magazines below.
+ */
+
+typedef struct szone_s { // vm_allocate()'d, so page-aligned to begin with.
+ malloc_zone_t basic_zone;
+ pthread_key_t cpu_id_key;
+ unsigned debug_flags;
+ void *log_address;
+
+ /* Regions for tiny objects */
+ pthread_lock_t tiny_regions_lock CACHE_ALIGN;
+ size_t num_tiny_regions;
+ size_t num_tiny_regions_dealloc;
+ region_hash_generation_t *tiny_region_generation;
+ region_hash_generation_t trg[2];
+
+ int num_tiny_magazines;
+ unsigned num_tiny_magazines_mask;
+ int num_tiny_magazines_mask_shift;
+ magazine_t *tiny_magazines; // array of per-processor magazines
+
+ /* Regions for small objects */
+ pthread_lock_t small_regions_lock CACHE_ALIGN;
+ size_t num_small_regions;
+ size_t num_small_regions_dealloc;
+ region_hash_generation_t *small_region_generation;
+ region_hash_generation_t srg[2];
+
+ unsigned num_small_slots; // determined by physmem size
+
+ int num_small_magazines;
+ unsigned num_small_magazines_mask;
+ int num_small_magazines_mask_shift;
+ magazine_t *small_magazines; // array of per-processor magazines
+
+ /* large objects: all the rest */
+ pthread_lock_t large_szone_lock CACHE_ALIGN; // One customer at a time for large
+ unsigned num_large_objects_in_use;
+ unsigned num_large_entries;
+ large_entry_t *large_entries; // hashed by location; null entries don't count
+ size_t num_bytes_in_large_objects;
+
+#if LARGE_CACHE
+ int large_entry_cache_oldest;
+ int large_entry_cache_newest;
+ large_entry_t large_entry_cache[LARGE_ENTRY_CACHE_SIZE]; // "death row" for large malloc/free
+ boolean_t large_legacy_reset_mprotect;
+ size_t large_entry_cache_hoard_bytes;
+ size_t large_entry_cache_hoard_lmit;
+#endif
+
+ /* flag and limits pertaining to altered malloc behavior for systems with
+ large amounts of physical memory */
+ unsigned is_largemem;
+ unsigned large_threshold;
+ unsigned vm_copy_threshold;
+
+ /* security cookie */
+ uintptr_t cookie;
+
+ /* Initial region list */
+ region_t initial_tiny_regions[INITIAL_NUM_REGIONS];
+ region_t initial_small_regions[INITIAL_NUM_REGIONS];
+
+ /* The purgeable zone constructed by create_purgeable_zone() would like to hand off tiny and small
+ * allocations to the default scalable zone. Record the latter as the "helper" zone here. */
+ struct szone_s *helper_zone;
+} szone_t;
+
+#define SZONE_PAGED_SIZE ((sizeof(szone_t) + vm_page_size - 1) & ~ (vm_page_size - 1))
+
+#if DEBUG_MALLOC || DEBUG_CLIENT
+static void szone_sleep(void);
+#endif
+__private_extern__ void malloc_error_break(void);
+
+// msg prints after fmt, ...
+static NOINLINE void szone_error(szone_t *szone, int is_corruption, const char *msg, const void *ptr, const char *fmt, ...)
+ __printflike(5, 6);
+
+static void protect(void *address, size_t size, unsigned protection, unsigned debug_flags);
+static void *allocate_pages(szone_t *szone, size_t size, unsigned char align, unsigned debug_flags,
+ int vm_page_label);
+static void deallocate_pages(szone_t *szone, void *addr, size_t size, unsigned debug_flags);
+static int madvise_free_range(szone_t *szone, region_t r, uintptr_t pgLo, uintptr_t pgHi);
+static kern_return_t _szone_default_reader(task_t task, vm_address_t address, vm_size_t size, void **ptr);
+
+static INLINE mag_index_t mag_get_thread_index(szone_t *szone) ALWAYSINLINE;
+static magazine_t *mag_lock_zine_for_region_trailer(szone_t *szone, magazine_t *magazines, region_trailer_t *trailer,
+ mag_index_t mag_index);
+
+static INLINE rgnhdl_t hash_lookup_region_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r)
+ ALWAYSINLINE;
+static void hash_region_insert_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r);
+static region_t *hash_regions_alloc_no_lock(szone_t *szone, size_t num_entries);
+static region_t *hash_regions_grow_no_lock(szone_t *szone, region_t *regions, size_t old_size,
+ size_t *mutable_shift, size_t *new_size);
+
+static INLINE uintptr_t free_list_gen_checksum(uintptr_t ptr) ALWAYSINLINE;
+static INLINE uintptr_t free_list_checksum_ptr(szone_t *szone, void *p) ALWAYSINLINE;
+static INLINE void *free_list_unchecksum_ptr(szone_t *szone, ptr_union *ptr) ALWAYSINLINE;
+static unsigned free_list_count(szone_t *szone, free_list_t *ptr);
+
+static INLINE void recirc_list_extract(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node) ALWAYSINLINE;
+static INLINE void recirc_list_splice_last(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node) ALWAYSINLINE;
+static INLINE void recirc_list_splice_first(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node) ALWAYSINLINE;
+
+static INLINE void BITARRAY_SET(uint32_t *bits, msize_t index) ALWAYSINLINE;
+static INLINE void BITARRAY_CLR(uint32_t *bits, msize_t index) ALWAYSINLINE;
+static INLINE boolean_t BITARRAY_BIT(uint32_t *bits, msize_t index) ALWAYSINLINE;
+
+static msize_t get_tiny_free_size(const void *ptr);
+static msize_t get_tiny_previous_free_msize(const void *ptr);
+static INLINE msize_t get_tiny_meta_header(const void *ptr, boolean_t *is_free) ALWAYSINLINE;
+static INLINE void set_tiny_meta_header_in_use(const void *ptr, msize_t msize) ALWAYSINLINE;
+static INLINE void set_tiny_meta_header_in_use_1(const void *ptr) ALWAYSINLINE;
+static INLINE void set_tiny_meta_header_middle(const void *ptr) ALWAYSINLINE;
+static INLINE void set_tiny_meta_header_free(const void *ptr, msize_t msize) ALWAYSINLINE;
+static INLINE boolean_t tiny_meta_header_is_free(const void *ptr) ALWAYSINLINE;
+static INLINE void *tiny_previous_preceding_free(void *ptr, msize_t *prev_msize) ALWAYSINLINE;
+
+static void tiny_free_list_add_ptr(szone_t *szone, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize);
+static void tiny_free_list_remove_ptr(szone_t *szone, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize);
+static INLINE region_t tiny_region_for_ptr_no_lock(szone_t *szone, const void *ptr) ALWAYSINLINE;
+
+static void tiny_finalize_region(szone_t *szone, magazine_t *tiny_mag_ptr);
+static int tiny_free_detach_region(szone_t *szone, magazine_t *tiny_mag_ptr, region_t r);
+static size_t tiny_free_reattach_region(szone_t *szone, magazine_t *tiny_mag_ptr, region_t r);
+static void tiny_free_scan_madvise_free(szone_t *szone, magazine_t *depot_ptr, region_t r);
+static void tiny_free_try_depot_unmap_no_lock(szone_t *szone, magazine_t *depot_ptr, region_trailer_t *node);
+static void tiny_free_do_recirc_to_depot(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index);
+static boolean_t tiny_get_region_from_depot(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index);
+
+static INLINE void tiny_free_no_lock(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index, region_t region,
+ void *ptr, msize_t msize) ALWAYSINLINE;
+static void *tiny_malloc_from_region_no_lock(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index,
+ msize_t msize);
+static boolean_t tiny_try_realloc_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size);
+static boolean_t tiny_check_region(szone_t *szone, region_t region);
+static kern_return_t tiny_in_use_enumerator(task_t task, void *context, unsigned type_mask, szone_t *szone,
+ memory_reader_t reader, vm_range_recorder_t recorder);
+static void *tiny_malloc_from_free_list(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index,
+ msize_t msize);
+static INLINE void *tiny_malloc_should_clear(szone_t *szone, msize_t msize, boolean_t cleared_requested) ALWAYSINLINE;
+static INLINE void free_tiny(szone_t *szone, void *ptr, region_t tiny_region, size_t known_size) ALWAYSINLINE;
+static void print_tiny_free_list(szone_t *szone);
+static void print_tiny_region(boolean_t verbose, region_t region, size_t bytes_at_end);
+static boolean_t tiny_free_list_check(szone_t *szone, grain_t slot);
+
+static INLINE void small_meta_header_set_is_free(msize_t *meta_headers, unsigned index, msize_t msize) ALWAYSINLINE;
+static INLINE void small_meta_header_set_in_use(msize_t *meta_headers, msize_t index, msize_t msize) ALWAYSINLINE;
+static INLINE void small_meta_header_set_middle(msize_t *meta_headers, msize_t index) ALWAYSINLINE;
+static void small_free_list_add_ptr(szone_t *szone, magazine_t *small_mag_ptr, void *ptr, msize_t msize);
+static void small_free_list_remove_ptr(szone_t *szone, magazine_t *small_mag_ptr, void *ptr, msize_t msize);
+static INLINE region_t small_region_for_ptr_no_lock(szone_t *szone, const void *ptr) ALWAYSINLINE;
+
+static void small_finalize_region(szone_t *szone, magazine_t *small_mag_ptr);
+static int small_free_detach_region(szone_t *szone, magazine_t *small_mag_ptr, region_t r);
+static size_t small_free_reattach_region(szone_t *szone, magazine_t *small_mag_ptr, region_t r);
+static void small_free_scan_depot_madvise_free(szone_t *szone, magazine_t *depot_ptr, region_t r);
+static void small_free_try_depot_unmap_no_lock(szone_t *szone, magazine_t *depot_ptr, region_trailer_t *node);
+static void small_free_do_recirc_to_depot(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index);
+static boolean_t small_get_region_from_depot(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index);
+static INLINE void small_free_no_lock(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index, region_t region,
+ void *ptr, msize_t msize) ALWAYSINLINE;
+static void *small_malloc_from_region_no_lock(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index,
+ msize_t msize);
+static boolean_t small_try_realloc_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size);
+static boolean_t small_check_region(szone_t *szone, region_t region);
+static kern_return_t small_in_use_enumerator(task_t task, void *context, unsigned type_mask, szone_t *szone,
+ memory_reader_t reader, vm_range_recorder_t recorder);
+static void *small_malloc_from_free_list(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index,
+ msize_t msize);
+static INLINE void *small_malloc_should_clear(szone_t *szone, msize_t msize, boolean_t cleared_requested) ALWAYSINLINE;
+static INLINE void free_small(szone_t *szone, void *ptr, region_t small_region, size_t known_size) ALWAYSINLINE;
+static void print_small_free_list(szone_t *szone);
+static void print_small_region(szone_t *szone, boolean_t verbose, region_t region, size_t bytes_at_end);
+static boolean_t small_free_list_check(szone_t *szone, grain_t grain);
+
+#if DEBUG_MALLOC
+static void large_debug_print(szone_t *szone);
+#endif
+static large_entry_t *large_entry_for_pointer_no_lock(szone_t *szone, const void *ptr);
+static void large_entry_insert_no_lock(szone_t *szone, large_entry_t range);
+static INLINE void large_entries_rehash_after_entry_no_lock(szone_t *szone, large_entry_t *entry) ALWAYSINLINE;
+static INLINE large_entry_t *large_entries_alloc_no_lock(szone_t *szone, unsigned num) ALWAYSINLINE;
+static void large_entries_free_no_lock(szone_t *szone, large_entry_t *entries, unsigned num,
+ vm_range_t *range_to_deallocate);
+static large_entry_t *large_entries_grow_no_lock(szone_t *szone, vm_range_t *range_to_deallocate);
+static vm_range_t large_entry_free_no_lock(szone_t *szone, large_entry_t *entry);
+static NOINLINE kern_return_t large_in_use_enumerator(task_t task, void *context,
+ unsigned type_mask, vm_address_t large_entries_address,
+ unsigned num_entries, memory_reader_t reader, vm_range_recorder_t recorder);
+static void *large_malloc(szone_t *szone, size_t num_pages, unsigned char alignment, boolean_t cleared_requested);
+static NOINLINE void free_large(szone_t *szone, void *ptr);
+static INLINE int large_try_realloc_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size) ALWAYSINLINE;
+
+/*
+ * Mark these NOINLINE to avoid bloating the purgeable zone call backs
+ */
+static NOINLINE void szone_free(szone_t *szone, void *ptr);
+static NOINLINE void *szone_malloc_should_clear(szone_t *szone, size_t size, boolean_t cleared_requested);
+static NOINLINE void *szone_malloc(szone_t *szone, size_t size);
+static NOINLINE void *szone_calloc(szone_t *szone, size_t num_items, size_t size);
+static NOINLINE void *szone_valloc(szone_t *szone, size_t size);
+static NOINLINE size_t szone_size_try_large(szone_t *szone, const void *ptr);
+static NOINLINE size_t szone_size(szone_t *szone, const void *ptr);
+static NOINLINE void *szone_realloc(szone_t *szone, void *ptr, size_t new_size);
+static NOINLINE void *szone_memalign(szone_t *szone, size_t alignment, size_t size);
+static NOINLINE void szone_free_definite_size(szone_t *szone, void *ptr, size_t size);
+static NOINLINE unsigned szone_batch_malloc(szone_t *szone, size_t size, void **results, unsigned count);
+static NOINLINE void szone_batch_free(szone_t *szone, void **to_be_freed, unsigned count);
+static void szone_destroy(szone_t *szone);
+static NOINLINE size_t szone_good_size(szone_t *szone, size_t size);
+
+static NOINLINE boolean_t szone_check_all(szone_t *szone, const char *function);
+static boolean_t szone_check(szone_t *szone);
+static kern_return_t szone_ptr_in_use_enumerator(task_t task, void *context,
+ unsigned type_mask, vm_address_t zone_address,
+ memory_reader_t reader, vm_range_recorder_t recorder);
+static NOINLINE void szone_print(szone_t *szone, boolean_t verbose);
+static void szone_log(malloc_zone_t *zone, void *log_address);
+static void szone_force_lock(szone_t *szone);
+static void szone_force_unlock(szone_t *szone);
+static boolean_t szone_locked(szone_t *szone);
+
+static void szone_statistics(szone_t *szone, malloc_statistics_t *stats);
+
+static void purgeable_free(szone_t *szone, void *ptr);
+static void *purgeable_malloc(szone_t *szone, size_t size);
+static void *purgeable_calloc(szone_t *szone, size_t num_items, size_t size);
+static void *purgeable_valloc(szone_t *szone, size_t size);
+static size_t purgeable_size(szone_t *szone, const void *ptr);
+static void *purgeable_realloc(szone_t *szone, void *ptr, size_t new_size);
+static void *purgeable_memalign(szone_t *szone, size_t alignment, size_t size);
+static void purgeable_free_definite_size(szone_t *szone, void *ptr, size_t size);
+static unsigned purgeable_batch_malloc(szone_t *szone, size_t size, void **results, unsigned count);
+static void purgeable_batch_free(szone_t *szone, void **to_be_freed, unsigned count);
+static void purgeable_destroy(szone_t *szone);
+static size_t purgeable_good_size(szone_t *szone, size_t size);
+
+static boolean_t purgeable_check(szone_t *szone);
+static kern_return_t purgeable_ptr_in_use_enumerator(task_t task, void *context,
+ unsigned type_mask, vm_address_t zone_address,
+ memory_reader_t reader, vm_range_recorder_t recorder);
+static void purgeable_print(szone_t *szone, boolean_t verbose);
+static void purgeable_log(malloc_zone_t *zone, void *log_address);
+static void purgeable_force_lock(szone_t *szone);
+static void purgeable_force_unlock(szone_t *szone);
+static boolean_t purgeable_locked(szone_t *szone);
+
+static void purgeable_statistics(szone_t *szone, malloc_statistics_t *stats);
+
+static void *frozen_malloc(szone_t *zone, size_t new_size);
+static void *frozen_calloc(szone_t *zone, size_t num_items, size_t size);
+static void *frozen_valloc(szone_t *zone, size_t new_size);
+static void *frozen_realloc(szone_t *zone, void *ptr, size_t new_size);
+static void frozen_free(szone_t *zone, void *ptr);
+static void frozen_destroy(szone_t *zone);
+
+#define SZONE_LOCK(szone) \
+ do { \
+ LOCK(szone->large_szone_lock); \
+ } while (0)
+
+#define SZONE_UNLOCK(szone) \
+ do { \
+ UNLOCK(szone->large_szone_lock); \
+ } while (0)
+
+#define SZONE_TRY_LOCK(szone) \
+ TRY_LOCK(szone->large_szone_lock);
+
+#define SZONE_MAGAZINE_PTR_LOCK(szone, mag_ptr) \
+ do { \
+ LOCK(mag_ptr->magazine_lock); \
+ } while(0)
+
+#define SZONE_MAGAZINE_PTR_UNLOCK(szone, mag_ptr) \
+ do { \
+ UNLOCK(mag_ptr->magazine_lock); \
+ } while(0)
+
+#define SZONE_MAGAZINE_PTR_TRY_LOCK(szone, mag_ptr) \
+ TRY_LOCK(mag_ptr->magazine_lock);
+
+#if DEBUG_MALLOC
+# define LOG(szone,ptr) \
+ (szone->log_address && (((uintptr_t)szone->log_address == -1) || \
+ (szone->log_address == (void *)(ptr))))
+#else
+# define LOG(szone,ptr) 0
+#endif
+
+#if DEBUG_MALLOC || DEBUG_CLIENT
+# define CHECK(szone,fun) \
+ if ((szone)->debug_flags & CHECK_REGIONS) \
+ szone_check_all(szone, fun)
+#else
+# define CHECK(szone,fun) \
+ do {} while (0)
+#endif
+
+/********************* VERY LOW LEVEL UTILITIES ************************/
+
+#if DEBUG_MALLOC || DEBUG_CLIENT
+static void
+szone_sleep(void)
+{
+
+ if (getenv("MallocErrorSleep")) {
+ _malloc_printf(ASL_LEVEL_NOTICE, "*** sleeping to help debug\n");
+ sleep(3600); // to help debug
+ }
+}
+#endif
+
+extern const char *__crashreporter_info__;
+
+// msg prints after fmt, ...
+static NOINLINE void
+szone_error(szone_t *szone, int is_corruption, const char *msg, const void *ptr, const char *fmt, ...)
+{
+ va_list ap;
+ _SIMPLE_STRING b = _simple_salloc();
+
+ if (szone) SZONE_UNLOCK(szone); // FIXME: unlock magazine and region locks?
+ if (b) {
+ if (fmt) {
+ va_start(ap, fmt);
+ _simple_vsprintf(b, fmt, ap);
+ va_end(ap);
+ }
+ if (ptr) {
+ _simple_sprintf(b, "*** error for object %p: %s\n", ptr, msg);
+ } else {
+ _simple_sprintf(b, "*** error: %s\n", msg);
+ }
+ malloc_printf("%s*** set a breakpoint in malloc_error_break to debug\n", _simple_string(b));
+ } else {
+ /*
+ * Should only get here if vm_allocate() can't get a single page of
+ * memory, implying _simple_asl_log() would also fail. So we just
+ * print to the file descriptor.
+ */
+ if (fmt) {
+ va_start(ap, fmt);
+ _malloc_vprintf(MALLOC_PRINTF_NOLOG, fmt, ap);
+ va_end(ap);
+ }
+ if (ptr) {
+ _malloc_printf(MALLOC_PRINTF_NOLOG, "*** error for object %p: %s\n", ptr, msg);
+ } else {
+ _malloc_printf(MALLOC_PRINTF_NOLOG, "*** error: %s\n", msg);
+ }
+ _malloc_printf(MALLOC_PRINTF_NOLOG, "*** set a breakpoint in malloc_error_break to debug\n");
+ }
+ malloc_error_break();
+#if DEBUG_MALLOC
+ szone_print(szone, 1);
+ szone_sleep();
+#endif
+#if DEBUG_CLIENT
+ szone_sleep();
+#endif
+ // Call abort() if this is a memory corruption error and the abort on
+ // corruption flag is set, or if any error should abort.
+ if ((is_corruption && (szone->debug_flags & SCALABLE_MALLOC_ABORT_ON_CORRUPTION)) ||
+ (szone->debug_flags & SCALABLE_MALLOC_ABORT_ON_ERROR)) {
+ __crashreporter_info__ = b ? _simple_string(b) : msg;
+ abort();
+ } else if (b) {
+ _simple_sfree(b);
+ }
+}
+
+static void
+protect(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,(uintptr_t)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, (uintptr_t)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
+ void *vm_addr;
+ uintptr_t addr = 0, aligned_address;
+ boolean_t add_guard_pages = debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES;
+ boolean_t purgeable = debug_flags & SCALABLE_MALLOC_PURGEABLE;
+ size_t allocation_size = round_page(size);
+ size_t delta;
+ int flags = VM_MAKE_TAG(vm_page_label);
+
+ 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;
+ if (purgeable) flags |= VM_FLAGS_PURGABLE;
+
+ if (allocation_size < size) // size_t arithmetic wrapped!
+ return NULL;
+
+ vm_addr = mmap(0, allocation_size, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, flags, 0);
+ if ((uintptr_t)vm_addr == -1) {
+ szone_error(szone, 0, "can't allocate region", NULL, "*** mmap(size=%lu) failed (error code=%d)\n",
+ allocation_size, errno);
+ 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;
+ if (munmap((void *)addr, delta) == -1)
+ malloc_printf("*** munmap unaligned header failed with %d\n", errno);
+ addr = aligned_address;
+ allocation_size -= delta;
+ }
+ if (allocation_size > size) {
+ if (munmap((void *)(addr + size), allocation_size - size) == -1)
+ malloc_printf("*** munmap unaligned footer failed with %d\n", errno);
+ }
+ }
+ if (add_guard_pages) {
+ addr += (uintptr_t)1 << vm_page_shift;
+ protect((void *)addr, size, 0, debug_flags);
+ }
+ return (void *)addr;
+}
+
+static void
+deallocate_pages(szone_t *szone, void *addr, size_t size, unsigned debug_flags)
+{
+ int err;
+ boolean_t add_guard_pages = debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES;
+
+ if (add_guard_pages) {
+ addr = (void *)((uintptr_t)addr - (1 << vm_page_shift));
+ size += 2 * (1 << vm_page_shift);
+ }
+ err = munmap(addr, size);
+ if ((err == -1) && szone)
+ szone_error(szone, 0, "Can't deallocate_pages region", addr, NULL);
+}
+
+static int
+madvise_free_range(szone_t *szone, region_t r, uintptr_t pgLo, uintptr_t pgHi)
+{
+ if (pgHi > pgLo) {
+ size_t len = pgHi - pgLo;
+
+#if DEBUG_MALLOC
+ if (szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE)
+ memset((void *)pgLo, 0xed, len); // Scribble on MADV_FREEd memory
+#endif
+ MAGMALLOC_MADVFREEREGION((void *)szone, (void *)r, (void *)pgLo, len); // DTrace USDT Probe
+ if (-1 == madvise((void *)pgLo, len, MADV_FREE_REUSABLE)) {
+ /* -1 return: VM map entry change makes this unfit for reuse. Something evil lurks. */
+#if DEBUG_MALLOC
+ szone_error(szone, 1, "madvise_free_range madvise(..., MADV_FREE_REUSABLE) failed", (void *)pgLo, NULL);
+#endif
+ }
+ }
+ return 0;
+}
+
+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;
+}
+
+// Multiplicative hash where the multiplier is a prime near (ULONG_MAX / phi). [phi = 1.618033...]
+// pthread_t's are page aligned, (sometimes even in ascending sequence). These hash well.
+// See Knuth TAOCP, Vol. 3.
+#if __LP64__
+#define HASH_SELF() \
+ ((((uintptr_t)pthread_self()) >> vm_page_shift) * 11400714819323198549ULL) >> (64 - szone->num_tiny_magazines_mask_shift)
+#else
+#define HASH_SELF() \
+ ((((uintptr_t)pthread_self()) >> vm_page_shift) * 2654435761UL) >> (32 - szone->num_tiny_magazines_mask_shift)
+#endif
+
+#if defined(__i386__) || defined(__x86_64__)
+#define __APPLE_API_PRIVATE
+#include <machine/cpu_capabilities.h>
+#define _COMM_PAGE_VERSION_REQD 9
+#undef __APPLE_API_PRIVATE
+
+/*
+ * These commpage routines provide fast access to the logical cpu number
+ * of the calling processor assuming no pre-emption occurs.
+ */
+#define CPU_NUMBER() (((int (*)()) _COMM_PAGE_CPU_NUMBER)()) /* Zero-based */
+
+static INLINE mag_index_t
+mag_get_thread_index(szone_t *szone)
+{
+ if (!__is_threaded)
+ return 0;
+ else
+ return CPU_NUMBER() & (TINY_MAX_MAGAZINES - 1);
+}
+
+#else
+#warning deriving magazine index from pthread_self() [want processor number]
+
+static INLINE mag_index_t
+mag_get_thread_index(szone_t *szone)
+{
+ if (!__is_threaded)
+ return 0;
+ else if ((pthread_key_t) -1 == szone->cpu_id_key) { // In case pthread_key_create() failed.
+ return HASH_SELF();
+ } else {
+ mag_index_t idx = (mag_index_t)(intptr_t)pthread_getspecific(szone->cpu_id_key);
+
+ // Has this thread been hinted with a non-zero value [i.e. 1 + cpuid()] ?
+ // If so, bump down the hint to a zero-based magazine index and return it.
+ if (idx) {
+ return idx - 1;
+ } else {
+ // No hint available. Contruct a magazine index for this thread ...
+ idx = HASH_SELF();
+
+ // bump up the hint to exclude zero and try to memorize it ...
+ pthread_setspecific(szone->cpu_id_key, (const void *)((uintptr_t)idx + 1));
+
+ // and return the (zero-based) magazine index.
+ return idx;
+ }
+ }
+}
+#endif
+
+static magazine_t *
+mag_lock_zine_for_region_trailer(szone_t *szone, magazine_t *magazines, region_trailer_t *trailer, mag_index_t mag_index)
+{
+ mag_index_t refreshed_index;
+ magazine_t *mag_ptr = &(magazines[mag_index]);
+
+ // Take the lock on entry.
+ SZONE_MAGAZINE_PTR_LOCK(szone, mag_ptr);
+
+ // Now in the time it took to acquire the lock, the region may have migrated
+ // from one magazine to another. In which case the magazine lock we obtained
+ // (namely magazines[mag_index].mag_lock) is stale. If so, keep on tryin' ...
+ while (mag_index != (refreshed_index = trailer->mag_index)) { // Note assignment
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, mag_ptr);
+
+ mag_index = refreshed_index;
+ mag_ptr = &(magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_LOCK(szone, mag_ptr);
+ }
+
+ return mag_ptr;
+}
+
+/*******************************************************************************
+ * Region hash implementation
+ *
+ * This is essentially a duplicate of the existing Large allocator hash, minus
+ * the ability to remove entries. The two should be combined eventually.
+ ******************************************************************************/
+#pragma mark region hash
+
+/*
+ * hash_lookup_region_no_lock - Scan a hash ring looking for an entry for a
+ * given region.
+ *
+ * FIXME: If consecutive queries of the same region are likely, a one-entry
+ * cache would likely be a significant performance win here.
+ */
+static INLINE rgnhdl_t
+hash_lookup_region_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r) {
+ size_t index, hash_index;
+ rgnhdl_t entry;
+
+ if (!num_entries)
+ return 0;
+
+ // Multiplicative hash where the multiplier is a prime near (ULONG_MAX / phi). [phi = 1.618033...]
+ // Since the values of (((uintptr_t)r >> HASH_BLOCKS_ALIGN) are (roughly) an ascending sequence of integers,
+ // this hash works really well. See Knuth TAOCP, Vol. 3.
+#if __LP64__
+ index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 11400714819323198549ULL) >> (64 - shift);
+#else
+ index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 2654435761UL) >> (32 - shift);
+#endif
+ do {
+ entry = regions + index;
+ if (*entry == 0)
+ return 0;
+ if (*entry == r)
+ return entry;
+ if (++index == num_entries)
+ index = 0;
+ } while (index != hash_index);
+ return 0;
+}
+
+/*
+ * hash_region_insert_no_lock - Insert a region into the hash ring.
+ */
+static void
+hash_region_insert_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r) {
+ size_t index, hash_index;
+ rgnhdl_t entry;
+
+ // Multiplicative hash where the multiplier is a prime near (ULONG_MAX / phi). [phi = 1.618033...]
+ // Since the values of (((uintptr_t)r >> HASH_BLOCKS_ALIGN) are (roughly) an ascending sequence of integers,
+ // this hash works really well. See Knuth TAOCP, Vol. 3.
+#if __LP64__
+ index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 11400714819323198549ULL) >> (64 - shift);
+#else
+ index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 2654435761UL) >> (32 - shift);
+#endif
+ do {
+ entry = regions + index;
+ if (*entry == HASHRING_OPEN_ENTRY || *entry == HASHRING_REGION_DEALLOCATED) {
+ *entry = r;
+ return;
+ }
+ if (++index == num_entries)
+ index = 0;
+ } while (index != hash_index);
+}
+
+/*
+ * hash_regions_alloc_no_lock - Allocate space for a number of entries. This
+ * must be a VM allocation as to avoid recursing between allocating a new small
+ * region, and asking the small region to allocate space for the new list of
+ * regions.
+ */
+static region_t *
+hash_regions_alloc_no_lock(szone_t *szone, size_t num_entries)
+{
+ size_t size = num_entries * sizeof(region_t);
+
+ return allocate_pages(szone, round_page(size), 0, 0, VM_MEMORY_MALLOC);
+}
+
+/*
+ * hash_regions_grow_no_lock - Grow the hash ring, and rehash the entries.
+ * Return the new region and new size to update the szone. Do not deallocate
+ * the old entries since someone may still be allocating them.
+ */
+static region_t *
+hash_regions_grow_no_lock(szone_t *szone, region_t *regions, size_t old_size, size_t *mutable_shift,
+ size_t *new_size)
+{
+ // double in size and allocate memory for the regions
+ *new_size = old_size + old_size;
+ *mutable_shift = *mutable_shift + 1;
+ region_t *new_regions = hash_regions_alloc_no_lock(szone, *new_size);
+
+ // rehash the entries into the new list
+ size_t index;
+ for (index = 0; index < old_size; ++index) {
+ region_t r = regions[index];
+ if (r != HASHRING_OPEN_ENTRY && r != HASHRING_REGION_DEALLOCATED)
+ hash_region_insert_no_lock(new_regions, *new_size, *mutable_shift, r);
+ }
+ return new_regions;
+}
+
+/********************* FREE LIST UTILITIES ************************/
+
+// A free list entry is comprised of a pair of pointers, previous and next.
+// These are used to implement a doubly-linked list, which permits efficient
+// extraction.
+//
+// Because the free list entries are previously freed objects, a misbehaved
+// program may write to a pointer after it has called free() on that pointer,
+// either by dereference or buffer overflow from an adjacent pointer. This write
+// would then corrupt the free list's previous and next pointers, leading to a
+// crash. In order to detect this case, we take advantage of the fact that
+// malloc'd pointers are known to be at least 16 byte aligned, and thus have
+// at least 4 trailing zero bits.
+//
+// When an entry is added to the free list, a checksum of the previous and next
+// pointers is calculated and written to the low four bits of the respective
+// pointers. Upon detection of an invalid checksum, an error is logged and NULL
+// is returned. Since all code which un-checksums pointers checks for a NULL
+// return, a potentially crashing or malicious dereference is avoided at the
+// cost of leaking the corrupted block, and any subsequent blocks on the free
+// list of that size.
+
+static NOINLINE void
+free_list_checksum_botch(szone_t *szone, free_list_t *ptr)
+{
+ szone_error(szone, 1, "incorrect checksum for freed object "
+ "- object was probably modified after being freed.", ptr, NULL);
+}
+
+static INLINE uintptr_t free_list_gen_checksum(uintptr_t ptr)
+{
+ uint8_t chk;
+
+ chk = (unsigned char)(ptr >> 0);
+ chk += (unsigned char)(ptr >> 8);
+ chk += (unsigned char)(ptr >> 16);
+ chk += (unsigned char)(ptr >> 24);
+#if __LP64__
+ chk += (unsigned char)(ptr >> 32);
+ chk += (unsigned char)(ptr >> 40);
+ chk += (unsigned char)(ptr >> 48);
+ chk += (unsigned char)(ptr >> 56);
+#endif
+
+ return chk & (uintptr_t)0xF;
+}
+
+static INLINE uintptr_t
+free_list_checksum_ptr(szone_t *szone, void *ptr)
+{
+ uintptr_t p = (uintptr_t)ptr;
+ return p | free_list_gen_checksum(p ^ szone->cookie);
+}
+
+static INLINE void *
+free_list_unchecksum_ptr(szone_t *szone, ptr_union *ptr)
+{
+ ptr_union p;
+ p.u = (ptr->u >> 4) << 4;
+
+ if ((ptr->u & (uintptr_t)0xF) != free_list_gen_checksum(p.u ^ szone->cookie))
+ {
+ free_list_checksum_botch(szone, (free_list_t *)ptr);
+ return NULL;
+ }
+ return p.p;
+}
+
+static unsigned
+free_list_count(szone_t *szone, free_list_t *ptr)
+{
+ unsigned count = 0;
+
+ while (ptr) {
+ count++;
+ ptr = free_list_unchecksum_ptr(szone, &ptr->next);
+ }
+ return count;
+}
+
+static INLINE void
+recirc_list_extract(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node)
+{
+ // excise node from list
+ if (NULL == node->prev)
+ mag_ptr->firstNode = node->next;
+ else
+ node->prev->next = node->next;
+
+ if (NULL == node->next)
+ mag_ptr->lastNode = node->prev;
+ else
+ node->next->prev = node->prev;
+
+ mag_ptr->recirculation_entries--;
+}
+
+static INLINE void
+recirc_list_splice_last(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node)
+{
+ if (NULL == mag_ptr->lastNode) {
+ mag_ptr->firstNode = node;
+ node->prev = NULL;
+ } else {
+ node->prev = mag_ptr->lastNode;
+ mag_ptr->lastNode->next = node;
+ }
+ mag_ptr->lastNode = node;
+ node->next = NULL;
+ node->recirc_suitable = FALSE;
+ mag_ptr->recirculation_entries++;
+}
+
+static INLINE void
+recirc_list_splice_first(szone_t *szone, magazine_t *mag_ptr, region_trailer_t *node)
+{
+ if (NULL == mag_ptr->firstNode) {
+ mag_ptr->lastNode = node;
+ node->next = NULL;
+ } else {
+ node->next = mag_ptr->firstNode;
+ mag_ptr->firstNode->prev = node;
+ }
+ mag_ptr->firstNode = node;
+ node->prev = NULL;
+ node->recirc_suitable = FALSE;
+ mag_ptr->recirculation_entries++;
+}
+
+/* Macros used to manipulate the uint32_t quantity mag_bitmap. */
+
+/* BITMAPV variants are used by tiny. */
+#if defined(__LP64__)
+// assert(NUM_SLOTS == 64) in which case (slot >> 5) is either 0 or 1
+#define BITMAPV_SET(bitmap,slot) (bitmap[(slot) >> 5] |= 1 << ((slot) & 31))
+#define BITMAPV_CLR(bitmap,slot) (bitmap[(slot) >> 5] &= ~ (1 << ((slot) & 31)))
+#define BITMAPV_BIT(bitmap,slot) ((bitmap[(slot) >> 5] >> ((slot) & 31)) & 1)
+#define BITMAPV_CTZ(bitmap) (__builtin_ctzl(bitmap))
+#else
+// assert(NUM_SLOTS == 32) in which case (slot >> 5) is always 0, so code it that way
+#define BITMAPV_SET(bitmap,slot) (bitmap[0] |= 1 << (slot))
+#define BITMAPV_CLR(bitmap,slot) (bitmap[0] &= ~ (1 << (slot)))
+#define BITMAPV_BIT(bitmap,slot) ((bitmap[0] >> (slot)) & 1)
+#define BITMAPV_CTZ(bitmap) (__builtin_ctz(bitmap))
+#endif
+
+/* BITMAPN is used by small. (slot >> 5) takes on values from 0 to 7. */
+#define BITMAPN_SET(bitmap,slot) (bitmap[(slot) >> 5] |= 1 << ((slot) & 31))
+#define BITMAPN_CLR(bitmap,slot) (bitmap[(slot) >> 5] &= ~ (1 << ((slot) & 31)))
+#define BITMAPN_BIT(bitmap,slot) ((bitmap[(slot) >> 5] >> ((slot) & 31)) & 1)
+
+/* returns bit # of least-significant one bit, starting at 0 (undefined if !bitmap) */
+#define BITMAP32_CTZ(bitmap) (__builtin_ctz(bitmap[0]))
+
+/********************* 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
+
+// We store the meta-header bit arrays by interleaving them 32 bits at a time.
+// Initial 32 bits of block_header, followed by initial 32 bits of in_use, followed
+// by next 32 bits of block_header, followed by next 32 bits of in_use, etc.
+// This localizes memory references thereby reducing cache and TLB pressures.
+
+static INLINE void
+BITARRAY_SET(uint32_t *bits, msize_t index)
+{
+ // index >> 5 identifies the uint32_t to manipulate in the conceptually contiguous bits array
+ // (index >> 5) << 1 identifies the uint32_t allowing for the actual interleaving
+ bits[(index >> 5) << 1] |= (1 << (index & 31));
+}
+
+static INLINE void
+BITARRAY_CLR(uint32_t *bits, msize_t index)
+{
+ bits[(index >> 5) << 1] &= ~(1 << (index & 31));
+}
+
+static INLINE boolean_t
+BITARRAY_BIT(uint32_t *bits, msize_t index)
+{
+ return ((bits[(index >> 5) << 1]) >> (index & 31)) & 1;
+}
+
+#if 0
+static INLINE void bitarray_mclr(uint32_t *bits, unsigned start, unsigned end) ALWAYSINLINE;
+
+static INLINE void
+bitarray_mclr(uint32_t *bits, unsigned start, unsigned end)
+{
+ // start >> 5 identifies the uint32_t to manipulate in the conceptually contiguous bits array
+ // (start >> 5) << 1 identifies the uint32_t allowing for the actual interleaving
+ uint32_t *addr = bits + ((start >> 5) << 1);
+
+ uint32_t span = end - start;
+ start = start & 31;
+ end = start + span;
+
+ if (end > 31) {
+ addr[0] &= (0xFFFFFFFFU >> (31 - start)) >> 1;
+ addr[2] &= (0xFFFFFFFFU << (end - 32));
+ } else {
+ unsigned mask = (0xFFFFFFFFU >> (31 - start)) >> 1;
+ mask |= (0xFFFFFFFFU << end);
+ addr[0] &= mask;
+ }
+}
+#endif
+
+/*
+ * Obtain the size of a free tiny block (in msize_t units).
+ */
+static msize_t
+get_tiny_free_size(const void *ptr)
+{
+ void *next_block = (void *)((uintptr_t)ptr + TINY_QUANTUM);
+ void *region_end = TINY_REGION_END(TINY_REGION_FOR_PTR(ptr));
+
+ // check whether the next block is outside the tiny region or a block header
+ // if so, then the size of this block is one, and there is no stored size.
+ if (next_block < region_end)
+ {
+ uint32_t *next_header = TINY_BLOCK_HEADER_FOR_PTR(next_block);
+ msize_t next_index = TINY_INDEX_FOR_PTR(next_block);
+
+ if (!BITARRAY_BIT(next_header, next_index))
+ return TINY_FREE_SIZE(ptr);
+ }
+ return 1;
+}
+
+/*
+ * Get the size of the previous free block, which is stored in the last two
+ * bytes of the block. If the previous block is not free, then the result is
+ * undefined.
+ */
+static msize_t
+get_tiny_previous_free_msize(const void *ptr)
+{
+ // check whether the previous block is in the tiny region and a block header
+ // if so, then the size of the previous block is one, and there is no stored
+ // size.
+ if (ptr != TINY_REGION_FOR_PTR(ptr))
+ {
+ void *prev_block = (void *)((uintptr_t)ptr - TINY_QUANTUM);
+ uint32_t *prev_header = TINY_BLOCK_HEADER_FOR_PTR(prev_block);
+ msize_t prev_index = TINY_INDEX_FOR_PTR(prev_block);
+ if (BITARRAY_BIT(prev_header, prev_index))
+ return 1;
+ return TINY_PREVIOUS_MSIZE(ptr);
+ }
+ // don't read possibly unmapped memory before the beginning of the region
+ return 0;
+}
+
+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)
+ uint32_t *block_header;
+ msize_t index;
+
+ block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ index = TINY_INDEX_FOR_PTR(ptr);
+
+ msize_t midx = (index >> 5) << 1;
+ uint32_t mask = 1 << (index & 31);
+ *is_free = 0;
+ if (0 == (block_header[midx] & mask)) // if (!BITARRAY_BIT(block_header, index))
+ return 0;
+ if (0 == (block_header[midx + 1] & mask)) { // if (!BITARRAY_BIT(in_use, index))
+ *is_free = 1;
+ return get_tiny_free_size(ptr);
+ }
+
+ // index >> 5 identifies the uint32_t to manipulate in the conceptually contiguous bits array
+ // (index >> 5) << 1 identifies the uint32_t allowing for the actual interleaving
+#if defined(__LP64__)
+ // The return value, msize, is computed as the distance to the next 1 bit in block_header.
+ // That's guaranteed to be somewhwere in the next 64 bits. And those bits could span three
+ // uint32_t block_header elements. Collect the bits into a single uint64_t and measure up with ffsl.
+ uint32_t *addr = ((uint32_t *)block_header) + ((index >> 5) << 1);
+ uint32_t bitidx = index & 31;
+ uint64_t word_lo = addr[0];
+ uint64_t word_mid = addr[2];
+ uint64_t word_hi = addr[4];
+ uint64_t word_lomid = (word_lo >> bitidx) | (word_mid << (32 - bitidx));
+ uint64_t word = bitidx ? word_lomid | (word_hi << (64 - bitidx)) : word_lomid;
+ uint32_t result = __builtin_ffsl(word >> 1);
+#else
+ // The return value, msize, is computed as the distance to the next 1 bit in block_header.
+ // That's guaranteed to be somwhwere in the next 32 bits. And those bits could span two
+ // uint32_t block_header elements. Collect the bits into a single uint32_t and measure up with ffs.
+ uint32_t *addr = ((uint32_t *)block_header) + ((index >> 5) << 1);
+ uint32_t bitidx = index & 31;
+ uint32_t word = bitidx ? (addr[0] >> bitidx) | (addr[2] << (32 - bitidx)) : addr[0];
+ uint32_t result = __builtin_ffs(word >> 1);
+#endif
+ return result;
+}
+
+static INLINE void
+set_tiny_meta_header_in_use(const void *ptr, msize_t msize)
+{
+ uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ msize_t index = TINY_INDEX_FOR_PTR(ptr);
+ msize_t clr_msize = msize - 1;
+ msize_t midx = (index >> 5) << 1;
+ uint32_t val = (1 << (index & 31));
+
+#if DEBUG_MALLOC
+ if (msize >= NUM_TINY_SLOTS)
+ 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[midx] |= val; // BITARRAY_SET(block_header, index);
+ block_header[midx + 1] |= val; // BITARRAY_SET(in_use, index);
+
+ // bitarray_mclr(block_header, index, end_bit);
+ // bitarray_mclr(in_use, index, end_bit);
+
+ index++;
+ midx = (index >> 5) << 1;
+
+ unsigned start = index & 31;
+ unsigned end = start + clr_msize;
+
+#if defined(__LP64__)
+ if (end > 63) {
+ unsigned mask0 = (0xFFFFFFFFU >> (31 - start)) >> 1;
+ unsigned mask1 = (0xFFFFFFFFU << (end - 64));
+ block_header[midx + 0] &= mask0; // clear header
+ block_header[midx + 1] &= mask0; // clear in_use
+ block_header[midx + 2] = 0; // clear header
+ block_header[midx + 3] = 0; // clear in_use
+ block_header[midx + 4] &= mask1; // clear header
+ block_header[midx + 5] &= mask1; // clear in_use
+ } else
+#endif
+ if (end > 31) {
+ unsigned mask0 = (0xFFFFFFFFU >> (31 - start)) >> 1;
+ unsigned mask1 = (0xFFFFFFFFU << (end - 32));
+ block_header[midx + 0] &= mask0;
+ block_header[midx + 1] &= mask0;
+ block_header[midx + 2] &= mask1;
+ block_header[midx + 3] &= mask1;
+ } else {
+ unsigned mask = (0xFFFFFFFFU >> (31 - start)) >> 1;
+ mask |= (0xFFFFFFFFU << end);
+ block_header[midx + 0] &= mask;
+ block_header[midx + 1] &= mask;
+ }
+
+ // we set the block_header bit for the following block to reaffirm next block is a block
+ index += clr_msize;
+ midx = (index >> 5) << 1;
+ val = (1 << (index & 31));
+ block_header[midx] |= val; // BITARRAY_SET(block_header, (index+clr_msize));
+#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_in_use_1(const void *ptr) // As above with msize == 1
+{
+ uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ msize_t index = TINY_INDEX_FOR_PTR(ptr);
+ msize_t midx = (index >> 5) << 1;
+ uint32_t val = (1 << (index & 31));
+
+ block_header[midx] |= val; // BITARRAY_SET(block_header, index);
+ block_header[midx + 1] |= val; // BITARRAY_SET(in_use, index);
+
+ index++;
+ midx = (index >> 5) << 1;
+ val = (1 << (index & 31));
+
+ block_header[midx] |= val; // BITARRAY_SET(block_header, (index+clr_msize))
+}
+
+static INLINE void
+set_tiny_meta_header_middle(const void *ptr)
+{
+ // indicates this block is in the middle of an in use block
+ uint32_t *block_header;
+ uint32_t *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);
+}
+
+static INLINE void
+set_tiny_meta_header_free(const void *ptr, msize_t msize)
+{
+ // !msize is acceptable and means 65536
+ uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
+ msize_t index = TINY_INDEX_FOR_PTR(ptr);
+ msize_t midx = (index >> 5) << 1;
+ uint32_t val = (1 << (index & 31));
+
+#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
+
+ block_header[midx] |= val; // BITARRAY_SET(block_header, index);
+ block_header[midx + 1] &= ~val; // BITARRAY_CLR(in_use, index);
+
+ // mark the end of this block if msize is > 1. For msize == 0, the whole
+ // region is free, so there is no following block. For msize == 1, there is
+ // no space to write the size on 64 bit systems. The size for 1 quantum
+ // blocks is computed from the metadata bitmaps.
+ if (msize > 1) {
+ void *follower = FOLLOWING_TINY_PTR(ptr, msize);
+ TINY_PREVIOUS_MSIZE(follower) = msize;
+ TINY_FREE_SIZE(ptr) = msize;
+ }
+ if (msize == 0) {
+ TINY_FREE_SIZE(ptr) = 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 : %u\n", ptr, msize);
+ malloc_printf("reading header for tiny %p : %u %u\n", ptr, mf, ff);
+ }
+#endif
+}
+
+static INLINE boolean_t
+tiny_meta_header_is_free(const void *ptr)
+{
+ uint32_t *block_header;
+ uint32_t *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
+ uint32_t *block_header;
+ uint32_t *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 = get_tiny_previous_free_msize(ptr)) > index)
+ return NULL;
+
+ previous_index = index - previous_msize;
+ previous_ptr = (void *)((uintptr_t)TINY_REGION_FOR_PTR(ptr) + TINY_BYTES_FOR_MSIZE(previous_index));
+ if (!BITARRAY_BIT(block_header, previous_index))
+ return NULL;
+ if (BITARRAY_BIT(in_use, previous_index))
+ return NULL;
+ if (get_tiny_free_size(previous_ptr) != previous_msize)
+ return NULL;
+
+ // conservative check did match true check
+ *prev_msize = previous_msize;
+ return previous_ptr;
+}
+
+/*
+ * Adds an item to the proper free list, and also marks the meta-header of the
+ * block properly.
+ * Assumes szone has been locked
+ */
+static void
+tiny_free_list_add_ptr(szone_t *szone, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize)
+{
+ 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 = tiny_mag_ptr->mag_free_list[slot];
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in %s, ptr=%p, msize=%d\n", __FUNCTION__, ptr, msize);
+ }
+ if (((uintptr_t)ptr) & (TINY_QUANTUM - 1)) {
+ szone_error(szone, 1, "tiny_free_list_add_ptr: Unaligned ptr", ptr, NULL);
+ }
+#endif
+ set_tiny_meta_header_free(ptr, msize);
+ if (free_head) {
+#if DEBUG_MALLOC
+ if (free_list_unchecksum_ptr(szone, &free_head->previous)) {
+ szone_error(szone, 1, "tiny_free_list_add_ptr: Internal invariant broken (free_head->previous)", ptr,
+ "ptr=%p slot=%d free_head=%p previous=%p\n", ptr, slot, (void *)free_head, free_head->previous.p);
+ }
+ if (! tiny_meta_header_is_free(free_head)) {
+ szone_error(szone, 1, "tiny_free_list_add_ptr: Internal invariant broken (free_head is not a free pointer)", ptr,
+ "ptr=%p slot=%d free_head=%p\n", ptr, slot, (void *)free_head);
+ }
+#endif
+ free_head->previous.u = free_list_checksum_ptr(szone, free_ptr);
+ } else {
+ BITMAPV_SET(tiny_mag_ptr->mag_bitmap, slot);
+ }
+ free_ptr->previous.u = free_list_checksum_ptr(szone, NULL);
+ free_ptr->next.u = free_list_checksum_ptr(szone, free_head);
+
+ tiny_mag_ptr->mag_free_list[slot] = free_ptr;
+}
+
+/*
+ * Removes the item pointed to by ptr in the proper free list.
+ * Assumes szone has been locked
+ */
+static void
+tiny_free_list_remove_ptr(szone_t *szone, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize)
+{
+ grain_t slot = (!msize || (msize >= NUM_TINY_SLOTS)) ? NUM_TINY_SLOTS - 1 : msize - 1;
+ free_list_t *free_ptr = ptr, *next, *previous;
+
+ next = free_list_unchecksum_ptr(szone, &free_ptr->next);
+ previous = free_list_unchecksum_ptr(szone, &free_ptr->previous);
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("In %s, ptr=%p, msize=%d\n", __FUNCTION__, ptr, msize);
+ }
+#endif
+ if (!previous) {
+ // The block to remove is the head of the free list
+#if DEBUG_MALLOC
+ if (tiny_mag_ptr->mag_free_list[slot] != ptr) {
+ szone_error(szone, 1, "tiny_free_list_remove_ptr: Internal invariant broken (tiny_mag_ptr->mag_free_list[slot])", ptr,
+ "ptr=%p slot=%d msize=%d tiny_mag_ptr->mag_free_list[slot]=%p\n",
+ ptr, slot, msize, (void *)tiny_mag_ptr->mag_free_list[slot]);
+ return;
+ }
+#endif
+ tiny_mag_ptr->mag_free_list[slot] = next;
+ if (!next) BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
+ } else {
+ // We know free_ptr is already checksummed, so we don't need to do it
+ // again.
+ previous->next = free_ptr->next;
+ }
+ if (next) {
+ // We know free_ptr is already checksummed, so we don't need to do it
+ // again.
+ next->previous = free_ptr->previous;
+ }
+}
+
+/*
+ * tiny_region_for_ptr_no_lock - Returns the tiny region containing the pointer,
+ * or NULL if not found.
+ */
+static INLINE region_t
+tiny_region_for_ptr_no_lock(szone_t *szone, const void *ptr)
+{
+ rgnhdl_t r = hash_lookup_region_no_lock(szone->tiny_region_generation->hashed_regions,
+ szone->tiny_region_generation->num_regions_allocated,
+ szone->tiny_region_generation->num_regions_allocated_shift,
+ TINY_REGION_FOR_PTR(ptr));
+ return r ? *r : r;
+}
+
+static void
+tiny_finalize_region(szone_t *szone, magazine_t *tiny_mag_ptr) {
+ void *last_block, *previous_block;
+ uint32_t *last_header;
+ msize_t last_msize, previous_msize, last_index;
+
+ last_block = (void *)
+ ((uintptr_t)TINY_REGION_END(tiny_mag_ptr->mag_last_region) - tiny_mag_ptr->mag_bytes_free_at_end);
+ last_msize = TINY_MSIZE_FOR_BYTES(tiny_mag_ptr->mag_bytes_free_at_end);
+ last_header = TINY_BLOCK_HEADER_FOR_PTR(last_block);
+ last_index = TINY_INDEX_FOR_PTR(last_block);
+
+ // Before anything we transform any remaining mag_bytes_free_at_end into a
+ // regular free block. We take special care here to update the bitfield
+ // information, since we are bypassing the normal free codepath. If there
+ // is more than one quanta worth of memory in mag_bytes_free_at_end, then
+ // there will be two block headers:
+ // 1) header for the free space at end, msize = 1
+ // 2) header inserted by set_tiny_meta_header_in_use after block
+ // We must clear the second one so that when the free block's size is
+ // queried, we do not think the block is only 1 quantum in size because
+ // of the second set header bit.
+ if (last_index != (NUM_TINY_BLOCKS - 1))
+ BITARRAY_CLR(last_header, (last_index + 1));
+
+ // It is possible that the block prior to the last block in the region has
+ // been free'd, but was not coalesced with the free bytes at the end of the
+ // block, since we treat the bytes at the end of the region as "in use" in
+ // the meta headers. Attempt to coalesce the last block with the previous
+ // block, so we don't violate the "no consecutive free blocks" invariant.
+ //
+ // FIXME: Need to investigate how much work would be required to increase
+ // 'mag_bytes_free_at_end' when freeing the preceding block, rather
+ // than performing this workaround.
+ //
+ previous_block = tiny_previous_preceding_free(last_block, &previous_msize);
+ if (previous_block) {
+ set_tiny_meta_header_middle(last_block);
+ tiny_free_list_remove_ptr(szone, tiny_mag_ptr, previous_block, previous_msize);
+ last_block = previous_block;
+ last_msize += previous_msize;
+ }
+
+ // splice last_block into the free list
+ tiny_free_list_add_ptr(szone, tiny_mag_ptr, last_block, last_msize);
+ tiny_mag_ptr->mag_bytes_free_at_end = 0;
+ tiny_mag_ptr->mag_last_region = NULL;
+}
+
+static int
+tiny_free_detach_region(szone_t *szone, magazine_t *tiny_mag_ptr, region_t r) {
+ uintptr_t start = (uintptr_t)TINY_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)TINY_REGION_END(r);
+ boolean_t is_free;
+ msize_t msize;
+ int total_alloc = 0;
+
+ while (current < limit) {
+ msize = get_tiny_meta_header((void *)current, &is_free);
+ if (is_free && !msize && (current == start)) {
+ // first block is all free
+ break;
+ }
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** tiny_free_detach_region error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ tiny_free_list_remove_ptr(szone, tiny_mag_ptr, (void *)current, msize);
+ } else {
+ total_alloc++;
+ }
+ current += TINY_BYTES_FOR_MSIZE(msize);
+ }
+ return total_alloc;
+}
+
+static size_t
+tiny_free_reattach_region(szone_t *szone, magazine_t *tiny_mag_ptr, region_t r) {
+ uintptr_t start = (uintptr_t)TINY_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)TINY_REGION_END(r);
+ boolean_t is_free;
+ msize_t msize;
+ size_t total_alloc = 0;
+
+ while (current < limit) {
+ msize = get_tiny_meta_header((void *)current, &is_free);
+ if (is_free && !msize && (current == start)) {
+ // first block is all free
+ break;
+ }
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** tiny_free_reattach_region error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ tiny_free_list_add_ptr(szone, tiny_mag_ptr, (void *)current, msize);
+ } else {
+ total_alloc += TINY_BYTES_FOR_MSIZE(msize);
+ }
+ current += TINY_BYTES_FOR_MSIZE(msize);
+ }
+ return total_alloc;
+}
+
+static void
+tiny_free_scan_madvise_free(szone_t *szone, magazine_t *depot_ptr, region_t r) {
+ uintptr_t start = (uintptr_t)TINY_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)TINY_REGION_END(r);
+ boolean_t is_free;
+ msize_t msize;
+ boolean_t did_advise = FALSE;
+
+ // Scan the metadata identifying blocks which span one or more pages. Mark the pages MADV_FREE taking care to preserve free list
+ // management data.
+ while (current < limit) {
+ msize = get_tiny_meta_header((void *)current, &is_free);
+ if (is_free && !msize && (current == start)) {
+ // first block is all free
+#if DEBUG_MALLOC
+ malloc_printf("*** tiny_free_scan_madvise_free first block is all free! %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ uintptr_t pgLo = round_page(start + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(start + TINY_REGION_SIZE - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ madvise_free_range(szone, r, pgLo, pgHi);
+ did_advise = TRUE;
+ }
+ break;
+ }
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** tiny_free_scan_madvise_free error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ uintptr_t pgLo = round_page(current + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(current + TINY_BYTES_FOR_MSIZE(msize) - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ madvise_free_range(szone, r, pgLo, pgHi);
+ did_advise = TRUE;
+ }
+ }
+ current += TINY_BYTES_FOR_MSIZE(msize);
+ }
+
+ if (did_advise) {
+ /* Move the node to the tail of the Deopt's recirculation list to delay its re-use. */
+ region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(r);
+ recirc_list_extract(szone, depot_ptr, node); // excise node from list
+ recirc_list_splice_last(szone, depot_ptr, node); // connect to magazine as last node
+ }
+}
+
+static void
+tiny_free_try_depot_unmap_no_lock(szone_t *szone, magazine_t *depot_ptr, region_trailer_t *node)
+{
+#warning Tune Depot headroom
+ if (0 < node->bytes_used ||
+ depot_ptr->recirculation_entries < (szone->num_tiny_magazines * 2)) {
+ return;
+ }
+
+ // disconnect node from Depot
+ recirc_list_extract(szone, depot_ptr, node);
+
+ // Iterate the region pulling its free entries off the (locked) Depot's free list
+ region_t sparse_region = TINY_REGION_FOR_PTR(node);
+ int objects_in_use = tiny_free_detach_region(szone, depot_ptr, sparse_region);
+
+ if (0 == objects_in_use) {
+ // Invalidate the hash table entry for this region with HASHRING_REGION_DEALLOCATED.
+ // Using HASHRING_REGION_DEALLOCATED preserves the collision chain, using HASHRING_OPEN_ENTRY (0) would not.
+ rgnhdl_t pSlot = hash_lookup_region_no_lock(szone->tiny_region_generation->hashed_regions,
+ szone->tiny_region_generation->num_regions_allocated,
+ szone->tiny_region_generation->num_regions_allocated_shift, sparse_region);
+ *pSlot = HASHRING_REGION_DEALLOCATED;
+ depot_ptr->num_bytes_in_magazine -= TINY_REGION_PAYLOAD_BYTES;
+#if ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 1))) /* GCC 4.1 and forward supports atomic builtins */
+ __sync_fetch_and_add( &(szone->num_tiny_regions_dealloc), 1); // Atomically increment num_tiny_regions_dealloc
+#else
+#ifdef __LP64__
+ OSAtomicIncrement64( (volatile int64_t *)&(szone->num_tiny_regions_dealloc) );
+#else
+ OSAtomicIncrement32( (volatile int32_t *)&(szone->num_tiny_regions_dealloc) );
+#endif
+#endif
+
+ // Transfer ownership of the region back to the OS
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, depot_ptr); // Avoid denial of service to Depot while in kernel
+ deallocate_pages(szone, sparse_region, TINY_REGION_SIZE, 0);
+ SZONE_MAGAZINE_PTR_LOCK(szone, depot_ptr);
+
+ MAGMALLOC_DEALLOCREGION((void *)szone, (void *)sparse_region); // DTrace USDT Probe
+
+ } else {
+ szone_error(szone, 1, "tiny_free_try_depot_unmap_no_lock objects_in_use not zero:", NULL, "%d\n", objects_in_use);
+ }
+}
+
+static void
+tiny_free_do_recirc_to_depot(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index)
+{
+ // The entire magazine crossed the "emptiness threshold". Transfer a region
+ // from this magazine to the Depot. Choose a region that itself has crossed the emptiness threshold (i.e
+ // is at least fraction "f" empty.) Such a region will be marked "suitable" on the recirculation list.
+ region_trailer_t *node = tiny_mag_ptr->firstNode;
+
+ while (node && !node->recirc_suitable) {
+ node = node->next;
+ }
+
+ if (NULL == node) {
+#if DEBUG_MALLOC
+ malloc_printf("*** tiny_free_do_recirc_to_depot end of list\n");
+#endif
+ return;
+ }
+
+ region_t sparse_region = TINY_REGION_FOR_PTR(node);
+
+ // Deal with unclaimed memory -- mag_bytes_free_at_end
+ if (sparse_region == tiny_mag_ptr->mag_last_region && tiny_mag_ptr->mag_bytes_free_at_end) {
+ tiny_finalize_region(szone, tiny_mag_ptr);
+ }
+
+ // disconnect "suitable" node from magazine
+ recirc_list_extract(szone, tiny_mag_ptr, node);
+
+ // Iterate the region pulling its free entries off its (locked) magazine's free list
+ int objects_in_use = tiny_free_detach_region(szone, tiny_mag_ptr, sparse_region);
+ magazine_t *depot_ptr = &(szone->tiny_magazines[DEPOT_MAGAZINE_INDEX]);
+
+ // hand over the region to the (locked) Depot
+ SZONE_MAGAZINE_PTR_LOCK(szone,depot_ptr);
+ // this will cause tiny_free_list_add_ptr called by tiny_free_reattach_region to use
+ // the depot as its target magazine, rather than magazine formerly associated with sparse_region
+ MAGAZINE_INDEX_FOR_TINY_REGION(sparse_region) = DEPOT_MAGAZINE_INDEX;
+
+ // Iterate the region putting its free entries on Depot's free list
+ size_t bytes_inplay = tiny_free_reattach_region(szone, depot_ptr, sparse_region);
+
+ tiny_mag_ptr->mag_num_bytes_in_objects -= bytes_inplay;
+ tiny_mag_ptr->num_bytes_in_magazine -= TINY_REGION_PAYLOAD_BYTES;
+ tiny_mag_ptr->mag_num_objects -= objects_in_use;
+
+ depot_ptr->mag_num_bytes_in_objects += bytes_inplay;
+ depot_ptr->num_bytes_in_magazine += TINY_REGION_PAYLOAD_BYTES;
+ depot_ptr->mag_num_objects += objects_in_use;
+
+ // connect to Depot as first (MRU) node
+ recirc_list_splice_first(szone, depot_ptr, node);
+
+ MAGMALLOC_RECIRCREGION((void *)szone, (int)mag_index, (int)BYTES_USED_FOR_TINY_REGION(sparse_region)); // DTrace USDT Probe
+
+ // Mark free'd dirty pages with MADV_FREE to reduce memory pressure
+ tiny_free_scan_madvise_free(szone, depot_ptr, sparse_region);
+
+ // If the region is entirely empty vm_deallocate() it
+ tiny_free_try_depot_unmap_no_lock(szone, depot_ptr, node);
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+}
+
+static boolean_t
+tiny_get_region_from_depot(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index)
+{
+ magazine_t *depot_ptr = &(szone->tiny_magazines[DEPOT_MAGAZINE_INDEX]);
+
+ /* FIXME: Would Uniprocessor benefit from recirc and MADV_FREE? */
+ if (szone->num_tiny_magazines == 1) // Uniprocessor, single magazine, so no recirculation necessary
+ return 0;
+
+#if DEBUG_MALLOC
+ if (DEPOT_MAGAZINE_INDEX == mag_index) {
+ szone_error(szone, 1, "tiny_get_region_from_depot called for magazine index -1", NULL, NULL);
+ return 0;
+ }
+#endif
+
+ SZONE_MAGAZINE_PTR_LOCK(szone,depot_ptr);
+
+ // Appropriate one of the Depot's regions. Prefer LIFO selection for best cache utilization.
+ region_trailer_t *node = depot_ptr->firstNode;
+
+ if (NULL == node) { // Depot empty?
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+ return 0;
+ }
+
+ // disconnect first node from Depot
+ recirc_list_extract(szone, depot_ptr, node);
+
+ // Iterate the region pulling its free entries off the (locked) Depot's free list
+ region_t sparse_region = TINY_REGION_FOR_PTR(node);
+ int objects_in_use = tiny_free_detach_region(szone, depot_ptr, sparse_region);
+
+ // Transfer ownership of the region
+ MAGAZINE_INDEX_FOR_TINY_REGION(sparse_region) = mag_index;
+
+ // Iterate the region putting its free entries on its new (locked) magazine's free list
+ size_t bytes_inplay = tiny_free_reattach_region(szone, tiny_mag_ptr, sparse_region);
+
+ depot_ptr->mag_num_bytes_in_objects -= bytes_inplay;
+ depot_ptr->num_bytes_in_magazine -= TINY_REGION_PAYLOAD_BYTES;
+ depot_ptr->mag_num_objects -= objects_in_use;
+
+ tiny_mag_ptr->mag_num_bytes_in_objects += bytes_inplay;
+ tiny_mag_ptr->num_bytes_in_magazine += TINY_REGION_PAYLOAD_BYTES;
+ tiny_mag_ptr->mag_num_objects += objects_in_use;
+
+ // connect to magazine as first node (it's maximally sparse at this moment)
+ recirc_list_splice_first(szone, tiny_mag_ptr, node);
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+
+ MAGMALLOC_DEPOTREGION((void *)szone, (int)mag_index, (int)BYTES_USED_FOR_TINY_REGION(sparse_region)); // DTrace USDT Probe
+
+ if (-1 == madvise((void *)sparse_region, TINY_REGION_PAYLOAD_BYTES, MADV_FREE_REUSE)) {
+ /* -1 return: VM map entry change makes this unfit for reuse. Something evil lurks. */
+#if DEBUG_MALLOC
+ szone_error(szone, 1, "tiny_get_region_from_depot madvise(..., MADV_FREE_REUSE) failed", sparse_region, NULL);
+#endif
+ return 0;
+ }
+
+ return 1;
+}
+
+#warning Tune K and f!
+#define K 1.5 // headroom measured in number of 1Mb regions
+#define DENSITY_THRESHOLD(a) \
+ ((a) - ((a) >> 2)) // "Emptiness" f = 0.25, so "Density" is (1 - f)*a. Generally: ((a) - ((a) >> -log2(f)))
+
+static INLINE void
+tiny_free_no_lock(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index, region_t region, void *ptr,
+ msize_t msize)
+{
+ void *original_ptr = ptr;
+ size_t original_size = TINY_BYTES_FOR_MSIZE(msize);
+ void *next_block = ((unsigned char *)ptr + original_size);
+ msize_t previous_msize, next_msize;
+ void *previous;
+ free_list_t *big_free_block;
+ free_list_t *after_next_block;
+ free_list_t *before_next_block;
+ boolean_t did_prepend = FALSE;
+ boolean_t did_append = FALSE;
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+ if (! msize) {
+ szone_error(szone, 1, "trying to free tiny block that is too small", ptr,
+ "in tiny_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+#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
+ did_prepend = TRUE;
+
+ // clear the meta_header since this is no longer the start of a block
+ set_tiny_meta_header_middle(ptr);
+ tiny_free_list_remove_ptr(szone, tiny_mag_ptr, 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)) {
+ did_append = TRUE;
+ next_msize = get_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 we are coalescing with the next block, and the next block is in
+ // the last slot of the free list, then we optimize this case here to
+ // avoid removing next_block from the slot (NUM_TINY_SLOTS - 1) and then adding ptr back
+ // to slot (NUM_TINY_SLOTS - 1).
+ if (next_msize >= NUM_TINY_SLOTS) {
+ msize += next_msize;
+
+ big_free_block = (free_list_t *)next_block;
+ after_next_block = free_list_unchecksum_ptr(szone, &big_free_block->next);
+ before_next_block = free_list_unchecksum_ptr(szone, &big_free_block->previous);
+
+ if (!before_next_block) {
+ tiny_mag_ptr->mag_free_list[NUM_TINY_SLOTS-1] = ptr;
+ } else {
+ before_next_block->next.u = free_list_checksum_ptr(szone, ptr);
+ }
+
+ if (after_next_block) {
+ after_next_block->previous.u = free_list_checksum_ptr(szone, ptr);
+ }
+
+ // we don't need to checksum these since they are already checksummed
+ ((free_list_t *)ptr)->previous = big_free_block->previous;
+ ((free_list_t *)ptr)->next = big_free_block->next;
+
+ // clear the meta_header to enable coalescing backwards
+ set_tiny_meta_header_middle(big_free_block);
+ set_tiny_meta_header_free(ptr, msize);
+
+ goto tiny_free_ending;
+ }
+ tiny_free_list_remove_ptr(szone, tiny_mag_ptr, next_block, next_msize);
+ set_tiny_meta_header_middle(next_block); // clear the meta_header to enable coalescing backwards
+ msize += next_msize;
+ }
+#if !TINY_CACHE
+ // The tiny cache already scribbles free blocks as they go through the
+ // cache, so we do not need to do it here.
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) && msize)
+ memset(ptr, 0x55, TINY_BYTES_FOR_MSIZE(msize));
+
+#endif
+ tiny_free_list_add_ptr(szone, tiny_mag_ptr, ptr, msize);
+ tiny_free_ending:
+ // When in proper debug mode we write on the memory to help debug memory smashers
+
+ tiny_mag_ptr->mag_num_objects--;
+ // we use original_size and not msize to avoid double counting the coalesced blocks
+ tiny_mag_ptr->mag_num_bytes_in_objects -= original_size;
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(region);
+ size_t bytes_used = node->bytes_used - original_size;
+ node->bytes_used = bytes_used;
+
+ /* FIXME: Would Uniprocessor benefit from recirc and MADV_FREE? */
+ if (szone->num_tiny_magazines == 1) { // Uniprocessor, single magazine, so no recirculation necessary
+ /* NOTHING */
+ } else if (DEPOT_MAGAZINE_INDEX != mag_index) {
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(TINY_REGION_PAYLOAD_BYTES)) {
+ /* Region has crossed threshold from density to sparsity. Mark it "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = TRUE;
+ } else {
+ /* After this free, we've found the region is still dense, so it must have been even more so before
+ the free. That implies the region is already correctly marked. Do nothing. */
+ }
+
+ // Has the entire magazine crossed the "emptiness threshold"? If so, transfer a region
+ // from this magazine to the Depot. Choose a region that itself has crossed the emptiness threshold (i.e
+ // is at least fraction "f" empty.) Such a region will be marked "suitable" on the recirculation list.
+ size_t a = tiny_mag_ptr->num_bytes_in_magazine; // Total bytes allocated to this magazine
+ size_t u = tiny_mag_ptr->mag_num_bytes_in_objects; // In use (malloc'd) from this magaqzine
+
+ if (a - u > ((3 * TINY_REGION_PAYLOAD_BYTES) / 2) && u < DENSITY_THRESHOLD(a))
+ tiny_free_do_recirc_to_depot(szone, tiny_mag_ptr, mag_index);
+
+ } else {
+ // Freed to Depot. N.B. Lock on tiny_magazines[DEPOT_MAGAZINE_INDEX] is already held
+ uintptr_t safe_ptr = (uintptr_t)ptr + sizeof(free_list_t) + sizeof(msize_t);
+ uintptr_t round_safe = round_page(safe_ptr);
+
+ uintptr_t safe_extent = (uintptr_t)ptr + TINY_BYTES_FOR_MSIZE(msize) - sizeof(msize_t);
+ uintptr_t trunc_extent = trunc_page(safe_extent);
+
+ // The newly freed block may complete a span of bytes that cover a page. Mark it with MADV_FREE.
+ if (round_safe < trunc_extent) { // Safe area covers a page
+ if (did_prepend & did_append) { // Coalesced preceding with original_ptr *and* with following
+ uintptr_t trunc_safe_prev = trunc_page((uintptr_t)original_ptr - sizeof(msize_t));
+ uintptr_t rnd_safe_follow =
+ round_page((uintptr_t)original_ptr + original_size + sizeof(free_list_t) + sizeof(msize_t));
+
+ madvise_free_range(szone, region, MAX(round_safe, trunc_safe_prev), MIN(rnd_safe_follow, trunc_extent));
+ } else if (did_prepend) { // Coalesced preceding with original_ptr
+ uintptr_t trunc_safe_prev = trunc_page((uintptr_t)original_ptr - sizeof(msize_t));
+
+ madvise_free_range(szone, region, MAX(round_safe, trunc_safe_prev), trunc_extent);
+ } else if (did_append) { // Coalesced original_ptr with following
+ uintptr_t rnd_safe_follow =
+ round_page((uintptr_t)original_ptr + original_size + sizeof(free_list_t) + sizeof(msize_t));
+
+ madvise_free_range(szone, region, round_safe, MIN(rnd_safe_follow, trunc_extent));
+ } else { // Isolated free cannot exceed 496 bytes, thus round_safe == trunc_extent, and so never get here.
+ /* madvise_free_range(szone, region, round_safe, trunc_extent); */
+ }
+ }
+
+ if (0 < bytes_used) {
+ /* Depot'd region is still live. Leave it in place on the Depot's recirculation list
+ so as to avoid thrashing between the Depot's free list and a magazines's free list
+ with detach_region/reattach_region */
+ } else {
+ /* Depot'd region is just now empty. Consider return to OS. */
+ region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(region);
+ magazine_t *depot_ptr = &(szone->tiny_magazines[DEPOT_MAGAZINE_INDEX]);
+ tiny_free_try_depot_unmap_no_lock(szone, depot_ptr, node); // FIXME: depot_ptr is simply tiny_mag_ptr?
+ }
+ }
+}
+
+// Allocates from the last region or a freshly allocated region
+static void *
+tiny_malloc_from_region_no_lock(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
+{
+ void *ptr, *aligned_address;
+
+ // Deal with unclaimed memory -- mag_bytes_free_at_end
+ if (tiny_mag_ptr->mag_bytes_free_at_end)
+ tiny_finalize_region(szone, tiny_mag_ptr);
+
+ // time to create a new region
+ aligned_address = allocate_pages(szone, TINY_REGION_SIZE, TINY_BLOCKS_ALIGN, 0, VM_MEMORY_MALLOC_TINY);
+ if (!aligned_address) // out of memory!
+ return NULL;
+
+ MAGMALLOC_ALLOCREGION((void *)szone, (int)mag_index); // DTrace USDT Probe
+
+ // We set the unused bits of the header in the last pair to be all ones, and those of the inuse to zeroes.
+ ((tiny_region_t)aligned_address)->pairs[CEIL_NUM_TINY_BLOCKS_WORDS-1].header =
+ (NUM_TINY_BLOCKS & 31) ? (0xFFFFFFFFU << (NUM_TINY_BLOCKS & 31)) : 0;
+ ((tiny_region_t)aligned_address)->pairs[CEIL_NUM_TINY_BLOCKS_WORDS-1].inuse = 0;
+
+ // Here find the only place in tinyland that (infrequently) takes the tiny_regions_lock.
+ // Only one thread at a time should be permitted to assess the density of the hash
+ // ring and adjust if needed.
+ // Only one thread at a time should be permitted to insert its new region on
+ // the hash ring.
+ // It is safe for all other threads to read the hash ring (hashed_regions) and
+ // the associated sizes (num_regions_allocated and num_tiny_regions).
+
+ LOCK(szone->tiny_regions_lock);
+
+ // Check to see if the hash ring of tiny regions needs to grow. Try to
+ // avoid the hash ring becoming too dense.
+ if (szone->tiny_region_generation->num_regions_allocated < (2 * szone->num_tiny_regions)) {
+ region_t *new_regions;
+ size_t new_size;
+ size_t new_shift = szone->tiny_region_generation->num_regions_allocated_shift; // In/Out parameter
+ new_regions = hash_regions_grow_no_lock(szone, szone->tiny_region_generation->hashed_regions,
+ szone->tiny_region_generation->num_regions_allocated,
+ &new_shift,
+ &new_size);
+ // Do not deallocate the current hashed_regions allocation since someone may
+ // be iterating it. Instead, just leak it.
+
+ // Prepare to advance to the "next generation" of the hash ring.
+ szone->tiny_region_generation->nextgen->hashed_regions = new_regions;
+ szone->tiny_region_generation->nextgen->num_regions_allocated = new_size;
+ szone->tiny_region_generation->nextgen->num_regions_allocated_shift = new_shift;
+
+ // Throw the switch to atomically advance to the next generation.
+ szone->tiny_region_generation = szone->tiny_region_generation->nextgen;
+ // Ensure everyone sees the advance.
+#if ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 1))) /* GCC 4.1 and forward supports atomic builtins */
+ __sync_synchronize();
+#else
+ OSMemoryBarrier();
+#endif
+ }
+ // Tag the region at "aligned_address" as belonging to us,
+ // and so put it under the protection of the magazine lock we are holding.
+ // Do this before advertising "aligned_address" on the hash ring(!)
+ MAGAZINE_INDEX_FOR_TINY_REGION(aligned_address) = mag_index;
+
+ // Insert the new region into the hash ring, and update malloc statistics
+ hash_region_insert_no_lock(szone->tiny_region_generation->hashed_regions,
+ szone->tiny_region_generation->num_regions_allocated,
+ szone->tiny_region_generation->num_regions_allocated_shift,
+ aligned_address);
+
+ szone->num_tiny_regions++;
+ UNLOCK(szone->tiny_regions_lock);
+
+ tiny_mag_ptr->mag_last_region = aligned_address;
+ BYTES_USED_FOR_TINY_REGION(aligned_address) = TINY_BYTES_FOR_MSIZE(msize);
+ ptr = aligned_address;
+ set_tiny_meta_header_in_use(ptr, msize);
+ tiny_mag_ptr->mag_num_objects++;
+ tiny_mag_ptr->mag_num_bytes_in_objects += TINY_BYTES_FOR_MSIZE(msize);
+ tiny_mag_ptr->num_bytes_in_magazine += TINY_REGION_PAYLOAD_BYTES;
+
+ // We put a header on the last block so that it appears in use (for coalescing, etc...)
+ set_tiny_meta_header_in_use_1((void *)((uintptr_t)ptr + TINY_BYTES_FOR_MSIZE(msize)));
+ tiny_mag_ptr->mag_bytes_free_at_end = TINY_BYTES_FOR_MSIZE(NUM_TINY_BLOCKS - msize);
+
+ // connect to magazine as first node (it's maximally sparse at this moment)
+ recirc_list_splice_first(szone, tiny_mag_ptr, REGION_TRAILER_FOR_TINY_REGION(aligned_address));
+
+#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
+tiny_try_realloc_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;
+
+ magazine_t *tiny_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->tiny_magazines,
+ REGION_TRAILER_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr)),
+ MAGAZINE_INDEX_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr)));
+
+ /*
+ * Look for a free block immediately afterwards. If it's large enough, we can consume (part of)
+ * it.
+ */
+ is_free = tiny_meta_header_is_free(next_block);
+ if (!is_free) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,tiny_mag_ptr);
+ return 0; // next_block is in use;
+ }
+ next_msize = get_tiny_free_size(next_block);
+ if (old_size + TINY_BYTES_FOR_MSIZE(next_msize) < new_size) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,tiny_mag_ptr);
+ return 0; // even with next block, not enough
+ }
+ /*
+ * The following block is big enough; pull it from its freelist and chop off enough to satisfy
+ * our needs.
+ */
+ tiny_free_list_remove_ptr(szone, tiny_mag_ptr, 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) {
+ /* there's some left, so put the remainder back */
+ leftover = (void *)((uintptr_t)next_block + TINY_BYTES_FOR_MSIZE(coalesced_msize));
+
+ tiny_free_list_add_ptr(szone, tiny_mag_ptr, leftover, leftover_msize);
+ }
+ set_tiny_meta_header_in_use(ptr, old_msize + coalesced_msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_try_realloc_in_place(), ptr=%p, msize=%d\n", ptr, old_msize + coalesced_msize);
+ }
+#endif
+ tiny_mag_ptr->mag_num_bytes_in_objects += TINY_BYTES_FOR_MSIZE(coalesced_msize);
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr));
+ size_t bytes_used = node->bytes_used + TINY_BYTES_FOR_MSIZE(coalesced_msize);
+ node->bytes_used = bytes_used;
+
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(TINY_REGION_PAYLOAD_BYTES)) {
+ /* After this reallocation the region is still sparse, so it must have been even more so before
+ the reallocation. That implies the region is already correctly marked. Do nothing. */
+ } else {
+ /* Region has crossed threshold from sparsity to density. Mark it not "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = FALSE;
+ }
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return 1;
+}
+
+static boolean_t
+tiny_check_region(szone_t *szone, region_t region)
+{
+ uintptr_t start, ptr, region_end;
+ boolean_t prev_free = 0;
+ boolean_t is_free;
+ msize_t msize;
+ free_list_t *free_head;
+ void *follower, *previous, *next;
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(region);
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+
+ // Assumes locked
+ CHECK_MAGAZINE_PTR_LOCKED(szone, tiny_mag_ptr, __PRETTY_FUNCTION__);
+
+ /* 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 == tiny_mag_ptr->mag_last_region)
+ region_end -= tiny_mag_ptr->mag_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 (NUM_TINY_SLOTS - 1) quanta large.
+ */
+ prev_free = 0;
+ if (msize > (NUM_TINY_SLOTS - 1)) {
+ malloc_printf("*** invariant broken for %p this tiny msize=%d - size is too large\n",
+ ptr, 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;
+ previous = free_list_unchecksum_ptr(szone, &free_head->previous);
+ next = free_list_unchecksum_ptr(szone, &free_head->next);
+ if (previous && !tiny_meta_header_is_free(previous)) {
+ malloc_printf("*** invariant broken for %p (previous %p is not a free pointer)\n",
+ ptr, previous);
+ return 0;
+ }
+ if (next && !tiny_meta_header_is_free(next)) {
+ malloc_printf("*** invariant broken for %p (next in free list %p is not a free pointer)\n",
+ ptr, next);
+ return 0;
+ }
+ /*
+ * Check the free block's trailing size value.
+ */
+ follower = FOLLOWING_TINY_PTR(ptr, msize);
+ if (((uintptr_t)follower != region_end) && (get_tiny_previous_free_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, get_tiny_previous_free_msize(follower));
+ return 0;
+ }
+ /* move to next block */
+ ptr = (uintptr_t)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 == tiny_mag_ptr->mag_last_region) {
+ if (tiny_mag_ptr->mag_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, szone_t *szone,
+ memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ size_t num_regions;
+ size_t index;
+ region_t *regions;
+ vm_range_t buffer[MAX_RECORDER_BUFFER];
+ unsigned count = 0;
+ kern_return_t err;
+ region_t region;
+ vm_range_t range;
+ vm_range_t admin_range;
+ vm_range_t ptr_range;
+ unsigned char *mapped_region;
+ uint32_t *block_header;
+ uint32_t *in_use;
+ unsigned block_index;
+ unsigned block_limit;
+ boolean_t is_free;
+ msize_t msize;
+ void *mapped_ptr;
+ unsigned bit;
+ vm_address_t mag_last_free_ptr = 0;
+ msize_t mag_last_free_msize = 0;
+
+ region_hash_generation_t *trg_ptr;
+ err = reader(task, (vm_address_t)szone->tiny_region_generation, sizeof(region_hash_generation_t), (void **)&trg_ptr);
+ if (err) return err;
+
+ num_regions = trg_ptr->num_regions_allocated;
+ err = reader(task, (vm_address_t)trg_ptr->hashed_regions, sizeof(region_t) * num_regions, (void **)®ions);
+ if (err) return err;
+
+ for (index = 0; index < num_regions; ++index) {
+ region = regions[index];
+ if (HASHRING_OPEN_ENTRY != region && HASHRING_REGION_DEALLOCATED != region) {
+ 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 + TINY_METADATA_START;
+ admin_range.size = TINY_METADATA_SIZE;
+ 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 = NUM_TINY_BLOCKS * TINY_QUANTUM;
+ 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;
+
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(mapped_region);
+ magazine_t *tiny_mag_ptr;
+ err = reader(task, (vm_address_t)&(szone->tiny_magazines[mag_index]), sizeof(magazine_t),
+ (void **)&tiny_mag_ptr);
+ if (err) return err;
+
+ void *mag_last_free = tiny_mag_ptr->mag_last_free;
+ if (mag_last_free) {
+ mag_last_free_ptr = (uintptr_t) mag_last_free & ~(TINY_QUANTUM - 1);
+ mag_last_free_msize = (uintptr_t) mag_last_free & (TINY_QUANTUM - 1);
+ }
+
+ block_header = (uint32_t *)(mapped_region + TINY_METADATA_START + sizeof(region_trailer_t));
+ in_use = TINY_INUSE_FOR_HEADER(block_header);
+ block_index = 0;
+ block_limit = NUM_TINY_BLOCKS;
+ if (region == tiny_mag_ptr->mag_last_region)
+ block_limit -= TINY_MSIZE_FOR_BYTES(tiny_mag_ptr->mag_bytes_free_at_end);
+
+ while (block_index < block_limit) {
+ vm_size_t block_offset = TINY_BYTES_FOR_MSIZE(block_index);
+ is_free = !BITARRAY_BIT(in_use, block_index);
+ if (is_free) {
+ mapped_ptr = mapped_region + block_offset;
+
+ // mapped_region, the address at which 'range' in 'task' has been
+ // mapped into our process, is not necessarily aligned to
+ // TINY_BLOCKS_ALIGN.
+ //
+ // Since the code in get_tiny_free_size() assumes the pointer came
+ // from a properly aligned tiny region, and mapped_region is not
+ // necessarily aligned, then do the size calculation directly.
+ // If the next bit is set in the header bitmap, then the size is one
+ // quantum. Otherwise, read the size field.
+ if (!BITARRAY_BIT(block_header, (block_index+1)))
+ msize = TINY_FREE_SIZE(mapped_ptr);
+ else
+ msize = 1;
+
+ if (!msize)
+ break;
+ } else if (range.address + block_offset != mag_last_free_ptr) {
+ msize = 1;
+ bit = block_index + 1;
+ while (! BITARRAY_BIT(block_header, bit)) {
+ bit++;
+ msize ++;
+ }
+ buffer[count].address = range.address + block_offset;
+ 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;
+ }
+ } else {
+ // Block is not free but it matches mag_last_free_ptr so even
+ // though it is not marked free in the bitmap, we treat it as if
+ // it is and move on
+ msize = mag_last_free_msize;
+ }
+ block_index += msize;
+ }
+ if (count) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE, buffer, count);
+ count = 0;
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+static void *
+tiny_malloc_from_free_list(szone_t *szone, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
+{
+ free_list_t *ptr;
+ msize_t this_msize;
+ grain_t slot = msize - 1;
+ free_list_t **free_list = tiny_mag_ptr->mag_free_list;
+ free_list_t **the_slot = free_list + slot;
+ free_list_t *next;
+ free_list_t **limit;
+#if defined(__LP64__)
+ uint64_t bitmap;
+#else
+ uint32_t bitmap;
+#endif
+ msize_t leftover_msize;
+ free_list_t *leftover_ptr;
+
+ // Assumes we've locked the region
+ CHECK_MAGAZINE_PTR_LOCKED(szone, tiny_mag_ptr, __PRETTY_FUNCTION__);
+
+ // Look for an exact match by checking the freelist for this msize.
+ //
+ ptr = *the_slot;
+ if (ptr) {
+ next = free_list_unchecksum_ptr(szone, &ptr->next);
+ if (next) {
+ next->previous = ptr->previous;
+ } else {
+ BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
+ }
+ *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;
+ }
+
+ // Mask off the bits representing slots holding free blocks smaller than the
+ // size we need. If there are no larger free blocks, try allocating from
+ // the free space at the end of the tiny region.
+#if defined(__LP64__)
+ bitmap = ((uint64_t *)(tiny_mag_ptr->mag_bitmap))[0] & ~ ((1ULL << slot) - 1);
+#else
+ bitmap = tiny_mag_ptr->mag_bitmap[0] & ~ ((1 << slot) - 1);
+#endif
+ if (!bitmap)
+ goto try_tiny_malloc_from_end;
+
+ slot = BITMAPV_CTZ(bitmap);
+ limit = free_list + NUM_TINY_SLOTS - 1;
+ free_list += slot;
+
+ if (free_list < limit) {
+ ptr = *free_list;
+ if (ptr) {
+ next = free_list_unchecksum_ptr(szone, &ptr->next);
+ *free_list = next;
+ if (next) {
+ next->previous = ptr->previous;
+ } else {
+ BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
+ }
+ this_msize = get_tiny_free_size(ptr);
+ goto add_leftover_and_proceed;
+ }
+#if DEBUG_MALLOC
+ malloc_printf("in tiny_malloc_from_free_list(), mag_bitmap out of sync, slot=%d\n",slot);
+#endif
+ }
+
+ // We are now looking at the last slot, which contains blocks equal to, or
+ // due to coalescing of free blocks, larger than (NUM_TINY_SLOTS - 1) * tiny quantum size.
+ // If the last freelist is not empty, and the head contains a block that is
+ // larger than our request, then the remainder is put back on the free list.
+ ptr = *limit;
+ if (ptr) {
+ this_msize = get_tiny_free_size(ptr);
+ next = free_list_unchecksum_ptr(szone, &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 a pop and push of the head
+ 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.u = free_list_checksum_ptr(szone, leftover_ptr);
+ }
+ leftover_ptr->previous = ptr->previous;
+ leftover_ptr->next = ptr->next;
+ 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;
+ }
+ if (next) {
+ next->previous = ptr->previous;
+ }
+ *limit = next;
+ goto add_leftover_and_proceed;
+ /* NOTREACHED */
+ }
+
+try_tiny_malloc_from_end:
+ // Let's see if we can use tiny_mag_ptr->mag_bytes_free_at_end
+ if (tiny_mag_ptr->mag_bytes_free_at_end >= TINY_BYTES_FOR_MSIZE(msize)) {
+ ptr = (free_list_t *)((uintptr_t)TINY_REGION_END(tiny_mag_ptr->mag_last_region) -
+ tiny_mag_ptr->mag_bytes_free_at_end);
+ tiny_mag_ptr->mag_bytes_free_at_end -= TINY_BYTES_FOR_MSIZE(msize);
+ if (tiny_mag_ptr->mag_bytes_free_at_end) {
+ // let's add an in use block after ptr to serve as boundary
+ set_tiny_meta_header_in_use_1((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
+ }
+ 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, tiny_mag_ptr, leftover_ptr, leftover_msize);
+ this_msize = msize;
+ }
+
+return_tiny_alloc:
+ tiny_mag_ptr->mag_num_objects++;
+ tiny_mag_ptr->mag_num_bytes_in_objects += TINY_BYTES_FOR_MSIZE(this_msize);
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr));
+ size_t bytes_used = node->bytes_used + TINY_BYTES_FOR_MSIZE(this_msize);
+ node->bytes_used = bytes_used;
+
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(TINY_REGION_PAYLOAD_BYTES)) {
+ /* After this allocation the region is still sparse, so it must have been even more so before
+ the allocation. That implies the region is already correctly marked. Do nothing. */
+ } else {
+ /* Region has crossed threshold from sparsity to density. Mark it not "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = FALSE;
+ }
+#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
+ if (this_msize > 1)
+ set_tiny_meta_header_in_use(ptr, this_msize);
+ else
+ set_tiny_meta_header_in_use_1(ptr);
+ return ptr;
+}
+#undef DENSITY_THRESHOLD
+#undef K
+
+static INLINE void *
+tiny_malloc_should_clear(szone_t *szone, msize_t msize, boolean_t cleared_requested)
+{
+ void *ptr;
+ mag_index_t mag_index = mag_get_thread_index(szone);
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+
+#if DEBUG_MALLOC
+ if (DEPOT_MAGAZINE_INDEX == mag_index) {
+ szone_error(szone, 1, "malloc called for magazine index -1", NULL, NULL);
+ return(NULL);
+ }
+
+ if (!msize) {
+ szone_error(szone, 1, "invariant broken (!msize) in allocation (region)", NULL, NULL);
+ return(NULL);
+ }
+#endif
+
+ SZONE_MAGAZINE_PTR_LOCK(szone, tiny_mag_ptr);
+
+#if TINY_CACHE
+ ptr = tiny_mag_ptr->mag_last_free;
+
+ if ((((uintptr_t)ptr) & (TINY_QUANTUM - 1)) == msize) {
+ // we have a winner
+ tiny_mag_ptr->mag_last_free = NULL;
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ ptr = (void *)((uintptr_t)ptr & ~ (TINY_QUANTUM - 1));
+ if (cleared_requested) {
+ memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
+ }
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in tiny_malloc_should_clear(), tiny cache ptr=%p, msize=%d\n", ptr, msize);
+ }
+#endif
+ return ptr;
+ }
+#endif /* TINY_CACHE */
+
+ ptr = tiny_malloc_from_free_list(szone, tiny_mag_ptr, mag_index, msize);
+ if (ptr) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ if (cleared_requested) {
+ memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
+ }
+ return ptr;
+ }
+
+ if (tiny_get_region_from_depot(szone, tiny_mag_ptr, mag_index)) {
+ ptr = tiny_malloc_from_free_list(szone, tiny_mag_ptr, mag_index, msize);
+ if (ptr) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ if (cleared_requested) {
+ memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));
+ }
+ return ptr;
+ }
+ }
+
+ ptr = tiny_malloc_from_region_no_lock(szone, tiny_mag_ptr, mag_index, msize);
+ // we don't clear because this freshly allocated space is pristine
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return ptr;
+}
+
+static NOINLINE void
+free_tiny_botch(szone_t *szone, free_list_t *ptr)
+{
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr));
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ szone_error(szone, 1, "double free", ptr, NULL);
+}
+
+static INLINE void
+free_tiny(szone_t *szone, void *ptr, region_t tiny_region, size_t known_size)
+{
+ msize_t msize;
+ boolean_t is_free;
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(tiny_region);
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+
+ // ptr is known to be in tiny_region
+ if (known_size) {
+ msize = TINY_MSIZE_FOR_BYTES(known_size + TINY_QUANTUM - 1);
+ } else {
+ msize = get_tiny_meta_header(ptr, &is_free);
+ if (is_free) {
+ free_tiny_botch(szone, ptr);
+ return;
+ }
+ }
+#if DEBUG_MALLOC
+ if (!msize) {
+ malloc_printf("*** free_tiny() block in use is too large: %p\n", ptr);
+ return;
+ }
+#endif
+
+ SZONE_MAGAZINE_PTR_LOCK(szone, tiny_mag_ptr);
+
+#if TINY_CACHE
+ // Depot does not participate in TINY_CACHE since it can't be directly malloc()'d
+ if (DEPOT_MAGAZINE_INDEX != mag_index) {
+ if (msize < TINY_QUANTUM) { // to see if the bits fit in the last 4 bits
+ void *ptr2 = tiny_mag_ptr->mag_last_free; // Might be NULL
+ region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;
+
+ /* check that we don't already have this pointer in the cache */
+ if (ptr == (void *)((uintptr_t)ptr2 & ~ (TINY_QUANTUM - 1))) {
+ free_tiny_botch(szone, ptr);
+ return;
+ }
+
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) && msize)
+ memset(ptr, 0x55, TINY_BYTES_FOR_MSIZE(msize));
+
+ tiny_mag_ptr->mag_last_free = (void *)(((uintptr_t)ptr) | msize);
+ tiny_mag_ptr->mag_last_free_rgn = tiny_region;
+
+ if (!ptr2) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return;
+ }
+
+ msize = (uintptr_t)ptr2 & (TINY_QUANTUM - 1);
+ ptr = (void *)(((uintptr_t)ptr2) & ~(TINY_QUANTUM - 1));
+ tiny_region = rgn2;
+ }
+ }
+#endif /* TINY_CACHE */
+
+ // Now in the time it took to acquire the lock, the region may have migrated
+ // from one magazine to another. I.e. trailer->mag_index is volatile.
+ // In which case the magazine lock we obtained (namely magazines[mag_index].mag_lock)
+ // is stale. If so, keep on tryin' ...
+ region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(tiny_region);
+ mag_index_t refreshed_index;
+
+ while (mag_index != (refreshed_index = trailer->mag_index)) { // Note assignment
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+
+ mag_index = refreshed_index;
+ tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_LOCK(szone, tiny_mag_ptr);
+ }
+
+ tiny_free_no_lock(szone, tiny_mag_ptr, mag_index, tiny_region, ptr, msize);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+}
+
+static void
+print_tiny_free_list(szone_t *szone)
+{
+ free_list_t *ptr;
+ _SIMPLE_STRING b = _simple_salloc();
+ mag_index_t mag_index;
+
+ if (b) {
+ _simple_sappend(b, "tiny free sizes:\n");
+ for (mag_index = -1; mag_index < szone->num_tiny_magazines; mag_index++) {
+ grain_t slot = 0;
+ _simple_sprintf(b,"\tMagazine %d: ", mag_index);
+ while (slot < NUM_TINY_SLOTS) {
+ ptr = szone->tiny_magazines[mag_index].mag_free_list[slot];
+ if (ptr) {
+ _simple_sprintf(b, "%s%y[%d]; ", (slot == NUM_TINY_SLOTS-1) ? ">=" : "",
+ (slot+1)*TINY_QUANTUM, free_list_count(szone, ptr));
+ }
+ slot++;
+ }
+ _simple_sappend(b,"\n");
+ }
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+}
+
+static void
+print_tiny_region(boolean_t verbose, region_t region, size_t bytes_at_end)
+{
+ unsigned counts[1024];
+ unsigned in_use = 0;
+ uintptr_t start = (uintptr_t)TINY_REGION_ADDRESS(region);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)TINY_REGION_END(region) - bytes_at_end;
+ boolean_t is_free;
+ msize_t msize;
+ unsigned ci;
+ _SIMPLE_STRING b;
+ uintptr_t pgTot = 0;
+
+ if (region == HASHRING_REGION_DEALLOCATED) {
+ if ((b = _simple_salloc()) != NULL) {
+ _simple_sprintf(b, "Tiny region [unknown address] was returned to the OS\n");
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+ return;
+ }
+
+ memset(counts, 0, sizeof(counts));
+ while (current < limit) {
+ msize = get_tiny_meta_header((void *)current, &is_free);
+ if (is_free & !msize && (current == start)) {
+ // first block is all free
+ uintptr_t pgLo = round_page(start + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(start + TINY_REGION_SIZE - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ pgTot += (pgHi - pgLo);
+ }
+ break;
+ }
+ if (!msize) {
+ malloc_printf("*** error with %p: msize=%d\n", (void *)current, (unsigned)msize);
+ break;
+ }
+ if (!is_free) {
+ // block in use
+ if (msize > NUM_TINY_SLOTS)
+ malloc_printf("*** error at %p msize for in_use is %d\n", (void *)current, msize);
+ if (msize < 1024)
+ counts[msize]++;
+ in_use++;
+ } else {
+ uintptr_t pgLo = round_page(current + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(current + TINY_BYTES_FOR_MSIZE(msize) - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ pgTot += (pgHi - pgLo);
+ }
+ }
+ current += TINY_BYTES_FOR_MSIZE(msize);
+ }
+ if ((b = _simple_salloc()) != NULL) {
+ _simple_sprintf(b, "Tiny region [%p-%p, %y] \t", (void *)start, TINY_REGION_END(region), (int)TINY_REGION_SIZE);
+ _simple_sprintf(b, "Magazine=%d \t", MAGAZINE_INDEX_FOR_TINY_REGION(region));
+ _simple_sprintf(b, "Allocations in use=%d \t Bytes in use=%ly \t", in_use, BYTES_USED_FOR_TINY_REGION(region));
+ if (bytes_at_end)
+ _simple_sprintf(b, "Untouched=%ly ", bytes_at_end);
+ if (DEPOT_MAGAZINE_INDEX == MAGAZINE_INDEX_FOR_TINY_REGION(region)) {
+ _simple_sprintf(b, "Advised MADV_FREE=%ly", pgTot);
+ } else {
+ _simple_sprintf(b, "Fragments subject to reclamation=%ly", pgTot);
+ }
+ if (verbose && in_use) {
+ _simple_sappend(b, "\n\tSizes in use: ");
+ for (ci = 0; ci < 1024; ci++)
+ if (counts[ci])
+ _simple_sprintf(b, "%d[%d] ", TINY_BYTES_FOR_MSIZE(ci), counts[ci]);
+ }
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+}
+
+static boolean_t
+tiny_free_list_check(szone_t *szone, grain_t slot)
+{
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_tiny_magazines; mag_index++) {
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_LOCK(szone, tiny_mag_ptr);
+
+ unsigned count = 0;
+ free_list_t *ptr = szone->tiny_magazines[mag_index].mag_free_list[slot];
+ boolean_t is_free;
+ free_list_t *previous = NULL;
+
+ while (ptr) {
+ is_free = tiny_meta_header_is_free(ptr);
+ if (! is_free) {
+ malloc_printf("*** in-use ptr in free list slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ return 0;
+ }
+ if (((uintptr_t)ptr) & (TINY_QUANTUM - 1)) {
+ malloc_printf("*** unaligned ptr in free list slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ return 0;
+ }
+ if (!tiny_region_for_ptr_no_lock(szone, ptr)) {
+ malloc_printf("*** ptr not in szone slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ return 0;
+ }
+ if (free_list_unchecksum_ptr(szone, &ptr->previous) != previous) {
+ malloc_printf("*** previous incorrectly set slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ return 0;
+ }
+ previous = ptr;
+ ptr = free_list_unchecksum_ptr(szone, &ptr->next);
+ count++;
+ }
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ }
+ return 1;
+}
+
+/********************* SMALL FREE LIST UTILITIES ************************/
+
+/*
+ * Mark a block as free. Only the first quantum of a block is marked thusly,
+ * the remainder are marked "middle".
+ */
+static INLINE void
+small_meta_header_set_is_free(msize_t *meta_headers, unsigned index, msize_t msize)
+{
+ meta_headers[index] = msize | SMALL_IS_FREE;
+}
+
+/*
+ * Mark a block as in use. Only the first quantum of a block is marked thusly,
+ * the remainder are marked "middle".
+ */
+static INLINE void
+small_meta_header_set_in_use(msize_t *meta_headers, msize_t index, msize_t msize)
+{
+ meta_headers[index] = msize;
+}
+
+/*
+ * Mark a quantum as being the second or later in a block.
+ */
+static INLINE void
+small_meta_header_set_middle(msize_t *meta_headers, msize_t index)
+{
+ meta_headers[index] = 0;
+}
+
+/*
+ * Adds an item to the proper free list, and also marks the meta-header of the
+ * block properly.
+ * Assumes szone has been locked
+ */
+static void
+small_free_list_add_ptr(szone_t *szone, magazine_t *small_mag_ptr, void *ptr, msize_t msize)
+{
+ grain_t slot = (msize <= szone->num_small_slots) ? msize - 1 : szone->num_small_slots - 1;
+ free_list_t *free_ptr = ptr;
+ free_list_t *free_head = small_mag_ptr->mag_free_list[slot];
+ void *follower;
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in %s, ptr=%p, msize=%d\n", __FUNCTION__, ptr, msize);
+ }
+ if (((uintptr_t)ptr) & (SMALL_QUANTUM - 1)) {
+ szone_error(szone, 1, "small_free_list_add_ptr: Unaligned ptr", ptr, NULL);
+ }
+#endif
+ small_meta_header_set_is_free(SMALL_META_HEADER_FOR_PTR(ptr), SMALL_META_INDEX_FOR_PTR(ptr), msize);
+
+ if (free_head) {
+#if DEBUG_MALLOC
+ if (free_list_unchecksum_ptr(szone, &free_head->previous)) {
+ szone_error(szone, 1, "small_free_list_add_ptr: Internal invariant broken (free_head->previous)", ptr,
+ "ptr=%p slot=%d free_head=%p previous=%p\n", ptr, slot, (void *)free_head, free_head->previous.p);
+ }
+ if (!SMALL_PTR_IS_FREE(free_head)) {
+ szone_error(szone, 1, "small_free_list_add_ptr: Internal invariant broken (free_head is not a free pointer)", ptr,
+ "ptr=%p slot=%d free_head=%p\n", ptr, slot, (void *)free_head);
+ }
+#endif
+ free_head->previous.u = free_list_checksum_ptr(szone, free_ptr);
+ } else {
+ BITMAPN_SET(small_mag_ptr->mag_bitmap, slot);
+ }
+ free_ptr->previous.u = free_list_checksum_ptr(szone, NULL);
+ free_ptr->next.u = free_list_checksum_ptr(szone, free_head);
+
+ small_mag_ptr->mag_free_list[slot] = free_ptr;
+
+ // Store msize at the end of the block denoted by "ptr" (i.e. at a negative offset from "follower")
+ follower = (void *)((uintptr_t)ptr + SMALL_BYTES_FOR_MSIZE(msize));
+ SMALL_PREVIOUS_MSIZE(follower) = msize;
+}
+
+/*
+ * Removes the item pointed to by ptr in the proper free list.
+ * Assumes szone has been locked
+ */
+static void
+small_free_list_remove_ptr(szone_t *szone, magazine_t *small_mag_ptr, void *ptr, msize_t msize)
+{
+ grain_t slot = (msize <= szone->num_small_slots) ? msize - 1 : szone->num_small_slots - 1;
+ free_list_t *free_ptr = ptr, *next, *previous;
+
+ next = free_list_unchecksum_ptr(szone, &free_ptr->next);
+ previous = free_list_unchecksum_ptr(szone, &free_ptr->previous);
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("In %s, ptr=%p, msize=%d\n", __FUNCTION__, ptr, msize);
+ }
+#endif
+
+ if (!previous) {
+ // The block to remove is the head of the free list
+#if DEBUG_MALLOC
+ if (small_mag_ptr->mag_free_list[slot] != ptr) {
+ szone_error(szone, 1, "small_free_list_remove_ptr: Internal invariant broken (small_mag_ptr->mag_free_list[slot])", ptr,
+ "ptr=%p slot=%d msize=%d small_mag_ptr->mag_free_list[slot]=%p\n",
+ ptr, slot, msize, (void *)small_mag_ptr->mag_free_list[slot]);
+ return;
+ }
+#endif
+ small_mag_ptr->mag_free_list[slot] = next;
+ if (!next) BITMAPN_CLR(small_mag_ptr->mag_bitmap, slot);
+ } else {
+ // We know free_ptr is already checksummed, so we don't need to do it
+ // again.
+ previous->next = free_ptr->next;
+ }
+ if (next) {
+ // We know free_ptr is already checksummed, so we don't need to do it
+ // again.
+ next->previous = free_ptr->previous;
+ }
+}
+
+/*
+ * small_region_for_ptr_no_lock - Returns the small region containing the pointer,
+ * or NULL if not found.
+ */
+static INLINE region_t
+small_region_for_ptr_no_lock(szone_t *szone, const void *ptr)
+{
+ rgnhdl_t r = hash_lookup_region_no_lock(szone->small_region_generation->hashed_regions,
+ szone->small_region_generation->num_regions_allocated,
+ szone->small_region_generation->num_regions_allocated_shift,
+ SMALL_REGION_FOR_PTR(ptr));
+ return r ? *r : r;
+}
+
+static void
+small_finalize_region(szone_t *szone, magazine_t *small_mag_ptr) {
+ void *last_block, *previous_block;
+ msize_t last_msize, previous_msize, last_index;
+
+ last_block = SMALL_REGION_END(small_mag_ptr->mag_last_region) - small_mag_ptr->mag_bytes_free_at_end;
+ last_msize = SMALL_MSIZE_FOR_BYTES(small_mag_ptr->mag_bytes_free_at_end);
+
+ // It is possible that the block prior to the last block in the region has
+ // been free'd, but was not coalesced with the free bytes at the end of the
+ // block, since we treat the bytes at the end of the region as "in use" in
+ // the meta headers. Attempt to coalesce the last block with the previous
+ // block, so we don't violate the "no consecutive free blocks" invariant.
+ //
+ // FIXME: If we could calculate the previous small free size in the same
+ // manner as tiny_previous_preceding_free, it would eliminate the
+ // index & previous msize checks, which are a guard against reading
+ // bogus data out of in-use or written-on-freed memory.
+ //
+ // FIXME: Need to investigate how much work would be required to increase
+ // 'mag_bytes_free_at_end' when freeing the preceding block, rather
+ // than performing this workaround.
+ //
+ last_index = SMALL_META_INDEX_FOR_PTR(last_block);
+ previous_msize = SMALL_PREVIOUS_MSIZE(last_block);
+
+ if (last_index && (previous_msize <= last_index)) {
+ previous_block = (void *)((uintptr_t)last_block - SMALL_BYTES_FOR_MSIZE(previous_msize));
+ if (*SMALL_METADATA_FOR_PTR(previous_block) == (previous_msize | SMALL_IS_FREE)) {
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(last_block);
+
+ small_meta_header_set_middle(meta_headers, last_index);
+ small_free_list_remove_ptr(szone, small_mag_ptr, previous_block, previous_msize);
+ last_block = (void *)((uintptr_t)last_block - SMALL_BYTES_FOR_MSIZE(previous_msize));
+ last_msize += previous_msize;
+ }
+ }
+
+ // splice last_block into the free list
+ small_free_list_add_ptr(szone, small_mag_ptr, last_block, last_msize);
+ small_mag_ptr->mag_bytes_free_at_end = 0;
+ small_mag_ptr->mag_last_region = NULL;
+}
+
+static int
+small_free_detach_region(szone_t *szone, magazine_t *small_mag_ptr, region_t r) {
+ unsigned char *ptr = SMALL_REGION_ADDRESS(r);
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
+ uintptr_t start = (uintptr_t)SMALL_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)SMALL_REGION_END(r);
+ int total_alloc = 0;
+
+ while (current < limit) {
+ unsigned index = SMALL_META_INDEX_FOR_PTR(current);
+ msize_t msize_and_free = meta_headers[index];
+ boolean_t is_free = msize_and_free & SMALL_IS_FREE;
+ msize_t msize = msize_and_free & ~ SMALL_IS_FREE;
+
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** small_free_detach_region error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ small_free_list_remove_ptr(szone, small_mag_ptr, (void *)current, msize);
+ } else {
+ total_alloc++;
+ }
+ current += SMALL_BYTES_FOR_MSIZE(msize);
+ }
+ return total_alloc;
+}
+
+static size_t
+small_free_reattach_region(szone_t *szone, magazine_t *small_mag_ptr, region_t r) {
+ unsigned char *ptr = SMALL_REGION_ADDRESS(r);
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
+ uintptr_t start = (uintptr_t)SMALL_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)SMALL_REGION_END(r);
+ size_t total_alloc = 0;
+
+ while (current < limit) {
+ unsigned index = SMALL_META_INDEX_FOR_PTR(current);
+ msize_t msize_and_free = meta_headers[index];
+ boolean_t is_free = msize_and_free & SMALL_IS_FREE;
+ msize_t msize = msize_and_free & ~ SMALL_IS_FREE;
+
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** small_free_reattach_region error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ small_free_list_add_ptr(szone, small_mag_ptr, (void *)current, msize);
+ } else {
+ total_alloc += SMALL_BYTES_FOR_MSIZE(msize);
+ }
+ current += SMALL_BYTES_FOR_MSIZE(msize);
+ }
+ return total_alloc;
+}
+
+static void
+small_free_scan_depot_madvise_free(szone_t *szone, magazine_t *depot_ptr, region_t r) {
+ uintptr_t start = (uintptr_t)SMALL_REGION_ADDRESS(r);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)SMALL_REGION_END(r);
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(start);
+ boolean_t did_advise = FALSE;
+
+ // Scan the metadata identifying blocks which span one or more pages. Mark the pages MADV_FREE taking care to preserve free list
+ // management data.
+ while (current < limit) {
+ unsigned index = SMALL_META_INDEX_FOR_PTR(current);
+ msize_t msize_and_free = meta_headers[index];
+ boolean_t is_free = msize_and_free & SMALL_IS_FREE;
+ msize_t msize = msize_and_free & ~ SMALL_IS_FREE;
+
+ if (is_free && !msize && (current == start)) {
+#if DEBUG_MALLOC
+ // first block is all free
+ malloc_printf("*** small_free_scan_depot_madvise_free first block is all free! %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ uintptr_t pgLo = round_page(start + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(start + SMALL_REGION_SIZE - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ madvise_free_range(szone, r, pgLo, pgHi);
+ did_advise = TRUE;
+ }
+ break;
+ }
+ if (!msize) {
+#if DEBUG_MALLOC
+ malloc_printf("*** small_free_scan_depot_madvise_free error with %p: msize=%d is_free =%d\n",
+ (void *)current, msize, is_free);
+#endif
+ break;
+ }
+ if (is_free) {
+ uintptr_t pgLo = round_page(current + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(current + SMALL_BYTES_FOR_MSIZE(msize) - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ madvise_free_range(szone, r, pgLo, pgHi);
+ did_advise = TRUE;
+ }
+ }
+ current += SMALL_BYTES_FOR_MSIZE(msize);
+ }
+
+ if (did_advise) {
+ /* Move the node to the tail of the Deopt's recirculation list to delay its re-use. */
+ region_trailer_t *node = REGION_TRAILER_FOR_SMALL_REGION(r);
+ recirc_list_extract(szone, depot_ptr, node); // excise node from list
+ recirc_list_splice_last(szone, depot_ptr, node); // connect to magazine as last node
+ }
+}
+
+static void
+small_free_try_depot_unmap_no_lock(szone_t *szone, magazine_t *depot_ptr, region_trailer_t *node)
+{
+#warning Tune Depot headroom
+ if (0 < node->bytes_used ||
+ depot_ptr->recirculation_entries < (szone->num_small_magazines * 2)) {
+ return;
+ }
+
+ // disconnect first node from Depot
+ recirc_list_extract(szone, depot_ptr, node);
+
+ // Iterate the region pulling its free entries off the (locked) Depot's free list
+ region_t sparse_region = SMALL_REGION_FOR_PTR(node);
+ int objects_in_use = small_free_detach_region(szone, depot_ptr, sparse_region);
+
+ if (0 == objects_in_use) {
+ // Invalidate the hash table entry for this region with HASHRING_REGION_DEALLOCATED.
+ // Using HASHRING_REGION_DEALLOCATED preserves the collision chain, using HASHRING_OPEN_ENTRY (0) would not.
+ rgnhdl_t pSlot = hash_lookup_region_no_lock(szone->small_region_generation->hashed_regions,
+ szone->small_region_generation->num_regions_allocated,
+ szone->small_region_generation->num_regions_allocated_shift, sparse_region);
+ *pSlot = HASHRING_REGION_DEALLOCATED;
+ depot_ptr->num_bytes_in_magazine -= SMALL_REGION_PAYLOAD_BYTES;
+#if ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 1))) /* GCC 4.1 and forward supports atomic builtins */
+ __sync_fetch_and_add( &(szone->num_small_regions_dealloc), 1); // Atomically increment num_small_regions_dealloc
+#else
+#ifdef __LP64__
+ OSAtomicIncrement64( (volatile int64_t *)&(szone->num_small_regions_dealloc) );
+#else
+ OSAtomicIncrement32( (volatile int32_t *)&(szone->num_small_regions_dealloc) );
+#endif
+#endif
+
+ // Transfer ownership of the region back to the OS
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, depot_ptr); // Avoid denial of service to Depot while in kernel
+ deallocate_pages(szone, sparse_region, SMALL_REGION_SIZE, 0);
+ SZONE_MAGAZINE_PTR_LOCK(szone, depot_ptr);
+
+ MAGMALLOC_DEALLOCREGION((void *)szone, (void *)sparse_region); // DTrace USDT Probe
+
+ } else {
+ szone_error(szone, 1, "small_free_try_depot_unmap_no_lock objects_in_use not zero:", NULL, "%d\n", objects_in_use);
+ }
+}
+
+static void
+small_free_do_recirc_to_depot(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index)
+{
+ // The entire magazine crossed the "emptiness threshold". Transfer a region
+ // from this magazine to the Depot. Choose a region that itself has crossed the emptiness threshold (i.e
+ // is at least fraction "f" empty.) Such a region will be marked "suitable" on the recirculation list.
+ region_trailer_t *node = small_mag_ptr->firstNode;
+
+ while (node && !node->recirc_suitable) {
+ node = node->next;
+ }
+
+ if (NULL == node) {
+#if DEBUG_MALLOC
+ malloc_printf("*** small_free_do_recirc_to_depot end of list\n");
+#endif
+ return;
+ }
+
+ region_t sparse_region = SMALL_REGION_FOR_PTR(node);
+
+ // Deal with unclaimed memory -- mag_bytes_free_at_end
+ if (sparse_region == small_mag_ptr->mag_last_region && small_mag_ptr->mag_bytes_free_at_end) {
+ small_finalize_region(szone, small_mag_ptr);
+ }
+
+ // disconnect first node from magazine
+ recirc_list_extract(szone, small_mag_ptr, node);
+
+ // Iterate the region pulling its free entries off its (locked) magazine's free list
+ int objects_in_use = small_free_detach_region(szone, small_mag_ptr, sparse_region);
+ magazine_t *depot_ptr = &(szone->small_magazines[DEPOT_MAGAZINE_INDEX]);
+
+ // hand over the region to the (locked) Depot
+ SZONE_MAGAZINE_PTR_LOCK(szone,depot_ptr);
+ // this will cause small_free_list_add_ptr called by small_free_reattach_region to use
+ // the depot as its target magazine, rather than magazine formerly associated with sparse_region
+ MAGAZINE_INDEX_FOR_SMALL_REGION(sparse_region) = DEPOT_MAGAZINE_INDEX;
+
+ // Iterate the region putting its free entries on Depot's free list
+ size_t bytes_inplay = small_free_reattach_region(szone, depot_ptr, sparse_region);
+
+ small_mag_ptr->mag_num_bytes_in_objects -= bytes_inplay;
+ small_mag_ptr->num_bytes_in_magazine -= SMALL_REGION_PAYLOAD_BYTES;
+ small_mag_ptr->mag_num_objects -= objects_in_use;
+
+ depot_ptr->mag_num_bytes_in_objects += bytes_inplay;
+ depot_ptr->num_bytes_in_magazine += SMALL_REGION_PAYLOAD_BYTES;
+ depot_ptr->mag_num_objects += objects_in_use;
+
+ // connect to Depot as first node
+ recirc_list_splice_first(szone, depot_ptr, node);
+
+ MAGMALLOC_RECIRCREGION((void *)szone, (int)mag_index, (int)BYTES_USED_FOR_SMALL_REGION(sparse_region)); // DTrace USDT Probe
+
+ // Mark free'd dirty pages with MADV_FREE to reduce memory pressure
+ small_free_scan_depot_madvise_free(szone, depot_ptr, sparse_region);
+
+ // If the region is entirely empty vm_deallocate() it
+ small_free_try_depot_unmap_no_lock(szone, depot_ptr, node);
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+}
+
+static boolean_t
+small_get_region_from_depot(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index)
+{
+ magazine_t *depot_ptr = &(szone->small_magazines[DEPOT_MAGAZINE_INDEX]);
+
+ /* FIXME: Would Uniprocessor benefit from recirc and MADV_FREE? */
+ if (szone->num_small_magazines == 1) // Uniprocessor, single magazine, so no recirculation necessary
+ return 0;
+
+#if DEBUG_MALLOC
+ if (DEPOT_MAGAZINE_INDEX == mag_index) {
+ szone_error(szone, 1, "small_get_region_from_depot called for magazine index -1", NULL, NULL);
+ return 0;
+ }
+#endif
+
+ SZONE_MAGAZINE_PTR_LOCK(szone,depot_ptr);
+
+ // Appropriate one of the Depot's regions. Prefer LIFO selection for best cache utilization.
+ region_trailer_t *node = depot_ptr->firstNode;
+
+ if (NULL == node) { // Depot empty?
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+ return 0;
+ }
+
+ // disconnect first node from Depot
+ recirc_list_extract(szone, depot_ptr, node);
+
+ // Iterate the region pulling its free entries off the (locked) Depot's free list
+ region_t sparse_region = SMALL_REGION_FOR_PTR(node);
+ int objects_in_use = small_free_detach_region(szone, depot_ptr, sparse_region);
+
+ // Transfer ownership of the region
+ MAGAZINE_INDEX_FOR_SMALL_REGION(sparse_region) = mag_index;
+
+ // Iterate the region putting its free entries on its new (locked) magazine's free list
+ size_t bytes_inplay = small_free_reattach_region(szone, small_mag_ptr, sparse_region);
+
+ depot_ptr->mag_num_bytes_in_objects -= bytes_inplay;
+ depot_ptr->num_bytes_in_magazine -= SMALL_REGION_PAYLOAD_BYTES;
+ depot_ptr->mag_num_objects -= objects_in_use;
+
+ small_mag_ptr->mag_num_bytes_in_objects += bytes_inplay;
+ small_mag_ptr->num_bytes_in_magazine += SMALL_REGION_PAYLOAD_BYTES;
+ small_mag_ptr->mag_num_objects += objects_in_use;
+
+ // connect to magazine as first node (it's maximally sparse at this moment)
+ recirc_list_splice_first(szone, small_mag_ptr, node);
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone,depot_ptr);
+
+ MAGMALLOC_DEPOTREGION((void *)szone, (int)mag_index, (int)BYTES_USED_FOR_SMALL_REGION(sparse_region)); // DTrace USDT Probe
+
+ if (-1 == madvise((void *)sparse_region, SMALL_REGION_PAYLOAD_BYTES, MADV_FREE_REUSE)) {
+ /* -1 return: VM map entry change makes this unfit for reuse. Something evil lurks. */
+#if DEBUG_MALLOC
+ szone_error(szone, 1, "small_get_region_from_depot madvise(..., MADV_FREE_REUSE) failed", sparse_region, NULL);
+#endif
+ return 0;
+ }
+
+ return 1;
+}
+
+#warning Tune K and f!
+#define K 1.5 // headroom measured in number of 8Mb regions
+#define DENSITY_THRESHOLD(a) \
+ ((a) - ((a) >> 2)) // "Emptiness" f = 0.25, so "Density" is (1 - f)*a. Generally: ((a) - ((a) >> -log2(f)))
+
+static INLINE void
+small_free_no_lock(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index, region_t region, void *ptr, msize_t msize)
+{
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
+ unsigned index = SMALL_META_INDEX_FOR_PTR(ptr);
+ void *original_ptr = ptr;
+ size_t original_size = SMALL_BYTES_FOR_MSIZE(msize);
+ unsigned char *next_block = ((unsigned char *)ptr + original_size);
+ msize_t next_index = index + msize;
+ msize_t previous_msize, next_msize;
+ void *previous;
+ boolean_t did_prepend = FALSE;
+ boolean_t did_append = FALSE;
+
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in small_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+ if (! msize) {
+ szone_error(szone, 1, "trying to free small block that is too small", ptr,
+ "in small_free_no_lock(), ptr=%p, msize=%d\n", ptr, msize);
+ }
+#endif
+
+ // We try to coalesce this block with the preceeding one
+ if (index && (SMALL_PREVIOUS_MSIZE(ptr) <= index)) {
+ previous_msize = SMALL_PREVIOUS_MSIZE(ptr);
+ if (meta_headers[index - previous_msize] == (previous_msize | SMALL_IS_FREE)) {
+ previous = (void *)((uintptr_t)ptr - SMALL_BYTES_FOR_MSIZE(previous_msize));
+ // previous is really to be coalesced
+ did_prepend = TRUE;
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr) || LOG(szone,previous)) {
+ malloc_printf("in small_free_no_lock(), coalesced backwards for %p previous=%p\n", ptr, previous);
+ }
+#endif
+ small_free_list_remove_ptr(szone, small_mag_ptr, previous, previous_msize);
+ small_meta_header_set_middle(meta_headers, index);
+ ptr = previous;
+ msize += previous_msize;
+ index -= previous_msize;
+ }
+ }
+ // We try to coalesce with the next block
+ if ((next_block < SMALL_REGION_END(region)) && (meta_headers[next_index] & SMALL_IS_FREE)) {
+ // next block is free, we coalesce
+ did_append = TRUE;
+ next_msize = meta_headers[next_index] & ~ SMALL_IS_FREE;
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr))
+ malloc_printf("In small_free_no_lock(), for ptr=%p, msize=%d coalesced next block=%p next_msize=%d\n",
+ ptr, msize, next_block, next_msize);
+#endif
+ small_free_list_remove_ptr(szone, small_mag_ptr, next_block, next_msize);
+ small_meta_header_set_middle(meta_headers, next_index);
+ msize += next_msize;
+ }
+ if (szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) {
+ if (!msize) {
+ szone_error(szone, 1, "incorrect size information - block header was damaged", ptr, NULL);
+ } else {
+ memset(ptr, 0x55, SMALL_BYTES_FOR_MSIZE(msize));
+ }
+ }
+ small_free_list_add_ptr(szone, small_mag_ptr, ptr, msize);
+ small_mag_ptr->mag_num_objects--;
+ // we use original_size and not msize to avoid double counting the coalesced blocks
+ small_mag_ptr->mag_num_bytes_in_objects -= original_size;
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_SMALL_REGION(region);
+ size_t bytes_used = node->bytes_used - original_size;
+ node->bytes_used = bytes_used;
+
+ /* FIXME: Would Uniprocessor benefit from recirc and MADV_FREE? */
+ if (szone->num_small_magazines == 1) { // Uniprocessor, single magazine, so no recirculation necessary
+ /* NOTHING */
+ } else if (DEPOT_MAGAZINE_INDEX != mag_index) {
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(SMALL_REGION_PAYLOAD_BYTES)) {
+ /* Region has crossed threshold from density to sparsity. Mark it "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = TRUE;
+ } else {
+ /* After this free, we've found the region is still dense, so it must have been even more so before
+ the free. That implies the region is already correctly marked. Do nothing. */
+ }
+
+ // Has the entire magazine crossed the "emptiness threshold"? If so, transfer a region
+ // from this magazine to the Depot. Choose a region that itself has crossed the emptiness threshold (i.e
+ // is at least fraction "f" empty.) Such a region will be marked "suitable" on the recirculation list.
+
+ size_t a = small_mag_ptr->num_bytes_in_magazine; // Total bytes allocated to this magazine
+ size_t u = small_mag_ptr->mag_num_bytes_in_objects; // In use (malloc'd) from this magaqzine
+
+ if (a - u > ((3 * SMALL_REGION_PAYLOAD_BYTES) / 2) && u < DENSITY_THRESHOLD(a))
+ small_free_do_recirc_to_depot(szone, small_mag_ptr, mag_index);
+
+ } else {
+ // Freed to Depot. N.B. Lock on small_magazines[DEPOT_MAGAZINE_INDEX] is already held
+ uintptr_t safe_ptr = (uintptr_t)ptr + sizeof(free_list_t) + sizeof(msize_t);
+ uintptr_t round_safe = round_page(safe_ptr);
+
+ uintptr_t safe_extent = (uintptr_t)ptr + SMALL_BYTES_FOR_MSIZE(msize) - sizeof(msize_t);
+ uintptr_t trunc_extent = trunc_page(safe_extent);
+
+ // The newly freed block may complete a span of bytes that cover a page. Mark it with MADV_FREE.
+ if (round_safe < trunc_extent) { // Safe area covers a page (perhaps many)
+ if (did_prepend & did_append) { // Coalesced preceding with original_ptr *and* with following
+ uintptr_t trunc_safe_prev = trunc_page((uintptr_t)original_ptr - sizeof(msize_t));
+ uintptr_t rnd_safe_follow =
+ round_page((uintptr_t)original_ptr + original_size + sizeof(free_list_t) + sizeof(msize_t));
+
+ madvise_free_range(szone, region, MAX(round_safe, trunc_safe_prev), MIN(rnd_safe_follow, trunc_extent));
+ } else if (did_prepend) { // Coalesced preceding with original_ptr
+ uintptr_t trunc_safe_prev = trunc_page((uintptr_t)original_ptr - sizeof(msize_t));
+
+ madvise_free_range(szone, region, MAX(round_safe, trunc_safe_prev), trunc_extent);
+ } else if (did_append) { // Coalesced original_ptr with following
+ uintptr_t rnd_safe_follow =
+ round_page((uintptr_t)original_ptr + original_size + sizeof(free_list_t) + sizeof(msize_t));
+
+ madvise_free_range(szone, region, round_safe, MIN(rnd_safe_follow, trunc_extent));
+ } else // Isolated free
+ madvise_free_range(szone, region, round_safe, trunc_extent);
+ }
+
+ if (0 < bytes_used) {
+ /* Depot'd region is still live. Leave it in place on the Depot's recirculation list
+ so as to avoid thrashing between the Depot's free list and a magazines's free list
+ with detach_region/reattach_region */
+ } else {
+ /* Depot'd region is just now empty. Consider return to OS. */
+ region_trailer_t *node = REGION_TRAILER_FOR_SMALL_REGION(region);
+ magazine_t *depot_ptr = &(szone->small_magazines[DEPOT_MAGAZINE_INDEX]);
+ small_free_try_depot_unmap_no_lock(szone, depot_ptr, node);
+ }
+ }
+}
+
+// Allocates from the last region or a freshly allocated region
+static void *
+small_malloc_from_region_no_lock(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index, msize_t msize)
+{
+ void *ptr, *aligned_address;
+
+ // Before anything we transform the mag_bytes_free_at_end - if any - to a regular free block
+ /* FIXME: last_block needs to be coalesced with previous entry if free, <rdar://5462322> */
+ if (small_mag_ptr->mag_bytes_free_at_end)
+ small_finalize_region(szone, small_mag_ptr);
+
+ // time to create a new region
+ aligned_address = allocate_pages(szone, SMALL_REGION_SIZE, SMALL_BLOCKS_ALIGN, 0, VM_MEMORY_MALLOC_SMALL);
+ if (!aligned_address)
+ return NULL;
+
+ MAGMALLOC_ALLOCREGION((void *)szone, (int)mag_index); // DTrace USDT Probe
+
+ // Here find the only place in smallville that (infrequently) takes the small_regions_lock.
+ // Only one thread at a time should be permitted to assess the density of the hash
+ // ring and adjust if needed.
+ // Only one thread at a time should be permitted to insert its new region on
+ // the hash ring.
+ // It is safe for all other threads to read the hash ring (hashed_regions) and
+ // the associated sizes (num_regions_allocated and num_small_regions).
+
+ LOCK(szone->small_regions_lock);
+ // Check to see if the hash ring of small regions needs to grow. Try to
+ // avoid the hash ring becoming too dense.
+ if (szone->small_region_generation->num_regions_allocated < (2 * szone->num_small_regions)) {
+ region_t *new_regions;
+ size_t new_size;
+ size_t new_shift = szone->small_region_generation->num_regions_allocated_shift; // In/Out parameter
+ new_regions = hash_regions_grow_no_lock(szone, szone->small_region_generation->hashed_regions,
+ szone->small_region_generation->num_regions_allocated,
+ &new_shift,
+ &new_size);
+ // Do not deallocate the current hashed_regions allocation since someone
+ // may be iterating it. Instead, just leak it.
+
+ // Prepare to advance to the "next generation" of the hash ring.
+ szone->small_region_generation->nextgen->hashed_regions = new_regions;
+ szone->small_region_generation->nextgen->num_regions_allocated = new_size;
+ szone->small_region_generation->nextgen->num_regions_allocated_shift = new_shift;
+
+ // Throw the switch to atomically advance to the next generation.
+ szone->small_region_generation = szone->small_region_generation->nextgen;
+ // Ensure everyone sees the advance.
+#if ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 1))) /* GCC 4.1 and forward supports atomic builtins */
+ __sync_synchronize();
+#else
+ OSMemoryBarrier();
+#endif
+ }
+ // Tag the region at "aligned_address" as belonging to us,
+ // and so put it under the protection of the magazine lock we are holding.
+ // Do this before advertising "aligned_address" on the hash ring(!)
+ MAGAZINE_INDEX_FOR_SMALL_REGION(aligned_address) = mag_index;
+
+ // Insert the new region into the hash ring, and update malloc statistics
+ hash_region_insert_no_lock(szone->small_region_generation->hashed_regions,
+ szone->small_region_generation->num_regions_allocated,
+ szone->small_region_generation->num_regions_allocated_shift,
+ aligned_address);
+
+ szone->num_small_regions++;
+
+ UNLOCK(szone->small_regions_lock);
+
+ small_mag_ptr->mag_last_region = aligned_address;
+ BYTES_USED_FOR_SMALL_REGION(aligned_address) = SMALL_BYTES_FOR_MSIZE(msize);
+ ptr = aligned_address;
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(ptr), 0, msize);
+ small_mag_ptr->mag_num_objects++;
+ small_mag_ptr->mag_num_bytes_in_objects += SMALL_BYTES_FOR_MSIZE(msize);
+ small_mag_ptr->num_bytes_in_magazine += SMALL_REGION_PAYLOAD_BYTES;
+
+ // add a big free block
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(ptr) , msize, NUM_SMALL_BLOCKS - msize);
+ small_mag_ptr->mag_bytes_free_at_end = SMALL_BYTES_FOR_MSIZE(NUM_SMALL_BLOCKS - msize);
+
+ // connect to magazine as first node (it's maximally sparse at this moment)
+ recirc_list_splice_first(szone, small_mag_ptr, REGION_TRAILER_FOR_SMALL_REGION(aligned_address));
+
+ return ptr;
+}
+
+static INLINE boolean_t
+small_try_realloc_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size)
+{
+ // returns 1 on success
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
+ unsigned index;
+ msize_t old_msize, new_msize;
+ unsigned next_index;
+ void *next_block;
+ msize_t next_msize_and_free;
+ boolean_t is_free;
+ msize_t next_msize, leftover_msize;
+ void *leftover;
+
+ index = SMALL_META_INDEX_FOR_PTR(ptr);
+ old_msize = SMALL_MSIZE_FOR_BYTES(old_size);
+ new_msize = SMALL_MSIZE_FOR_BYTES(new_size + SMALL_QUANTUM - 1);
+ next_index = index + old_msize;
+
+ if (next_index >= NUM_SMALL_BLOCKS) {
+ return 0;
+ }
+ next_block = (char *)ptr + old_size;
+
+#if DEBUG_MALLOC
+ if ((uintptr_t)next_block & (SMALL_QUANTUM - 1)) {
+ szone_error(szone, 1, "internal invariant broken in realloc(next_block)", next_block, NULL);
+ }
+ if (meta_headers[index] != old_msize)
+ malloc_printf("*** small_try_realloc_in_place incorrect old %d %d\n",
+ meta_headers[index], old_msize);
+#endif
+
+ magazine_t *small_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->small_magazines,
+ REGION_TRAILER_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr)),
+ MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr)));
+
+ /*
+ * Look for a free block immediately afterwards. If it's large enough, we can consume (part of)
+ * it.
+ */
+ next_msize_and_free = meta_headers[next_index];
+ is_free = next_msize_and_free & SMALL_IS_FREE;
+ if (!is_free) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0; // next_block is in use;
+ }
+ next_msize = next_msize_and_free & ~ SMALL_IS_FREE;
+ if (old_msize + next_msize < new_msize) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0; // even with next block, not enough
+ }
+ /*
+ * The following block is big enough; pull it from its freelist and chop off enough to satisfy
+ * our needs.
+ */
+ small_free_list_remove_ptr(szone, small_mag_ptr, next_block, next_msize);
+ small_meta_header_set_middle(meta_headers, next_index);
+ leftover_msize = old_msize + next_msize - new_msize;
+ if (leftover_msize) {
+ /* there's some left, so put the remainder back */
+ leftover = (unsigned char *)ptr + SMALL_BYTES_FOR_MSIZE(new_msize);
+
+ small_free_list_add_ptr(szone, small_mag_ptr, leftover, leftover_msize);
+ }
+#if DEBUG_MALLOC
+ if (SMALL_BYTES_FOR_MSIZE(new_msize) > szone->large_threshold) {
+ malloc_printf("*** realloc in place for %p exceeded msize=%d\n", new_msize);
+ }
+#endif
+ small_meta_header_set_in_use(meta_headers, index, new_msize);
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in szone_realloc(), ptr=%p, msize=%d\n", ptr, *SMALL_METADATA_FOR_PTR(ptr));
+ }
+#endif
+ small_mag_ptr->mag_num_bytes_in_objects += SMALL_BYTES_FOR_MSIZE(new_msize - old_msize);
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ size_t bytes_used = node->bytes_used + SMALL_BYTES_FOR_MSIZE(new_msize - old_msize);
+ node->bytes_used = bytes_used;
+
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(SMALL_REGION_PAYLOAD_BYTES)) {
+ /* After this reallocation the region is still sparse, so it must have been even more so before
+ the reallocation. That implies the region is already correctly marked. Do nothing. */
+ } else {
+ /* Region has crossed threshold from sparsity to density. Mark it not "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = FALSE;
+ }
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return 1;
+}
+
+static boolean_t
+small_check_region(szone_t *szone, region_t region)
+{
+ unsigned char *ptr = SMALL_REGION_ADDRESS(region);
+ msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
+ unsigned char *region_end = SMALL_REGION_END(region);
+ msize_t prev_free = 0;
+ unsigned index;
+ msize_t msize_and_free;
+ msize_t msize;
+ free_list_t *free_head;
+ void *previous, *next;
+ msize_t *follower;
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+
+ // Assumes locked
+ CHECK_MAGAZINE_PTR_LOCKED(szone, small_mag_ptr, __PRETTY_FUNCTION__);
+
+ if (region == small_mag_ptr->mag_last_region)
+ region_end -= small_mag_ptr->mag_bytes_free_at_end;
+
+ while (ptr < region_end) {
+ index = SMALL_META_INDEX_FOR_PTR(ptr);
+ msize_and_free = meta_headers[index];
+ if (!(msize_and_free & SMALL_IS_FREE)) {
+ // block is in use
+ msize = msize_and_free;
+ if (!msize) {
+ malloc_printf("*** invariant broken: null msize ptr=%p num_small_regions=%d end=%p\n",
+ ptr, szone->num_small_regions, region_end);
+ return 0;
+ }
+ if (SMALL_BYTES_FOR_MSIZE(msize) > szone->large_threshold) {
+ malloc_printf("*** invariant broken for %p this small msize=%d - size is too large\n",
+ ptr, msize_and_free);
+ return 0;
+ }
+ ptr += SMALL_BYTES_FOR_MSIZE(msize);
+ prev_free = 0;
+ } else {
+ // free pointer
+ msize = msize_and_free & ~ SMALL_IS_FREE;
+ free_head = (free_list_t *)ptr;
+ follower = (msize_t *)FOLLOWING_SMALL_PTR(ptr, msize);
+ if (!msize) {
+ malloc_printf("*** invariant broken for free block %p this msize=%d\n", ptr, msize);
+ return 0;
+ }
+ if (prev_free) {
+ malloc_printf("*** invariant broken for %p (2 free in a row)\n", ptr);
+ return 0;
+ }
+ previous = free_list_unchecksum_ptr(szone, &free_head->previous);
+ next = free_list_unchecksum_ptr(szone, &free_head->next);
+ if (previous && !SMALL_PTR_IS_FREE(previous)) {
+ malloc_printf("*** invariant broken for %p (previous %p is not a free pointer)\n",
+ ptr, free_head->previous);
+ return 0;
+ }
+ if (next && !SMALL_PTR_IS_FREE(next)) {
+ malloc_printf("*** invariant broken for %p (next is not a free pointer)\n", ptr);
+ return 0;
+ }
+ if (SMALL_PREVIOUS_MSIZE(follower) != msize) {
+ malloc_printf("*** invariant broken for small free %p followed by %p in region [%p-%p] "
+ "(end marker incorrect) should be %d; in fact %d\n",
+ ptr, follower, SMALL_REGION_ADDRESS(region), region_end, msize, SMALL_PREVIOUS_MSIZE(follower));
+ return 0;
+ }
+ ptr = (unsigned char *)follower;
+ prev_free = SMALL_IS_FREE;
+ }
+ }
+ return 1;
+}
+
+static kern_return_t
+small_in_use_enumerator(task_t task, void *context, unsigned type_mask, szone_t *szone,
+ memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ size_t num_regions;
+ size_t index;
+ region_t *regions;
+ vm_range_t buffer[MAX_RECORDER_BUFFER];
+ unsigned count = 0;
+ kern_return_t err;
+ region_t region;
+ vm_range_t range;
+ vm_range_t admin_range;
+ vm_range_t ptr_range;
+ unsigned char *mapped_region;
+ msize_t *block_header;
+ unsigned block_index;
+ unsigned block_limit;
+ msize_t msize_and_free;
+ msize_t msize;
+ vm_address_t mag_last_free_ptr = 0;
+ msize_t mag_last_free_msize = 0;
+
+ region_hash_generation_t *srg_ptr;
+ err = reader(task, (vm_address_t)szone->small_region_generation, sizeof(region_hash_generation_t), (void **)&srg_ptr);
+ if (err) return err;
+
+ num_regions = srg_ptr->num_regions_allocated;
+ err = reader(task, (vm_address_t)srg_ptr->hashed_regions, sizeof(region_t) * num_regions, (void **)®ions);
+ if (err) return err;
+
+ for (index = 0; index < num_regions; ++index) {
+ region = regions[index];
+ if (HASHRING_OPEN_ENTRY != region && HASHRING_REGION_DEALLOCATED != region) {
+ range.address = (vm_address_t)SMALL_REGION_ADDRESS(region);
+ range.size = SMALL_REGION_SIZE;
+ if (type_mask & MALLOC_ADMIN_REGION_RANGE_TYPE) {
+ admin_range.address = range.address + SMALL_METADATA_START;
+ admin_range.size = SMALL_METADATA_SIZE;
+ 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 = NUM_SMALL_BLOCKS * SMALL_QUANTUM;
+ 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;
+
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(mapped_region);
+ magazine_t *small_mag_ptr;
+ err = reader(task, (vm_address_t)&(szone->small_magazines[mag_index]), sizeof(magazine_t),
+ (void **)&small_mag_ptr);
+ if (err) return err;
+
+ void *mag_last_free = small_mag_ptr->mag_last_free;
+ if (mag_last_free) {
+ mag_last_free_ptr = (uintptr_t) mag_last_free & ~(SMALL_QUANTUM - 1);
+ mag_last_free_msize = (uintptr_t) mag_last_free & (SMALL_QUANTUM - 1);
+ }
+
+ block_header = (msize_t *)(mapped_region + SMALL_METADATA_START + sizeof(region_trailer_t));
+ block_index = 0;
+ block_limit = NUM_SMALL_BLOCKS;
+ if (region == small_mag_ptr->mag_last_region)
+ block_limit -= SMALL_MSIZE_FOR_BYTES(small_mag_ptr->mag_bytes_free_at_end);
+ while (block_index < block_limit) {
+ msize_and_free = block_header[block_index];
+ msize = msize_and_free & ~ SMALL_IS_FREE;
+ if (! (msize_and_free & SMALL_IS_FREE) &&
+ range.address + SMALL_BYTES_FOR_MSIZE(block_index) != mag_last_free_ptr) {
+ // Block in use
+ buffer[count].address = range.address + SMALL_BYTES_FOR_MSIZE(block_index);
+ buffer[count].size = SMALL_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;
+ }
+ if (count) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE, buffer, count);
+ count = 0;
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+static void *
+small_malloc_from_free_list(szone_t *szone, magazine_t *small_mag_ptr, mag_index_t mag_index, msize_t msize)
+{
+ free_list_t *ptr;
+ msize_t this_msize;
+ grain_t slot = (msize <= szone->num_small_slots) ? msize - 1 : szone->num_small_slots - 1;
+ free_list_t **free_list = small_mag_ptr->mag_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;
+
+ // Assumes we've locked the region
+ CHECK_MAGAZINE_PTR_LOCKED(szone, small_mag_ptr, __PRETTY_FUNCTION__);
+
+ // Look for an exact match by checking the freelist for this msize.
+ //
+ ptr = *the_slot;
+ if (ptr) {
+ next = free_list_unchecksum_ptr(szone, &ptr->next);
+ if (next) {
+ next->previous = ptr->previous;
+ } else {
+ BITMAPN_CLR(small_mag_ptr->mag_bitmap, slot);
+ }
+ *the_slot = next;
+ this_msize = msize;
+ goto return_small_alloc;
+ }
+
+ // Mask off the bits representing slots holding free blocks smaller than
+ // the size we need. If there are no larger free blocks, try allocating
+ // from the free space at the end of the small region.
+ if (szone->is_largemem) {
+ // BITMAPN_CTZ implementation
+ unsigned idx = slot >> 5;
+ bitmap = 0;
+ unsigned mask = ~ ((1 << (slot & 31)) - 1);
+ for ( ; idx < SMALL_BITMAP_WORDS; ++idx ) {
+ bitmap = small_mag_ptr->mag_bitmap[idx] & mask;
+ if (bitmap != 0)
+ break;
+ mask = ~0U;
+ }
+ // Check for fallthrough: No bits set in bitmap
+ if ((bitmap == 0) && (idx == SMALL_BITMAP_WORDS))
+ goto try_small_from_end;
+
+ // Start looking at the first set bit, plus 32 bits for every word of
+ // zeroes or entries that were too small.
+ slot = BITMAP32_CTZ((&bitmap)) + (idx * 32);
+ } else {
+ bitmap = small_mag_ptr->mag_bitmap[0] & ~ ((1 << slot) - 1);
+ if (!bitmap)
+ goto try_small_from_end;
+
+ slot = BITMAP32_CTZ((&bitmap));
+ }
+ // FIXME: Explain use of - 1 here, last slot has special meaning
+ limit = free_list + szone->num_small_slots - 1;
+ free_list += slot;
+
+ if (free_list < limit) {
+ ptr = *free_list;
+ if (ptr) {
+
+ next = free_list_unchecksum_ptr(szone, &ptr->next);
+ *free_list = next;
+ if (next) {
+ next->previous = ptr->previous;
+ } else {
+ BITMAPN_CLR(small_mag_ptr->mag_bitmap, slot);
+ }
+ this_msize = SMALL_PTR_SIZE(ptr);
+ goto add_leftover_and_proceed;
+ }
+#if DEBUG_MALLOC
+ malloc_printf("in small_malloc_from_free_list(), mag_bitmap out of sync, slot=%d\n",slot);
+#endif
+ }
+
+ // We are now looking at the last slot, which contains blocks equal to, or
+ // due to coalescing of free blocks, larger than (num_small_slots - 1) * (small quantum size).
+ // If the last freelist is not empty, and the head contains a block that is
+ // larger than our request, then the remainder is put back on the free list.
+ //
+ ptr = *limit;
+ if (ptr) {
+ this_msize = SMALL_PTR_SIZE(ptr);
+ next = free_list_unchecksum_ptr(szone, &ptr->next);
+ if (this_msize - msize >= szone->num_small_slots) {
+ // the leftover will go back to the free list, so we optimize by
+ // modifying the free list rather than a pop and push of the head
+ leftover_msize = this_msize - msize;
+ leftover_ptr = (free_list_t *)((unsigned char *)ptr + SMALL_BYTES_FOR_MSIZE(msize));
+ *limit = leftover_ptr;
+ if (next) {
+ next->previous.u = free_list_checksum_ptr(szone, leftover_ptr);
+ }
+ leftover_ptr->previous = ptr->previous;
+ leftover_ptr->next = ptr->next;
+ small_meta_header_set_is_free(SMALL_META_HEADER_FOR_PTR(leftover_ptr),
+ SMALL_META_INDEX_FOR_PTR(leftover_ptr), leftover_msize);
+ // Store msize at the end of the block denoted by "leftover_ptr" (i.e. at a negative offset from follower)
+ SMALL_PREVIOUS_MSIZE(FOLLOWING_SMALL_PTR(leftover_ptr, leftover_msize)) = leftover_msize; // Access is safe
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in small_malloc_from_free_list(), last slot ptr=%p, msize=%d this_msize=%d\n", ptr, msize, this_msize);
+ }
+#endif
+ this_msize = msize;
+ goto return_small_alloc;
+ }
+ if (next) {
+ next->previous = ptr->previous;
+ }
+ *limit = next;
+ goto add_leftover_and_proceed;
+ }
+
+try_small_from_end:
+ // Let's see if we can use small_mag_ptr->mag_bytes_free_at_end
+ if (small_mag_ptr->mag_bytes_free_at_end >= SMALL_BYTES_FOR_MSIZE(msize)) {
+ ptr = (free_list_t *)(SMALL_REGION_END(small_mag_ptr->mag_last_region) -
+ small_mag_ptr->mag_bytes_free_at_end);
+ small_mag_ptr->mag_bytes_free_at_end -= SMALL_BYTES_FOR_MSIZE(msize);
+ if (small_mag_ptr->mag_bytes_free_at_end) {
+ // let's mark this block as in use to serve as boundary
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(ptr),
+ SMALL_META_INDEX_FOR_PTR((unsigned char *)ptr + SMALL_BYTES_FOR_MSIZE(msize)),
+ SMALL_MSIZE_FOR_BYTES(small_mag_ptr->mag_bytes_free_at_end));
+ }
+ this_msize = msize;
+ goto return_small_alloc;
+ }
+ return NULL;
+
+add_leftover_and_proceed:
+ if (this_msize > msize) {
+ leftover_msize = this_msize - msize;
+ leftover_ptr = (free_list_t *)((unsigned char *)ptr + SMALL_BYTES_FOR_MSIZE(msize));
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in small_malloc_from_free_list(), adding leftover ptr=%p, this_msize=%d\n", ptr, this_msize);
+ }
+#endif
+ small_free_list_add_ptr(szone, small_mag_ptr, leftover_ptr, leftover_msize);
+ this_msize = msize;
+ }
+
+return_small_alloc:
+ small_mag_ptr->mag_num_objects++;
+ small_mag_ptr->mag_num_bytes_in_objects += SMALL_BYTES_FOR_MSIZE(this_msize);
+
+ // Update this region's bytes in use count
+ region_trailer_t *node = REGION_TRAILER_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ size_t bytes_used = node->bytes_used + SMALL_BYTES_FOR_MSIZE(this_msize);
+ node->bytes_used = bytes_used;
+
+ // Emptiness discriminant
+ if (bytes_used < DENSITY_THRESHOLD(SMALL_REGION_PAYLOAD_BYTES)) {
+ /* After this allocation the region is still sparse, so it must have been even more so before
+ the allocation. That implies the region is already correctly marked. Do nothing. */
+ } else {
+ /* Region has crossed threshold from sparsity to density. Mark in not "suitable" on the
+ recirculation candidates list. */
+ node->recirc_suitable = FALSE;
+ }
+#if DEBUG_MALLOC
+ if (LOG(szone,ptr)) {
+ malloc_printf("in small_malloc_from_free_list(), ptr=%p, this_msize=%d, msize=%d\n", ptr, this_msize, msize);
+ }
+#endif
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(ptr), SMALL_META_INDEX_FOR_PTR(ptr), this_msize);
+ return ptr;
+}
+#undef DENSITY_THRESHOLD
+#undef K
+
+static INLINE void *
+small_malloc_should_clear(szone_t *szone, msize_t msize, boolean_t cleared_requested)
+{
+ void *ptr;
+ mag_index_t mag_index = mag_get_thread_index(szone);
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+
+ SZONE_MAGAZINE_PTR_LOCK(szone, small_mag_ptr);
+
+#if SMALL_CACHE
+ ptr = (void *)small_mag_ptr->mag_last_free;
+
+ if ((((uintptr_t)ptr) & (SMALL_QUANTUM - 1)) == msize) {
+ // we have a winner
+ small_mag_ptr->mag_last_free = NULL;
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ ptr = (void *)((uintptr_t)ptr & ~ (SMALL_QUANTUM - 1));
+ if (cleared_requested) {
+ memset(ptr, 0, SMALL_BYTES_FOR_MSIZE(msize));
+ }
+ return ptr;
+ }
+#endif /* SMALL_CACHE */
+
+ ptr = small_malloc_from_free_list(szone, small_mag_ptr, mag_index, msize);
+ if (ptr) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ if (cleared_requested) {
+ memset(ptr, 0, SMALL_BYTES_FOR_MSIZE(msize));
+ }
+ return ptr;
+ }
+
+ if (small_get_region_from_depot(szone, small_mag_ptr, mag_index)) {
+ ptr = small_malloc_from_free_list(szone, small_mag_ptr, mag_index, msize);
+ if (ptr) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ if (cleared_requested) {
+ memset(ptr, 0, SMALL_BYTES_FOR_MSIZE(msize));
+ }
+ return ptr;
+ }
+ }
+
+ ptr = small_malloc_from_region_no_lock(szone, small_mag_ptr, mag_index, msize);
+ // we don't clear because this freshly allocated space is pristine
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return ptr;
+}
+
+static NOINLINE void
+free_small_botch(szone_t *szone, free_list_t *ptr)
+{
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ szone_error(szone, 1, "double free", ptr, NULL);
+}
+
+static INLINE void
+free_small(szone_t *szone, void *ptr, region_t small_region, size_t known_size)
+{
+ msize_t msize;
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+
+ // ptr is known to be in small_region
+ if (known_size) {
+ msize = SMALL_MSIZE_FOR_BYTES(known_size + SMALL_QUANTUM - 1);
+ } else {
+ msize = SMALL_PTR_SIZE(ptr);
+ if (SMALL_PTR_IS_FREE(ptr)) {
+ free_small_botch(szone, ptr);
+ return;
+ }
+ }
+
+ SZONE_MAGAZINE_PTR_LOCK(szone, small_mag_ptr);
+
+#if SMALL_CACHE
+ // Depot does not participate in SMALL_CACHE since it can't be directly malloc()'d
+ if (DEPOT_MAGAZINE_INDEX != mag_index) {
+
+ void *ptr2 = small_mag_ptr->mag_last_free; // Might be NULL
+ region_t rgn2 = small_mag_ptr->mag_last_free_rgn;
+
+ /* check that we don't already have this pointer in the cache */
+ if (ptr == (void *)((uintptr_t)ptr2 & ~ (SMALL_QUANTUM - 1))) {
+ free_small_botch(szone, ptr);
+ return;
+ }
+
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) && msize)
+ memset(ptr, 0x55, SMALL_BYTES_FOR_MSIZE(msize));
+
+ small_mag_ptr->mag_last_free = (void *)(((uintptr_t)ptr) | msize);
+ small_mag_ptr->mag_last_free_rgn = small_region;
+
+ if (!ptr2) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return;
+ }
+
+ msize = (uintptr_t)ptr2 & (SMALL_QUANTUM - 1);
+ ptr = (void *)(((uintptr_t)ptr2) & ~(SMALL_QUANTUM - 1));
+ small_region = rgn2;
+ }
+#endif /* SMALL_CACHE */
+
+ // Now in the time it took to acquire the lock, the region may have migrated
+ // from one magazine to another. I.e. trailer->mag_index is volatile.
+ // In which case the magazine lock we obtained (namely magazines[mag_index].mag_lock)
+ // is stale. If so, keep on tryin' ...
+ region_trailer_t *trailer = REGION_TRAILER_FOR_SMALL_REGION(small_region);
+ mag_index_t refreshed_index;
+
+ while (mag_index != (refreshed_index = trailer->mag_index)) { // Note assignment
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+
+ mag_index = refreshed_index;
+ small_mag_ptr = &(szone->small_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_LOCK(szone, small_mag_ptr);
+ }
+
+ small_free_no_lock(szone, small_mag_ptr, mag_index, small_region, ptr, msize);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ CHECK(szone, __PRETTY_FUNCTION__);
+}
+
+static void
+print_small_free_list(szone_t *szone)
+{
+ free_list_t *ptr;
+ _SIMPLE_STRING b = _simple_salloc();
+ mag_index_t mag_index;
+
+ if (b) {
+ _simple_sappend(b, "small free sizes:\n");
+ for (mag_index = -1; mag_index < szone->num_small_magazines; mag_index++) {
+ grain_t slot = 0;
+ _simple_sprintf(b,"\tMagazine %d: ", mag_index);
+ while (slot < szone->num_small_slots) {
+ ptr = szone->small_magazines[mag_index].mag_free_list[slot];
+ if (ptr) {
+ _simple_sprintf(b, "%s%y[%d]; ", (slot == szone->num_small_slots-1) ? ">=" : "",
+ (slot + 1) * SMALL_QUANTUM, free_list_count(szone, ptr));
+ }
+ slot++;
+ }
+ _simple_sappend(b,"\n");
+ }
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+}
+
+static void
+print_small_region(szone_t *szone, boolean_t verbose, region_t region, size_t bytes_at_end)
+{
+ unsigned counts[1024];
+ unsigned in_use = 0;
+ uintptr_t start = (uintptr_t)SMALL_REGION_ADDRESS(region);
+ uintptr_t current = start;
+ uintptr_t limit = (uintptr_t)SMALL_REGION_END(region) - bytes_at_end;
+ msize_t msize_and_free;
+ msize_t msize;
+ unsigned ci;
+ _SIMPLE_STRING b;
+ uintptr_t pgTot = 0;
+
+ if (region == HASHRING_REGION_DEALLOCATED) {
+ if ((b = _simple_salloc()) != NULL) {
+ _simple_sprintf(b, "Small region [unknown address] was returned to the OS\n");
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+ return;
+ }
+
+ memset(counts, 0, sizeof(counts));
+ while (current < limit) {
+ msize_and_free = *SMALL_METADATA_FOR_PTR(current);
+ msize = msize_and_free & ~ SMALL_IS_FREE;
+ if (!msize) {
+ malloc_printf("*** error with %p: msize=%d\n", (void *)current, (unsigned)msize);
+ break;
+ }
+ if (!(msize_and_free & SMALL_IS_FREE)) {
+ // block in use
+ if (msize < 1024)
+ counts[msize]++;
+ in_use++;
+ } else {
+ uintptr_t pgLo = round_page(current + sizeof(free_list_t) + sizeof(msize_t));
+ uintptr_t pgHi = trunc_page(current + TINY_BYTES_FOR_MSIZE(msize) - sizeof(msize_t));
+
+ if (pgLo < pgHi) {
+ pgTot += (pgHi - pgLo);
+ }
+ }
+ current += SMALL_BYTES_FOR_MSIZE(msize);
+ }
+ if ((b = _simple_salloc()) != NULL) {
+ _simple_sprintf(b, "Small region [%p-%p, %y] \t", (void *)start, SMALL_REGION_END(region), (int)SMALL_REGION_SIZE);
+ _simple_sprintf(b, "Magazine=%d \t", MAGAZINE_INDEX_FOR_SMALL_REGION(region));
+ _simple_sprintf(b, "Allocations in use=%d \t Bytes in use=%ly \t", in_use, BYTES_USED_FOR_SMALL_REGION(region));
+ if (bytes_at_end)
+ _simple_sprintf(b, "Untouched=%ly ", bytes_at_end);
+ if (DEPOT_MAGAZINE_INDEX == MAGAZINE_INDEX_FOR_SMALL_REGION(region)) {
+ _simple_sprintf(b, "Advised MADV_FREE=%ly", pgTot);
+ } else {
+ _simple_sprintf(b, "Fragments subject to reclamation=%ly", pgTot);
+ }
+ if (verbose && in_use) {
+ _simple_sappend(b, "\n\tSizes in use: ");
+ for (ci = 0; ci < 1024; ci++)
+ if (counts[ci])
+ _simple_sprintf(b, "%d[%d] ", SMALL_BYTES_FOR_MSIZE(ci), counts[ci]);
+ }
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+}
+
+static boolean_t
+small_free_list_check(szone_t *szone, grain_t slot)
+{
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_small_magazines; mag_index++) {
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+ SZONE_MAGAZINE_PTR_LOCK(szone, small_mag_ptr);
+
+ unsigned count = 0;
+ free_list_t *ptr = szone->small_magazines[mag_index].mag_free_list[slot];
+ msize_t msize_and_free;
+ free_list_t *previous = NULL;
+
+ while (ptr) {
+ msize_and_free = *SMALL_METADATA_FOR_PTR(ptr);
+ if (!(msize_and_free & SMALL_IS_FREE)) {
+ malloc_printf("*** in-use ptr in free list slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0;
+ }
+ if (((uintptr_t)ptr) & (SMALL_QUANTUM - 1)) {
+ malloc_printf("*** unaligned ptr in free list slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0;
+ }
+ if (!small_region_for_ptr_no_lock(szone, ptr)) {
+ malloc_printf("*** ptr not in szone slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0;
+ }
+ if (free_list_unchecksum_ptr(szone, &ptr->previous) != previous) {
+ malloc_printf("*** previous incorrectly set slot=%d count=%d ptr=%p\n", slot, count, ptr);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ return 0;
+ }
+ previous = ptr;
+ ptr = free_list_unchecksum_ptr(szone, &ptr->next);
+ count++;
+ }
+
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ }
+ return 1;
+}
+
+/*******************************************************************************
+ * Large allocator implementation
+ ******************************************************************************/
+#pragma mark large allocator
+
+#if DEBUG_MALLOC
+
+static void
+large_debug_print(szone_t *szone)
+{
+ unsigned index;
+ large_entry_t *range;
+ _SIMPLE_STRING b = _simple_salloc();
+
+ if (b) {
+ for (index = 0, range = szone->large_entries; index < szone->num_large_entries; index++, range++)
+ if (range->address)
+ _simple_sprintf(b, "%d: %p(%y); ", index, range->address, range->size);
+
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX, "%s\n", _simple_string(b));
+ _simple_sfree(b);
+ }
+}
+#endif
+
+/*
+ * Scan the hash ring looking for an entry for the given pointer.
+ */
+static large_entry_t *
+large_entry_for_pointer_no_lock(szone_t *szone, const void *ptr)
+{
+ // result only valid with lock held
+ unsigned num_large_entries = szone->num_large_entries;
+ unsigned hash_index;
+ unsigned index;
+ large_entry_t *range;
+
+ if (!num_large_entries)
+ return NULL;
+
+ hash_index = ((uintptr_t)ptr >> vm_page_shift) % num_large_entries;
+ index = hash_index;
+
+ do {
+ range = szone->large_entries + index;
+ if (range->address == (vm_address_t)ptr)
+ return range;
+ if (0 == range->address)
+ return NULL; // end of chain
+ index++;
+ if (index == num_large_entries)
+ index = 0;
+ } while (index != hash_index);
+
+ return NULL;
+}
+
+static void
+large_entry_insert_no_lock(szone_t *szone, large_entry_t range)
+{
+ unsigned num_large_entries = szone->num_large_entries;
+ unsigned hash_index = (((uintptr_t)(range.address)) >> vm_page_shift) % num_large_entries;
+ unsigned index = hash_index;
+ large_entry_t *entry;
+
+ // assert(szone->num_large_objects_in_use < szone->num_large_entries); /* must be called with room to spare */
+
+ do {
+ entry = szone->large_entries + index;
+ if (0 == entry->address) {
+ *entry = range;
+ return; // end of chain
+ }
+ index++;
+ if (index == num_large_entries)
+ index = 0;
+ } while (index != hash_index);
+
+ // assert(0); /* must not fallthrough! */
+}
+
+// FIXME: can't we simply swap the (now empty) entry with the last entry on the collision chain for this hash slot?
+static INLINE void
+large_entries_rehash_after_entry_no_lock(szone_t *szone, large_entry_t *entry)
+{
+ unsigned num_large_entries = szone->num_large_entries;
+ unsigned hash_index = entry - szone->large_entries;
+ unsigned index = hash_index;
+ large_entry_t range;
+
+ // assert(entry->address == 0) /* caller must have cleared *entry */
+
+ do {
+ index++;
+ if (index == num_large_entries)
+ index = 0;
+ range = szone->large_entries[index];
+ if (0 == range.address)
+ return;
+ szone->large_entries[index].address = (vm_address_t)0;
+ szone->large_entries[index].size = 0;
+ szone->large_entries[index].did_madvise_reusable = FALSE;
+ large_entry_insert_no_lock(szone, range); // this will reinsert in the
+ // proper place
+ } while (index != hash_index);
+
+ // assert(0); /* since entry->address == 0, must not fallthrough! */
+}
+
+// FIXME: num should probably be a size_t, since you can theoretically allocate
+// more than 2^32-1 large_threshold objects in 64 bit.
+static INLINE large_entry_t *
+large_entries_alloc_no_lock(szone_t *szone, unsigned num)
+{
+ size_t size = num * sizeof(large_entry_t);
+
+ // Note that we allocate memory (via a system call) under a spin lock
+ // That is certainly evil, however it's very rare in the lifetime of a process
+ // The alternative would slow down the normal case
+ return allocate_pages(szone, round_page(size), 0, 0, VM_MEMORY_MALLOC_LARGE);
+}
+
+static void
+large_entries_free_no_lock(szone_t *szone, large_entry_t *entries, unsigned num, vm_range_t *range_to_deallocate)
+{
+ size_t size = num * sizeof(large_entry_t);
+
+ range_to_deallocate->address = (vm_address_t)entries;
+ range_to_deallocate->size = round_page(size);
+}
+
+static large_entry_t *
+large_entries_grow_no_lock(szone_t *szone, vm_range_t *range_to_deallocate)
+{
+ // sets range_to_deallocate
+ unsigned old_num_entries = szone->num_large_entries;
+ large_entry_t *old_entries = szone->large_entries;
+ // always an odd number for good hashing
+ unsigned new_num_entries = (old_num_entries) ? old_num_entries * 2 + 1 :
+ ((vm_page_size / sizeof(large_entry_t)) - 1);
+ large_entry_t *new_entries = large_entries_alloc_no_lock(szone, new_num_entries);
+ unsigned index = old_num_entries;
+ large_entry_t oldRange;
+
+ // if the allocation of new entries failed, bail
+ if (new_entries == NULL)
+ return NULL;
+
+ szone->num_large_entries = new_num_entries;
+ szone->large_entries = new_entries;
+
+ /* rehash entries into the new list */
+ while (index--) {
+ oldRange = old_entries[index];
+ if (oldRange.address) {
+ large_entry_insert_no_lock(szone, oldRange);
+ }
+ }
+
+ if (old_entries) {
+ large_entries_free_no_lock(szone, old_entries, old_num_entries, range_to_deallocate);
+ } else {
+ range_to_deallocate->address = (vm_address_t)0;
+ range_to_deallocate->size = 0;
+ }
+
+ return new_entries;
+}
+
+// frees the specific entry in the size table
+// returns a range to truly deallocate
+static vm_range_t
+large_entry_free_no_lock(szone_t *szone, large_entry_t *entry)
+{
+ vm_range_t range;
+
+ range.address = entry->address;
+ range.size = entry->size;
+
+ if (szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) {
+ protect((void *)range.address, range.size, VM_PROT_READ | VM_PROT_WRITE, szone->debug_flags);
+ range.address -= vm_page_size;
+ range.size += 2 * vm_page_size;
+ }
+
+ entry->address = 0;
+ entry->size = 0;
+ entry->did_madvise_reusable = FALSE;
+ large_entries_rehash_after_entry_no_lock(szone, entry);
+
+#if DEBUG_MALLOC
+ if (large_entry_for_pointer_no_lock(szone, (void *)range.address)) {
+ malloc_printf("*** freed entry %p still in use; num_large_entries=%d\n",
+ range.address, szone->num_large_entries);
+ large_debug_print(szone);
+ szone_sleep();
+ }
+#endif
+ return range;
+}
+
+static NOINLINE kern_return_t
+large_in_use_enumerator(task_t task, void *context, unsigned type_mask, vm_address_t large_entries_address,
+ unsigned num_entries, memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ unsigned index = 0;
+ vm_range_t buffer[MAX_RECORDER_BUFFER];
+ unsigned count = 0;
+ large_entry_t *entries;
+ kern_return_t err;
+ vm_range_t range;
+ large_entry_t entry;
+
+ err = reader(task, large_entries_address, sizeof(large_entry_t) * num_entries, (void **)&entries);
+ if (err)
+ return err;
+
+ index = num_entries;
+ if (type_mask & MALLOC_ADMIN_REGION_RANGE_TYPE) {
+ range.address = large_entries_address;
+ range.size = round_page(num_entries * sizeof(large_entry_t));
+ recorder(task, context, MALLOC_ADMIN_REGION_RANGE_TYPE, &range, 1);
+ }
+ if (type_mask & (MALLOC_PTR_IN_USE_RANGE_TYPE | MALLOC_PTR_REGION_RANGE_TYPE)) {
+ while (index--) {
+ entry = entries[index];
+ if (entry.address) {
+ range.address = entry.address;
+ range.size = entry.size;
+ buffer[count++] = range;
+ if (count >= MAX_RECORDER_BUFFER) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE | MALLOC_PTR_REGION_RANGE_TYPE,
+ buffer, count);
+ count = 0;
+ }
+ }
+ }
+ }
+ if (count) {
+ recorder(task, context, MALLOC_PTR_IN_USE_RANGE_TYPE | MALLOC_PTR_REGION_RANGE_TYPE,
+ buffer, count);
+ }
+ return 0;
+}
+
+static void *
+large_malloc(szone_t *szone, size_t num_pages, unsigned char alignment,
+ boolean_t cleared_requested)
+{
+ void *addr;
+ vm_range_t range_to_deallocate;
+ size_t size;
+ large_entry_t large_entry;
+
+ if (!num_pages)
+ num_pages = 1; // minimal allocation size for this szone
+ size = (size_t)num_pages << vm_page_shift;
+ range_to_deallocate.size = 0;
+ range_to_deallocate.address = 0;
+
+#if LARGE_CACHE
+ if (size < LARGE_CACHE_SIZE_ENTRY_LIMIT) { // Look for a large_entry_t on the death-row cache?
+ SZONE_LOCK(szone);
+
+ int i, best = -1, idx = szone->large_entry_cache_newest, stop_idx = szone->large_entry_cache_oldest;
+ size_t best_size = SIZE_T_MAX;
+
+ while (1) { // Scan large_entry_cache for best fit, starting with most recent entry
+ size_t this_size = szone->large_entry_cache[idx].size;
+
+ if (size == this_size) { // size match!
+ best = idx;
+ best_size = this_size;
+ break;
+ }
+
+ if (size <= this_size && this_size < best_size) { // improved fit?
+ best = idx;
+ best_size = this_size;
+ }
+
+ if (idx == stop_idx) // exhausted live ring?
+ break;
+
+ if (idx)
+ idx--; // bump idx down
+ else
+ idx = LARGE_ENTRY_CACHE_SIZE - 1; // wrap idx
+ }
+
+ if (best > -1 && (best_size - size) < size) { //limit fragmentation to 50%
+ addr = (void *)szone->large_entry_cache[best].address;
+ boolean_t was_madvised_reusable = szone->large_entry_cache[best].did_madvise_reusable;
+
+ // Compact live ring to fill entry now vacated at large_entry_cache[best]
+ // while preserving time-order
+ if (szone->large_entry_cache_oldest < szone->large_entry_cache_newest) {
+
+ // Ring hasn't wrapped. Fill in from right.
+ for (i = best; i < szone->large_entry_cache_newest; ++i)
+ szone->large_entry_cache[i] = szone->large_entry_cache[i + 1];
+
+ szone->large_entry_cache_newest--; // Pull in right endpoint.
+
+ } else if (szone->large_entry_cache_newest < szone->large_entry_cache_oldest) {
+
+ // Ring has wrapped. Arrange to fill in from the contiguous side.
+ if (best <= szone->large_entry_cache_newest) {
+ // Fill from right.
+ for (i = best; i < szone->large_entry_cache_newest; ++i)
+ szone->large_entry_cache[i] = szone->large_entry_cache[i + 1];
+
+ if (0 < szone->large_entry_cache_newest)
+ szone->large_entry_cache_newest--;
+ else
+ szone->large_entry_cache_newest = LARGE_ENTRY_CACHE_SIZE - 1;
+ } else {
+ // Fill from left.
+ for ( i = best; i > szone->large_entry_cache_oldest; --i)
+ szone->large_entry_cache[i] = szone->large_entry_cache[i - 1];
+
+ if (szone->large_entry_cache_oldest < LARGE_ENTRY_CACHE_SIZE - 1)
+ szone->large_entry_cache_oldest++;
+ else
+ szone->large_entry_cache_oldest = 0;
+ }
+
+ } else {
+ // By trichotomy, large_entry_cache_newest == large_entry_cache_oldest.
+ // That implies best == large_entry_cache_newest == large_entry_cache_oldest
+ // and the ring is now empty.
+ szone->large_entry_cache[best].address = 0;
+ szone->large_entry_cache[best].size = 0;
+ szone->large_entry_cache[best].did_madvise_reusable = FALSE;
+ }
+
+ if ((szone->num_large_objects_in_use + 1) * 4 > szone->num_large_entries) {
+ // density of hash table too high; grow table
+ // we do that under lock to avoid a race
+ large_entry_t *entries = large_entries_grow_no_lock(szone, &range_to_deallocate);
+ if (entries == NULL) {
+ SZONE_UNLOCK(szone);
+ return NULL;
+ }
+ }
+
+ large_entry.address = (vm_address_t)addr;
+ large_entry.size = best_size;
+ large_entry.did_madvise_reusable = FALSE;
+ large_entry_insert_no_lock(szone, large_entry);
+
+ szone->num_large_objects_in_use ++;
+ szone->num_bytes_in_large_objects += best_size;
+ if (!was_madvised_reusable)
+ szone->large_entry_cache_hoard_bytes -= best_size;
+ SZONE_UNLOCK(szone);
+
+ if (range_to_deallocate.size) {
+ // we deallocate outside the lock
+ deallocate_pages(szone, (void *)range_to_deallocate.address, range_to_deallocate.size, 0);
+ }
+
+ // Perform the madvise() outside the lock.
+ // Typically the madvise() is successful and we'll quickly return from this routine.
+ // In the unusual case of failure, reacquire the lock to unwind.
+ if (was_madvised_reusable && -1 == madvise(addr, size, MADV_FREE_REUSE)) {
+ /* -1 return: VM map entry change makes this unfit for reuse. */
+#if DEBUG_MALLOC
+ szone_error(szone, 1, "large_malloc madvise(..., MADV_FREE_REUSE) failed", addr, NULL);
+#endif
+
+ SZONE_LOCK(szone);
+ szone->num_large_objects_in_use--;
+ szone->num_bytes_in_large_objects -= large_entry.size;
+
+ // Re-acquire "entry" after interval just above where we let go the lock.
+ large_entry_t *entry = large_entry_for_pointer_no_lock(szone, addr);
+ if (NULL == entry) {
+ szone_error(szone, 1, "entry for pointer being discarded from death-row vanished", addr, NULL);
+ SZONE_UNLOCK(szone);
+ } else {
+
+ range_to_deallocate = large_entry_free_no_lock(szone, entry);
+ SZONE_UNLOCK(szone);
+
+ if (range_to_deallocate.size) {
+ // we deallocate outside the lock
+ deallocate_pages(szone, (void *)range_to_deallocate.address, range_to_deallocate.size, 0);
+ }
+ }
+ /* Fall through to allocate_pages() afresh. */
+ } else {
+ if (cleared_requested) {
+ memset(addr, 0, size);
+ }
+
+ return addr;
+ }
+ } else {
+ SZONE_UNLOCK(szone);
+ }
+ }
+
+ range_to_deallocate.size = 0;
+ range_to_deallocate.address = 0;
+#endif /* LARGE_CACHE */
+
+ addr = allocate_pages(szone, size, alignment, szone->debug_flags, VM_MEMORY_MALLOC_LARGE);
+ if (addr == NULL) {
+ return NULL;
+ }
+
+ SZONE_LOCK(szone);
+ if ((szone->num_large_objects_in_use + 1) * 4 > szone->num_large_entries) {
+ // density of hash table too high; grow table
+ // we do that under lock to avoid a race
+ large_entry_t *entries = large_entries_grow_no_lock(szone, &range_to_deallocate);
+ if (entries == NULL) {
+ SZONE_UNLOCK(szone);
+ return NULL;
+ }
+ }
+
+ large_entry.address = (vm_address_t)addr;
+ large_entry.size = size;
+ large_entry.did_madvise_reusable = FALSE;
+ large_entry_insert_no_lock(szone, large_entry);
+
+ szone->num_large_objects_in_use ++;
+ szone->num_bytes_in_large_objects += size;
+ SZONE_UNLOCK(szone);
+
+ if (range_to_deallocate.size) {
+ // we deallocate outside the lock
+ deallocate_pages(szone, (void *)range_to_deallocate.address, range_to_deallocate.size, 0);
+ }
+ return addr;
+}
+
+static NOINLINE void
+free_large(szone_t *szone, void *ptr)
+{
+ // We have established ptr is page-aligned and neither tiny nor small
+ large_entry_t *entry;
+ vm_range_t vm_range_to_deallocate;
+
+ SZONE_LOCK(szone);
+ entry = large_entry_for_pointer_no_lock(szone, ptr);
+ if (entry) {
+#if LARGE_CACHE
+#ifndef MADV_CAN_REUSE
+#define MADV_CAN_REUSE 9 /* per Francois, for testing until xnu is resubmitted to B&I */
+#endif
+ if (entry->size < LARGE_CACHE_SIZE_ENTRY_LIMIT &&
+ -1 != madvise((void *)(entry->address), entry->size, MADV_CAN_REUSE)) { // Put the large_entry_t on the death-row cache?
+ int idx = szone->large_entry_cache_newest, stop_idx = szone->large_entry_cache_oldest;
+ large_entry_t this_entry = *entry; // Make a local copy, "entry" is volatile when lock is let go.
+ boolean_t reusable = TRUE;
+ boolean_t should_madvise = szone->large_entry_cache_hoard_bytes + this_entry.size > szone->large_entry_cache_hoard_lmit;
+
+ // Already freed?
+ // [Note that repeated entries in death-row risk vending the same entry subsequently
+ // to two different malloc() calls. By checking here the (illegal) double free
+ // is accommodated, matching the behavior of the previous implementation.]
+ while (1) { // Scan large_entry_cache starting with most recent entry
+ if (szone->large_entry_cache[idx].address == entry->address) {
+ szone_error(szone, 1, "pointer being freed already on death-row", ptr, NULL);
+ SZONE_UNLOCK(szone);
+ return;
+ }
+
+ if (idx == stop_idx) // exhausted live ring?
+ break;
+
+ if (idx)
+ idx--; // bump idx down
+ else
+ idx = LARGE_ENTRY_CACHE_SIZE - 1; // wrap idx
+ }
+
+ SZONE_UNLOCK(szone);
+
+ if (szone->debug_flags & SCALABLE_MALLOC_PURGEABLE) { // Are we a purgable zone?
+ int state = VM_PURGABLE_NONVOLATILE; // restore to default condition
+
+ if (KERN_SUCCESS != vm_purgable_control(mach_task_self(), this_entry.address, VM_PURGABLE_SET_STATE, &state)) {
+ malloc_printf("*** can't vm_purgable_control(..., VM_PURGABLE_SET_STATE) for large freed block at %p\n", this_entry.address);
+ reusable = FALSE;
+ }
+ }
+
+ if (szone->large_legacy_reset_mprotect) { // Linked for Leopard?
+ // Accomodate Leopard apps that (illegally) mprotect() their own guard pages on large malloc'd allocations
+ kern_return_t err = vm_protect(mach_task_self(), (vm_address_t)(this_entry.address), this_entry.size,
+ 0, PROT_READ | PROT_WRITE);
+ if (err) {
+ malloc_printf("*** can't reset protection for large freed block at %p\n", this_entry.address);
+ reusable = FALSE;
+ }
+ }
+
+ // madvise(..., MADV_REUSABLE) death-row arrivals if hoarding would exceed large_entry_cache_hoard_lmit
+ if (should_madvise) {
+ // Issue madvise to avoid paging out the dirtied free()'d pages in "entry"
+ MAGMALLOC_MADVFREEREGION((void *)szone, (void *)0, (void *)(this_entry.address), this_entry.size); // DTrace USDT Probe
+
+ if (-1 == madvise((void *)(this_entry.address), this_entry.size, MADV_FREE_REUSABLE)) {
+ /* -1 return: VM map entry change makes this unfit for reuse. */
+#if DEBUG_MALLOC
+ szone_error(szone, 1, "free_large madvise(..., MADV_FREE_REUSABLE) failed", (void *)this_entry.address, NULL);
+#endif
+ reusable = FALSE;
+ }
+ }
+
+ SZONE_LOCK(szone);
+
+ // Re-acquire "entry" after interval just above where we let go the lock.
+ entry = large_entry_for_pointer_no_lock(szone, ptr);
+ if (NULL == entry) {
+ szone_error(szone, 1, "entry for pointer being freed from death-row vanished", ptr, NULL);
+ SZONE_UNLOCK(szone);
+ return;
+ }
+
+ // Add "entry" to death-row ring
+ if (reusable) {
+ int idx = szone->large_entry_cache_newest; // Most recently occupied
+ vm_address_t addr;
+ size_t adjsize;
+
+ if (szone->large_entry_cache_newest == szone->large_entry_cache_oldest &&
+ 0 == szone->large_entry_cache[idx].address) {
+ // Ring is empty, idx is good as it stands
+ addr = 0;
+ adjsize = 0;
+ } else {
+ // Extend the queue to the "right" by bumping up large_entry_cache_newest
+ if (idx == LARGE_ENTRY_CACHE_SIZE - 1)
+ idx = 0; // Wrap index
+ else
+ idx++; // Bump index
+
+ if (idx == szone->large_entry_cache_oldest) { // Fully occupied
+ // Drop this entry from the cache and deallocate the VM
+ addr = szone->large_entry_cache[idx].address;
+ adjsize = szone->large_entry_cache[idx].size;
+ if (!szone->large_entry_cache[idx].did_madvise_reusable)
+ szone->large_entry_cache_hoard_bytes -= adjsize;
+ } else {
+ // Using an unoccupied cache slot
+ addr = 0;
+ adjsize = 0;
+ }
+ }
+
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE))
+ memset((void *)(entry->address), 0x55, entry->size);
+
+ entry->did_madvise_reusable = should_madvise; // Was madvise()'d above?
+ if (!should_madvise) // Entered on death-row without madvise() => up the hoard total
+ szone->large_entry_cache_hoard_bytes += entry->size;
+
+ szone->large_entry_cache[idx] = *entry;
+ szone->large_entry_cache_newest = idx;
+
+ szone->num_large_objects_in_use--;
+ szone->num_bytes_in_large_objects -= entry->size;
+
+ (void)large_entry_free_no_lock(szone, entry);
+
+ if (0 == addr) {
+ SZONE_UNLOCK(szone);
+ return;
+ }
+
+ // Fall through to drop large_entry_cache_oldest from the cache,
+ // and then deallocate its pages.
+
+ // Trim the queue on the "left" by bumping up large_entry_cache_oldest
+ if (szone->large_entry_cache_oldest == LARGE_ENTRY_CACHE_SIZE - 1)
+ szone->large_entry_cache_oldest = 0;
+ else
+ szone->large_entry_cache_oldest++;
+
+ // we deallocate_pages, including guard pages, outside the lock
+ SZONE_UNLOCK(szone);
+ deallocate_pages(szone, (void *)addr, (size_t)adjsize, 0);
+ return;
+ } else {
+ /* fall through to discard an allocation that is not reusable */
+ }
+ }
+#endif /* LARGE_CACHE */
+
+ szone->num_large_objects_in_use--;
+ szone->num_bytes_in_large_objects -= entry->size;
+
+ vm_range_to_deallocate = large_entry_free_no_lock(szone, entry);
+ } else {
+#if DEBUG_MALLOC
+ large_debug_print(szone);
+#endif
+ szone_error(szone, 1, "pointer being freed was not allocated", ptr, NULL);
+ SZONE_UNLOCK(szone);
+ return;
+ }
+ SZONE_UNLOCK(szone); // we release the lock asap
+ CHECK(szone, __PRETTY_FUNCTION__);
+
+ // we deallocate_pages, including guard pages, outside the lock
+ if (vm_range_to_deallocate.address) {
+#if DEBUG_MALLOC
+ // FIXME: large_entry_for_pointer_no_lock() needs the lock held ...
+ if (large_entry_for_pointer_no_lock(szone, (void *)vm_range_to_deallocate.address)) {
+ malloc_printf("*** invariant broken: %p still in use num_large_entries=%d\n",
+ vm_range_to_deallocate.address, szone->num_large_entries);
+ large_debug_print(szone);
+ szone_sleep();
+ }
+#endif
+ deallocate_pages(szone, (void *)vm_range_to_deallocate.address, (size_t)vm_range_to_deallocate.size, 0);
+ }
+}
+
+static INLINE int
+large_try_realloc_in_place(szone_t *szone, void *ptr, size_t old_size, size_t new_size)
+{
+ vm_address_t addr = (vm_address_t)ptr + old_size;
+ large_entry_t *large_entry;
+ kern_return_t err;
+
+ SZONE_LOCK(szone);
+ large_entry = large_entry_for_pointer_no_lock(szone, (void *)addr);
+ SZONE_UNLOCK(szone);
+
+ if (large_entry) { // check if "addr = ptr + old_size" is already spoken for
+ return 0; // large pointer already exists in table - extension is not going to work
+ }
+
+ new_size = round_page(new_size);
+ /*
+ * Ask for allocation at a specific address, and mark as realloc
+ * to request coalescing with previous realloc'ed extensions.
+ */
+ err = vm_allocate(mach_task_self(), &addr, new_size - old_size, VM_MAKE_TAG(VM_MEMORY_REALLOC));
+ if (err != KERN_SUCCESS) {
+ return 0;
+ }
+
+ SZONE_LOCK(szone);
+ /* extend existing large entry */
+ large_entry = large_entry_for_pointer_no_lock(szone, ptr);
+ if (!large_entry) {
+ szone_error(szone, 1, "large entry reallocated is not properly in table", ptr, NULL);
+ SZONE_UNLOCK(szone);
+ return 0; // Bail, leaking "addr"
+ }
+
+ large_entry->address = (vm_address_t)ptr;
+ large_entry->size = new_size;
+ szone->num_bytes_in_large_objects += new_size - old_size;
+ SZONE_UNLOCK(szone); // we release the lock asap
+
+ return 1;
+}
+
+/********************* Zone call backs ************************/
+/*
+ * Mark these NOINLINE to avoid bloating the purgeable zone call backs
+ */
+static NOINLINE void
+szone_free(szone_t *szone, void *ptr)
+{
+ region_t tiny_region;
+ region_t small_region;
+
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr))
+ malloc_printf("in szone_free with %p\n", ptr);
+#endif
+ if (!ptr)
+ return;
+ /*
+ * Try to free to a tiny region.
+ */
+ if ((uintptr_t)ptr & (TINY_QUANTUM - 1)) {
+ szone_error(szone, 1, "Non-aligned pointer being freed", ptr, NULL);
+ return;
+ }
+ if ((tiny_region = tiny_region_for_ptr_no_lock(szone, ptr)) != NULL) {
+ if (TINY_INDEX_FOR_PTR(ptr) >= NUM_TINY_BLOCKS) {
+ szone_error(szone, 1, "Pointer to metadata being freed", ptr, NULL);
+ return;
+ }
+ free_tiny(szone, ptr, tiny_region, 0);
+ return;
+ }
+
+ /*
+ * Try to free to a small region.
+ */
+ if ((uintptr_t)ptr & (SMALL_QUANTUM - 1)) {
+ szone_error(szone, 1, "Non-aligned pointer being freed (2)", ptr, NULL);
+ return;
+ }
+ if ((small_region = small_region_for_ptr_no_lock(szone, ptr)) != NULL) {
+ if (SMALL_META_INDEX_FOR_PTR(ptr) >= NUM_SMALL_BLOCKS) {
+ szone_error(szone, 1, "Pointer to metadata being freed (2)", ptr, NULL);
+ return;
+ }
+ free_small(szone, ptr, small_region, 0);
+ return;
+ }
+
+ /* check that it's a legal large allocation */
+ if ((uintptr_t)ptr & (vm_page_size - 1)) {
+ szone_error(szone, 1, "non-page-aligned, non-allocated pointer being freed", ptr, NULL);
+ return;
+ }
+ free_large(szone, ptr);
+}
+
+static NOINLINE void
+szone_free_definite_size(szone_t *szone, void *ptr, size_t size)
+{
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr))
+ malloc_printf("in szone_free_definite_size with %p\n", ptr);
+
+ if (0 == size) {
+ szone_error(szone, 1, "pointer of size zero being freed", ptr, NULL);
+ return;
+ }
+
+#endif
+ if (!ptr)
+ return;
+
+ /*
+ * Try to free to a tiny region.
+ */
+ if ((uintptr_t)ptr & (TINY_QUANTUM - 1)) {
+ szone_error(szone, 1, "Non-aligned pointer being freed", ptr, NULL);
+ return;
+ }
+ if (size <= (NUM_TINY_SLOTS - 1)*TINY_QUANTUM) {
+ if (TINY_INDEX_FOR_PTR(ptr) >= NUM_TINY_BLOCKS) {
+ szone_error(szone, 1, "Pointer to metadata being freed", ptr, NULL);
+ return;
+ }
+ free_tiny(szone, ptr, TINY_REGION_FOR_PTR(ptr), size);
+ return;
+ }
+
+ /*
+ * Try to free to a small region.
+ */
+ if ((uintptr_t)ptr & (SMALL_QUANTUM - 1)) {
+ szone_error(szone, 1, "Non-aligned pointer being freed (2)", ptr, NULL);
+ return;
+ }
+ if (!((szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL) &&
+ (size <= szone->large_threshold)) {
+ if (SMALL_META_INDEX_FOR_PTR(ptr) >= NUM_SMALL_BLOCKS) {
+ szone_error(szone, 1, "Pointer to metadata being freed (2)", ptr, NULL);
+ return;
+ }
+ free_small(szone, ptr, SMALL_REGION_FOR_PTR(ptr), size);
+ return;
+ }
+
+ /* check that it's a legal large allocation */
+ if ((uintptr_t)ptr & (vm_page_size - 1)) {
+ szone_error(szone, 1, "non-page-aligned, non-allocated pointer being freed", ptr, NULL);
+ return;
+ }
+ free_large(szone, ptr);
+}
+
+static NOINLINE void *
+szone_malloc_should_clear(szone_t *szone, size_t size, boolean_t cleared_requested)
+{
+ void *ptr;
+ msize_t msize;
+
+ if (size <= (NUM_TINY_SLOTS - 1)*TINY_QUANTUM) {
+ // think tiny
+ msize = TINY_MSIZE_FOR_BYTES(size + TINY_QUANTUM - 1);
+ if (!msize)
+ msize = 1;
+ ptr = tiny_malloc_should_clear(szone, msize, cleared_requested);
+ } else if (!((szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL) &&
+ (size <= szone->large_threshold)) {
+ // think small
+ msize = SMALL_MSIZE_FOR_BYTES(size + SMALL_QUANTUM - 1);
+ if (! msize)
+ msize = 1;
+ ptr = small_malloc_should_clear(szone, msize, cleared_requested);
+ } else {
+ // large
+ size_t num_pages = round_page(size) >> vm_page_shift;
+ if (num_pages == 0) /* Overflowed */
+ ptr = 0;
+ else
+ ptr = large_malloc(szone, num_pages, 0, cleared_requested);
+ }
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr))
+ malloc_printf("szone_malloc returned %p\n", ptr);
+#endif
+ /*
+ * If requested, scribble on allocated memory.
+ */
+ if ((szone->debug_flags & SCALABLE_MALLOC_DO_SCRIBBLE) && ptr && !cleared_requested && size)
+ memset(ptr, 0xaa, size);
+
+ return ptr;
+}
+
+static NOINLINE void *
+szone_malloc(szone_t *szone, size_t size) {
+ return szone_malloc_should_clear(szone, size, 0);
+}
+
+static NOINLINE void *
+szone_calloc(szone_t *szone, size_t num_items, size_t size)
+{
+ size_t total_bytes = num_items * size;
+
+ // Check for overflow of integer multiplication
+ if (num_items > 1) {
+#if __LP64__ /* size_t is uint64_t */
+ if ((num_items | size) & 0xffffffff00000000ul) {
+ // num_items or size equals or exceeds sqrt(2^64) == 2^32, appeal to wider arithmetic
+ __uint128_t product = ((__uint128_t)num_items) * ((__uint128_t)size);
+ if ((uint64_t)(product >> 64)) // compiles to test on upper register of register pair
+ return NULL;
+ }
+#else /* size_t is uint32_t */
+ if ((num_items | size) & 0xffff0000ul) {
+ // num_items or size equals or exceeds sqrt(2^32) == 2^16, appeal to wider arithmetic
+ uint64_t product = ((uint64_t)num_items) * ((uint64_t)size);
+ if ((uint32_t)(product >> 32)) // compiles to test on upper register of register pair
+ return NULL;
+ }
+#endif
+ }
+
+ return szone_malloc_should_clear(szone, total_bytes, 1);
+}
+
+static NOINLINE void *
+szone_valloc(szone_t *szone, size_t size)
+{
+ void *ptr;
+
+ if (size <= szone->large_threshold) {
+ ptr = szone_memalign(szone, vm_page_size, size);
+ } else {
+ size_t num_pages;
+
+ num_pages = round_page(size) >> vm_page_shift;
+ ptr = large_malloc(szone, num_pages, 0, 0);
+ }
+
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr))
+ malloc_printf("szone_valloc returned %p\n", ptr);
+#endif
+ return ptr;
+}
+
+/* Isolate PIC-base load (for __is_threaded) here. */
+static NOINLINE size_t
+szone_size_try_large(szone_t *szone, const void *ptr)
+{
+ size_t size = 0;
+ large_entry_t *entry;
+
+ SZONE_LOCK(szone);
+ entry = large_entry_for_pointer_no_lock(szone, ptr);
+ if (entry) {
+ size = entry->size;
+ }
+ SZONE_UNLOCK(szone);
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("szone_size for %p returned %d\n", ptr, (unsigned)size);
+ }
+#endif
+ return size;
+}
+
+static NOINLINE size_t
+szone_size(szone_t *szone, const void *ptr)
+{
+ boolean_t is_free;
+ msize_t msize, msize_and_free;
+
+ if (!ptr)
+ return 0;
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("in szone_size for %p (szone=%p)\n", ptr, szone);
+ }
+#endif
+
+ /*
+ * Look for it in a tiny region.
+ */
+ if ((uintptr_t)ptr & (TINY_QUANTUM - 1))
+ return 0;
+ if (tiny_region_for_ptr_no_lock(szone, ptr)) {
+ if (TINY_INDEX_FOR_PTR(ptr) >= NUM_TINY_BLOCKS)
+ return 0;
+ msize = get_tiny_meta_header(ptr, &is_free);
+ if (is_free)
+ return 0;
+#if TINY_CACHE
+ {
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(TINY_REGION_FOR_PTR(ptr));
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+
+ if (msize < TINY_QUANTUM && ptr == (void *)((uintptr_t)(tiny_mag_ptr->mag_last_free) & ~ (TINY_QUANTUM - 1)))
+ return 0;
+ }
+#endif
+ return TINY_BYTES_FOR_MSIZE(msize);
+ }
+
+ /*
+ * Look for it in a small region.
+ */
+ if ((uintptr_t)ptr & (SMALL_QUANTUM - 1))
+ return 0;
+ if (small_region_for_ptr_no_lock(szone, ptr)) {
+ if (SMALL_META_INDEX_FOR_PTR(ptr) >= NUM_SMALL_BLOCKS)
+ return 0;
+ msize_and_free = *SMALL_METADATA_FOR_PTR(ptr);
+ if (msize_and_free & SMALL_IS_FREE)
+ return 0;
+#if SMALL_CACHE
+ {
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
+ magazine_t *small_mag_ptr = &(szone->small_magazines[mag_index]);
+
+ if (ptr == (void *)((uintptr_t)(small_mag_ptr->mag_last_free) & ~ (SMALL_QUANTUM - 1)))
+ return 0;
+ }
+#endif
+ return SMALL_BYTES_FOR_MSIZE(msize_and_free);
+ }
+
+ /*
+ * If not page-aligned, it cannot have come from a large allocation.
+ */
+ if ((uintptr_t)ptr & (vm_page_size - 1))
+ return 0;
+
+ /*
+ * Look for it in a large entry.
+ */
+ return szone_size_try_large(szone, ptr);
+}
+
+static NOINLINE void *
+szone_realloc(szone_t *szone, void *ptr, size_t new_size)
+{
+ size_t old_size;
+ void *new_ptr;
+
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("in szone_realloc for %p, %d\n", ptr, (unsigned)new_size);
+ }
+#endif
+ if (!ptr) {
+ ptr = szone_malloc(szone, new_size);
+ return ptr;
+ }
+ old_size = szone_size(szone, ptr);
+ if (!old_size) {
+ szone_error(szone, 1, "pointer being reallocated was not allocated", ptr, NULL);
+ return NULL;
+ }
+ /* we never shrink an allocation */
+ if (old_size >= new_size)
+ return ptr;
+
+ /*
+ * If the new size suits the tiny allocator and the pointer being resized
+ * belongs to a tiny region, try to reallocate in-place.
+ */
+ if ((new_size + TINY_QUANTUM - 1) <= (NUM_TINY_SLOTS - 1) * TINY_QUANTUM) {
+ if (tiny_region_for_ptr_no_lock(szone, ptr) != NULL) {
+ if (tiny_try_realloc_in_place(szone, ptr, old_size, new_size)) {
+ return ptr;
+ }
+ }
+
+ /*
+ * If the new size suits the small allocator and the pointer being resized
+ * belongs to a small region, and we're not protecting the small allocations
+ * try to reallocate in-place.
+ */
+ } else if (!((szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL) &&
+ ((new_size + SMALL_QUANTUM - 1) <= szone->large_threshold) &&
+ (small_region_for_ptr_no_lock(szone, ptr) != NULL)) {
+ if (small_try_realloc_in_place(szone, ptr, old_size, new_size)) {
+ return ptr;
+ }
+
+ /*
+ * If the allocation's a large allocation, try to reallocate in-place there.
+ */
+ } else if (!((szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL) &&
+ !(szone->debug_flags & SCALABLE_MALLOC_PURGEABLE) &&
+ (old_size > szone->large_threshold)) {
+ if (large_try_realloc_in_place(szone, ptr, old_size, new_size)) {
+ return ptr;
+ }
+ }
+
+ /*
+ * Can't reallocate in place for whatever reason; allocate a new buffer and copy.
+ */
+ new_ptr = szone_malloc(szone, new_size);
+ if (new_ptr == NULL)
+ return NULL;
+
+ /*
+ * If the allocation's large enough, try to copy using VM. If that fails, or
+ * if it's too small, just copy by hand.
+ */
+ if ((old_size < szone->vm_copy_threshold) ||
+ vm_copy(mach_task_self(), (vm_address_t)ptr, old_size, (vm_address_t)new_ptr))
+ memcpy(new_ptr, ptr, old_size);
+ szone_free(szone, ptr);
+
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr)) {
+ malloc_printf("szone_realloc returned %p for %d\n", new_ptr, (unsigned)new_size);
+ }
+#endif
+ return new_ptr;
+}
+
+static NOINLINE void *
+szone_memalign(szone_t *szone, size_t alignment, size_t size)
+{
+ if ((size + alignment) < size) // size_t arithmetic wrapped!
+ return NULL;
+
+ // alignment is gauranteed a power of 2 at least as large as sizeof(void *), hence non-zero.
+ // Since size + alignment didn't wrap, 0 <= size + alignment - 1 < size + alignment
+ size_t span = size + alignment - 1;
+
+ if (alignment <= TINY_QUANTUM) {
+ return szone_malloc(szone, size); // Trivially satisfied by tiny, small, or large
+
+ } else if (span <= (NUM_TINY_SLOTS - 1)*TINY_QUANTUM) {
+ msize_t mspan = TINY_MSIZE_FOR_BYTES(span + TINY_QUANTUM - 1);
+ void *p = szone_malloc(szone, span); // avoids inlining tiny_malloc_should_clear(szone, mspan, 0);
+
+ if (NULL == p)
+ return NULL;
+
+ size_t offset = ((uintptr_t) p) & (alignment - 1); // p % alignment
+ size_t pad = (0 == offset) ? 0 : alignment - offset; // p + pad achieves desired alignment
+
+ msize_t msize = TINY_MSIZE_FOR_BYTES(size + TINY_QUANTUM - 1);
+ msize_t mpad = TINY_MSIZE_FOR_BYTES(pad + TINY_QUANTUM - 1);
+ msize_t mwaste = mspan - msize - mpad; // excess blocks
+
+ if (mpad > 0) {
+ void *q = (void *)(((uintptr_t) p) + pad);
+
+ // Mark q as a block header and in-use, thus creating two blocks.
+ magazine_t *tiny_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->tiny_magazines,
+ REGION_TRAILER_FOR_TINY_REGION(TINY_REGION_FOR_PTR(p)),
+ MAGAZINE_INDEX_FOR_TINY_REGION(TINY_REGION_FOR_PTR(p)));
+ set_tiny_meta_header_in_use(q, msize);
+
+ // set_tiny_meta_header_in_use() "reaffirms" the block_header on the *following* block, so
+ // now set its in_use bit as well. But only if its within the original allocation made above.
+ if (mwaste > 0)
+ BITARRAY_SET(TINY_INUSE_FOR_HEADER(TINY_BLOCK_HEADER_FOR_PTR(q)), TINY_INDEX_FOR_PTR(q) + msize);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+
+ // Give up mpad blocks beginning at p to the tiny free list
+ // region_t r = TINY_REGION_FOR_PTR(p);
+ szone_free(szone, p); // avoids inlining free_tiny(szone, p, &r);
+
+ p = q; // advance p to the desired alignment
+ }
+
+ if (mwaste > 0) {
+ void *q = (void *)(((uintptr_t) p) + TINY_BYTES_FOR_MSIZE(msize));
+ // Mark q as block header and in-use, thus creating two blocks.
+ magazine_t *tiny_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->tiny_magazines,
+ REGION_TRAILER_FOR_TINY_REGION(TINY_REGION_FOR_PTR(p)),
+ MAGAZINE_INDEX_FOR_TINY_REGION(TINY_REGION_FOR_PTR(p)));
+ set_tiny_meta_header_in_use(q, mwaste);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+
+ // Give up mwaste blocks beginning at q to the tiny free list
+ // region_t r = TINY_REGION_FOR_PTR(q);
+ szone_free(szone, q); // avoids inlining free_tiny(szone, q, &r);
+ }
+
+ return p; // p has the desired size and alignment, and can later be free()'d
+
+ } else if ((NUM_TINY_SLOTS - 1)*TINY_QUANTUM < size && alignment <= SMALL_QUANTUM) {
+ return szone_malloc(szone, size); // Trivially satisfied by small or large
+
+ } else if (!((szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL) && (span <= szone->large_threshold)) {
+
+ if (size <= (NUM_TINY_SLOTS - 1)*TINY_QUANTUM) {
+ size = (NUM_TINY_SLOTS - 1)*TINY_QUANTUM + TINY_QUANTUM; // ensure block allocated by small does not have a tiny-possible size
+ span = size + alignment - 1;
+ }
+
+ msize_t mspan = SMALL_MSIZE_FOR_BYTES(span + SMALL_QUANTUM - 1);
+ void *p = szone_malloc(szone, span); // avoid inlining small_malloc_should_clear(szone, mspan, 0);
+
+ if (NULL == p)
+ return NULL;
+
+ size_t offset = ((uintptr_t) p) & (alignment - 1); // p % alignment
+ size_t pad = (0 == offset) ? 0 : alignment - offset; // p + pad achieves desired alignment
+
+ msize_t msize = SMALL_MSIZE_FOR_BYTES(size + SMALL_QUANTUM - 1);
+ msize_t mpad = SMALL_MSIZE_FOR_BYTES(pad + SMALL_QUANTUM - 1);
+ msize_t mwaste = mspan - msize - mpad; // excess blocks
+
+ if (mpad > 0) {
+ void *q = (void *)(((uintptr_t) p) + pad);
+
+ // Mark q as block header and in-use, thus creating two blocks.
+ magazine_t *small_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->small_magazines,
+ REGION_TRAILER_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(p)),
+ MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(p)));
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(p), SMALL_META_INDEX_FOR_PTR(p), mpad);
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(q), SMALL_META_INDEX_FOR_PTR(q), msize + mwaste);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+
+ // Give up mpad blocks beginning at p to the small free list
+ // region_t r = SMALL_REGION_FOR_PTR(p);
+ szone_free(szone, p); // avoid inlining free_small(szone, p, &r);
+
+ p = q; // advance p to the desired alignment
+ }
+ if (mwaste > 0) {
+ void *q = (void *)(((uintptr_t) p) + SMALL_BYTES_FOR_MSIZE(msize));
+ // Mark q as block header and in-use, thus creating two blocks.
+ magazine_t *small_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->small_magazines,
+ REGION_TRAILER_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(p)),
+ MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(p)));
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(p), SMALL_META_INDEX_FOR_PTR(p), msize);
+ small_meta_header_set_in_use(SMALL_META_HEADER_FOR_PTR(q), SMALL_META_INDEX_FOR_PTR(q), mwaste);
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+
+ // Give up mwaste blocks beginning at q to the small free list
+ // region_t r = SMALL_REGION_FOR_PTR(q);
+ szone_free(szone, q); // avoid inlining free_small(szone, q, &r);
+ }
+
+ return p; // p has the desired size and alignment, and can later be free()'d
+
+ } else if (szone->large_threshold < size && alignment <= vm_page_size) {
+ return szone_malloc(szone, size); // Trivially satisfied by large
+
+ } else {
+ // ensure block allocated by large does not have a small-possible size
+ size_t num_pages = round_page(MAX(szone->large_threshold + 1, size)) >> vm_page_shift;
+ void *p;
+
+ if (num_pages == 0) /* Overflowed */
+ p = NULL;
+ else
+ p = large_malloc(szone, num_pages, MAX(vm_page_shift, __builtin_ctz(alignment)), 0);
+
+ return p;
+ }
+ /* NOTREACHED */
+}
+
+// given a size, returns the number of pointers allocated capable of holding
+// that size, up to the limit specified by the 'count' argument. These pointers
+// are stored in the 'results' array, which must be allocated by the caller.
+// may return zero, since this function is only a best attempt at allocating
+// the pointers. clients should be prepared to call malloc for any additional
+// blocks they need.
+static NOINLINE unsigned
+szone_batch_malloc(szone_t *szone, size_t size, void **results, unsigned count)
+{
+ msize_t msize = TINY_MSIZE_FOR_BYTES(size + TINY_QUANTUM - 1);
+ unsigned found = 0;
+ mag_index_t mag_index = mag_get_thread_index(szone);
+ magazine_t *tiny_mag_ptr = &(szone->tiny_magazines[mag_index]);
+
+ // only bother implementing this for tiny
+ if (size > (NUM_TINY_SLOTS - 1)*TINY_QUANTUM)
+ return 0;
+ // make sure to return objects at least one quantum in size
+ if (!msize)
+ msize = 1;
+
+ CHECK(szone, __PRETTY_FUNCTION__);
+
+ // We must lock the zone now, since tiny_malloc_from_free_list assumes that
+ // the caller has done so.
+ SZONE_MAGAZINE_PTR_LOCK(szone, tiny_mag_ptr);
+
+ // with the zone locked, allocate objects from the free list until all
+ // sufficiently large objects have been exhausted, or we have met our quota
+ // of objects to allocate.
+ while (found < count) {
+ void *ptr = tiny_malloc_from_free_list(szone, tiny_mag_ptr, mag_index, msize);
+ if (!ptr)
+ break;
+
+ *results++ = ptr;
+ found++;
+ }
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ return found;
+}
+
+/* Try caching the tiny_region and checking if the next ptr hits there. */
+static NOINLINE void
+szone_batch_free(szone_t *szone, void **to_be_freed, unsigned count)
+{
+ unsigned cc = 0;
+ void *ptr;
+ region_t tiny_region = NULL;
+ boolean_t is_free;
+ msize_t msize;
+ magazine_t *tiny_mag_ptr = NULL;
+ mag_index_t mag_index = -1;
+
+ // frees all the pointers in to_be_freed
+ // note that to_be_freed may be overwritten during the process
+ if (!count)
+ return;
+
+ CHECK(szone, __PRETTY_FUNCTION__);
+ while (cc < count) {
+ ptr = to_be_freed[cc];
+ if (ptr) {
+ if (NULL == tiny_region || tiny_region != TINY_REGION_FOR_PTR(ptr)) { // region same as last iteration?
+ if (tiny_mag_ptr) { // non-NULL iff magazine lock taken
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ tiny_mag_ptr = NULL;
+ }
+
+ tiny_region = tiny_region_for_ptr_no_lock(szone, ptr);
+
+ if (tiny_region) {
+ tiny_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->tiny_magazines,
+ REGION_TRAILER_FOR_TINY_REGION(tiny_region),
+ MAGAZINE_INDEX_FOR_TINY_REGION(tiny_region));
+ mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(tiny_region);
+ }
+ }
+ if (tiny_region) {
+ // this is a tiny pointer
+ if (TINY_INDEX_FOR_PTR(ptr) >= NUM_TINY_BLOCKS)
+ break; // pointer to metadata; let the standard free deal with it
+ msize = get_tiny_meta_header(ptr, &is_free);
+ if (is_free)
+ break; // a double free; let the standard free deal with it
+
+ tiny_free_no_lock(szone, tiny_mag_ptr, mag_index, tiny_region, ptr, msize);
+ to_be_freed[cc] = NULL;
+ } else {
+ // No region in this zone claims ptr; let the standard free deal with it
+ break;
+ }
+ }
+ cc++;
+ }
+
+ if (tiny_mag_ptr) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ tiny_mag_ptr = NULL;
+ }
+
+ CHECK(szone, __PRETTY_FUNCTION__);
+ while (count--) {
+ ptr = to_be_freed[count];
+ if (ptr)
+ szone_free(szone, ptr);
+ }
+}
+
+// FIXME: Suppose one of the locks is held?
+static void
+szone_destroy(szone_t *szone)
+{
+ size_t index;
+ large_entry_t *large;
+ vm_range_t range_to_deallocate;
+
+ /* destroy large entries */
+ index = szone->num_large_entries;
+ while (index--) {
+ large = szone->large_entries + index;
+ if (large->address) {
+ // we deallocate_pages, including guard pages
+ deallocate_pages(szone, (void *)(large->address), large->size, szone->debug_flags);
+ }
+ }
+ large_entries_free_no_lock(szone, szone->large_entries, szone->num_large_entries, &range_to_deallocate);
+ if (range_to_deallocate.size)
+ deallocate_pages(szone, (void *)range_to_deallocate.address, (size_t)range_to_deallocate.size, 0);
+
+ /* destroy tiny regions */
+ for (index = 0; index < szone->tiny_region_generation->num_regions_allocated; ++index)
+ if ((HASHRING_OPEN_ENTRY != szone->tiny_region_generation->hashed_regions[index]) &&
+ (HASHRING_REGION_DEALLOCATED != szone->tiny_region_generation->hashed_regions[index]))
+ deallocate_pages(szone, szone->tiny_region_generation->hashed_regions[index], TINY_REGION_SIZE, 0);
+
+ /* destroy small regions */
+ for (index = 0; index < szone->small_region_generation->num_regions_allocated; ++index)
+ if ((HASHRING_OPEN_ENTRY != szone->small_region_generation->hashed_regions[index]) &&
+ (HASHRING_REGION_DEALLOCATED != szone->small_region_generation->hashed_regions[index]))
+ deallocate_pages(szone, szone->small_region_generation->hashed_regions[index], SMALL_REGION_SIZE, 0);
+
+ /* destroy region hash rings, if any */
+ if (szone->tiny_region_generation->hashed_regions != szone->initial_tiny_regions) {
+ size_t size = round_page(szone->tiny_region_generation->num_regions_allocated * sizeof(region_t));
+ deallocate_pages(szone, szone->tiny_region_generation->hashed_regions, size, 0);
+ }
+ if (szone->small_region_generation->hashed_regions != szone->initial_small_regions) {
+ size_t size = round_page(szone->small_region_generation->num_regions_allocated * sizeof(region_t));
+ deallocate_pages(szone, szone->small_region_generation->hashed_regions, size, 0);
+ }
+
+ /* Now destroy the separate szone region */
+ if (szone->cpu_id_key != (pthread_key_t) -1)
+ (void)pthread_key_delete(szone->cpu_id_key);
+ deallocate_pages(szone, (void *)&(szone->tiny_magazines[-1]), TINY_MAGAZINE_PAGED_SIZE, SCALABLE_MALLOC_ADD_GUARD_PAGES);
+ deallocate_pages(szone, (void *)&(szone->small_magazines[-1]), SMALL_MAGAZINE_PAGED_SIZE, SCALABLE_MALLOC_ADD_GUARD_PAGES);
+ deallocate_pages(szone, (void *)szone, SZONE_PAGED_SIZE, SCALABLE_MALLOC_ADD_GUARD_PAGES);
+}
+
+static NOINLINE size_t
+szone_good_size(szone_t *szone, size_t size)
+{
+ msize_t msize;
+ int guard_small = (szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) && PROTECT_SMALL;
+
+ // Find a good size for this tiny allocation.
+ if (size <= (NUM_TINY_SLOTS - 1) * TINY_QUANTUM) {
+ msize = TINY_MSIZE_FOR_BYTES(size + TINY_QUANTUM - 1);
+ if (!msize)
+ msize = 1;
+ return TINY_BYTES_FOR_MSIZE(msize);
+ }
+
+ // Find a good size for this small allocation.
+ if (!guard_small && (size <= szone->large_threshold)) {
+ msize = SMALL_MSIZE_FOR_BYTES(size + SMALL_QUANTUM - 1);
+ if (!msize)
+ msize = 1;
+ return SMALL_BYTES_FOR_MSIZE(msize);
+ }
+
+ // Check for integer overflow on the size, since unlike the two cases above,
+ // there is no upper bound on allocation size at this point.
+ if (size > round_page(size))
+ return (size_t)(-1LL);
+
+#if DEBUG_MALLOC
+ // It is not acceptable to see a size of zero here, since that means we
+ // failed to catch a request for zero bytes in the tiny check, or the size
+ // overflowed to zero during some arithmetic.
+ if (size == 0)
+ malloc_printf("szone_good_size() invariant broken %y\n", size);
+#endif
+ return round_page(size);
+}
+
+unsigned szone_check_counter = 0;
+unsigned szone_check_start = 0;
+unsigned szone_check_modulo = 1;
+
+static NOINLINE boolean_t
+szone_check_all(szone_t *szone, const char *function)
+{
+ size_t index;
+
+ /* check tiny regions - chould check region count */
+ for (index = 0; index < szone->tiny_region_generation->num_regions_allocated; ++index) {
+ region_t tiny = szone->tiny_region_generation->hashed_regions[index];
+
+ if (HASHRING_REGION_DEALLOCATED == tiny)
+ continue;
+
+ if (tiny) {
+ magazine_t *tiny_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->tiny_magazines,
+ REGION_TRAILER_FOR_TINY_REGION(tiny), MAGAZINE_INDEX_FOR_TINY_REGION(tiny));
+
+ if (!tiny_check_region(szone, tiny)) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ szone->debug_flags &= ~ CHECK_REGIONS;
+ szone_error(szone, 1, "check: tiny region incorrect", NULL,
+ "*** tiny region %ld incorrect szone_check_all(%s) counter=%d\n",
+ index, function, szone_check_counter);
+ return 0;
+ }
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, tiny_mag_ptr);
+ }
+ }
+ /* check tiny free lists */
+ for (index = 0; index < NUM_TINY_SLOTS; ++index) {
+ if (!tiny_free_list_check(szone, index)) {
+ szone->debug_flags &= ~ CHECK_REGIONS;
+ szone_error(szone, 1, "check: tiny free list incorrect", NULL,
+ "*** tiny free list incorrect (slot=%ld) szone_check_all(%s) counter=%d\n",
+ index, function, szone_check_counter);
+ return 0;
+ }
+ }
+
+ /* check small regions - could check region count */
+ for (index = 0; index < szone->small_region_generation->num_regions_allocated; ++index) {
+ region_t small = szone->small_region_generation->hashed_regions[index];
+
+ if (HASHRING_REGION_DEALLOCATED == small)
+ continue;
+
+ if (small) {
+ magazine_t *small_mag_ptr = mag_lock_zine_for_region_trailer(szone, szone->small_magazines,
+ REGION_TRAILER_FOR_SMALL_REGION(small), MAGAZINE_INDEX_FOR_SMALL_REGION(small));
+
+ if (!small_check_region(szone, small)) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ szone->debug_flags &= ~ CHECK_REGIONS;
+ szone_error(szone, 1, "check: small region incorrect", NULL,
+ "*** small region %ld incorrect szone_check_all(%s) counter=%d\n",
+ index, function, szone_check_counter);
+ return 0;
+ }
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, small_mag_ptr);
+ }
+ }
+ /* check small free lists */
+ for (index = 0; index < szone->num_small_slots; ++index) {
+ if (!small_free_list_check(szone, index)) {
+ szone->debug_flags &= ~ CHECK_REGIONS;
+ szone_error(szone, 1, "check: small free list incorrect", NULL,
+ "*** small free list incorrect (slot=%ld) szone_check_all(%s) counter=%d\n",
+ index, function, szone_check_counter);
+ return 0;
+ }
+ }
+
+ return 1;
+}
+
+static boolean_t
+szone_check(szone_t *szone)
+{
+ if ((++szone_check_counter % 10000) == 0)
+ _malloc_printf(ASL_LEVEL_NOTICE, "at szone_check counter=%d\n", szone_check_counter);
+
+ if (szone_check_counter < szone_check_start)
+ return 1;
+
+ if (szone_check_counter % szone_check_modulo)
+ return 1;
+
+ return szone_check_all(szone, "");
+}
+
+static kern_return_t
+szone_ptr_in_use_enumerator(task_t task, void *context, unsigned type_mask, vm_address_t zone_address,
+ memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ szone_t *szone;
+ kern_return_t err;
+
+ if (!reader) reader = _szone_default_reader;
+
+ err = reader(task, zone_address, sizeof(szone_t), (void **)&szone);
+ if (err) return err;
+
+ err = tiny_in_use_enumerator(task, context, type_mask, szone, reader, recorder);
+ if (err) return err;
+
+ err = small_in_use_enumerator(task, context, type_mask, szone, reader, recorder);
+ if (err) return err;
+
+ err = large_in_use_enumerator(task, context, type_mask,
+ (vm_address_t)szone->large_entries, szone->num_large_entries, reader, recorder);
+ return err;
+}
+
+// Following method is deprecated: use scalable_zone_statistics instead
+void
+scalable_zone_info(malloc_zone_t *zone, unsigned *info_to_fill, unsigned count)
+{
+ szone_t *szone = (void *)zone;
+ unsigned info[13];
+
+ // We do not lock to facilitate debug
+
+ size_t s = 0;
+ unsigned t = 0;
+ size_t u = 0;
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_tiny_magazines; mag_index++) {
+ s += szone->tiny_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->tiny_magazines[mag_index].mag_num_objects;
+ u += szone->tiny_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ info[4] = t;
+ info[5] = u;
+
+ for (t = 0, u = 0, mag_index = -1; mag_index < szone->num_small_magazines; mag_index++) {
+ s += szone->small_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->small_magazines[mag_index].mag_num_objects;
+ u += szone->small_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ info[6] = t;
+ info[7] = u;
+
+ info[8] = szone->num_large_objects_in_use;
+ info[9] = szone->num_bytes_in_large_objects;
+
+ info[10] = 0; // DEPRECATED szone->num_huge_entries;
+ info[11] = 0; // DEPRECATED szone->num_bytes_in_huge_objects;
+
+ info[12] = szone->debug_flags;
+
+ info[0] = info[4] + info[6] + info[8] + info[10];
+ info[1] = info[5] + info[7] + info[9] + info[11];
+
+ info[3] = (szone->num_tiny_regions - szone->num_tiny_regions_dealloc) * TINY_REGION_SIZE +
+ (szone->num_small_regions - szone->num_small_regions_dealloc) * SMALL_REGION_SIZE + info[9] + info[11];
+
+ info[2] = info[3] - s;
+ memcpy(info_to_fill, info, sizeof(unsigned)*count);
+}
+
+// FIXME: consistent picture requires locking!
+static NOINLINE void
+szone_print(szone_t *szone, boolean_t verbose)
+{
+ unsigned info[13];
+ size_t index;
+ region_t region;
+
+ scalable_zone_info((void *)szone, info, 13);
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "Scalable zone %p: inUse=%d(%y) touched=%y allocated=%y flags=%d\n",
+ szone, info[0], info[1], info[2], info[3], info[12]);
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "\ttiny=%d(%y) small=%d(%y) large=%d(%y) huge=%d(%y)\n",
+ info[4], info[5], info[6], info[7], info[8], info[9], info[10], info[11]);
+ // tiny
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "%d tiny regions:\n", szone->num_tiny_regions);
+ if (szone->num_tiny_regions_dealloc)
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "[%d tiny regions have been vm_deallocate'd]\n", szone->num_tiny_regions_dealloc);
+ for (index = 0; index < szone->tiny_region_generation->num_regions_allocated; ++index) {
+ region = szone->tiny_region_generation->hashed_regions[index];
+ if (HASHRING_OPEN_ENTRY != region && HASHRING_REGION_DEALLOCATED != region) {
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(region);
+ print_tiny_region(verbose, region, (region == szone->tiny_magazines[mag_index].mag_last_region) ?
+ szone->tiny_magazines[mag_index].mag_bytes_free_at_end : 0);
+ }
+ }
+ if (verbose)
+ print_tiny_free_list(szone);
+ // small
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "%d small regions:\n", szone->num_small_regions);
+ if (szone->num_small_regions_dealloc)
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "[%d small regions have been vm_deallocate'd]\n", szone->num_small_regions_dealloc);
+ for (index = 0; index < szone->small_region_generation->num_regions_allocated; ++index) {
+ region = szone->small_region_generation->hashed_regions[index];
+ if (HASHRING_OPEN_ENTRY != region && HASHRING_REGION_DEALLOCATED != region) {
+ mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(region);
+ print_small_region(szone, verbose, region,
+ (region == szone->small_magazines[mag_index].mag_last_region) ?
+ szone->small_magazines[mag_index].mag_bytes_free_at_end : 0);
+ }
+ }
+ if (verbose)
+ print_small_free_list(szone);
+}
+
+static void
+szone_log(malloc_zone_t *zone, void *log_address)
+{
+ szone_t *szone = (szone_t *)zone;
+
+ szone->log_address = log_address;
+}
+
+static void
+szone_force_lock(szone_t *szone)
+{
+ mag_index_t i;
+
+ for (i = 0; i < szone->num_tiny_magazines; ++i) {
+ SZONE_MAGAZINE_PTR_LOCK(szone, (&(szone->tiny_magazines[i])));
+ }
+ SZONE_MAGAZINE_PTR_LOCK(szone, (&(szone->tiny_magazines[DEPOT_MAGAZINE_INDEX])));
+
+ for (i = 0; i < szone->num_small_magazines; ++i) {
+ SZONE_MAGAZINE_PTR_LOCK(szone, (&(szone->small_magazines[i])));
+ }
+ SZONE_MAGAZINE_PTR_LOCK(szone, (&(szone->small_magazines[DEPOT_MAGAZINE_INDEX])));
+
+ SZONE_LOCK(szone);
+}
+
+static void
+szone_force_unlock(szone_t *szone)
+{
+ mag_index_t i;
+
+ SZONE_UNLOCK(szone);
+
+ for (i = -1; i < szone->num_small_magazines; ++i) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, (&(szone->small_magazines[i])));
+ }
+
+ for (i = -1; i < szone->num_tiny_magazines; ++i) {
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, (&(szone->tiny_magazines[i])));
+ }
+}
+
+static boolean_t
+szone_locked(szone_t *szone)
+{
+ mag_index_t i;
+ int tookLock;
+
+ tookLock = SZONE_TRY_LOCK(szone);
+ if (tookLock == 0)
+ return 1;
+ SZONE_UNLOCK(szone);
+
+ for (i = -1; i < szone->num_small_magazines; ++i) {
+ tookLock = SZONE_MAGAZINE_PTR_TRY_LOCK(szone, (&(szone->small_magazines[i])));
+ if (tookLock == 0)
+ return 1;
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, (&(szone->small_magazines[i])));
+ }
+
+ for (i = -1; i < szone->num_tiny_magazines; ++i) {
+ tookLock = SZONE_MAGAZINE_PTR_TRY_LOCK(szone, (&(szone->tiny_magazines[i])));
+ if (tookLock == 0)
+ return 1;
+ SZONE_MAGAZINE_PTR_UNLOCK(szone, (&(szone->tiny_magazines[i])));
+ }
+ return 0;
+}
+
+boolean_t
+scalable_zone_statistics(malloc_zone_t *zone, malloc_statistics_t *stats, unsigned subzone)
+{
+ szone_t *szone = (szone_t *)zone;
+
+ switch (subzone) {
+ case 0:
+ {
+ size_t s = 0;
+ unsigned t = 0;
+ size_t u = 0;
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_tiny_magazines; mag_index++) {
+ s += szone->tiny_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->tiny_magazines[mag_index].mag_num_objects;
+ u += szone->tiny_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ stats->blocks_in_use = t;
+ stats->size_in_use = u;
+ stats->size_allocated = (szone->num_tiny_regions - szone->num_tiny_regions_dealloc) * TINY_REGION_SIZE;
+ stats->max_size_in_use = stats->size_allocated - s;
+ return 1;
+ }
+ case 1:
+ {
+ size_t s = 0;
+ unsigned t = 0;
+ size_t u = 0;
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_small_magazines; mag_index++) {
+ s += szone->small_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->small_magazines[mag_index].mag_num_objects;
+ u += szone->small_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ stats->blocks_in_use = t;
+ stats->size_in_use = u;
+ stats->size_allocated = (szone->num_small_regions - szone->num_small_regions_dealloc) * SMALL_REGION_SIZE;
+ stats->max_size_in_use = stats->size_allocated - s;
+ return 1;
+ }
+ case 2:
+ stats->blocks_in_use = szone->num_large_objects_in_use;
+ stats->size_in_use = szone->num_bytes_in_large_objects;
+ stats->max_size_in_use = stats->size_allocated = stats->size_in_use;
+ return 1;
+ case 3:
+ stats->blocks_in_use = 0; // DEPRECATED szone->num_huge_entries;
+ stats->size_in_use = 0; // DEPRECATED szone->num_bytes_in_huge_objects;
+ stats->max_size_in_use = stats->size_allocated = 0;
+ return 1;
+ }
+ return 0;
+}
+
+static void
+szone_statistics(szone_t *szone, malloc_statistics_t *stats)
+{
+ size_t large;
+
+ size_t s = 0;
+ unsigned t = 0;
+ size_t u = 0;
+ mag_index_t mag_index;
+
+ for (mag_index = -1; mag_index < szone->num_tiny_magazines; mag_index++) {
+ s += szone->tiny_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->tiny_magazines[mag_index].mag_num_objects;
+ u += szone->tiny_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ for (mag_index = -1; mag_index < szone->num_small_magazines; mag_index++) {
+ s += szone->small_magazines[mag_index].mag_bytes_free_at_end;
+ t += szone->small_magazines[mag_index].mag_num_objects;
+ u += szone->small_magazines[mag_index].mag_num_bytes_in_objects;
+ }
+
+ large = szone->num_bytes_in_large_objects + 0; // DEPRECATED szone->num_bytes_in_huge_objects;
+
+ stats->blocks_in_use = t + szone->num_large_objects_in_use + 0; // DEPRECATED szone->num_huge_entries;
+ stats->size_in_use = u + large;
+ stats->max_size_in_use = stats->size_allocated =
+ (szone->num_tiny_regions - szone->num_tiny_regions_dealloc) * TINY_REGION_SIZE +
+ (szone->num_small_regions - szone->num_small_regions_dealloc) * SMALL_REGION_SIZE + large;
+ // Now we account for the untouched areas
+ stats->max_size_in_use -= s;
+}
+
+static void *
+legacy_zeroing_large_malloc(szone_t *szone, size_t size) {
+ if (size > LARGE_THRESHOLD) // Leopard and earlier returned a ZFOD range, so ...
+ return szone_calloc(szone, 1, size); // Clear to zero always, ham-handedly touching in each page
+ else
+ return szone_malloc(szone, size);
+}
+
+static void *
+legacy_zeroing_large_valloc(szone_t *szone, size_t size) {
+ void *p = szone_valloc(szone, size);
+
+ // Leopard and earlier returned a ZFOD range, so ...
+ memset(p, 0, size); // Clear to zero always, ham-handedly touching in each page
+ return p;
+}
+
+void zeroify_scalable_zone(malloc_zone_t *zone)
+{
+ szone_t *szone = (szone_t *)zone;
+
+ if (szone) {
+ szone->basic_zone.malloc = (void *)legacy_zeroing_large_malloc;
+ szone->basic_zone.valloc = (void *)legacy_zeroing_large_valloc;
+ }
+}
+
+static const struct malloc_introspection_t szone_introspect = {
+ (void *)szone_ptr_in_use_enumerator,
+ (void *)szone_good_size,
+ (void *)szone_check,
+ (void *)szone_print,
+ szone_log,
+ (void *)szone_force_lock,
+ (void *)szone_force_unlock,
+ (void *)szone_statistics,
+ (void *)szone_locked,
+}; // marked as const to spare the DATA section
+
+malloc_zone_t *
+create_scalable_zone(size_t initial_size, unsigned debug_flags)
+{
+ szone_t *szone;
+ uint64_t hw_memsize = 0;
+ size_t uint64_t_size = sizeof(hw_memsize);
+ int err;
+
+ /*
+ * Sanity-check our build-time assumptions about the size of a page.
+ * Since we have sized various things assuming the default page size,
+ * attempting to determine it dynamically is not useful.
+ */
+ if ((vm_page_size != _vm_page_size) || (vm_page_shift != _vm_page_shift)) {
+ malloc_printf("*** FATAL ERROR - machine page size does not match our assumptions.\n");
+ exit(-1);
+ }
+
+#if defined(__i386__) || defined(__x86_64__)
+ if (_COMM_PAGE_VERSION_REQD > (*((short *) _COMM_PAGE_VERSION))) { // _COMM_PAGE_CPU_NUMBER must be present at runtime
+ malloc_printf("*** ERROR - comm page version mismatch.\n");
+ exit(-1);
+ }
+#endif
+
+ /* get memory for the zone, which is now separate from any region.
+ add guard pages to prevent walking from any other vm allocations
+ to here and overwriting the function pointers in basic_zone. */
+ szone = allocate_pages(NULL, SZONE_PAGED_SIZE, 0, SCALABLE_MALLOC_ADD_GUARD_PAGES, VM_MEMORY_MALLOC);
+ if (!szone)
+ return NULL;
+
+ /* set up the szone structure */
+#if 0
+#warning CHECK_REGIONS enabled
+ debug_flags |= CHECK_REGIONS;
+#endif
+#if 0
+#warning LOG enabled
+ szone->log_address = ~0;
+#endif
+ szone->trg[0].nextgen = &(szone->trg[1]);
+ szone->trg[1].nextgen = &(szone->trg[0]);
+ szone->tiny_region_generation = &(szone->trg[0]);
+
+ szone->tiny_region_generation->hashed_regions = szone->initial_tiny_regions;
+ szone->tiny_region_generation->num_regions_allocated = INITIAL_NUM_REGIONS;
+ szone->tiny_region_generation->num_regions_allocated_shift = INITIAL_NUM_REGIONS_SHIFT;
+
+ szone->srg[0].nextgen = &(szone->srg[1]);
+ szone->srg[1].nextgen = &(szone->srg[0]);
+ szone->small_region_generation = &(szone->srg[0]);
+
+ szone->small_region_generation->hashed_regions = szone->initial_small_regions;
+ szone->small_region_generation->num_regions_allocated = INITIAL_NUM_REGIONS;
+ szone->small_region_generation->num_regions_allocated_shift = INITIAL_NUM_REGIONS_SHIFT;
+
+
+ /*
+ * Initialize variables that size the free list for SMALL allocations based
+ * upon the amount of memory in the system. Switch to a larger number of
+ * free list entries at 1GB.
+ */
+ if (0 == sysctlbyname("hw.memsize", &hw_memsize, &uint64_t_size, 0, 0) &&
+ hw_memsize >= (1ULL << 30)) {
+ szone->is_largemem = 1;
+ szone->num_small_slots = NUM_SMALL_SLOTS_LARGEMEM;
+ szone->large_threshold = LARGE_THRESHOLD_LARGEMEM;
+ szone->vm_copy_threshold = VM_COPY_THRESHOLD_LARGEMEM;
+ } else {
+ szone->is_largemem = 0;
+ szone->num_small_slots = NUM_SMALL_SLOTS;
+ szone->large_threshold = LARGE_THRESHOLD;
+ szone->vm_copy_threshold = VM_COPY_THRESHOLD;
+ }
+#if LARGE_CACHE
+ szone->large_entry_cache_hoard_lmit = hw_memsize >> 10; // madvise(..., MADV_REUSABLE) death-row arrivals above this threshold [~0.1%]
+
+ /* <rdar://problem/6610904> Reset protection when returning a previous large allocation? */
+ int32_t libSystemVersion = NSVersionOfLinkTimeLibrary("System");
+ if ((-1 != libSystemVersion) && ((libSystemVersion >> 16) < 112) /* CFSystemVersionSnowLeopard */)
+ szone->large_legacy_reset_mprotect = TRUE;
+ else
+ szone->large_legacy_reset_mprotect = FALSE;
+#endif
+
+ // Initialize the security token.
+#if __LP64__
+ szone->cookie = ((uintptr_t)arc4random() << 32) | (uintptr_t)arc4random();
+#else
+ szone->cookie = arc4random();
+#endif
+
+ szone->basic_zone.version = 6;
+ szone->basic_zone.size = (void *)szone_size;
+ szone->basic_zone.malloc = (void *)szone_malloc;
+ szone->basic_zone.calloc = (void *)szone_calloc;
+ szone->basic_zone.valloc = (void *)szone_valloc;
+ szone->basic_zone.free = (void *)szone_free;
+ szone->basic_zone.realloc = (void *)szone_realloc;
+ szone->basic_zone.destroy = (void *)szone_destroy;
+ szone->basic_zone.batch_malloc = (void *)szone_batch_malloc;
+ szone->basic_zone.batch_free = (void *)szone_batch_free;
+ szone->basic_zone.introspect = (struct malloc_introspection_t *)&szone_introspect;
+ szone->basic_zone.memalign = (void *)szone_memalign;
+ szone->basic_zone.free_definite_size = (void *)szone_free_definite_size;
+ szone->debug_flags = debug_flags;
+ LOCK_INIT(szone->large_szone_lock);
+
+#if defined(__ppc__) || defined(__ppc64__)
+ /*
+ * In the interest of compatibility for PPC applications executing via Rosetta,
+ * arrange to zero-fill allocations as occurred by side effect in Leopard and earlier.
+ */
+ zeroify_scalable_zone((malloc_zone_t *)szone);
+#endif
+
+ if ((err = pthread_key_create(&(szone->cpu_id_key), NULL))) {
+ malloc_printf("*** ERROR -pthread_key_create failure err=%d.\n", err);
+ szone->cpu_id_key = (pthread_key_t) -1;
+ }
+
+ // Query the number of configured processors.
+ // Uniprocessor case gets just one tiny and one small magazine (whose index is zero). This gives
+ // the same behavior as the original scalable malloc. MP gets per-CPU magazines
+ // that scale (way) better.
+ int nproc = sysconf(_SC_NPROCESSORS_CONF);
+ szone->num_tiny_magazines = (nproc > 1) ? MIN(nproc, TINY_MAX_MAGAZINES) : 1;
+
+ // FIXME vm_allocate() based on number of configured CPUs
+ magazine_t *tiny_magazines = allocate_pages(NULL, TINY_MAGAZINE_PAGED_SIZE, 0,
+ SCALABLE_MALLOC_ADD_GUARD_PAGES, VM_MEMORY_MALLOC);
+ if (NULL == tiny_magazines)
+ return NULL;
+
+ szone->tiny_magazines = &(tiny_magazines[1]); // szone->tiny_magazines[-1] is the Depot
+
+ // The magazines are indexed in [0 .. (num_tiny_magazines - 1)]
+ // Find the smallest power of 2 that exceeds (num_tiny_magazines - 1)
+ szone->num_tiny_magazines_mask_shift = 0;
+ int i = 1;
+ while( i <= (szone->num_tiny_magazines - 1) ) {
+ szone->num_tiny_magazines_mask_shift++;
+ i <<= 1;
+ }
+
+ // Now if i <= TINY_MAX_MAGAZINES we'll never access tiny_magazines[] out of bounds.
+ if (i > TINY_MAX_MAGAZINES) {
+ malloc_printf("*** FATAL ERROR - magazine mask exceeds allocated magazines.\n");
+ exit(-1);
+ }
+
+ // Reduce i by 1 to obtain a mask covering [0 .. (num_tiny_magazines - 1)]
+ szone->num_tiny_magazines_mask = i - 1; // A mask used for hashing to a magazine index (and a safety aid)
+
+ // Init the tiny_magazine locks
+ LOCK_INIT(szone->tiny_regions_lock);
+ LOCK_INIT(szone->tiny_magazines[DEPOT_MAGAZINE_INDEX].magazine_lock);
+ for (i = 0; i < szone->num_tiny_magazines; ++i) {
+ LOCK_INIT(szone->tiny_magazines[i].magazine_lock);
+ }
+
+ szone->num_small_magazines = (nproc > 1) ? MIN(nproc, SMALL_MAX_MAGAZINES) : 1;
+
+ // FIXME vm_allocate() based on number of configured CPUs
+ magazine_t *small_magazines = allocate_pages(NULL, SMALL_MAGAZINE_PAGED_SIZE, 0,
+ SCALABLE_MALLOC_ADD_GUARD_PAGES, VM_MEMORY_MALLOC);
+ if (NULL == small_magazines)
+ return NULL;
+
+ szone->small_magazines = &(small_magazines[1]); // szone->small_magazines[-1] is the Depot
+
+ // The magazines are indexed in [0 .. (num_small_magazines - 1)]
+ // Find the smallest power of 2 that exceeds (num_small_magazines - 1)
+ szone->num_small_magazines_mask_shift = 0;
+ while( i <= (szone->num_small_magazines - 1) ) {
+ szone->num_small_magazines_mask_shift++;
+ i <<= 1;
+ }
+
+ // Now if i <= SMALL_MAX_MAGAZINES we'll never access small_magazines[] out of bounds.
+ if (i > SMALL_MAX_MAGAZINES) {
+ malloc_printf("*** FATAL ERROR - magazine mask exceeds allocated magazines.\n");
+ exit(-1);
+ }
+
+ // Reduce i by 1 to obtain a mask covering [0 .. (num_small_magazines - 1)]
+ szone->num_small_magazines_mask = i - 1; // A mask used for hashing to a magazine index (and a safety aid)
+
+ // Init the small_magazine locks
+ LOCK_INIT(szone->small_regions_lock);
+ LOCK_INIT(szone->small_magazines[DEPOT_MAGAZINE_INDEX].magazine_lock);
+ for (i = 0; i < szone->num_small_magazines; ++i) {
+ LOCK_INIT(szone->small_magazines[i].magazine_lock);
+ }
+
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return (malloc_zone_t *)szone;
+}
+
+//
+// purgeable zones have their own "large" allocation pool, but share "tiny" and "large"
+// heaps with a helper_zone identified in the call to create_purgeable_zone()
+//
+static size_t
+purgeable_size(szone_t *szone, const void *ptr)
+{
+ size_t t = szone_size_try_large(szone, ptr);
+
+ if (t)
+ return t;
+ else
+ return szone_size(szone->helper_zone, ptr);
+}
+
+static void *
+purgeable_malloc(szone_t *szone, size_t size) {
+ if (size <= szone->large_threshold)
+ return szone_malloc(szone->helper_zone, size);
+ else
+ return szone_malloc(szone, size);
+}
+
+static void *
+purgeable_calloc(szone_t *szone, size_t num_items, size_t size)
+{
+ size_t total_bytes = num_items * size;
+
+ // Check for overflow of integer multiplication
+ if (num_items > 1) {
+#if __LP64__ /* size_t is uint64_t */
+ if ((num_items | size) & 0xffffffff00000000ul) {
+ // num_items or size equals or exceeds sqrt(2^64) == 2^32, appeal to wider arithmetic
+ __uint128_t product = ((__uint128_t)num_items) * ((__uint128_t)size);
+ if ((uint64_t)(product >> 64)) // compiles to test on upper register of register pair
+ return NULL;
+ }
+#else /* size_t is uint32_t */
+ if ((num_items | size) & 0xffff0000ul) {
+ // num_items or size equals or exceeds sqrt(2^32) == 2^16, appeal to wider arithmetic
+ uint64_t product = ((uint64_t)num_items) * ((uint64_t)size);
+ if ((uint32_t)(product >> 32)) // compiles to test on upper register of register pair
+ return NULL;
+ }
+#endif
+ }
+
+ if (total_bytes <= szone->large_threshold)
+ return szone_calloc(szone->helper_zone, 1, total_bytes);
+ else
+ return szone_calloc(szone, 1, total_bytes);
+}
+
+static void *
+purgeable_valloc(szone_t *szone, size_t size)
+{
+ if (size <= szone->large_threshold)
+ return szone_valloc(szone->helper_zone, size);
+ else
+ return szone_valloc(szone, size);
+}
+
+static void
+purgeable_free(szone_t *szone, void *ptr)
+{
+ large_entry_t *entry;
+
+ SZONE_LOCK(szone);
+ entry = large_entry_for_pointer_no_lock(szone, ptr);
+ SZONE_UNLOCK(szone);
+ if (entry) {
+ return free_large(szone, ptr);
+ } else {
+ return szone_free(szone->helper_zone, ptr);
+ }
+}
+
+static void
+purgeable_free_definite_size(szone_t *szone, void *ptr, size_t size)
+{
+ if (size <= szone->large_threshold)
+ return szone_free_definite_size(szone->helper_zone, ptr, size);
+ else
+ return szone_free_definite_size(szone, ptr, size);
+}
+
+static void *
+purgeable_realloc(szone_t *szone, void *ptr, size_t new_size)
+{
+ if (new_size <= szone->large_threshold)
+ return szone_realloc(szone->helper_zone, ptr, new_size);
+ else
+ return szone_realloc(szone, ptr, new_size);
+}
+
+static void
+purgeable_destroy(szone_t *szone)
+{
+ /* destroy large entries */
+ size_t index = szone->num_large_entries;
+ large_entry_t *large;
+ vm_range_t range_to_deallocate;
+
+ while (index--) {
+ large = szone->large_entries + index;
+ if (large->address) {
+ // we deallocate_pages, including guard pages
+ deallocate_pages(szone, (void *)(large->address), large->size, szone->debug_flags);
+ }
+ }
+ large_entries_free_no_lock(szone, szone->large_entries, szone->num_large_entries, &range_to_deallocate);
+ if (range_to_deallocate.size)
+ deallocate_pages(szone, (void *)range_to_deallocate.address, (size_t)range_to_deallocate.size, 0);
+
+ /* Now destroy the separate szone region */
+ deallocate_pages(szone, (void *)szone, SZONE_PAGED_SIZE, SCALABLE_MALLOC_ADD_GUARD_PAGES);
+}
+
+static unsigned
+purgeable_batch_malloc(szone_t *szone, size_t size, void **results, unsigned count)
+{
+ return szone_batch_malloc(szone->helper_zone, size, results, count);
+}
+
+static void
+purgeable_batch_free(szone_t *szone, void **to_be_freed, unsigned count)
+{
+ return szone_batch_free(szone->helper_zone, to_be_freed, count);
+}
+
+static void *
+purgeable_memalign(szone_t *szone, size_t alignment, size_t size)
+{
+ if (size <= szone->large_threshold)
+ return szone_memalign(szone->helper_zone, alignment, size);
+ else
+ return szone_memalign(szone, alignment, size);
+}
+
+static kern_return_t
+purgeable_ptr_in_use_enumerator(task_t task, void *context, unsigned type_mask, vm_address_t zone_address,
+ memory_reader_t reader, vm_range_recorder_t recorder)
+{
+ szone_t *szone;
+ kern_return_t err;
+
+ if (!reader) reader = _szone_default_reader;
+
+ err = reader(task, zone_address, sizeof(szone_t), (void **)&szone);
+ if (err) return err;
+
+ err = large_in_use_enumerator(task, context, type_mask,
+ (vm_address_t)szone->large_entries, szone->num_large_entries, reader, recorder);
+ return err;
+}
+
+static size_t
+purgeable_good_size(szone_t *szone, size_t size)
+{
+ if (size <= szone->large_threshold)
+ return szone_good_size(szone->helper_zone, size);
+ else
+ return szone_good_size(szone, size);
+}
+
+static boolean_t
+purgeable_check(szone_t *szone)
+{
+ return 1;
+}
+
+static void
+purgeable_print(szone_t *szone, boolean_t verbose)
+{
+ _malloc_printf(MALLOC_PRINTF_NOLOG | MALLOC_PRINTF_NOPREFIX,
+ "Scalable zone %p: inUse=%d(%y) flags=%d\n",
+ szone, szone->num_large_objects_in_use, szone->num_bytes_in_large_objects, szone->debug_flags);
+}
+
+static void
+purgeable_log(malloc_zone_t *zone, void *log_address)
+{
+ szone_t *szone = (szone_t *)zone;
+
+ szone->log_address = log_address;
+}
+
+static void
+purgeable_force_lock(szone_t *szone)
+{
+ SZONE_LOCK(szone);
+}
+
+static void
+purgeable_force_unlock(szone_t *szone)
+{
+ SZONE_UNLOCK(szone);
+}
+
+static void
+purgeable_statistics(szone_t *szone, malloc_statistics_t *stats)
+{
+ stats->blocks_in_use = szone->num_large_objects_in_use;
+ stats->size_in_use = stats->max_size_in_use = stats->size_allocated = szone->num_bytes_in_large_objects;
+}
+
+static boolean_t
+purgeable_locked(szone_t *szone)
+{
+ int tookLock;
+
+ tookLock = SZONE_TRY_LOCK(szone);
+ if (tookLock == 0)
+ return 1;
+ SZONE_UNLOCK(szone);
+ return 0;
+}
+
+static const struct malloc_introspection_t purgeable_introspect = {
+ (void *)purgeable_ptr_in_use_enumerator,
+ (void *)purgeable_good_size,
+ (void *)purgeable_check,
+ (void *)purgeable_print,
+ purgeable_log,
+ (void *)purgeable_force_lock,
+ (void *)purgeable_force_unlock,
+ (void *)purgeable_statistics,
+ (void *)purgeable_locked,
+}; // marked as const to spare the DATA section
+
+malloc_zone_t *
+create_purgeable_zone(size_t initial_size, malloc_zone_t *malloc_default_zone, unsigned debug_flags)
+{
+ szone_t *szone;
+
+ /* get memory for the zone, which is now separate from any region.
+ add guard pages to prevent walking from any other vm allocations
+ to here and overwriting the function pointers in basic_zone. */
+ szone = allocate_pages(NULL, SZONE_PAGED_SIZE, 0, SCALABLE_MALLOC_ADD_GUARD_PAGES, VM_MEMORY_MALLOC);
+ if (!szone)
+ return NULL;
+
+ /* set up the szone structure */
+#if 0
+#warning LOG enabled
+ szone->log_address = ~0;
+#endif
+
+ /* Purgeable zone does not participate in the adaptive "largemem" sizing. */
+ szone->is_largemem = 0;
+ szone->large_threshold = LARGE_THRESHOLD;
+ szone->vm_copy_threshold = VM_COPY_THRESHOLD;
+
+#if LARGE_CACHE
+ /* <rdar://problem/6610904> Reset protection when returning a previous large allocation? */
+ int32_t libSystemVersion = NSVersionOfLinkTimeLibrary("System");
+ if ((-1 != libSystemVersion) && ((libSystemVersion >> 16) < 112) /* CFSystemVersionSnowLeopard */)
+ szone->large_legacy_reset_mprotect = TRUE;
+ else
+ szone->large_legacy_reset_mprotect = FALSE;
+#endif
+
+ szone->basic_zone.version = 6;
+ szone->basic_zone.size = (void *)purgeable_size;
+ szone->basic_zone.malloc = (void *)purgeable_malloc;
+ szone->basic_zone.calloc = (void *)purgeable_calloc;
+ szone->basic_zone.valloc = (void *)purgeable_valloc;
+ szone->basic_zone.free = (void *)purgeable_free;
+ szone->basic_zone.realloc = (void *)purgeable_realloc;
+ szone->basic_zone.destroy = (void *)purgeable_destroy;
+ szone->basic_zone.batch_malloc = (void *)purgeable_batch_malloc;
+ szone->basic_zone.batch_free = (void *)purgeable_batch_free;
+ szone->basic_zone.introspect = (struct malloc_introspection_t *)&purgeable_introspect;
+ szone->basic_zone.memalign = (void *)purgeable_memalign;
+ szone->basic_zone.free_definite_size = (void *)purgeable_free_definite_size;
+
+ szone->debug_flags = debug_flags | SCALABLE_MALLOC_PURGEABLE;
+
+ /* Purgeable zone does not support SCALABLE_MALLOC_ADD_GUARD_PAGES. */
+ if (szone->debug_flags & SCALABLE_MALLOC_ADD_GUARD_PAGES) {
+ _malloc_printf(ASL_LEVEL_INFO, "purgeable zone does not support guard pages\n");
+ szone->debug_flags &= ~SCALABLE_MALLOC_ADD_GUARD_PAGES;
+ }
+
+ LOCK_INIT(szone->large_szone_lock);
+
+ szone->helper_zone = (struct szone_s *)malloc_default_zone;
+
+ CHECK(szone, __PRETTY_FUNCTION__);
+ return (malloc_zone_t *)szone;
+}
+
+/*
+ * For use by CheckFix: create a new zone whose behavior is, apart from
+ * the use of death-row and per-CPU magazines, that of Leopard.
+ */
+static NOINLINE void *
+legacy_valloc(szone_t *szone, size_t size)
+{
+ void *ptr;
+ size_t num_pages;
+
+ num_pages = round_page(size) >> vm_page_shift;
+ ptr = large_malloc(szone, num_pages, 0, TRUE);
+#if DEBUG_MALLOC
+ if (LOG(szone, ptr))
+ malloc_printf("legacy_valloc returned %p\n", ptr);
+#endif
+ return ptr;
+}
+
+malloc_zone_t *
+create_legacy_scalable_zone(size_t initial_size, unsigned debug_flags)
+{
+ malloc_zone_t *mzone = create_scalable_zone(initial_size, debug_flags);
+ szone_t *szone = (szone_t *)mzone;
+
+ if (!szone)
+ return NULL;
+
+ szone->is_largemem = 0;
+ szone->num_small_slots = NUM_SMALL_SLOTS;
+ szone->large_threshold = LARGE_THRESHOLD;
+ szone->vm_copy_threshold = VM_COPY_THRESHOLD;
+
+ szone->basic_zone.valloc = (void *)legacy_valloc;
+ szone->basic_zone.free_definite_size = NULL;
+
+ return mzone;
+}
+
+/********* Support code for emacs unexec ************/
+
+/* History of freezedry version numbers:
+ *
+ * 1) Old malloc (before the scalable malloc implementation in this file
+ * existed).
+ * 2) Original freezedrying code for scalable malloc. This code was apparently
+ * based on the old freezedrying code and was fundamentally flawed in its
+ * assumption that tracking allocated memory regions was adequate to fake
+ * operations on freezedried memory. This doesn't work, since scalable
+ * malloc does not store flags in front of large page-aligned allocations.
+ * 3) Original szone-based freezedrying code.
+ * 4) Fresher malloc with tiny zone
+ * 5) 32/64bit compatible malloc
+ * 6) Metadata within 1MB and 8MB region for tiny and small
+ *
+ * No version backward compatibility is provided, but the version number does
+ * make it possible for malloc_jumpstart() to return an error if the application
+ * was freezedried with an older version of malloc.
+ */
+#define MALLOC_FREEZEDRY_VERSION 6
+
+typedef struct {
+ unsigned version;
+ unsigned nszones;
+ szone_t *szones;
+} malloc_frozen;
+
+static void *
+frozen_malloc(szone_t *zone, size_t new_size)
+{
+ return malloc(new_size);
+}
+
+static void *
+frozen_calloc(szone_t *zone, size_t num_items, size_t size)
+{
+ return calloc(num_items, size);
+}
+
+static void *
+frozen_valloc(szone_t *zone, size_t new_size)
+{
+ return valloc(new_size);
+}
+
+static void *
+frozen_realloc(szone_t *zone, void *ptr, size_t new_size)
+{
+ size_t old_size = szone_size(zone, ptr);
+ void *new_ptr;
+
+ if (new_size <= old_size) {
+ return ptr;
+ }
+ new_ptr = malloc(new_size);
+ if (old_size > 0) {
+ memcpy(new_ptr, ptr, old_size);
+ }
+ return new_ptr;
+}
+
+static void
+frozen_free(szone_t *zone, void *ptr)
+{
+}
+
+static void
+frozen_destroy(szone_t *zone)
+{
+}
+
+/********* Pseudo-private API for emacs unexec ************/
+
+/*
+ * malloc_freezedry() records all of the szones in use, so that they can be
+ * partially reconstituted by malloc_jumpstart(). Due to the differences
+ * between reconstituted memory regions and those created by the szone code,
+ * care is taken not to reallocate from the freezedried memory, except in the
+ * case of a non-growing realloc().
+ *
+ * Due to the flexibility provided by the zone registration mechanism, it is
+ * impossible to implement generic freezedrying for any zone type. This code
+ * only handles applications that use the szone allocator, so malloc_freezedry()
+ * returns 0 (error) if any non-szone zones are encountered.
+ */
+
+uintptr_t
+malloc_freezedry(void)
+{
+ extern unsigned malloc_num_zones;
+ extern malloc_zone_t **malloc_zones;
+ malloc_frozen *data;
+ unsigned i;
+
+ /* Allocate space in which to store the freezedry state. */
+ data = (malloc_frozen *) malloc(sizeof(malloc_frozen));
+
+ /* Set freezedry version number so that malloc_jumpstart() can check for compatibility. */
+ data->version = MALLOC_FREEZEDRY_VERSION;
+
+ /* Allocate the array of szone pointers. */
+ data->nszones = malloc_num_zones;
+ data->szones = (szone_t *) calloc(malloc_num_zones, sizeof(szone_t));
+
+ /*
+ * Fill in the array of szone structures. They are copied rather than
+ * referenced, since the originals are likely to be clobbered during malloc
+ * initialization.
+ */
+ for (i = 0; i < malloc_num_zones; i++) {
+ if (strcmp(malloc_zones[i]->zone_name, "DefaultMallocZone")) {
+ /* Unknown zone type. */
+ free(data->szones);
+ free(data);
+ return 0;
+ }
+ memcpy(&data->szones[i], malloc_zones[i], sizeof(szone_t));
+ }
+
+ return((uintptr_t)data);
+}
+
+int
+malloc_jumpstart(uintptr_t cookie)
+{
+ malloc_frozen *data = (malloc_frozen *)cookie;
+ unsigned i;
+
+ if (data->version != MALLOC_FREEZEDRY_VERSION) {
+ /* Unsupported freezedry version. */
+ return 1;
+ }
+
+ for (i = 0; i < data->nszones; i++) {
+ /* Set function pointers. Even the functions that stay the same must be
+ * set, since there are no guarantees that they will be mapped to the
+ * same addresses. */
+ data->szones[i].basic_zone.size = (void *) szone_size;
+ data->szones[i].basic_zone.malloc = (void *) frozen_malloc;
+ data->szones[i].basic_zone.calloc = (void *) frozen_calloc;
+ data->szones[i].basic_zone.valloc = (void *) frozen_valloc;
+ data->szones[i].basic_zone.free = (void *) frozen_free;
+ data->szones[i].basic_zone.realloc = (void *) frozen_realloc;
+ data->szones[i].basic_zone.destroy = (void *) frozen_destroy;
+ data->szones[i].basic_zone.introspect = (struct malloc_introspection_t *)&szone_introspect;
+
+ /* Register the freezedried zone. */
+ malloc_zone_register(&data->szones[i].basic_zone);
+ }
+
+ return 0;
+}
projects / apple / libc.git / commitdiff
