/*

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

| Zend Engine |

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

| Copyright (c) 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@php.net> |

| Zeev Suraski <zeev@php.net> |

| Dmitry Stogov <dmitry@php.net> |

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

*/

/*

* zend_alloc is designed to be a modern CPU cache friendly memory manager

* for PHP. Most ideas are taken from jemalloc and tcmalloc implementations.

*

* All allocations are split into 3 categories:

*

* Huge - the size is greater than CHUNK size (~2M by default), allocation is

* performed using mmap(). The result is aligned on 2M boundary.

*

* Large - a number of 4096K pages inside a CHUNK. Large blocks

* are always aligned on page boundary.

*

* Small - less than 3/4 of page size. Small sizes are rounded up to nearest

* greater predefined small size (there are 30 predefined sizes:

* 8, 16, 24, 32, ... 3072). Small blocks are allocated from

* RUNs. Each RUN is allocated as a single or few following pages.

* Allocation inside RUNs implemented using linked list of free

* elements. The result is aligned to 8 bytes.

*

* zend_alloc allocates memory from OS by CHUNKs, these CHUNKs and huge memory

* blocks are always aligned to CHUNK boundary. So it's very easy to determine

* the CHUNK owning the certain pointer. Regular CHUNKs reserve a single

* page at start for special purpose. It contains bitset of free pages,

* few bitset for available runs of predefined small sizes, map of pages that

* keeps information about usage of each page in this CHUNK, etc.

*

* zend_alloc provides familiar emalloc/efree/erealloc API, but in addition it

* provides specialized and optimized routines to allocate blocks of predefined

* sizes (e.g. emalloc_2(), emallc_4(), ..., emalloc_large(), etc)

* The library uses C preprocessor tricks that substitute calls to emalloc()

* with more specialized routines when the requested size is known.

*/

#include "zend.h"

#include "zend_alloc.h"

#include "zend_globals.h"

#include "zend_operators.h"

#include "zend_multiply.h"

#include "zend_bitset.h"

#include <signal.h>

#ifdef HAVE_UNISTD_H

# include <unistd.h>

#endif

#ifdef ZEND_WIN32

# include <wincrypt.h>

# include <process.h>

# include "win32/winutil.h"

#endif

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <limits.h>

#include <fcntl.h>

#include <errno.h>

#ifndef _WIN32

# include <sys/mman.h>

# ifndef MAP_ANON

# ifdef MAP_ANONYMOUS

# define MAP_ANON MAP_ANONYMOUS

# endif

# endif

# ifndef MAP_FAILED

# define MAP_FAILED ((void*)-1)

# endif

# ifndef MAP_POPULATE

# define MAP_POPULATE 0

# endif

# if defined(_SC_PAGESIZE) || (_SC_PAGE_SIZE)

# define REAL_PAGE_SIZE _real_page_size

static size_t _real_page_size = ZEND_MM_PAGE_SIZE;

# endif

# ifdef MAP_ALIGNED_SUPER

# define MAP_HUGETLB MAP_ALIGNED_SUPER

# endif

#endif

#ifndef REAL_PAGE_SIZE

# define REAL_PAGE_SIZE ZEND_MM_PAGE_SIZE

#endif

/* NetBSD has an mremap() function with a signature that is incompatible with Linux (WTF?),

* so pretend it doesn't exist. */

#ifndef __linux__

# undef HAVE_MREMAP

#endif

#ifndef __APPLE__

# define ZEND_MM_FD -1

#else

/* Mac allows to track anonymous page via vmmap per TAG id.

* user land applications are allowed to take from 240 to 255.

*/

# define ZEND_MM_FD (250<<24)

#endif

#ifndef ZEND_MM_STAT

# define ZEND_MM_STAT 1 /* track current and peak memory usage */

#endif

#ifndef ZEND_MM_LIMIT

# define ZEND_MM_LIMIT 1 /* support for user-defined memory limit */

#endif

#ifndef ZEND_MM_CUSTOM

# define ZEND_MM_CUSTOM 1 /* support for custom memory allocator */

/* USE_ZEND_ALLOC=0 may switch to system malloc() */

#endif

#ifndef ZEND_MM_STORAGE

# define ZEND_MM_STORAGE 1 /* support for custom memory storage */

#endif

#ifndef ZEND_MM_ERROR

# define ZEND_MM_ERROR 1 /* report system errors */

#endif

#ifndef ZEND_MM_CHECK

# define ZEND_MM_CHECK(condition, message) do { \

if (UNEXPECTED(!(condition))) { \

zend_mm_panic(message); \

} \

} while (0)

#endif

typedef uint32_t zend_mm_page_info; /* 4-byte integer */

typedef zend_ulong zend_mm_bitset; /* 4-byte or 8-byte integer */

#define ZEND_MM_ALIGNED_OFFSET(size, alignment) \

(((size_t)(size)) & ((alignment) - 1))

#define ZEND_MM_ALIGNED_BASE(size, alignment) \

(((size_t)(size)) & ~((alignment) - 1))

#define ZEND_MM_SIZE_TO_NUM(size, alignment) \

(((size_t)(size) + ((alignment) - 1)) / (alignment))

#define ZEND_MM_BITSET_LEN (sizeof(zend_mm_bitset) * 8) /* 32 or 64 */

#define ZEND_MM_PAGE_MAP_LEN (ZEND_MM_PAGES / ZEND_MM_BITSET_LEN) /* 16 or 8 */

typedef zend_mm_bitset zend_mm_page_map[ZEND_MM_PAGE_MAP_LEN]; /* 64B */

#define ZEND_MM_IS_FRUN 0x00000000

#define ZEND_MM_IS_LRUN 0x40000000

#define ZEND_MM_IS_SRUN 0x80000000

#define ZEND_MM_LRUN_PAGES_MASK 0x000003ff

#define ZEND_MM_LRUN_PAGES_OFFSET 0

#define ZEND_MM_SRUN_BIN_NUM_MASK 0x0000001f

#define ZEND_MM_SRUN_BIN_NUM_OFFSET 0

#define ZEND_MM_SRUN_FREE_COUNTER_MASK 0x01ff0000

#define ZEND_MM_SRUN_FREE_COUNTER_OFFSET 16

#define ZEND_MM_NRUN_OFFSET_MASK 0x01ff0000

#define ZEND_MM_NRUN_OFFSET_OFFSET 16

#define ZEND_MM_LRUN_PAGES(info) (((info) & ZEND_MM_LRUN_PAGES_MASK) >> ZEND_MM_LRUN_PAGES_OFFSET)

#define ZEND_MM_SRUN_BIN_NUM(info) (((info) & ZEND_MM_SRUN_BIN_NUM_MASK) >> ZEND_MM_SRUN_BIN_NUM_OFFSET)

#define ZEND_MM_SRUN_FREE_COUNTER(info) (((info) & ZEND_MM_SRUN_FREE_COUNTER_MASK) >> ZEND_MM_SRUN_FREE_COUNTER_OFFSET)

#define ZEND_MM_NRUN_OFFSET(info) (((info) & ZEND_MM_NRUN_OFFSET_MASK) >> ZEND_MM_NRUN_OFFSET_OFFSET)

#define ZEND_MM_FRUN() ZEND_MM_IS_FRUN

#define ZEND_MM_LRUN(count) (ZEND_MM_IS_LRUN | ((count) << ZEND_MM_LRUN_PAGES_OFFSET))

#define ZEND_MM_SRUN(bin_num) (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET))

#define ZEND_MM_SRUN_EX(bin_num, count) (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) | ((count) << ZEND_MM_SRUN_FREE_COUNTER_OFFSET))

#define ZEND_MM_NRUN(bin_num, offset) (ZEND_MM_IS_SRUN | ZEND_MM_IS_LRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) | ((offset) << ZEND_MM_NRUN_OFFSET_OFFSET))

#define ZEND_MM_BINS 30

typedef struct _zend_mm_page zend_mm_page;

typedef struct _zend_mm_bin zend_mm_bin;

typedef struct _zend_mm_free_slot zend_mm_free_slot;

typedef struct _zend_mm_chunk zend_mm_chunk;

typedef struct _zend_mm_huge_list zend_mm_huge_list;

int zend_mm_use_huge_pages = 0;

/*

* Memory is retrieved from OS by chunks of fixed size 2MB.

* Inside chunk it's managed by pages of fixed size 4096B.

* So each chunk consists from 512 pages.

* The first page of each chunk is reserved for chunk header.

* It contains service information about all pages.

*

* free_pages - current number of free pages in this chunk

*

* free_tail - number of continuous free pages at the end of chunk

*

* free_map - bitset (a bit for each page). The bit is set if the corresponding

* page is allocated. Allocator for "lage sizes" may easily find a

* free page (or a continuous number of pages) searching for zero

* bits.

*

* map - contains service information for each page. (32-bits for each

* page).

* usage:

* (2 bits)

* FRUN - free page,

* LRUN - first page of "large" allocation

* SRUN - first page of a bin used for "small" allocation

*

* lrun_pages:

* (10 bits) number of allocated pages

*

* srun_bin_num:

* (5 bits) bin number (e.g. 0 for sizes 0-2, 1 for 3-4,

* 2 for 5-8, 3 for 9-16 etc) see zend_alloc_sizes.h

*/

struct _zend_mm_heap {

#if ZEND_MM_CUSTOM

int use_custom_heap;

#endif

#if ZEND_MM_STORAGE

zend_mm_storage *storage;

#endif

#if ZEND_MM_STAT

size_t size; /* current memory usage */

size_t peak; /* peak memory usage */

#endif

zend_mm_free_slot *free_slot[ZEND_MM_BINS]; /* free lists for small sizes */

#if ZEND_MM_STAT || ZEND_MM_LIMIT

size_t real_size; /* current size of allocated pages */

#endif

#if ZEND_MM_STAT

size_t real_peak; /* peak size of allocated pages */

#endif

#if ZEND_MM_LIMIT

size_t limit; /* memory limit */

int overflow; /* memory overflow flag */

#endif

zend_mm_huge_list *huge_list; /* list of huge allocated blocks */

zend_mm_chunk *main_chunk;

zend_mm_chunk *cached_chunks; /* list of unused chunks */

int chunks_count; /* number of allocated chunks */

int peak_chunks_count; /* peak number of allocated chunks for current request */

int cached_chunks_count; /* number of cached chunks */

double avg_chunks_count; /* average number of chunks allocated per request */

int last_chunks_delete_boundary; /* number of chunks after last deletion */

int last_chunks_delete_count; /* number of deletion over the last boundary */

#if ZEND_MM_CUSTOM

union {

struct {

void *(*_malloc)(size_t);

void (*_free)(void*);

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

} std;

struct {

void *(*_malloc)(size_t ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

void (*_free)(void* ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

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

} debug;

} custom_heap;

HashTable *tracked_allocs;

#endif

};

struct _zend_mm_chunk {

zend_mm_heap *heap;

zend_mm_chunk *next;

zend_mm_chunk *prev;

uint32_t free_pages; /* number of free pages */

uint32_t free_tail; /* number of free pages at the end of chunk */

uint32_t num;

char reserve[64 - (sizeof(void*) * 3 + sizeof(uint32_t) * 3)];

zend_mm_heap heap_slot; /* used only in main chunk */

zend_mm_page_map free_map; /* 512 bits or 64 bytes */

zend_mm_page_info map[ZEND_MM_PAGES]; /* 2 KB = 512 * 4 */

};

struct _zend_mm_page {

char bytes[ZEND_MM_PAGE_SIZE];

};

/*

* bin - is one or few continuous pages (up to 8) used for allocation of

* a particular "small size".

*/

struct _zend_mm_bin {

char bytes[ZEND_MM_PAGE_SIZE * 8];

};

struct _zend_mm_free_slot {

zend_mm_free_slot *next_free_slot;

};

struct _zend_mm_huge_list {

void *ptr;

size_t size;

zend_mm_huge_list *next;

#if ZEND_DEBUG

zend_mm_debug_info dbg;

#endif

};

#define ZEND_MM_PAGE_ADDR(chunk, page_num) \

((void*)(((zend_mm_page*)(chunk)) + (page_num)))

#define _BIN_DATA_SIZE(num, size, elements, pages, x, y) size,

static const uint32_t bin_data_size[] = {

ZEND_MM_BINS_INFO(_BIN_DATA_SIZE, x, y)

};

#define _BIN_DATA_ELEMENTS(num, size, elements, pages, x, y) elements,

static const uint32_t bin_elements[] = {

ZEND_MM_BINS_INFO(_BIN_DATA_ELEMENTS, x, y)

};

#define _BIN_DATA_PAGES(num, size, elements, pages, x, y) pages,

static const uint32_t bin_pages[] = {

ZEND_MM_BINS_INFO(_BIN_DATA_PAGES, x, y)

};

#if ZEND_DEBUG

ZEND_COLD 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

static ZEND_COLD ZEND_NORETURN void zend_mm_panic(const char *message)

{

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

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

#ifdef ZEND_WIN32

fflush(stderr);

#endif

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

kill(getpid(), SIGSEGV);

#endif

exit(1);

}

static ZEND_COLD ZEND_NORETURN void zend_mm_safe_error(zend_mm_heap *heap,

const char *format,

size_t limit,

#if ZEND_DEBUG

const char *filename,

uint32_t lineno,

#endif

size_t size)

{

heap->overflow = 1;

zend_try {

zend_error_noreturn(E_ERROR,

format,

limit,

#if ZEND_DEBUG

filename,

lineno,

#endif

size);

} zend_catch {

} zend_end_try();

heap->overflow = 0;

zend_bailout();

exit(1);

}

#ifdef _WIN32

void

stderr_last_error(char *msg)

{

DWORD err = GetLastError();

char *buf = php_win32_error_to_msg(err);

if (!buf[0]) {

fprintf(stderr, "\n%s: [0x%08lx]\n", msg, err);

}

else {

fprintf(stderr, "\n%s: [0x%08lx] %s\n", msg, err, buf);

}

php_win32_error_msg_free(buf);

}

#endif

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

/* OS Allocation */

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

#ifndef HAVE_MREMAP

static void *zend_mm_mmap_fixed(void *addr, size_t size)

{

#ifdef _WIN32

return VirtualAlloc(addr, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

#else

int flags = MAP_PRIVATE | MAP_ANON;

#if defined(MAP_EXCL)

flags |= MAP_FIXED | MAP_EXCL;

#endif

/* MAP_FIXED leads to discarding of the old mapping, so it can't be used. */

void *ptr = mmap(addr, size, PROT_READ | PROT_WRITE, flags /*| MAP_POPULATE | MAP_HUGETLB*/, ZEND_MM_FD, 0);

if (ptr == MAP_FAILED) {

#if ZEND_MM_ERROR && !defined(MAP_EXCL)

fprintf(stderr, "\nmmap() failed: [%d] %s\n", errno, strerror(errno));

#endif

return NULL;

} else if (ptr != addr) {

if (munmap(ptr, size) != 0) {

#if ZEND_MM_ERROR

fprintf(stderr, "\nmunmap() failed: [%d] %s\n", errno, strerror(errno));

#endif

}

return NULL;

}

return ptr;

#endif

}

#endif

static void *zend_mm_mmap(size_t size)

{

#ifdef _WIN32

void *ptr = VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

if (ptr == NULL) {

#if ZEND_MM_ERROR

stderr_last_error("VirtualAlloc() failed");

#endif

return NULL;

}

return ptr;

#else

void *ptr;

#ifdef MAP_HUGETLB

if (zend_mm_use_huge_pages && size == ZEND_MM_CHUNK_SIZE) {

ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON | MAP_HUGETLB, -1, 0);

if (ptr != MAP_FAILED) {

return ptr;

}

}

#endif

ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, ZEND_MM_FD, 0);

if (ptr == MAP_FAILED) {

#if ZEND_MM_ERROR

fprintf(stderr, "\nmmap() failed: [%d] %s\n", errno, strerror(errno));

#endif

return NULL;

}

return ptr;

#endif

}

static void zend_mm_munmap(void *addr, size_t size)

{

#ifdef _WIN32

if (VirtualFree(addr, 0, MEM_RELEASE) == 0) {

#if ZEND_MM_ERROR

stderr_last_error("VirtualFree() failed");

#endif

}

#else

if (munmap(addr, size) != 0) {

#if ZEND_MM_ERROR

fprintf(stderr, "\nmunmap() failed: [%d] %s\n", errno, strerror(errno));

#endif

}

#endif

}

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

/* Bitmask */

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

/* number of trailing set (1) bits */

static zend_always_inline int zend_mm_bitset_nts(zend_mm_bitset bitset)

{

#if (defined(__GNUC__) || __has_builtin(__builtin_ctzl)) && SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CTZL)

return __builtin_ctzl(~bitset);

#elif (defined(__GNUC__) || __has_builtin(__builtin_ctzll)) && defined(PHP_HAVE_BUILTIN_CTZLL)

return __builtin_ctzll(~bitset);

#elif defined(_WIN32)

unsigned long index;

#if defined(_WIN64)

if (!BitScanForward64(&index, ~bitset)) {

#else

if (!BitScanForward(&index, ~bitset)) {

#endif

/* undefined behavior */

return 32;

}

return (int)index;

#else

int n;

if (bitset == (zend_mm_bitset)-1) return ZEND_MM_BITSET_LEN;

n = 0;

#if SIZEOF_ZEND_LONG == 8

if (sizeof(zend_mm_bitset) == 8) {

if ((bitset & 0xffffffff) == 0xffffffff) {n += 32; bitset = bitset >> Z_UL(32);}

}

#endif

if ((bitset & 0x0000ffff) == 0x0000ffff) {n += 16; bitset = bitset >> 16;}

if ((bitset & 0x000000ff) == 0x000000ff) {n += 8; bitset = bitset >> 8;}

if ((bitset & 0x0000000f) == 0x0000000f) {n += 4; bitset = bitset >> 4;}

if ((bitset & 0x00000003) == 0x00000003) {n += 2; bitset = bitset >> 2;}

return n + (bitset & 1);

#endif

}

static zend_always_inline int zend_mm_bitset_is_set(zend_mm_bitset *bitset, int bit)

{

return ZEND_BIT_TEST(bitset, bit);

}

static zend_always_inline void zend_mm_bitset_set_bit(zend_mm_bitset *bitset, int bit)

{

bitset[bit / ZEND_MM_BITSET_LEN] |= (Z_UL(1) << (bit & (ZEND_MM_BITSET_LEN-1)));

}

static zend_always_inline void zend_mm_bitset_reset_bit(zend_mm_bitset *bitset, int bit)

{

bitset[bit / ZEND_MM_BITSET_LEN] &= ~(Z_UL(1) << (bit & (ZEND_MM_BITSET_LEN-1)));

}

static zend_always_inline void zend_mm_bitset_set_range(zend_mm_bitset *bitset, int start, int len)

{

if (len == 1) {

zend_mm_bitset_set_bit(bitset, start);

} else {

int pos = start / ZEND_MM_BITSET_LEN;

int end = (start + len - 1) / ZEND_MM_BITSET_LEN;

int bit = start & (ZEND_MM_BITSET_LEN - 1);

zend_mm_bitset tmp;

if (pos != end) {

/* set bits from "bit" to ZEND_MM_BITSET_LEN-1 */

tmp = (zend_mm_bitset)-1 << bit;

bitset[pos++] |= tmp;

while (pos != end) {

/* set all bits */

bitset[pos++] = (zend_mm_bitset)-1;

}

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* set bits from "0" to "end" */

tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

bitset[pos] |= tmp;

} else {

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* set bits from "bit" to "end" */

tmp = (zend_mm_bitset)-1 << bit;

tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

bitset[pos] |= tmp;

}

}

}

static zend_always_inline void zend_mm_bitset_reset_range(zend_mm_bitset *bitset, int start, int len)

{

if (len == 1) {

zend_mm_bitset_reset_bit(bitset, start);

} else {

int pos = start / ZEND_MM_BITSET_LEN;

int end = (start + len - 1) / ZEND_MM_BITSET_LEN;

int bit = start & (ZEND_MM_BITSET_LEN - 1);

zend_mm_bitset tmp;

if (pos != end) {

/* reset bits from "bit" to ZEND_MM_BITSET_LEN-1 */

tmp = ~((Z_UL(1) << bit) - 1);

bitset[pos++] &= ~tmp;

while (pos != end) {

/* set all bits */

bitset[pos++] = 0;

}

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* reset bits from "0" to "end" */

tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

bitset[pos] &= ~tmp;

} else {

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* reset bits from "bit" to "end" */

tmp = (zend_mm_bitset)-1 << bit;

tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

bitset[pos] &= ~tmp;

}

}

}

static zend_always_inline int zend_mm_bitset_is_free_range(zend_mm_bitset *bitset, int start, int len)

{

if (len == 1) {

return !zend_mm_bitset_is_set(bitset, start);

} else {

int pos = start / ZEND_MM_BITSET_LEN;

int end = (start + len - 1) / ZEND_MM_BITSET_LEN;

int bit = start & (ZEND_MM_BITSET_LEN - 1);

zend_mm_bitset tmp;

if (pos != end) {

/* set bits from "bit" to ZEND_MM_BITSET_LEN-1 */

tmp = (zend_mm_bitset)-1 << bit;

if ((bitset[pos++] & tmp) != 0) {

return 0;

}

while (pos != end) {

/* set all bits */

if (bitset[pos++] != 0) {

return 0;

}

}

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* set bits from "0" to "end" */

tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

return (bitset[pos] & tmp) == 0;

} else {

end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);

/* set bits from "bit" to "end" */

tmp = (zend_mm_bitset)-1 << bit;

tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);

return (bitset[pos] & tmp) == 0;

}

}

}

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

/* Chunks */

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

static void *zend_mm_chunk_alloc_int(size_t size, size_t alignment)

{

void *ptr = zend_mm_mmap(size);

if (ptr == NULL) {

return NULL;

} else if (ZEND_MM_ALIGNED_OFFSET(ptr, alignment) == 0) {

#ifdef MADV_HUGEPAGE

if (zend_mm_use_huge_pages) {

madvise(ptr, size, MADV_HUGEPAGE);

}

#endif

return ptr;

} else {

size_t offset;

/* chunk has to be aligned */

zend_mm_munmap(ptr, size);

ptr = zend_mm_mmap(size + alignment - REAL_PAGE_SIZE);

#ifdef _WIN32

offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);

zend_mm_munmap(ptr, size + alignment - REAL_PAGE_SIZE);

ptr = zend_mm_mmap_fixed((void*)((char*)ptr + (alignment - offset)), size);

offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);

if (offset != 0) {

zend_mm_munmap(ptr, size);

return NULL;

}

return ptr;

#else

offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);

if (offset != 0) {

offset = alignment - offset;

zend_mm_munmap(ptr, offset);

ptr = (char*)ptr + offset;

alignment -= offset;

}

if (alignment > REAL_PAGE_SIZE) {

zend_mm_munmap((char*)ptr + size, alignment - REAL_PAGE_SIZE);

}

# ifdef MADV_HUGEPAGE

if (zend_mm_use_huge_pages) {

madvise(ptr, size, MADV_HUGEPAGE);

}

# endif

#endif

return ptr;

}

}

static void *zend_mm_chunk_alloc(zend_mm_heap *heap, size_t size, size_t alignment)

{

#if ZEND_MM_STORAGE

if (UNEXPECTED(heap->storage)) {

void *ptr = heap->storage->handlers.chunk_alloc(heap->storage, size, alignment);

ZEND_ASSERT(((zend_uintptr_t)((char*)ptr + (alignment-1)) & (alignment-1)) == (zend_uintptr_t)ptr);

return ptr;

}

#endif

return zend_mm_chunk_alloc_int(size, alignment);

}

static void zend_mm_chunk_free(zend_mm_heap *heap, void *addr, size_t size)

{

#if ZEND_MM_STORAGE

if (UNEXPECTED(heap->storage)) {

heap->storage->handlers.chunk_free(heap->storage, addr, size);

return;

}

#endif

zend_mm_munmap(addr, size);

}

static int zend_mm_chunk_truncate(zend_mm_heap *heap, void *addr, size_t old_size, size_t new_size)

{

#if ZEND_MM_STORAGE

if (UNEXPECTED(heap->storage)) {

if (heap->storage->handlers.chunk_truncate) {

return heap->storage->handlers.chunk_truncate(heap->storage, addr, old_size, new_size);

} else {

return 0;

}

}

#endif

#ifndef _WIN32

zend_mm_munmap((char*)addr + new_size, old_size - new_size);

return 1;

#else

return 0;

#endif

}

static int zend_mm_chunk_extend(zend_mm_heap *heap, void *addr, size_t old_size, size_t new_size)

{

#if ZEND_MM_STORAGE

if (UNEXPECTED(heap->storage)) {

if (heap->storage->handlers.chunk_extend) {

return heap->storage->handlers.chunk_extend(heap->storage, addr, old_size, new_size);

} else {

return 0;

}

}

#endif

#ifdef HAVE_MREMAP

/* We don't use MREMAP_MAYMOVE due to alignment requirements. */

void *ptr = mremap(addr, old_size, new_size, 0);

if (ptr == MAP_FAILED) {

return 0;

}

/* Sanity check: The mapping shouldn't have moved. */

ZEND_ASSERT(ptr == addr);

return 1;

#elif !defined(_WIN32)

return (zend_mm_mmap_fixed((char*)addr + old_size, new_size - old_size) != NULL);

#else

return 0;

#endif

}

static zend_always_inline void zend_mm_chunk_init(zend_mm_heap *heap, zend_mm_chunk *chunk)

{

chunk->heap = heap;

chunk->next = heap->main_chunk;

chunk->prev = heap->main_chunk->prev;

chunk->prev->next = chunk;

chunk->next->prev = chunk;

/* mark first pages as allocated */

chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;

chunk->free_tail = ZEND_MM_FIRST_PAGE;

/* the younger chunks have bigger number */

chunk->num = chunk->prev->num + 1;

/* mark first pages as allocated */

chunk->free_map[0] = (1L << ZEND_MM_FIRST_PAGE) - 1;

chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);

}

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

/* Huge Runs (forward) */

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

static size_t zend_mm_get_huge_block_size(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

static void *zend_mm_alloc_huge(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

static void zend_mm_free_huge(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

#if ZEND_DEBUG

static void zend_mm_change_huge_block_size(zend_mm_heap *heap, void *ptr, size_t size, size_t dbg_size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

#else

static void zend_mm_change_huge_block_size(zend_mm_heap *heap, void *ptr, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);

#endif

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

/* Large Runs */

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

#if ZEND_DEBUG

static void *zend_mm_alloc_pages(zend_mm_heap *heap, uint32_t pages_count, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)

#else

static void *zend_mm_alloc_pages(zend_mm_heap *heap, uint32_t pages_count ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)

#endif

{

zend_mm_chunk *chunk = heap->main_chunk;

uint32_t page_num, len;

int steps = 0;

while (1) {

if (UNEXPECTED(chunk->free_pages < pages_count)) {

goto not_found;

#if 0

} else if (UNEXPECTED(chunk->free_pages + chunk->free_tail == ZEND_MM_PAGES)) {

if (UNEXPECTED(ZEND_MM_PAGES - chunk->free_tail < pages_count)) {

goto not_found;

} else {

page_num = chunk->free_tail;

goto found;

}

} else if (0) {

/* First-Fit Search */

int free_tail = chunk->free_tail;

zend_mm_bitset *bitset = chunk->free_map;

zend_mm_bitset tmp = *(bitset++);

int i = 0;

while (1) {

/* skip allocated blocks */

while (tmp == (zend_mm_bitset)-1) {

i += ZEND_MM_BITSET_LEN;

if (i == ZEND_MM_PAGES) {

goto not_found;

}

tmp = *(bitset++);

}

/* find first 0 bit */

page_num = i + zend_mm_bitset_nts(tmp);

/* reset bits from 0 to "bit" */

tmp &= tmp + 1;

/* skip free blocks */

while (tmp == 0) {

i += ZEND_MM_BITSET_LEN;

len = i - page_num;

if (len >= pages_count) {

goto found;

} else if (i >= free_tail) {

goto not_found;

}

tmp = *(bitset++);

}

/* find first 1 bit */

len = (i + zend_ulong_ntz(tmp)) - page_num;

if (len >= pages_count) {

goto found;

}

/* set bits from 0 to "bit" */

tmp |= tmp - 1;

}

#endif

} else {

/* Best-Fit Search */

int best = -1;

uint32_t best_len = ZEND_MM_PAGES;

uint32_t free_tail = chunk->free_tail;

zend_mm_bitset *bitset = chunk->free_map;

zend_mm_bitset tmp = *(bitset++);

uint32_t i = 0;

while (1) {

/* skip allocated blocks */

while (tmp == (zend_mm_bitset)-1) {

i += ZEND_MM_BITSET_LEN;

if (i == ZEND_MM_PAGES) {

if (best > 0) {

page_num = best;

goto found;

} else {

goto not_found;

}

}

tmp = *(bitset++);

}

/* find first 0 bit */

page_num = i + zend_mm_bitset_nts(tmp);

/* reset bits from 0 to "bit" */

tmp &= tmp + 1;

/* skip free blocks */

while (tmp == 0) {

i += ZEND_MM_BITSET_LEN;

if (i >= free_tail || i == ZEND_MM_PAGES) {

len = ZEND_MM_PAGES - page_num;

if (len >= pages_count && len < best_len) {

chunk->free_tail = page_num + pages_count;

goto found;

} else {

/* set accurate value */

chunk->free_tail = page_num;

if (best > 0) {

page_num = best;

goto found;

} else {

goto not_found;

}

}

}

tmp = *(bitset++);

}

/* find first 1 bit */

len = i + zend_ulong_ntz(tmp) - page_num;

if (len >= pages_count) {

if (len == pages_count) {

goto found;

} else if (len < best_len) {

best_len = len;

best = page_num;

}

}

/* set bits from 0 to "bit" */

tmp |= tmp - 1;

}

}

not_found:

if (chunk->next == heap->main_chunk) {

get_chunk:

if (heap->cached_chunks) {

heap->cached_chunks_count--;

chunk = heap->cached_chunks;

heap->cached_chunks = chunk->next;

} else {

#if ZEND_MM_LIMIT

if (UNEXPECTED(ZEND_MM_CHUNK_SIZE > heap->limit - heap->real_size)) {

if (zend_mm_gc(heap)) {

goto get_chunk;

} else if (heap->overflow == 0) {

#if ZEND_DEBUG

zend_mm_safe_error(heap, "Allowed memory size of %zu bytes exhausted at %s:%d (tried to allocate %zu bytes)", heap->limit, __zend_filename, __zend_lineno, size);

#else

zend_mm_safe_error(heap, "Allowed memory size of %zu bytes exhausted (tried to allocate %zu bytes)", heap->limit, ZEND_MM_PAGE_SIZE * pages_count);

#endif

return NULL;

}

}

#endif

chunk = (zend_mm_chunk*)zend_mm_chunk_alloc(heap, ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);

if (UNEXPECTED(chunk == NULL)) {

/* insufficient memory */

if (zend_mm_gc(heap) &&

(chunk = (zend_mm_chunk*)zend_mm_chunk_alloc(heap, ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE)) != NULL) {

/* pass */

} else {

#if !ZEND_MM_LIMIT

zend_mm_safe_error(heap, "Out of memory");

#elif ZEND_DEBUG

zend_mm_safe_error(heap, "Out of memory (allocated %zu) at %s:%d (tried to allocate %zu bytes)", heap->real_size, __zend_filename, __zend_lineno, size);

#else

zend_mm_safe_error(heap, "Out of memory (allocated %zu) (tried to allocate %zu bytes)", heap->real_size, ZEND_MM_PAGE_SIZE * pages_count);

#endif

return NULL;

}

}

#if ZEND_MM_STAT

do {

size_t size = heap->real_size + ZEND_MM_CHUNK_SIZE;

size_t peak = MAX(heap->real_peak, size);

heap->real_size = size;

heap->real_peak = peak;

} while (0);

#elif ZEND_MM_LIMIT

heap->real_size += ZEND_MM_CHUNK_SIZE;

#endif

}

heap->chunks_count++;

if (heap->chunks_count > heap->peak_chunks_count) {

heap->peak_chunks_count = heap->chunks_count;

}

zend_mm_chunk_init(heap, chunk);

page_num = ZEND_MM_FIRST_PAGE;

len = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;

goto found;