1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
//! Garbage collection
//!
//! Garbage collection
//!
//! This module implements PHP's reference-counting garbage collector with
//! cycle detection using the tri-color marking algorithm.
#[cfg(test)]
mod tests;
use crate::engine::types::Refcounted;
use std::sync::atomic::{AtomicU32, Ordering};
/// GC colors for tri-color marking
#[repr(u32)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum GcColor {
Black = 0x000000, // In use or free
White = 0x100000, // Member of garbage cycle
Grey = 0x200000, // Possible member of cycle
Purple = 0x300000, // Possible root of cycle
}
// GC buffer entry (for future use)
// struct GcRootBuffer {
// ref_: *mut Refcounted,
// next: Option<Box<GcRootBuffer>>,
// }
/// Garbage collector state
pub struct Gc {
/// Root buffer for possible cycles
roots: Vec<*mut Refcounted>,
/// Threshold for triggering GC
threshold: AtomicU32,
/// Number of roots in buffer
root_count: AtomicU32,
/// Statistics
collected: AtomicU32,
}
impl Gc {
pub fn new() -> Self {
Self {
roots: Vec::new(),
threshold: AtomicU32::new(10000),
root_count: AtomicU32::new(0),
collected: AtomicU32::new(0),
}
}
/// Add a possible root to the GC buffer
///
/// # Safety
///
/// The caller must ensure that `ref_` is a valid pointer to a `Refcounted`
/// object. If `ref_` is null, the function will return early without doing anything.
pub unsafe fn add_possible_root(&mut self, ref_: *mut Refcounted) {
if ref_.is_null() {
return;
}
// Check if refcount is 1 (possible cycle)
let refcount = unsafe { (*ref_).gc.refcount.load(Ordering::Acquire) };
if refcount == 1 {
self.roots.push(ref_);
self.root_count.fetch_add(1, Ordering::Relaxed);
}
}
/// Check if GC should run
pub fn should_collect(&self) -> bool {
let count = self.root_count.load(Ordering::Relaxed);
let threshold = self.threshold.load(Ordering::Relaxed);
count >= threshold
}
/// Collect cycles
pub fn collect_cycles(&mut self) -> u32 {
if !self.should_collect() {
return 0;
}
// Mark phase - mark all roots as grey
for &root in &self.roots {
unsafe {
if !root.is_null() {
self.mark_grey(root);
}
}
}
// Scan phase - scan all grey nodes
for &root in &self.roots {
unsafe {
if !root.is_null() {
self.scan(root);
}
}
}
// Collect phase - collect white nodes
let collected = self.collect_white();
// Clear roots
self.roots.clear();
self.root_count.store(0, Ordering::Relaxed);
self.collected.fetch_add(collected, Ordering::Relaxed);
collected
}
/// Mark a node as grey (possible member of cycle)
unsafe fn mark_grey(&self, ref_: *mut Refcounted) {
if ref_.is_null() {
return;
}
unsafe {
let type_info = (*ref_).gc.type_info.load(Ordering::Acquire);
let current_color = type_info & 0xFF0000;
if current_color == GcColor::Purple as u32 {
(*ref_).gc.type_info.store(
type_info & !0xFF0000 | GcColor::Grey as u32,
Ordering::Release,
);
}
}
}
/// Scan a grey node
unsafe fn scan(&self, ref_: *mut Refcounted) -> u32 {
if ref_.is_null() {
return 0;
}
unsafe {
let mut type_info = (*ref_).gc.type_info.load(Ordering::Acquire);
let current_color = type_info & 0xFF0000;
if current_color != GcColor::Grey as u32 {
return 0;
}
let refcount = (*ref_).gc.refcount.load(Ordering::Acquire);
let is_black = refcount > 0;
type_info &= !0xFF0000;
type_info |= if is_black {
GcColor::Black as u32
} else {
GcColor::White as u32
};
(*ref_).gc.type_info.store(type_info, Ordering::Release);
if is_black {
1
} else {
0
}
}
}
/// Collect white nodes (garbage)
fn collect_white(&mut self) -> u32 {
let mut collected = 0;
for &ref_ in &self.roots {
unsafe {
if !ref_.is_null() {
let type_info = (*ref_).gc.type_info.load(Ordering::Acquire);
let current_color = type_info & 0xFF0000;
if current_color == GcColor::White as u32 {
self.free_node(ref_);
collected += 1;
}
}
}
}
collected
}
/// Free a node and its children
unsafe fn free_node(&self, ref_: *mut Refcounted) {
if ref_.is_null() {
return;
}
unsafe {
let refcount = (*ref_).gc.refcount.fetch_sub(1, Ordering::AcqRel);
if refcount == 1 {
let _ = Box::from_raw(ref_);
}
}
}
/// Get GC statistics
pub fn get_stats(&self) -> GcStats {
GcStats {
root_count: self.root_count.load(Ordering::Relaxed),
threshold: self.threshold.load(Ordering::Relaxed),
collected: self.collected.load(Ordering::Relaxed),
}
}
/// Set GC threshold
pub fn set_threshold(&self, threshold: u32) {
self.threshold.store(threshold, Ordering::Relaxed);
}
}
/// GC statistics
#[derive(Debug, Clone, Copy)]
pub struct GcStats {
pub root_count: u32,
pub threshold: u32,
pub collected: u32,
}
impl Default for Gc {
fn default() -> Self {
Self::new()
}
}