1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine                                                          |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 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: David Wang <planetbeing@gmail.com>                          |
16    |          Dmitry Stogov <dmitry@php.net>                              |
17    +----------------------------------------------------------------------+
18 */
19 
20 /**
21  * zend_gc_collect_cycles
22  * ======================
23  *
24  * Colors and its meaning
25  * ----------------------
26  *
27  * BLACK  (GC_BLACK)   - In use or free.
28  * GREY   (GC_GREY)    - Possible member of cycle.
29  * WHITE  (GC_WHITE)   - Member of garbage cycle.
30  * PURPLE (GC_PURPLE)  - Possible root of cycle.
31  *
32  * Colors described in the paper but not used
33  * ------------------------------------------
34  *
35  * GREEN - Acyclic
36  * RED   - Candidate cycle underogin
37  * ORANGE - Candidate cycle awaiting epoch boundary.
38  *
39  *
40  * Flow
41  * =====
42  *
43  * The garbage collect cycle starts from 'gc_mark_roots', which traverses the
44  * possible roots, and calls mark_grey for roots are marked purple with
45  * depth-first traverse.
46  *
47  * After all possible roots are traversed and marked,
48  * gc_scan_roots will be called, and each root will be called with
49  * gc_scan(root->ref)
50  *
51  * gc_scan checks the colors of possible members.
52  *
53  * If the node is marked as grey and the refcount > 0
54  *    gc_scan_black will be called on that node to scan it's subgraph.
55  * otherwise (refcount == 0), it marks the node white.
56  *
57  * A node MAY be added to possible roots when ZEND_UNSET_VAR happens or
58  * zend_assign_to_variable is called only when possible garbage node is
59  * produced.
60  * gc_possible_root() will be called to add the nodes to possible roots.
61  *
62  *
63  * For objects, we call their get_gc handler (by default 'zend_std_get_gc') to
64  * get the object properties to scan.
65  *
66  *
67  * @see http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf
68  */
69 #include "zend.h"
70 #include "zend_API.h"
71 
72 #ifndef GC_BENCH
73 # define GC_BENCH 0
74 #endif
75 
76 #ifndef ZEND_GC_DEBUG
77 # define ZEND_GC_DEBUG 0
78 #endif
79 
80 /* GC_INFO layout */
81 #define GC_ADDRESS  0x0fffffu
82 #define GC_COLOR    0x300000u
83 
84 #define GC_BLACK    0x000000u /* must be zero */
85 #define GC_WHITE    0x100000u
86 #define GC_GREY     0x200000u
87 #define GC_PURPLE   0x300000u
88 
89 /* Debug tracing */
90 #if ZEND_GC_DEBUG > 1
91 # define GC_TRACE(format, ...) fprintf(stderr, format "\n", ##__VA_ARGS__);
92 # define GC_TRACE_REF(ref, format, ...) \
93 	do { \
94 		gc_trace_ref((zend_refcounted *) ref); \
95 		fprintf(stderr, format "\n", ##__VA_ARGS__); \
96 	} while (0)
97 # define GC_TRACE_SET_COLOR(ref, color) \
98 	GC_TRACE_REF(ref, "->%s", gc_color_name(color))
99 #else
100 # define GC_TRACE_REF(ref, format, ...)
101 # define GC_TRACE_SET_COLOR(ref, new_color)
102 # define GC_TRACE(str)
103 #endif
104 
105 /* GC_INFO access */
106 #define GC_REF_ADDRESS(ref) \
107 	(((GC_TYPE_INFO(ref)) & (GC_ADDRESS << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)
108 
109 #define GC_REF_COLOR(ref) \
110 	(((GC_TYPE_INFO(ref)) & (GC_COLOR << GC_INFO_SHIFT)) >> GC_INFO_SHIFT)
111 
112 #define GC_REF_CHECK_COLOR(ref, color) \
113 	((GC_TYPE_INFO(ref) & (GC_COLOR << GC_INFO_SHIFT)) == ((color) << GC_INFO_SHIFT))
114 
115 #define GC_REF_SET_INFO(ref, info) do { \
116 		GC_TYPE_INFO(ref) = \
117 			(GC_TYPE_INFO(ref) & (GC_TYPE_MASK | GC_FLAGS_MASK)) | \
118 			((info) << GC_INFO_SHIFT); \
119 	} while (0)
120 
121 #define GC_REF_SET_COLOR(ref, c) do { \
122 		GC_TRACE_SET_COLOR(ref, c); \
123 		GC_TYPE_INFO(ref) = \
124 			(GC_TYPE_INFO(ref) & ~(GC_COLOR << GC_INFO_SHIFT)) | \
125 			((c) << GC_INFO_SHIFT); \
126 	} while (0)
127 
128 #define GC_REF_SET_BLACK(ref) do { \
129 		GC_TRACE_SET_COLOR(ref, GC_BLACK); \
130 		GC_TYPE_INFO(ref) &= ~(GC_COLOR << GC_INFO_SHIFT); \
131 	} while (0)
132 
133 #define GC_REF_SET_PURPLE(ref) do { \
134 		GC_TRACE_SET_COLOR(ref, GC_PURPLE); \
135 		GC_TYPE_INFO(ref) |= (GC_COLOR << GC_INFO_SHIFT); \
136 	} while (0)
137 
138 /* bit stealing tags for gc_root_buffer.ref */
139 #define GC_BITS    0x3
140 
141 #define GC_ROOT    0x0 /* possible root of circular garbage     */
142 #define GC_UNUSED  0x1 /* part of linked list of unused buffers */
143 #define GC_GARBAGE 0x2 /* garbage to delete                     */
144 #define GC_DTOR_GARBAGE 0x3 /* garbage on which only the dtor should be invoked */
145 
146 #define GC_GET_PTR(ptr) \
147 	((void*)(((uintptr_t)(ptr)) & ~GC_BITS))
148 
149 #define GC_IS_ROOT(ptr) \
150 	((((uintptr_t)(ptr)) & GC_BITS) == GC_ROOT)
151 #define GC_IS_UNUSED(ptr) \
152 	((((uintptr_t)(ptr)) & GC_BITS) == GC_UNUSED)
153 #define GC_IS_GARBAGE(ptr) \
154 	((((uintptr_t)(ptr)) & GC_BITS) == GC_GARBAGE)
155 #define GC_IS_DTOR_GARBAGE(ptr) \
156 	((((uintptr_t)(ptr)) & GC_BITS) == GC_DTOR_GARBAGE)
157 
158 #define GC_MAKE_GARBAGE(ptr) \
159 	((void*)(((uintptr_t)(ptr)) | GC_GARBAGE))
160 #define GC_MAKE_DTOR_GARBAGE(ptr) \
161 	((void*)(((uintptr_t)(ptr)) | GC_DTOR_GARBAGE))
162 
163 /* GC address conversion */
164 #define GC_IDX2PTR(idx)      (GC_G(buf) + (idx))
165 #define GC_PTR2IDX(ptr)      ((ptr) - GC_G(buf))
166 
167 #define GC_IDX2LIST(idx)     ((void*)(uintptr_t)(((idx) * sizeof(void*)) | GC_UNUSED))
168 #define GC_LIST2IDX(list)    (((uint32_t)(uintptr_t)(list)) / sizeof(void*))
169 
170 /* GC buffers */
171 #define GC_INVALID           0
172 #define GC_FIRST_ROOT        1
173 
174 #define GC_DEFAULT_BUF_SIZE  (16 * 1024)
175 #define GC_BUF_GROW_STEP     (128 * 1024)
176 
177 #define GC_MAX_UNCOMPRESSED  (512 * 1024)
178 #define GC_MAX_BUF_SIZE      0x40000000
179 
180 #define GC_THRESHOLD_DEFAULT 10000
181 #define GC_THRESHOLD_STEP    10000
182 #define GC_THRESHOLD_MAX     1000000000
183 #define GC_THRESHOLD_TRIGGER 100
184 
185 /* GC flags */
186 #define GC_HAS_DESTRUCTORS  (1<<0)
187 
188 /* unused buffers */
189 #define GC_HAS_UNUSED() \
190 	(GC_G(unused) != GC_INVALID)
191 #define GC_FETCH_UNUSED() \
192 	gc_fetch_unused()
193 #define GC_LINK_UNUSED(root) \
194 	gc_link_unused(root)
195 
196 #define GC_HAS_NEXT_UNUSED_UNDER_THRESHOLD() \
197 	(GC_G(first_unused) < GC_G(gc_threshold))
198 #define GC_HAS_NEXT_UNUSED() \
199 	(GC_G(first_unused) != GC_G(buf_size))
200 #define GC_FETCH_NEXT_UNUSED() \
201 	gc_fetch_next_unused()
202 
203 ZEND_API int (*gc_collect_cycles)(void);
204 
205 typedef struct _gc_root_buffer {
206 	zend_refcounted  *ref;
207 } gc_root_buffer;
208 
209 typedef struct _zend_gc_globals {
210 	gc_root_buffer   *buf;				/* preallocated arrays of buffers   */
211 
212 	zend_bool         gc_enabled;
213 	zend_bool         gc_active;        /* GC currently running, forbid nested GC */
214 	zend_bool         gc_protected;     /* GC protected, forbid root additions */
215 	zend_bool         gc_full;
216 
217 	uint32_t          unused;			/* linked list of unused buffers    */
218 	uint32_t          first_unused;		/* first unused buffer              */
219 	uint32_t          gc_threshold;     /* GC collection threshold          */
220 	uint32_t          buf_size;			/* size of the GC buffer            */
221 	uint32_t          num_roots;		/* number of roots in GC buffer     */
222 
223 	uint32_t gc_runs;
224 	uint32_t collected;
225 
226 #if GC_BENCH
227 	uint32_t root_buf_length;
228 	uint32_t root_buf_peak;
229 	uint32_t zval_possible_root;
230 	uint32_t zval_buffered;
231 	uint32_t zval_remove_from_buffer;
232 	uint32_t zval_marked_grey;
233 #endif
234 } zend_gc_globals;
235 
236 #ifdef ZTS
237 static int gc_globals_id;
238 static size_t gc_globals_offset;
239 #define GC_G(v) ZEND_TSRMG_FAST(gc_globals_offset, zend_gc_globals *, v)
240 #else
241 #define GC_G(v) (gc_globals.v)
242 static zend_gc_globals gc_globals;
243 #endif
244 
245 #if GC_BENCH
246 # define GC_BENCH_INC(counter) GC_G(counter)++
247 # define GC_BENCH_DEC(counter) GC_G(counter)--
248 # define GC_BENCH_PEAK(peak, counter) do {		\
249 		if (GC_G(counter) > GC_G(peak)) {		\
250 			GC_G(peak) = GC_G(counter);			\
251 		}										\
252 	} while (0)
253 #else
254 # define GC_BENCH_INC(counter)
255 # define GC_BENCH_DEC(counter)
256 # define GC_BENCH_PEAK(peak, counter)
257 #endif
258 
259 
260 #define GC_STACK_SEGMENT_SIZE (((4096 - ZEND_MM_OVERHEAD) / sizeof(void*)) - 2)
261 
262 typedef struct _gc_stack gc_stack;
263 
264 struct _gc_stack {
265 	gc_stack        *prev;
266 	gc_stack        *next;
267 	zend_refcounted *data[GC_STACK_SEGMENT_SIZE];
268 };
269 
270 #define GC_STACK_DCL(init) \
271 	gc_stack *_stack = init; \
272 	size_t    _top = 0;
273 
274 #define GC_STACK_PUSH(ref) \
275 	gc_stack_push(&_stack, &_top, ref);
276 
277 #define GC_STACK_POP() \
278 	gc_stack_pop(&_stack, &_top)
279 
gc_stack_next(gc_stack * stack)280 static zend_never_inline gc_stack* gc_stack_next(gc_stack *stack)
281 {
282 	if (UNEXPECTED(!stack->next)) {
283 		gc_stack *segment = emalloc(sizeof(gc_stack));
284 		segment->prev = stack;
285 		segment->next = NULL;
286 		stack->next = segment;
287 	}
288 	return stack->next;
289 }
290 
gc_stack_push(gc_stack ** stack,size_t * top,zend_refcounted * ref)291 static zend_always_inline void gc_stack_push(gc_stack **stack, size_t *top, zend_refcounted *ref)
292 {
293 	if (UNEXPECTED(*top == GC_STACK_SEGMENT_SIZE)) {
294 		(*stack) = gc_stack_next(*stack);
295 		(*top) = 0;
296 	}
297 	(*stack)->data[(*top)++] = ref;
298 }
299 
gc_stack_pop(gc_stack ** stack,size_t * top)300 static zend_always_inline zend_refcounted* gc_stack_pop(gc_stack **stack, size_t *top)
301 {
302 	if (UNEXPECTED((*top) == 0)) {
303 		if (!(*stack)->prev) {
304 			return NULL;
305 		} else {
306 			(*stack) = (*stack)->prev;
307 			(*top) = GC_STACK_SEGMENT_SIZE - 1;
308 			return (*stack)->data[GC_STACK_SEGMENT_SIZE - 1];
309 		}
310 	} else {
311 		return (*stack)->data[--(*top)];
312 	}
313 }
314 
gc_stack_free(gc_stack * stack)315 static void gc_stack_free(gc_stack *stack)
316 {
317 	gc_stack *p = stack->next;
318 
319 	while (p) {
320 		stack = p->next;
321 		efree(p);
322 		p = stack;
323 	}
324 }
325 
gc_compress(uint32_t idx)326 static zend_always_inline uint32_t gc_compress(uint32_t idx)
327 {
328 	if (EXPECTED(idx < GC_MAX_UNCOMPRESSED)) {
329 		return idx;
330 	}
331 	return (idx % GC_MAX_UNCOMPRESSED) | GC_MAX_UNCOMPRESSED;
332 }
333 
gc_decompress(zend_refcounted * ref,uint32_t idx)334 static zend_always_inline gc_root_buffer* gc_decompress(zend_refcounted *ref, uint32_t idx)
335 {
336 	gc_root_buffer *root = GC_IDX2PTR(idx);
337 
338 	if (EXPECTED(GC_GET_PTR(root->ref) == ref)) {
339 		return root;
340 	}
341 
342 	while (1) {
343 		idx += GC_MAX_UNCOMPRESSED;
344 		ZEND_ASSERT(idx < GC_G(first_unused));
345 		root = GC_IDX2PTR(idx);
346 		if (GC_GET_PTR(root->ref) == ref) {
347 			return root;
348 		}
349 	}
350 }
351 
gc_fetch_unused(void)352 static zend_always_inline uint32_t gc_fetch_unused(void)
353 {
354 	uint32_t idx;
355 	gc_root_buffer *root;
356 
357 	ZEND_ASSERT(GC_HAS_UNUSED());
358 	idx = GC_G(unused);
359 	root = GC_IDX2PTR(idx);
360 	ZEND_ASSERT(GC_IS_UNUSED(root->ref));
361 	GC_G(unused) = GC_LIST2IDX(root->ref);
362 	return idx;
363 }
364 
gc_link_unused(gc_root_buffer * root)365 static zend_always_inline void gc_link_unused(gc_root_buffer *root)
366 {
367 	root->ref = GC_IDX2LIST(GC_G(unused));
368 	GC_G(unused) = GC_PTR2IDX(root);
369 }
370 
gc_fetch_next_unused(void)371 static zend_always_inline uint32_t gc_fetch_next_unused(void)
372 {
373 	uint32_t idx;
374 
375 	ZEND_ASSERT(GC_HAS_NEXT_UNUSED());
376 	idx = GC_G(first_unused);
377 	GC_G(first_unused) = GC_G(first_unused) + 1;
378 	return idx;
379 }
380 
381 #if ZEND_GC_DEBUG > 1
gc_color_name(uint32_t color)382 static const char *gc_color_name(uint32_t color) {
383 	switch (color) {
384 		case GC_BLACK: return "black";
385 		case GC_WHITE: return "white";
386 		case GC_GREY: return "grey";
387 		case GC_PURPLE: return "purple";
388 		default: return "unknown";
389 	}
390 }
gc_trace_ref(zend_refcounted * ref)391 static void gc_trace_ref(zend_refcounted *ref) {
392 	if (GC_TYPE(ref) == IS_OBJECT) {
393 		zend_object *obj = (zend_object *) ref;
394 		fprintf(stderr, "[%p] rc=%d addr=%d %s object(%s)#%d ",
395 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
396 			gc_color_name(GC_REF_COLOR(ref)),
397 			obj->ce->name->val, obj->handle);
398 	} else if (GC_TYPE(ref) == IS_ARRAY) {
399 		zend_array *arr = (zend_array *) ref;
400 		fprintf(stderr, "[%p] rc=%d addr=%d %s array(%d) ",
401 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
402 			gc_color_name(GC_REF_COLOR(ref)),
403 			zend_hash_num_elements(arr));
404 	} else {
405 		fprintf(stderr, "[%p] rc=%d addr=%d %s %s ",
406 			ref, GC_REFCOUNT(ref), GC_REF_ADDRESS(ref),
407 			gc_color_name(GC_REF_COLOR(ref)),
408 			GC_TYPE(ref) == IS_REFERENCE
409 				? "reference" : zend_get_type_by_const(GC_TYPE(ref)));
410 	}
411 }
412 #endif
413 
gc_remove_from_roots(gc_root_buffer * root)414 static zend_always_inline void gc_remove_from_roots(gc_root_buffer *root)
415 {
416 	GC_LINK_UNUSED(root);
417 	GC_G(num_roots)--;
418 	GC_BENCH_DEC(root_buf_length);
419 }
420 
root_buffer_dtor(zend_gc_globals * gc_globals)421 static void root_buffer_dtor(zend_gc_globals *gc_globals)
422 {
423 	if (gc_globals->buf) {
424 		free(gc_globals->buf);
425 		gc_globals->buf = NULL;
426 	}
427 }
428 
gc_globals_ctor_ex(zend_gc_globals * gc_globals)429 static void gc_globals_ctor_ex(zend_gc_globals *gc_globals)
430 {
431 	gc_globals->gc_enabled = 0;
432 	gc_globals->gc_active = 0;
433 	gc_globals->gc_protected = 1;
434 	gc_globals->gc_full = 0;
435 
436 	gc_globals->buf = NULL;
437 	gc_globals->unused = GC_INVALID;
438 	gc_globals->first_unused = GC_INVALID;
439 	gc_globals->gc_threshold = GC_INVALID;
440 	gc_globals->buf_size = GC_INVALID;
441 	gc_globals->num_roots = 0;
442 
443 	gc_globals->gc_runs = 0;
444 	gc_globals->collected = 0;
445 
446 #if GC_BENCH
447 	gc_globals->root_buf_length = 0;
448 	gc_globals->root_buf_peak = 0;
449 	gc_globals->zval_possible_root = 0;
450 	gc_globals->zval_buffered = 0;
451 	gc_globals->zval_remove_from_buffer = 0;
452 	gc_globals->zval_marked_grey = 0;
453 #endif
454 }
455 
gc_globals_ctor(void)456 void gc_globals_ctor(void)
457 {
458 #ifdef ZTS
459 	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);
460 #else
461 	gc_globals_ctor_ex(&gc_globals);
462 #endif
463 }
464 
gc_globals_dtor(void)465 void gc_globals_dtor(void)
466 {
467 #ifndef ZTS
468 	root_buffer_dtor(&gc_globals);
469 #endif
470 }
471 
gc_reset(void)472 void gc_reset(void)
473 {
474 	if (GC_G(buf)) {
475 		GC_G(gc_active) = 0;
476 		GC_G(gc_protected) = 0;
477 		GC_G(gc_full) = 0;
478 		GC_G(unused) = GC_INVALID;
479 		GC_G(first_unused) = GC_FIRST_ROOT;
480 		GC_G(num_roots) = 0;
481 
482 		GC_G(gc_runs) = 0;
483 		GC_G(collected) = 0;
484 
485 #if GC_BENCH
486 		GC_G(root_buf_length) = 0;
487 		GC_G(root_buf_peak) = 0;
488 		GC_G(zval_possible_root) = 0;
489 		GC_G(zval_buffered) = 0;
490 		GC_G(zval_remove_from_buffer) = 0;
491 		GC_G(zval_marked_grey) = 0;
492 #endif
493 	}
494 }
495 
gc_enable(zend_bool enable)496 ZEND_API zend_bool gc_enable(zend_bool enable)
497 {
498 	zend_bool old_enabled = GC_G(gc_enabled);
499 	GC_G(gc_enabled) = enable;
500 	if (enable && !old_enabled && GC_G(buf) == NULL) {
501 		GC_G(buf) = (gc_root_buffer*) pemalloc(sizeof(gc_root_buffer) * GC_DEFAULT_BUF_SIZE, 1);
502 		GC_G(buf)[0].ref = NULL;
503 		GC_G(buf_size) = GC_DEFAULT_BUF_SIZE;
504 		GC_G(gc_threshold) = GC_THRESHOLD_DEFAULT + GC_FIRST_ROOT;
505 		gc_reset();
506 	}
507 	return old_enabled;
508 }
509 
gc_enabled(void)510 ZEND_API zend_bool gc_enabled(void)
511 {
512 	return GC_G(gc_enabled);
513 }
514 
gc_protect(zend_bool protect)515 ZEND_API zend_bool gc_protect(zend_bool protect)
516 {
517 	zend_bool old_protected = GC_G(gc_protected);
518 	GC_G(gc_protected) = protect;
519 	return old_protected;
520 }
521 
gc_protected(void)522 ZEND_API zend_bool gc_protected(void)
523 {
524 	return GC_G(gc_protected);
525 }
526 
gc_grow_root_buffer(void)527 static void gc_grow_root_buffer(void)
528 {
529 	size_t new_size;
530 
531 	if (GC_G(buf_size) >= GC_MAX_BUF_SIZE) {
532 		if (!GC_G(gc_full)) {
533 			zend_error(E_WARNING, "GC buffer overflow (GC disabled)\n");
534 			GC_G(gc_active) = 1;
535 			GC_G(gc_protected) = 1;
536 			GC_G(gc_full) = 1;
537 			return;
538 		}
539 	}
540 	if (GC_G(buf_size) < GC_BUF_GROW_STEP) {
541 		new_size = GC_G(buf_size) * 2;
542 	} else {
543 		new_size = GC_G(buf_size) + GC_BUF_GROW_STEP;
544 	}
545 	if (new_size > GC_MAX_BUF_SIZE) {
546 		new_size = GC_MAX_BUF_SIZE;
547 	}
548 	GC_G(buf) = perealloc(GC_G(buf), sizeof(gc_root_buffer) * new_size, 1);
549 	GC_G(buf_size) = new_size;
550 }
551 
gc_adjust_threshold(int count)552 static void gc_adjust_threshold(int count)
553 {
554 	uint32_t new_threshold;
555 
556 	/* TODO Very simple heuristic for dynamic GC buffer resizing:
557 	 * If there are "too few" collections, increase the collection threshold
558 	 * by a fixed step */
559 	if (count < GC_THRESHOLD_TRIGGER) {
560 		/* increase */
561 		if (GC_G(gc_threshold) < GC_THRESHOLD_MAX) {
562 			new_threshold = GC_G(gc_threshold) + GC_THRESHOLD_STEP;
563 			if (new_threshold > GC_THRESHOLD_MAX) {
564 				new_threshold = GC_THRESHOLD_MAX;
565 			}
566 			if (new_threshold > GC_G(buf_size)) {
567 				gc_grow_root_buffer();
568 			}
569 			if (new_threshold <= GC_G(buf_size)) {
570 				GC_G(gc_threshold) = new_threshold;
571 			}
572 		}
573 	} else if (GC_G(gc_threshold) > GC_THRESHOLD_DEFAULT) {
574 		new_threshold = GC_G(gc_threshold) - GC_THRESHOLD_STEP;
575 		if (new_threshold < GC_THRESHOLD_DEFAULT) {
576 			new_threshold = GC_THRESHOLD_DEFAULT;
577 		}
578 		GC_G(gc_threshold) = new_threshold;
579 	}
580 }
581 
gc_possible_root_when_full(zend_refcounted * ref)582 static zend_never_inline void ZEND_FASTCALL gc_possible_root_when_full(zend_refcounted *ref)
583 {
584 	uint32_t idx;
585 	gc_root_buffer *newRoot;
586 
587 	ZEND_ASSERT(GC_TYPE(ref) == IS_ARRAY || GC_TYPE(ref) == IS_OBJECT);
588 	ZEND_ASSERT(GC_INFO(ref) == 0);
589 
590 	if (GC_G(gc_enabled) && !GC_G(gc_active)) {
591 		GC_ADDREF(ref);
592 		gc_adjust_threshold(gc_collect_cycles());
593 		if (UNEXPECTED(GC_DELREF(ref)) == 0) {
594 			rc_dtor_func(ref);
595 			return;
596 		} else if (UNEXPECTED(GC_INFO(ref))) {
597 			return;
598 		}
599 	}
600 
601 	if (GC_HAS_UNUSED()) {
602 		idx = GC_FETCH_UNUSED();
603 	} else if (EXPECTED(GC_HAS_NEXT_UNUSED())) {
604 		idx = GC_FETCH_NEXT_UNUSED();
605 	} else {
606 		gc_grow_root_buffer();
607 		if (UNEXPECTED(!GC_HAS_NEXT_UNUSED())) {
608 			return;
609 		}
610 		idx = GC_FETCH_NEXT_UNUSED();
611 	}
612 
613 	newRoot = GC_IDX2PTR(idx);
614 	newRoot->ref = ref; /* GC_ROOT tag is 0 */
615 	GC_TRACE_SET_COLOR(ref, GC_PURPLE);
616 
617 	idx = gc_compress(idx);
618 	GC_REF_SET_INFO(ref, idx | GC_PURPLE);
619 	GC_G(num_roots)++;
620 
621 	GC_BENCH_INC(zval_buffered);
622 	GC_BENCH_INC(root_buf_length);
623 	GC_BENCH_PEAK(root_buf_peak, root_buf_length);
624 }
625 
gc_possible_root(zend_refcounted * ref)626 ZEND_API void ZEND_FASTCALL gc_possible_root(zend_refcounted *ref)
627 {
628 	uint32_t idx;
629 	gc_root_buffer *newRoot;
630 
631 	if (UNEXPECTED(GC_G(gc_protected))) {
632 		return;
633 	}
634 
635 	GC_BENCH_INC(zval_possible_root);
636 
637 	if (EXPECTED(GC_HAS_UNUSED())) {
638 		idx = GC_FETCH_UNUSED();
639 	} else if (EXPECTED(GC_HAS_NEXT_UNUSED_UNDER_THRESHOLD())) {
640 		idx = GC_FETCH_NEXT_UNUSED();
641 	} else {
642 		gc_possible_root_when_full(ref);
643 		return;
644 	}
645 
646 	ZEND_ASSERT(GC_TYPE(ref) == IS_ARRAY || GC_TYPE(ref) == IS_OBJECT);
647 	ZEND_ASSERT(GC_INFO(ref) == 0);
648 
649 	newRoot = GC_IDX2PTR(idx);
650 	newRoot->ref = ref; /* GC_ROOT tag is 0 */
651 	GC_TRACE_SET_COLOR(ref, GC_PURPLE);
652 
653 	idx = gc_compress(idx);
654 	GC_REF_SET_INFO(ref, idx | GC_PURPLE);
655 	GC_G(num_roots)++;
656 
657 	GC_BENCH_INC(zval_buffered);
658 	GC_BENCH_INC(root_buf_length);
659 	GC_BENCH_PEAK(root_buf_peak, root_buf_length);
660 }
661 
gc_remove_compressed(zend_refcounted * ref,uint32_t idx)662 static zend_never_inline void ZEND_FASTCALL gc_remove_compressed(zend_refcounted *ref, uint32_t idx)
663 {
664 	gc_root_buffer *root = gc_decompress(ref, idx);
665 	gc_remove_from_roots(root);
666 }
667 
gc_remove_from_buffer(zend_refcounted * ref)668 ZEND_API void ZEND_FASTCALL gc_remove_from_buffer(zend_refcounted *ref)
669 {
670 	gc_root_buffer *root;
671 	uint32_t idx = GC_REF_ADDRESS(ref);
672 
673 	GC_BENCH_INC(zval_remove_from_buffer);
674 
675 	if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
676 		GC_TRACE_SET_COLOR(ref, GC_BLACK);
677 	}
678 	GC_REF_SET_INFO(ref, 0);
679 
680 	/* Perform decompression only in case of large buffers */
681 	if (UNEXPECTED(GC_G(first_unused) >= GC_MAX_UNCOMPRESSED)) {
682 		gc_remove_compressed(ref, idx);
683 		return;
684 	}
685 
686 	ZEND_ASSERT(idx);
687 	root = GC_IDX2PTR(idx);
688 	gc_remove_from_roots(root);
689 }
690 
gc_scan_black(zend_refcounted * ref,gc_stack * stack)691 static void gc_scan_black(zend_refcounted *ref, gc_stack *stack)
692 {
693 	HashTable *ht = NULL;
694 	Bucket *p, *end;
695 	zval *zv;
696 	GC_STACK_DCL(stack);
697 
698 tail_call:
699 	if (GC_TYPE(ref) == IS_OBJECT) {
700 		zend_object *obj = (zend_object*)ref;
701 
702 		if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
703 			int n;
704 			zval *zv, *end;
705 			zval tmp;
706 
707 			ZVAL_OBJ(&tmp, obj);
708 			ht = obj->handlers->get_gc(&tmp, &zv, &n);
709 			end = zv + n;
710 			if (EXPECTED(!ht) || UNEXPECTED(GC_REF_CHECK_COLOR(ht, GC_BLACK))) {
711 				ht = NULL;
712 				if (!n) goto next;
713 				while (!Z_REFCOUNTED_P(--end)) {
714 					if (zv == end) goto next;
715 				}
716 			} else {
717 				GC_REF_SET_BLACK(ht);
718 			}
719 			while (zv != end) {
720 				if (Z_REFCOUNTED_P(zv)) {
721 					ref = Z_COUNTED_P(zv);
722 					GC_ADDREF(ref);
723 					if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
724 						GC_REF_SET_BLACK(ref);
725 						GC_STACK_PUSH(ref);
726 					}
727 				}
728 				zv++;
729 			}
730 			if (EXPECTED(!ht)) {
731 				ref = Z_COUNTED_P(zv);
732 				GC_ADDREF(ref);
733 				if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
734 					GC_REF_SET_BLACK(ref);
735 					goto tail_call;
736 				}
737 				goto next;
738 			}
739 		} else {
740 			goto next;
741 		}
742 	} else if (GC_TYPE(ref) == IS_ARRAY) {
743 		if ((zend_array*)ref != &EG(symbol_table)) {
744 			ht = (zend_array*)ref;
745 		} else {
746 			goto next;
747 		}
748 	} else if (GC_TYPE(ref) == IS_REFERENCE) {
749 		if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
750 			ref = Z_COUNTED(((zend_reference*)ref)->val);
751 			GC_ADDREF(ref);
752 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
753 				GC_REF_SET_BLACK(ref);
754 				goto tail_call;
755 			}
756 		}
757 		goto next;
758 	} else {
759 		goto next;
760 	}
761 
762 	if (!ht->nNumUsed) goto next;
763 	p = ht->arData;
764 	end = p + ht->nNumUsed;
765 	while (1) {
766 		end--;
767 		zv = &end->val;
768 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
769 			zv = Z_INDIRECT_P(zv);
770 		}
771 		if (Z_REFCOUNTED_P(zv)) {
772 			break;
773 		}
774 		if (p == end) goto next;
775 	}
776 	while (p != end) {
777 		zv = &p->val;
778 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
779 			zv = Z_INDIRECT_P(zv);
780 		}
781 		if (Z_REFCOUNTED_P(zv)) {
782 			ref = Z_COUNTED_P(zv);
783 			GC_ADDREF(ref);
784 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
785 				GC_REF_SET_BLACK(ref);
786 				GC_STACK_PUSH(ref);
787 			}
788 		}
789 		p++;
790 	}
791 	zv = &p->val;
792 	if (Z_TYPE_P(zv) == IS_INDIRECT) {
793 		zv = Z_INDIRECT_P(zv);
794 	}
795 	ref = Z_COUNTED_P(zv);
796 	GC_ADDREF(ref);
797 	if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
798 		GC_REF_SET_BLACK(ref);
799 		goto tail_call;
800 	}
801 
802 next:
803 	ref = GC_STACK_POP();
804 	if (ref) {
805 		goto tail_call;
806 	}
807 }
808 
gc_mark_grey(zend_refcounted * ref,gc_stack * stack)809 static void gc_mark_grey(zend_refcounted *ref, gc_stack *stack)
810 {
811 	HashTable *ht = NULL;
812 	Bucket *p, *end;
813 	zval *zv;
814 	GC_STACK_DCL(stack);
815 
816 	do {
817 		GC_BENCH_INC(zval_marked_grey);
818 
819 		if (GC_TYPE(ref) == IS_OBJECT) {
820 			zend_object *obj = (zend_object*)ref;
821 
822 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
823 				int n;
824 				zval *zv, *end;
825 				zval tmp;
826 
827 				ZVAL_OBJ(&tmp, obj);
828 				ht = obj->handlers->get_gc(&tmp, &zv, &n);
829 				end = zv + n;
830 				if (EXPECTED(!ht) || UNEXPECTED(GC_REF_CHECK_COLOR(ht, GC_GREY))) {
831 					ht = NULL;
832 					if (!n) goto next;
833 					while (!Z_REFCOUNTED_P(--end)) {
834 						if (zv == end) goto next;
835 					}
836 				} else {
837 					GC_REF_SET_COLOR(ht, GC_GREY);
838 				}
839 				while (zv != end) {
840 					if (Z_REFCOUNTED_P(zv)) {
841 						ref = Z_COUNTED_P(zv);
842 						GC_DELREF(ref);
843 						if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
844 							GC_REF_SET_COLOR(ref, GC_GREY);
845 							GC_STACK_PUSH(ref);
846 						}
847 					}
848 					zv++;
849 				}
850 				if (EXPECTED(!ht)) {
851 					ref = Z_COUNTED_P(zv);
852 					GC_DELREF(ref);
853 					if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
854 						GC_REF_SET_COLOR(ref, GC_GREY);
855 						continue;
856 					}
857 					goto next;
858 				}
859 			} else {
860 				goto next;
861 			}
862 		} else if (GC_TYPE(ref) == IS_ARRAY) {
863 			if (((zend_array*)ref) == &EG(symbol_table)) {
864 				GC_REF_SET_BLACK(ref);
865 				goto next;
866 			} else {
867 				ht = (zend_array*)ref;
868 			}
869 		} else if (GC_TYPE(ref) == IS_REFERENCE) {
870 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
871 				ref = Z_COUNTED(((zend_reference*)ref)->val);
872 				GC_DELREF(ref);
873 				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
874 					GC_REF_SET_COLOR(ref, GC_GREY);
875 					continue;
876 				}
877 			}
878 			goto next;
879 		} else {
880 			goto next;
881 		}
882 
883 		if (!ht->nNumUsed) goto next;
884 		p = ht->arData;
885 		end = p + ht->nNumUsed;
886 		while (1) {
887 			end--;
888 			zv = &end->val;
889 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
890 				zv = Z_INDIRECT_P(zv);
891 			}
892 			if (Z_REFCOUNTED_P(zv)) {
893 				break;
894 			}
895 			if (p == end) goto next;
896 		}
897 		while (p != end) {
898 			zv = &p->val;
899 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
900 				zv = Z_INDIRECT_P(zv);
901 			}
902 			if (Z_REFCOUNTED_P(zv)) {
903 				ref = Z_COUNTED_P(zv);
904 				GC_DELREF(ref);
905 				if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
906 					GC_REF_SET_COLOR(ref, GC_GREY);
907 					GC_STACK_PUSH(ref);
908 				}
909 			}
910 			p++;
911 		}
912 		zv = &p->val;
913 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
914 			zv = Z_INDIRECT_P(zv);
915 		}
916 		ref = Z_COUNTED_P(zv);
917 		GC_DELREF(ref);
918 		if (!GC_REF_CHECK_COLOR(ref, GC_GREY)) {
919 			GC_REF_SET_COLOR(ref, GC_GREY);
920 			continue;
921 		}
922 
923 next:
924 		ref = GC_STACK_POP();
925 	} while (ref);
926 }
927 
928 /* Two-Finger compaction algorithm */
gc_compact(void)929 static void gc_compact(void)
930 {
931 	if (GC_G(num_roots) + GC_FIRST_ROOT != GC_G(first_unused)) {
932 		if (GC_G(num_roots)) {
933 			gc_root_buffer *free = GC_IDX2PTR(GC_FIRST_ROOT);
934 			gc_root_buffer *scan = GC_IDX2PTR(GC_G(first_unused) - 1);
935 			gc_root_buffer *end  = GC_IDX2PTR(GC_G(num_roots));
936 			uint32_t idx;
937 			zend_refcounted *p;
938 
939 			while (free < scan) {
940 				while (!GC_IS_UNUSED(free->ref)) {
941 					free++;
942 				}
943 				while (GC_IS_UNUSED(scan->ref)) {
944 					scan--;
945 				}
946 				if (scan > free) {
947 					p = scan->ref;
948 					free->ref = p;
949 					p = GC_GET_PTR(p);
950 					idx = gc_compress(GC_PTR2IDX(free));
951 					GC_REF_SET_INFO(p, idx | GC_REF_COLOR(p));
952 					free++;
953 					scan--;
954 					if (scan <= end) {
955 						break;
956 					}
957 				}
958 			}
959 		}
960 		GC_G(unused) = GC_INVALID;
961 		GC_G(first_unused) = GC_G(num_roots) + GC_FIRST_ROOT;
962 	}
963 }
964 
gc_mark_roots(gc_stack * stack)965 static void gc_mark_roots(gc_stack *stack)
966 {
967 	gc_root_buffer *current, *last;
968 
969 	gc_compact();
970 
971 	current = GC_IDX2PTR(GC_FIRST_ROOT);
972 	last = GC_IDX2PTR(GC_G(first_unused));
973 	while (current != last) {
974 		if (GC_IS_ROOT(current->ref)) {
975 			if (GC_REF_CHECK_COLOR(current->ref, GC_PURPLE)) {
976 				GC_REF_SET_COLOR(current->ref, GC_GREY);
977 				gc_mark_grey(current->ref, stack);
978 			}
979 		}
980 		current++;
981 	}
982 }
983 
gc_scan(zend_refcounted * ref,gc_stack * stack)984 static void gc_scan(zend_refcounted *ref, gc_stack *stack)
985 {
986 	HashTable *ht = NULL;
987 	Bucket *p, *end;
988 	zval *zv;
989 	GC_STACK_DCL(stack);
990 
991 tail_call:
992 	if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
993 		if (GC_REFCOUNT(ref) > 0) {
994 			if (!GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
995 				GC_REF_SET_BLACK(ref);
996 				if (UNEXPECTED(!_stack->next)) {
997 					gc_stack_next(_stack);
998 				}
999 				/* Split stack and reuse the tail */
1000 				_stack->next->prev = NULL;
1001 				gc_scan_black(ref, _stack->next);
1002 				_stack->next->prev = _stack;
1003 			}
1004 		} else {
1005 			if (GC_TYPE(ref) == IS_OBJECT) {
1006 				zend_object *obj = (zend_object*)ref;
1007 
1008 				if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
1009 					int n;
1010 					zval *zv, *end;
1011 					zval tmp;
1012 
1013 					ZVAL_OBJ(&tmp, obj);
1014 					ht = obj->handlers->get_gc(&tmp, &zv, &n);
1015 					end = zv + n;
1016 					if (EXPECTED(!ht) || UNEXPECTED(!GC_REF_CHECK_COLOR(ht, GC_GREY))) {
1017 						ht = NULL;
1018 						if (!n) goto next;
1019 						while (!Z_REFCOUNTED_P(--end)) {
1020 							if (zv == end) goto next;
1021 						}
1022 					} else {
1023 						GC_REF_SET_COLOR(ht, GC_WHITE);
1024 					}
1025 					while (zv != end) {
1026 						if (Z_REFCOUNTED_P(zv)) {
1027 							ref = Z_COUNTED_P(zv);
1028 							if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
1029 								GC_REF_SET_COLOR(ref, GC_WHITE);
1030 								GC_STACK_PUSH(ref);
1031 							}
1032 						}
1033 						zv++;
1034 					}
1035 					if (EXPECTED(!ht)) {
1036 						ref = Z_COUNTED_P(zv);
1037 						if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
1038 							GC_REF_SET_COLOR(ref, GC_WHITE);
1039 							goto tail_call;
1040 						}
1041 						goto next;
1042 					}
1043 				} else {
1044 					goto next;
1045 				}
1046 			} else if (GC_TYPE(ref) == IS_ARRAY) {
1047 				if ((zend_array*)ref == &EG(symbol_table)) {
1048 					GC_REF_SET_BLACK(ref);
1049 					goto next;
1050 				} else {
1051 					ht = (zend_array*)ref;
1052 				}
1053 			} else if (GC_TYPE(ref) == IS_REFERENCE) {
1054 				if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
1055 					ref = Z_COUNTED(((zend_reference*)ref)->val);
1056 					if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
1057 						GC_REF_SET_COLOR(ref, GC_WHITE);
1058 						goto tail_call;
1059 					}
1060 				}
1061 				goto next;
1062 			} else {
1063 				goto next;
1064 			}
1065 
1066 			if (!ht->nNumUsed) goto next;
1067 			p = ht->arData;
1068 			end = p + ht->nNumUsed;
1069 			while (1) {
1070 				end--;
1071 				zv = &end->val;
1072 				if (Z_TYPE_P(zv) == IS_INDIRECT) {
1073 					zv = Z_INDIRECT_P(zv);
1074 				}
1075 				if (Z_REFCOUNTED_P(zv)) {
1076 					break;
1077 				}
1078 				if (p == end) goto next;
1079 			}
1080 			while (p != end) {
1081 				zv = &p->val;
1082 				if (Z_TYPE_P(zv) == IS_INDIRECT) {
1083 					zv = Z_INDIRECT_P(zv);
1084 				}
1085 				if (Z_REFCOUNTED_P(zv)) {
1086 					ref = Z_COUNTED_P(zv);
1087 					if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
1088 						GC_REF_SET_COLOR(ref, GC_WHITE);
1089 						GC_STACK_PUSH(ref);
1090 					}
1091 				}
1092 				p++;
1093 			}
1094 			zv = &p->val;
1095 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
1096 				zv = Z_INDIRECT_P(zv);
1097 			}
1098 			ref = Z_COUNTED_P(zv);
1099 			if (GC_REF_CHECK_COLOR(ref, GC_GREY)) {
1100 				GC_REF_SET_COLOR(ref, GC_WHITE);
1101 				goto tail_call;
1102 			}
1103 		}
1104 	}
1105 
1106 next:
1107 	ref = GC_STACK_POP();
1108 	if (ref) {
1109 		goto tail_call;
1110 	}
1111 }
1112 
gc_scan_roots(gc_stack * stack)1113 static void gc_scan_roots(gc_stack *stack)
1114 {
1115 	gc_root_buffer *current = GC_IDX2PTR(GC_FIRST_ROOT);
1116 	gc_root_buffer *last = GC_IDX2PTR(GC_G(first_unused));
1117 
1118 	while (current != last) {
1119 		if (GC_IS_ROOT(current->ref)) {
1120 			if (GC_REF_CHECK_COLOR(current->ref, GC_GREY)) {
1121 				GC_REF_SET_COLOR(current->ref, GC_WHITE);
1122 				gc_scan(current->ref, stack);
1123 			}
1124 		}
1125 		current++;
1126 	}
1127 }
1128 
gc_add_garbage(zend_refcounted * ref)1129 static void gc_add_garbage(zend_refcounted *ref)
1130 {
1131 	uint32_t idx;
1132 	gc_root_buffer *buf;
1133 
1134 	if (GC_HAS_UNUSED()) {
1135 		idx = GC_FETCH_UNUSED();
1136 	} else if (GC_HAS_NEXT_UNUSED()) {
1137 		idx = GC_FETCH_NEXT_UNUSED();
1138 	} else {
1139 		gc_grow_root_buffer();
1140 		if (UNEXPECTED(!GC_HAS_NEXT_UNUSED())) {
1141 			return;
1142 		}
1143 		idx = GC_FETCH_NEXT_UNUSED();
1144 	}
1145 
1146 	buf = GC_IDX2PTR(idx);
1147 	buf->ref = GC_MAKE_GARBAGE(ref);
1148 
1149 	idx = gc_compress(idx);
1150 	GC_REF_SET_INFO(ref, idx | GC_BLACK);
1151 	GC_G(num_roots)++;
1152 }
1153 
gc_collect_white(zend_refcounted * ref,uint32_t * flags,gc_stack * stack)1154 static int gc_collect_white(zend_refcounted *ref, uint32_t *flags, gc_stack *stack)
1155 {
1156 	int count = 0;
1157 	HashTable *ht = NULL;
1158 	Bucket *p, *end;
1159 	zval *zv;
1160 	GC_STACK_DCL(stack);
1161 
1162 	do {
1163 		/* don't count references for compatibility ??? */
1164 		if (GC_TYPE(ref) != IS_REFERENCE) {
1165 			count++;
1166 		}
1167 
1168 		if (GC_TYPE(ref) == IS_OBJECT) {
1169 			zend_object *obj = (zend_object*)ref;
1170 
1171 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
1172 				int n;
1173 				zval *zv, *end;
1174 				zval tmp;
1175 
1176 				/* optimization: color is GC_BLACK (0) */
1177 				if (!GC_INFO(ref)) {
1178 					gc_add_garbage(ref);
1179 				}
1180 				if (!(OBJ_FLAGS(obj) & IS_OBJ_DESTRUCTOR_CALLED)
1181 				 && (obj->handlers->dtor_obj != zend_objects_destroy_object
1182 				  || obj->ce->destructor != NULL)) {
1183 					*flags |= GC_HAS_DESTRUCTORS;
1184 				}
1185 				ZVAL_OBJ(&tmp, obj);
1186 				ht = obj->handlers->get_gc(&tmp, &zv, &n);
1187 				end = zv + n;
1188 				if (EXPECTED(!ht) || UNEXPECTED(GC_REF_CHECK_COLOR(ht, GC_BLACK))) {
1189 					ht = NULL;
1190 					if (!n) goto next;
1191 					while (!Z_REFCOUNTED_P(--end)) {
1192 						if (zv == end) goto next;
1193 					}
1194 				} else {
1195 					GC_REF_SET_BLACK(ht);
1196 				}
1197 				while (zv != end) {
1198 					if (Z_REFCOUNTED_P(zv)) {
1199 						ref = Z_COUNTED_P(zv);
1200 						GC_ADDREF(ref);
1201 						if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1202 							GC_REF_SET_BLACK(ref);
1203 							GC_STACK_PUSH(ref);
1204 						}
1205 					}
1206 					zv++;
1207 				}
1208 				if (EXPECTED(!ht)) {
1209 					ref = Z_COUNTED_P(zv);
1210 					GC_ADDREF(ref);
1211 					if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1212 						GC_REF_SET_BLACK(ref);
1213 						continue;
1214 					}
1215 					goto next;
1216 				}
1217 			} else {
1218 				goto next;
1219 			}
1220 		} else if (GC_TYPE(ref) == IS_ARRAY) {
1221 			/* optimization: color is GC_BLACK (0) */
1222 			if (!GC_INFO(ref)) {
1223 				gc_add_garbage(ref);
1224 			}
1225 			ht = (zend_array*)ref;
1226 		} else if (GC_TYPE(ref) == IS_REFERENCE) {
1227 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
1228 				ref = Z_COUNTED(((zend_reference*)ref)->val);
1229 				GC_ADDREF(ref);
1230 				if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1231 					GC_REF_SET_BLACK(ref);
1232 					continue;
1233 				}
1234 			}
1235 			goto next;
1236 		} else {
1237 			goto next;
1238 		}
1239 
1240 		if (!ht->nNumUsed) goto next;
1241 		p = ht->arData;
1242 		end = p + ht->nNumUsed;
1243 		while (1) {
1244 			end--;
1245 			zv = &end->val;
1246 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
1247 				zv = Z_INDIRECT_P(zv);
1248 			}
1249 			if (Z_REFCOUNTED_P(zv)) {
1250 				break;
1251 			}
1252 			if (p == end) goto next;
1253 		}
1254 		while (p != end) {
1255 			zv = &p->val;
1256 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
1257 				zv = Z_INDIRECT_P(zv);
1258 			}
1259 			if (Z_REFCOUNTED_P(zv)) {
1260 				ref = Z_COUNTED_P(zv);
1261 				GC_ADDREF(ref);
1262 				if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1263 					GC_REF_SET_BLACK(ref);
1264 					GC_STACK_PUSH(ref);
1265 				}
1266 			}
1267 			p++;
1268 		}
1269 		zv = &p->val;
1270 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
1271 			zv = Z_INDIRECT_P(zv);
1272 		}
1273 		ref = Z_COUNTED_P(zv);
1274 		GC_ADDREF(ref);
1275 		if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1276 			GC_REF_SET_BLACK(ref);
1277 			continue;
1278 		}
1279 
1280 next:
1281 		ref = GC_STACK_POP();
1282 	} while (ref);
1283 
1284 	return count;
1285 }
1286 
gc_collect_roots(uint32_t * flags,gc_stack * stack)1287 static int gc_collect_roots(uint32_t *flags, gc_stack *stack)
1288 {
1289 	uint32_t idx, end;
1290 	zend_refcounted *ref;
1291 	int count = 0;
1292 	gc_root_buffer *current = GC_IDX2PTR(GC_FIRST_ROOT);
1293 	gc_root_buffer *last = GC_IDX2PTR(GC_G(first_unused));
1294 
1295 	/* remove non-garbage from the list */
1296 	while (current != last) {
1297 		if (GC_IS_ROOT(current->ref)) {
1298 			if (GC_REF_CHECK_COLOR(current->ref, GC_BLACK)) {
1299 				GC_REF_SET_INFO(current->ref, 0); /* reset GC_ADDRESS() and keep GC_BLACK */
1300 				gc_remove_from_roots(current);
1301 			}
1302 		}
1303 		current++;
1304 	}
1305 
1306 	gc_compact();
1307 
1308 	/* Root buffer might be reallocated during gc_collect_white,
1309 	 * make sure to reload pointers. */
1310 	idx = GC_FIRST_ROOT;
1311 	end = GC_G(first_unused);
1312 	while (idx != end) {
1313 		current = GC_IDX2PTR(idx);
1314 		ref = current->ref;
1315 		ZEND_ASSERT(GC_IS_ROOT(ref));
1316 		current->ref = GC_MAKE_GARBAGE(ref);
1317 		if (GC_REF_CHECK_COLOR(ref, GC_WHITE)) {
1318 			GC_REF_SET_BLACK(ref);
1319 			count += gc_collect_white(ref, flags, stack);
1320 		}
1321 		idx++;
1322 	}
1323 
1324 	return count;
1325 }
1326 
gc_remove_nested_data_from_buffer(zend_refcounted * ref,gc_root_buffer * root)1327 static int gc_remove_nested_data_from_buffer(zend_refcounted *ref, gc_root_buffer *root)
1328 {
1329 	HashTable *ht = NULL;
1330 	Bucket *p, *end;
1331 	zval *zv;
1332 	int count = 0;
1333 
1334 tail_call:
1335 	do {
1336 		if (root) {
1337 			root = NULL;
1338 			count++;
1339 		} else if (GC_REF_ADDRESS(ref) != 0
1340 		 && GC_REF_CHECK_COLOR(ref, GC_BLACK)) {
1341 			GC_TRACE_REF(ref, "removing from buffer");
1342 			GC_REMOVE_FROM_BUFFER(ref);
1343 			count++;
1344 		} else if (GC_TYPE(ref) == IS_REFERENCE) {
1345 			if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
1346 				ref = Z_COUNTED(((zend_reference*)ref)->val);
1347 				goto tail_call;
1348 			}
1349 			return count;
1350 		} else {
1351 			return count;
1352 		}
1353 
1354 		if (GC_TYPE(ref) == IS_OBJECT) {
1355 			zend_object *obj = (zend_object*)ref;
1356 
1357 			if (EXPECTED(!(OBJ_FLAGS(ref) & IS_OBJ_FREE_CALLED))) {
1358 				int n;
1359 				zval *zv, *end;
1360 				zval tmp;
1361 
1362 				ZVAL_OBJ(&tmp, obj);
1363 				ht = obj->handlers->get_gc(&tmp, &zv, &n);
1364 				end = zv + n;
1365 				if (EXPECTED(!ht)) {
1366 					if (!n) return count;
1367 					while (!Z_REFCOUNTED_P(--end)) {
1368 						if (zv == end) return count;
1369 					}
1370 				}
1371 				while (zv != end) {
1372 					if (Z_REFCOUNTED_P(zv)) {
1373 						ref = Z_COUNTED_P(zv);
1374 						count += gc_remove_nested_data_from_buffer(ref, NULL);
1375 					}
1376 					zv++;
1377 				}
1378 				if (EXPECTED(!ht)) {
1379 					ref = Z_COUNTED_P(zv);
1380 					goto tail_call;
1381 				}
1382 				if (GC_REF_ADDRESS(ht) != 0 && GC_REF_CHECK_COLOR(ht, GC_BLACK)) {
1383 					GC_TRACE_REF(ht, "removing from buffer");
1384 					GC_REMOVE_FROM_BUFFER(ht);
1385 				}
1386 			} else {
1387 				return count;
1388 			}
1389 		} else if (GC_TYPE(ref) == IS_ARRAY) {
1390 			ht = (zend_array*)ref;
1391 		} else {
1392 			return count;
1393 		}
1394 
1395 		if (!ht->nNumUsed) return count;
1396 		p = ht->arData;
1397 		end = p + ht->nNumUsed;
1398 		while (1) {
1399 			end--;
1400 			zv = &end->val;
1401 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
1402 				zv = Z_INDIRECT_P(zv);
1403 			}
1404 			if (Z_REFCOUNTED_P(zv)) {
1405 				break;
1406 			}
1407 			if (p == end) return count;
1408 		}
1409 		while (p != end) {
1410 			zv = &p->val;
1411 			if (Z_TYPE_P(zv) == IS_INDIRECT) {
1412 				zv = Z_INDIRECT_P(zv);
1413 			}
1414 			if (Z_REFCOUNTED_P(zv)) {
1415 				ref = Z_COUNTED_P(zv);
1416 				count += gc_remove_nested_data_from_buffer(ref, NULL);
1417 			}
1418 			p++;
1419 		}
1420 		zv = &p->val;
1421 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
1422 			zv = Z_INDIRECT_P(zv);
1423 		}
1424 		ref = Z_COUNTED_P(zv);
1425 		goto tail_call;
1426 	} while (0);
1427 }
1428 
zend_gc_collect_cycles(void)1429 ZEND_API int zend_gc_collect_cycles(void)
1430 {
1431 	int count = 0;
1432 
1433 	if (GC_G(num_roots)) {
1434 		gc_root_buffer *current, *last;
1435 		zend_refcounted *p;
1436 		uint32_t gc_flags = 0;
1437 		uint32_t idx, end;
1438 		gc_stack stack;
1439 
1440 		stack.prev = NULL;
1441 		stack.next = NULL;
1442 
1443 		if (GC_G(gc_active)) {
1444 			return 0;
1445 		}
1446 
1447 		GC_TRACE("Collecting cycles");
1448 		GC_G(gc_runs)++;
1449 		GC_G(gc_active) = 1;
1450 
1451 		GC_TRACE("Marking roots");
1452 		gc_mark_roots(&stack);
1453 		GC_TRACE("Scanning roots");
1454 		gc_scan_roots(&stack);
1455 
1456 		GC_TRACE("Collecting roots");
1457 		count = gc_collect_roots(&gc_flags, &stack);
1458 
1459 		gc_stack_free(&stack);
1460 
1461 		if (!GC_G(num_roots)) {
1462 			/* nothing to free */
1463 			GC_TRACE("Nothing to free");
1464 			GC_G(gc_active) = 0;
1465 			return 0;
1466 		}
1467 
1468 		end = GC_G(first_unused);
1469 
1470 		if (gc_flags & GC_HAS_DESTRUCTORS) {
1471 			GC_TRACE("Calling destructors");
1472 
1473 			/* During a destructor call, new externally visible references to nested data may
1474 			 * be introduced. These references can be introduced in a way that does not
1475 			 * modify any refcounts, so we have no real way to detect this situation
1476 			 * short of rerunning full GC tracing. What we do instead is to only run
1477 			 * destructors at this point, and leave the actual freeing of the objects
1478 			 * until the next GC run. */
1479 
1480 			/* Mark all roots for which a dtor will be invoked as DTOR_GARBAGE. Additionally
1481 			 * color them purple. This serves a double purpose: First, they should be
1482 			 * considered new potential roots for the next GC run. Second, it will prevent
1483 			 * their removal from the root buffer by nested data removal. */
1484 			idx = GC_FIRST_ROOT;
1485 			current = GC_IDX2PTR(GC_FIRST_ROOT);
1486 			while (idx != end) {
1487 				if (GC_IS_GARBAGE(current->ref)) {
1488 					p = GC_GET_PTR(current->ref);
1489 					if (GC_TYPE(p) == IS_OBJECT && !(OBJ_FLAGS(p) & IS_OBJ_DESTRUCTOR_CALLED)) {
1490 						zend_object *obj = (zend_object *) p;
1491 						if (obj->handlers->dtor_obj != zend_objects_destroy_object
1492 							|| obj->ce->destructor) {
1493 							current->ref = GC_MAKE_DTOR_GARBAGE(obj);
1494 							GC_REF_SET_COLOR(obj, GC_PURPLE);
1495 						} else {
1496 							GC_ADD_FLAGS(obj, IS_OBJ_DESTRUCTOR_CALLED);
1497 						}
1498 					}
1499 				}
1500 				current++;
1501 				idx++;
1502 			}
1503 
1504 			/* Remove nested data for objects on which a destructor will be called.
1505 			 * This will not remove the objects themselves, as they have been colored
1506 			 * purple. */
1507 			idx = GC_FIRST_ROOT;
1508 			current = GC_IDX2PTR(GC_FIRST_ROOT);
1509 			while (idx != end) {
1510 				if (GC_IS_DTOR_GARBAGE(current->ref)) {
1511 					p = GC_GET_PTR(current->ref);
1512 					count -= gc_remove_nested_data_from_buffer(p, current);
1513 				}
1514 				current++;
1515 				idx++;
1516 			}
1517 
1518 			/* Actually call destructors.
1519 			 *
1520 			 * The root buffer might be reallocated during destructors calls,
1521 			 * make sure to reload pointers as necessary. */
1522 			idx = GC_FIRST_ROOT;
1523 			while (idx != end) {
1524 				current = GC_IDX2PTR(idx);
1525 				if (GC_IS_DTOR_GARBAGE(current->ref)) {
1526 					p = GC_GET_PTR(current->ref);
1527 					/* Mark this is as a normal root for the next GC run,
1528 					 * it's no longer garbage for this run. */
1529 					current->ref = p;
1530 					/* Double check that the destructor hasn't been called yet. It could have
1531 					 * already been invoked indirectly by some other destructor. */
1532 					if (!(OBJ_FLAGS(p) & IS_OBJ_DESTRUCTOR_CALLED)) {
1533 						zend_object *obj = (zend_object*)p;
1534 						GC_TRACE_REF(obj, "calling destructor");
1535 						GC_ADD_FLAGS(obj, IS_OBJ_DESTRUCTOR_CALLED);
1536 						GC_ADDREF(obj);
1537 						obj->handlers->dtor_obj(obj);
1538 						GC_DELREF(obj);
1539 					}
1540 				}
1541 				idx++;
1542 			}
1543 
1544 			if (GC_G(gc_protected)) {
1545 				/* something went wrong */
1546 				return 0;
1547 			}
1548 		}
1549 
1550 		/* Destroy zvals. The root buffer may be reallocated. */
1551 		GC_TRACE("Destroying zvals");
1552 		idx = GC_FIRST_ROOT;
1553 		while (idx != end) {
1554 			current = GC_IDX2PTR(idx);
1555 			if (GC_IS_GARBAGE(current->ref)) {
1556 				p = GC_GET_PTR(current->ref);
1557 				GC_TRACE_REF(p, "destroying");
1558 				if (GC_TYPE(p) == IS_OBJECT) {
1559 					zend_object *obj = (zend_object*)p;
1560 
1561 					EG(objects_store).object_buckets[obj->handle] = SET_OBJ_INVALID(obj);
1562 					GC_TYPE_INFO(obj) = IS_NULL |
1563 						(GC_TYPE_INFO(obj) & ~GC_TYPE_MASK);
1564 					/* Modify current before calling free_obj (bug #78811: free_obj() can cause the root buffer (with current) to be reallocated.) */
1565 					current->ref = GC_MAKE_GARBAGE(((char*)obj) - obj->handlers->offset);
1566 					if (!(OBJ_FLAGS(obj) & IS_OBJ_FREE_CALLED)) {
1567 						GC_ADD_FLAGS(obj, IS_OBJ_FREE_CALLED);
1568 						GC_ADDREF(obj);
1569 						obj->handlers->free_obj(obj);
1570 						GC_DELREF(obj);
1571 					}
1572 
1573 					ZEND_OBJECTS_STORE_ADD_TO_FREE_LIST(obj->handle);
1574 				} else if (GC_TYPE(p) == IS_ARRAY) {
1575 					zend_array *arr = (zend_array*)p;
1576 
1577 					GC_TYPE_INFO(arr) = IS_NULL |
1578 						(GC_TYPE_INFO(arr) & ~GC_TYPE_MASK);
1579 
1580 					/* GC may destroy arrays with rc>1. This is valid and safe. */
1581 					HT_ALLOW_COW_VIOLATION(arr);
1582 
1583 					zend_hash_destroy(arr);
1584 				}
1585 			}
1586 			idx++;
1587 		}
1588 
1589 		/* Free objects */
1590 		current = GC_IDX2PTR(GC_FIRST_ROOT);
1591 		last = GC_IDX2PTR(end);
1592 		while (current != last) {
1593 			if (GC_IS_GARBAGE(current->ref)) {
1594 				p = GC_GET_PTR(current->ref);
1595 				GC_LINK_UNUSED(current);
1596 				GC_G(num_roots)--;
1597 				efree(p);
1598 			}
1599 			current++;
1600 		}
1601 
1602 		GC_TRACE("Collection finished");
1603 		GC_G(collected) += count;
1604 		GC_G(gc_active) = 0;
1605 	}
1606 
1607 	gc_compact();
1608 
1609 	return count;
1610 }
1611 
zend_gc_get_status(zend_gc_status * status)1612 ZEND_API void zend_gc_get_status(zend_gc_status *status)
1613 {
1614 	status->runs = GC_G(gc_runs);
1615 	status->collected = GC_G(collected);
1616 	status->threshold = GC_G(gc_threshold);
1617 	status->num_roots = GC_G(num_roots);
1618 }
1619 
1620 #ifdef ZTS
zend_gc_globals_size(void)1621 size_t zend_gc_globals_size(void)
1622 {
1623 	return sizeof(zend_gc_globals);
1624 }
1625 #endif
1626