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