zend_gc.c

/*
 +----------------------------------------------------------------------+
 | Zend Engine |
 +----------------------------------------------------------------------+
 | Copyright (c) Zend Technologies Ltd. (http://www.zend.com) |
 +----------------------------------------------------------------------+
 | This source file is subject to version 2.00 of the Zend license, |
 | that is bundled with this package in the file LICENSE, and is |
 | available through the world-wide-web at the following url: |
 | http://www.zend.com/license/2_00.txt. |
 | If you did not receive a copy of the Zend license and are unable to |
 | obtain it through the world-wide-web, please send a note to |
 | license@zend.com so we can mail you a copy immediately. |
 +----------------------------------------------------------------------+
 | Authors: David Wang <planetbeing@gmail.com> |
 | Dmitry Stogov <dmitry@php.net> |
 +----------------------------------------------------------------------+
*/

/**
 * zend_gc_collect_cycles
 * ======================
 *
 * Colors and its meaning
 * ----------------------
 *
 * BLACK (GC_BLACK) - In use or free.
 * GREY (GC_GREY) - Possible member of cycle.
 * WHITE (GC_WHITE) - Member of garbage cycle.
 * PURPLE (GC_PURPLE) - Possible root of cycle.
 *
 * Colors described in the paper but not used
 * ------------------------------------------
 *
 * GREEN - Acyclic
 * RED - Candidate cycle undergoing
 * ORANGE - Candidate cycle awaiting epoch boundary.
 *
 *
 * Flow
 * =====
 *
 * The garbage collect cycle starts from 'gc_mark_roots', which traverses the
 * possible roots, and calls mark_grey for roots are marked purple with
 * depth-first traverse.
 *
 * After all possible roots are traversed and marked,
 * gc_scan_roots will be called, and each root will be called with
 * gc_scan(root->ref)
 *
 * gc_scan checks the colors of possible members.
 *
 * If the node is marked as grey and the refcount > 0
 * gc_scan_black will be called on that node to scan it's subgraph.
 * otherwise (refcount == 0), it marks the node white.
 *
 * A node MAY be added to possible roots when ZEND_UNSET_VAR happens or
 * zend_assign_to_variable is called only when possible garbage node is
 * produced.
 * gc_possible_root() will be called to add the nodes to possible roots.
 *
 *
 * For objects, we call their get_gc handler (by default 'zend_std_get_gc') to
 * get the object properties to scan.
 *
 *
 * @see http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf
 */
#include"zend.h"
#include"zend_API.h"
#include"zend_compile.h"
#include"zend_errors.h"
#include"zend_fibers.h"
#include"zend_hrtime.h"
#include"zend_portability.h"
#include"zend_types.h"
#include"zend_weakrefs.h"
#include"zend_string.h"

#ifndefGC_BENCH
# defineGC_BENCH 0
#endif

#ifndefZEND_GC_DEBUG
# defineZEND_GC_DEBUG 0
#endif

/* GC_INFO layout */
#defineGC_ADDRESS 0x0fffffu
#defineGC_COLOR 0x300000u

#defineGC_BLACK 0x000000u /* must be zero */
#defineGC_WHITE 0x100000u
#defineGC_GREY 0x200000u
#defineGC_PURPLE 0x300000u

/* Debug tracing */
#ifZEND_GC_DEBUG>1
# defineGC_TRACE(format, ...) fprintf(stderr, format "\n", ##__VA_ARGS__);
# defineGC_TRACE_REF(ref, format, ...) \
 do { \
 gc_trace_ref((zend_refcounted *) ref); \
 fprintf(stderr, format "\n", ##__VA_ARGS__); \
 } while (0)
# defineGC_TRACE_SET_COLOR(ref, color) \
 GC_TRACE_REF(ref, "->%s", gc_color_name(color))
#else
# defineGC_TRACE_REF(ref, format, ...)
# defineGC_TRACE_SET_COLOR(ref, new_color)
# defineGC_TRACE(str)
#endif

/* GC_INFO access */
#defineGC_REF_ADDRESS(ref) \
 (((GC_TYPE_INFO(ref)) & (GC_ADDRESS << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)

#defineGC_REF_COLOR(ref) \
 (((GC_TYPE_INFO(ref)) & (GC_COLOR << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)

#defineGC_REF_CHECK_COLOR(ref, color) \
 ((GC_TYPE_INFO(ref) & (GC_COLOR << GC_INFO_SHIFT)) == ((color) << GC_INFO_SHIFT))

#defineGC_REF_SET_INFO(ref, info) do { \
 GC_TYPE_INFO(ref) = \
 (GC_TYPE_INFO(ref) & (GC_TYPE_MASK | GC_FLAGS_MASK)) | \
 ((info) << GC_INFO_SHIFT); \
 } while (0)

#defineGC_REF_SET_COLOR(ref, c) do { \
 GC_TRACE_SET_COLOR(ref, c); \
 GC_TYPE_INFO(ref) = \
 (GC_TYPE_INFO(ref) & ~(GC_COLOR << GC_INFO_SHIFT)) | \
 ((c) << GC_INFO_SHIFT); \
 } while (0)

#defineGC_REF_SET_BLACK(ref) do { \
 GC_TRACE_SET_COLOR(ref, GC_BLACK); \
 GC_TYPE_INFO(ref) &= ~(GC_COLOR << GC_INFO_SHIFT); \
 } while (0)

#defineGC_REF_SET_PURPLE(ref) do { \
 GC_TRACE_SET_COLOR(ref, GC_PURPLE); \
 GC_TYPE_INFO(ref) |= (GC_COLOR << GC_INFO_SHIFT); \
 } while (0)

/* bit stealing tags for gc_root_buffer.ref */
#defineGC_BITS 0x3

#defineGC_ROOT 0x0 /* possible root of circular garbage */
#defineGC_UNUSED 0x1 /* part of linked list of unused buffers */
#defineGC_GARBAGE 0x2 /* garbage to delete */
#defineGC_DTOR_GARBAGE 0x3 /* garbage on which only the dtor should be invoked */

#defineGC_GET_PTR(ptr) \
 ((void*)(((uintptr_t)(ptr)) & ~GC_BITS))

#defineGC_IS_ROOT(ptr) \
 ((((uintptr_t)(ptr)) & GC_BITS) == GC_ROOT)
#defineGC_IS_UNUSED(ptr) \
 ((((uintptr_t)(ptr)) & GC_BITS) == GC_UNUSED)
#defineGC_IS_GARBAGE(ptr) \
 ((((uintptr_t)(ptr)) & GC_BITS) == GC_GARBAGE)
#defineGC_IS_DTOR_GARBAGE(ptr) \
 ((((uintptr_t)(ptr)) & GC_BITS) == GC_DTOR_GARBAGE)

#defineGC_MAKE_GARBAGE(ptr) \
 ((void*)(((uintptr_t)(ptr)) | GC_GARBAGE))
#defineGC_MAKE_DTOR_GARBAGE(ptr) \
 ((void*)(((uintptr_t)(ptr)) | GC_DTOR_GARBAGE))

/* GC address conversion */
#defineGC_IDX2PTR(idx) (GC_G(buf) + (idx))
#defineGC_PTR2IDX(ptr) ((ptr) - GC_G(buf))

#defineGC_IDX2LIST(idx) ((void*)(uintptr_t)(((idx) * sizeof(void*)) | GC_UNUSED))
#defineGC_LIST2IDX(list) (((uint32_t)(uintptr_t)(list)) / sizeof(void*))

/* GC buffers */
#defineGC_INVALID 0
#defineGC_FIRST_ROOT 1

#defineGC_DEFAULT_BUF_SIZE (16 * 1024)
#defineGC_BUF_GROW_STEP (128 * 1024)

#defineGC_MAX_UNCOMPRESSED (512 * 1024)
#defineGC_MAX_BUF_SIZE 0x40000000

#defineGC_THRESHOLD_DEFAULT (10000 + GC_FIRST_ROOT)
#defineGC_THRESHOLD_STEP 10000
#defineGC_THRESHOLD_MAX 1000000000
#defineGC_THRESHOLD_TRIGGER 100

/* GC flags */
#defineGC_HAS_DESTRUCTORS (1<<0)

/* Weak maps */
#defineZ_FROM_WEAKMAP_KEY (1<<0)
#defineZ_FROM_WEAKMAP (1<<1)

/* The WeakMap entry zv is reachable from roots by following the virtual
 * reference from the a WeakMap key to the entry */
#defineGC_FROM_WEAKMAP_KEY(zv) \
 (Z_TYPE_INFO_P((zv)) & (Z_FROM_WEAKMAP_KEY << Z_TYPE_INFO_EXTRA_SHIFT))

#defineGC_SET_FROM_WEAKMAP_KEY(zv) do { \
 zval *_z = (zv); \
 Z_TYPE_INFO_P(_z) = Z_TYPE_INFO_P(_z) | (Z_FROM_WEAKMAP_KEY << Z_TYPE_INFO_EXTRA_SHIFT); \
} while (0)

#defineGC_UNSET_FROM_WEAKMAP_KEY(zv) do { \
 zval *_z = (zv); \
 Z_TYPE_INFO_P(_z) = Z_TYPE_INFO_P(_z) & ~(Z_FROM_WEAKMAP_KEY << Z_TYPE_INFO_EXTRA_SHIFT); \
} while (0)

/* The WeakMap entry zv is reachable from roots by following the reference from
 * the WeakMap */
#defineGC_FROM_WEAKMAP(zv) \
 (Z_TYPE_INFO_P((zv)) & (Z_FROM_WEAKMAP << Z_TYPE_INFO_EXTRA_SHIFT))

#defineGC_SET_FROM_WEAKMAP(zv) do { \
 zval *_z = (zv); \
 Z_TYPE_INFO_P(_z) = Z_TYPE_INFO_P(_z) | (Z_FROM_WEAKMAP << Z_TYPE_INFO_EXTRA_SHIFT); \
} while (0)

#defineGC_UNSET_FROM_WEAKMAP(zv) do { \
 zval *_z = (zv); \
 Z_TYPE_INFO_P(_z) = Z_TYPE_INFO_P(_z) & ~(Z_FROM_WEAKMAP << Z_TYPE_INFO_EXTRA_SHIFT); \
} while (0)

/* unused buffers */
#defineGC_HAS_UNUSED() \
 (GC_G(unused) != GC_INVALID)
#defineGC_FETCH_UNUSED() \
 gc_fetch_unused()
#defineGC_LINK_UNUSED(root) \
 gc_link_unused(root)

#defineGC_HAS_NEXT_UNUSED_UNDER_THRESHOLD() \
 (GC_G(first_unused) < GC_G(gc_threshold))
#defineGC_HAS_NEXT_UNUSED() \
 (GC_G(first_unused) != GC_G(buf_size))
#defineGC_FETCH_NEXT_UNUSED() \
 gc_fetch_next_unused()

ZEND_APIint (*gc_collect_cycles)(void);

typedefstruct_gc_root_buffer {
zend_refcounted*ref;
} gc_root_buffer;

typedefstruct_zend_gc_globals {
gc_root_buffer*buf; /* preallocated arrays of buffers */

boolgc_enabled;
boolgc_active; /* GC currently running, forbid nested GC */
boolgc_protected; /* GC protected, forbid root additions */
boolgc_full;

uint32_tunused; /* linked list of unused buffers */
uint32_tfirst_unused; /* first unused buffer */
uint32_tgc_threshold; /* GC collection threshold */
uint32_tbuf_size; /* size of the GC buffer */
uint32_tnum_roots; /* number of roots in GC buffer */

uint32_tgc_runs;
uint32_tcollected;

zend_hrtime_tactivated_at;
zend_hrtime_tcollector_time;
zend_hrtime_tdtor_time;
zend_hrtime_tfree_time;

uint32_tdtor_idx; /* root buffer index */
uint32_tdtor_end;
zend_fiber*dtor_fiber;
booldtor_fiber_running;

#ifGC_BENCH
uint32_troot_buf_length;
uint32_troot_buf_peak;
uint32_tzval_possible_root;
uint32_tzval_buffered;
uint32_tzval_remove_from_buffer;
uint32_tzval_marked_grey;
#endif
} zend_gc_globals;

#ifdefZTS
staticintgc_globals_id;
staticsize_tgc_globals_offset;
#defineGC_G(v) ZEND_TSRMG_FAST(gc_globals_offset, zend_gc_globals *, v)
#else
#defineGC_G(v) (gc_globals.v)
staticzend_gc_globalsgc_globals;
#endif

#ifGC_BENCH
# defineGC_BENCH_INC(counter) GC_G(counter)++
# defineGC_BENCH_DEC(counter) GC_G(counter)--
# defineGC_BENCH_PEAK(peak, counter) do { \
 if (GC_G(counter) > GC_G(peak)) { \
 GC_G(peak) = GC_G(counter); \
 } \
 } while (0)
#else
# defineGC_BENCH_INC(counter)
# defineGC_BENCH_DEC(counter)
# defineGC_BENCH_PEAK(peak, counter)
#endif


#defineGC_STACK_SEGMENT_SIZE (((4096 - ZEND_MM_OVERHEAD) / sizeof(void*)) - 2)

typedefstruct_gc_stackgc_stack;

struct_gc_stack {
gc_stack*prev;
gc_stack*next;
zend_refcounted*data[GC_STACK_SEGMENT_SIZE];
};

#defineGC_STACK_DCL(init) \
 gc_stack *_stack = init; \
 size_t _top = 0;

#defineGC_STACK_PUSH(ref) \
 gc_stack_push(&_stack, &_top, ref);

#defineGC_STACK_POP() \
 gc_stack_pop(&_stack, &_top)

staticzend_never_inlinegc_stack*gc_stack_next(gc_stack*stack)
{
if (UNEXPECTED(!stack->next)) {
gc_stack*segment=emalloc(sizeof(gc_stack));
segment->prev=stack;
segment->next=NULL;
stack->next=segment;
 }
returnstack->next;
}

staticzend_always_inlinevoidgc_stack_push(gc_stack**stack, size_t*top, zend_refcounted*ref)
{
if (UNEXPECTED(*top==GC_STACK_SEGMENT_SIZE)) {
 (*stack) =gc_stack_next(*stack);
 (*top) =0;
 }
 (*stack)->data[(*top)++] =ref;
}

staticzend_always_inlinezend_refcounted*gc_stack_pop(gc_stack**stack, size_t*top)
{
if (UNEXPECTED((*top) ==0)) {
if (!(*stack)->prev) {
returnNULL;
 } else {
 (*stack) = (*stack)->prev;
 (*top) =GC_STACK_SEGMENT_SIZE-1;
return (*stack)->data[GC_STACK_SEGMENT_SIZE-1];
 }
 } else {
return (*stack)->data[--(*top)];
 }
}

staticvoidgc_stack_free(gc_stack*stack)
{
gc_stack*p=stack->next;

while (p) {
stack=p->next;
efree(p);
p=stack;
 }
}

staticzend_always_inlineuint32_tgc_compress(uint32_tidx)
{
if (EXPECTED(idx<GC_MAX_UNCOMPRESSED)) {
returnidx;
 }
return (idx % GC_MAX_UNCOMPRESSED) | GC_MAX_UNCOMPRESSED;
}

staticzend_always_inlinegc_root_buffer*gc_decompress(zend_refcounted*ref, uint32_tidx)
{
gc_root_buffer*root=GC_IDX2PTR(idx);

if (EXPECTED(GC_GET_PTR(root->ref) ==ref)) {
returnroot;
 }

while (1) {
idx+=GC_MAX_UNCOMPRESSED;
ZEND_ASSERT(idx<GC_G(first_unused));
root=GC_IDX2PTR(idx);
if (GC_GET_PTR(root->ref) ==ref) {
returnroot;
 }
 }
}

staticzend_always_inlineuint32_tgc_fetch_unused(void)
{
uint32_tidx;
gc_root_buffer*root;

ZEND_ASSERT(GC_HAS_UNUSED());
idx=GC_G(unused);
root=GC_IDX2PTR(idx);
ZEND_ASSERT(GC_IS_UNUSED(root->ref));
GC_G(unused) =GC_LIST2IDX(root->ref);
returnidx;
}

staticzend_always_inlinevoidgc_link_unused(gc_root_buffer*root)
{
root->ref=GC_IDX2LIST(GC_G(unused));
GC_G(unused) =GC_PTR2IDX(root);
}

staticzend_always_inlineuint32_tgc_fetch_next_unused(void)
{
uint32_tidx;

ZEND_ASSERT(GC_HAS_NEXT_UNUSED());
idx=GC_G(first_unused);
GC_G(first_unused) =GC_G(first_unused) +1;
returnidx;
}

#ifZEND_GC_DEBUG>1
staticconstchar*gc_color_name(uint32_tcolor) {
switch (color) {
caseGC_BLACK: return"black";
caseGC_WHITE: return"white";
caseGC_GREY: return"grey";
caseGC_PURPLE: return"purple";
default: return"unknown";
 }
}
staticvoidgc_trace_ref(zend_refcounted*ref) {
if (GC_TYPE(ref) ==IS_OBJECT) {
zend_object*obj= (zend_object*) ref;
fprintf(stderr, "[%p] rc=%d addr=%d %s object(%s)#%d ",
ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
gc_color_name(GC_REF_COLOR(ref)),
obj->ce->name->val, obj->handle);
 } elseif (GC_TYPE(ref) ==IS_ARRAY) {
zend_array*arr= (zend_array*) ref;
fprintf(stderr, "[%p] rc=%d addr=%d %s array(%d) ",
ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
gc_color_name(GC_REF_COLOR(ref)),
zend_hash_num_elements(arr));
 } else {
fprintf(stderr, "[%p] rc=%d addr=%d %s %s ",
ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
gc_color_name(GC_REF_COLOR(ref)),
GC_TYPE(ref) ==IS_REFERENCE
 ? "reference" : zend_get_type_by_const(GC_TYPE(ref)));
 }
}
#endif

staticzend_always_inlinevoidgc_remove_from_roots(gc_root_buffer*root)
{
GC_LINK_UNUSED(root);
GC_G(num_roots)--;
GC_BENCH_DEC(root_buf_length);
}

staticvoidroot_buffer_dtor(zend_gc_globals*gc_globals)
{
if (gc_globals->buf) {
free(gc_globals->buf);
gc_globals->buf=NULL;
 }
}

staticvoidgc_globals_ctor_ex(zend_gc_globals*gc_globals)
{
gc_globals->gc_enabled=0;
gc_globals->gc_active=0;
gc_globals->gc_protected=1;
gc_globals->gc_full=0;

gc_globals->buf=NULL;
gc_globals->unused=GC_INVALID;
gc_globals->first_unused=GC_INVALID;
gc_globals->gc_threshold=GC_INVALID;
gc_globals->buf_size=GC_INVALID;
gc_globals->num_roots=0;

gc_globals->gc_runs=0;
gc_globals->collected=0;
gc_globals->collector_time=0;
gc_globals->dtor_time=0;
gc_globals->free_time=0;
gc_globals->activated_at=0;

gc_globals->dtor_idx=GC_FIRST_ROOT;
gc_globals->dtor_end=0;
gc_globals->dtor_fiber=NULL;
gc_globals->dtor_fiber_running= false;

#ifGC_BENCH
gc_globals->root_buf_length=0;
gc_globals->root_buf_peak=0;
gc_globals->zval_possible_root=0;
gc_globals->zval_buffered=0;
gc_globals->zval_remove_from_buffer=0;
gc_globals->zval_marked_grey=0;
#endif
}

voidgc_globals_ctor(void)
{
#ifdefZTS
ts_allocate_fast_id(&gc_globals_id, &gc_globals_offset, sizeof(zend_gc_globals), (ts_allocate_ctor) gc_globals_ctor_ex, (ts_allocate_dtor) root_buffer_dtor);
#else
gc_globals_ctor_ex(&gc_globals);
#endif
}

voidgc_globals_dtor(void)
{
#ifndefZTS
root_buffer_dtor(&gc_globals);
#endif
}

voidgc_reset(void)
{
if (GC_G(buf)) {
GC_G(gc_active) =0;
GC_G(gc_protected) =0;
GC_G(gc_full) =0;
GC_G(unused) =GC_INVALID;
GC_G(first_unused) =GC_FIRST_ROOT;
GC_G(num_roots) =0;

GC_G(gc_runs) =0;
GC_G(collected) =0;

GC_G(collector_time) =0;
GC_G(dtor_time) =0;
GC_G(free_time) =0;

GC_G(dtor_idx) =GC_FIRST_ROOT;
GC_G(dtor_end) =0;
GC_G(dtor_fiber) =NULL;
GC_G(dtor_fiber_running) = false;

#ifGC_BENCH
GC_G(root_buf_length) =0;
GC_G(root_buf_peak) =0;
GC_G(zval_possible_root) =0;
GC_G(zval_buffered) =0;
GC_G(zval_remove_from_buffer) =0;
GC_G(zval_marked_grey) =0;
#endif
 }

GC_G(activated_at) =zend_hrtime();
}

ZEND_APIboolgc_enable(boolenable)
{
boolold_enabled=GC_G(gc_enabled);
GC_G(gc_enabled) =enable;
if (enable&& !old_enabled&&GC_G(buf) ==NULL) {
GC_G(buf) = (gc_root_buffer*) pemalloc(sizeof(gc_root_buffer) *GC_DEFAULT_BUF_SIZE, 1);
GC_G(buf)[0].ref=NULL;
GC_G(buf_size) =GC_DEFAULT_BUF_SIZE;
GC_G(gc_threshold) =GC_THRESHOLD_DEFAULT;
gc_reset();
 }
returnold_enabled;
}

ZEND_APIboolgc_enabled(void)
{
returnGC_G(gc_enabled);
}

ZEND_APIboolgc_protect(boolprotect)
{
boolold_protected=GC_G(gc_protected);
GC_G(gc_protected) =protect;
returnold_protected;
}

ZEND_APIboolgc_protected(void)
{
returnGC_G(gc_protected);
}

staticvoidgc_grow_root_buffer(void)
{
size_tnew_size;

if (GC_G(buf_size) >= GC_MAX_BUF_SIZE) {
if (!GC_G(gc_full)) {
zend_error(E_WARNING, "GC buffer overflow (GC disabled)\n");
GC_G(gc_active) =1;
GC_G(gc_protected) =1;
GC_G(gc_full) =1;
return;
 }
 }
if (GC_G(buf_size) <GC_BUF_GROW_STEP) {
new_size=GC_G(buf_size) *2;
 } else {
new_size=GC_G(buf_size) +GC_BUF_GROW_STEP;
 }
if (new_size>GC_MAX_BUF_SIZE) {
new_size=GC_MAX_BUF_SIZE;
 }
GC_G(buf) =perealloc(GC_G(buf), sizeof(gc_root_buffer) *new_size, 1);
GC_G(buf_size) =new_size;
}

staticvoidgc_adjust_threshold(intcount)
{
uint32_tnew_threshold;

/* TODO Very simple heuristic for dynamic GC buffer resizing:
 * If there are "too few" collections, increase the collection threshold
 * by a fixed step */
if (count<GC_THRESHOLD_TRIGGER||GC_G(num_roots) >= GC_G(gc_threshold)) {
/* increase */
if (GC_G(gc_threshold) <GC_THRESHOLD_MAX) {
new_threshold=GC_G(gc_threshold) +GC_THRESHOLD_STEP;
if (new_threshold>GC_THRESHOLD_MAX) {
new_threshold=GC_THRESHOLD_MAX;
 }
if (new_threshold>GC_G(buf_size)) {
gc_grow_root_buffer();
 }
if (new_threshold <= GC_G(buf_size)) {
GC_G(gc_threshold) =new_threshold;
 }
 }
 } elseif (GC_G(gc_threshold) >GC_THRESHOLD_DEFAULT) {
new_threshold=GC_G(gc_threshold) -GC_THRESHOLD_STEP;
if (new_threshold<GC_THRESHOLD_DEFAULT) {
new_threshold=GC_THRESHOLD_DEFAULT;
 }
GC_G(gc_threshold) =new_threshold;
 }
}

staticzend_never_inlinevoidZEND_FASTCALLgc_possible_root_when_full(zend_refcounted*ref)
{
uint32_tidx;
gc_root_buffer*newRoot;

ZEND_ASSERT(GC_TYPE(ref) ==IS_ARRAY||GC_TYPE(ref) ==IS_OBJECT);
ZEND_ASSERT(GC_INFO(ref) ==0);

if (GC_G(gc_enabled) && !GC_G(gc_active)) {
GC_ADDREF(ref);
gc_adjust_threshold(gc_collect_cycles());
if (UNEXPECTED(GC_DELREF(ref) ==0)) {
rc_dtor_func(ref);
return;
 } elseif (UNEXPECTED(GC_INFO(ref))) {
return;
 }
 }

if (GC_HAS_UNUSED()) {
idx=GC_FETCH_UNUSED();
 } elseif (EXPECTED(GC_HAS_NEXT_UNUSED())) {
idx=GC_FETCH_NEXT_UNUSED();
 } else {
gc_grow_root_buffer();
if (UNEXPECTED(!GC_HAS_NEXT_UNUSED())) {
return;
 }
idx=GC_FETCH_NEXT_UNUSED();
 }

newRoot=GC_IDX2PTR(idx);
newRoot->ref=ref; /* GC_ROOT tag is 0 */
GC_TRACE_SET_COLOR(ref, GC_PURPLE);

idx=gc_compress(idx);
GC_REF_SET_INFO(ref, idx | GC_PURPLE);
GC_G(num_roots)++;

GC_BENCH_INC(zval_buffered);
GC_BENCH_INC(root_buf_length);
GC_BENCH_PEAK(root_buf_peak, root_buf_length);
}

ZEND_APIvoidZEND_FASTCALLgc_possible_root(zend_refcounted*ref)
{
uint32_tidx;
gc_root_buffer*newRoot;

if (UNEXPECTED(GC_G(gc_protected))) {
return;
 }

GC_BENCH_INC(zval_possible_root);

if (EXPECTED(GC_HAS_UNUSED())) {
idx=GC_FETCH_UNUSED();
 } elseif (EXPECTED(GC_HAS_NEXT_UNUSED_UNDER_THRESHOLD())) {
idx=GC_FETCH_NEXT_UNUSED();
 } else {
gc_possible_root_when_full(ref);
return;
 }

ZEND_ASSERT(GC_TYPE(ref) ==IS_ARRAY||GC_TYPE(ref) ==IS_OBJECT);
ZEND_ASSERT(GC_INFO(ref) ==0);

newRoot=GC_IDX2PTR(idx);
newRoot->ref=ref; /* GC_ROOT tag is 0 */
GC_TRACE_SET_COLOR(ref, GC_PURPLE);

idx=gc_compress(idx);
GC_REF_SET_INFO(ref, idx | GC_PURPLE);
GC_G(num_roots)++;

GC_BENCH_INC(zval_buffered);
GC_BENCH_INC(root_buf_length);
GC_BENCH_PEAK(root_buf_peak, root_buf_length);
}

staticvoidZEND_FASTCALLgc_extra_root(zend_refcounted*ref)
{
uint32_tidx;
gc_root_buffer*newRoot;

if (EXPECTED(GC_HAS_UNUSED())) {
idx=GC_FETCH_UNUSED();
 } elseif (EXPECTED(GC_HAS_NEXT_UNUSED())) {
idx=GC_FETCH_NEXT_UNUSED();
 } else {
gc_grow_root_buffer();
if (UNEXPECTED(!GC_HAS_NEXT_UNUSED())) {
/* TODO: can this really happen? */
return;
 }
idx=GC_FETCH_NEXT_UNUSED();
 }

ZEND_ASSERT(GC_TYPE(ref) ==IS_ARRAY||GC_TYPE(ref) ==IS_OBJECT);
ZEND_ASSERT(GC_REF_ADDRESS(ref) ==0);

newRoot=GC_IDX2PTR(idx);
newRoot->ref=ref; /* GC_ROOT tag is 0 */

idx=gc_compress(idx);
GC_REF_SET_INFO(ref, idx | GC_REF_COLOR(ref));
GC_G(num_roots)++;

GC_BENCH_INC(zval_buffered);
GC_BENCH_INC(root_buf_length);
GC_BENCH_PEAK(root_buf_peak, root_buf_length);
}

staticzend_never_inlinevoidZEND_FASTCALLgc_remove_compressed(zend_refcounted*ref, uint32_tidx)
{
gc_root_buffer*root=gc_decompress(ref, idx);
gc_remove_from_roots(root);
}

ZEND_APIvoidZEND_FASTCALLgc_remove_from_buffer(zend_refcounted*ref)
{
gc_root_buffer*root;
uint32_tidx=GC_REF_ADDRESS(ref);

GC_BENCH_INC(zval_remove_from_buffer);

if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_TRACE_SET_COLOR(ref, GC_BLACK);
 }
GC_REF_SET_INFO(ref, 0);

/* Perform decompression only in case of large buffers */
if (UNEXPECTED(GC_G(first_unused) >= GC_MAX_UNCOMPRESSED)) {
gc_remove_compressed(ref, idx);
return;
 }

ZEND_ASSERT(idx);
root=GC_IDX2PTR(idx);
gc_remove_from_roots(root);
}

staticvoidgc_scan_black(zend_refcounted*ref, gc_stack*stack)
{
HashTable*ht;
Bucket*p;
zval*zv;
uint32_tn;
GC_STACK_DCL(stack);

tail_call:
if (GC_TYPE(ref) ==IS_OBJECT) {
zend_object*obj= (zend_object*)ref;

if (EXPECTED(!(OBJ_FLAGS(ref) &IS_OBJ_FREE_CALLED))) {
zval*table;
intlen;

if (UNEXPECTED(GC_FLAGS(obj) &IS_OBJ_WEAKLY_REFERENCED)) {
zend_weakmap_get_object_key_entry_gc(obj, &table, &len);
n=len;
zv=table;
for (; n!=0; n-=2) {
ZEND_ASSERT(Z_TYPE_P(zv) ==IS_PTR);
zval*entry= (zval*) Z_PTR_P(zv);
zval*weakmap=zv+1;
ZEND_ASSERT(Z_REFCOUNTED_P(weakmap));
if (Z_OPT_REFCOUNTED_P(entry)) {
GC_UNSET_FROM_WEAKMAP_KEY(entry);
if (GC_REF_CHECK_COLOR(Z_COUNTED_P(weakmap), GC_GREY)) {
/* Weakmap was scanned in gc_mark_roots, we must
 * ensure that it's eventually scanned in
 * gc_scan_roots as well. */
if (!GC_REF_ADDRESS(Z_COUNTED_P(weakmap))) {
gc_extra_root(Z_COUNTED_P(weakmap));
 }
 } elseif (/* GC_REF_CHECK_COLOR(Z_COUNTED_P(weakmap), GC_BLACK) && */ !GC_FROM_WEAKMAP(entry)) {
/* Both the entry weakmap and key are BLACK, so we
 * can mark the entry BLACK as well.
 * !GC_FROM_WEAKMAP(entry) means that the weakmap
 * was already scanned black (or will not be
 * scanned), so it's our responsibility to mark the
 * entry */
ZEND_ASSERT(GC_REF_CHECK_COLOR(Z_COUNTED_P(weakmap), GC_BLACK));
ref=Z_COUNTED_P(entry);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
GC_STACK_PUSH(ref);
 }
 }
 }
zv+=2;
 }
 }

if (UNEXPECTED(obj->handlers->get_gc==zend_weakmap_get_gc)) {
zend_weakmap_get_key_entry_gc(obj, &table, &len);
n=len;
zv=table;
for (; n!=0; n-=2) {
ZEND_ASSERT(Z_TYPE_P(zv+1) ==IS_PTR);
zval*key=zv;
zval*entry= (zval*) Z_PTR_P(zv+1);
if (Z_OPT_REFCOUNTED_P(entry)) {
GC_UNSET_FROM_WEAKMAP(entry);
if (GC_REF_CHECK_COLOR(Z_COUNTED_P(key), GC_GREY)) {
/* Key was scanned in gc_mark_roots, we must
 * ensure that it's eventually scanned in
 * gc_scan_roots as well. */
if (!GC_REF_ADDRESS(Z_COUNTED_P(key))) {
gc_extra_root(Z_COUNTED_P(key));
 }
 } elseif (/* GC_REF_CHECK_COLOR(Z_COUNTED_P(key), GC_BLACK) && */ !GC_FROM_WEAKMAP_KEY(entry)) {
/* Both the entry weakmap and key are BLACK, so we
 * can mark the entry BLACK as well.
 * !GC_FROM_WEAKMAP_KEY(entry) means that the key
 * was already scanned black (or will not be
 * scanned), so it's our responsibility to mark the
 * entry */
ZEND_ASSERT(GC_REF_CHECK_COLOR(Z_COUNTED_P(key), GC_BLACK));
ref=Z_COUNTED_P(entry);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
GC_STACK_PUSH(ref);
 }
 }
 }
zv+=2;
 }
 goto next;
 }

ht=obj->handlers->get_gc(obj, &table, &len);
n=len;
zv=table;
if (UNEXPECTED(ht)) {
GC_ADDREF(ht);
if (!GC_REF_CHECK_COLOR(ht, GC_BLACK)) {
GC_REF_SET_BLACK(ht);
for (; n!=0; n--) {
if (Z_REFCOUNTED_P(zv)) {
ref=Z_COUNTED_P(zv);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
GC_STACK_PUSH(ref);
 }
 }
zv++;
 }
 goto handle_ht;
 }
 }

handle_zvals:
for (; n!=0; n--) {
if (Z_REFCOUNTED_P(zv)) {
ref=Z_COUNTED_P(zv);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
zv++;
while (--n) {
if (Z_REFCOUNTED_P(zv)) {
zend_refcounted*ref=Z_COUNTED_P(zv);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
GC_STACK_PUSH(ref);
 }
 }
zv++;
 }
 goto tail_call;
 }
 }
zv++;
 }
 }
 } elseif (GC_TYPE(ref) ==IS_ARRAY) {
ZEND_ASSERT((zend_array*)ref!=&EG(symbol_table));
ht= (zend_array*)ref;
handle_ht:
n=ht->nNumUsed;
zv=ht->arPacked;
if (HT_IS_PACKED(ht)) {
 goto handle_zvals;
 }

p= (Bucket*)zv;
for (; n!=0; n--) {
zv=&p->val;
if (Z_TYPE_P(zv) ==IS_INDIRECT) {
zv=Z_INDIRECT_P(zv);
 }
if (Z_REFCOUNTED_P(zv)) {
ref=Z_COUNTED_P(zv);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
p++;
while (--n) {
zv=&p->val;
if (Z_TYPE_P(zv) ==IS_INDIRECT) {
zv=Z_INDIRECT_P(zv);
 }
if (Z_REFCOUNTED_P(zv)) {
zend_refcounted*ref=Z_COUNTED_P(zv);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
GC_STACK_PUSH(ref);
 }
 }
p++;
 }
 goto tail_call;
 }
 }
p++;
 }
 } elseif (GC_TYPE(ref) ==IS_REFERENCE) {
if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
ref=Z_COUNTED(((zend_reference*)ref)->val);
GC_ADDREF(ref);
if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
GC_REF_SET_BLACK(ref);
 goto tail_call;
 }
 }
 }

next:
ref=GC_STACK_POP();
if (ref) {
 goto tail_call;
 }
}

staticvoidgc_mark_grey(zend_refcounted*ref, gc_stack*stack)
{
HashTable*ht;
Bucket*p;
zval*zv;
uint32_tn;