1use crate::VmErrorResult;
2use crate::gc::GcObject;
3use crate::gc::GcRuntime;
4use crate::gc::debug::{DumpContext, HeapEnumContext};
5use crate::gc::{GCS_ATOMIC, GCS_PAUSE, GCS_PROPAGATE, GCS_PROPAGATE_AGAIN, GCS_SWEEP};
6use crate::gc::{GcCategoryNamer, GcHeapEdge, GcHeapNode};
7use crate::handle::RawHandle;
8use crate::memory::MemoryRuntime;
9use crate::state::GlobalState;
10use crate::state::{GcInterrupt, GcPhase};
11use crate::thread::Thread;
12use crate::types;
13use crate::value::TValue;
14use luau_common::{BString, flags};
15
16const GC_SWEEP_PAGE_STEP_COST: usize = 16;
17
18impl GlobalState {
19 unsafe fn heap_trigger_error_offset(&self) -> i64 {
21 let global_mut = unsafe { self.as_ptr().as_mut().unwrap_unchecked() };
22 let stats = &mut global_mut.gc_stats;
23 let error_kb = (stats
24 .atomic_start_total_size_bytes
25 .wrapping_sub(stats.heap_goal_size_bytes)
26 / 1024) as i32;
27
28 let slot =
29 &mut stats.trigger_terms[stats.trigger_term_pos as usize % stats.trigger_terms.len()];
30 let previous = *slot;
31 *slot = error_kb;
32 stats.trigger_integral += error_kb - previous;
33 stats.trigger_term_pos += 1;
34
35 let ku = 0.9f64;
36 let tu = 2.5f64;
37 let kp = 0.45 * ku;
38 let ti = 0.8 * tu;
39 let ki = 0.54 * ku / ti;
40
41 let proportional = kp * error_kb as f64;
42 let integral = ki * stats.trigger_integral as f64;
43 ((proportional + integral) * 1024.0) as i64
44 }
45
46 unsafe fn heap_trigger(&self, heap_goal: usize) -> usize {
48 unsafe {
49 let stats = &self.as_ptr().as_ref().unwrap_unchecked().gc_stats;
50 let allocation_duration = stats.atomic_start_timestamp - stats.end_timestamp;
51
52 if allocation_duration < 1e-3 {
53 return heap_goal;
54 }
55
56 let allocation_rate = stats
57 .atomic_start_total_size_bytes
58 .wrapping_sub(stats.end_total_size_bytes) as f64
59 / allocation_duration;
60 let mark_duration = stats.atomic_start_timestamp - stats.start_timestamp;
61
62 let expected_growth = (mark_duration * allocation_rate) as i64;
63 let offset = self.heap_trigger_error_offset();
64 let heap_trigger = heap_goal as i64 - (expected_growth + offset);
65 let total_bytes = self.as_ptr().as_ref().unwrap_unchecked().total_bytes as i64;
66
67 if heap_trigger < total_bytes {
68 total_bytes as usize
69 } else if heap_trigger > heap_goal as i64 {
70 heap_goal
71 } else {
72 heap_trigger as usize
73 }
74 }
75 }
76}
77
78impl Thread {
79 unsafe fn gc_interrupt(&self, event: GcInterrupt) -> VmErrorResult {
81 let global = unsafe { self.global() };
82 let Some(interrupt) = global.take_gc_interrupt_callback() else {
83 return Ok(());
84 };
85
86 interrupt(self, event)
87 }
88
89 unsafe fn gc_step(&self, limit: usize) -> usize {
91 unsafe {
92 let global = self.global();
93 let mut cost = 0usize;
94
95 match global.gc_state() {
96 GCS_PAUSE => {
97 self.mark_root();
98 debug_assert_eq!(global.gc_state(), GCS_PROPAGATE);
99 }
100 GCS_PROPAGATE => {
101 while global.gray().is_some() && cost < limit {
102 cost += global.propagate_mark();
103 }
104
105 if global.gray().is_none() {
106 global.set_gray(global.gray_again());
107 global.set_gray_again(None);
108 global.set_gc_state(GCS_PROPAGATE_AGAIN);
109 }
110 }
111 GCS_PROPAGATE_AGAIN => {
112 while global.gray().is_some() && cost < limit {
113 cost += global.propagate_mark();
114 }
115
116 if global.gray().is_none() {
117 global.set_gc_state(GCS_ATOMIC);
118 }
119 }
120 GCS_ATOMIC => {
121 let global_mut = global.as_ptr().as_mut().unwrap_unchecked();
122 global_mut.gc_stats.atomic_start_timestamp = crate::perf::clock();
123 global_mut.gc_stats.atomic_start_total_size_bytes = global_mut.total_bytes;
124
125 cost = self.atomic();
126 debug_assert_eq!(global.gc_state(), GCS_SWEEP);
127 }
128 GCS_SWEEP => {
129 while let Some(page) = global.sweep_gco_page()
130 && cost < limit
131 {
132 let next = page.next_page();
133 let steps = page.sweep_gco(self);
134
135 global.set_sweep_gco_page(next);
136 cost += steps as usize * GC_SWEEP_PAGE_STEP_COST;
137 }
138
139 if global.sweep_gco_page().is_none() {
140 let main_thread = global.main_thread();
141 debug_assert!(!global.is_dead((&main_thread).into()));
142 global.make_white((&main_thread).into());
143 self.shrink_buffers();
144 global.set_gc_state(GCS_PAUSE);
145 }
146 }
147 other => unreachable!("unexpected gc state {}", other),
148 }
149
150 cost
151 }
152 }
153}
154
155impl GcRuntime for Thread {
156 unsafe fn free_all(&self) {
158 unsafe {
159 let global = self.global();
160 debug_assert!(*self == global.main_thread());
161 self.visit_gco(self.as_ptr().cast(), super::sweep::delete_gco);
162
163 for index in 0..global
164 .as_ptr()
165 .as_ref()
166 .unwrap_unchecked()
167 .string_table
168 .size
169 .max(0) as usize
170 {
171 debug_assert!(
172 global
173 .as_ptr()
174 .as_ref()
175 .unwrap_unchecked()
176 .string_table
177 .hash
178 .add(index)
179 .read()
180 .is_null()
181 );
182 }
183
184 debug_assert_eq!(
185 global
186 .as_ptr()
187 .as_ref()
188 .unwrap_unchecked()
189 .string_table
190 .n_use,
191 0
192 );
193 }
194 }
195
196 unsafe fn needs_gc(&self) -> bool {
198 let global = unsafe { self.global() };
199 unsafe {
200 global.as_ptr().as_ref().unwrap_unchecked().total_bytes
201 >= global.as_ptr().as_ref().unwrap_unchecked().gc_threshold
202 }
203 }
204
205 unsafe fn check_gc(&self) -> VmErrorResult {
207 if unsafe { self.needs_gc() } {
208 unsafe { self.step(true)? };
209 }
210 Ok(())
211 }
212
213 unsafe fn step(&self, assist: bool) -> VmErrorResult<usize> {
215 unsafe {
216 let global = self.global();
217 let step_size = global.as_ptr().as_ref().unwrap_unchecked().gc_step_size as usize;
218 let step_mul = global.as_ptr().as_ref().unwrap_unchecked().gc_step_mul as usize;
219 let mut limit = step_size * step_mul / 100;
220
221 debug_assert!(
222 global.as_ptr().as_ref().unwrap_unchecked().total_bytes
223 >= global.as_ptr().as_ref().unwrap_unchecked().gc_threshold
224 );
225 let debt = global.as_ptr().as_ref().unwrap_unchecked().total_bytes
226 - global.as_ptr().as_ref().unwrap_unchecked().gc_threshold;
227
228 if flags::LuauBackedgeHeapCheck.get() && assist {
229 limit = limit.max(debt * step_mul / 100);
230 }
231
232 self.gc_interrupt(GcInterrupt::BeforeStep)?;
233
234 let gc_state = global.gc_state();
235 if gc_state == GCS_PAUSE {
236 global
237 .as_ptr()
238 .as_mut()
239 .unwrap_unchecked()
240 .gc_stats
241 .start_timestamp = crate::perf::clock();
242 }
243
244 let last_gc_state = gc_state;
245 let work = self.gc_step(limit);
246 let actual_step_size =
247 work * 100 / global.as_ptr().as_ref().unwrap_unchecked().gc_step_mul as usize;
248
249 if global.gc_state() == GCS_PAUSE {
250 let total_bytes = global.as_ptr().as_ref().unwrap_unchecked().total_bytes;
251 let gc_goal = global.as_ptr().as_ref().unwrap_unchecked().gc_goal as usize;
252 let heap_goal = (total_bytes / 100) * gc_goal;
253 let heap_trigger = global.heap_trigger(heap_goal);
254 let end_timestamp = crate::perf::clock();
255
256 let global_mut = global.as_ptr().as_mut().unwrap_unchecked();
257 global_mut.gc_threshold = heap_trigger;
258 global_mut.gc_stats.heap_goal_size_bytes = heap_goal;
259 global_mut.gc_stats.end_timestamp = end_timestamp;
260 global_mut.gc_stats.end_total_size_bytes = global_mut.total_bytes;
261 } else {
262 let global_mut = global.as_ptr().as_mut().unwrap_unchecked();
263 global_mut.gc_threshold = global_mut.total_bytes + actual_step_size;
264 if global_mut.gc_threshold >= debt {
265 global_mut.gc_threshold -= debt;
266 }
267 }
268
269 self.gc_interrupt(GcInterrupt::AfterStep {
270 previous_phase: GcPhase::from_state(last_gc_state),
271 })?;
272 Ok(actual_step_size)
273 }
274 }
275
276 unsafe fn full_gc(&self) {
278 unsafe {
279 let global = self.global();
280
281 if global.keep_invariant() {
282 global.set_sweep_gco_page(global.all_gco_pages());
283 global.set_gray(None);
284 global.set_gray_again(None);
285 global.set_weak(None);
286 global.set_gc_state(GCS_SWEEP);
287 }
288
289 debug_assert!(matches!(global.gc_state(), GCS_PAUSE | GCS_SWEEP));
290 while global.gc_state() != GCS_PAUSE {
291 debug_assert_eq!(global.gc_state(), GCS_SWEEP);
292 self.gc_step(usize::MAX);
293 }
294
295 let sentinel = global.uv_head();
296 let mut upvalue = sentinel.open_data().next();
297
298 while upvalue != sentinel {
299 let current_upvalue = upvalue;
300 let next = current_upvalue.open_data().next();
301
302 current_upvalue
303 .as_ptr()
304 .as_mut()
305 .unwrap_unchecked()
306 .marked_open = 0;
307 upvalue = next;
308 }
309
310 self.mark_root();
311 while global.gc_state() != GCS_PAUSE {
312 self.gc_step(usize::MAX);
313 }
314
315 self.shrink_buffers_full();
316
317 let total_bytes = global.as_ptr().as_ref().unwrap_unchecked().total_bytes;
318 let gc_goal = global.as_ptr().as_ref().unwrap_unchecked().gc_goal as usize;
319 let gc_step_mul = global.as_ptr().as_ref().unwrap_unchecked().gc_step_mul as usize;
320 let heap_goal_size_bytes = (total_bytes / 100) * gc_goal;
321 let mut gc_threshold = total_bytes * (gc_goal * gc_step_mul / 100 - 100) / gc_step_mul;
322
323 if gc_threshold < total_bytes {
324 gc_threshold = total_bytes;
325 }
326
327 let global_mut = global.as_ptr().as_mut().unwrap_unchecked();
328 global_mut.gc_threshold = gc_threshold;
329 global_mut.gc_stats.heap_goal_size_bytes = heap_goal_size_bytes;
330 }
331 }
332
333 unsafe fn validate(&self) {
335 unsafe {
336 let global = self.global();
337
338 debug_assert!(!global.is_dead(self.into()));
339 global.validate_liveness(TValue::from_ref(
340 &global.as_ptr().as_ref().unwrap_unchecked().registry,
341 ));
342
343 for tag in 0..types::LUA_T_COUNT {
344 if let Some(metatable) = global.metatable(tag) {
345 debug_assert!(!global.is_dead(metatable.into()));
346 }
347 }
348
349 for metatable in (&*global.userdata_type_registry_ptr()).recognized_metatables() {
350 debug_assert!(!global.is_dead(metatable.into()));
351 }
352
353 for tag in 0..crate::userdata::USERDATA_TAG_LIMIT {
354 if let Some(metatable) = global.userdata_metatable(tag) {
355 debug_assert!(!global.is_dead(metatable.into()));
356 }
357 }
358
359 for tag in 0..crate::userdata::USERDATA_INTERNAL_LIMIT {
360 let direct_access =
361 &global.as_ptr().as_ref().unwrap_unchecked().userdata_direct[tag];
362 global.validate_liveness(TValue::from_ref(&direct_access.index_tm));
363 global.validate_liveness(TValue::from_ref(&direct_access.new_index_tm));
364 global.validate_liveness(TValue::from_ref(&direct_access.name_call_tm));
365
366 if let Some(fields) = global.userdata_direct_field(tag) {
367 debug_assert!(!global.is_dead(fields.into()));
368 }
369 }
370
371 global.validate_gray_list(global.weak());
372 global.validate_gray_list(global.gray());
373 global.validate_gray_list(global.gray_again());
374
375 global.validate_object(GcObject::from(self));
376 self.visit_gco(self.as_ptr().cast(), super::debug::validate_gco_visitor);
377
378 let sentinel = global.uv_head();
379 let mut upvalue = sentinel.open_data().next();
380
381 while upvalue != sentinel {
382 let current_upvalue = upvalue;
383 let open = current_upvalue.open_data();
384 let object: GcObject = current_upvalue.into();
385 debug_assert_eq!(
386 current_upvalue.as_ptr().as_ref().unwrap_unchecked().tt,
387 types::LUA_TUPVALUE as u8
388 );
389 debug_assert!(current_upvalue.is_open());
390 debug_assert!(open.next().open_data().prev() == current_upvalue);
391 debug_assert!(open.prev().open_data().next() == current_upvalue);
392 debug_assert!(!object.is_black());
393
394 upvalue = open.next();
395 }
396 }
397 }
398
399 unsafe fn dump(&self, file: *mut (), category_name: Option<&mut dyn GcCategoryNamer>) {
401 unsafe {
402 let global = self.global();
403 let output = &mut *file.cast::<BString>();
404 let mut category_name = category_name;
405
406 output.clear();
407 output.extend_from_slice(b"{\"objects\":{\n");
408
409 super::debug::dump_gco(output, self, global.main_thread().into());
410
411 let mut context = DumpContext {
412 thread: self,
413 output,
414 };
415 self.visit_gco((&raw mut context).cast(), super::debug::dump_gco_visitor);
416
417 output.extend_from_slice(b"\"0\":{\"type\":\"userdata\",\"cat\":0,\"size\":0}\n");
418 output.extend_from_slice(b"},\"roots\":{\n");
419 output.extend_from_slice(b"\"mainthread\":");
420 super::debug::append_ref(output, global.main_thread().into());
421 output.extend_from_slice(b",\"registry\":");
422 super::debug::append_ref(
423 output,
424 TValue::from_ref(&global.as_ptr().as_ref().unwrap_unchecked().registry).gc_value(),
425 );
426 output.extend_from_slice(b"},\"stats\":{\n");
427 output.extend_from_slice(b"\"size\":");
428 super::debug::append_decimal(
429 output,
430 global.as_ptr().as_ref().unwrap_unchecked().total_bytes,
431 );
432 output.extend_from_slice(b",\n\"categories\":{\n");
433
434 for (index, bytes) in global
435 .as_ptr()
436 .as_ref()
437 .unwrap_unchecked()
438 .memcat_bytes
439 .iter()
440 .copied()
441 .enumerate()
442 {
443 if bytes == 0 {
444 continue;
445 }
446
447 output.push(b'"');
448 super::debug::append_decimal(output, index);
449 output.extend_from_slice(b"\":{");
450
451 if let Some(category_name) = category_name.as_deref_mut() {
452 output.extend_from_slice(b"\"name\":\"");
453 category_name.category_name(self, index as u8, output);
454 output.extend_from_slice(b"\", ");
455 }
456
457 output.extend_from_slice(b"\"size\":");
458 super::debug::append_decimal(output, bytes);
459 output.extend_from_slice(b"},\n");
460 }
461
462 output.extend_from_slice(b"\"none\":{}\n}\n}}\n");
463 }
464 }
465
466 unsafe fn enum_heap(&self, context: *mut (), node: GcHeapNode, edge: GcHeapEdge) {
468 unsafe {
469 let global = self.global();
470 let mut heap = HeapEnumContext {
471 thread: self,
472 context,
473 node,
474 edge,
475 };
476
477 heap.enum_object(global.main_thread().into());
478 self.visit_gco((&raw mut heap).cast(), super::debug::enum_heap_gco_visitor);
479 }
480 }
481
482 unsafe fn allocation_rate(&self) -> i64 {
484 unsafe {
485 let global = self.global();
486 let duration_threshold = 1e-3;
487
488 let (bytes, duration) = match global.gc_state() {
489 x if x <= GCS_ATOMIC => (
490 global
491 .as_ptr()
492 .as_ref()
493 .unwrap_unchecked()
494 .total_bytes
495 .wrapping_sub(
496 global
497 .as_ptr()
498 .as_ref()
499 .unwrap_unchecked()
500 .gc_stats
501 .end_total_size_bytes,
502 ),
503 crate::perf::clock()
504 - global
505 .as_ptr()
506 .as_ref()
507 .unwrap_unchecked()
508 .gc_stats
509 .end_timestamp,
510 ),
511 _ => (
512 global
513 .as_ptr()
514 .as_ref()
515 .unwrap_unchecked()
516 .gc_stats
517 .atomic_start_total_size_bytes
518 .wrapping_sub(
519 global
520 .as_ptr()
521 .as_ref()
522 .unwrap_unchecked()
523 .gc_stats
524 .end_total_size_bytes,
525 ),
526 global
527 .as_ptr()
528 .as_ref()
529 .unwrap_unchecked()
530 .gc_stats
531 .atomic_start_timestamp
532 - global
533 .as_ptr()
534 .as_ref()
535 .unwrap_unchecked()
536 .gc_stats
537 .end_timestamp,
538 ),
539 };
540
541 if duration < duration_threshold {
542 -1
543 } else {
544 (bytes as f64 / duration) as i64
545 }
546 }
547 }
548}