1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2018 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@zend.com> |
17 +----------------------------------------------------------------------+
18 */
19
20 /* $Id$ */
21
22
23 /**
24 * zend_gc_collect_cycles
25 * ======================
26 *
27 * Colors and its meaning
28 * ----------------------
29 *
30 * BLACK (GC_BLACK) - In use or free.
31 * GREY (GC_GREY) - Possible member of cycle.
32 * WHITE (GC_WHITE) - Member of garbage cycle.
33 * PURPLE (GC_PURPLE) - Possible root of cycle.
34 *
35 * Colors described in the paper but not used
36 * ------------------------------------------
37 *
38 * GREEN - Acyclic
39 * RED - Candidate cycle underogin
40 * ORANGE - Candidate cycle awaiting epoch boundary.
41 *
42 *
43 * Flow
44 * =====
45 *
46 * The garbage collect cycle starts from 'gc_mark_roots', which traverses the
47 * possible roots, and calls mark_grey for roots are marked purple with
48 * depth-first traverse.
49 *
50 * After all possible roots are traversed and marked,
51 * gc_scan_roots will be called, and each root will be called with
52 * gc_scan(root->ref)
53 *
54 * gc_scan checkes the colors of possible members.
55 *
56 * If the node is marked as grey and the refcount > 0
57 * gc_scan_black will be called on that node to scan it's subgraph.
58 * otherwise (refcount == 0), it marks the node white.
59 *
60 * A node MAY be added to possbile roots when ZEND_UNSET_VAR happens or
61 * zend_assign_to_variable is called only when possible garbage node is
62 * produced.
63 * gc_possible_root() will be called to add the nodes to possible roots.
64 *
65 *
66 * For objects, we call their get_gc handler (by default 'zend_std_get_gc') to
67 * get the object properties to scan.
68 *
69 *
70 * @see http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf
71 */
72 #include "zend.h"
73 #include "zend_API.h"
74
75 /* one (0) is reserved */
76 #define GC_ROOT_BUFFER_MAX_ENTRIES 10001
77
78 #define GC_HAS_DESTRUCTORS (1<<0)
79
80 #ifndef ZEND_GC_DEBUG
81 # define ZEND_GC_DEBUG 0
82 #endif
83
84 #ifdef ZTS
85 ZEND_API int gc_globals_id;
86 #else
87 ZEND_API zend_gc_globals gc_globals;
88 #endif
89
90 ZEND_API int (*gc_collect_cycles)(void);
91
92 #if ZEND_GC_DEBUG > 1
93 # define GC_TRACE(format, ...) fprintf(stderr, format "\n", ##__VA_ARGS__);
94 # define GC_TRACE_REF(ref, format, ...) \
95 do { \
96 gc_trace_ref((zend_refcounted *) ref); \
97 fprintf(stderr, format "\n", ##__VA_ARGS__); \
98 } while (0)
99 # define GC_TRACE_SET_COLOR(ref, color) \
100 GC_TRACE_REF(ref, "->%s", gc_color_name(color))
101 #else
102 # define GC_TRACE_REF(ref, format, ...)
103 # define GC_TRACE_SET_COLOR(ref, new_color)
104 # define GC_TRACE(str)
105 #endif
106
107 #define GC_REF_SET_ADDRESS(ref, a) \
108 GC_INFO_SET_ADDRESS(GC_INFO(ref), a)
109 #define GC_REF_GET_COLOR(ref) \
110 GC_INFO_GET_COLOR(GC_INFO(ref))
111 #define GC_REF_SET_COLOR(ref, c) \
112 do { GC_TRACE_SET_COLOR(ref, c); GC_INFO_SET_COLOR(GC_INFO(ref), c); } while (0)
113 #define GC_REF_SET_BLACK(ref) \
114 do { GC_TRACE_SET_COLOR(ref, GC_BLACK); GC_INFO_SET_BLACK(GC_INFO(ref)); } while (0)
115 #define GC_REF_SET_PURPLE(ref) \
116 do { GC_TRACE_SET_COLOR(ref, GC_PURPLE); GC_INFO_SET_PURPLE(GC_INFO(ref)); } while (0)
117
118 #if ZEND_GC_DEBUG > 1
gc_color_name(uint32_t color)119 static const char *gc_color_name(uint32_t color) {
120 switch (color) {
121 case GC_BLACK: return "black";
122 case GC_WHITE: return "white";
123 case GC_GREY: return "grey";
124 case GC_PURPLE: return "purple";
125 default: return "unknown";
126 }
127 }
gc_trace_ref(zend_refcounted * ref)128 static void gc_trace_ref(zend_refcounted *ref) {
129 if (GC_TYPE(ref) == IS_OBJECT) {
130 zend_object *obj = (zend_object *) ref;
131 fprintf(stderr, "[%p] rc=%d addr=%d %s object(%s)#%d ",
132 ref, GC_REFCOUNT(ref), GC_ADDRESS(GC_INFO(ref)),
133 gc_color_name(GC_REF_GET_COLOR(ref)),
134 obj->ce->name->val, obj->handle);
135 } else if (GC_TYPE(ref) == IS_ARRAY) {
136 zend_array *arr = (zend_array *) ref;
137 fprintf(stderr, "[%p] rc=%d addr=%d %s array(%d) ",
138 ref, GC_REFCOUNT(ref), GC_ADDRESS(GC_INFO(ref)),
139 gc_color_name(GC_REF_GET_COLOR(ref)),
140 zend_hash_num_elements(arr));
141 } else {
142 fprintf(stderr, "[%p] rc=%d addr=%d %s %s ",
143 ref, GC_REFCOUNT(ref), GC_ADDRESS(GC_INFO(ref)),
144 gc_color_name(GC_REF_GET_COLOR(ref)),
145 zend_get_type_by_const(GC_TYPE(ref)));
146 }
147 }
148 #endif
149
gc_remove_from_roots(gc_root_buffer * root)150 static zend_always_inline void gc_remove_from_roots(gc_root_buffer *root)
151 {
152 root->next->prev = root->prev;
153 root->prev->next = root->next;
154 root->prev = GC_G(unused);
155 GC_G(unused) = root;
156 GC_BENCH_DEC(root_buf_length);
157 }
158
gc_remove_from_additional_roots(gc_root_buffer * root)159 static zend_always_inline void gc_remove_from_additional_roots(gc_root_buffer *root)
160 {
161 root->next->prev = root->prev;
162 root->prev->next = root->next;
163 }
164
root_buffer_dtor(zend_gc_globals * gc_globals)165 static void root_buffer_dtor(zend_gc_globals *gc_globals)
166 {
167 if (gc_globals->buf) {
168 free(gc_globals->buf);
169 gc_globals->buf = NULL;
170 }
171 }
172
gc_globals_ctor_ex(zend_gc_globals * gc_globals)173 static void gc_globals_ctor_ex(zend_gc_globals *gc_globals)
174 {
175 gc_globals->gc_enabled = 0;
176 gc_globals->gc_active = 0;
177
178 gc_globals->buf = NULL;
179
180 gc_globals->roots.next = &gc_globals->roots;
181 gc_globals->roots.prev = &gc_globals->roots;
182 gc_globals->unused = NULL;
183 gc_globals->next_to_free = NULL;
184
185 gc_globals->to_free.next = &gc_globals->to_free;
186 gc_globals->to_free.prev = &gc_globals->to_free;
187
188 gc_globals->gc_runs = 0;
189 gc_globals->collected = 0;
190
191 gc_globals->additional_buffer = NULL;
192
193 #if GC_BENCH
194 gc_globals->root_buf_length = 0;
195 gc_globals->root_buf_peak = 0;
196 gc_globals->zval_possible_root = 0;
197 gc_globals->zval_buffered = 0;
198 gc_globals->zval_remove_from_buffer = 0;
199 gc_globals->zval_marked_grey = 0;
200 #endif
201 }
202
gc_globals_ctor(void)203 ZEND_API void gc_globals_ctor(void)
204 {
205 #ifdef ZTS
206 ts_allocate_id(&gc_globals_id, sizeof(zend_gc_globals), (ts_allocate_ctor) gc_globals_ctor_ex, (ts_allocate_dtor) root_buffer_dtor);
207 #else
208 gc_globals_ctor_ex(&gc_globals);
209 #endif
210 }
211
gc_globals_dtor(void)212 ZEND_API void gc_globals_dtor(void)
213 {
214 #ifndef ZTS
215 root_buffer_dtor(&gc_globals);
216 #endif
217 }
218
gc_reset(void)219 ZEND_API void gc_reset(void)
220 {
221 GC_G(gc_runs) = 0;
222 GC_G(collected) = 0;
223 GC_G(gc_full) = 0;
224
225 #if GC_BENCH
226 GC_G(root_buf_length) = 0;
227 GC_G(root_buf_peak) = 0;
228 GC_G(zval_possible_root) = 0;
229 GC_G(zval_buffered) = 0;
230 GC_G(zval_remove_from_buffer) = 0;
231 GC_G(zval_marked_grey) = 0;
232 #endif
233
234 GC_G(roots).next = &GC_G(roots);
235 GC_G(roots).prev = &GC_G(roots);
236
237 GC_G(to_free).next = &GC_G(to_free);
238 GC_G(to_free).prev = &GC_G(to_free);
239
240 if (GC_G(buf)) {
241 GC_G(unused) = NULL;
242 GC_G(first_unused) = GC_G(buf) + 1;
243 } else {
244 GC_G(unused) = NULL;
245 GC_G(first_unused) = NULL;
246 GC_G(last_unused) = NULL;
247 }
248
249 GC_G(additional_buffer) = NULL;
250 }
251
gc_init(void)252 ZEND_API void gc_init(void)
253 {
254 if (GC_G(buf) == NULL && GC_G(gc_enabled)) {
255 GC_G(buf) = (gc_root_buffer*) malloc(sizeof(gc_root_buffer) * GC_ROOT_BUFFER_MAX_ENTRIES);
256 GC_G(last_unused) = &GC_G(buf)[GC_ROOT_BUFFER_MAX_ENTRIES];
257 gc_reset();
258 }
259 }
260
gc_possible_root(zend_refcounted * ref)261 ZEND_API void ZEND_FASTCALL gc_possible_root(zend_refcounted *ref)
262 {
263 gc_root_buffer *newRoot;
264
265 if (UNEXPECTED(CG(unclean_shutdown)) || UNEXPECTED(GC_G(gc_active))) {
266 return;
267 }
268
269 ZEND_ASSERT(GC_TYPE(ref) == IS_ARRAY || GC_TYPE(ref) == IS_OBJECT);
270 ZEND_ASSERT(EXPECTED(GC_REF_GET_COLOR(ref) == GC_BLACK));
271 ZEND_ASSERT(!GC_ADDRESS(GC_INFO(ref)));
272
273 GC_BENCH_INC(zval_possible_root);
274
275 newRoot = GC_G(unused);
276 if (newRoot) {
277 GC_G(unused) = newRoot->prev;
278 } else if (GC_G(first_unused) != GC_G(last_unused)) {
279 newRoot = GC_G(first_unused);
280 GC_G(first_unused)++;
281 } else {
282 if (!GC_G(gc_enabled)) {
283 return;
284 }
285 GC_REFCOUNT(ref)++;
286 gc_collect_cycles();
287 GC_REFCOUNT(ref)--;
288 if (UNEXPECTED(GC_REFCOUNT(ref)) == 0) {
289 zval_dtor_func(ref);
290 return;
291 }
292 if (UNEXPECTED(GC_INFO(ref))) {
293 return;
294 }
295 newRoot = GC_G(unused);
296 if (!newRoot) {
297 #if ZEND_GC_DEBUG
298 if (!GC_G(gc_full)) {
299 fprintf(stderr, "GC: no space to record new root candidate\n");
300 GC_G(gc_full) = 1;
301 }
302 #endif
303 return;
304 }
305 GC_G(unused) = newRoot->prev;
306 }
307
308 GC_TRACE_SET_COLOR(ref, GC_PURPLE);
309 GC_INFO(ref) = (newRoot - GC_G(buf)) | GC_PURPLE;
310 newRoot->ref = ref;
311
312 newRoot->next = GC_G(roots).next;
313 newRoot->prev = &GC_G(roots);
314 GC_G(roots).next->prev = newRoot;
315 GC_G(roots).next = newRoot;
316
317 GC_BENCH_INC(zval_buffered);
318 GC_BENCH_INC(root_buf_length);
319 GC_BENCH_PEAK(root_buf_peak, root_buf_length);
320 }
321
gc_find_additional_buffer(zend_refcounted * ref)322 static zend_always_inline gc_root_buffer* gc_find_additional_buffer(zend_refcounted *ref)
323 {
324 gc_additional_buffer *additional_buffer = GC_G(additional_buffer);
325
326 /* We have to check each additional_buffer to find which one holds the ref */
327 while (additional_buffer) {
328 uint32_t idx = GC_ADDRESS(GC_INFO(ref)) - GC_ROOT_BUFFER_MAX_ENTRIES;
329 if (idx < additional_buffer->used) {
330 gc_root_buffer *root = additional_buffer->buf + idx;
331 if (root->ref == ref) {
332 return root;
333 }
334 }
335 additional_buffer = additional_buffer->next;
336 }
337
338 ZEND_ASSERT(0);
339 return NULL;
340 }
341
gc_remove_from_buffer(zend_refcounted * ref)342 ZEND_API void ZEND_FASTCALL gc_remove_from_buffer(zend_refcounted *ref)
343 {
344 gc_root_buffer *root;
345
346 ZEND_ASSERT(GC_ADDRESS(GC_INFO(ref)));
347
348 GC_BENCH_INC(zval_remove_from_buffer);
349
350 if (EXPECTED(GC_ADDRESS(GC_INFO(ref)) < GC_ROOT_BUFFER_MAX_ENTRIES)) {
351 root = GC_G(buf) + GC_ADDRESS(GC_INFO(ref));
352 gc_remove_from_roots(root);
353 } else {
354 root = gc_find_additional_buffer(ref);
355 gc_remove_from_additional_roots(root);
356 }
357 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
358 GC_TRACE_SET_COLOR(ref, GC_PURPLE);
359 }
360 GC_INFO(ref) = 0;
361
362 /* updete next root that is going to be freed */
363 if (GC_G(next_to_free) == root) {
364 GC_G(next_to_free) = root->next;
365 }
366 }
367
gc_scan_black(zend_refcounted * ref)368 static void gc_scan_black(zend_refcounted *ref)
369 {
370 HashTable *ht;
371 Bucket *p, *end;
372 zval *zv;
373
374 tail_call:
375 ht = NULL;
376 GC_REF_SET_BLACK(ref);
377
378 if (GC_TYPE(ref) == IS_OBJECT) {
379 zend_object_get_gc_t get_gc;
380 zend_object *obj = (zend_object*)ref;
381
382 if (EXPECTED(!(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
383 (get_gc = obj->handlers->get_gc) != NULL)) {
384 int n;
385 zval *zv, *end;
386 zval tmp;
387
388 ZVAL_OBJ(&tmp, obj);
389 ht = get_gc(&tmp, &zv, &n);
390 end = zv + n;
391 if (EXPECTED(!ht) || UNEXPECTED(GC_REF_GET_COLOR(ht) == GC_BLACK)) {
392 ht = NULL;
393 if (!n) return;
394 while (!Z_REFCOUNTED_P(--end)) {
395 if (zv == end) return;
396 }
397 } else {
398 GC_REF_SET_BLACK(ht);
399 }
400 while (zv != end) {
401 if (Z_REFCOUNTED_P(zv)) {
402 ref = Z_COUNTED_P(zv);
403 GC_REFCOUNT(ref)++;
404 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
405 gc_scan_black(ref);
406 }
407 }
408 zv++;
409 }
410 if (EXPECTED(!ht)) {
411 ref = Z_COUNTED_P(zv);
412 GC_REFCOUNT(ref)++;
413 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
414 goto tail_call;
415 }
416 return;
417 }
418 } else {
419 return;
420 }
421 } else if (GC_TYPE(ref) == IS_ARRAY) {
422 if ((zend_array*)ref != &EG(symbol_table)) {
423 ht = (zend_array*)ref;
424 } else {
425 return;
426 }
427 } else if (GC_TYPE(ref) == IS_REFERENCE) {
428 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
429 ref = Z_COUNTED(((zend_reference*)ref)->val);
430 GC_REFCOUNT(ref)++;
431 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
432 goto tail_call;
433 }
434 }
435 return;
436 } else {
437 return;
438 }
439
440 if (!ht->nNumUsed) return;
441 p = ht->arData;
442 end = p + ht->nNumUsed;
443 while (1) {
444 end--;
445 zv = &end->val;
446 if (Z_TYPE_P(zv) == IS_INDIRECT) {
447 zv = Z_INDIRECT_P(zv);
448 }
449 if (Z_REFCOUNTED_P(zv)) {
450 break;
451 }
452 if (p == end) return;
453 }
454 while (p != end) {
455 zv = &p->val;
456 if (Z_TYPE_P(zv) == IS_INDIRECT) {
457 zv = Z_INDIRECT_P(zv);
458 }
459 if (Z_REFCOUNTED_P(zv)) {
460 ref = Z_COUNTED_P(zv);
461 GC_REFCOUNT(ref)++;
462 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
463 gc_scan_black(ref);
464 }
465 }
466 p++;
467 }
468 zv = &p->val;
469 if (Z_TYPE_P(zv) == IS_INDIRECT) {
470 zv = Z_INDIRECT_P(zv);
471 }
472 ref = Z_COUNTED_P(zv);
473 GC_REFCOUNT(ref)++;
474 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
475 goto tail_call;
476 }
477 }
478
gc_mark_grey(zend_refcounted * ref)479 static void gc_mark_grey(zend_refcounted *ref)
480 {
481 HashTable *ht;
482 Bucket *p, *end;
483 zval *zv;
484
485 tail_call:
486 if (GC_REF_GET_COLOR(ref) != GC_GREY) {
487 ht = NULL;
488 GC_BENCH_INC(zval_marked_grey);
489 GC_REF_SET_COLOR(ref, GC_GREY);
490
491 if (GC_TYPE(ref) == IS_OBJECT) {
492 zend_object_get_gc_t get_gc;
493 zend_object *obj = (zend_object*)ref;
494
495 if (EXPECTED(!(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
496 (get_gc = obj->handlers->get_gc) != NULL)) {
497 int n;
498 zval *zv, *end;
499 zval tmp;
500
501 ZVAL_OBJ(&tmp, obj);
502 ht = get_gc(&tmp, &zv, &n);
503 end = zv + n;
504 if (EXPECTED(!ht) || UNEXPECTED(GC_REF_GET_COLOR(ht) == GC_GREY)) {
505 ht = NULL;
506 if (!n) return;
507 while (!Z_REFCOUNTED_P(--end)) {
508 if (zv == end) return;
509 }
510 } else {
511 GC_REF_SET_COLOR(ht, GC_GREY);
512 }
513 while (zv != end) {
514 if (Z_REFCOUNTED_P(zv)) {
515 ref = Z_COUNTED_P(zv);
516 ZEND_ASSERT(GC_REFCOUNT(ref) > 0);
517 GC_REFCOUNT(ref)--;
518 gc_mark_grey(ref);
519 }
520 zv++;
521 }
522 if (EXPECTED(!ht)) {
523 ref = Z_COUNTED_P(zv);
524 ZEND_ASSERT(GC_REFCOUNT(ref) > 0);
525 GC_REFCOUNT(ref)--;
526 goto tail_call;
527 }
528 } else {
529 return;
530 }
531 } else if (GC_TYPE(ref) == IS_ARRAY) {
532 if (((zend_array*)ref) == &EG(symbol_table)) {
533 GC_REF_SET_BLACK(ref);
534 return;
535 } else {
536 ht = (zend_array*)ref;
537 }
538 } else if (GC_TYPE(ref) == IS_REFERENCE) {
539 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
540 ref = Z_COUNTED(((zend_reference*)ref)->val);
541 ZEND_ASSERT(GC_REFCOUNT(ref) > 0);
542 GC_REFCOUNT(ref)--;
543 goto tail_call;
544 }
545 return;
546 } else {
547 return;
548 }
549
550 if (!ht->nNumUsed) return;
551 p = ht->arData;
552 end = p + ht->nNumUsed;
553 while (1) {
554 end--;
555 zv = &end->val;
556 if (Z_TYPE_P(zv) == IS_INDIRECT) {
557 zv = Z_INDIRECT_P(zv);
558 }
559 if (Z_REFCOUNTED_P(zv)) {
560 break;
561 }
562 if (p == end) return;
563 }
564 while (p != end) {
565 zv = &p->val;
566 if (Z_TYPE_P(zv) == IS_INDIRECT) {
567 zv = Z_INDIRECT_P(zv);
568 }
569 if (Z_REFCOUNTED_P(zv)) {
570 ref = Z_COUNTED_P(zv);
571 ZEND_ASSERT(GC_REFCOUNT(ref) > 0);
572 GC_REFCOUNT(ref)--;
573 gc_mark_grey(ref);
574 }
575 p++;
576 }
577 zv = &p->val;
578 if (Z_TYPE_P(zv) == IS_INDIRECT) {
579 zv = Z_INDIRECT_P(zv);
580 }
581 ref = Z_COUNTED_P(zv);
582 ZEND_ASSERT(GC_REFCOUNT(ref) > 0);
583 GC_REFCOUNT(ref)--;
584 goto tail_call;
585 }
586 }
587
gc_mark_roots(void)588 static void gc_mark_roots(void)
589 {
590 gc_root_buffer *current = GC_G(roots).next;
591
592 while (current != &GC_G(roots)) {
593 if (GC_REF_GET_COLOR(current->ref) == GC_PURPLE) {
594 gc_mark_grey(current->ref);
595 }
596 current = current->next;
597 }
598 }
599
gc_scan(zend_refcounted * ref)600 static void gc_scan(zend_refcounted *ref)
601 {
602 HashTable *ht;
603 Bucket *p, *end;
604 zval *zv;
605
606 tail_call:
607 if (GC_REF_GET_COLOR(ref) == GC_GREY) {
608 if (GC_REFCOUNT(ref) > 0) {
609 gc_scan_black(ref);
610 } else {
611 GC_REF_SET_COLOR(ref, GC_WHITE);
612 if (GC_TYPE(ref) == IS_OBJECT) {
613 zend_object_get_gc_t get_gc;
614 zend_object *obj = (zend_object*)ref;
615
616 if (EXPECTED(!(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
617 (get_gc = obj->handlers->get_gc) != NULL)) {
618 int n;
619 zval *zv, *end;
620 zval tmp;
621
622 ZVAL_OBJ(&tmp, obj);
623 ht = get_gc(&tmp, &zv, &n);
624 end = zv + n;
625 if (EXPECTED(!ht) || UNEXPECTED(GC_REF_GET_COLOR(ht) != GC_GREY)) {
626 ht = NULL;
627 if (!n) return;
628 while (!Z_REFCOUNTED_P(--end)) {
629 if (zv == end) return;
630 }
631 } else {
632 GC_REF_SET_COLOR(ht, GC_WHITE);
633 }
634 while (zv != end) {
635 if (Z_REFCOUNTED_P(zv)) {
636 ref = Z_COUNTED_P(zv);
637 gc_scan(ref);
638 }
639 zv++;
640 }
641 if (EXPECTED(!ht)) {
642 ref = Z_COUNTED_P(zv);
643 goto tail_call;
644 }
645 } else {
646 return;
647 }
648 } else if (GC_TYPE(ref) == IS_ARRAY) {
649 if ((zend_array*)ref == &EG(symbol_table)) {
650 GC_REF_SET_BLACK(ref);
651 return;
652 } else {
653 ht = (zend_array*)ref;
654 }
655 } else if (GC_TYPE(ref) == IS_REFERENCE) {
656 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
657 ref = Z_COUNTED(((zend_reference*)ref)->val);
658 goto tail_call;
659 }
660 return;
661 } else {
662 return;
663 }
664
665 if (!ht->nNumUsed) return;
666 p = ht->arData;
667 end = p + ht->nNumUsed;
668 while (1) {
669 end--;
670 zv = &end->val;
671 if (Z_TYPE_P(zv) == IS_INDIRECT) {
672 zv = Z_INDIRECT_P(zv);
673 }
674 if (Z_REFCOUNTED_P(zv)) {
675 break;
676 }
677 if (p == end) return;
678 }
679 while (p != end) {
680 zv = &p->val;
681 if (Z_TYPE_P(zv) == IS_INDIRECT) {
682 zv = Z_INDIRECT_P(zv);
683 }
684 if (Z_REFCOUNTED_P(zv)) {
685 ref = Z_COUNTED_P(zv);
686 gc_scan(ref);
687 }
688 p++;
689 }
690 zv = &p->val;
691 if (Z_TYPE_P(zv) == IS_INDIRECT) {
692 zv = Z_INDIRECT_P(zv);
693 }
694 ref = Z_COUNTED_P(zv);
695 goto tail_call;
696 }
697 }
698 }
699
gc_scan_roots(void)700 static void gc_scan_roots(void)
701 {
702 gc_root_buffer *current = GC_G(roots).next;
703
704 while (current != &GC_G(roots)) {
705 gc_scan(current->ref);
706 current = current->next;
707 }
708 }
709
gc_add_garbage(zend_refcounted * ref)710 static void gc_add_garbage(zend_refcounted *ref)
711 {
712 gc_root_buffer *buf = GC_G(unused);
713
714 if (buf) {
715 GC_G(unused) = buf->prev;
716 #if 1
717 /* optimization: color is already GC_BLACK (0) */
718 GC_INFO(ref) = buf - GC_G(buf);
719 #else
720 GC_REF_SET_ADDRESS(ref, buf - GC_G(buf));
721 #endif
722 } else if (GC_G(first_unused) != GC_G(last_unused)) {
723 buf = GC_G(first_unused);
724 GC_G(first_unused)++;
725 #if 1
726 /* optimization: color is already GC_BLACK (0) */
727 GC_INFO(ref) = buf - GC_G(buf);
728 #else
729 GC_REF_SET_ADDRESS(ref, buf - GC_G(buf));
730 #endif
731 } else {
732 /* If we don't have free slots in the buffer, allocate a new one and
733 * set it's address above GC_ROOT_BUFFER_MAX_ENTRIES that have special
734 * meaning.
735 */
736 if (!GC_G(additional_buffer) || GC_G(additional_buffer)->used == GC_NUM_ADDITIONAL_ENTRIES) {
737 gc_additional_buffer *new_buffer = emalloc(sizeof(gc_additional_buffer));
738 new_buffer->used = 0;
739 new_buffer->next = GC_G(additional_buffer);
740 GC_G(additional_buffer) = new_buffer;
741 }
742 buf = GC_G(additional_buffer)->buf + GC_G(additional_buffer)->used;
743 #if 1
744 /* optimization: color is already GC_BLACK (0) */
745 GC_INFO(ref) = GC_ROOT_BUFFER_MAX_ENTRIES + GC_G(additional_buffer)->used;
746 #else
747 GC_REF_SET_ADDRESS(ref, GC_ROOT_BUFFER_MAX_ENTRIES) + GC_G(additional_buffer)->used;
748 #endif
749 GC_G(additional_buffer)->used++;
750 }
751 if (buf) {
752 buf->ref = ref;
753 buf->next = GC_G(roots).next;
754 buf->prev = &GC_G(roots);
755 GC_G(roots).next->prev = buf;
756 GC_G(roots).next = buf;
757 }
758 }
759
gc_collect_white(zend_refcounted * ref,uint32_t * flags)760 static int gc_collect_white(zend_refcounted *ref, uint32_t *flags)
761 {
762 int count = 0;
763 HashTable *ht;
764 Bucket *p, *end;
765 zval *zv;
766
767 tail_call:
768 if (GC_REF_GET_COLOR(ref) == GC_WHITE) {
769 ht = NULL;
770 GC_REF_SET_BLACK(ref);
771
772 /* don't count references for compatibility ??? */
773 if (GC_TYPE(ref) != IS_REFERENCE) {
774 count++;
775 }
776
777 if (GC_TYPE(ref) == IS_OBJECT) {
778 zend_object_get_gc_t get_gc;
779 zend_object *obj = (zend_object*)ref;
780
781 if (EXPECTED(!(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
782 (get_gc = obj->handlers->get_gc) != NULL)) {
783 int n;
784 zval *zv, *end;
785 zval tmp;
786
787 #if 1
788 /* optimization: color is GC_BLACK (0) */
789 if (!GC_INFO(ref)) {
790 #else
791 if (!GC_ADDRESS(GC_INFO(ref))) {
792 #endif
793 gc_add_garbage(ref);
794 }
795 if (obj->handlers->dtor_obj &&
796 ((obj->handlers->dtor_obj != zend_objects_destroy_object) ||
797 (obj->ce->destructor != NULL))) {
798 *flags |= GC_HAS_DESTRUCTORS;
799 }
800 ZVAL_OBJ(&tmp, obj);
801 ht = get_gc(&tmp, &zv, &n);
802 end = zv + n;
803 if (EXPECTED(!ht) || UNEXPECTED(GC_REF_GET_COLOR(ht) == GC_BLACK)) {
804 ht = NULL;
805 if (!n) return count;
806 while (!Z_REFCOUNTED_P(--end)) {
807 /* count non-refcounted for compatibility ??? */
808 if (Z_TYPE_P(zv) != IS_UNDEF) {
809 count++;
810 }
811 if (zv == end) return count;
812 }
813 } else {
814 GC_REF_SET_BLACK(ht);
815 }
816 while (zv != end) {
817 if (Z_REFCOUNTED_P(zv)) {
818 ref = Z_COUNTED_P(zv);
819 GC_REFCOUNT(ref)++;
820 count += gc_collect_white(ref, flags);
821 /* count non-refcounted for compatibility ??? */
822 } else if (Z_TYPE_P(zv) != IS_UNDEF) {
823 count++;
824 }
825 zv++;
826 }
827 if (EXPECTED(!ht)) {
828 ref = Z_COUNTED_P(zv);
829 GC_REFCOUNT(ref)++;
830 goto tail_call;
831 }
832 } else {
833 return count;
834 }
835 } else if (GC_TYPE(ref) == IS_ARRAY) {
836 #if 1
837 /* optimization: color is GC_BLACK (0) */
838 if (!GC_INFO(ref)) {
839 #else
840 if (!GC_ADDRESS(GC_INFO(ref))) {
841 #endif
842 gc_add_garbage(ref);
843 }
844 ht = (zend_array*)ref;
845 } else if (GC_TYPE(ref) == IS_REFERENCE) {
846 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
847 ref = Z_COUNTED(((zend_reference*)ref)->val);
848 GC_REFCOUNT(ref)++;
849 goto tail_call;
850 }
851 return count;
852 } else {
853 return count;
854 }
855
856 if (!ht->nNumUsed) return count;
857 p = ht->arData;
858 end = p + ht->nNumUsed;
859 while (1) {
860 end--;
861 zv = &end->val;
862 if (Z_TYPE_P(zv) == IS_INDIRECT) {
863 zv = Z_INDIRECT_P(zv);
864 }
865 if (Z_REFCOUNTED_P(zv)) {
866 break;
867 }
868 /* count non-refcounted for compatibility ??? */
869 if (Z_TYPE_P(zv) != IS_UNDEF) {
870 count++;
871 }
872 if (p == end) return count;
873 }
874 while (p != end) {
875 zv = &p->val;
876 if (Z_TYPE_P(zv) == IS_INDIRECT) {
877 zv = Z_INDIRECT_P(zv);
878 }
879 if (Z_REFCOUNTED_P(zv)) {
880 ref = Z_COUNTED_P(zv);
881 GC_REFCOUNT(ref)++;
882 count += gc_collect_white(ref, flags);
883 /* count non-refcounted for compatibility ??? */
884 } else if (Z_TYPE_P(zv) != IS_UNDEF) {
885 count++;
886 }
887 p++;
888 }
889 zv = &p->val;
890 if (Z_TYPE_P(zv) == IS_INDIRECT) {
891 zv = Z_INDIRECT_P(zv);
892 }
893 ref = Z_COUNTED_P(zv);
894 GC_REFCOUNT(ref)++;
895 goto tail_call;
896 }
897 return count;
898 }
899
900 static int gc_collect_roots(uint32_t *flags)
901 {
902 int count = 0;
903 gc_root_buffer *current = GC_G(roots).next;
904
905 /* remove non-garbage from the list */
906 while (current != &GC_G(roots)) {
907 gc_root_buffer *next = current->next;
908 if (GC_REF_GET_COLOR(current->ref) == GC_BLACK) {
909 if (EXPECTED(GC_ADDRESS(GC_INFO(current->ref)) < GC_ROOT_BUFFER_MAX_ENTRIES)) {
910 gc_remove_from_roots(current);
911 } else {
912 gc_remove_from_additional_roots(current);
913 }
914 GC_INFO(current->ref) = 0; /* reset GC_ADDRESS() and keep GC_BLACK */
915 }
916 current = next;
917 }
918
919 current = GC_G(roots).next;
920 while (current != &GC_G(roots)) {
921 if (GC_REF_GET_COLOR(current->ref) == GC_WHITE) {
922 count += gc_collect_white(current->ref, flags);
923 }
924 current = current->next;
925 }
926
927 /* relink remaining roots into list to free */
928 if (GC_G(roots).next != &GC_G(roots)) {
929 if (GC_G(to_free).next == &GC_G(to_free)) {
930 /* move roots into list to free */
931 GC_G(to_free).next = GC_G(roots).next;
932 GC_G(to_free).prev = GC_G(roots).prev;
933 GC_G(to_free).next->prev = &GC_G(to_free);
934 GC_G(to_free).prev->next = &GC_G(to_free);
935 } else {
936 /* add roots into list to free */
937 GC_G(to_free).prev->next = GC_G(roots).next;
938 GC_G(roots).next->prev = GC_G(to_free).prev;
939 GC_G(roots).prev->next = &GC_G(to_free);
940 GC_G(to_free).prev = GC_G(roots).prev;
941 }
942
943 GC_G(roots).next = &GC_G(roots);
944 GC_G(roots).prev = &GC_G(roots);
945 }
946 return count;
947 }
948
949 static void gc_remove_nested_data_from_buffer(zend_refcounted *ref, gc_root_buffer *root)
950 {
951 HashTable *ht = NULL;
952 Bucket *p, *end;
953 zval *zv;
954
955 tail_call:
956 do {
957 if (root) {
958 GC_TRACE_REF(ref, "removing from buffer");
959 if (EXPECTED(GC_ADDRESS(GC_INFO(root->ref)) < GC_ROOT_BUFFER_MAX_ENTRIES)) {
960 gc_remove_from_roots(root);
961 } else {
962 gc_remove_from_additional_roots(root);
963 }
964 GC_INFO(ref) = 0;
965 root = NULL;
966 } else if (GC_ADDRESS(GC_INFO(ref)) != 0
967 && GC_REF_GET_COLOR(ref) == GC_BLACK) {
968 GC_TRACE_REF(ref, "removing from buffer");
969 GC_REMOVE_FROM_BUFFER(ref);
970 } else if (GC_TYPE(ref) == IS_REFERENCE) {
971 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
972 ref = Z_COUNTED(((zend_reference*)ref)->val);
973 goto tail_call;
974 }
975 return;
976 } else {
977 return;
978 }
979
980 if (GC_TYPE(ref) == IS_OBJECT) {
981 zend_object_get_gc_t get_gc;
982 zend_object *obj = (zend_object*)ref;
983
984 if (EXPECTED(!(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED) &&
985 (get_gc = obj->handlers->get_gc) != NULL)) {
986 int n;
987 zval *zv, *end;
988 zval tmp;
989
990 ZVAL_OBJ(&tmp, obj);
991 ht = get_gc(&tmp, &zv, &n);
992 end = zv + n;
993 if (EXPECTED(!ht)) {
994 if (!n) return;
995 while (!Z_REFCOUNTED_P(--end)) {
996 if (zv == end) return;
997 }
998 }
999 while (zv != end) {
1000 if (Z_REFCOUNTED_P(zv)) {
1001 ref = Z_COUNTED_P(zv);
1002 gc_remove_nested_data_from_buffer(ref, NULL);
1003 }
1004 zv++;
1005 }
1006 if (EXPECTED(!ht)) {
1007 ref = Z_COUNTED_P(zv);
1008 goto tail_call;
1009 }
1010 if (GC_ADDRESS(GC_INFO(ht)) != 0 && GC_REF_GET_COLOR(ht) == GC_BLACK) {
1011 GC_TRACE_REF(ht, "removing from buffer");
1012 GC_REMOVE_FROM_BUFFER(ht);
1013 }
1014 } else {
1015 return;
1016 }
1017 } else if (GC_TYPE(ref) == IS_ARRAY) {
1018 ht = (zend_array*)ref;
1019 } else {
1020 return;
1021 }
1022
1023 if (!ht->nNumUsed) return;
1024 p = ht->arData;
1025 end = p + ht->nNumUsed;
1026 while (1) {
1027 end--;
1028 zv = &end->val;
1029 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1030 zv = Z_INDIRECT_P(zv);
1031 }
1032 if (Z_REFCOUNTED_P(zv)) {
1033 break;
1034 }
1035 if (p == end) return;
1036 }
1037 while (p != end) {
1038 zv = &p->val;
1039 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1040 zv = Z_INDIRECT_P(zv);
1041 }
1042 if (Z_REFCOUNTED_P(zv)) {
1043 ref = Z_COUNTED_P(zv);
1044 gc_remove_nested_data_from_buffer(ref, NULL);
1045 }
1046 p++;
1047 }
1048 zv = &p->val;
1049 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1050 zv = Z_INDIRECT_P(zv);
1051 }
1052 ref = Z_COUNTED_P(zv);
1053 goto tail_call;
1054 } while (0);
1055 }
1056
1057 ZEND_API int zend_gc_collect_cycles(void)
1058 {
1059 int count = 0;
1060
1061 if (GC_G(roots).next != &GC_G(roots)) {
1062 gc_root_buffer *current, *next, *orig_next_to_free;
1063 zend_refcounted *p;
1064 gc_root_buffer to_free;
1065 uint32_t gc_flags = 0;
1066 gc_additional_buffer *additional_buffer_snapshot;
1067 #if ZEND_GC_DEBUG
1068 zend_bool orig_gc_full;
1069 #endif
1070
1071 if (GC_G(gc_active)) {
1072 return 0;
1073 }
1074
1075 GC_TRACE("Collecting cycles");
1076 GC_G(gc_runs)++;
1077 GC_G(gc_active) = 1;
1078
1079 GC_TRACE("Marking roots");
1080 gc_mark_roots();
1081 GC_TRACE("Scanning roots");
1082 gc_scan_roots();
1083
1084 #if ZEND_GC_DEBUG
1085 orig_gc_full = GC_G(gc_full);
1086 GC_G(gc_full) = 0;
1087 #endif
1088
1089 GC_TRACE("Collecting roots");
1090 additional_buffer_snapshot = GC_G(additional_buffer);
1091 count = gc_collect_roots(&gc_flags);
1092 #if ZEND_GC_DEBUG
1093 GC_G(gc_full) = orig_gc_full;
1094 #endif
1095 GC_G(gc_active) = 0;
1096
1097 if (GC_G(to_free).next == &GC_G(to_free)) {
1098 /* nothing to free */
1099 GC_TRACE("Nothing to free");
1100 return 0;
1101 }
1102
1103 /* Copy global to_free list into local list */
1104 to_free.next = GC_G(to_free).next;
1105 to_free.prev = GC_G(to_free).prev;
1106 to_free.next->prev = &to_free;
1107 to_free.prev->next = &to_free;
1108
1109 /* Free global list */
1110 GC_G(to_free).next = &GC_G(to_free);
1111 GC_G(to_free).prev = &GC_G(to_free);
1112
1113 orig_next_to_free = GC_G(next_to_free);
1114
1115 #if ZEND_GC_DEBUG
1116 orig_gc_full = GC_G(gc_full);
1117 GC_G(gc_full) = 0;
1118 #endif
1119
1120 if (gc_flags & GC_HAS_DESTRUCTORS) {
1121 GC_TRACE("Calling destructors");
1122
1123 /* Remember reference counters before calling destructors */
1124 current = to_free.next;
1125 while (current != &to_free) {
1126 current->refcount = GC_REFCOUNT(current->ref);
1127 current = current->next;
1128 }
1129
1130 /* Call destructors */
1131 current = to_free.next;
1132 while (current != &to_free) {
1133 p = current->ref;
1134 GC_G(next_to_free) = current->next;
1135 if (GC_TYPE(p) == IS_OBJECT) {
1136 zend_object *obj = (zend_object*)p;
1137
1138 if (!(GC_FLAGS(obj) & IS_OBJ_DESTRUCTOR_CALLED)) {
1139 GC_TRACE_REF(obj, "calling destructor");
1140 GC_FLAGS(obj) |= IS_OBJ_DESTRUCTOR_CALLED;
1141 if (obj->handlers->dtor_obj
1142 && (obj->handlers->dtor_obj != zend_objects_destroy_object
1143 || obj->ce->destructor)) {
1144 GC_REFCOUNT(obj)++;
1145 obj->handlers->dtor_obj(obj);
1146 GC_REFCOUNT(obj)--;
1147 }
1148 }
1149 }
1150 current = GC_G(next_to_free);
1151 }
1152
1153 /* Remove values captured in destructors */
1154 current = to_free.next;
1155 while (current != &to_free) {
1156 GC_G(next_to_free) = current->next;
1157 if (GC_REFCOUNT(current->ref) > current->refcount) {
1158 gc_remove_nested_data_from_buffer(current->ref, current);
1159 }
1160 current = GC_G(next_to_free);
1161 }
1162 }
1163
1164 /* Destroy zvals */
1165 GC_TRACE("Destroying zvals");
1166 GC_G(gc_active) = 1;
1167 current = to_free.next;
1168 while (current != &to_free) {
1169 p = current->ref;
1170 GC_G(next_to_free) = current->next;
1171 GC_TRACE_REF(p, "destroying");
1172 if (GC_TYPE(p) == IS_OBJECT) {
1173 zend_object *obj = (zend_object*)p;
1174
1175 EG(objects_store).object_buckets[obj->handle] = SET_OBJ_INVALID(obj);
1176 GC_TYPE(obj) = IS_NULL;
1177 if (!(GC_FLAGS(obj) & IS_OBJ_FREE_CALLED)) {
1178 GC_FLAGS(obj) |= IS_OBJ_FREE_CALLED;
1179 if (obj->handlers->free_obj) {
1180 GC_REFCOUNT(obj)++;
1181 obj->handlers->free_obj(obj);
1182 GC_REFCOUNT(obj)--;
1183 }
1184 }
1185 SET_OBJ_BUCKET_NUMBER(EG(objects_store).object_buckets[obj->handle], EG(objects_store).free_list_head);
1186 EG(objects_store).free_list_head = obj->handle;
1187 p = current->ref = (zend_refcounted*)(((char*)obj) - obj->handlers->offset);
1188 } else if (GC_TYPE(p) == IS_ARRAY) {
1189 zend_array *arr = (zend_array*)p;
1190
1191 GC_TYPE(arr) = IS_NULL;
1192
1193 /* GC may destroy arrays with rc>1. This is valid and safe. */
1194 HT_ALLOW_COW_VIOLATION(arr);
1195
1196 zend_hash_destroy(arr);
1197 }
1198 current = GC_G(next_to_free);
1199 }
1200
1201 /* Free objects */
1202 current = to_free.next;
1203 while (current != &to_free) {
1204 next = current->next;
1205 p = current->ref;
1206 if (EXPECTED(current >= GC_G(buf) && current < GC_G(buf) + GC_ROOT_BUFFER_MAX_ENTRIES)) {
1207 current->prev = GC_G(unused);
1208 GC_G(unused) = current;
1209 }
1210 efree(p);
1211 current = next;
1212 }
1213
1214 while (GC_G(additional_buffer) != additional_buffer_snapshot) {
1215 gc_additional_buffer *next = GC_G(additional_buffer)->next;
1216 efree(GC_G(additional_buffer));
1217 GC_G(additional_buffer) = next;
1218 }
1219
1220 GC_TRACE("Collection finished");
1221 GC_G(collected) += count;
1222 GC_G(next_to_free) = orig_next_to_free;
1223 #if ZEND_GC_DEBUG
1224 GC_G(gc_full) = orig_gc_full;
1225 #endif
1226 GC_G(gc_active) = 0;
1227 }
1228
1229 return count;
1230 }
1231
1232 /*
1233 * Local variables:
1234 * tab-width: 4
1235 * c-basic-offset: 4
1236 * indent-tabs-mode: t
1237 * End:
1238 * vim600: sw=4 ts=4 fdm=marker
1239 * vim<600: sw=4 ts=4
1240 *
1241 * vim:noexpandtab:
1242 */
1243
