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