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