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 && !(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED)) {
379 zend_object_get_gc_t get_gc;
380 zend_object *obj = (zend_object*)ref;
381
382 if (EXPECTED(IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
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)) {
392 if (!n) return;
393 while (!Z_REFCOUNTED_P(--end)) {
394 if (zv == end) return;
395 }
396 }
397 while (zv != end) {
398 if (Z_REFCOUNTED_P(zv)) {
399 ref = Z_COUNTED_P(zv);
400 GC_REFCOUNT(ref)++;
401 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
402 gc_scan_black(ref);
403 }
404 }
405 zv++;
406 }
407 if (EXPECTED(!ht)) {
408 ref = Z_COUNTED_P(zv);
409 GC_REFCOUNT(ref)++;
410 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
411 goto tail_call;
412 }
413 return;
414 }
415 } else {
416 return;
417 }
418 } else if (GC_TYPE(ref) == IS_ARRAY) {
419 if ((zend_array*)ref != &EG(symbol_table)) {
420 ht = (zend_array*)ref;
421 } else {
422 return;
423 }
424 } else if (GC_TYPE(ref) == IS_REFERENCE) {
425 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
426 ref = Z_COUNTED(((zend_reference*)ref)->val);
427 GC_REFCOUNT(ref)++;
428 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
429 goto tail_call;
430 }
431 }
432 return;
433 } else {
434 return;
435 }
436
437 if (!ht->nNumUsed) return;
438 p = ht->arData;
439 end = p + ht->nNumUsed;
440 while (1) {
441 end--;
442 zv = &end->val;
443 if (Z_TYPE_P(zv) == IS_INDIRECT) {
444 zv = Z_INDIRECT_P(zv);
445 }
446 if (Z_REFCOUNTED_P(zv)) {
447 break;
448 }
449 if (p == end) return;
450 }
451 while (p != end) {
452 zv = &p->val;
453 if (Z_TYPE_P(zv) == IS_INDIRECT) {
454 zv = Z_INDIRECT_P(zv);
455 }
456 if (Z_REFCOUNTED_P(zv)) {
457 ref = Z_COUNTED_P(zv);
458 GC_REFCOUNT(ref)++;
459 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
460 gc_scan_black(ref);
461 }
462 }
463 p++;
464 }
465 zv = &p->val;
466 if (Z_TYPE_P(zv) == IS_INDIRECT) {
467 zv = Z_INDIRECT_P(zv);
468 }
469 ref = Z_COUNTED_P(zv);
470 GC_REFCOUNT(ref)++;
471 if (GC_REF_GET_COLOR(ref) != GC_BLACK) {
472 goto tail_call;
473 }
474 }
475
gc_mark_grey(zend_refcounted * ref)476 static void gc_mark_grey(zend_refcounted *ref)
477 {
478 HashTable *ht;
479 Bucket *p, *end;
480 zval *zv;
481
482 tail_call:
483 if (GC_REF_GET_COLOR(ref) != GC_GREY) {
484 ht = NULL;
485 GC_BENCH_INC(zval_marked_grey);
486 GC_REF_SET_COLOR(ref, GC_GREY);
487
488 if (GC_TYPE(ref) == IS_OBJECT && !(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED)) {
489 zend_object_get_gc_t get_gc;
490 zend_object *obj = (zend_object*)ref;
491
492 if (EXPECTED(IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
493 (get_gc = obj->handlers->get_gc) != NULL)) {
494 int n;
495 zval *zv, *end;
496 zval tmp;
497
498 ZVAL_OBJ(&tmp, obj);
499 ht = get_gc(&tmp, &zv, &n);
500 end = zv + n;
501 if (EXPECTED(!ht)) {
502 if (!n) return;
503 while (!Z_REFCOUNTED_P(--end)) {
504 if (zv == end) return;
505 }
506 }
507 while (zv != end) {
508 if (Z_REFCOUNTED_P(zv)) {
509 ref = Z_COUNTED_P(zv);
510 GC_REFCOUNT(ref)--;
511 gc_mark_grey(ref);
512 }
513 zv++;
514 }
515 if (EXPECTED(!ht)) {
516 ref = Z_COUNTED_P(zv);
517 GC_REFCOUNT(ref)--;
518 goto tail_call;
519 }
520 } else {
521 return;
522 }
523 } else if (GC_TYPE(ref) == IS_ARRAY) {
524 if (((zend_array*)ref) == &EG(symbol_table)) {
525 GC_REF_SET_BLACK(ref);
526 return;
527 } else {
528 ht = (zend_array*)ref;
529 }
530 } else if (GC_TYPE(ref) == IS_REFERENCE) {
531 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
532 if (UNEXPECTED(!EG(objects_store).object_buckets) &&
533 Z_TYPE(((zend_reference*)ref)->val) == IS_OBJECT) {
534 Z_TYPE_INFO(((zend_reference*)ref)->val) = IS_NULL;
535 return;
536 }
537 ref = Z_COUNTED(((zend_reference*)ref)->val);
538 GC_REFCOUNT(ref)--;
539 goto tail_call;
540 }
541 return;
542 } else {
543 return;
544 }
545
546 if (!ht->nNumUsed) return;
547 p = ht->arData;
548 end = p + ht->nNumUsed;
549 while (1) {
550 end--;
551 zv = &end->val;
552 if (Z_TYPE_P(zv) == IS_INDIRECT) {
553 zv = Z_INDIRECT_P(zv);
554 }
555 if (Z_REFCOUNTED_P(zv)) {
556 break;
557 }
558 if (p == end) return;
559 }
560 while (p != end) {
561 zv = &p->val;
562 if (Z_TYPE_P(zv) == IS_INDIRECT) {
563 zv = Z_INDIRECT_P(zv);
564 }
565 if (Z_REFCOUNTED_P(zv)) {
566 if (Z_TYPE_P(zv) == IS_OBJECT &&
567 UNEXPECTED(!EG(objects_store).object_buckets)) {
568 Z_TYPE_INFO_P(zv) = IS_NULL;
569 } else {
570 ref = Z_COUNTED_P(zv);
571 GC_REFCOUNT(ref)--;
572 gc_mark_grey(ref);
573 }
574 }
575 p++;
576 }
577 zv = &p->val;
578 if (Z_TYPE_P(zv) == IS_INDIRECT) {
579 zv = Z_INDIRECT_P(zv);
580 }
581 if (Z_TYPE_P(zv) == IS_OBJECT &&
582 UNEXPECTED(!EG(objects_store).object_buckets)) {
583 Z_TYPE_INFO_P(zv) = IS_NULL;
584 } else {
585 ref = Z_COUNTED_P(zv);
586 GC_REFCOUNT(ref)--;
587 goto tail_call;
588 }
589 }
590 }
591
gc_mark_roots(void)592 static void gc_mark_roots(void)
593 {
594 gc_root_buffer *current = GC_G(roots).next;
595
596 while (current != &GC_G(roots)) {
597 if (GC_REF_GET_COLOR(current->ref) == GC_PURPLE) {
598 gc_mark_grey(current->ref);
599 }
600 current = current->next;
601 }
602 }
603
gc_scan(zend_refcounted * ref)604 static void gc_scan(zend_refcounted *ref)
605 {
606 HashTable *ht;
607 Bucket *p, *end;
608 zval *zv;
609
610 tail_call:
611 if (GC_REF_GET_COLOR(ref) == GC_GREY) {
612 if (GC_REFCOUNT(ref) > 0) {
613 gc_scan_black(ref);
614 } else {
615 GC_REF_SET_COLOR(ref, GC_WHITE);
616 if (GC_TYPE(ref) == IS_OBJECT && !(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED)) {
617 zend_object_get_gc_t get_gc;
618 zend_object *obj = (zend_object*)ref;
619
620 if (EXPECTED(IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
621 (get_gc = obj->handlers->get_gc) != NULL)) {
622 int n;
623 zval *zv, *end;
624 zval tmp;
625
626 ZVAL_OBJ(&tmp, obj);
627 ht = get_gc(&tmp, &zv, &n);
628 end = zv + n;
629 if (EXPECTED(!ht)) {
630 if (!n) return;
631 while (!Z_REFCOUNTED_P(--end)) {
632 if (zv == end) return;
633 }
634 }
635 while (zv != end) {
636 if (Z_REFCOUNTED_P(zv)) {
637 ref = Z_COUNTED_P(zv);
638 gc_scan(ref);
639 }
640 zv++;
641 }
642 if (EXPECTED(!ht)) {
643 ref = Z_COUNTED_P(zv);
644 goto tail_call;
645 }
646 } else {
647 return;
648 }
649 } else if (GC_TYPE(ref) == IS_ARRAY) {
650 if ((zend_array*)ref == &EG(symbol_table)) {
651 GC_REF_SET_BLACK(ref);
652 return;
653 } else {
654 ht = (zend_array*)ref;
655 }
656 } else if (GC_TYPE(ref) == IS_REFERENCE) {
657 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
658 ref = Z_COUNTED(((zend_reference*)ref)->val);
659 goto tail_call;
660 }
661 return;
662 } else {
663 return;
664 }
665
666 if (!ht->nNumUsed) return;
667 p = ht->arData;
668 end = p + ht->nNumUsed;
669 while (1) {
670 end--;
671 zv = &end->val;
672 if (Z_TYPE_P(zv) == IS_INDIRECT) {
673 zv = Z_INDIRECT_P(zv);
674 }
675 if (Z_REFCOUNTED_P(zv)) {
676 break;
677 }
678 if (p == end) return;
679 }
680 while (p != end) {
681 zv = &p->val;
682 if (Z_TYPE_P(zv) == IS_INDIRECT) {
683 zv = Z_INDIRECT_P(zv);
684 }
685 if (Z_REFCOUNTED_P(zv)) {
686 ref = Z_COUNTED_P(zv);
687 gc_scan(ref);
688 }
689 p++;
690 }
691 zv = &p->val;
692 if (Z_TYPE_P(zv) == IS_INDIRECT) {
693 zv = Z_INDIRECT_P(zv);
694 }
695 ref = Z_COUNTED_P(zv);
696 goto tail_call;
697 }
698 }
699 }
700
gc_scan_roots(void)701 static void gc_scan_roots(void)
702 {
703 gc_root_buffer *current = GC_G(roots).next;
704
705 while (current != &GC_G(roots)) {
706 gc_scan(current->ref);
707 current = current->next;
708 }
709 }
710
gc_add_garbage(zend_refcounted * ref)711 static void gc_add_garbage(zend_refcounted *ref)
712 {
713 gc_root_buffer *buf = GC_G(unused);
714
715 if (buf) {
716 GC_G(unused) = buf->prev;
717 #if 1
718 /* optimization: color is already GC_BLACK (0) */
719 GC_INFO(ref) = buf - GC_G(buf);
720 #else
721 GC_REF_SET_ADDRESS(ref, buf - GC_G(buf));
722 #endif
723 } else if (GC_G(first_unused) != GC_G(last_unused)) {
724 buf = GC_G(first_unused);
725 GC_G(first_unused)++;
726 #if 1
727 /* optimization: color is already GC_BLACK (0) */
728 GC_INFO(ref) = buf - GC_G(buf);
729 #else
730 GC_REF_SET_ADDRESS(ref, buf - GC_G(buf));
731 #endif
732 } else {
733 /* If we don't have free slots in the buffer, allocate a new one and
734 * set it's address above GC_ROOT_BUFFER_MAX_ENTRIES that have special
735 * meaning.
736 */
737 if (!GC_G(additional_buffer) || GC_G(additional_buffer)->used == GC_NUM_ADDITIONAL_ENTRIES) {
738 gc_additional_buffer *new_buffer = emalloc(sizeof(gc_additional_buffer));
739 new_buffer->used = 0;
740 new_buffer->next = GC_G(additional_buffer);
741 GC_G(additional_buffer) = new_buffer;
742 }
743 buf = GC_G(additional_buffer)->buf + GC_G(additional_buffer)->used;
744 #if 1
745 /* optimization: color is already GC_BLACK (0) */
746 GC_INFO(ref) = GC_ROOT_BUFFER_MAX_ENTRIES + GC_G(additional_buffer)->used;
747 #else
748 GC_REF_SET_ADDRESS(ref, GC_ROOT_BUFFER_MAX_ENTRIES) + GC_G(additional_buffer)->used;
749 #endif
750 GC_G(additional_buffer)->used++;
751 }
752 if (buf) {
753 buf->ref = ref;
754 buf->next = GC_G(roots).next;
755 buf->prev = &GC_G(roots);
756 GC_G(roots).next->prev = buf;
757 GC_G(roots).next = buf;
758 }
759 }
760
gc_collect_white(zend_refcounted * ref,uint32_t * flags)761 static int gc_collect_white(zend_refcounted *ref, uint32_t *flags)
762 {
763 int count = 0;
764 HashTable *ht;
765 Bucket *p, *end;
766 zval *zv;
767
768 tail_call:
769 if (GC_REF_GET_COLOR(ref) == GC_WHITE) {
770 ht = NULL;
771 GC_REF_SET_BLACK(ref);
772
773 /* don't count references for compatibility ??? */
774 if (GC_TYPE(ref) != IS_REFERENCE) {
775 count++;
776 }
777
778 if (GC_TYPE(ref) == IS_OBJECT && !(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED)) {
779 zend_object_get_gc_t get_gc;
780 zend_object *obj = (zend_object*)ref;
781
782 if (EXPECTED(IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
783 (get_gc = obj->handlers->get_gc) != NULL)) {
784 int n;
785 zval *zv, *end;
786 zval tmp;
787
788 #if 1
789 /* optimization: color is GC_BLACK (0) */
790 if (!GC_INFO(ref)) {
791 #else
792 if (!GC_ADDRESS(GC_INFO(ref))) {
793 #endif
794 gc_add_garbage(ref);
795 }
796 if (obj->handlers->dtor_obj &&
797 ((obj->handlers->dtor_obj != zend_objects_destroy_object) ||
798 (obj->ce->destructor != NULL))) {
799 *flags |= GC_HAS_DESTRUCTORS;
800 }
801 ZVAL_OBJ(&tmp, obj);
802 ht = get_gc(&tmp, &zv, &n);
803 end = zv + n;
804 if (EXPECTED(!ht)) {
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 }
814 while (zv != end) {
815 if (Z_REFCOUNTED_P(zv)) {
816 ref = Z_COUNTED_P(zv);
817 GC_REFCOUNT(ref)++;
818 count += gc_collect_white(ref, flags);
819 /* count non-refcounted for compatibility ??? */
820 } else if (Z_TYPE_P(zv) != IS_UNDEF) {
821 count++;
822 }
823 zv++;
824 }
825 if (EXPECTED(!ht)) {
826 ref = Z_COUNTED_P(zv);
827 GC_REFCOUNT(ref)++;
828 goto tail_call;
829 }
830 } else {
831 return count;
832 }
833 } else if (GC_TYPE(ref) == IS_ARRAY) {
834 #if 1
835 /* optimization: color is GC_BLACK (0) */
836 if (!GC_INFO(ref)) {
837 #else
838 if (!GC_ADDRESS(GC_INFO(ref))) {
839 #endif
840 gc_add_garbage(ref);
841 }
842 ht = (zend_array*)ref;
843 } else if (GC_TYPE(ref) == IS_REFERENCE) {
844 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
845 ref = Z_COUNTED(((zend_reference*)ref)->val);
846 GC_REFCOUNT(ref)++;
847 goto tail_call;
848 }
849 return count;
850 } else {
851 return count;
852 }
853
854 if (!ht->nNumUsed) return count;
855 p = ht->arData;
856 end = p + ht->nNumUsed;
857 while (1) {
858 end--;
859 zv = &end->val;
860 if (Z_TYPE_P(zv) == IS_INDIRECT) {
861 zv = Z_INDIRECT_P(zv);
862 }
863 if (Z_REFCOUNTED_P(zv)) {
864 break;
865 }
866 /* count non-refcounted for compatibility ??? */
867 if (Z_TYPE_P(zv) != IS_UNDEF) {
868 count++;
869 }
870 if (p == end) return count;
871 }
872 while (p != end) {
873 zv = &p->val;
874 if (Z_TYPE_P(zv) == IS_INDIRECT) {
875 zv = Z_INDIRECT_P(zv);
876 }
877 if (Z_REFCOUNTED_P(zv)) {
878 ref = Z_COUNTED_P(zv);
879 GC_REFCOUNT(ref)++;
880 count += gc_collect_white(ref, flags);
881 /* count non-refcounted for compatibility ??? */
882 } else if (Z_TYPE_P(zv) != IS_UNDEF) {
883 count++;
884 }
885 p++;
886 }
887 zv = &p->val;
888 if (Z_TYPE_P(zv) == IS_INDIRECT) {
889 zv = Z_INDIRECT_P(zv);
890 }
891 ref = Z_COUNTED_P(zv);
892 GC_REFCOUNT(ref)++;
893 goto tail_call;
894 }
895 return count;
896 }
897
898 static int gc_collect_roots(uint32_t *flags)
899 {
900 int count = 0;
901 gc_root_buffer *current = GC_G(roots).next;
902
903 /* remove non-garbage from the list */
904 while (current != &GC_G(roots)) {
905 gc_root_buffer *next = current->next;
906 if (GC_REF_GET_COLOR(current->ref) == GC_BLACK) {
907 if (EXPECTED(GC_ADDRESS(GC_INFO(current->ref)) < GC_ROOT_BUFFER_MAX_ENTRIES)) {
908 gc_remove_from_roots(current);
909 } else {
910 gc_remove_from_additional_roots(current);
911 }
912 GC_INFO(current->ref) = 0; /* reset GC_ADDRESS() and keep GC_BLACK */
913 }
914 current = next;
915 }
916
917 current = GC_G(roots).next;
918 while (current != &GC_G(roots)) {
919 if (GC_REF_GET_COLOR(current->ref) == GC_WHITE) {
920 count += gc_collect_white(current->ref, flags);
921 }
922 current = current->next;
923 }
924
925 /* relink remaining roots into list to free */
926 if (GC_G(roots).next != &GC_G(roots)) {
927 if (GC_G(to_free).next == &GC_G(to_free)) {
928 /* move roots into list to free */
929 GC_G(to_free).next = GC_G(roots).next;
930 GC_G(to_free).prev = GC_G(roots).prev;
931 GC_G(to_free).next->prev = &GC_G(to_free);
932 GC_G(to_free).prev->next = &GC_G(to_free);
933 } else {
934 /* add roots into list to free */
935 GC_G(to_free).prev->next = GC_G(roots).next;
936 GC_G(roots).next->prev = GC_G(to_free).prev;
937 GC_G(roots).prev->next = &GC_G(to_free);
938 GC_G(to_free).prev = GC_G(roots).prev;
939 }
940
941 GC_G(roots).next = &GC_G(roots);
942 GC_G(roots).prev = &GC_G(roots);
943 }
944 return count;
945 }
946
947 static void gc_remove_nested_data_from_buffer(zend_refcounted *ref, gc_root_buffer *root)
948 {
949 HashTable *ht = NULL;
950 Bucket *p, *end;
951 zval *zv;
952
953 tail_call:
954 if (root ||
955 (GC_ADDRESS(GC_INFO(ref)) != 0 &&
956 GC_REF_GET_COLOR(ref) == GC_BLACK)) {
957 GC_TRACE_REF(ref, "removing from buffer");
958 if (root) {
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 {
967 GC_REMOVE_FROM_BUFFER(ref);
968 }
969
970 if (GC_TYPE(ref) == IS_OBJECT && !(GC_FLAGS(ref) & IS_OBJ_FREE_CALLED)) {
971 zend_object_get_gc_t get_gc;
972 zend_object *obj = (zend_object*)ref;
973
974 if (EXPECTED(IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
975 (get_gc = obj->handlers->get_gc) != NULL)) {
976 int n;
977 zval *zv, *end;
978 zval tmp;
979
980 ZVAL_OBJ(&tmp, obj);
981 ht = get_gc(&tmp, &zv, &n);
982 end = zv + n;
983 if (EXPECTED(!ht)) {
984 if (!n) return;
985 while (!Z_REFCOUNTED_P(--end)) {
986 if (zv == end) return;
987 }
988 }
989 while (zv != end) {
990 if (Z_REFCOUNTED_P(zv)) {
991 ref = Z_COUNTED_P(zv);
992 gc_remove_nested_data_from_buffer(ref, NULL);
993 }
994 zv++;
995 }
996 if (EXPECTED(!ht)) {
997 ref = Z_COUNTED_P(zv);
998 goto tail_call;
999 }
1000 } else {
1001 return;
1002 }
1003 } else if (GC_TYPE(ref) == IS_ARRAY) {
1004 ht = (zend_array*)ref;
1005 } else if (GC_TYPE(ref) == IS_REFERENCE) {
1006 if (Z_REFCOUNTED(((zend_reference*)ref)->val)) {
1007 ref = Z_COUNTED(((zend_reference*)ref)->val);
1008 goto tail_call;
1009 }
1010 return;
1011 } else {
1012 return;
1013 }
1014
1015 if (!ht->nNumUsed) return;
1016 p = ht->arData;
1017 end = p + ht->nNumUsed;
1018 while (1) {
1019 end--;
1020 zv = &end->val;
1021 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1022 zv = Z_INDIRECT_P(zv);
1023 }
1024 if (Z_REFCOUNTED_P(zv)) {
1025 break;
1026 }
1027 if (p == end) return;
1028 }
1029 while (p != end) {
1030 zv = &p->val;
1031 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1032 zv = Z_INDIRECT_P(zv);
1033 }
1034 if (Z_REFCOUNTED_P(zv)) {
1035 ref = Z_COUNTED_P(zv);
1036 gc_remove_nested_data_from_buffer(ref, NULL);
1037 }
1038 p++;
1039 }
1040 zv = &p->val;
1041 if (Z_TYPE_P(zv) == IS_INDIRECT) {
1042 zv = Z_INDIRECT_P(zv);
1043 }
1044 ref = Z_COUNTED_P(zv);
1045 goto tail_call;
1046 }
1047 }
1048
1049 ZEND_API int zend_gc_collect_cycles(void)
1050 {
1051 int count = 0;
1052
1053 if (GC_G(roots).next != &GC_G(roots)) {
1054 gc_root_buffer *current, *next, *orig_next_to_free;
1055 zend_refcounted *p;
1056 gc_root_buffer to_free;
1057 uint32_t gc_flags = 0;
1058 gc_additional_buffer *additional_buffer_snapshot;
1059 #if ZEND_GC_DEBUG
1060 zend_bool orig_gc_full;
1061 #endif
1062
1063 if (GC_G(gc_active)) {
1064 return 0;
1065 }
1066
1067 GC_TRACE("Collecting cycles");
1068 GC_G(gc_runs)++;
1069 GC_G(gc_active) = 1;
1070
1071 GC_TRACE("Marking roots");
1072 gc_mark_roots();
1073 GC_TRACE("Scanning roots");
1074 gc_scan_roots();
1075
1076 #if ZEND_GC_DEBUG
1077 orig_gc_full = GC_G(gc_full);
1078 GC_G(gc_full) = 0;
1079 #endif
1080
1081 GC_TRACE("Collecting roots");
1082 additional_buffer_snapshot = GC_G(additional_buffer);
1083 count = gc_collect_roots(&gc_flags);
1084 #if ZEND_GC_DEBUG
1085 GC_G(gc_full) = orig_gc_full;
1086 #endif
1087 GC_G(gc_active) = 0;
1088
1089 if (GC_G(to_free).next == &GC_G(to_free)) {
1090 /* nothing to free */
1091 GC_TRACE("Nothing to free");
1092 return 0;
1093 }
1094
1095 /* Copy global to_free list into local list */
1096 to_free.next = GC_G(to_free).next;
1097 to_free.prev = GC_G(to_free).prev;
1098 to_free.next->prev = &to_free;
1099 to_free.prev->next = &to_free;
1100
1101 /* Free global list */
1102 GC_G(to_free).next = &GC_G(to_free);
1103 GC_G(to_free).prev = &GC_G(to_free);
1104
1105 orig_next_to_free = GC_G(next_to_free);
1106
1107 #if ZEND_GC_DEBUG
1108 orig_gc_full = GC_G(gc_full);
1109 GC_G(gc_full) = 0;
1110 #endif
1111
1112 if (gc_flags & GC_HAS_DESTRUCTORS) {
1113 GC_TRACE("Calling destructors");
1114 if (EG(objects_store).object_buckets) {
1115 /* Remember reference counters before calling destructors */
1116 current = to_free.next;
1117 while (current != &to_free) {
1118 current->refcount = GC_REFCOUNT(current->ref);
1119 current = current->next;
1120 }
1121
1122 /* Call destructors */
1123 current = to_free.next;
1124 while (current != &to_free) {
1125 p = current->ref;
1126 GC_G(next_to_free) = current->next;
1127 if (GC_TYPE(p) == IS_OBJECT) {
1128 zend_object *obj = (zend_object*)p;
1129
1130 if (IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle]) &&
1131 !(GC_FLAGS(obj) & IS_OBJ_DESTRUCTOR_CALLED)) {
1132 GC_TRACE_REF(obj, "calling destructor");
1133 GC_FLAGS(obj) |= IS_OBJ_DESTRUCTOR_CALLED;
1134 if (obj->handlers->dtor_obj) {
1135 GC_REFCOUNT(obj)++;
1136 obj->handlers->dtor_obj(obj);
1137 GC_REFCOUNT(obj)--;
1138 }
1139 }
1140 }
1141 current = GC_G(next_to_free);
1142 }
1143
1144 /* Remove values captured in destructors */
1145 current = to_free.next;
1146 while (current != &to_free) {
1147 GC_G(next_to_free) = current->next;
1148 if (GC_REFCOUNT(current->ref) > current->refcount) {
1149 gc_remove_nested_data_from_buffer(current->ref, current);
1150 }
1151 current = GC_G(next_to_free);
1152 }
1153 }
1154 }
1155
1156 /* Destroy zvals */
1157 GC_TRACE("Destroying zvals");
1158 GC_G(gc_active) = 1;
1159 current = to_free.next;
1160 while (current != &to_free) {
1161 p = current->ref;
1162 GC_G(next_to_free) = current->next;
1163 GC_TRACE_REF(p, "destroying");
1164 if (GC_TYPE(p) == IS_OBJECT) {
1165 zend_object *obj = (zend_object*)p;
1166
1167 if (EG(objects_store).object_buckets &&
1168 IS_OBJ_VALID(EG(objects_store).object_buckets[obj->handle])) {
1169 EG(objects_store).object_buckets[obj->handle] = SET_OBJ_INVALID(obj);
1170 GC_TYPE(obj) = IS_NULL;
1171 if (!(GC_FLAGS(obj) & IS_OBJ_FREE_CALLED)) {
1172 GC_FLAGS(obj) |= IS_OBJ_FREE_CALLED;
1173 if (obj->handlers->free_obj) {
1174 GC_REFCOUNT(obj)++;
1175 obj->handlers->free_obj(obj);
1176 GC_REFCOUNT(obj)--;
1177 }
1178 }
1179 SET_OBJ_BUCKET_NUMBER(EG(objects_store).object_buckets[obj->handle], EG(objects_store).free_list_head);
1180 EG(objects_store).free_list_head = obj->handle;
1181 p = current->ref = (zend_refcounted*)(((char*)obj) - obj->handlers->offset);
1182 }
1183 } else if (GC_TYPE(p) == IS_ARRAY) {
1184 zend_array *arr = (zend_array*)p;
1185
1186 GC_TYPE(arr) = IS_NULL;
1187 zend_hash_destroy(arr);
1188 }
1189 current = GC_G(next_to_free);
1190 }
1191
1192 /* Free objects */
1193 current = to_free.next;
1194 while (current != &to_free) {
1195 next = current->next;
1196 p = current->ref;
1197 if (EXPECTED(current >= GC_G(buf) && current < GC_G(buf) + GC_ROOT_BUFFER_MAX_ENTRIES)) {
1198 current->prev = GC_G(unused);
1199 GC_G(unused) = current;
1200 }
1201 efree(p);
1202 current = next;
1203 }
1204
1205 while (GC_G(additional_buffer) != additional_buffer_snapshot) {
1206 gc_additional_buffer *next = GC_G(additional_buffer)->next;
1207 efree(GC_G(additional_buffer));
1208 GC_G(additional_buffer) = next;
1209 }
1210
1211 GC_TRACE("Collection finished");
1212 GC_G(collected) += count;
1213 GC_G(next_to_free) = orig_next_to_free;
1214 #if ZEND_GC_DEBUG
1215 GC_G(gc_full) = orig_gc_full;
1216 #endif
1217 GC_G(gc_active) = 0;
1218 }
1219
1220 return count;
1221 }
1222
1223 /*
1224 * Local variables:
1225 * tab-width: 4
1226 * c-basic-offset: 4
1227 * indent-tabs-mode: t
1228 * End:
1229 *
1230 * vim:noexpandtab:
1231 */
1232
