1/*
2   +----------------------------------------------------------------------+
3   | Zend Engine                                                          |
4   +----------------------------------------------------------------------+
5   | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) |
6   +----------------------------------------------------------------------+
7   | This source file is subject to version 2.00 of the Zend license,     |
8   | that is bundled with this package in the file LICENSE, and is        |
9   | available through the world-wide-web at the following url:           |
10   | http://www.zend.com/license/2_00.txt.                                |
11   | If you did not receive a copy of the Zend license and are unable to  |
12   | obtain it through the world-wide-web, please send a note to          |
13   | license@zend.com so we can mail you a copy immediately.              |
14   +----------------------------------------------------------------------+
15   | Authors: Andi Gutmans <andi@zend.com>                                |
16   |          Zeev Suraski <zeev@zend.com>                                |
17   |          Dmitry Stogov <dmitry@zend.com>                             |
18   +----------------------------------------------------------------------+
19*/
20
21/* $Id$ */
22
23/*
24 * zend_alloc is designed to be a modern CPU cache friendly memory manager
25 * for PHP. Most ideas are taken from jemalloc and tcmalloc implementations.
26 *
27 * All allocations are split into 3 categories:
28 *
29 * Huge  - the size is greater than CHUNK size (~2M by default), allocation is
30 *         performed using mmap(). The result is aligned on 2M boundary.
31 *
32 * Large - a number of 4096K pages inside a CHUNK. Large blocks
33 *         are always alligned on page boundary.
34 *
35 * Small - less than 3/4 of page size. Small sizes are rounded up to nearest
36 *         greater predefined small size (there are 30 predefined sizes:
37 *         8, 16, 24, 32, ... 3072). Small blocks are allocated from
38 *         RUNs. Each RUN is allocated as a single or few following pages.
39 *         Allocation inside RUNs implemented using linked list of free
40 *         elements. The result is aligned to 8 bytes.
41 *
42 * zend_alloc allocates memory from OS by CHUNKs, these CHUNKs and huge memory
43 * blocks are always aligned to CHUNK boundary. So it's very easy to determine
44 * the CHUNK owning the certain pointer. Regular CHUNKs reserve a single
45 * page at start for special purpose. It contains bitset of free pages,
46 * few bitset for available runs of predefined small sizes, map of pages that
47 * keeps information about usage of each page in this CHUNK, etc.
48 *
49 * zend_alloc provides familiar emalloc/efree/erealloc API, but in addition it
50 * provides specialized and optimized routines to allocate blocks of predefined
51 * sizes (e.g. emalloc_2(), emallc_4(), ..., emalloc_large(), etc)
52 * The library uses C preprocessor tricks that substitute calls to emalloc()
53 * with more specialized routines when the requested size is known.
54 */
55
56#include "zend.h"
57#include "zend_alloc.h"
58#include "zend_globals.h"
59#include "zend_operators.h"
60#include "zend_multiply.h"
61
62#ifdef HAVE_SIGNAL_H
63# include <signal.h>
64#endif
65#ifdef HAVE_UNISTD_H
66# include <unistd.h>
67#endif
68
69#ifdef ZEND_WIN32
70# include <wincrypt.h>
71# include <process.h>
72#endif
73
74#include <stdio.h>
75#include <stdlib.h>
76#include <string.h>
77
78#include <sys/types.h>
79#include <sys/stat.h>
80#if HAVE_LIMITS_H
81#include <limits.h>
82#endif
83#include <fcntl.h>
84#include <errno.h>
85
86#ifndef _WIN32
87# ifdef HAVE_MREMAP
88#  ifndef _GNU_SOURCE
89#   define _GNU_SOURCE
90#  endif
91#  ifndef __USE_GNU
92#   define __USE_GNU
93#  endif
94# endif
95# include <sys/mman.h>
96# ifndef MAP_ANON
97#  ifdef MAP_ANONYMOUS
98#   define MAP_ANON MAP_ANONYMOUS
99#  endif
100# endif
101# ifndef MREMAP_MAYMOVE
102#  define MREMAP_MAYMOVE 0
103# endif
104# ifndef MAP_FAILED
105#  define MAP_FAILED ((void*)-1)
106# endif
107# ifndef MAP_POPULATE
108#  define MAP_POPULATE 0
109#endif
110#endif
111
112#ifndef ZEND_MM_STAT
113# define ZEND_MM_STAT 1    /* track current and peak memory usage            */
114#endif
115#ifndef ZEND_MM_LIMIT
116# define ZEND_MM_LIMIT 1   /* support for user-defined memory limit          */
117#endif
118#ifndef ZEND_MM_CUSTOM
119# define ZEND_MM_CUSTOM 1  /* support for custom memory allocator            */
120                           /* USE_ZEND_ALLOC=0 may switch to system malloc() */
121#endif
122#ifndef ZEND_MM_STORAGE
123# define ZEND_MM_STORAGE 1 /* support for custom memory storage              */
124#endif
125#ifndef ZEND_MM_ERROR
126# define ZEND_MM_ERROR 1   /* report system errors                           */
127#endif
128
129#ifndef ZEND_MM_CHECK
130# define ZEND_MM_CHECK(condition, message)  do { \
131        if (UNEXPECTED(!(condition))) { \
132            zend_mm_panic(message); \
133        } \
134    } while (0)
135#endif
136
137typedef uint32_t   zend_mm_page_info; /* 4-byte integer */
138typedef zend_ulong zend_mm_bitset;    /* 4-byte or 8-byte integer */
139
140#define ZEND_MM_ALIGNED_OFFSET(size, alignment) \
141    (((size_t)(size)) & ((alignment) - 1))
142#define ZEND_MM_ALIGNED_BASE(size, alignment) \
143    (((size_t)(size)) & ~((alignment) - 1))
144#define ZEND_MM_ALIGNED_SIZE_EX(size, alignment) \
145    (((size_t)(size) + ((alignment) - 1)) & ~((alignment) - 1))
146#define ZEND_MM_SIZE_TO_NUM(size, alignment) \
147    (((size_t)(size) + ((alignment) - 1)) / (alignment))
148
149#define ZEND_MM_BITSET_LEN      (sizeof(zend_mm_bitset) * 8)       /* 32 or 64 */
150#define ZEND_MM_PAGE_MAP_LEN    (ZEND_MM_PAGES / ZEND_MM_BITSET_LEN) /* 16 or 8 */
151
152typedef zend_mm_bitset zend_mm_page_map[ZEND_MM_PAGE_MAP_LEN];     /* 64B */
153
154#define ZEND_MM_IS_FRUN                  0x00000000
155#define ZEND_MM_IS_LRUN                  0x40000000
156#define ZEND_MM_IS_SRUN                  0x80000000
157
158#define ZEND_MM_LRUN_PAGES_MASK          0x000003ff
159#define ZEND_MM_LRUN_PAGES_OFFSET        0
160
161#define ZEND_MM_SRUN_BIN_NUM_MASK        0x0000001f
162#define ZEND_MM_SRUN_BIN_NUM_OFFSET      0
163
164#define ZEND_MM_LRUN_PAGES(info)         (((info) & ZEND_MM_LRUN_PAGES_MASK) >> ZEND_MM_LRUN_PAGES_OFFSET)
165#define ZEND_MM_SRUN_BIN_NUM(info)       (((info) & ZEND_MM_SRUN_BIN_NUM_MASK) >> ZEND_MM_SRUN_BIN_NUM_OFFSET)
166
167#define ZEND_MM_FRUN()                   ZEND_MM_IS_FRUN
168#define ZEND_MM_LRUN(count)              (ZEND_MM_IS_LRUN | ((count) << ZEND_MM_LRUN_PAGES_OFFSET))
169#define ZEND_MM_SRUN(bin_num)            (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET))
170
171#define ZEND_MM_BINS 30
172
173typedef struct  _zend_mm_page      zend_mm_page;
174typedef struct  _zend_mm_bin       zend_mm_bin;
175typedef struct  _zend_mm_free_slot zend_mm_free_slot;
176typedef struct  _zend_mm_chunk     zend_mm_chunk;
177typedef struct  _zend_mm_huge_list zend_mm_huge_list;
178
179#ifdef _WIN64
180# define PTR_FMT "0x%0.16I64x"
181#elif SIZEOF_LONG == 8
182# define PTR_FMT "0x%0.16lx"
183#else
184# define PTR_FMT "0x%0.8lx"
185#endif
186
187/*
188 * Memory is retrived from OS by chunks of fixed size 2MB.
189 * Inside chunk it's managed by pages of fixed size 4096B.
190 * So each chunk consists from 512 pages.
191 * The first page of each chunk is reseved for chunk header.
192 * It contains service information about all pages.
193 *
194 * free_pages - current number of free pages in this chunk
195 *
196 * free_tail  - number of continuous free pages at the end of chunk
197 *
198 * free_map   - bitset (a bit for each page). The bit is set if the corresponding
199 *              page is allocated. Allocator for "lage sizes" may easily find a
200 *              free page (or a continuous number of pages) searching for zero
201 *              bits.
202 *
203 * map        - contains service information for each page. (32-bits for each
204 *              page).
205 *    usage:
206 *              (2 bits)
207 *              FRUN - free page,
208 *              LRUN - first page of "large" allocation
209 *              SRUN - first page of a bin used for "small" allocation
210 *
211 *    lrun_pages:
212 *              (10 bits) number of allocated pages
213 *
214 *    srun_bin_num:
215 *              (5 bits) bin number (e.g. 0 for sizes 0-2, 1 for 3-4,
216 *               2 for 5-8, 3 for 9-16 etc) see zend_alloc_sizes.h
217 */
218
219struct _zend_mm_heap {
220#if ZEND_MM_CUSTOM
221    int                use_custom_heap;
222#endif
223#if ZEND_MM_STORAGE
224    zend_mm_storage   *storage;
225#endif
226#if ZEND_MM_STAT
227    size_t             size;                    /* current memory usage */
228    size_t             peak;                    /* peak memory usage */
229#endif
230    zend_mm_free_slot *free_slot[ZEND_MM_BINS]; /* free lists for small sizes */
231#if ZEND_MM_STAT || ZEND_MM_LIMIT
232    size_t             real_size;               /* current size of allocated pages */
233#endif
234#if ZEND_MM_STAT
235    size_t             real_peak;               /* peak size of allocated pages */
236#endif
237#if ZEND_MM_LIMIT
238    size_t             limit;                   /* memory limit */
239    int                overflow;                /* memory overflow flag */
240#endif
241
242    zend_mm_huge_list *huge_list;               /* list of huge allocated blocks */
243
244    zend_mm_chunk     *main_chunk;
245    zend_mm_chunk     *cached_chunks;           /* list of unused chunks */
246    int                chunks_count;            /* number of alocated chunks */
247    int                peak_chunks_count;       /* peak number of allocated chunks for current request */
248    int                cached_chunks_count;     /* number of cached chunks */
249    double             avg_chunks_count;        /* average number of chunks allocated per request */
250#if ZEND_MM_CUSTOM
251    void              *(*_malloc)(size_t);
252    void               (*_free)(void*);
253    void              *(*_realloc)(void*, size_t);
254#endif
255};
256
257struct _zend_mm_chunk {
258    zend_mm_heap      *heap;
259    zend_mm_chunk     *next;
260    zend_mm_chunk     *prev;
261    int                free_pages;              /* number of free pages */
262    int                free_tail;               /* number of free pages at the end of chunk */
263    int                num;
264    char               reserve[64 - (sizeof(void*) * 3 + sizeof(int) * 3)];
265    zend_mm_heap       heap_slot;               /* used only in main chunk */
266    zend_mm_page_map   free_map;                /* 512 bits or 64 bytes */
267    zend_mm_page_info  map[ZEND_MM_PAGES];      /* 2 KB = 512 * 4 */
268};
269
270struct _zend_mm_page {
271    char               bytes[ZEND_MM_PAGE_SIZE];
272};
273
274/*
275 * bin - is one or few continuous pages (up to 8) used for alocation of
276 * a particular "small size".
277 */
278struct _zend_mm_bin {
279    char               bytes[ZEND_MM_PAGE_SIZE * 8];
280};
281
282#if ZEND_DEBUG
283typedef struct _zend_mm_debug_info {
284    size_t             size;
285    const char        *filename;
286    const char        *orig_filename;
287    uint               lineno;
288    uint               orig_lineno;
289} zend_mm_debug_info;
290#endif
291
292struct _zend_mm_free_slot {
293    zend_mm_free_slot *next_free_slot;
294};
295
296struct _zend_mm_huge_list {
297    void              *ptr;
298    size_t             size;
299    zend_mm_huge_list *next;
300#if ZEND_DEBUG
301    zend_mm_debug_info dbg;
302#endif
303};
304
305#define ZEND_MM_PAGE_ADDR(chunk, page_num) \
306    ((void*)(((zend_mm_page*)(chunk)) + (page_num)))
307
308#define _BIN_DATA_SIZE(num, size, elements, pages, x, y) size,
309static const unsigned int bin_data_size[] = {
310  ZEND_MM_BINS_INFO(_BIN_DATA_SIZE, x, y)
311};
312
313#define _BIN_DATA_ELEMENTS(num, size, elements, pages, x, y) elements,
314static const int bin_elements[] = {
315  ZEND_MM_BINS_INFO(_BIN_DATA_ELEMENTS, x, y)
316};
317
318#define _BIN_DATA_PAGES(num, size, elements, pages, x, y) pages,
319static const int bin_pages[] = {
320  ZEND_MM_BINS_INFO(_BIN_DATA_PAGES, x, y)
321};
322
323#if ZEND_DEBUG
324void zend_debug_alloc_output(char *format, ...)
325{
326    char output_buf[256];
327    va_list args;
328
329    va_start(args, format);
330    vsprintf(output_buf, format, args);
331    va_end(args);
332
333#ifdef ZEND_WIN32
334    OutputDebugString(output_buf);
335#else
336    fprintf(stderr, "%s", output_buf);
337#endif
338}
339#endif
340
341static ZEND_NORETURN void zend_mm_panic(const char *message)
342{
343    fprintf(stderr, "%s\n", message);
344/* See http://support.microsoft.com/kb/190351 */
345#ifdef PHP_WIN32
346    fflush(stderr);
347#endif
348#if ZEND_DEBUG && defined(HAVE_KILL) && defined(HAVE_GETPID)
349    kill(getpid(), SIGSEGV);
350#endif
351    exit(1);
352}
353
354static ZEND_NORETURN void zend_mm_safe_error(zend_mm_heap *heap,
355    const char *format,
356    size_t limit,
357#if ZEND_DEBUG
358    const char *filename,
359    uint lineno,
360#endif
361    size_t size)
362{
363    TSRMLS_FETCH();
364
365    heap->overflow = 1;
366    zend_try {
367        zend_error_noreturn(E_ERROR,
368            format,
369            limit,
370#if ZEND_DEBUG
371            filename,
372            lineno,
373#endif
374            size);
375    } zend_catch {
376    }  zend_end_try();
377    heap->overflow = 0;
378    zend_bailout();
379    exit(1);
380}
381
382#ifdef _WIN32
383void
384stderr_last_error(char *msg)
385{
386    LPSTR buf = NULL;
387    DWORD err = GetLastError();
388
389    if (!FormatMessage(
390            FORMAT_MESSAGE_ALLOCATE_BUFFER |
391            FORMAT_MESSAGE_FROM_SYSTEM |
392            FORMAT_MESSAGE_IGNORE_INSERTS,
393            NULL,
394            err,
395            MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
396            (LPSTR)&buf,
397        0, NULL)) {
398        fprintf(stderr, "\n%s: [0x%08x]\n", msg, err);
399    }
400    else {
401        fprintf(stderr, "\n%s: [0x%08x] %s\n", msg, err, buf);
402    }
403}
404#endif
405
406/*****************/
407/* OS Allocation */
408/*****************/
409
410static void *zend_mm_mmap_fixed(void *addr, size_t size)
411{
412#ifdef _WIN32
413    return VirtualAlloc(addr, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
414#else
415    /* MAP_FIXED leads to discarding of the old mapping, so it can't be used. */
416    void *ptr = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON /*| MAP_POPULATE | MAP_HUGETLB*/, -1, 0);
417
418    if (ptr == MAP_FAILED) {
419#if ZEND_MM_ERROR
420        fprintf(stderr, "\nmmap() failed: [%d] %s\n", errno, strerror(errno));
421#endif
422        return NULL;
423    } else if (ptr != addr) {
424        if (munmap(ptr, size) != 0) {
425#if ZEND_MM_ERROR
426            fprintf(stderr, "\nmunmap() failed: [%d] %s\n", errno, strerror(errno));
427#endif
428        }
429        return NULL;
430    }
431    return ptr;
432#endif
433}
434
435static void *zend_mm_mmap(size_t size)
436{
437#ifdef _WIN32
438    void *ptr = VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
439
440    if (ptr == NULL) {
441#if ZEND_MM_ERROR
442        stderr_last_error("VirtualAlloc() failed");
443#endif
444        return NULL;
445    }
446    return ptr;
447#else
448    void *ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON /*| MAP_POPULATE | MAP_HUGETLB*/, -1, 0);
449
450    if (ptr == MAP_FAILED) {
451#if ZEND_MM_ERROR
452        fprintf(stderr, "\nmmap() failed: [%d] %s\n", errno, strerror(errno));
453#endif
454        return NULL;
455    }
456    return ptr;
457#endif
458}
459
460static void zend_mm_munmap(void *addr, size_t size)
461{
462#ifdef _WIN32
463    if (VirtualFree(addr, 0, MEM_RELEASE) == 0) {
464#if ZEND_MM_ERROR
465        stderr_last_error("VirtualFree() failed");
466#endif
467    }
468#else
469    if (munmap(addr, size) != 0) {
470#if ZEND_MM_ERROR
471        fprintf(stderr, "\nmunmap() failed: [%d] %s\n", errno, strerror(errno));
472#endif
473    }
474#endif
475}
476
477/***********/
478/* Bitmask */
479/***********/
480
481/* number of trailing set (1) bits */
482static zend_always_inline int zend_mm_bitset_nts(zend_mm_bitset bitset)
483{
484#if defined(__GNUC__)
485# if SIZEOF_ZEND_LONG == SIZEOF_LONG
486    return __builtin_ctzl(~bitset);
487# else
488    return __builtin_ctzll(~bitset);
489# endif
490#elif defined(_WIN32)
491    unsigned long index;
492
493#if defined(_WIN64)
494    if (!BitScanForward64(&index, ~bitset)) {
495#else
496    if (!BitScanForward(&index, ~bitset)) {
497#endif
498        /* undefined behavior */
499        return 32;
500    }
501
502    return (int)index;
503#else
504    int n;
505
506    if (bitset == (zend_mm_bitset)-1) return ZEND_MM_BITSET_LEN;
507
508    n = 0;
509#if SIZEOF_ZEND_LONG == 8
510    if (sizeof(zend_mm_bitset) == 8) {
511        if ((bitset & 0xffffffff) == 0xffffffff) {n += 32; bitset = bitset >> Z_UL(32);}
512    }
513#endif
514    if ((bitset & 0x0000ffff) == 0x0000ffff) {n += 16; bitset = bitset >> 16;}
515    if ((bitset & 0x000000ff) == 0x000000ff) {n +=  8; bitset = bitset >>  8;}
516    if ((bitset & 0x0000000f) == 0x0000000f) {n +=  4; bitset = bitset >>  4;}
517    if ((bitset & 0x00000003) == 0x00000003) {n +=  2; bitset = bitset >>  2;}
518    return n + (bitset & 1);
519#endif
520}
521
522/* number of trailing zero bits (0x01 -> 1; 0x40 -> 6; 0x00 -> LEN) */
523static zend_always_inline int zend_mm_bitset_ntz(zend_mm_bitset bitset)
524{
525#if defined(__GNUC__)
526# if SIZEOF_ZEND_LONG == SIZEOF_LONG
527    return __builtin_ctzl(bitset);
528# else
529    return __builtin_ctzll(bitset);
530# endif
531#elif defined(_WIN32)
532    unsigned long index;
533
534#if defined(_WIN64)
535    if (!BitScanForward64(&index, bitset)) {
536#else
537    if (!BitScanForward(&index, bitset)) {
538#endif
539        /* undefined behavior */
540        return 32;
541    }
542
543    return (int)index;
544#else
545    int n;
546
547    if (bitset == (zend_mm_bitset)0) return ZEND_MM_BITSET_LEN;
548
549    n = 1;
550#if SIZEOF_ZEND_LONG == 8
551    if (sizeof(zend_mm_bitset) == 8) {
552        if ((bitset & 0xffffffff) == 0) {n += 32; bitset = bitset >> Z_UL(32);}
553    }
554#endif
555    if ((bitset & 0x0000ffff) == 0) {n += 16; bitset = bitset >> 16;}
556    if ((bitset & 0x000000ff) == 0) {n +=  8; bitset = bitset >>  8;}
557    if ((bitset & 0x0000000f) == 0) {n +=  4; bitset = bitset >>  4;}
558    if ((bitset & 0x00000003) == 0) {n +=  2; bitset = bitset >>  2;}
559    return n - (bitset & 1);
560#endif
561}
562
563static zend_always_inline int zend_mm_bitset_find_zero(zend_mm_bitset *bitset, int size)
564{
565    int i = 0;
566
567    do {
568        zend_mm_bitset tmp = bitset[i];
569        if (tmp != (zend_mm_bitset)-1) {
570            return i * ZEND_MM_BITSET_LEN + zend_mm_bitset_nts(tmp);
571        }
572        i++;
573    } while (i < size);
574    return -1;
575}
576
577static zend_always_inline int zend_mm_bitset_find_one(zend_mm_bitset *bitset, int size)
578{
579    int i = 0;
580
581    do {
582        zend_mm_bitset tmp = bitset[i];
583        if (tmp != 0) {
584            return i * ZEND_MM_BITSET_LEN + zend_mm_bitset_ntz(tmp);
585        }
586        i++;
587    } while (i < size);
588    return -1;
589}
590
591static zend_always_inline int zend_mm_bitset_find_zero_and_set(zend_mm_bitset *bitset, int size)
592{
593    int i = 0;
594
595    do {
596        zend_mm_bitset tmp = bitset[i];
597        if (tmp != (zend_mm_bitset)-1) {
598            int n = zend_mm_bitset_nts(tmp);
599            bitset[i] |= Z_UL(1) << n;
600            return i * ZEND_MM_BITSET_LEN + n;
601        }
602        i++;
603    } while (i < size);
604    return -1;
605}
606
607static zend_always_inline int zend_mm_bitset_is_set(zend_mm_bitset *bitset, int bit)
608{
609    return (bitset[bit / ZEND_MM_BITSET_LEN] & (Z_L(1) << (bit & (ZEND_MM_BITSET_LEN-1)))) != 0;
610}
611
612static zend_always_inline void zend_mm_bitset_set_bit(zend_mm_bitset *bitset, int bit)
613{
614    bitset[bit / ZEND_MM_BITSET_LEN] |= (Z_L(1) << (bit & (ZEND_MM_BITSET_LEN-1)));
615}
616
617static zend_always_inline void zend_mm_bitset_reset_bit(zend_mm_bitset *bitset, int bit)
618{
619    bitset[bit / ZEND_MM_BITSET_LEN] &= ~(Z_L(1) << (bit & (ZEND_MM_BITSET_LEN-1)));
620}
621
622static zend_always_inline void zend_mm_bitset_set_range(zend_mm_bitset *bitset, int start, int len)
623{
624    if (len == 1) {
625        zend_mm_bitset_set_bit(bitset, start);
626    } else {
627        int pos = start / ZEND_MM_BITSET_LEN;
628        int end = (start + len - 1) / ZEND_MM_BITSET_LEN;
629        int bit = start & (ZEND_MM_BITSET_LEN - 1);
630        zend_mm_bitset tmp;
631
632        if (pos != end) {
633            /* set bits from "bit" to ZEND_MM_BITSET_LEN-1 */
634            tmp = (zend_mm_bitset)-1 << bit;
635            bitset[pos++] |= tmp;
636            while (pos != end) {
637                /* set all bits */
638                bitset[pos++] = (zend_mm_bitset)-1;
639            }
640            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
641            /* set bits from "0" to "end" */
642            tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
643            bitset[pos] |= tmp;
644        } else {
645            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
646            /* set bits from "bit" to "end" */
647            tmp = (zend_mm_bitset)-1 << bit;
648            tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
649            bitset[pos] |= tmp;
650        }
651    }
652}
653
654static zend_always_inline void zend_mm_bitset_reset_range(zend_mm_bitset *bitset, int start, int len)
655{
656    if (len == 1) {
657        zend_mm_bitset_reset_bit(bitset, start);
658    } else {
659        int pos = start / ZEND_MM_BITSET_LEN;
660        int end = (start + len - 1) / ZEND_MM_BITSET_LEN;
661        int bit = start & (ZEND_MM_BITSET_LEN - 1);
662        zend_mm_bitset tmp;
663
664        if (pos != end) {
665            /* reset bits from "bit" to ZEND_MM_BITSET_LEN-1 */
666            tmp = ~((Z_L(1) << bit) - 1);
667            bitset[pos++] &= ~tmp;
668            while (pos != end) {
669                /* set all bits */
670                bitset[pos++] = 0;
671            }
672            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
673            /* reset bits from "0" to "end" */
674            tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
675            bitset[pos] &= ~tmp;
676        } else {
677            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
678            /* reset bits from "bit" to "end" */
679            tmp = (zend_mm_bitset)-1 << bit;
680            tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
681            bitset[pos] &= ~tmp;
682        }
683    }
684}
685
686static zend_always_inline int zend_mm_bitset_is_free_range(zend_mm_bitset *bitset, int start, int len)
687{
688    if (len == 1) {
689        return !zend_mm_bitset_is_set(bitset, start);
690    } else {
691        int pos = start / ZEND_MM_BITSET_LEN;
692        int end = (start + len - 1) / ZEND_MM_BITSET_LEN;
693        int bit = start & (ZEND_MM_BITSET_LEN - 1);
694        zend_mm_bitset tmp;
695
696        if (pos != end) {
697            /* set bits from "bit" to ZEND_MM_BITSET_LEN-1 */
698            tmp = (zend_mm_bitset)-1 << bit;
699            if ((bitset[pos++] & tmp) != 0) {
700                return 0;
701            }
702            while (pos != end) {
703                /* set all bits */
704                if (bitset[pos++] != 0) {
705                    return 0;
706                }
707            }
708            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
709            /* set bits from "0" to "end" */
710            tmp = (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
711            return (bitset[pos] & tmp) == 0;
712        } else {
713            end = (start + len - 1) & (ZEND_MM_BITSET_LEN - 1);
714            /* set bits from "bit" to "end" */
715            tmp = (zend_mm_bitset)-1 << bit;
716            tmp &= (zend_mm_bitset)-1 >> ((ZEND_MM_BITSET_LEN - 1) - end);
717            return (bitset[pos] & tmp) == 0;
718        }
719    }
720}
721
722/**********/
723/* Chunks */
724/**********/
725
726static void *zend_mm_chunk_alloc_int(size_t size, size_t alignment)
727{
728    void *ptr = zend_mm_mmap(size);
729
730    if (ptr == NULL) {
731        return NULL;
732    } else if (ZEND_MM_ALIGNED_OFFSET(ptr, alignment) == 0) {
733#ifdef MADV_HUGEPAGE
734        madvise(ptr, size, MADV_HUGEPAGE);
735#endif
736        return ptr;
737    } else {
738        size_t offset;
739
740        /* chunk has to be aligned */
741        zend_mm_munmap(ptr, size);
742        ptr = zend_mm_mmap(size + alignment - ZEND_MM_PAGE_SIZE);
743#ifdef _WIN32
744        offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);
745        zend_mm_munmap(ptr, size + alignment - ZEND_MM_PAGE_SIZE);
746        ptr = zend_mm_mmap_fixed((void*)((char*)ptr + (alignment - offset)), size);
747        offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);
748        if (offset != 0) {
749            zend_mm_munmap(ptr, size);
750            return NULL;
751        }
752        return ptr;
753#else
754        offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);
755        if (offset != 0) {
756            offset = alignment - offset;
757            zend_mm_munmap(ptr, offset);
758            ptr = (char*)ptr + offset;
759        } else {
760            zend_mm_munmap((char*)ptr + size, alignment - ZEND_MM_PAGE_SIZE);
761        }
762# ifdef MADV_HUGEPAGE
763        madvise(ptr, size, MADV_HUGEPAGE);
764# endif
765#endif
766        return ptr;
767    }
768}
769
770static void *zend_mm_chunk_alloc(zend_mm_heap *heap, size_t size, size_t alignment)
771{
772#if ZEND_MM_STORAGE
773    if (UNEXPECTED(heap->storage)) {
774        void *ptr = heap->storage->chunk_alloc(heap->storage, size, alignment);
775        ZEND_ASSERT(((zend_uintptr_t)((char*)ptr + (alignment-1)) & (alignment-1)) == (zend_uintptr_t)ptr);
776        return ptr;
777    }
778#endif
779    return zend_mm_chunk_alloc_int(size, alignment);
780}
781
782static void zend_mm_chunk_free(zend_mm_heap *heap, void *addr, size_t size)
783{
784#if ZEND_MM_STORAGE
785    if (UNEXPECTED(heap->storage)) {
786        heap->storage->chunk_free(heap->storage, addr, size);
787        return;
788    }
789#endif
790    zend_mm_munmap(addr, size);
791}
792
793static void zend_mm_chunk_truncate(zend_mm_heap *heap, void *addr, size_t old_size, size_t new_size)
794{
795#if ZEND_MM_STORAGE
796    if (UNEXPECTED(heap->storage)) {
797        heap->storage->chunk_truncate(heap->storage, addr, old_size, new_size);
798        return;
799    }
800#endif
801    zend_mm_munmap((char*)addr + new_size, old_size - new_size);
802}
803
804static zend_always_inline void zend_mm_chunk_init(zend_mm_heap *heap, zend_mm_chunk *chunk)
805{
806    chunk->heap = heap;
807    chunk->next = heap->main_chunk;
808    chunk->prev = heap->main_chunk->prev;
809    chunk->prev->next = chunk;
810    chunk->next->prev = chunk;
811    /* mark first pages as allocated */
812    chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
813    chunk->free_tail = ZEND_MM_FIRST_PAGE;
814    /* the younger chunks have bigger number */
815    chunk->num = chunk->prev->num + 1;
816    /* mark first pages as allocated */
817    chunk->free_map[0] = (1L << ZEND_MM_FIRST_PAGE) - 1;
818    chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
819}
820
821/***********************/
822/* Huge Runs (forward) */
823/***********************/
824
825static size_t zend_mm_get_huge_block_size(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);
826static void *zend_mm_alloc_huge(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);
827static void zend_mm_free_huge(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC);
828
829#if ZEND_DEBUG
830static 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);
831#else
832static 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);
833#endif
834
835/**************/
836/* Large Runs */
837/**************/
838
839#if ZEND_DEBUG
840static void *zend_mm_alloc_pages(zend_mm_heap *heap, int pages_count, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
841#else
842static void *zend_mm_alloc_pages(zend_mm_heap *heap, int pages_count ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
843#endif
844{
845    zend_mm_chunk *chunk = heap->main_chunk;
846    int page_num, len;
847
848    while (1) {
849        if (UNEXPECTED(chunk->free_pages < pages_count)) {
850            goto not_found;
851#if 0
852        } else if (UNEXPECTED(chunk->free_pages + chunk->free_tail == ZEND_MM_PAGES)) {
853            if (UNEXPECTED(ZEND_MM_PAGES - chunk->free_tail < pages_count)) {
854                goto not_found;
855            } else {
856                page_num = chunk->free_tail;
857                goto found;
858            }
859        } else if (0) {
860            /* First-Fit Search */
861            int free_tail = chunk->free_tail;
862            zend_mm_bitset *bitset = chunk->free_map;
863            zend_mm_bitset tmp = *(bitset++);
864            int i = 0;
865
866            while (1) {
867                /* skip allocated blocks */
868                while (tmp == (zend_mm_bitset)-1) {
869                    i += ZEND_MM_BITSET_LEN;
870                    if (i == ZEND_MM_PAGES) {
871                        goto not_found;
872                    }
873                    tmp = *(bitset++);
874                }
875                /* find first 0 bit */
876                page_num = i + zend_mm_bitset_nts(tmp);
877                /* reset bits from 0 to "bit" */
878                tmp &= tmp + 1;
879                /* skip free blocks */
880                while (tmp == 0) {
881                    i += ZEND_MM_BITSET_LEN;
882                    len = i - page_num;
883                    if (len >= pages_count) {
884                        goto found;
885                    } else if (i >= free_tail) {
886                        goto not_found;
887                    }
888                    tmp = *(bitset++);
889                }
890                /* find first 1 bit */
891                len = (i + zend_mm_bitset_ntz(tmp)) - page_num;
892                if (len >= pages_count) {
893                    goto found;
894                }
895                /* set bits from 0 to "bit" */
896                tmp |= tmp - 1;
897            }
898#endif
899        } else {
900            /* Best-Fit Search */
901            int best = -1;
902            int best_len = ZEND_MM_PAGES;
903            int free_tail = chunk->free_tail;
904            zend_mm_bitset *bitset = chunk->free_map;
905            zend_mm_bitset tmp = *(bitset++);
906            int i = 0;
907
908            while (1) {
909                /* skip allocated blocks */
910                while (tmp == (zend_mm_bitset)-1) {
911                    i += ZEND_MM_BITSET_LEN;
912                    if (i == ZEND_MM_PAGES) {
913                        if (best > 0) {
914                            page_num = best;
915                            goto found;
916                        } else {
917                            goto not_found;
918                        }
919                    }
920                    tmp = *(bitset++);
921                }
922                /* find first 0 bit */
923                page_num = i + zend_mm_bitset_nts(tmp);
924                /* reset bits from 0 to "bit" */
925                tmp &= tmp + 1;
926                /* skip free blocks */
927                while (tmp == 0) {
928                    i += ZEND_MM_BITSET_LEN;
929                    if (i >= free_tail) {
930                        len = ZEND_MM_PAGES - page_num;
931                        if (len >= pages_count && len < best_len) {
932                            chunk->free_tail = page_num + pages_count;
933                            goto found;
934                        } else {
935                            /* set accurate value */
936                            chunk->free_tail = page_num;
937                            if (best > 0) {
938                                page_num = best;
939                                goto found;
940                            } else {
941                                goto not_found;
942                            }
943                        }
944                    }
945                    tmp = *(bitset++);
946                }
947                /* find first 1 bit */
948                len = i + zend_mm_bitset_ntz(tmp) - page_num;
949                if (len >= pages_count) {
950                    if (len == pages_count) {
951                        goto found;
952                    } else if (len < best_len) {
953                        best_len = len;
954                        best = page_num;
955                    }
956                }
957                /* set bits from 0 to "bit" */
958                tmp |= tmp - 1;
959            }
960        }
961
962not_found:
963        if (chunk->next == heap->main_chunk) {
964            if (heap->cached_chunks) {
965                heap->cached_chunks_count--;
966                chunk = heap->cached_chunks;
967                heap->cached_chunks = chunk->next;
968            } else {
969#if ZEND_MM_LIMIT
970                if (heap->real_size + ZEND_MM_CHUNK_SIZE > heap->limit) {
971                    if (heap->overflow == 0) {
972#if ZEND_DEBUG
973                        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);
974#else
975                        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);
976#endif
977                        return NULL;
978                    }
979                }
980#endif
981                chunk = (zend_mm_chunk*)zend_mm_chunk_alloc(heap, ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);
982                if (UNEXPECTED(chunk == NULL)) {
983                    /* insufficient memory */
984#if !ZEND_MM_LIMIT
985                    zend_mm_safe_error(heap, "Out of memory");
986#elif ZEND_DEBUG
987                    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);
988#else
989                    zend_mm_safe_error(heap, "Out of memory (allocated %zu) (tried to allocate %zu bytes)", heap->real_size, ZEND_MM_PAGE_SIZE * pages_count);
990#endif
991                    return NULL;
992                }
993#if ZEND_MM_STAT
994                do {
995                    size_t size = heap->real_size + ZEND_MM_CHUNK_SIZE;
996                    size_t peak = MAX(heap->real_peak, size);
997                    heap->real_size = size;
998                    heap->real_peak = peak;
999                } while (0);
1000#elif ZEND_MM_LIMIT
1001                heap->real_size += ZEND_MM_CHUNK_SIZE;
1002
1003#endif
1004            }
1005            heap->chunks_count++;
1006            if (heap->chunks_count > heap->peak_chunks_count) {
1007                heap->peak_chunks_count = heap->chunks_count;
1008            }
1009            zend_mm_chunk_init(heap, chunk);
1010            page_num = ZEND_MM_FIRST_PAGE;
1011            len = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
1012            goto found;
1013        } else {
1014            chunk = chunk->next;
1015        }
1016    }
1017
1018found:
1019    /* mark run as allocated */
1020    chunk->free_pages -= pages_count;
1021    zend_mm_bitset_set_range(chunk->free_map, page_num, pages_count);
1022    chunk->map[page_num] = ZEND_MM_LRUN(pages_count);
1023    if (page_num == chunk->free_tail) {
1024        chunk->free_tail = page_num + pages_count;
1025    }
1026    return ZEND_MM_PAGE_ADDR(chunk, page_num);
1027}
1028
1029static zend_always_inline void *zend_mm_alloc_large(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1030{
1031    int pages_count = ZEND_MM_SIZE_TO_NUM(size, ZEND_MM_PAGE_SIZE);
1032#if ZEND_DEBUG
1033    void *ptr = zend_mm_alloc_pages(heap, pages_count, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1034#else
1035    void *ptr = zend_mm_alloc_pages(heap, pages_count ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1036#endif
1037#if ZEND_MM_STAT
1038    do {
1039        size_t size = heap->size + pages_count * ZEND_MM_PAGE_SIZE;
1040        size_t peak = MAX(heap->peak, size);
1041        heap->size = size;
1042        heap->peak = peak;
1043    } while (0);
1044#endif
1045    return ptr;
1046}
1047
1048static void zend_mm_free_pages(zend_mm_heap *heap, zend_mm_chunk *chunk, int page_num, int pages_count)
1049{
1050    chunk->free_pages += pages_count;
1051    zend_mm_bitset_reset_range(chunk->free_map, page_num, pages_count);
1052    chunk->map[page_num] = 0;
1053    if (chunk->free_tail == page_num + pages_count) {
1054        /* this setting may be not accurate */
1055        chunk->free_tail = page_num;
1056    }
1057    if (chunk->free_pages == ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE) {
1058        /* delete chunk */
1059        chunk->next->prev = chunk->prev;
1060        chunk->prev->next = chunk->next;
1061        heap->chunks_count--;
1062        if (heap->chunks_count + heap->cached_chunks_count < heap->avg_chunks_count + 0.1) {
1063            /* delay deletion */
1064            heap->cached_chunks_count++;
1065            chunk->next = heap->cached_chunks;
1066            heap->cached_chunks = chunk;
1067        } else {
1068#if ZEND_MM_STAT || ZEND_MM_LIMIT
1069            heap->real_size -= ZEND_MM_CHUNK_SIZE;
1070#endif
1071            if (!heap->cached_chunks || chunk->num > heap->cached_chunks->num) {
1072                zend_mm_chunk_free(heap, chunk, ZEND_MM_CHUNK_SIZE);
1073            } else {
1074//TODO: select the best chunk to delete???
1075                chunk->next = heap->cached_chunks->next;
1076                zend_mm_chunk_free(heap, heap->cached_chunks, ZEND_MM_CHUNK_SIZE);
1077                heap->cached_chunks = chunk;
1078            }
1079        }
1080    }
1081}
1082
1083static zend_always_inline void zend_mm_free_large(zend_mm_heap *heap, zend_mm_chunk *chunk, int page_num, int pages_count)
1084{
1085#if ZEND_MM_STAT
1086    heap->size -= pages_count * ZEND_MM_PAGE_SIZE;
1087#endif
1088    zend_mm_free_pages(heap, chunk, page_num, pages_count);
1089}
1090
1091/**************/
1092/* Small Runs */
1093/**************/
1094
1095/* higher set bit number (0->N/A, 1->1, 2->2, 4->3, 8->4, 127->7, 128->8 etc) */
1096static zend_always_inline int zend_mm_small_size_to_bit(int size)
1097{
1098#if defined(__GNUC__)
1099    return (__builtin_clz(size) ^ 0x1f) + 1;
1100#elif defined(_WIN32)
1101    unsigned long index;
1102
1103    if (!BitScanReverse(&index, (unsigned long)size)) {
1104        /* undefined behavior */
1105        return 64;
1106    }
1107
1108    return (((31 - (int)index) ^ 0x1f) + 1);
1109#else
1110    int n = 16;
1111    if (size <= 0x00ff) {n -= 8; size = size << 8;}
1112    if (size <= 0x0fff) {n -= 4; size = size << 4;}
1113    if (size <= 0x3fff) {n -= 2; size = size << 2;}
1114    if (size <= 0x7fff) {n -= 1;}
1115    return n;
1116#endif
1117}
1118
1119#ifndef MAX
1120# define MAX(a, b) (((a) > (b)) ? (a) : (b))
1121#endif
1122
1123#ifndef MIN
1124# define MIN(a, b) (((a) < (b)) ? (a) : (b))
1125#endif
1126
1127static zend_always_inline int zend_mm_small_size_to_bin(size_t size)
1128{
1129#if 0
1130    int n;
1131                            /*0,  1,  2,  3,  4,  5,  6,  7,  8,  9  10, 11, 12*/
1132    static const int f1[] = { 3,  3,  3,  3,  3,  3,  3,  4,  5,  6,  7,  8,  9};
1133    static const int f2[] = { 0,  0,  0,  0,  0,  0,  0,  4,  8, 12, 16, 20, 24};
1134
1135    if (UNEXPECTED(size <= 2)) return 0;
1136    n = zend_mm_small_size_to_bit(size - 1);
1137    return ((size-1) >> f1[n]) + f2[n];
1138#else
1139    int t1, t2, t3;
1140
1141    if (UNEXPECTED(size <= 8)) return 0;
1142    t1 = (int)(size - 1);
1143    t2 = zend_mm_small_size_to_bit(t1);
1144    t3 = t2 - 6;
1145    t3 = (t3 < 0) ? 0 : t3;
1146    t2 = t3 + 3;
1147    t1 = t1 >> t2;
1148    t3 = t3 << 2;
1149    return t1 + t3;
1150#endif
1151}
1152
1153#define ZEND_MM_SMALL_SIZE_TO_BIN(size)  zend_mm_small_size_to_bin(size)
1154
1155static zend_never_inline void *zend_mm_alloc_small_slow(zend_mm_heap *heap, int bin_num ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1156{
1157    zend_mm_chunk *chunk;
1158    int page_num;
1159    zend_mm_bin *bin;
1160    zend_mm_free_slot *p, *end;
1161
1162#if ZEND_DEBUG
1163    bin = (zend_mm_bin*)zend_mm_alloc_pages(heap, bin_pages[bin_num], bin_data_size[bin_num] ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1164#else
1165    bin = (zend_mm_bin*)zend_mm_alloc_pages(heap, bin_pages[bin_num] ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1166#endif
1167    if (UNEXPECTED(bin == NULL)) {
1168        /* insufficient memory */
1169        return NULL;
1170    }
1171
1172    chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(bin, ZEND_MM_CHUNK_SIZE);
1173    page_num = ZEND_MM_ALIGNED_OFFSET(bin, ZEND_MM_CHUNK_SIZE) / ZEND_MM_PAGE_SIZE;
1174    chunk->map[page_num] = ZEND_MM_SRUN(bin_num);
1175    if (bin_pages[bin_num] > 1) {
1176        int i = 1;
1177        do {
1178            chunk->map[page_num+i] = ZEND_MM_SRUN(bin_num);
1179            i++;
1180        } while (i < bin_pages[bin_num]);
1181    }
1182
1183    /* create a linked list of elements from 1 to last */
1184    end = (zend_mm_free_slot*)((char*)bin + (bin_data_size[bin_num] * (bin_elements[bin_num] - 1)));
1185    heap->free_slot[bin_num] = p = (zend_mm_free_slot*)((char*)bin + bin_data_size[bin_num]);
1186    do {
1187        p->next_free_slot = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);;
1188#if ZEND_DEBUG
1189        do {
1190            zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + bin_data_size[bin_num] - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1191            dbg->size = 0;
1192        } while (0);
1193#endif
1194        p = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);
1195    } while (p != end);
1196
1197    /* terminate list using NULL */
1198    p->next_free_slot = NULL;
1199#if ZEND_DEBUG
1200        do {
1201            zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + bin_data_size[bin_num] - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1202            dbg->size = 0;
1203        } while (0);
1204#endif
1205
1206    /* return first element */
1207    return (char*)bin;
1208}
1209
1210static zend_always_inline void *zend_mm_alloc_small(zend_mm_heap *heap, size_t size, int bin_num ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1211{
1212#if ZEND_MM_STAT
1213    do {
1214        size_t size = heap->size + bin_data_size[bin_num];
1215        size_t peak = MAX(heap->peak, size);
1216        heap->size = size;
1217        heap->peak = peak;
1218    } while (0);
1219#endif
1220
1221    if (EXPECTED(heap->free_slot[bin_num] != NULL)) {
1222        zend_mm_free_slot *p = heap->free_slot[bin_num];
1223        heap->free_slot[bin_num] = p->next_free_slot;
1224        return (void*)p;
1225    } else {
1226        return zend_mm_alloc_small_slow(heap, bin_num ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1227    }
1228}
1229
1230static zend_always_inline void zend_mm_free_small(zend_mm_heap *heap, void *ptr, int bin_num)
1231{
1232    zend_mm_free_slot *p;
1233
1234#if ZEND_MM_STAT
1235    heap->size -= bin_data_size[bin_num];
1236#endif
1237
1238#if ZEND_DEBUG
1239    do {
1240        zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)ptr + bin_data_size[bin_num] - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1241        dbg->size = 0;
1242    } while (0);
1243#endif
1244
1245    p = (zend_mm_free_slot*)ptr;
1246    p->next_free_slot = heap->free_slot[bin_num];
1247    heap->free_slot[bin_num] = p;
1248}
1249
1250/********/
1251/* Heap */
1252/********/
1253
1254#if ZEND_DEBUG
1255static zend_always_inline zend_mm_debug_info *zend_mm_get_debug_info(zend_mm_heap *heap, void *ptr)
1256{
1257    size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
1258    zend_mm_chunk *chunk;
1259    int page_num;
1260    zend_mm_page_info info;
1261
1262    ZEND_MM_CHECK(page_offset != 0, "zend_mm_heap corrupted");
1263    chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
1264    page_num = page_offset / ZEND_MM_PAGE_SIZE;
1265    info = chunk->map[page_num];
1266    ZEND_MM_CHECK(chunk->heap == heap, "zend_mm_heap corrupted");
1267    if (EXPECTED(info & ZEND_MM_IS_SRUN)) {
1268        int bin_num = ZEND_MM_SRUN_BIN_NUM(info);
1269        return (zend_mm_debug_info*)((char*)ptr + bin_data_size[bin_num] - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1270    } else /* if (info & ZEND_MM_IS_LRUN) */ {
1271        int pages_count = ZEND_MM_LRUN_PAGES(info);
1272
1273        return (zend_mm_debug_info*)((char*)ptr + ZEND_MM_PAGE_SIZE * pages_count - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1274    }
1275}
1276#endif
1277
1278static zend_always_inline void *zend_mm_alloc_heap(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1279{
1280    void *ptr;
1281#if ZEND_DEBUG
1282    size_t real_size = size;
1283    zend_mm_debug_info *dbg;
1284
1285    /* special handling for zero-size allocation */
1286    size = MAX(size, 1);
1287    size = ZEND_MM_ALIGNED_SIZE(size) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info));
1288#endif
1289    if (size <= ZEND_MM_MAX_SMALL_SIZE) {
1290        ptr = zend_mm_alloc_small(heap, size, ZEND_MM_SMALL_SIZE_TO_BIN(size) ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1291#if ZEND_DEBUG
1292        dbg = zend_mm_get_debug_info(heap, ptr);
1293        dbg->size = real_size;
1294        dbg->filename = __zend_filename;
1295        dbg->orig_filename = __zend_orig_filename;
1296        dbg->lineno = __zend_lineno;
1297        dbg->orig_lineno = __zend_orig_lineno;
1298#endif
1299        return ptr;
1300    } else if (size <= ZEND_MM_MAX_LARGE_SIZE) {
1301        ptr = zend_mm_alloc_large(heap, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1302#if ZEND_DEBUG
1303        dbg = zend_mm_get_debug_info(heap, ptr);
1304        dbg->size = real_size;
1305        dbg->filename = __zend_filename;
1306        dbg->orig_filename = __zend_orig_filename;
1307        dbg->lineno = __zend_lineno;
1308        dbg->orig_lineno = __zend_orig_lineno;
1309#endif
1310        return ptr;
1311    } else {
1312#if ZEND_DEBUG
1313        size = real_size;
1314#endif
1315        return zend_mm_alloc_huge(heap, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1316    }
1317}
1318
1319static zend_always_inline void zend_mm_free_heap(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1320{
1321    size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
1322
1323    if (UNEXPECTED(page_offset == 0)) {
1324        if (ptr != NULL) {
1325            zend_mm_free_huge(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1326        }
1327    } else {
1328        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
1329        int page_num = page_offset / ZEND_MM_PAGE_SIZE;
1330        zend_mm_page_info info = chunk->map[page_num];
1331
1332        ZEND_MM_CHECK(chunk->heap == heap, "zend_mm_heap corrupted");
1333        if (EXPECTED(info & ZEND_MM_IS_SRUN)) {
1334            zend_mm_free_small(heap, ptr, ZEND_MM_SRUN_BIN_NUM(info));
1335        } else /* if (info & ZEND_MM_IS_LRUN) */ {
1336            int pages_count = ZEND_MM_LRUN_PAGES(info);
1337
1338            ZEND_MM_CHECK(ZEND_MM_ALIGNED_OFFSET(page_offset, ZEND_MM_PAGE_SIZE) == 0, "zend_mm_heap corrupted");
1339            zend_mm_free_large(heap, chunk, page_num, pages_count);
1340        }
1341    }
1342}
1343
1344static size_t zend_mm_size(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1345{
1346    size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
1347
1348    if (UNEXPECTED(page_offset == 0)) {
1349        return zend_mm_get_huge_block_size(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1350    } else {
1351        zend_mm_chunk *chunk;
1352#if 0 && ZEND_DEBUG
1353        zend_mm_debug_info *dbg = zend_mm_get_debug_info(heap, ptr);
1354        return dbg->size;
1355#else
1356        int page_num;
1357        zend_mm_page_info info;
1358
1359        chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
1360        page_num = page_offset / ZEND_MM_PAGE_SIZE;
1361        info = chunk->map[page_num];
1362        ZEND_MM_CHECK(chunk->heap == heap, "zend_mm_heap corrupted");
1363        if (EXPECTED(info & ZEND_MM_IS_SRUN)) {
1364            return bin_data_size[ZEND_MM_SRUN_BIN_NUM(info)];
1365        } else /* if (info & ZEND_MM_IS_LARGE_RUN) */ {
1366            return ZEND_MM_LRUN_PAGES(info) * ZEND_MM_PAGE_SIZE;
1367        }
1368#endif
1369    }
1370}
1371
1372static void *zend_mm_realloc_heap(zend_mm_heap *heap, void *ptr, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1373{
1374    size_t page_offset;
1375    size_t old_size;
1376    size_t new_size;
1377    void *ret;
1378#if ZEND_DEBUG
1379    size_t real_size;
1380    zend_mm_debug_info *dbg;
1381#endif
1382
1383    page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
1384    if (UNEXPECTED(page_offset == 0)) {
1385        if (UNEXPECTED(ptr == NULL)) {
1386            return zend_mm_alloc_heap(heap, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1387        }
1388        old_size = zend_mm_get_huge_block_size(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1389#if ZEND_DEBUG
1390        real_size = size;
1391        size = ZEND_MM_ALIGNED_SIZE(size) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info));
1392#endif
1393        if (size > ZEND_MM_MAX_LARGE_SIZE) {
1394#if ZEND_DEBUG
1395            size = real_size;
1396#endif
1397            new_size = ZEND_MM_ALIGNED_SIZE_EX(size, ZEND_MM_PAGE_SIZE);
1398            if (new_size == old_size) {
1399#if ZEND_DEBUG
1400                zend_mm_change_huge_block_size(heap, ptr, new_size, real_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1401#else
1402                zend_mm_change_huge_block_size(heap, ptr, new_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1403#endif
1404                return ptr;
1405#ifndef _WIN32
1406            } else if (new_size < old_size) {
1407                /* unmup tail */
1408                zend_mm_chunk_truncate(heap, ptr, old_size, new_size);
1409#if ZEND_MM_STAT || ZEND_MM_LIMIT
1410                heap->real_size -= old_size - new_size;
1411#endif
1412#if ZEND_MM_STAT
1413                heap->size -= old_size - new_size;
1414#endif
1415#if ZEND_DEBUG
1416                zend_mm_change_huge_block_size(heap, ptr, new_size, real_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1417#else
1418                zend_mm_change_huge_block_size(heap, ptr, new_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1419#endif
1420                return ptr;
1421            } else /* if (new_size > old_size) */ {
1422#if ZEND_MM_LIMIT
1423                if (heap->real_size + (new_size - old_size) > heap->limit) {
1424                    if (heap->overflow == 0) {
1425#if ZEND_DEBUG
1426                        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);
1427#else
1428                        zend_mm_safe_error(heap, "Allowed memory size of %zu bytes exhausted (tried to allocate %zu bytes)", heap->limit, size);
1429#endif
1430                        return NULL;
1431                    }
1432                }
1433#endif
1434                /* try to map tail right after this block */
1435                if (zend_mm_mmap_fixed((char*)ptr + old_size, new_size - old_size)) {
1436#if ZEND_MM_STAT || ZEND_MM_LIMIT
1437                    heap->real_size += new_size - old_size;
1438#endif
1439#if ZEND_MM_STAT
1440                    heap->size += new_size - old_size;
1441#endif
1442#if ZEND_DEBUG
1443                    zend_mm_change_huge_block_size(heap, ptr, new_size, real_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1444#else
1445                    zend_mm_change_huge_block_size(heap, ptr, new_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1446#endif
1447                    return ptr;
1448                }
1449#endif
1450            }
1451        }
1452    } else {
1453        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
1454        int page_num = page_offset / ZEND_MM_PAGE_SIZE;
1455        zend_mm_page_info info = chunk->map[page_num];
1456#if ZEND_DEBUG
1457        size_t real_size = size;
1458
1459        size = ZEND_MM_ALIGNED_SIZE(size) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info));
1460#endif
1461
1462        ZEND_MM_CHECK(chunk->heap == heap, "zend_mm_heap corrupted");
1463        if (info & ZEND_MM_IS_SRUN) {
1464            int old_bin_num, bin_num;
1465
1466            old_bin_num = ZEND_MM_SRUN_BIN_NUM(info);
1467            old_size = bin_data_size[old_bin_num];
1468            bin_num = ZEND_MM_SMALL_SIZE_TO_BIN(size);
1469            if (old_bin_num == bin_num) {
1470#if ZEND_DEBUG
1471                dbg = zend_mm_get_debug_info(heap, ptr);
1472                dbg->size = real_size;
1473                dbg->filename = __zend_filename;
1474                dbg->orig_filename = __zend_orig_filename;
1475                dbg->lineno = __zend_lineno;
1476                dbg->orig_lineno = __zend_orig_lineno;
1477#endif
1478                return ptr;
1479            }
1480        } else /* if (info & ZEND_MM_IS_LARGE_RUN) */ {
1481            ZEND_MM_CHECK(ZEND_MM_ALIGNED_OFFSET(page_offset, ZEND_MM_PAGE_SIZE) == 0, "zend_mm_heap corrupted");
1482            old_size = ZEND_MM_LRUN_PAGES(info) * ZEND_MM_PAGE_SIZE;
1483            if (size > ZEND_MM_MAX_SMALL_SIZE && size <= ZEND_MM_MAX_LARGE_SIZE) {
1484                new_size = ZEND_MM_ALIGNED_SIZE_EX(size, ZEND_MM_PAGE_SIZE);
1485                if (new_size == old_size) {
1486#if ZEND_DEBUG
1487                    dbg = zend_mm_get_debug_info(heap, ptr);
1488                    dbg->size = real_size;
1489                    dbg->filename = __zend_filename;
1490                    dbg->orig_filename = __zend_orig_filename;
1491                    dbg->lineno = __zend_lineno;
1492                    dbg->orig_lineno = __zend_orig_lineno;
1493#endif
1494                    return ptr;
1495                } else if (new_size < old_size) {
1496                    /* free tail pages */
1497                    int new_pages_count = new_size / ZEND_MM_PAGE_SIZE;
1498                    int rest_pages_count = (old_size - new_size) / ZEND_MM_PAGE_SIZE;
1499
1500#if ZEND_MM_STAT
1501                    heap->size -= rest_pages_count * ZEND_MM_PAGE_SIZE;
1502#endif
1503                    chunk->map[page_num] = ZEND_MM_LRUN(new_pages_count);
1504                    chunk->free_pages += rest_pages_count;
1505                    zend_mm_bitset_reset_range(chunk->free_map, page_num + new_pages_count, rest_pages_count);
1506#if ZEND_DEBUG
1507                    dbg = zend_mm_get_debug_info(heap, ptr);
1508                    dbg->size = real_size;
1509                    dbg->filename = __zend_filename;
1510                    dbg->orig_filename = __zend_orig_filename;
1511                    dbg->lineno = __zend_lineno;
1512                    dbg->orig_lineno = __zend_orig_lineno;
1513#endif
1514                    return ptr;
1515                } else /* if (new_size > old_size) */ {
1516                    int new_pages_count = new_size / ZEND_MM_PAGE_SIZE;
1517                    int old_pages_count = old_size / ZEND_MM_PAGE_SIZE;
1518
1519                    /* try to allocate tail pages after this block */
1520                    if (page_num + new_pages_count <= ZEND_MM_PAGES &&
1521                        zend_mm_bitset_is_free_range(chunk->free_map, page_num + old_pages_count, new_pages_count - old_pages_count)) {
1522#if ZEND_MM_STAT
1523                        do {
1524                            size_t size = heap->size + (new_size - old_size);
1525                            size_t peak = MAX(heap->peak, size);
1526                            heap->size = size;
1527                            heap->peak = peak;
1528                        } while (0);
1529#endif
1530                        chunk->free_pages -= new_pages_count - old_pages_count;
1531                        zend_mm_bitset_set_range(chunk->free_map, page_num + old_pages_count, new_pages_count - old_pages_count);
1532                        chunk->map[page_num] = ZEND_MM_LRUN(new_pages_count);
1533#if ZEND_DEBUG
1534                        dbg = zend_mm_get_debug_info(heap, ptr);
1535                        dbg->size = real_size;
1536                        dbg->filename = __zend_filename;
1537                        dbg->orig_filename = __zend_orig_filename;
1538                        dbg->lineno = __zend_lineno;
1539                        dbg->orig_lineno = __zend_orig_lineno;
1540#endif
1541                        return ptr;
1542                    }
1543                }
1544            }
1545        }
1546#if ZEND_DEBUG
1547        size = real_size;
1548#endif
1549    }
1550
1551    /* Naive reallocation */
1552    old_size = zend_mm_size(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1553    ret = zend_mm_alloc_heap(heap, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1554    memcpy(ret, ptr, MIN(old_size, size));
1555    zend_mm_free_heap(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1556    return ret;
1557}
1558
1559/*********************/
1560/* Huge Runs (again) */
1561/*********************/
1562
1563#if ZEND_DEBUG
1564static void zend_mm_add_huge_block(zend_mm_heap *heap, void *ptr, size_t size, size_t dbg_size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1565#else
1566static void zend_mm_add_huge_block(zend_mm_heap *heap, void *ptr, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1567#endif
1568{
1569    zend_mm_huge_list *list = (zend_mm_huge_list*)zend_mm_alloc_heap(heap, sizeof(zend_mm_huge_list) ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1570    list->ptr = ptr;
1571    list->size = size;
1572    list->next = heap->huge_list;
1573#if ZEND_DEBUG
1574    list->dbg.size = dbg_size;
1575    list->dbg.filename = __zend_filename;
1576    list->dbg.orig_filename = __zend_orig_filename;
1577    list->dbg.lineno = __zend_lineno;
1578    list->dbg.orig_lineno = __zend_orig_lineno;
1579#endif
1580    heap->huge_list = list;
1581}
1582
1583static size_t zend_mm_del_huge_block(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1584{
1585    zend_mm_huge_list *prev = NULL;
1586    zend_mm_huge_list *list = heap->huge_list;
1587    while (list != NULL) {
1588        if (list->ptr == ptr) {
1589            size_t size;
1590
1591            if (prev) {
1592                prev->next = list->next;
1593            } else {
1594                heap->huge_list = list->next;
1595            }
1596            size = list->size;
1597            zend_mm_free_heap(heap, list ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1598            return size;
1599        }
1600        prev = list;
1601        list = list->next;
1602    }
1603    ZEND_MM_CHECK(0, "zend_mm_heap corrupted");
1604    return 0;
1605}
1606
1607static size_t zend_mm_get_huge_block_size(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1608{
1609    zend_mm_huge_list *list = heap->huge_list;
1610    while (list != NULL) {
1611        if (list->ptr == ptr) {
1612            return list->size;
1613        }
1614        list = list->next;
1615    }
1616    ZEND_MM_CHECK(0, "zend_mm_heap corrupted");
1617    return 0;
1618}
1619
1620#if ZEND_DEBUG
1621static 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)
1622#else
1623static 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)
1624#endif
1625{
1626    zend_mm_huge_list *list = heap->huge_list;
1627    while (list != NULL) {
1628        if (list->ptr == ptr) {
1629            list->size = size;
1630#if ZEND_DEBUG
1631            list->dbg.size = dbg_size;
1632            list->dbg.filename = __zend_filename;
1633            list->dbg.orig_filename = __zend_orig_filename;
1634            list->dbg.lineno = __zend_lineno;
1635            list->dbg.orig_lineno = __zend_orig_lineno;
1636#endif
1637            return;
1638        }
1639        list = list->next;
1640    }
1641}
1642
1643static void *zend_mm_alloc_huge(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1644{
1645    size_t new_size = ZEND_MM_ALIGNED_SIZE_EX(size, ZEND_MM_PAGE_SIZE);
1646    void *ptr;
1647
1648#if ZEND_MM_LIMIT
1649    if (heap->real_size + new_size > heap->limit) {
1650        if (heap->overflow == 0) {
1651#if ZEND_DEBUG
1652            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);
1653#else
1654            zend_mm_safe_error(heap, "Allowed memory size of %zu bytes exhausted (tried to allocate %zu bytes)", heap->limit, size);
1655#endif
1656            return NULL;
1657        }
1658    }
1659#endif
1660    ptr = zend_mm_chunk_alloc(heap, new_size, ZEND_MM_CHUNK_SIZE);
1661    if (UNEXPECTED(ptr == NULL)) {
1662        /* insufficient memory */
1663#if !ZEND_MM_LIMIT
1664        zend_mm_safe_error(heap, "Out of memory");
1665#elif ZEND_DEBUG
1666        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);
1667#else
1668        zend_mm_safe_error(heap, "Out of memory (allocated %zu) (tried to allocate %zu bytes)", heap->real_size, size);
1669#endif
1670        return NULL;
1671    }
1672#if ZEND_DEBUG
1673    zend_mm_add_huge_block(heap, ptr, new_size, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1674#else
1675    zend_mm_add_huge_block(heap, ptr, new_size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1676#endif
1677#if ZEND_MM_STAT
1678    do {
1679        size_t size = heap->real_size + new_size;
1680        size_t peak = MAX(heap->real_peak, size);
1681        heap->real_size = size;
1682        heap->real_peak = peak;
1683    } while (0);
1684    do {
1685        size_t size = heap->size + new_size;
1686        size_t peak = MAX(heap->peak, size);
1687        heap->size = size;
1688        heap->peak = peak;
1689    } while (0);
1690#elif ZEND_MM_LIMIT
1691    heap->real_size += new_size;
1692#endif
1693    return ptr;
1694}
1695
1696static void zend_mm_free_huge(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
1697{
1698    size_t size;
1699
1700    ZEND_MM_CHECK(ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE) == 0, "zend_mm_heap corrupted");
1701    size = zend_mm_del_huge_block(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
1702    zend_mm_chunk_free(heap, ptr, size);
1703#if ZEND_MM_STAT || ZEND_MM_LIMIT
1704    heap->real_size -= size;
1705#endif
1706#if ZEND_MM_STAT
1707    heap->size -= size;
1708#endif
1709}
1710
1711/******************/
1712/* Initialization */
1713/******************/
1714
1715static zend_mm_heap *zend_mm_init(void)
1716{
1717    zend_mm_chunk *chunk = (zend_mm_chunk*)zend_mm_chunk_alloc_int(ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);
1718    zend_mm_heap *heap;
1719
1720    if (UNEXPECTED(chunk == NULL)) {
1721#if ZEND_MM_ERROR
1722#ifdef _WIN32
1723        stderr_last_error("Can't initialize heap");
1724#else
1725        fprintf(stderr, "\nCan't initialize heap: [%d] %s\n", errno, strerror(errno));
1726#endif
1727#endif
1728        return NULL;
1729    }
1730    heap = &chunk->heap_slot;
1731    chunk->heap = heap;
1732    chunk->next = chunk;
1733    chunk->prev = chunk;
1734    chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
1735    chunk->free_tail = ZEND_MM_FIRST_PAGE;
1736    chunk->num = 0;
1737    chunk->free_map[0] = (Z_L(1) << ZEND_MM_FIRST_PAGE) - 1;
1738    chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
1739    heap->main_chunk = chunk;
1740    heap->cached_chunks = NULL;
1741    heap->chunks_count = 1;
1742    heap->peak_chunks_count = 1;
1743    heap->cached_chunks_count = 0;
1744    heap->avg_chunks_count = 1.0;
1745#if ZEND_MM_STAT || ZEND_MM_LIMIT
1746    heap->real_size = ZEND_MM_CHUNK_SIZE;
1747#endif
1748#if ZEND_MM_STAT
1749    heap->real_peak = ZEND_MM_CHUNK_SIZE;
1750    heap->size = 0;
1751    heap->peak = 0;
1752#endif
1753#if ZEND_MM_LIMIT
1754    heap->limit = (Z_L(-1) >> Z_L(1));
1755    heap->overflow = 0;
1756#endif
1757#if ZEND_MM_CUSTOM
1758    heap->use_custom_heap = 0;
1759#endif
1760#if ZEND_MM_STORAGE
1761    heap->storage = NULL;
1762#endif
1763    heap->huge_list = NULL;
1764    return heap;
1765}
1766
1767#if ZEND_DEBUG
1768/******************/
1769/* Leak detection */
1770/******************/
1771
1772static zend_long zend_mm_find_leaks_small(zend_mm_chunk *p, int i, int j, zend_leak_info *leak)
1773{
1774    int empty = 1;
1775    zend_long count = 0;
1776    int bin_num = ZEND_MM_SRUN_BIN_NUM(p->map[i]);
1777    zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * i + bin_data_size[bin_num] * (j + 1) - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1778
1779    while (j < bin_elements[bin_num]) {
1780        if (dbg->size != 0) {
1781            if (dbg->filename == leak->filename && dbg->lineno == leak->lineno) {
1782                count++;
1783                dbg->size = 0;
1784                dbg->filename = NULL;
1785                dbg->lineno = 0;
1786            } else {
1787                empty = 0;
1788            }
1789        }
1790        j++;
1791        dbg = (zend_mm_debug_info*)((char*)dbg + bin_data_size[bin_num]);
1792    }
1793    if (empty) {
1794        zend_mm_bitset_reset_range(p->free_map, i, bin_pages[bin_num]);
1795    }
1796    return count;
1797}
1798
1799static zend_long zend_mm_find_leaks(zend_mm_heap *heap, zend_mm_chunk *p, int i, zend_leak_info *leak)
1800{
1801    zend_long count = 0;
1802
1803    do {
1804        while (i < p->free_tail) {
1805            if (zend_mm_bitset_is_set(p->free_map, i)) {
1806                if (p->map[i] & ZEND_MM_IS_SRUN) {
1807                    int bin_num = ZEND_MM_SRUN_BIN_NUM(p->map[i]);
1808                    count += zend_mm_find_leaks_small(p, i, 0, leak);
1809                    i += bin_pages[bin_num];
1810                } else /* if (p->map[i] & ZEND_MM_IS_LRUN) */ {
1811                    int pages_count = ZEND_MM_LRUN_PAGES(p->map[i]);
1812                    zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * (i + pages_count) - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1813
1814                    if (dbg->filename == leak->filename && dbg->lineno == leak->lineno) {
1815                        count++;
1816                    }
1817                    zend_mm_bitset_reset_range(p->free_map, i, pages_count);
1818                    i += pages_count;
1819                }
1820            } else {
1821                i++;
1822            }
1823        }
1824        p = p->next;
1825    } while (p != heap->main_chunk);
1826    return count;
1827}
1828
1829static void zend_mm_check_leaks(zend_mm_heap *heap TSRMLS_DC)
1830{
1831    zend_mm_huge_list *list;
1832    zend_mm_chunk *p;
1833    zend_leak_info leak;
1834    zend_long repeated = 0;
1835    uint32_t total = 0;
1836    int i, j;
1837
1838    /* find leaked huge blocks and free them */
1839    list = heap->huge_list;
1840    while (list) {
1841        zend_mm_huge_list *q = list;
1842
1843        heap->huge_list = list->next;
1844
1845        leak.addr = list->ptr;
1846        leak.size = list->dbg.size;
1847        leak.filename = list->dbg.filename;
1848        leak.orig_filename = list->dbg.orig_filename;
1849        leak.lineno = list->dbg.lineno;
1850        leak.orig_lineno = list->dbg.orig_lineno;
1851
1852        zend_message_dispatcher(ZMSG_LOG_SCRIPT_NAME, NULL TSRMLS_CC);
1853        zend_message_dispatcher(ZMSG_MEMORY_LEAK_DETECTED, &leak TSRMLS_CC);
1854//???       repeated = zend_mm_find_leaks_huge(segment, p);
1855        total += 1 + repeated;
1856        if (repeated) {
1857            zend_message_dispatcher(ZMSG_MEMORY_LEAK_REPEATED, (void *)(zend_uintptr_t)repeated TSRMLS_CC);
1858        }
1859
1860        list = list->next;
1861        zend_mm_chunk_free(heap, q->ptr, q->size);
1862        zend_mm_free_heap(heap, q, NULL, 0, NULL, 0);
1863    }
1864
1865    /* for each chunk */
1866    p = heap->main_chunk;
1867    do {
1868        i = ZEND_MM_FIRST_PAGE;
1869        while (i < p->free_tail) {
1870            if (zend_mm_bitset_is_set(p->free_map, i)) {
1871                if (p->map[i] & ZEND_MM_IS_SRUN) {
1872                    int bin_num = ZEND_MM_SRUN_BIN_NUM(p->map[i]);
1873                    zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * i + bin_data_size[bin_num] - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1874
1875                    j = 0;
1876                    while (j < bin_elements[bin_num]) {
1877                        if (dbg->size != 0) {
1878                            leak.addr = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * i + bin_data_size[bin_num] * j);
1879                            leak.size = dbg->size;
1880                            leak.filename = dbg->filename;
1881                            leak.orig_filename = dbg->orig_filename;
1882                            leak.lineno = dbg->lineno;
1883                            leak.orig_lineno = dbg->orig_lineno;
1884
1885                            zend_message_dispatcher(ZMSG_LOG_SCRIPT_NAME, NULL TSRMLS_CC);
1886                            zend_message_dispatcher(ZMSG_MEMORY_LEAK_DETECTED, &leak TSRMLS_CC);
1887
1888                            dbg->size = 0;
1889                            dbg->filename = NULL;
1890                            dbg->lineno = 0;
1891
1892                            repeated = zend_mm_find_leaks_small(p, i, j + 1, &leak) +
1893                                       zend_mm_find_leaks(heap, p, i + bin_pages[bin_num], &leak);
1894                            total += 1 + repeated;
1895                            if (repeated) {
1896                                zend_message_dispatcher(ZMSG_MEMORY_LEAK_REPEATED, (void *)(zend_uintptr_t)repeated TSRMLS_CC);
1897                            }
1898                        }
1899                        dbg = (zend_mm_debug_info*)((char*)dbg + bin_data_size[bin_num]);
1900                        j++;
1901                    }
1902                    i += bin_pages[bin_num];
1903                } else /* if (p->map[i] & ZEND_MM_IS_LRUN) */ {
1904                    int pages_count = ZEND_MM_LRUN_PAGES(p->map[i]);
1905                    zend_mm_debug_info *dbg = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * (i + pages_count) - ZEND_MM_ALIGNED_SIZE(sizeof(zend_mm_debug_info)));
1906
1907                    leak.addr = (void*)((char*)p + ZEND_MM_PAGE_SIZE * i);
1908                    leak.size = dbg->size;
1909                    leak.filename = dbg->filename;
1910                    leak.orig_filename = dbg->orig_filename;
1911                    leak.lineno = dbg->lineno;
1912                    leak.orig_lineno = dbg->orig_lineno;
1913
1914                    zend_message_dispatcher(ZMSG_LOG_SCRIPT_NAME, NULL TSRMLS_CC);
1915                    zend_message_dispatcher(ZMSG_MEMORY_LEAK_DETECTED, &leak TSRMLS_CC);
1916
1917                    zend_mm_bitset_reset_range(p->free_map, i, pages_count);
1918
1919                    repeated = zend_mm_find_leaks(heap, p, i + pages_count, &leak);
1920                    total += 1 + repeated;
1921                    if (repeated) {
1922                        zend_message_dispatcher(ZMSG_MEMORY_LEAK_REPEATED, (void *)(zend_uintptr_t)repeated TSRMLS_CC);
1923                    }
1924                    i += pages_count;
1925                }
1926            } else {
1927                i++;
1928            }
1929        }
1930        p = p->next;
1931    } while (p != heap->main_chunk);
1932    if (total) {
1933        zend_message_dispatcher(ZMSG_MEMORY_LEAKS_GRAND_TOTAL, &total TSRMLS_CC);
1934    }
1935}
1936#endif
1937
1938void zend_mm_shutdown(zend_mm_heap *heap, int full, int silent TSRMLS_DC)
1939{
1940    zend_mm_chunk *p;
1941    zend_mm_huge_list *list;
1942
1943#if ZEND_MM_CUSTOM
1944    if (heap->use_custom_heap) {
1945        return;
1946    }
1947#endif
1948
1949#if ZEND_DEBUG
1950    if (!silent) {
1951        zend_mm_check_leaks(heap TSRMLS_CC);
1952    }
1953#endif
1954
1955    /* free huge blocks */
1956    list = heap->huge_list;
1957    while (list) {
1958        zend_mm_huge_list *q = list;
1959        list = list->next;
1960        zend_mm_chunk_free(heap, q->ptr, q->size);
1961    }
1962
1963    /* move all chunks except of the first one into the cache */
1964    p = heap->main_chunk->next;
1965    while (p != heap->main_chunk) {
1966        zend_mm_chunk *q = p->next;
1967        p->next = heap->cached_chunks;
1968        heap->cached_chunks = p;
1969        p = q;
1970        heap->chunks_count--;
1971        heap->cached_chunks_count++;
1972    }
1973
1974    if (full) {
1975        /* free all cached chunks */
1976        while (heap->cached_chunks) {
1977            p = heap->cached_chunks;
1978            heap->cached_chunks = p->next;
1979            zend_mm_chunk_free(heap, p, ZEND_MM_CHUNK_SIZE);
1980        }
1981        /* free the first chunk */
1982#if ZEND_MM_STORAGE
1983        if (UNEXPECTED(heap->storage)) {
1984            zend_mm_storage *storage = heap->storage;
1985            zend_mm_chunk_free(heap, heap->main_chunk, ZEND_MM_CHUNK_SIZE);
1986            storage->dtor(storage);
1987        } else {
1988            zend_mm_chunk_free(heap, heap->main_chunk, ZEND_MM_CHUNK_SIZE);
1989        }
1990#else
1991        zend_mm_chunk_free(heap, heap->main_chunk, ZEND_MM_CHUNK_SIZE);
1992#endif
1993    } else {
1994        zend_mm_heap old_heap;
1995
1996        /* free some cached chunks to keep average count */
1997        heap->avg_chunks_count = (heap->avg_chunks_count + (double)heap->peak_chunks_count) / 2.0;
1998        while ((double)heap->cached_chunks_count + 0.9 > heap->avg_chunks_count &&
1999               heap->cached_chunks) {
2000            p = heap->cached_chunks;
2001            heap->cached_chunks = p->next;
2002            zend_mm_chunk_free(heap, p, ZEND_MM_CHUNK_SIZE);
2003            heap->cached_chunks_count--;
2004        }
2005        /* clear cached chunks */
2006        p = heap->cached_chunks;
2007        while (p != NULL) {
2008            zend_mm_chunk *q = p->next;
2009            memset(p, 0, sizeof(zend_mm_chunk));
2010            p->next = q;
2011            p = q;
2012        }
2013
2014        /* reinitialize the first chunk and heap */
2015        old_heap = *heap;
2016        p = heap->main_chunk;
2017        memset(p, 0, ZEND_MM_FIRST_PAGE * ZEND_MM_PAGE_SIZE);
2018        *heap = old_heap;
2019        memset(heap->free_slot, 0, sizeof(heap->free_slot));
2020        heap->main_chunk = p;
2021        p->heap = &p->heap_slot;
2022        p->next = p;
2023        p->prev = p;
2024        p->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
2025        p->free_tail = ZEND_MM_FIRST_PAGE;
2026        p->free_map[0] = (1L << ZEND_MM_FIRST_PAGE) - 1;
2027        p->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
2028        heap->chunks_count = 1;
2029        heap->peak_chunks_count = 1;
2030#if ZEND_MM_STAT || ZEND_MM_LIMIT
2031        heap->real_size = ZEND_MM_CHUNK_SIZE;
2032#endif
2033#if ZEND_MM_STAT
2034        heap->real_peak = ZEND_MM_CHUNK_SIZE;
2035#endif
2036    }
2037}
2038
2039/**************/
2040/* PUBLIC API */
2041/**************/
2042
2043ZEND_API void* ZEND_FASTCALL _zend_mm_alloc(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2044{
2045    return zend_mm_alloc_heap(heap, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2046}
2047
2048ZEND_API void ZEND_FASTCALL _zend_mm_free(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2049{
2050    zend_mm_free_heap(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2051}
2052
2053void* ZEND_FASTCALL _zend_mm_realloc(zend_mm_heap *heap, void *ptr, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2054{
2055    return zend_mm_realloc_heap(heap, ptr, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2056}
2057
2058ZEND_API size_t ZEND_FASTCALL _zend_mm_block_size(zend_mm_heap *heap, void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2059{
2060    return zend_mm_size(heap, ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2061}
2062
2063/**********************/
2064/* Allocation Manager */
2065/**********************/
2066
2067typedef struct _zend_alloc_globals {
2068    zend_mm_heap *mm_heap;
2069} zend_alloc_globals;
2070
2071#ifdef ZTS
2072static int alloc_globals_id;
2073# define AG(v) TSRMG(alloc_globals_id, zend_alloc_globals *, v)
2074#else
2075# define AG(v) (alloc_globals.v)
2076static zend_alloc_globals alloc_globals;
2077#endif
2078
2079ZEND_API int is_zend_mm(TSRMLS_D)
2080{
2081#if ZEND_MM_CUSTOM
2082    return !AG(mm_heap)->use_custom_heap;
2083#else
2084    return 1;
2085#endif
2086}
2087
2088#if !ZEND_DEBUG && !defined(_WIN32)
2089#undef _emalloc
2090
2091#if ZEND_MM_CUSTOM
2092# define ZEND_MM_CUSTOM_ALLOCATOR(size) do { \
2093        if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) { \
2094            return AG(mm_heap)->_malloc(size); \
2095        } \
2096    } while (0)
2097# define ZEND_MM_CUSTOM_DEALLOCATOR(ptr) do { \
2098        if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) { \
2099            AG(mm_heap)->_free(ptr); \
2100            return; \
2101        } \
2102    } while (0)
2103#else
2104# define ZEND_MM_CUSTOM_ALLOCATOR(size)
2105# define ZEND_MM_CUSTOM_DEALLOCATOR(ptr)
2106#endif
2107
2108# define _ZEND_BIN_ALLOCATOR(_num, _size, _elements, _pages, x, y) \
2109    ZEND_API void* ZEND_FASTCALL _emalloc_ ## _size(void) { \
2110        TSRMLS_FETCH(); \
2111        ZEND_MM_CUSTOM_ALLOCATOR(_size); \
2112        return zend_mm_alloc_small(AG(mm_heap), _size, _num ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC); \
2113    }
2114
2115ZEND_MM_BINS_INFO(_ZEND_BIN_ALLOCATOR, x, y)
2116
2117ZEND_API void* ZEND_FASTCALL _emalloc_large(size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2118{
2119    TSRMLS_FETCH();
2120
2121    ZEND_MM_CUSTOM_ALLOCATOR(size);
2122    return zend_mm_alloc_large(AG(mm_heap), size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2123}
2124
2125ZEND_API void* ZEND_FASTCALL _emalloc_huge(size_t size)
2126{
2127    TSRMLS_FETCH();
2128
2129    ZEND_MM_CUSTOM_ALLOCATOR(size);
2130    return zend_mm_alloc_huge(AG(mm_heap), size);
2131}
2132
2133# define _ZEND_BIN_FREE(_num, _size, _elements, _pages, x, y) \
2134    ZEND_API void ZEND_FASTCALL _efree_ ## _size(void *ptr) { \
2135        TSRMLS_FETCH(); \
2136        ZEND_MM_CUSTOM_DEALLOCATOR(ptr); \
2137        { \
2138            size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE); \
2139            zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE); \
2140            int page_num = page_offset / ZEND_MM_PAGE_SIZE; \
2141            ZEND_MM_CHECK(chunk->heap == AG(mm_heap), "zend_mm_heap corrupted"); \
2142            ZEND_ASSERT(chunk->map[page_num] & ZEND_MM_IS_SRUN); \
2143            ZEND_ASSERT(ZEND_MM_SRUN_BIN_NUM(chunk->map[page_num]) == _num); \
2144            zend_mm_free_small(AG(mm_heap), ptr, _num); \
2145        } \
2146    }
2147
2148ZEND_MM_BINS_INFO(_ZEND_BIN_FREE, x, y)
2149
2150ZEND_API void ZEND_FASTCALL _efree_large(void *ptr, size_t size)
2151{
2152    TSRMLS_FETCH();
2153
2154    ZEND_MM_CUSTOM_DEALLOCATOR(ptr);
2155    {
2156        size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
2157        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
2158        int page_num = page_offset / ZEND_MM_PAGE_SIZE;
2159        int pages_count = ZEND_MM_ALIGNED_SIZE_EX(size, ZEND_MM_PAGE_SIZE) / ZEND_MM_PAGE_SIZE;
2160
2161        ZEND_MM_CHECK(chunk->heap == AG(mm_heap) && ZEND_MM_ALIGNED_OFFSET(page_offset, ZEND_MM_PAGE_SIZE) == 0, "zend_mm_heap corrupted");
2162        ZEND_ASSERT(chunk->map[page_num] & ZEND_MM_IS_LRUN);
2163        ZEND_ASSERT(ZEND_MM_LRUN_PAGES(chunk->map[page_num]) == pages_count);
2164        zend_mm_free_large(AG(mm_heap), chunk, page_num, pages_count);
2165    }
2166}
2167
2168ZEND_API void ZEND_FASTCALL _efree_huge(void *ptr, size_t size)
2169{
2170    TSRMLS_FETCH();
2171
2172    ZEND_MM_CUSTOM_DEALLOCATOR(ptr);
2173    // TODO: use size???
2174    zend_mm_free_huge(AG(mm_heap), ptr);
2175}
2176#endif
2177
2178ZEND_API void* ZEND_FASTCALL _emalloc(size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2179{
2180    TSRMLS_FETCH();
2181
2182#if ZEND_MM_CUSTOM
2183    if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) {
2184        return AG(mm_heap)->_malloc(size);
2185    }
2186#endif
2187    return zend_mm_alloc_heap(AG(mm_heap), size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2188}
2189
2190ZEND_API void ZEND_FASTCALL _efree(void *ptr ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2191{
2192    TSRMLS_FETCH();
2193
2194#if ZEND_MM_CUSTOM
2195    if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) {
2196        AG(mm_heap)->_free(ptr);
2197        return;
2198    }
2199#endif
2200    zend_mm_free_heap(AG(mm_heap), ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2201}
2202
2203ZEND_API void* ZEND_FASTCALL _erealloc(void *ptr, size_t size, int allow_failure ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2204{
2205    TSRMLS_FETCH();
2206
2207    if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) {
2208        return AG(mm_heap)->_realloc(ptr, size);
2209    }
2210    return zend_mm_realloc_heap(AG(mm_heap), ptr, size ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2211}
2212
2213ZEND_API size_t ZEND_FASTCALL _zend_mem_block_size(void *ptr TSRMLS_DC ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2214{
2215    if (UNEXPECTED(AG(mm_heap)->use_custom_heap)) {
2216        return 0;
2217    }
2218    return zend_mm_size(AG(mm_heap), ptr ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2219}
2220
2221static zend_always_inline size_t safe_address(size_t nmemb, size_t size, size_t offset)
2222{
2223    int overflow;
2224    size_t ret = zend_safe_address(nmemb, size, offset, &overflow);
2225
2226    if (UNEXPECTED(overflow)) {
2227        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", nmemb, size, offset);
2228        return 0;
2229    }
2230    return ret;
2231}
2232
2233
2234ZEND_API void* ZEND_FASTCALL _safe_emalloc(size_t nmemb, size_t size, size_t offset ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2235{
2236    return emalloc_rel(safe_address(nmemb, size, offset));
2237}
2238
2239ZEND_API void* ZEND_FASTCALL _safe_malloc(size_t nmemb, size_t size, size_t offset)
2240{
2241    return pemalloc(safe_address(nmemb, size, offset), 1);
2242}
2243
2244ZEND_API void* ZEND_FASTCALL _safe_erealloc(void *ptr, size_t nmemb, size_t size, size_t offset ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2245{
2246    return erealloc_rel(ptr, safe_address(nmemb, size, offset));
2247}
2248
2249ZEND_API void* ZEND_FASTCALL _safe_realloc(void *ptr, size_t nmemb, size_t size, size_t offset)
2250{
2251    return perealloc(ptr, safe_address(nmemb, size, offset), 1);
2252}
2253
2254
2255ZEND_API void* ZEND_FASTCALL _ecalloc(size_t nmemb, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2256{
2257    void *p;
2258#ifdef ZEND_SIGNALS
2259    TSRMLS_FETCH();
2260#endif
2261    HANDLE_BLOCK_INTERRUPTIONS();
2262
2263    p = _safe_emalloc(nmemb, size, 0 ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2264    if (UNEXPECTED(p == NULL)) {
2265        HANDLE_UNBLOCK_INTERRUPTIONS();
2266        return p;
2267    }
2268    memset(p, 0, size * nmemb);
2269    HANDLE_UNBLOCK_INTERRUPTIONS();
2270    return p;
2271}
2272
2273ZEND_API char* ZEND_FASTCALL _estrdup(const char *s ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2274{
2275    size_t length;
2276    char *p;
2277#ifdef ZEND_SIGNALS
2278    TSRMLS_FETCH();
2279#endif
2280
2281    HANDLE_BLOCK_INTERRUPTIONS();
2282
2283    length = strlen(s)+1;
2284    p = (char *) _emalloc(length ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2285    if (UNEXPECTED(p == NULL)) {
2286        HANDLE_UNBLOCK_INTERRUPTIONS();
2287        return p;
2288    }
2289    memcpy(p, s, length);
2290    HANDLE_UNBLOCK_INTERRUPTIONS();
2291    return p;
2292}
2293
2294ZEND_API char* ZEND_FASTCALL _estrndup(const char *s, size_t length ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
2295{
2296    char *p;
2297#ifdef ZEND_SIGNALS
2298    TSRMLS_FETCH();
2299#endif
2300
2301    HANDLE_BLOCK_INTERRUPTIONS();
2302
2303    p = (char *) _emalloc(length+1 ZEND_FILE_LINE_RELAY_CC ZEND_FILE_LINE_ORIG_RELAY_CC);
2304    if (UNEXPECTED(p == NULL)) {
2305        HANDLE_UNBLOCK_INTERRUPTIONS();
2306        return p;
2307    }
2308    memcpy(p, s, length);
2309    p[length] = 0;
2310    HANDLE_UNBLOCK_INTERRUPTIONS();
2311    return p;
2312}
2313
2314
2315ZEND_API char* ZEND_FASTCALL zend_strndup(const char *s, size_t length)
2316{
2317    char *p;
2318#ifdef ZEND_SIGNALS
2319    TSRMLS_FETCH();
2320#endif
2321
2322    HANDLE_BLOCK_INTERRUPTIONS();
2323
2324    p = (char *) malloc(length+1);
2325    if (UNEXPECTED(p == NULL)) {
2326        HANDLE_UNBLOCK_INTERRUPTIONS();
2327        return p;
2328    }
2329    if (length) {
2330        memcpy(p, s, length);
2331    }
2332    p[length] = 0;
2333    HANDLE_UNBLOCK_INTERRUPTIONS();
2334    return p;
2335}
2336
2337
2338ZEND_API int zend_set_memory_limit(size_t memory_limit TSRMLS_DC)
2339{
2340#if ZEND_MM_LIMIT
2341    AG(mm_heap)->limit = (memory_limit >= ZEND_MM_CHUNK_SIZE) ? memory_limit : ZEND_MM_CHUNK_SIZE;
2342#endif
2343    return SUCCESS;
2344}
2345
2346ZEND_API size_t zend_memory_usage(int real_usage TSRMLS_DC)
2347{
2348#if ZEND_MM_STAT
2349    if (real_usage) {
2350        return AG(mm_heap)->real_size;
2351    } else {
2352        size_t usage = AG(mm_heap)->size;
2353        return usage;
2354    }
2355#endif
2356    return 0;
2357}
2358
2359ZEND_API size_t zend_memory_peak_usage(int real_usage TSRMLS_DC)
2360{
2361#if ZEND_MM_STAT
2362    if (real_usage) {
2363        return AG(mm_heap)->real_peak;
2364    } else {
2365        return AG(mm_heap)->peak;
2366    }
2367#endif
2368    return 0;
2369}
2370
2371ZEND_API void shutdown_memory_manager(int silent, int full_shutdown TSRMLS_DC)
2372{
2373    zend_mm_shutdown(AG(mm_heap), full_shutdown, silent TSRMLS_CC);
2374}
2375
2376static void alloc_globals_ctor(zend_alloc_globals *alloc_globals TSRMLS_DC)
2377{
2378#if ZEND_MM_CUSTOM
2379    char *tmp = getenv("USE_ZEND_ALLOC");
2380
2381    if (tmp && !zend_atoi(tmp, 0)) {
2382        alloc_globals->mm_heap = malloc(sizeof(zend_mm_heap));
2383        memset(alloc_globals->mm_heap, 0, sizeof(zend_mm_heap));
2384        alloc_globals->mm_heap->use_custom_heap = 1;
2385        alloc_globals->mm_heap->_malloc = malloc;
2386        alloc_globals->mm_heap->_free = free;
2387        alloc_globals->mm_heap->_realloc = realloc;
2388        return;
2389    }
2390#endif
2391    alloc_globals->mm_heap = zend_mm_init();
2392}
2393
2394#ifdef ZTS
2395static void alloc_globals_dtor(zend_alloc_globals *alloc_globals TSRMLS_DC)
2396{
2397    shutdown_memory_manager(1, 1 TSRMLS_CC);
2398}
2399#endif
2400
2401ZEND_API void start_memory_manager(TSRMLS_D)
2402{
2403#ifdef ZTS
2404    ts_allocate_id(&alloc_globals_id, sizeof(zend_alloc_globals), (ts_allocate_ctor) alloc_globals_ctor, (ts_allocate_dtor) alloc_globals_dtor);
2405#else
2406    alloc_globals_ctor(&alloc_globals);
2407#endif
2408}
2409
2410ZEND_API zend_mm_heap *zend_mm_set_heap(zend_mm_heap *new_heap TSRMLS_DC)
2411{
2412    zend_mm_heap *old_heap;
2413
2414    old_heap = AG(mm_heap);
2415    AG(mm_heap) = (zend_mm_heap*)new_heap;
2416    return (zend_mm_heap*)old_heap;
2417}
2418
2419ZEND_API void zend_mm_set_custom_handlers(zend_mm_heap *heap,
2420                                          void* (*_malloc)(size_t),
2421                                          void  (*_free)(void*),
2422                                          void* (*_realloc)(void*, size_t))
2423{
2424#if ZEND_MM_CUSTOM
2425    zend_mm_heap *_heap = (zend_mm_heap*)heap;
2426
2427    _heap->use_custom_heap = 1;
2428    _heap->_malloc = _malloc;
2429    _heap->_free = _free;
2430    _heap->_realloc = _realloc;
2431#endif
2432}
2433
2434ZEND_API void zend_mm_get_custom_handlers(zend_mm_heap *heap,
2435                                          void* (**_malloc)(size_t),
2436                                          void  (**_free)(void*),
2437                                          void* (**_realloc)(void*, size_t))
2438{
2439#if ZEND_MM_CUSTOM
2440    zend_mm_heap *_heap = (zend_mm_heap*)heap;
2441
2442    if (heap->use_custom_heap) {
2443        *_malloc = _heap->_malloc;
2444        *_free = _heap->_free;
2445        *_realloc = _heap->_realloc;
2446    } else {
2447        *_malloc = NULL;
2448        *_free = NULL;
2449        *_realloc = NULL;
2450    }
2451#else
2452    *_malloc = NULL;
2453    *_free = NULL;
2454    *_realloc = NULL;
2455#endif
2456}
2457
2458ZEND_API zend_mm_storage *zend_mm_get_storage(zend_mm_heap *heap)
2459{
2460#if ZEND_MM_CUSTOM
2461    return heap->storage;
2462#else
2463    return NULL
2464#endif
2465}
2466
2467ZEND_API zend_mm_heap *zend_mm_startup(void)
2468{
2469    return zend_mm_init();
2470}
2471
2472ZEND_API zend_mm_heap *zend_mm_startup_ex(zend_mm_storage *storage)
2473{
2474#if ZEND_MM_STORAGE
2475    zend_mm_chunk *chunk = (zend_mm_chunk*)storage->chunk_alloc(storage, ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);
2476    zend_mm_heap *heap;
2477
2478    if (UNEXPECTED(chunk == NULL)) {
2479#if ZEND_MM_ERROR
2480#ifdef _WIN32
2481        stderr_last_error("Can't initialize heap");
2482#else
2483        fprintf(stderr, "\nCan't initialize heap: [%d] %s\n", errno, strerror(errno));
2484#endif
2485#endif
2486        return NULL;
2487    }
2488    heap = &chunk->heap_slot;
2489    chunk->heap = heap;
2490    chunk->next = chunk;
2491    chunk->prev = chunk;
2492    chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
2493    chunk->free_tail = ZEND_MM_FIRST_PAGE;
2494    chunk->num = 0;
2495    chunk->free_map[0] = (Z_L(1) << ZEND_MM_FIRST_PAGE) - 1;
2496    chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
2497    heap->main_chunk = chunk;
2498    heap->cached_chunks = NULL;
2499    heap->chunks_count = 1;
2500    heap->peak_chunks_count = 1;
2501    heap->cached_chunks_count = 0;
2502    heap->avg_chunks_count = 1.0;
2503#if ZEND_MM_STAT || ZEND_MM_LIMIT
2504    heap->real_size = ZEND_MM_CHUNK_SIZE;
2505#endif
2506#if ZEND_MM_STAT
2507    heap->real_peak = ZEND_MM_CHUNK_SIZE;
2508    heap->size = 0;
2509    heap->peak = 0;
2510#endif
2511#if ZEND_MM_LIMIT
2512    heap->limit = (Z_L(-1) >> Z_L(1));
2513    heap->overflow = 0;
2514#endif
2515#if ZEND_MM_CUSTOM
2516    heap->use_custom_heap = 0;
2517#endif
2518    heap->storage = storage;
2519    heap->huge_list = NULL;
2520    return heap;
2521#else
2522    return NULL;
2523#endif
2524}
2525
2526/*
2527 * Local variables:
2528 * tab-width: 4
2529 * c-basic-offset: 4
2530 * indent-tabs-mode: t
2531 * End:
2532 */
2533