xref: /PHP-7.4/Zend/zend_gc.c (revision b037fe5b)
16847c181SDmitry Stogov /*
26847c181SDmitry Stogov    +----------------------------------------------------------------------+
36847c181SDmitry Stogov    | Zend Engine                                                          |
46847c181SDmitry Stogov    +----------------------------------------------------------------------+
5a81202acSZeev Suraski    | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |
66847c181SDmitry Stogov    +----------------------------------------------------------------------+
76847c181SDmitry Stogov    | This source file is subject to version 2.00 of the Zend license,     |
86847c181SDmitry Stogov    | that is bundled with this package in the file LICENSE, and is        |
96847c181SDmitry Stogov    | available through the world-wide-web at the following url:           |
106847c181SDmitry Stogov    | http://www.zend.com/license/2_00.txt.                                |
116847c181SDmitry Stogov    | If you did not receive a copy of the Zend license and are unable to  |
126847c181SDmitry Stogov    | obtain it through the world-wide-web, please send a note to          |
136847c181SDmitry Stogov    | license@zend.com so we can mail you a copy immediately.              |
146847c181SDmitry Stogov    +----------------------------------------------------------------------+
156847c181SDmitry Stogov    | Authors: David Wang <planetbeing@gmail.com>                          |
1654dc07f3SZeev Suraski    |          Dmitry Stogov <dmitry@php.net>                              |
176847c181SDmitry Stogov    +----------------------------------------------------------------------+
186847c181SDmitry Stogov */
196847c181SDmitry Stogov 
209288ce53Sc /**
219288ce53Sc  * zend_gc_collect_cycles
229288ce53Sc  * ======================
239288ce53Sc  *
249288ce53Sc  * Colors and its meaning
259288ce53Sc  * ----------------------
269288ce53Sc  *
279288ce53Sc  * BLACK  (GC_BLACK)   - In use or free.
289288ce53Sc  * GREY   (GC_GREY)    - Possible member of cycle.
299288ce53Sc  * WHITE  (GC_WHITE)   - Member of garbage cycle.
309288ce53Sc  * PURPLE (GC_PURPLE)  - Possible root of cycle.
319288ce53Sc  *
329288ce53Sc  * Colors described in the paper but not used
339288ce53Sc  * ------------------------------------------
349288ce53Sc  *
359288ce53Sc  * GREEN - Acyclic
369288ce53Sc  * RED   - Candidate cycle underogin
379288ce53Sc  * ORANGE - Candidate cycle awaiting epoch boundary.
389288ce53Sc  *
399288ce53Sc  *
409288ce53Sc  * Flow
419288ce53Sc  * =====
429288ce53Sc  *
439288ce53Sc  * The garbage collect cycle starts from 'gc_mark_roots', which traverses the
449288ce53Sc  * possible roots, and calls mark_grey for roots are marked purple with
459288ce53Sc  * depth-first traverse.
469288ce53Sc  *
479288ce53Sc  * After all possible roots are traversed and marked,
489288ce53Sc  * gc_scan_roots will be called, and each root will be called with
499288ce53Sc  * gc_scan(root->ref)
509288ce53Sc  *
51da3316ffSTyson Andre  * gc_scan checks the colors of possible members.
529288ce53Sc  *
539288ce53Sc  * If the node is marked as grey and the refcount > 0
549288ce53Sc  *    gc_scan_black will be called on that node to scan it's subgraph.
559288ce53Sc  * otherwise (refcount == 0), it marks the node white.
569288ce53Sc  *
57231feceeSROVAST  * A node MAY be added to possible roots when ZEND_UNSET_VAR happens or
589288ce53Sc  * zend_assign_to_variable is called only when possible garbage node is
599288ce53Sc  * produced.
609288ce53Sc  * gc_possible_root() will be called to add the nodes to possible roots.
619288ce53Sc  *
629288ce53Sc  *
639288ce53Sc  * For objects, we call their get_gc handler (by default 'zend_std_get_gc') to
649288ce53Sc  * get the object properties to scan.
659288ce53Sc  *
669288ce53Sc  *
679288ce53Sc  * @see http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf
689288ce53Sc  */
696847c181SDmitry Stogov #include "zend.h"
706847c181SDmitry Stogov #include "zend_API.h"
716847c181SDmitry Stogov 
72baa98901SDmitry Stogov #ifndef GC_BENCH
73baa98901SDmitry Stogov # define GC_BENCH 0
74baa98901SDmitry Stogov #endif
75baa98901SDmitry Stogov 
76baa98901SDmitry Stogov #ifndef ZEND_GC_DEBUG
77baa98901SDmitry Stogov # define ZEND_GC_DEBUG 0
78baa98901SDmitry Stogov #endif
79baa98901SDmitry Stogov 
80165dadacSDmitry Stogov /* GC_INFO layout */
813d429869SNikita Popov #define GC_ADDRESS  0x0fffffu
823d429869SNikita Popov #define GC_COLOR    0x300000u
83baa98901SDmitry Stogov 
843d429869SNikita Popov #define GC_BLACK    0x000000u /* must be zero */
853d429869SNikita Popov #define GC_WHITE    0x100000u
863d429869SNikita Popov #define GC_GREY     0x200000u
873d429869SNikita Popov #define GC_PURPLE   0x300000u
88baa98901SDmitry Stogov 
8938f10ff5SNikita Popov /* Debug tracing */
9038f10ff5SNikita Popov #if ZEND_GC_DEBUG > 1
9138f10ff5SNikita Popov # define GC_TRACE(format, ...) fprintf(stderr, format "\n", ##__VA_ARGS__);
9238f10ff5SNikita Popov # define GC_TRACE_REF(ref, format, ...) \
9338f10ff5SNikita Popov 	do { \
9438f10ff5SNikita Popov 		gc_trace_ref((zend_refcounted *) ref); \
9538f10ff5SNikita Popov 		fprintf(stderr, format "\n", ##__VA_ARGS__); \
9638f10ff5SNikita Popov 	} while (0)
9738f10ff5SNikita Popov # define GC_TRACE_SET_COLOR(ref, color) \
9838f10ff5SNikita Popov 	GC_TRACE_REF(ref, "->%s", gc_color_name(color))
9938f10ff5SNikita Popov #else
10038f10ff5SNikita Popov # define GC_TRACE_REF(ref, format, ...)
10138f10ff5SNikita Popov # define GC_TRACE_SET_COLOR(ref, new_color)
10238f10ff5SNikita Popov # define GC_TRACE(str)
10338f10ff5SNikita Popov #endif
10438f10ff5SNikita Popov 
105165dadacSDmitry Stogov /* GC_INFO access */
106165dadacSDmitry Stogov #define GC_REF_ADDRESS(ref) \
107165dadacSDmitry Stogov 	(((GC_TYPE_INFO(ref)) & (GC_ADDRESS << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)
108fd348ec4SDmitry Stogov 
109165dadacSDmitry Stogov #define GC_REF_COLOR(ref) \
110165dadacSDmitry Stogov 	(((GC_TYPE_INFO(ref)) & (GC_COLOR << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)
111fd348ec4SDmitry Stogov 
1125994b8acSDmitry Stogov #define GC_REF_CHECK_COLOR(ref, color) \
1135994b8acSDmitry Stogov 	((GC_TYPE_INFO(ref) & (GC_COLOR << GC_INFO_SHIFT)) == ((color) << GC_INFO_SHIFT))
1145994b8acSDmitry Stogov 
115165dadacSDmitry Stogov #define GC_REF_SET_INFO(ref, info) do { \
116165dadacSDmitry Stogov 		GC_TYPE_INFO(ref) = \
117165dadacSDmitry Stogov 			(GC_TYPE_INFO(ref) & (GC_TYPE_MASK | GC_FLAGS_MASK)) | \
118165dadacSDmitry Stogov 			((info) << GC_INFO_SHIFT); \
119165dadacSDmitry Stogov 	} while (0)
120165dadacSDmitry Stogov 
121fd348ec4SDmitry Stogov #define GC_REF_SET_COLOR(ref, c) do { \
12238f10ff5SNikita Popov 		GC_TRACE_SET_COLOR(ref, c); \
1235994b8acSDmitry Stogov 		GC_TYPE_INFO(ref) = \
1245994b8acSDmitry Stogov 			(GC_TYPE_INFO(ref) & ~(GC_COLOR << GC_INFO_SHIFT)) | \
1255994b8acSDmitry Stogov 			((c) << GC_INFO_SHIFT); \
126fd348ec4SDmitry Stogov 	} while (0)
127165dadacSDmitry Stogov 
128fd348ec4SDmitry Stogov #define GC_REF_SET_BLACK(ref) do { \
12938f10ff5SNikita Popov 		GC_TRACE_SET_COLOR(ref, GC_BLACK); \
130fd348ec4SDmitry Stogov 		GC_TYPE_INFO(ref) &= ~(GC_COLOR << GC_INFO_SHIFT); \
131fd348ec4SDmitry Stogov 	} while (0)
132165dadacSDmitry Stogov 
133fd348ec4SDmitry Stogov #define GC_REF_SET_PURPLE(ref) do { \
13438f10ff5SNikita Popov 		GC_TRACE_SET_COLOR(ref, GC_PURPLE); \
135fd348ec4SDmitry Stogov 		GC_TYPE_INFO(ref) |= (GC_COLOR << GC_INFO_SHIFT); \
136fd348ec4SDmitry Stogov 	} while (0)
137fd348ec4SDmitry Stogov 
138fd348ec4SDmitry Stogov /* bit stealing tags for gc_root_buffer.ref */
139fd348ec4SDmitry Stogov #define GC_BITS    0x3
140fd348ec4SDmitry Stogov 
1415c78bb80SDmitry Stogov #define GC_ROOT    0x0 /* possible root of circular garbage     */
142fd348ec4SDmitry Stogov #define GC_UNUSED  0x1 /* part of linked list of unused buffers */
143fd348ec4SDmitry Stogov #define GC_GARBAGE 0x2 /* garbage to delete                     */
14460a7e60bSNikita Popov #define GC_DTOR_GARBAGE 0x3 /* garbage on which only the dtor should be invoked */
145fd348ec4SDmitry Stogov 
146fd348ec4SDmitry Stogov #define GC_GET_PTR(ptr) \
147fd348ec4SDmitry Stogov 	((void*)(((uintptr_t)(ptr)) & ~GC_BITS))
148fd348ec4SDmitry Stogov 
149fd348ec4SDmitry Stogov #define GC_IS_ROOT(ptr) \
150fd348ec4SDmitry Stogov 	((((uintptr_t)(ptr)) & GC_BITS) == GC_ROOT)
151fd348ec4SDmitry Stogov #define GC_IS_UNUSED(ptr) \
152fd348ec4SDmitry Stogov 	((((uintptr_t)(ptr)) & GC_BITS) == GC_UNUSED)
153fd348ec4SDmitry Stogov #define GC_IS_GARBAGE(ptr) \
154fd348ec4SDmitry Stogov 	((((uintptr_t)(ptr)) & GC_BITS) == GC_GARBAGE)
15560a7e60bSNikita Popov #define GC_IS_DTOR_GARBAGE(ptr) \
15660a7e60bSNikita Popov 	((((uintptr_t)(ptr)) & GC_BITS) == GC_DTOR_GARBAGE)
157fd348ec4SDmitry Stogov 
158fd348ec4SDmitry Stogov #define GC_MAKE_GARBAGE(ptr) \
159fd348ec4SDmitry Stogov 	((void*)(((uintptr_t)(ptr)) | GC_GARBAGE))
16060a7e60bSNikita Popov #define GC_MAKE_DTOR_GARBAGE(ptr) \
16160a7e60bSNikita Popov 	((void*)(((uintptr_t)(ptr)) | GC_DTOR_GARBAGE))
162fd348ec4SDmitry Stogov 
163ae64dd6dSDmitry Stogov /* GC address conversion */
164ab139b6bSDmitry Stogov #define GC_IDX2PTR(idx)      (GC_G(buf) + (idx))
165ab139b6bSDmitry Stogov #define GC_PTR2IDX(ptr)      ((ptr) - GC_G(buf))
166ae64dd6dSDmitry Stogov 
167ab139b6bSDmitry Stogov #define GC_IDX2LIST(idx)     ((void*)(uintptr_t)(((idx) * sizeof(void*)) | GC_UNUSED))
168ab139b6bSDmitry Stogov #define GC_LIST2IDX(list)    (((uint32_t)(uintptr_t)(list)) / sizeof(void*))
169ae64dd6dSDmitry Stogov 
170ae64dd6dSDmitry Stogov /* GC buffers */
171ab139b6bSDmitry Stogov #define GC_INVALID           0
172ab139b6bSDmitry Stogov #define GC_FIRST_ROOT        1
173ae64dd6dSDmitry Stogov 
174ae64dd6dSDmitry Stogov #define GC_DEFAULT_BUF_SIZE  (16 * 1024)
175ae64dd6dSDmitry Stogov #define GC_BUF_GROW_STEP     (128 * 1024)
176ae64dd6dSDmitry Stogov 
177193f28c7SNikita Popov #define GC_MAX_UNCOMPRESSED  (512 * 1024)
178ae64dd6dSDmitry Stogov #define GC_MAX_BUF_SIZE      0x40000000
179ae64dd6dSDmitry Stogov 
180ae64dd6dSDmitry Stogov #define GC_THRESHOLD_DEFAULT 10000
181ae64dd6dSDmitry Stogov #define GC_THRESHOLD_STEP    10000
182ae64dd6dSDmitry Stogov #define GC_THRESHOLD_MAX     1000000000
183ae64dd6dSDmitry Stogov #define GC_THRESHOLD_TRIGGER 100
184ae64dd6dSDmitry Stogov 
185ae64dd6dSDmitry Stogov /* GC flags */
186ae64dd6dSDmitry Stogov #define GC_HAS_DESTRUCTORS  (1<<0)
187ae64dd6dSDmitry Stogov 
188fd348ec4SDmitry Stogov /* unused buffers */
189fd348ec4SDmitry Stogov #define GC_HAS_UNUSED() \
190ab139b6bSDmitry Stogov 	(GC_G(unused) != GC_INVALID)
191fd348ec4SDmitry Stogov #define GC_FETCH_UNUSED() \
192fd348ec4SDmitry Stogov 	gc_fetch_unused()
193fd348ec4SDmitry Stogov #define GC_LINK_UNUSED(root) \
194fd348ec4SDmitry Stogov 	gc_link_unused(root)
195fd348ec4SDmitry Stogov 
196fd348ec4SDmitry Stogov #define GC_HAS_NEXT_UNUSED_UNDER_THRESHOLD() \
197fd348ec4SDmitry Stogov 	(GC_G(first_unused) < GC_G(gc_threshold))
198fd348ec4SDmitry Stogov #define GC_HAS_NEXT_UNUSED() \
199fd348ec4SDmitry Stogov 	(GC_G(first_unused) != GC_G(buf_size))
200fd348ec4SDmitry Stogov #define GC_FETCH_NEXT_UNUSED() \
201fd348ec4SDmitry Stogov 	gc_fetch_next_unused()
202baa98901SDmitry Stogov 
203baa98901SDmitry Stogov ZEND_API int (*gc_collect_cycles)(void);
204baa98901SDmitry Stogov 
205baa98901SDmitry Stogov typedef struct _gc_root_buffer {
206fd348ec4SDmitry Stogov 	zend_refcounted  *ref;
207baa98901SDmitry Stogov } gc_root_buffer;
208baa98901SDmitry Stogov 
209baa98901SDmitry Stogov typedef struct _zend_gc_globals {
210824a9333SDmitry Stogov 	gc_root_buffer   *buf;				/* preallocated arrays of buffers   */
211824a9333SDmitry Stogov 
212baa98901SDmitry Stogov 	zend_bool         gc_enabled;
213fd348ec4SDmitry Stogov 	zend_bool         gc_active;        /* GC currently running, forbid nested GC */
214fd348ec4SDmitry Stogov 	zend_bool         gc_protected;     /* GC protected, forbid root additions */
215baa98901SDmitry Stogov 	zend_bool         gc_full;
216baa98901SDmitry Stogov 
217fd348ec4SDmitry Stogov 	uint32_t          unused;			/* linked list of unused buffers    */
218fd348ec4SDmitry Stogov 	uint32_t          first_unused;		/* first unused buffer              */
219ab139b6bSDmitry Stogov 	uint32_t          gc_threshold;     /* GC collection threshold          */
220ab139b6bSDmitry Stogov 	uint32_t          buf_size;			/* size of the GC buffer            */
221fd348ec4SDmitry Stogov 	uint32_t          num_roots;		/* number of roots in GC buffer     */
222baa98901SDmitry Stogov 
223baa98901SDmitry Stogov 	uint32_t gc_runs;
224baa98901SDmitry Stogov 	uint32_t collected;
225baa98901SDmitry Stogov 
226baa98901SDmitry Stogov #if GC_BENCH
227baa98901SDmitry Stogov 	uint32_t root_buf_length;
228baa98901SDmitry Stogov 	uint32_t root_buf_peak;
229baa98901SDmitry Stogov 	uint32_t zval_possible_root;
230baa98901SDmitry Stogov 	uint32_t zval_buffered;
231baa98901SDmitry Stogov 	uint32_t zval_remove_from_buffer;
232baa98901SDmitry Stogov 	uint32_t zval_marked_grey;
2338eaa0988SDmitry Stogov #endif
234baa98901SDmitry Stogov } zend_gc_globals;
235baa98901SDmitry Stogov 
2366847c181SDmitry Stogov #ifdef ZTS
237baa98901SDmitry Stogov static int gc_globals_id;
2389499484eSDmitry Stogov static size_t gc_globals_offset;
2399499484eSDmitry Stogov #define GC_G(v) ZEND_TSRMG_FAST(gc_globals_offset, zend_gc_globals *, v)
2406847c181SDmitry Stogov #else
241baa98901SDmitry Stogov #define GC_G(v) (gc_globals.v)
242baa98901SDmitry Stogov static zend_gc_globals gc_globals;
2436847c181SDmitry Stogov #endif
2446847c181SDmitry Stogov 
245baa98901SDmitry Stogov #if GC_BENCH
246baa98901SDmitry Stogov # define GC_BENCH_INC(counter) GC_G(counter)++
247baa98901SDmitry Stogov # define GC_BENCH_DEC(counter) GC_G(counter)--
248baa98901SDmitry Stogov # define GC_BENCH_PEAK(peak, counter) do {		\
249baa98901SDmitry Stogov 		if (GC_G(counter) > GC_G(peak)) {		\
250baa98901SDmitry Stogov 			GC_G(peak) = GC_G(counter);			\
251baa98901SDmitry Stogov 		}										\
252baa98901SDmitry Stogov 	} while (0)
253baa98901SDmitry Stogov #else
254baa98901SDmitry Stogov # define GC_BENCH_INC(counter)
255baa98901SDmitry Stogov # define GC_BENCH_DEC(counter)
256baa98901SDmitry Stogov # define GC_BENCH_PEAK(peak, counter)
257baa98901SDmitry Stogov #endif
258eb6dc9dbSAdam Harvey 
2595da591c5SDmitry Stogov 
2605da591c5SDmitry Stogov #define GC_STACK_SEGMENT_SIZE (((4096 - ZEND_MM_OVERHEAD) / sizeof(void*)) - 2)
2615da591c5SDmitry Stogov 
2625da591c5SDmitry Stogov typedef struct _gc_stack gc_stack;
2635da591c5SDmitry Stogov 
2645da591c5SDmitry Stogov struct _gc_stack {
2655da591c5SDmitry Stogov 	gc_stack        *prev;
2665da591c5SDmitry Stogov 	gc_stack        *next;
2675da591c5SDmitry Stogov 	zend_refcounted *data[GC_STACK_SEGMENT_SIZE];
2685da591c5SDmitry Stogov };
2695da591c5SDmitry Stogov 
2705da591c5SDmitry Stogov #define GC_STACK_DCL(init) \
2715da591c5SDmitry Stogov 	gc_stack *_stack = init; \
2725da591c5SDmitry Stogov 	size_t    _top = 0;
2735da591c5SDmitry Stogov 
2745da591c5SDmitry Stogov #define GC_STACK_PUSH(ref) \
2755da591c5SDmitry Stogov 	gc_stack_push(&_stack, &_top, ref);
2765da591c5SDmitry Stogov 
2775da591c5SDmitry Stogov #define GC_STACK_POP() \
2785da591c5SDmitry Stogov 	gc_stack_pop(&_stack, &_top)
2795da591c5SDmitry Stogov 
gc_stack_next(gc_stack * stack)2805da591c5SDmitry Stogov static zend_never_inline gc_stack* gc_stack_next(gc_stack *stack)
2815da591c5SDmitry Stogov {
2825da591c5SDmitry Stogov 	if (UNEXPECTED(!stack->next)) {
2835da591c5SDmitry Stogov 		gc_stack *segment = emalloc(sizeof(gc_stack));
2845da591c5SDmitry Stogov 		segment->prev = stack;
2855da591c5SDmitry Stogov 		segment->next = NULL;
2865da591c5SDmitry Stogov 		stack->next = segment;
2875da591c5SDmitry Stogov 	}
2885da591c5SDmitry Stogov 	return stack->next;
2895da591c5SDmitry Stogov }
2905da591c5SDmitry Stogov 
gc_stack_push(gc_stack ** stack,size_t * top,zend_refcounted * ref)2915da591c5SDmitry Stogov static zend_always_inline void gc_stack_push(gc_stack **stack, size_t *top, zend_refcounted *ref)
2925da591c5SDmitry Stogov {
2935da591c5SDmitry Stogov 	if (UNEXPECTED(*top == GC_STACK_SEGMENT_SIZE)) {
2945da591c5SDmitry Stogov 		(*stack) = gc_stack_next(*stack);
2955da591c5SDmitry Stogov 		(*top) = 0;
2965da591c5SDmitry Stogov 	}
2975da591c5SDmitry Stogov 	(*stack)->data[(*top)++] = ref;
2985da591c5SDmitry Stogov }
2995da591c5SDmitry Stogov 
gc_stack_pop(gc_stack ** stack,size_t * top)3005da591c5SDmitry Stogov static zend_always_inline zend_refcounted* gc_stack_pop(gc_stack **stack, size_t *top)
3015da591c5SDmitry Stogov {
3025da591c5SDmitry Stogov 	if (UNEXPECTED((*top) == 0)) {
3035da591c5SDmitry Stogov 		if (!(*stack)->prev) {
3045da591c5SDmitry Stogov 			return NULL;
3055da591c5SDmitry Stogov 		} else {
3065da591c5SDmitry Stogov 			(*stack) = (*stack)->prev;
3075da591c5SDmitry Stogov 			(*top) = GC_STACK_SEGMENT_SIZE - 1;
3085da591c5SDmitry Stogov 			return (*stack)->data[GC_STACK_SEGMENT_SIZE - 1];
3095da591c5SDmitry Stogov 		}
3105da591c5SDmitry Stogov 	} else {
3115da591c5SDmitry Stogov 		return (*stack)->data[--(*top)];
3125da591c5SDmitry Stogov 	}
3135da591c5SDmitry Stogov }
3145da591c5SDmitry Stogov 
gc_stack_free(gc_stack * stack)3155da591c5SDmitry Stogov static void gc_stack_free(gc_stack *stack)
3165da591c5SDmitry Stogov {
3175da591c5SDmitry Stogov 	gc_stack *p = stack->next;
3185da591c5SDmitry Stogov 
3195da591c5SDmitry Stogov 	while (p) {
3205da591c5SDmitry Stogov 		stack = p->next;
3215da591c5SDmitry Stogov 		efree(p);
3225da591c5SDmitry Stogov 		p = stack;
3235da591c5SDmitry Stogov 	}
3245da591c5SDmitry Stogov }
3255da591c5SDmitry Stogov 
gc_compress(uint32_t idx)326ab139b6bSDmitry Stogov static zend_always_inline uint32_t gc_compress(uint32_t idx)
327fd348ec4SDmitry Stogov {
328193f28c7SNikita Popov 	if (EXPECTED(idx < GC_MAX_UNCOMPRESSED)) {
329193f28c7SNikita Popov 		return idx;
330193f28c7SNikita Popov 	}
331193f28c7SNikita Popov 	return (idx % GC_MAX_UNCOMPRESSED) | GC_MAX_UNCOMPRESSED;
332fd348ec4SDmitry Stogov }
333fd348ec4SDmitry Stogov 
gc_decompress(zend_refcounted * ref,uint32_t idx)334ab139b6bSDmitry Stogov static zend_always_inline gc_root_buffer* gc_decompress(zend_refcounted *ref, uint32_t idx)
335fd348ec4SDmitry Stogov {
336ab139b6bSDmitry Stogov 	gc_root_buffer *root = GC_IDX2PTR(idx);
33706c6c632SDmitry Stogov 
33806c6c632SDmitry Stogov 	if (EXPECTED(GC_GET_PTR(root->ref) == ref)) {
33906c6c632SDmitry Stogov 		return root;
34006c6c632SDmitry Stogov 	}
341fd348ec4SDmitry Stogov 
34206c6c632SDmitry Stogov 	while (1) {
343ab139b6bSDmitry Stogov 		idx += GC_MAX_UNCOMPRESSED;
344ab139b6bSDmitry Stogov 		ZEND_ASSERT(idx < GC_G(first_unused));
345ab139b6bSDmitry Stogov 		root = GC_IDX2PTR(idx);
34606c6c632SDmitry Stogov 		if (GC_GET_PTR(root->ref) == ref) {
34726e0ebffSDmitry Stogov 			return root;
348fd348ec4SDmitry Stogov 		}
349fd348ec4SDmitry Stogov 	}
350fd348ec4SDmitry Stogov }
351fd348ec4SDmitry Stogov 
gc_fetch_unused(void)35226e0ebffSDmitry Stogov static zend_always_inline uint32_t gc_fetch_unused(void)
353fd348ec4SDmitry Stogov {
354ab139b6bSDmitry Stogov 	uint32_t idx;
355fd348ec4SDmitry Stogov 	gc_root_buffer *root;
356fd348ec4SDmitry Stogov 
357fd348ec4SDmitry Stogov 	ZEND_ASSERT(GC_HAS_UNUSED());
358ab139b6bSDmitry Stogov 	idx = GC_G(unused);
359ab139b6bSDmitry Stogov 	root = GC_IDX2PTR(idx);
360fd348ec4SDmitry Stogov 	ZEND_ASSERT(GC_IS_UNUSED(root->ref));
361ab139b6bSDmitry Stogov 	GC_G(unused) = GC_LIST2IDX(root->ref);
362ab139b6bSDmitry Stogov 	return idx;
363fd348ec4SDmitry Stogov }
364fd348ec4SDmitry Stogov 
gc_link_unused(gc_root_buffer * root)365fd348ec4SDmitry Stogov static zend_always_inline void gc_link_unused(gc_root_buffer *root)
366fd348ec4SDmitry Stogov {
367ab139b6bSDmitry Stogov 	root->ref = GC_IDX2LIST(GC_G(unused));
368ab139b6bSDmitry Stogov 	GC_G(unused) = GC_PTR2IDX(root);
369fd348ec4SDmitry Stogov }
370fd348ec4SDmitry Stogov 
gc_fetch_next_unused(void)37126e0ebffSDmitry Stogov static zend_always_inline uint32_t gc_fetch_next_unused(void)
372fd348ec4SDmitry Stogov {
373ab139b6bSDmitry Stogov 	uint32_t idx;
374fd348ec4SDmitry Stogov 
375fd348ec4SDmitry Stogov 	ZEND_ASSERT(GC_HAS_NEXT_UNUSED());
376ab139b6bSDmitry Stogov 	idx = GC_G(first_unused);
377ab139b6bSDmitry Stogov 	GC_G(first_unused) = GC_G(first_unused) + 1;
378ab139b6bSDmitry Stogov 	return idx;
379fd348ec4SDmitry Stogov }
380fd348ec4SDmitry Stogov 
38171ccbf77SNikita Popov #if ZEND_GC_DEBUG > 1
gc_color_name(uint32_t color)38271ccbf77SNikita Popov static const char *gc_color_name(uint32_t color) {
38371ccbf77SNikita Popov 	switch (color) {
38471ccbf77SNikita Popov 		case GC_BLACK: return "black";
38571ccbf77SNikita Popov 		case GC_WHITE: return "white";
38671ccbf77SNikita Popov 		case GC_GREY: return "grey";
38771ccbf77SNikita Popov 		case GC_PURPLE: return "purple";
38871ccbf77SNikita Popov 		default: return "unknown";
38971ccbf77SNikita Popov 	}
39071ccbf77SNikita Popov }
gc_trace_ref(zend_refcounted * ref)39171ccbf77SNikita Popov static void gc_trace_ref(zend_refcounted *ref) {
39271ccbf77SNikita Popov 	if (GC_TYPE(ref) == IS_OBJECT) {
39371ccbf77SNikita Popov 		zend_object *obj = (zend_object *) ref;
39471ccbf77SNikita Popov 		fprintf(stderr, "[%p] rc=%d addr=%d %s object(%s)#%d ",
395165dadacSDmitry Stogov 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
396165dadacSDmitry Stogov 			gc_color_name(GC_REF_COLOR(ref)),
39771ccbf77SNikita Popov 			obj->ce->name->val, obj->handle);
39871ccbf77SNikita Popov 	} else if (GC_TYPE(ref) == IS_ARRAY) {
39971ccbf77SNikita Popov 		zend_array *arr = (zend_array *) ref;
40071ccbf77SNikita Popov 		fprintf(stderr, "[%p] rc=%d addr=%d %s array(%d) ",
401165dadacSDmitry Stogov 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
402165dadacSDmitry Stogov 			gc_color_name(GC_REF_COLOR(ref)),
40371ccbf77SNikita Popov 			zend_hash_num_elements(arr));
40471ccbf77SNikita Popov 	} else {
40571ccbf77SNikita Popov 		fprintf(stderr, "[%p] rc=%d addr=%d %s %s ",
406165dadacSDmitry Stogov 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
407165dadacSDmitry Stogov 			gc_color_name(GC_REF_COLOR(ref)),
408c238b5bbSNikita Popov 			GC_TYPE(ref) == IS_REFERENCE
409c238b5bbSNikita Popov 				? "reference" : zend_get_type_by_const(GC_TYPE(ref)));
41071ccbf77SNikita Popov 	}
41171ccbf77SNikita Popov }
41271ccbf77SNikita Popov #endif
41371ccbf77SNikita Popov 
gc_remove_from_roots(gc_root_buffer * root)414bdeb220fSAnatol Belski static zend_always_inline void gc_remove_from_roots(gc_root_buffer *root)
415f4cfaf36SDmitry Stogov {
416fd348ec4SDmitry Stogov 	GC_LINK_UNUSED(root);
417fd348ec4SDmitry Stogov 	GC_G(num_roots)--;
418f4cfaf36SDmitry Stogov 	GC_BENCH_DEC(root_buf_length);
419f4cfaf36SDmitry Stogov }
420f4cfaf36SDmitry Stogov 
root_buffer_dtor(zend_gc_globals * gc_globals)421bdeb220fSAnatol Belski static void root_buffer_dtor(zend_gc_globals *gc_globals)
4226847c181SDmitry Stogov {
4236847c181SDmitry Stogov 	if (gc_globals->buf) {
4246847c181SDmitry Stogov 		free(gc_globals->buf);
4256847c181SDmitry Stogov 		gc_globals->buf = NULL;
426b7a7b1a6SStanislav Malyshev 	}
4276847c181SDmitry Stogov }
4286847c181SDmitry Stogov 
gc_globals_ctor_ex(zend_gc_globals * gc_globals)429bdeb220fSAnatol Belski static void gc_globals_ctor_ex(zend_gc_globals *gc_globals)
4306847c181SDmitry Stogov {
4316847c181SDmitry Stogov 	gc_globals->gc_enabled = 0;
432a2b707fcSDmitry Stogov 	gc_globals->gc_active = 0;
433fd348ec4SDmitry Stogov 	gc_globals->gc_protected = 1;
434fd348ec4SDmitry Stogov 	gc_globals->gc_full = 0;
4356847c181SDmitry Stogov 
4366847c181SDmitry Stogov 	gc_globals->buf = NULL;
437ab139b6bSDmitry Stogov 	gc_globals->unused = GC_INVALID;
438ab139b6bSDmitry Stogov 	gc_globals->first_unused = GC_INVALID;
439ab139b6bSDmitry Stogov 	gc_globals->gc_threshold = GC_INVALID;
440ab139b6bSDmitry Stogov 	gc_globals->buf_size = GC_INVALID;
441fd348ec4SDmitry Stogov 	gc_globals->num_roots = 0;
442b7938ab1SDmitry Stogov 
4436847c181SDmitry Stogov 	gc_globals->gc_runs = 0;
4446847c181SDmitry Stogov 	gc_globals->collected = 0;
4456847c181SDmitry Stogov 
4466847c181SDmitry Stogov #if GC_BENCH
4476847c181SDmitry Stogov 	gc_globals->root_buf_length = 0;
4486847c181SDmitry Stogov 	gc_globals->root_buf_peak = 0;
4496847c181SDmitry Stogov 	gc_globals->zval_possible_root = 0;
4506847c181SDmitry Stogov 	gc_globals->zval_buffered = 0;
4516847c181SDmitry Stogov 	gc_globals->zval_remove_from_buffer = 0;
4526847c181SDmitry Stogov 	gc_globals->zval_marked_grey = 0;
4536847c181SDmitry Stogov #endif
4546847c181SDmitry Stogov }
4556847c181SDmitry Stogov 
gc_globals_ctor(void)456f844d40fSDmitry Stogov void gc_globals_ctor(void)
4576847c181SDmitry Stogov {
4586847c181SDmitry Stogov #ifdef ZTS
4599499484eSDmitry Stogov 	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);
4606847c181SDmitry Stogov #else
4616847c181SDmitry Stogov 	gc_globals_ctor_ex(&gc_globals);
4626847c181SDmitry Stogov #endif
4636847c181SDmitry Stogov }
4646847c181SDmitry Stogov 
gc_globals_dtor(void)465f844d40fSDmitry Stogov void gc_globals_dtor(void)
4666847c181SDmitry Stogov {
4676847c181SDmitry Stogov #ifndef ZTS
468bdeb220fSAnatol Belski 	root_buffer_dtor(&gc_globals);
4696847c181SDmitry Stogov #endif
4706847c181SDmitry Stogov }
4716847c181SDmitry Stogov 
gc_reset(void)472f844d40fSDmitry Stogov void gc_reset(void)
4736847c181SDmitry Stogov {
474fd348ec4SDmitry Stogov 	if (GC_G(buf)) {
475fd348ec4SDmitry Stogov 		GC_G(gc_active) = 0;
476fd348ec4SDmitry Stogov 		GC_G(gc_protected) = 0;
477fd348ec4SDmitry Stogov 		GC_G(gc_full) = 0;
478ab139b6bSDmitry Stogov 		GC_G(unused) = GC_INVALID;
479ab139b6bSDmitry Stogov 		GC_G(first_unused) = GC_FIRST_ROOT;
480fd348ec4SDmitry Stogov 		GC_G(num_roots) = 0;
481fd348ec4SDmitry Stogov 
482fd348ec4SDmitry Stogov 		GC_G(gc_runs) = 0;
483fd348ec4SDmitry Stogov 		GC_G(collected) = 0;
4846847c181SDmitry Stogov 
4856847c181SDmitry Stogov #if GC_BENCH
486fd348ec4SDmitry Stogov 		GC_G(root_buf_length) = 0;
487fd348ec4SDmitry Stogov 		GC_G(root_buf_peak) = 0;
488fd348ec4SDmitry Stogov 		GC_G(zval_possible_root) = 0;
489fd348ec4SDmitry Stogov 		GC_G(zval_buffered) = 0;
490fd348ec4SDmitry Stogov 		GC_G(zval_remove_from_buffer) = 0;
491fd348ec4SDmitry Stogov 		GC_G(zval_marked_grey) = 0;
4926847c181SDmitry Stogov #endif
4936847c181SDmitry Stogov 	}
4946847c181SDmitry Stogov }
4956847c181SDmitry Stogov 
gc_enable(zend_bool enable)496f844d40fSDmitry Stogov ZEND_API zend_bool gc_enable(zend_bool enable)
4976847c181SDmitry Stogov {
498baa98901SDmitry Stogov 	zend_bool old_enabled = GC_G(gc_enabled);
499baa98901SDmitry Stogov 	GC_G(gc_enabled) = enable;
500baa98901SDmitry Stogov 	if (enable && !old_enabled && GC_G(buf) == NULL) {
501c060d88cSDmitry Stogov 		GC_G(buf) = (gc_root_buffer*) pemalloc(sizeof(gc_root_buffer) * GC_DEFAULT_BUF_SIZE, 1);
502c060d88cSDmitry Stogov 		GC_G(buf)[0].ref = NULL;
503ab139b6bSDmitry Stogov 		GC_G(buf_size) = GC_DEFAULT_BUF_SIZE;
504ab139b6bSDmitry Stogov 		GC_G(gc_threshold) = GC_THRESHOLD_DEFAULT + GC_FIRST_ROOT;
505bdeb220fSAnatol Belski 		gc_reset();
5066847c181SDmitry Stogov 	}
507baa98901SDmitry Stogov 	return old_enabled;
508baa98901SDmitry Stogov }
509baa98901SDmitry Stogov 
gc_enabled(void)510baa98901SDmitry Stogov ZEND_API zend_bool gc_enabled(void)
511baa98901SDmitry Stogov {
512baa98901SDmitry Stogov 	return GC_G(gc_enabled);
5136847c181SDmitry Stogov }
5146847c181SDmitry Stogov 
gc_protect(zend_bool protect)515f844d40fSDmitry Stogov ZEND_API zend_bool gc_protect(zend_bool protect)
516f844d40fSDmitry Stogov {
517f844d40fSDmitry Stogov 	zend_bool old_protected = GC_G(gc_protected);
518f844d40fSDmitry Stogov 	GC_G(gc_protected) = protect;
519f844d40fSDmitry Stogov 	return old_protected;
520f844d40fSDmitry Stogov }
521f844d40fSDmitry Stogov 
gc_protected(void)522f844d40fSDmitry Stogov ZEND_API zend_bool gc_protected(void)
523f844d40fSDmitry Stogov {
524f844d40fSDmitry Stogov 	return GC_G(gc_protected);
525f844d40fSDmitry Stogov }
526f844d40fSDmitry Stogov 
gc_grow_root_buffer(void)527fd348ec4SDmitry Stogov static void gc_grow_root_buffer(void)
528fd348ec4SDmitry Stogov {
529fd348ec4SDmitry Stogov 	size_t new_size;
530fd348ec4SDmitry Stogov 
531ab139b6bSDmitry Stogov 	if (GC_G(buf_size) >= GC_MAX_BUF_SIZE) {
532fd348ec4SDmitry Stogov 		if (!GC_G(gc_full)) {
533fd348ec4SDmitry Stogov 			zend_error(E_WARNING, "GC buffer overflow (GC disabled)\n");
534fd348ec4SDmitry Stogov 			GC_G(gc_active) = 1;
535fd348ec4SDmitry Stogov 			GC_G(gc_protected) = 1;
536fd348ec4SDmitry Stogov 			GC_G(gc_full) = 1;
537fd348ec4SDmitry Stogov 			return;
538fd348ec4SDmitry Stogov 		}
539fd348ec4SDmitry Stogov 	}
540ab139b6bSDmitry Stogov 	if (GC_G(buf_size) < GC_BUF_GROW_STEP) {
541ab139b6bSDmitry Stogov 		new_size = GC_G(buf_size) * 2;
542fd348ec4SDmitry Stogov 	} else {
543ab139b6bSDmitry Stogov 		new_size = GC_G(buf_size) + GC_BUF_GROW_STEP;
544fd348ec4SDmitry Stogov 	}
545fd348ec4SDmitry Stogov 	if (new_size > GC_MAX_BUF_SIZE) {
546fd348ec4SDmitry Stogov 		new_size = GC_MAX_BUF_SIZE;
547fd348ec4SDmitry Stogov 	}
548fd348ec4SDmitry Stogov 	GC_G(buf) = perealloc(GC_G(buf), sizeof(gc_root_buffer) * new_size, 1);
549ab139b6bSDmitry Stogov 	GC_G(buf_size) = new_size;
550fd348ec4SDmitry Stogov }
551fd348ec4SDmitry Stogov 
gc_adjust_threshold(int count)552fd348ec4SDmitry Stogov static void gc_adjust_threshold(int count)
553fd348ec4SDmitry Stogov {
5545c78bb80SDmitry Stogov 	uint32_t new_threshold;
555077d2275SDmitry Stogov 
556fd348ec4SDmitry Stogov 	/* TODO Very simple heuristic for dynamic GC buffer resizing:
557fd348ec4SDmitry Stogov 	 * If there are "too few" collections, increase the collection threshold
558077d2275SDmitry Stogov 	 * by a fixed step */
559077d2275SDmitry Stogov 	if (count < GC_THRESHOLD_TRIGGER) {
560077d2275SDmitry Stogov 		/* increase */
561ab139b6bSDmitry Stogov 		if (GC_G(gc_threshold) < GC_THRESHOLD_MAX) {
562ab139b6bSDmitry Stogov 			new_threshold = GC_G(gc_threshold) + GC_THRESHOLD_STEP;
563077d2275SDmitry Stogov 			if (new_threshold > GC_THRESHOLD_MAX) {
564077d2275SDmitry Stogov 				new_threshold = GC_THRESHOLD_MAX;
565077d2275SDmitry Stogov 			}
566ab139b6bSDmitry Stogov 			if (new_threshold > GC_G(buf_size)) {
567077d2275SDmitry Stogov 				gc_grow_root_buffer();
568077d2275SDmitry Stogov 			}
569ab139b6bSDmitry Stogov 			if (new_threshold <= GC_G(buf_size)) {
570ab139b6bSDmitry Stogov 				GC_G(gc_threshold) = new_threshold;
571077d2275SDmitry Stogov 			}
572077d2275SDmitry Stogov 		}
573ab139b6bSDmitry Stogov 	} else if (GC_G(gc_threshold) > GC_THRESHOLD_DEFAULT) {
574ab139b6bSDmitry Stogov 		new_threshold = GC_G(gc_threshold) - GC_THRESHOLD_STEP;
5755994b8acSDmitry Stogov 		if (new_threshold < GC_THRESHOLD_DEFAULT) {
5765994b8acSDmitry Stogov 			new_threshold = GC_THRESHOLD_DEFAULT;
577077d2275SDmitry Stogov 		}
578ab139b6bSDmitry Stogov 		GC_G(gc_threshold) = new_threshold;
579fd348ec4SDmitry Stogov 	}
580fd348ec4SDmitry Stogov }
581fd348ec4SDmitry Stogov 
gc_possible_root_when_full(zend_refcounted * ref)5824631a5e2SDmitry Stogov static zend_never_inline void ZEND_FASTCALL gc_possible_root_when_full(zend_refcounted *ref)
5834631a5e2SDmitry Stogov {
584ab139b6bSDmitry Stogov 	uint32_t idx;
5854631a5e2SDmitry Stogov 	gc_root_buffer *newRoot;
5864631a5e2SDmitry Stogov 
5874631a5e2SDmitry Stogov 	ZEND_ASSERT(GC_TYPE(ref) == IS_ARRAY || GC_TYPE(ref) == IS_OBJECT);
5884631a5e2SDmitry Stogov 	ZEND_ASSERT(GC_INFO(ref) == 0);
5894631a5e2SDmitry Stogov 
590fd348ec4SDmitry Stogov 	if (GC_G(gc_enabled) && !GC_G(gc_active)) {
591fd348ec4SDmitry Stogov 		GC_ADDREF(ref);
592fd348ec4SDmitry Stogov 		gc_adjust_threshold(gc_collect_cycles());
593fd348ec4SDmitry Stogov 		if (UNEXPECTED(GC_DELREF(ref)) == 0) {
5949d1e9b73SXinchen Hui 			rc_dtor_func(ref);
595fd348ec4SDmitry Stogov 			return;
596fd348ec4SDmitry Stogov 		} else if (UNEXPECTED(GC_INFO(ref))) {
597fd348ec4SDmitry Stogov 			return;
5984631a5e2SDmitry Stogov 		}
5994631a5e2SDmitry Stogov 	}
600fd348ec4SDmitry Stogov 
601fd348ec4SDmitry Stogov 	if (GC_HAS_UNUSED()) {
602ab139b6bSDmitry Stogov 		idx = GC_FETCH_UNUSED();
603fd348ec4SDmitry Stogov 	} else if (EXPECTED(GC_HAS_NEXT_UNUSED())) {
604ab139b6bSDmitry Stogov 		idx = GC_FETCH_NEXT_UNUSED();
605fd348ec4SDmitry Stogov 	} else {
606fd348ec4SDmitry Stogov 		gc_grow_root_buffer();
607ae64dd6dSDmitry Stogov 		if (UNEXPECTED(!GC_HAS_NEXT_UNUSED())) {
608ae64dd6dSDmitry Stogov 			return;
609ae64dd6dSDmitry Stogov 		}
610ab139b6bSDmitry Stogov 		idx = GC_FETCH_NEXT_UNUSED();
611fd348ec4SDmitry Stogov 	}
6124631a5e2SDmitry Stogov 
613ab139b6bSDmitry Stogov 	newRoot = GC_IDX2PTR(idx);
614fd348ec4SDmitry Stogov 	newRoot->ref = ref; /* GC_ROOT tag is 0 */
61526e0ebffSDmitry Stogov 	GC_TRACE_SET_COLOR(ref, GC_PURPLE);
61626e0ebffSDmitry Stogov 
617ab139b6bSDmitry Stogov 	idx = gc_compress(idx);
618ab139b6bSDmitry Stogov 	GC_REF_SET_INFO(ref, idx | GC_PURPLE);
619fd348ec4SDmitry Stogov 	GC_G(num_roots)++;
6204631a5e2SDmitry Stogov 
6214631a5e2SDmitry Stogov 	GC_BENCH_INC(zval_buffered);
6224631a5e2SDmitry Stogov 	GC_BENCH_INC(root_buf_length);
6234631a5e2SDmitry Stogov 	GC_BENCH_PEAK(root_buf_peak, root_buf_length);
6244631a5e2SDmitry Stogov }
6254631a5e2SDmitry Stogov 
gc_possible_root(zend_refcounted * ref)626db10b725SDmitry Stogov ZEND_API void ZEND_FASTCALL gc_possible_root(zend_refcounted *ref)
6276847c181SDmitry Stogov {
628ab139b6bSDmitry Stogov 	uint32_t idx;
6296718b56eSDmitry Stogov 	gc_root_buffer *newRoot;
6306718b56eSDmitry Stogov 
631f844d40fSDmitry Stogov 	if (UNEXPECTED(GC_G(gc_protected))) {
632f71e64e5SDmitry Stogov 		return;
633f71e64e5SDmitry Stogov 	}
634f71e64e5SDmitry Stogov 
6356718b56eSDmitry Stogov 	GC_BENCH_INC(zval_possible_root);
6366847c181SDmitry Stogov 
63726e0ebffSDmitry Stogov 	if (EXPECTED(GC_HAS_UNUSED())) {
638ab139b6bSDmitry Stogov 		idx = GC_FETCH_UNUSED();
639fd348ec4SDmitry Stogov 	} else if (EXPECTED(GC_HAS_NEXT_UNUSED_UNDER_THRESHOLD())) {
640ab139b6bSDmitry Stogov 		idx = GC_FETCH_NEXT_UNUSED();
6416718b56eSDmitry Stogov 	} else {
6424631a5e2SDmitry Stogov 		gc_possible_root_when_full(ref);
6434631a5e2SDmitry Stogov 		return;
6446718b56eSDmitry Stogov 	}
6456847c181SDmitry Stogov 
6464631a5e2SDmitry Stogov 	ZEND_ASSERT(GC_TYPE(ref) == IS_ARRAY || GC_TYPE(ref) == IS_OBJECT);
6474631a5e2SDmitry Stogov 	ZEND_ASSERT(GC_INFO(ref) == 0);
6484631a5e2SDmitry Stogov 
649ab139b6bSDmitry Stogov 	newRoot = GC_IDX2PTR(idx);
65026e0ebffSDmitry Stogov 	newRoot->ref = ref; /* GC_ROOT tag is 0 */
6516718b56eSDmitry Stogov 	GC_TRACE_SET_COLOR(ref, GC_PURPLE);
65226e0ebffSDmitry Stogov 
653ab139b6bSDmitry Stogov 	idx = gc_compress(idx);
654ab139b6bSDmitry Stogov 	GC_REF_SET_INFO(ref, idx | GC_PURPLE);
655fd348ec4SDmitry Stogov 	GC_G(num_roots)++;
6566847c181SDmitry Stogov 
6576718b56eSDmitry Stogov 	GC_BENCH_INC(zval_buffered);
6586718b56eSDmitry Stogov 	GC_BENCH_INC(root_buf_length);
6596718b56eSDmitry Stogov 	GC_BENCH_PEAK(root_buf_peak, root_buf_length);
6606847c181SDmitry Stogov }
6616847c181SDmitry Stogov 
gc_remove_compressed(zend_refcounted * ref,uint32_t idx)662ab139b6bSDmitry Stogov static zend_never_inline void ZEND_FASTCALL gc_remove_compressed(zend_refcounted *ref, uint32_t idx)
66326e0ebffSDmitry Stogov {
6646c3a3835SXinchen Hui 	gc_root_buffer *root = gc_decompress(ref, idx);
6656c3a3835SXinchen Hui 	gc_remove_from_roots(root);
66626e0ebffSDmitry Stogov }
66726e0ebffSDmitry Stogov 
gc_remove_from_buffer(zend_refcounted * ref)668db10b725SDmitry Stogov ZEND_API void ZEND_FASTCALL gc_remove_from_buffer(zend_refcounted *ref)
6696847c181SDmitry Stogov {
670b7938ab1SDmitry Stogov 	gc_root_buffer *root;
671ab139b6bSDmitry Stogov 	uint32_t idx = GC_REF_ADDRESS(ref);
6726847c181SDmitry Stogov 
6732b82e0d7SDmitry Stogov 	GC_BENCH_INC(zval_remove_from_buffer);
6746718b56eSDmitry Stogov 
6755994b8acSDmitry Stogov 	if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
67631e5c345SDmitry Stogov 		GC_TRACE_SET_COLOR(ref, GC_BLACK);
6776718b56eSDmitry Stogov 	}
6786f483dc9SDmitry Stogov 	GC_REF_SET_INFO(ref, 0);
679120dfd1eSDmitry Stogov 
680877da311SDmitry Stogov 	/* Perform decompression only in case of large buffers */
681a0563aa7SNikita Popov 	if (UNEXPECTED(GC_G(first_unused) >= GC_MAX_UNCOMPRESSED)) {
682ab139b6bSDmitry Stogov 		gc_remove_compressed(ref, idx);
68326e0ebffSDmitry Stogov 		return;
6844631a5e2SDmitry Stogov 	}
6854631a5e2SDmitry Stogov 
686c060d88cSDmitry Stogov 	ZEND_ASSERT(idx);
687ab139b6bSDmitry Stogov 	root = GC_IDX2PTR(idx);
688fd348ec4SDmitry Stogov 	gc_remove_from_roots(root);
6892b82e0d7SDmitry Stogov }
6902b82e0d7SDmitry Stogov 
gc_scan_black(zend_refcounted * ref,gc_stack * stack)6915da591c5SDmitry Stogov static void gc_scan_black(zend_refcounted *ref, gc_stack *stack)
6926847c181SDmitry Stogov {
6935da591c5SDmitry Stogov 	HashTable *ht = NULL;
6948eaa0988SDmitry Stogov 	Bucket *p, *end;
6952a9f9860SDmitry Stogov 	zval *zv;
6965da591c5SDmitry Stogov 	GC_STACK_DCL(stack);
69731fd155bSDmitry Stogov 
69831fd155bSDmitry Stogov tail_call:
699a0828247SDmitry Stogov 	if (GC_TYPE(ref) == IS_OBJECT) {
700b7938ab1SDmitry Stogov 		zend_object *obj = (zend_object*)ref;
7016847c181SDmitry Stogov 
7021cfbb217SNikita Popov 		if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
7038eaa0988SDmitry Stogov 			int n;
7048eaa0988SDmitry Stogov 			zval *zv, *end;
705b7938ab1SDmitry Stogov 			zval tmp;
706b64e91ddSDmitry Stogov 
707b7938ab1SDmitry Stogov 			ZVAL_OBJ(&tmp, obj);
7081cfbb217SNikita Popov 			ht = obj->handlers->get_gc(&tmp, &zv, &n);
7098eaa0988SDmitry Stogov 			end = zv + n;
71022d23e08SDmitry Stogov 			if (EXPECTED(!ht) || UNEXPECTED(GC_REF_CHECK_COLOR(ht, GC_BLACK))) {
7116b1cc125SDmitry Stogov 				ht = NULL;
7125da591c5SDmitry Stogov 				if (!n) goto next;
7138eaa0988SDmitry Stogov 				while (!Z_REFCOUNTED_P(--end)) {
7145da591c5SDmitry Stogov 					if (zv == end) goto next;
7158eaa0988SDmitry Stogov 				}
7166b1cc125SDmitry Stogov 			} else {
7176b1cc125SDmitry Stogov 				GC_REF_SET_BLACK(ht);
7188eaa0988SDmitry Stogov 			}
7198eaa0988SDmitry Stogov 			while (zv != end) {
7208eaa0988SDmitry Stogov 				if (Z_REFCOUNTED_P(zv)) {
7218eaa0988SDmitry Stogov 					ref = Z_COUNTED_P(zv);
72249ea143bSDmitry Stogov 					GC_ADDREF(ref);
7235994b8acSDmitry Stogov 					if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
7245da591c5SDmitry Stogov 						GC_REF_SET_BLACK(ref);
7255da591c5SDmitry Stogov 						GC_STACK_PUSH(ref);
726e6235434SDmitry Stogov 					}
727de363cf8SStanislav Malyshev 				}
7288eaa0988SDmitry Stogov 				zv++;
72931fd155bSDmitry Stogov 			}
7308eaa0988SDmitry Stogov 			if (EXPECTED(!ht)) {
7318eaa0988SDmitry Stogov 				ref = Z_COUNTED_P(zv);
73249ea143bSDmitry Stogov 				GC_ADDREF(ref);
7335994b8acSDmitry Stogov 				if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
7345da591c5SDmitry Stogov 					GC_REF_SET_BLACK(ref);
735f08414ceSXinchen Hui 					goto tail_call;
736f08414ceSXinchen Hui 				}
7375da591c5SDmitry Stogov 				goto next;
738b7938ab1SDmitry Stogov 			}
7398eaa0988SDmitry Stogov 		} else {
7405da591c5SDmitry Stogov 			goto next;
7416847c181SDmitry Stogov 		}
742d8099d04SDmitry Stogov 	} else if (GC_TYPE(ref) == IS_ARRAY) {
743b7938ab1SDmitry Stogov 		if ((zend_array*)ref != &EG(symbol_table)) {
744e10e151eSDmitry Stogov 			ht = (zend_array*)ref;
7458eaa0988SDmitry Stogov 		} else {
7465da591c5SDmitry Stogov 			goto next;
747b7938ab1SDmitry Stogov 		}
748d8099d04SDmitry Stogov 	} else if (GC_TYPE(ref) == IS_REFERENCE) {
749b7938ab1SDmitry Stogov 		if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
750b7938ab1SDmitry Stogov 			ref = Z_COUNTED(((zend_reference*)ref)->val);
75149ea143bSDmitry Stogov 			GC_ADDREF(ref);
7525994b8acSDmitry Stogov 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
7535da591c5SDmitry Stogov 				GC_REF_SET_BLACK(ref);
754b7938ab1SDmitry Stogov 				goto tail_call;
755b7938ab1SDmitry Stogov 			}
7566847c181SDmitry Stogov 		}
7575da591c5SDmitry Stogov 		goto next;
7588eaa0988SDmitry Stogov 	} else {
7595da591c5SDmitry Stogov 		goto next;
7606847c181SDmitry Stogov 	}
7618eaa0988SDmitry Stogov 
7625da591c5SDmitry Stogov 	if (!ht->nNumUsed) goto next;
7638eaa0988SDmitry Stogov 	p = ht->arData;
7648eaa0988SDmitry Stogov 	end = p + ht->nNumUsed;
7652a9f9860SDmitry Stogov 	while (1) {
7662a9f9860SDmitry Stogov 		end--;
7672a9f9860SDmitry Stogov 		zv = &end->val;
7682a9f9860SDmitry Stogov 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
7692a9f9860SDmitry Stogov 			zv = Z_INDIRECT_P(zv);
7702a9f9860SDmitry Stogov 		}
7712a9f9860SDmitry Stogov 		if (Z_REFCOUNTED_P(zv)) {
7722a9f9860SDmitry Stogov 			break;
7732a9f9860SDmitry Stogov 		}
7745da591c5SDmitry Stogov 		if (p == end) goto next;
7758eaa0988SDmitry Stogov 	}
7768eaa0988SDmitry Stogov 	while (p != end) {
7772a9f9860SDmitry Stogov 		zv = &p->val;
7782a9f9860SDmitry Stogov 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
7792a9f9860SDmitry Stogov 			zv = Z_INDIRECT_P(zv);
7802a9f9860SDmitry Stogov 		}
7812a9f9860SDmitry Stogov 		if (Z_REFCOUNTED_P(zv)) {
7822a9f9860SDmitry Stogov 			ref = Z_COUNTED_P(zv);
78349ea143bSDmitry Stogov 			GC_ADDREF(ref);
7845994b8acSDmitry Stogov 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
7855da591c5SDmitry Stogov 				GC_REF_SET_BLACK(ref);
7865da591c5SDmitry Stogov 				GC_STACK_PUSH(ref);
78731fd155bSDmitry Stogov 			}
78831fd155bSDmitry Stogov 		}
7898eaa0988SDmitry Stogov 		p++;
7908eaa0988SDmitry Stogov 	}
7912a9f9860SDmitry Stogov 	zv = &p->val;
7922a9f9860SDmitry Stogov 	if (Z_TYPE_P(zv) == IS_INDIRECT) {
7932a9f9860SDmitry Stogov 		zv = Z_INDIRECT_P(zv);
7942a9f9860SDmitry Stogov 	}
7952a9f9860SDmitry Stogov 	ref = Z_COUNTED_P(zv);
79649ea143bSDmitry Stogov 	GC_ADDREF(ref);
7975994b8acSDmitry Stogov 	if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
7985da591c5SDmitry Stogov 		GC_REF_SET_BLACK(ref);
7995da591c5SDmitry Stogov 		goto tail_call;
8005da591c5SDmitry Stogov 	}
8015da591c5SDmitry Stogov 
8025da591c5SDmitry Stogov next:
8035da591c5SDmitry Stogov 	ref = GC_STACK_POP();
8045da591c5SDmitry Stogov 	if (ref) {
8058eaa0988SDmitry Stogov 		goto tail_call;
8066847c181SDmitry Stogov 	}
8076847c181SDmitry Stogov }
8086847c181SDmitry Stogov 
gc_mark_grey(zend_refcounted * ref,gc_stack * stack)8095da591c5SDmitry Stogov static void gc_mark_grey(zend_refcounted *ref, gc_stack *stack)
8106847c181SDmitry Stogov {
8115da591c5SDmitry Stogov 	HashTable *ht = NULL;
8128eaa0988SDmitry Stogov 	Bucket *p, *end;
8132a9f9860SDmitry Stogov 	zval *zv;
8145da591c5SDmitry Stogov 	GC_STACK_DCL(stack);
81531fd155bSDmitry Stogov 
8165da591c5SDmitry Stogov 	do {
8176847c181SDmitry Stogov 		GC_BENCH_INC(zval_marked_grey);
8186847c181SDmitry Stogov 
819a0828247SDmitry Stogov 		if (GC_TYPE(ref) == IS_OBJECT) {
820b7938ab1SDmitry Stogov 			zend_object *obj = (zend_object*)ref;
821b64e91ddSDmitry Stogov 
8221cfbb217SNikita Popov 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
8238eaa0988SDmitry Stogov 				int n;
8248eaa0988SDmitry Stogov 				zval *zv, *end;
825b7938ab1SDmitry Stogov 				zval tmp;
826b7938ab1SDmitry Stogov 
827b7938ab1SDmitry Stogov 				ZVAL_OBJ(&tmp, obj);
8281cfbb217SNikita Popov 				ht = obj->handlers->get_gc(&tmp, &zv, &n);
8298eaa0988SDmitry Stogov 				end = zv + n;
83022d23e08SDmitry Stogov 				if (EXPECTED(!ht) || UNEXPECTED(GC_REF_CHECK_COLOR(ht, GC_GREY))) {
8316b1cc125SDmitry Stogov 					ht = NULL;
8325da591c5SDmitry Stogov 					if (!n) goto next;
8338eaa0988SDmitry Stogov 					while (!Z_REFCOUNTED_P(--end)) {
8345da591c5SDmitry Stogov 						if (zv == end) goto next;
8358eaa0988SDmitry Stogov 					}
8366b1cc125SDmitry Stogov 				} else {
8376b1cc125SDmitry Stogov 					GC_REF_SET_COLOR(ht, GC_GREY);
8388eaa0988SDmitry Stogov 				}
8398eaa0988SDmitry Stogov 				while (zv != end) {
8408eaa0988SDmitry Stogov 					if (Z_REFCOUNTED_P(zv)) {
8418eaa0988SDmitry Stogov 						ref = Z_COUNTED_P(zv);
84249ea143bSDmitry Stogov 						GC_DELREF(ref);
8435da591c5SDmitry Stogov 						if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
8445da591c5SDmitry Stogov 							GC_REF_SET_COLOR(ref, GC_GREY);
8455da591c5SDmitry Stogov 							GC_STACK_PUSH(ref);
8465da591c5SDmitry Stogov 						}
847de363cf8SStanislav Malyshev 					}
8488eaa0988SDmitry Stogov 					zv++;
84931fd155bSDmitry Stogov 				}
8508eaa0988SDmitry Stogov 				if (EXPECTED(!ht)) {
8518eaa0988SDmitry Stogov 					ref = Z_COUNTED_P(zv);
85249ea143bSDmitry Stogov 					GC_DELREF(ref);
8535da591c5SDmitry Stogov 					if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
8545da591c5SDmitry Stogov 						GC_REF_SET_COLOR(ref, GC_GREY);
8555da591c5SDmitry Stogov 						continue;
8565da591c5SDmitry Stogov 					}
8575da591c5SDmitry Stogov 					goto next;
858b7938ab1SDmitry Stogov 				}
8598eaa0988SDmitry Stogov 			} else {
8605da591c5SDmitry Stogov 				goto next;
86131fd155bSDmitry Stogov 			}
862d8099d04SDmitry Stogov 		} else if (GC_TYPE(ref) == IS_ARRAY) {
863b7938ab1SDmitry Stogov 			if (((zend_array*)ref) == &EG(symbol_table)) {
86471ccbf77SNikita Popov 				GC_REF_SET_BLACK(ref);
8655da591c5SDmitry Stogov 				goto next;
8666847c181SDmitry Stogov 			} else {
867e10e151eSDmitry Stogov 				ht = (zend_array*)ref;
86831fd155bSDmitry Stogov 			}
869d8099d04SDmitry Stogov 		} else if (GC_TYPE(ref) == IS_REFERENCE) {
870b7938ab1SDmitry Stogov 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
871b7938ab1SDmitry Stogov 				ref = Z_COUNTED(((zend_reference*)ref)->val);
87249ea143bSDmitry Stogov 				GC_DELREF(ref);
8735da591c5SDmitry Stogov 				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
8745da591c5SDmitry Stogov 					GC_REF_SET_COLOR(ref, GC_GREY);
8755da591c5SDmitry Stogov 					continue;
8765da591c5SDmitry Stogov 				}
877b7938ab1SDmitry Stogov 			}
8785da591c5SDmitry Stogov 			goto next;
8798eaa0988SDmitry Stogov 		} else {
8805da591c5SDmitry Stogov 			goto next;
88131fd155bSDmitry Stogov 		}
8828eaa0988SDmitry Stogov 
8835da591c5SDmitry Stogov 		if (!ht->nNumUsed) goto next;
8848eaa0988SDmitry Stogov 		p = ht->arData;
8858eaa0988SDmitry Stogov 		end = p + ht->nNumUsed;
8862a9f9860SDmitry Stogov 		while (1) {
8872a9f9860SDmitry Stogov 			end--;
8882a9f9860SDmitry Stogov 			zv = &end->val;
8892a9f9860SDmitry Stogov 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
8902a9f9860SDmitry Stogov 				zv = Z_INDIRECT_P(zv);
8912a9f9860SDmitry Stogov 			}
8922a9f9860SDmitry Stogov 			if (Z_REFCOUNTED_P(zv)) {
8932a9f9860SDmitry Stogov 				break;
8942a9f9860SDmitry Stogov 			}
8955da591c5SDmitry Stogov 			if (p == end) goto next;
8968eaa0988SDmitry Stogov 		}
8978eaa0988SDmitry Stogov 		while (p != end) {
8982a9f9860SDmitry Stogov 			zv = &p->val;
8992a9f9860SDmitry Stogov 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
9002a9f9860SDmitry Stogov 				zv = Z_INDIRECT_P(zv);
9012a9f9860SDmitry Stogov 			}
9022a9f9860SDmitry Stogov 			if (Z_REFCOUNTED_P(zv)) {
903a0828247SDmitry Stogov 				ref = Z_COUNTED_P(zv);
90449ea143bSDmitry Stogov 				GC_DELREF(ref);
9055da591c5SDmitry Stogov 				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
9065da591c5SDmitry Stogov 					GC_REF_SET_COLOR(ref, GC_GREY);
9075da591c5SDmitry Stogov 					GC_STACK_PUSH(ref);
9085da591c5SDmitry Stogov 				}
9096f0e5aabSDmitry Stogov 			}
9108eaa0988SDmitry Stogov 			p++;
9118eaa0988SDmitry Stogov 		}
9122a9f9860SDmitry Stogov 		zv = &p->val;
9132a9f9860SDmitry Stogov 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
9142a9f9860SDmitry Stogov 			zv = Z_INDIRECT_P(zv);
9152a9f9860SDmitry Stogov 		}
916a0828247SDmitry Stogov 		ref = Z_COUNTED_P(zv);
91749ea143bSDmitry Stogov 		GC_DELREF(ref);
9185da591c5SDmitry Stogov 		if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
9195da591c5SDmitry Stogov 			GC_REF_SET_COLOR(ref, GC_GREY);
9205da591c5SDmitry Stogov 			continue;
9215da591c5SDmitry Stogov 		}
9225da591c5SDmitry Stogov 
9235da591c5SDmitry Stogov next:
9245da591c5SDmitry Stogov 		ref = GC_STACK_POP();
9255da591c5SDmitry Stogov 	} while (ref);
9266847c181SDmitry Stogov }
9276847c181SDmitry Stogov 
928fd348ec4SDmitry Stogov /* Two-Finger compaction algorithm */
gc_compact(void)929fd348ec4SDmitry Stogov static void gc_compact(void)
930fd348ec4SDmitry Stogov {
931ab139b6bSDmitry Stogov 	if (GC_G(num_roots) + GC_FIRST_ROOT != GC_G(first_unused)) {
932fd348ec4SDmitry Stogov 		if (GC_G(num_roots)) {
933ab139b6bSDmitry Stogov 			gc_root_buffer *free = GC_IDX2PTR(GC_FIRST_ROOT);
934ab139b6bSDmitry Stogov 			gc_root_buffer *scan = GC_IDX2PTR(GC_G(first_unused) - 1);
935ab139b6bSDmitry Stogov 			gc_root_buffer *end  = GC_IDX2PTR(GC_G(num_roots));
936ab139b6bSDmitry Stogov 			uint32_t idx;
937fd348ec4SDmitry Stogov 			zend_refcounted *p;
938fd348ec4SDmitry Stogov 
939fd348ec4SDmitry Stogov 			while (free < scan) {
940ae64dd6dSDmitry Stogov 				while (!GC_IS_UNUSED(free->ref)) {
941fd348ec4SDmitry Stogov 					free++;
942fd348ec4SDmitry Stogov 				}
943ae64dd6dSDmitry Stogov 				while (GC_IS_UNUSED(scan->ref)) {
944fd348ec4SDmitry Stogov 					scan--;
945fd348ec4SDmitry Stogov 				}
946fd348ec4SDmitry Stogov 				if (scan > free) {
947ae64dd6dSDmitry Stogov 					p = scan->ref;
948ae64dd6dSDmitry Stogov 					free->ref = p;
949fd348ec4SDmitry Stogov 					p = GC_GET_PTR(p);
950ab139b6bSDmitry Stogov 					idx = gc_compress(GC_PTR2IDX(free));
951ab139b6bSDmitry Stogov 					GC_REF_SET_INFO(p, idx | GC_REF_COLOR(p));
952fd348ec4SDmitry Stogov 					free++;
953fd348ec4SDmitry Stogov 					scan--;
954ae64dd6dSDmitry Stogov 					if (scan <= end) {
955fd348ec4SDmitry Stogov 						break;
956fd348ec4SDmitry Stogov 					}
957fd348ec4SDmitry Stogov 				}
958fd348ec4SDmitry Stogov 			}
959fd348ec4SDmitry Stogov 		}
960ab139b6bSDmitry Stogov 		GC_G(unused) = GC_INVALID;
961ab139b6bSDmitry Stogov 		GC_G(first_unused) = GC_G(num_roots) + GC_FIRST_ROOT;
962fd348ec4SDmitry Stogov 	}
963fd348ec4SDmitry Stogov }
964fd348ec4SDmitry Stogov 
gc_mark_roots(gc_stack * stack)9655da591c5SDmitry Stogov static void gc_mark_roots(gc_stack *stack)
9666847c181SDmitry Stogov {
967fd348ec4SDmitry Stogov 	gc_root_buffer *current, *last;
968fd348ec4SDmitry Stogov 
969fd348ec4SDmitry Stogov 	gc_compact();
9706847c181SDmitry Stogov 
971ab139b6bSDmitry Stogov 	current = GC_IDX2PTR(GC_FIRST_ROOT);
972ab139b6bSDmitry Stogov 	last = GC_IDX2PTR(GC_G(first_unused));
973fd348ec4SDmitry Stogov 	while (current != last) {
974fd348ec4SDmitry Stogov 		if (GC_IS_ROOT(current->ref)) {
9755994b8acSDmitry Stogov 			if (GC_REF_CHECK_COLOR(current->ref, GC_PURPLE)) {
9765da591c5SDmitry Stogov 				GC_REF_SET_COLOR(current->ref, GC_GREY);
9775da591c5SDmitry Stogov 				gc_mark_grey(current->ref, stack);
978fd348ec4SDmitry Stogov 			}
9796847c181SDmitry Stogov 		}
980fd348ec4SDmitry Stogov 		current++;
9816847c181SDmitry Stogov 	}
9826847c181SDmitry Stogov }
9836847c181SDmitry Stogov 
gc_scan(zend_refcounted * ref,gc_stack * stack)9845da591c5SDmitry Stogov static void gc_scan(zend_refcounted *ref, gc_stack *stack)
9856847c181SDmitry Stogov {
9865da591c5SDmitry Stogov 	HashTable *ht = NULL;
9878eaa0988SDmitry Stogov 	Bucket *p, *end;
9882a9f9860SDmitry Stogov 	zval *zv;
9895da591c5SDmitry Stogov 	GC_STACK_DCL(stack);
99031fd155bSDmitry Stogov 
991b7a7b1a6SStanislav Malyshev tail_call:
9925da591c5SDmitry Stogov 	if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
993d8099d04SDmitry Stogov 		if (GC_REFCOUNT(ref) > 0) {
9945da591c5SDmitry Stogov 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
9955da591c5SDmitry Stogov 				GC_REF_SET_BLACK(ref);
9965da591c5SDmitry Stogov 				if (UNEXPECTED(!_stack->next)) {
9975da591c5SDmitry Stogov 					gc_stack_next(_stack);
9985da591c5SDmitry Stogov 				}
9995da591c5SDmitry Stogov 				/* Split stack and reuse the tail */
10005da591c5SDmitry Stogov 				_stack->next->prev = NULL;
10015da591c5SDmitry Stogov 				gc_scan_black(ref, _stack->next);
10025da591c5SDmitry Stogov 				_stack->next->prev = _stack;
10035da591c5SDmitry Stogov 			}
10046847c181SDmitry Stogov 		} else {
1005a0828247SDmitry Stogov 			if (GC_TYPE(ref) == IS_OBJECT) {
1006b7938ab1SDmitry Stogov 				zend_object *obj = (zend_object*)ref;
1007b7938ab1SDmitry Stogov 
10081cfbb217SNikita Popov 				if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
10098eaa0988SDmitry Stogov 					int n;
10108eaa0988SDmitry Stogov 					zval *zv, *end;
1011b7938ab1SDmitry Stogov 					zval tmp;
1012b7a7b1a6SStanislav Malyshev 
1013b7938ab1SDmitry Stogov 					ZVAL_OBJ(&tmp, obj);
10141cfbb217SNikita Popov 					ht = obj->handlers->get_gc(&tmp, &zv, &n);
10158eaa0988SDmitry Stogov 					end = zv + n;
101622d23e08SDmitry Stogov 					if (EXPECTED(!ht) || UNEXPECTED(!GC_REF_CHECK_COLOR(ht, GC_GREY))) {
10176b1cc125SDmitry Stogov 						ht = NULL;
10185da591c5SDmitry Stogov 						if (!n) goto next;
10198eaa0988SDmitry Stogov 						while (!Z_REFCOUNTED_P(--end)) {
10205da591c5SDmitry Stogov 							if (zv == end) goto next;
102131fd155bSDmitry Stogov 						}
10226b1cc125SDmitry Stogov 					} else {
10236b1cc125SDmitry Stogov 						GC_REF_SET_COLOR(ht, GC_WHITE);
102431fd155bSDmitry Stogov 					}
10258eaa0988SDmitry Stogov 					while (zv != end) {
10268eaa0988SDmitry Stogov 						if (Z_REFCOUNTED_P(zv)) {
10278eaa0988SDmitry Stogov 							ref = Z_COUNTED_P(zv);
10285da591c5SDmitry Stogov 							if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
10295da591c5SDmitry Stogov 								GC_REF_SET_COLOR(ref, GC_WHITE);
10305da591c5SDmitry Stogov 								GC_STACK_PUSH(ref);
10315da591c5SDmitry Stogov 							}
10328eaa0988SDmitry Stogov 						}
10338eaa0988SDmitry Stogov 						zv++;
10348eaa0988SDmitry Stogov 					}
10358eaa0988SDmitry Stogov 					if (EXPECTED(!ht)) {
10368eaa0988SDmitry Stogov 						ref = Z_COUNTED_P(zv);
10375da591c5SDmitry Stogov 						if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
10385da591c5SDmitry Stogov 							GC_REF_SET_COLOR(ref, GC_WHITE);
10395da591c5SDmitry Stogov 							goto tail_call;
10405da591c5SDmitry Stogov 						}
10415da591c5SDmitry Stogov 						goto next;
1042b7938ab1SDmitry Stogov 					}
10438eaa0988SDmitry Stogov 				} else {
10445da591c5SDmitry Stogov 					goto next;
104531fd155bSDmitry Stogov 				}
1046d8099d04SDmitry Stogov 			} else if (GC_TYPE(ref) == IS_ARRAY) {
1047b7938ab1SDmitry Stogov 				if ((zend_array*)ref == &EG(symbol_table)) {
104871ccbf77SNikita Popov 					GC_REF_SET_BLACK(ref);
10495da591c5SDmitry Stogov 					goto next;
10506847c181SDmitry Stogov 				} else {
1051e10e151eSDmitry Stogov 					ht = (zend_array*)ref;
1052b7938ab1SDmitry Stogov 				}
1053d8099d04SDmitry Stogov 			} else if (GC_TYPE(ref) == IS_REFERENCE) {
1054b7938ab1SDmitry Stogov 				if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
1055b7938ab1SDmitry Stogov 					ref = Z_COUNTED(((zend_reference*)ref)->val);
10565da591c5SDmitry Stogov 					if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
10575da591c5SDmitry Stogov 						GC_REF_SET_COLOR(ref, GC_WHITE);
10585da591c5SDmitry Stogov 						goto tail_call;
10595da591c5SDmitry Stogov 					}
10606847c181SDmitry Stogov 				}
1061