/*

+----------------------------------------------------------------------+

| Zend Engine |

+----------------------------------------------------------------------+

| Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) |

+----------------------------------------------------------------------+

| This source file is subject to version 2.00 of the Zend license, |

| that is bundled with this package in the file LICENSE, and is |

| available through the world-wide-web at the following url: |

| http://www.zend.com/license/2_00.txt. |

| If you did not receive a copy of the Zend license and are unable to |

| obtain it through the world-wide-web, please send a note to |

| license@zend.com so we can mail you a copy immediately. |

+----------------------------------------------------------------------+

| Authors: Andi Gutmans <andi@zend.com> |

| Zeev Suraski <zeev@zend.com> |

| Dmitry Stogov <dmitry@zend.com> |

+----------------------------------------------------------------------+

*/

/* $Id$ */

#include "zend.h"

#include "zend_alloc.h"

#include "zend_globals.h"

#include "zend_operators.h"

#ifdef HAVE_SIGNAL_H

# include <signal.h>

#endif

#ifdef HAVE_UNISTD_H

# include <unistd.h>

#endif

#ifdef ZEND_WIN32

# include <wincrypt.h>

# include <process.h>

#endif

#ifndef ZEND_MM_HEAP_PROTECTION

# define ZEND_MM_HEAP_PROTECTION ZEND_DEBUG

#endif

#ifndef ZEND_MM_SAFE_UNLINKING

# define ZEND_MM_SAFE_UNLINKING 1

#endif

#ifndef ZEND_MM_COOKIES

# define ZEND_MM_COOKIES ZEND_DEBUG

#endif

#ifdef _WIN64

# define PTR_FMT "0x%0.16I64x"

/*

#elif sizeof(long) == 8

# define PTR_FMT "0x%0.16lx"

*/

#else

# define PTR_FMT "0x%0.8lx"

#endif

#if ZEND_DEBUG

void zend_debug_alloc_output(char *format, ...)

{

char output_buf[256];

va_list args;

va_start(args, format);

vsprintf(output_buf, format, args);

va_end(args);

#ifdef ZEND_WIN32

OutputDebugString(output_buf);

#else

fprintf(stderr, "%s", output_buf);

#endif

}

#endif

#if (defined (__GNUC__) && __GNUC__ > 2 ) && !defined(__INTEL_COMPILER) && !defined(DARWIN) && !defined(__hpux) && !defined(_AIX)

static void zend_mm_panic(const char *message) __attribute__ ((noreturn));

#endif

static void zend_mm_panic(const char *message)

{

fprintf(stderr, "%s\n", message);

/* See http://support.microsoft.com/kb/190351 */

#ifdef PHP_WIN32

fflush(stderr);

#endif

#if ZEND_DEBUG && defined(HAVE_KILL) && defined(HAVE_GETPID)

kill(getpid(), SIGSEGV);

#endif

exit(1);

}

/*******************/

/* Storage Manager */

/*******************/

#ifdef ZEND_WIN32

# define HAVE_MEM_WIN32 /* use VirtualAlloc() to allocate memory */

#endif

#define HAVE_MEM_MALLOC /* use malloc() to allocate segments */

#include <sys/types.h>

#include <sys/stat.h>

#if HAVE_LIMITS_H

#include <limits.h>

#endif

#include <fcntl.h>

#include <errno.h>

#if defined(HAVE_MEM_MMAP_ANON) || defined(HAVE_MEM_MMAP_ZERO)

# ifdef HAVE_MREMAP

# ifndef _GNU_SOURCE

# define _GNU_SOURCE

# endif

# ifndef __USE_GNU

# define __USE_GNU

# endif

# endif

# include <sys/mman.h>

# ifndef MAP_ANON

# ifdef MAP_ANONYMOUS

# define MAP_ANON MAP_ANONYMOUS

# endif

# endif

# ifndef MREMAP_MAYMOVE

# define MREMAP_MAYMOVE 0

# endif

# ifndef MAP_FAILED

# define MAP_FAILED ((void*)-1)

# endif

#endif

static zend_mm_storage* zend_mm_mem_dummy_init(void *params)

{

return malloc(sizeof(zend_mm_storage));

}

static void zend_mm_mem_dummy_dtor(zend_mm_storage *storage)

{

free(storage);

}

static void zend_mm_mem_dummy_compact(zend_mm_storage *storage)

{

}

#if defined(HAVE_MEM_MMAP_ANON) || defined(HAVE_MEM_MMAP_ZERO)

static zend_mm_segment* zend_mm_mem_mmap_realloc(zend_mm_storage *storage, zend_mm_segment* segment, size_t size)

{

zend_mm_segment *ret;

#ifdef HAVE_MREMAP

#if defined(__NetBSD__)

/* NetBSD 5 supports mremap but takes an extra newp argument */

ret = (zend_mm_segment*)mremap(segment, segment->size, segment, size, MREMAP_MAYMOVE);

#else

ret = (zend_mm_segment*)mremap(segment, segment->size, size, MREMAP_MAYMOVE);

#endif

if (ret == MAP_FAILED) {

#endif

ret = storage->handlers->_alloc(storage, size);

if (ret) {

memcpy(ret, segment, size > segment->size ? segment->size : size);

storage->handlers->_free(storage, segment);

}

#ifdef HAVE_MREMAP

}

#endif

return ret;

}

static void zend_mm_mem_mmap_free(zend_mm_storage *storage, zend_mm_segment* segment)

{

munmap((void*)segment, segment->size);

}

#endif

#ifdef HAVE_MEM_MMAP_ANON

static zend_mm_segment* zend_mm_mem_mmap_anon_alloc(zend_mm_storage *storage, size_t size)

{

zend_mm_segment *ret = (zend_mm_segment*)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);

if (ret == MAP_FAILED) {

ret = NULL;

}

return ret;

}

# define ZEND_MM_MEM_MMAP_ANON_DSC {"mmap_anon", zend_mm_mem_dummy_init, zend_mm_mem_dummy_dtor, zend_mm_mem_dummy_compact, zend_mm_mem_mmap_anon_alloc, zend_mm_mem_mmap_realloc, zend_mm_mem_mmap_free}

#endif

#ifdef HAVE_MEM_MMAP_ZERO

static int zend_mm_dev_zero_fd = -1;

static zend_mm_storage* zend_mm_mem_mmap_zero_init(void *params)

{

if (zend_mm_dev_zero_fd == -1) {

zend_mm_dev_zero_fd = open("/dev/zero", O_RDWR, S_IRUSR | S_IWUSR);

}

if (zend_mm_dev_zero_fd >= 0) {

return malloc(sizeof(zend_mm_storage));

} else {

return NULL;

}

}

static void zend_mm_mem_mmap_zero_dtor(zend_mm_storage *storage)

{

close(zend_mm_dev_zero_fd);

free(storage);

}

static zend_mm_segment* zend_mm_mem_mmap_zero_alloc(zend_mm_storage *storage, size_t size)

{

zend_mm_segment *ret = (zend_mm_segment*)mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, zend_mm_dev_zero_fd, 0);

if (ret == MAP_FAILED) {

ret = NULL;

}

return ret;

}

# define ZEND_MM_MEM_MMAP_ZERO_DSC {"mmap_zero", zend_mm_mem_mmap_zero_init, zend_mm_mem_mmap_zero_dtor, zend_mm_mem_dummy_compact, zend_mm_mem_mmap_zero_alloc, zend_mm_mem_mmap_realloc, zend_mm_mem_mmap_free}

#endif

#ifdef HAVE_MEM_WIN32

static zend_mm_storage* zend_mm_mem_win32_init(void *params)

{

HANDLE heap = HeapCreate(HEAP_NO_SERIALIZE, 0, 0);

zend_mm_storage* storage;

if (heap == NULL) {

return NULL;

}

storage = (zend_mm_storage*)malloc(sizeof(zend_mm_storage));

if (storage == NULL) {

HeapDestroy(heap);

return NULL;

}

storage->data = (void*) heap;

return storage;

}

static void zend_mm_mem_win32_dtor(zend_mm_storage *storage)

{

HeapDestroy((HANDLE)storage->data);

free(storage);

}

static void zend_mm_mem_win32_compact(zend_mm_storage *storage)

{

HeapDestroy((HANDLE)storage->data);

storage->data = (void*)HeapCreate(HEAP_NO_SERIALIZE, 0, 0);

}

static zend_mm_segment* zend_mm_mem_win32_alloc(zend_mm_storage *storage, size_t size)

{

return (zend_mm_segment*) HeapAlloc((HANDLE)storage->data, HEAP_NO_SERIALIZE, size);

}

static void zend_mm_mem_win32_free(zend_mm_storage *storage, zend_mm_segment* segment)

{

HeapFree((HANDLE)storage->data, HEAP_NO_SERIALIZE, segment);

}

static zend_mm_segment* zend_mm_mem_win32_realloc(zend_mm_storage *storage, zend_mm_segment* segment, size_t size)

{

return (zend_mm_segment*) HeapReAlloc((HANDLE)storage->data, HEAP_NO_SERIALIZE, segment, size);

}

# define ZEND_MM_MEM_WIN32_DSC {"win32", zend_mm_mem_win32_init, zend_mm_mem_win32_dtor, zend_mm_mem_win32_compact, zend_mm_mem_win32_alloc, zend_mm_mem_win32_realloc, zend_mm_mem_win32_free}

#endif

#ifdef HAVE_MEM_MALLOC

static zend_mm_segment* zend_mm_mem_malloc_alloc(zend_mm_storage *storage, size_t size)

{

return (zend_mm_segment*)malloc(size);

}

static zend_mm_segment* zend_mm_mem_malloc_realloc(zend_mm_storage *storage, zend_mm_segment *ptr, size_t size)

{

return (zend_mm_segment*)realloc(ptr, size);

}

static void zend_mm_mem_malloc_free(zend_mm_storage *storage, zend_mm_segment *ptr)

{

free(ptr);

}

# define ZEND_MM_MEM_MALLOC_DSC {"malloc", zend_mm_mem_dummy_init, zend_mm_mem_dummy_dtor, zend_mm_mem_dummy_compact, zend_mm_mem_malloc_alloc, zend_mm_mem_malloc_realloc, zend_mm_mem_malloc_free}

#endif

static const zend_mm_mem_handlers mem_handlers[] = {

#ifdef HAVE_MEM_WIN32

ZEND_MM_MEM_WIN32_DSC,

#endif

#ifdef HAVE_MEM_MALLOC

ZEND_MM_MEM_MALLOC_DSC,

#endif

#ifdef HAVE_MEM_MMAP_ANON

ZEND_MM_MEM_MMAP_ANON_DSC,

#endif

#ifdef HAVE_MEM_MMAP_ZERO

ZEND_MM_MEM_MMAP_ZERO_DSC,

#endif

{NULL, NULL, NULL, NULL, NULL, NULL}

};

# define ZEND_MM_STORAGE_DTOR() heap->storage->handlers->dtor(heap->storage)

# define ZEND_MM_STORAGE_ALLOC(size) heap->storage->handlers->_alloc(heap->storage, size)

# define ZEND_MM_STORAGE_REALLOC(ptr, size) heap->storage->handlers->_realloc(heap->storage, ptr, size)

# define ZEND_MM_STORAGE_FREE(ptr) heap->storage->handlers->_free(heap->storage, ptr)

/****************/

/* Heap Manager */

/****************/

#define MEM_BLOCK_VALID 0x7312F8DC

#define MEM_BLOCK_FREED 0x99954317

#define MEM_BLOCK_CACHED 0xFB8277DC

#define MEM_BLOCK_GUARD 0x2A8FCC84

#define MEM_BLOCK_LEAK 0x6C5E8F2D

/* mm block type */

typedef struct _zend_mm_block_info {

#if ZEND_MM_COOKIES

size_t _cookie;

#endif

size_t _size;

size_t _prev;

} zend_mm_block_info;

#if ZEND_DEBUG

typedef struct _zend_mm_debug_info {

const char *filename;

uint lineno;

const char *orig_filename;

uint orig_lineno;

size_t size;

#if ZEND_MM_HEAP_PROTECTION

unsigned int start_magic;

#endif

} zend_mm_debug_info;

#elif ZEND_MM_HEAP_PROTECTION

typedef struct _zend_mm_debug_info {

size_t size;

unsigned int start_magic;

} zend_mm_debug_info;

#endif

typedef struct _zend_mm_block {

zend_mm_block_info info;

#if ZEND_DEBUG

unsigned int magic;

# ifdef ZTS

THREAD_T thread_id;

# endif

zend_mm_debug_info debug;

#elif ZEND_MM_HEAP_PROTECTION

zend_mm_debug_info debug;

#endif

} zend_mm_block;

typedef struct _zend_mm_small_free_block {

zend_mm_block_info info;

#if ZEND_DEBUG

unsigned int magic;

# ifdef ZTS

THREAD_T thread_id;

# endif

#endif

struct _zend_mm_free_block *prev_free_block;

struct _zend_mm_free_block *next_free_block;

} zend_mm_small_free_block;

typedef struct _zend_mm_free_block {

zend_mm_block_info info;

#if ZEND_DEBUG

unsigned int magic;

# ifdef ZTS

THREAD_T thread_id;

# endif

#endif

struct _zend_mm_free_block *prev_free_block;

struct _zend_mm_free_block *next_free_block;

struct _zend_mm_free_block **parent;

struct _zend_mm_free_block *child[2];

} zend_mm_free_block;

#define ZEND_MM_NUM_BUCKETS (sizeof(size_t) << 3)

#define ZEND_MM_CACHE 1

#define ZEND_MM_CACHE_SIZE (ZEND_MM_NUM_BUCKETS * 4 * 1024)

#ifndef ZEND_MM_CACHE_STAT

# define ZEND_MM_CACHE_STAT 0

#endif

struct _zend_mm_heap {

int use_zend_alloc;

void *(*_malloc)(size_t);

void (*_free)(void*);

void *(*_realloc)(void*, size_t);

size_t free_bitmap;

size_t large_free_bitmap;

size_t block_size;

size_t compact_size;

zend_mm_segment *segments_list;

zend_mm_storage *storage;

size_t real_size;

size_t real_peak;

size_t limit;

size_t size;

size_t peak;

size_t reserve_size;

void *reserve;

int overflow;

int internal;

#if ZEND_MM_CACHE

unsigned int cached;

zend_mm_free_block *cache[ZEND_MM_NUM_BUCKETS];

#endif

zend_mm_free_block *free_buckets[ZEND_MM_NUM_BUCKETS*2];

zend_mm_free_block *large_free_buckets[ZEND_MM_NUM_BUCKETS];

zend_mm_free_block *rest_buckets[2];

int rest_count;

#if ZEND_MM_CACHE_STAT

struct {

int count;

int max_count;

int hit;

int miss;

} cache_stat[ZEND_MM_NUM_BUCKETS+1];

#endif

};

#define ZEND_MM_SMALL_FREE_BUCKET(heap, index) \

(zend_mm_free_block*) ((char*)&heap->free_buckets[index * 2] + \

sizeof(zend_mm_free_block*) * 2 - \

sizeof(zend_mm_small_free_block))

#define ZEND_MM_REST_BUCKET(heap) \

(zend_mm_free_block*)((char*)&heap->rest_buckets[0] + \

sizeof(zend_mm_free_block*) * 2 - \

sizeof(zend_mm_small_free_block))

#define ZEND_MM_REST_BLOCK ((zend_mm_free_block**)(zend_uintptr_t)(1))

#define ZEND_MM_MAX_REST_BLOCKS 16

#if ZEND_MM_COOKIES

static unsigned int _zend_mm_cookie = 0;

# define ZEND_MM_COOKIE(block) \

(((size_t)(block)) ^ _zend_mm_cookie)

# define ZEND_MM_SET_COOKIE(block) \

(block)->info._cookie = ZEND_MM_COOKIE(block)

# define ZEND_MM_CHECK_COOKIE(block) \

if (UNEXPECTED((block)->info._cookie != ZEND_MM_COOKIE(block))) { \

zend_mm_panic("zend_mm_heap corrupted"); \

}

#else

# define ZEND_MM_SET_COOKIE(block)

# define ZEND_MM_CHECK_COOKIE(block)

#endif

/* Default memory segment size */

#define ZEND_MM_SEG_SIZE (256 * 1024)

/* Reserved space for error reporting in case of memory overflow */

#define ZEND_MM_RESERVE_SIZE (8*1024)

#ifdef _WIN64

# define ZEND_MM_LONG_CONST(x) (x##i64)

#else

# define ZEND_MM_LONG_CONST(x) (x##L)

#endif

#define ZEND_MM_TYPE_MASK ZEND_MM_LONG_CONST(0x3)

#define ZEND_MM_FREE_BLOCK ZEND_MM_LONG_CONST(0x0)

#define ZEND_MM_USED_BLOCK ZEND_MM_LONG_CONST(0x1)

#define ZEND_MM_GUARD_BLOCK ZEND_MM_LONG_CONST(0x3)

#define ZEND_MM_BLOCK(b, type, size) do { \

size_t _size = (size); \

(b)->info._size = (type) | _size; \

ZEND_MM_BLOCK_AT(b, _size)->info._prev = (type) | _size; \

ZEND_MM_SET_COOKIE(b); \

} while (0);

#define ZEND_MM_LAST_BLOCK(b) do { \

(b)->info._size = ZEND_MM_GUARD_BLOCK | ZEND_MM_ALIGNED_HEADER_SIZE; \

ZEND_MM_SET_MAGIC(b, MEM_BLOCK_GUARD); \

} while (0);

#define ZEND_MM_BLOCK_SIZE(b) ((b)->info._size & ~ZEND_MM_TYPE_MASK)

#define ZEND_MM_IS_FREE_BLOCK(b) (!((b)->info._size & ZEND_MM_USED_BLOCK))

#define ZEND_MM_IS_USED_BLOCK(b) ((b)->info._size & ZEND_MM_USED_BLOCK)

#define ZEND_MM_IS_GUARD_BLOCK(b) (((b)->info._size & ZEND_MM_TYPE_MASK) == ZEND_MM_GUARD_BLOCK)

#define ZEND_MM_NEXT_BLOCK(b) ZEND_MM_BLOCK_AT(b, ZEND_MM_BLOCK_SIZE(b))

#define ZEND_MM_PREV_BLOCK(b) ZEND_MM_BLOCK_AT(b, -(ssize_t)((b)->info._prev & ~ZEND_MM_TYPE_MASK))

#define ZEND_MM_PREV_BLOCK_IS_FREE(b) (!((b)->info._prev & ZEND_MM_USED_BLOCK))

#define ZEND_MM_MARK_FIRST_BLOCK(b) ((b)->info._prev = ZEND_MM_GUARD_BLOCK)

#define ZEND_MM_IS_FIRST_BLOCK(b) ((b)->info._prev == ZEND_MM_GUARD_BLOCK)

/* optimized access */

#define ZEND_MM_FREE_BLOCK_SIZE(b) (b)->info._size

/* Aligned header size */

#define ZEND_MM_ALIGNED_HEADER_SIZE ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_block))

#define ZEND_MM_ALIGNED_FREE_HEADER_SIZE ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_small_free_block))

#define ZEND_MM_MIN_ALLOC_BLOCK_SIZE ZEND_MM_ALIGNED_SIZE(ZEND_MM_ALIGNED_HEADER_SIZE + END_MAGIC_SIZE)

#define ZEND_MM_ALIGNED_MIN_HEADER_SIZE (ZEND_MM_MIN_ALLOC_BLOCK_SIZE>ZEND_MM_ALIGNED_FREE_HEADER_SIZE?ZEND_MM_MIN_ALLOC_BLOCK_SIZE:ZEND_MM_ALIGNED_FREE_HEADER_SIZE)

#define ZEND_MM_ALIGNED_SEGMENT_SIZE ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_segment))

#define ZEND_MM_MIN_SIZE ((ZEND_MM_ALIGNED_MIN_HEADER_SIZE>(ZEND_MM_ALIGNED_HEADER_SIZE+END_MAGIC_SIZE))?(ZEND_MM_ALIGNED_MIN_HEADER_SIZE-(ZEND_MM_ALIGNED_HEADER_SIZE+END_MAGIC_SIZE)):0)

#define ZEND_MM_MAX_SMALL_SIZE ((ZEND_MM_NUM_BUCKETS<<ZEND_MM_ALIGNMENT_LOG2)+ZEND_MM_ALIGNED_MIN_HEADER_SIZE)

#define ZEND_MM_TRUE_SIZE(size) ((size<ZEND_MM_MIN_SIZE)?(ZEND_MM_ALIGNED_MIN_HEADER_SIZE):(ZEND_MM_ALIGNED_SIZE(size+ZEND_MM_ALIGNED_HEADER_SIZE+END_MAGIC_SIZE)))

#define ZEND_MM_BUCKET_INDEX(true_size) ((true_size>>ZEND_MM_ALIGNMENT_LOG2)-(ZEND_MM_ALIGNED_MIN_HEADER_SIZE>>ZEND_MM_ALIGNMENT_LOG2))

#define ZEND_MM_SMALL_SIZE(true_size) (true_size < ZEND_MM_MAX_SMALL_SIZE)

/* Memory calculations */

#define ZEND_MM_BLOCK_AT(blk, offset) ((zend_mm_block *) (((char *) (blk))+(offset)))

#define ZEND_MM_DATA_OF(p) ((void *) (((char *) (p))+ZEND_MM_ALIGNED_HEADER_SIZE))

#define ZEND_MM_HEADER_OF(blk) ZEND_MM_BLOCK_AT(blk, -(int)ZEND_MM_ALIGNED_HEADER_SIZE)

/* Debug output */

#if ZEND_DEBUG

# ifdef ZTS

# define ZEND_MM_SET_THREAD_ID(block) \

((zend_mm_block*)(block))->thread_id = tsrm_thread_id()

# define ZEND_MM_BAD_THREAD_ID(block) ((block)->thread_id != tsrm_thread_id())

# else

# define ZEND_MM_SET_THREAD_ID(block)

# define ZEND_MM_BAD_THREAD_ID(block) 0

# endif

# define ZEND_MM_VALID_PTR(block) \

zend_mm_check_ptr(heap, block, 1 ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC)

# define ZEND_MM_SET_MAGIC(block, val) do { \

(block)->magic = (val); \

} while (0)

# define ZEND_MM_CHECK_MAGIC(block, val) do { \

if ((block)->magic != (val)) { \

zend_mm_panic("zend_mm_heap corrupted"); \

} \

} while (0)

# define ZEND_MM_SET_DEBUG_INFO(block, __size, set_valid, set_thread) do { \

((zend_mm_block*)(block))->debug.filename = __zend_filename; \

((zend_mm_block*)(block))->debug.lineno = __zend_lineno; \

((zend_mm_block*)(block))->debug.orig_filename = __zend_orig_filename; \

((zend_mm_block*)(block))->debug.orig_lineno = __zend_orig_lineno; \

ZEND_MM_SET_BLOCK_SIZE(block, __size); \

if (set_valid) { \

ZEND_MM_SET_MAGIC(block, MEM_BLOCK_VALID); \

} \

if (set_thread) { \

ZEND_MM_SET_THREAD_ID(block); \

} \

} while (0)

#else

# define ZEND_MM_VALID_PTR(ptr) EXPECTED(ptr != NULL)

# define ZEND_MM_SET_MAGIC(block, val)

# define ZEND_MM_CHECK_MAGIC(block, val)

# define ZEND_MM_SET_DEBUG_INFO(block, __size, set_valid, set_thread) ZEND_MM_SET_BLOCK_SIZE(block, __size)

#endif

#if ZEND_MM_HEAP_PROTECTION

# define ZEND_MM_CHECK_PROTECTION(block) \

do { \

if ((block)->debug.start_magic != _mem_block_start_magic || \

memcmp(ZEND_MM_END_MAGIC_PTR(block), &_mem_block_end_magic, END_MAGIC_SIZE) != 0) { \

zend_mm_panic("zend_mm_heap corrupted"); \

} \

} while (0)

# define ZEND_MM_END_MAGIC_PTR(block) \

(((char*)(ZEND_MM_DATA_OF(block))) + ((zend_mm_block*)(block))->debug.size)

# define END_MAGIC_SIZE sizeof(unsigned int)

# define ZEND_MM_SET_BLOCK_SIZE(block, __size) do { \

char *p; \

((zend_mm_block*)(block))->debug.size = (__size); \

p = ZEND_MM_END_MAGIC_PTR(block); \

((zend_mm_block*)(block))->debug.start_magic = _mem_block_start_magic; \

memcpy(p, &_mem_block_end_magic, END_MAGIC_SIZE); \

} while (0)

static unsigned int _mem_block_start_magic = 0;

static unsigned int _mem_block_end_magic = 0;

#else

# if ZEND_DEBUG

# define ZEND_MM_SET_BLOCK_SIZE(block, _size) \

((zend_mm_block*)(block))->debug.size = (_size)

# else

# define ZEND_MM_SET_BLOCK_SIZE(block, _size)

# endif

# define ZEND_MM_CHECK_PROTECTION(block)

# define END_MAGIC_SIZE 0

#endif

#if ZEND_MM_SAFE_UNLINKING

# define ZEND_MM_CHECK_BLOCK_LINKAGE(block) \

if (UNEXPECTED((block)->info._size != ZEND_MM_BLOCK_AT(block, ZEND_MM_FREE_BLOCK_SIZE(block))->info._prev) || \

UNEXPECTED(!UNEXPECTED(ZEND_MM_IS_FIRST_BLOCK(block)) && \

UNEXPECTED(ZEND_MM_PREV_BLOCK(block)->info._size != (block)->info._prev))) { \

zend_mm_panic("zend_mm_heap corrupted"); \

}

#define ZEND_MM_CHECK_TREE(block) \

if (UNEXPECTED(*((block)->parent) != (block))) { \

zend_mm_panic("zend_mm_heap corrupted"); \

}

#else

# define ZEND_MM_CHECK_BLOCK_LINKAGE(block)

# define ZEND_MM_CHECK_TREE(block)

#endif

#define ZEND_MM_LARGE_BUCKET_INDEX(S) zend_mm_high_bit(S)

static void *_zend_mm_alloc_int(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC) ZEND_ATTRIBUTE_MALLOC ZEND_ATTRIBUTE_ALLOC_SIZE(2);

static void _zend_mm_free_int(zend_mm_heap *heap, void *p ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

static void *_zend_mm_realloc_int(zend_mm_heap *heap, void *p, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC) ZEND_ATTRIBUTE_ALLOC_SIZE(3);

static inline unsigned int zend_mm_high_bit(size_t _size)

{

#if defined(__GNUC__) && (defined(__native_client__) || defined(i386))

unsigned int n;

__asm__("bsrl %1,%0\n\t" : "=r" (n) : "rm" (_size) : "cc");

return n;

#elif defined(__GNUC__) && defined(__x86_64__)

unsigned long n;

__asm__("bsr %1,%0\n\t" : "=r" (n) : "rm" (_size) : "cc");

return (unsigned int)n;

#elif defined(_MSC_VER) && defined(_M_IX86)

__asm {

bsr eax, _size

}

#elif defined(__GNUC__) && (defined(__arm__) || defined(__aarch64__))

return (8 * SIZEOF_SIZE_T - 1) - __builtin_clzl(_size);

#else

unsigned int n = 0;

while (_size != 0) {

_size = _size >> 1;

n++;

}

return n-1;

#endif

}

static inline unsigned int zend_mm_low_bit(size_t _size)

{

#if defined(__GNUC__) && (defined(__native_client__) || defined(i386))

unsigned int n;

__asm__("bsfl %1,%0\n\t" : "=r" (n) : "rm" (_size) : "cc");

return n;

#elif defined(__GNUC__) && defined(__x86_64__)

unsigned long n;

__asm__("bsf %1,%0\n\t" : "=r" (n) : "rm" (_size) : "cc");

return (unsigned int)n;

#elif defined(_MSC_VER) && defined(_M_IX86)

__asm {

bsf eax, _size

}

#elif defined(__GNUC__) && (defined(__arm__) || defined(__aarch64__))

return __builtin_ctzl(_size);

#else

static const int offset[16] = {4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};

unsigned int n;

unsigned int index = 0;

n = offset[_size & 15];

while (n == 4) {

_size >>= 4;

index += n;

n = offset[_size & 15];

}

return index + n;

#endif

}

static inline void zend_mm_add_to_free_list(zend_mm_heap *heap, zend_mm_free_block *mm_block)

{

size_t size;

size_t index;

ZEND_MM_SET_MAGIC(mm_block, MEM_BLOCK_FREED);

size = ZEND_MM_FREE_BLOCK_SIZE(mm_block);

if (EXPECTED(!ZEND_MM_SMALL_SIZE(size))) {

zend_mm_free_block **p;

index = ZEND_MM_LARGE_BUCKET_INDEX(size);

p = &heap->large_free_buckets[index];

mm_block->child[0] = mm_block->child[1] = NULL;

if (!*p) {

*p = mm_block;

mm_block->parent = p;

mm_block->prev_free_block = mm_block->next_free_block = mm_block;

heap->large_free_bitmap |= (ZEND_MM_LONG_CONST(1) << index);

} else {

size_t m;

for (m = size << (ZEND_MM_NUM_BUCKETS - index); ; m <<= 1) {

zend_mm_free_block *prev = *p;

if (ZEND_MM_FREE_BLOCK_SIZE(prev) != size) {

p = &prev->child[(m >> (ZEND_MM_NUM_BUCKETS-1)) & 1];

if (!*p) {

*p = mm_block;

mm_block->parent = p;

mm_block->prev_free_block = mm_block->next_free_block = mm_block;

break;

}

} else {

zend_mm_free_block *next = prev->next_free_block;

prev->next_free_block = next->prev_free_block = mm_block;

mm_block->next_free_block = next;

mm_block->prev_free_block = prev;

mm_block->parent = NULL;

break;

}

}

}

} else {

zend_mm_free_block *prev, *next;

index = ZEND_MM_BUCKET_INDEX(size);

prev = ZEND_MM_SMALL_FREE_BUCKET(heap, index);

if (prev->prev_free_block == prev) {

heap->free_bitmap |= (ZEND_MM_LONG_CONST(1) << index);

}

next = prev->next_free_block;

mm_block->prev_free_block = prev;

mm_block->next_free_block = next;

prev->next_free_block = next->prev_free_block = mm_block;

}

}

static inline void zend_mm_remove_from_free_list(zend_mm_heap *heap, zend_mm_free_block *mm_block)

{

zend_mm_free_block *prev = mm_block->prev_free_block;

zend_mm_free_block *next = mm_block->next_free_block;

ZEND_MM_CHECK_MAGIC(mm_block, MEM_BLOCK_FREED);

if (EXPECTED(prev == mm_block)) {

zend_mm_free_block **rp, **cp;

#if ZEND_MM_SAFE_UNLINKING

if (UNEXPECTED(next != mm_block)) {

zend_mm_panic("zend_mm_heap corrupted");

}

#endif

rp = &mm_block->child[mm_block->child[1] != NULL];

prev = *rp;

if (EXPECTED(prev == NULL)) {

size_t index = ZEND_MM_LARGE_BUCKET_INDEX(ZEND_MM_FREE_BLOCK_SIZE(mm_block));

ZEND_MM_CHECK_TREE(mm_block);

*mm_block->parent = NULL;

if (mm_block->parent == &heap->large_free_buckets[index]) {

heap->large_free_bitmap &= ~(ZEND_MM_LONG_CONST(1) << index);

}

} else {

while (*(cp = &(prev->child[prev->child[1] != NULL])) != NULL) {

prev = *cp;

rp = cp;

}

*rp = NULL;

subst_block:

ZEND_MM_CHECK_TREE(mm_block);

*mm_block->parent = prev;

prev->parent = mm_block->parent;

if ((prev->child[0] = mm_block->child[0])) {

ZEND_MM_CHECK_TREE(prev->child[0]);

prev->child[0]->parent = &prev->child[0];

}

if ((prev->child[1] = mm_block->child[1])) {

ZEND_MM_CHECK_TREE(prev->child[1]);

prev->child[1]->parent = &prev->child[1];

}

}

} else {

#if ZEND_MM_SAFE_UNLINKING

if (UNEXPECTED(prev->next_free_block != mm_block) || UNEXPECTED(next->prev_free_block != mm_block)) {

zend_mm_panic("zend_mm_heap corrupted");

}

#endif

prev->next_free_block = next;

next->prev_free_block = prev;

if (EXPECTED(ZEND_MM_SMALL_SIZE(ZEND_MM_FREE_BLOCK_SIZE(mm_block)))) {

if (EXPECTED(prev == next)) {

size_t index = ZEND_MM_BUCKET_INDEX(ZEND_MM_FREE_BLOCK_SIZE(mm_block));

if (EXPECTED(heap->free_buckets[index*2] == heap->free_buckets[index*2+1])) {

heap->free_bitmap &= ~(ZEND_MM_LONG_CONST(1) << index);

}

}

} else if (UNEXPECTED(mm_block->parent == ZEND_MM_REST_BLOCK)) {

heap->rest_count--;

} else if (UNEXPECTED(mm_block->parent != NULL)) {

goto subst_block;

}

}

}

static inline void zend_mm_add_to_rest_list(zend_mm_heap *heap, zend_mm_free_block *mm_block)

{

zend_mm_free_block *prev, *next;

while (heap->rest_count >= ZEND_MM_MAX_REST_BLOCKS) {

zend_mm_free_block *p = heap->rest_buckets[1];

if (!ZEND_MM_SMALL_SIZE(ZEND_MM_FREE_BLOCK_SIZE(p))) {

heap->rest_count--;

}

prev = p->prev_free_block;

next = p->next_free_block;

prev->next_free_block = next;

next->prev_free_block = prev;

zend_mm_add_to_free_list(heap, p);

}

if (!ZEND_MM_SMALL_SIZE(ZEND_MM_FREE_BLOCK_SIZE(mm_block))) {

mm_block->parent = ZEND_MM_REST_BLOCK;

heap->rest_count++;

}

ZEND_MM_SET_MAGIC(mm_block, MEM_BLOCK_FREED);

prev = heap->rest_buckets[0];

next = prev->next_free_block;

mm_block->prev_free_block = prev;

mm_block->next_free_block = next;

prev->next_free_block = next->prev_free_block = mm_block;

}

static inline void zend_mm_init(zend_mm_heap *heap)

{

zend_mm_free_block* p;

int i;

heap->free_bitmap = 0;

heap->large_free_bitmap = 0;

#if ZEND_MM_CACHE

heap->cached = 0;

memset(heap->cache, 0, sizeof(heap->cache));

#endif

#if ZEND_MM_CACHE_STAT

for (i = 0; i < ZEND_MM_NUM_BUCKETS; i++) {

heap->cache_stat[i].count = 0;

}

#endif

p = ZEND_MM_SMALL_FREE_BUCKET(heap, 0);

for (i = 0; i < ZEND_MM_NUM_BUCKETS; i++) {

p->next_free_block = p;

p->prev_free_block = p;

p = (zend_mm_free_block*)((char*)p + sizeof(zend_mm_free_block*) * 2);

heap->large_free_buckets[i] = NULL;

}

heap->rest_buckets[0] = heap->rest_buckets[1] = ZEND_MM_REST_BUCKET(heap);

heap->rest_count = 0;

}

static void zend_mm_del_segment(zend_mm_heap *heap, zend_mm_segment *segment)

{

zend_mm_segment **p = &heap->segments_list;

while (*p != segment) {

p = &(*p)->next_segment;

}

*p = segment->next_segment;

heap->real_size -= segment->size;

ZEND_MM_STORAGE_FREE(segment);

}

#if ZEND_MM_CACHE

static void zend_mm_free_cache(zend_mm_heap *heap)

{

int i;

for (i = 0; i < ZEND_MM_NUM_BUCKETS; i++) {

if (heap->cache[i]) {

zend_mm_free_block *mm_block = heap->cache[i];

while (mm_block) {

size_t size = ZEND_MM_BLOCK_SIZE(mm_block);

zend_mm_free_block *q = mm_block->prev_free_block;

zend_mm_block *next_block = ZEND_MM_NEXT_BLOCK(mm_block);

heap->cached -= size;

if (ZEND_MM_PREV_BLOCK_IS_FREE(mm_block)) {

mm_block = (zend_mm_free_block*)ZEND_MM_PREV_BLOCK(mm_block);

size += ZEND_MM_FREE_BLOCK_SIZE(mm_block);

zend_mm_remove_from_free_list(heap, (zend_mm_free_block *) mm_block);

}

if (ZEND_MM_IS_FREE_BLOCK(next_block)) {

size += ZEND_MM_FREE_BLOCK_SIZE(next_block);

zend_mm_remove_from_free_list(heap, (zend_mm_free_block *) next_block);

}

ZEND_MM_BLOCK(mm_block, ZEND_MM_FREE_BLOCK, size);

if (ZEND_MM_IS_FIRST_BLOCK(mm_block) &&

ZEND_MM_IS_GUARD_BLOCK(ZEND_MM_NEXT_BLOCK(mm_block))) {

zend_mm_del_segment(heap, (zend_mm_segment *) ((char *)mm_block - ZEND_MM_ALIGNED_SEGMENT_SIZE));

} else {

zend_mm_add_to_free_list(heap, (zend_mm_free_block *) mm_block);

}

mm_block = q;

}

heap->cache[i] = NULL;

#if ZEND_MM_CACHE_STAT

heap->cache_stat[i].count = 0;

#endif

}

}

}

#endif

#if ZEND_MM_HEAP_PROTECTION || ZEND_MM_COOKIES

static void zend_mm_random(unsigned char *buf, size_t size) /* {{{ */

{

size_t i = 0;

unsigned char t;

#ifdef ZEND_WIN32

HCRYPTPROV hCryptProv;

int has_context = 0;

if (!CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, 0)) {

/* Could mean that the key container does not exist, let try

again by asking for a new one */

if (GetLastError() == NTE_BAD_KEYSET) {

if (CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_NEWKEYSET)) {

has_context = 1;

}

}

} else {

has_context = 1;

}

if (has_context) {

do {

BOOL ret = CryptGenRandom(hCryptProv, size, buf);

CryptReleaseContext(hCryptProv, 0);