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