use std::marker::PhantomData;
use crate::id::{Handle, Kind, ObjectId, TerminationReason};
use crate::opcode::{Capture, Op};
use crate::table::{Table, TableKey};
use crate::value::Value;
pub(crate) const MAX_OBJECTS: u32 = 1 << 20;
pub(crate) const OBJECTS_CEILING: u32 = 1 << 28;
pub(crate) const RESERVED_NAMES: [&str; 12] = [
"nil", "boolean", "number", "string", "table", "function", "thread", "userdata", "true",
"false", "integer", "float",
];
pub(crate) fn reserved_texts() -> impl Iterator<Item = &'static str> {
crate::id::LuaFault::ALL
.iter()
.map(|fault| fault.text())
.chain(RESERVED_NAMES)
}
pub(crate) const BASIC_TYPES: usize = 9;
#[inline]
pub(crate) fn basic_type(value: Value) -> usize {
match value {
Value::Nil => 0,
Value::Bool(_) => 1,
Value::Integer(_) | Value::Float(_) => 3,
Value::String(_) => 4,
Value::Table(_) => 5,
Value::Closure(_) | Value::Native(_) | Value::NativeClosure(_) => 6,
Value::LightUserdata(..) => 2,
Value::Userdata(_) => 7,
Value::Thread(_) => 8,
}
}
pub(crate) fn type_name(value: Value) -> &'static str {
match value {
Value::Nil => "nil",
Value::Bool(_) => "boolean",
Value::Integer(_) | Value::Float(_) => "number",
Value::String(_) => "string",
Value::Table(_) => "table",
Value::Closure(_) | Value::Native(_) | Value::NativeClosure(_) => "function",
Value::Thread(_) => "thread",
Value::Userdata(_) | Value::LightUserdata(..) => "userdata",
}
}
pub(crate) const PER_OBJECT_TYPES: [usize; 2] = [5, 7];
pub(crate) fn userdata_cost(user_values: usize, charge: u64) -> u64 {
cost::OBJECT
.saturating_add(cost::USER_VALUE.saturating_mul(user_values as u64))
.saturating_add(charge)
}
pub(crate) fn native_closure_cost(values: usize, state: usize) -> u64 {
cost::OBJECT + cost::REF * (values + state) as u64
}
pub(crate) mod cost {
pub(crate) const OBJECT: u64 = 32;
pub(crate) const ENTRY: u64 = 32;
pub(crate) const REF: u64 = 8;
pub(crate) const THREAD: u64 = 256;
pub(crate) const STACK_SLOT: u64 = 16;
pub(crate) const USER_VALUE: u64 = 16;
}
pub(crate) const STRING_CEILING: usize = 1 << 30;
pub(crate) const MAX_STRING_BYTES: usize = STRING_CEILING;
pub(crate) const STRING_BYTES_RANGE: std::ops::RangeInclusive<usize> = 1_024..=STRING_CEILING;
pub(crate) const GC_MIN_DEBT: u64 = 64 * 1024;
pub(crate) const MAX_LOGICAL_HEAP: u64 = 64 * 1024 * 1024;
pub(crate) const GC_PAUSE: u8 = 200 / 4;
pub(crate) const GC_STEPMUL: u8 = 100 / 4;
pub(crate) const GC_STEPSIZE: u8 = 13;
pub(crate) const GC_MINORMUL: u8 = 20;
pub(crate) const GC_MAJORMUL: u8 = 100 / 4;
#[derive(Clone, Debug)]
pub(crate) struct GcState {
pub(crate) auto: bool,
pub(crate) debt: u64,
pub(crate) threshold: u64,
pub(crate) min_debt: u64,
pub(crate) live: u64,
pub(crate) used: u64,
pub(crate) collections: u64,
pub(crate) quota: u64,
pub(crate) pause: u8,
pub(crate) stepmul: u8,
pub(crate) stepsize: u8,
pub(crate) sched: i64,
pub(crate) owed: u64,
pub(crate) full: Option<u64>,
pub(crate) prepaid: u32,
pub(crate) work: u64,
pub(crate) cycle_work: u64,
pub(crate) trace: u64,
pub(crate) generational: bool,
pub(crate) minormul: u8,
pub(crate) majormul: u8,
pub(crate) major_base: u64,
pub(crate) major_objects: u32,
pub(crate) bad: u64,
pub(crate) minors: u64,
}
impl GcState {
pub(crate) fn new(auto: bool, min_debt: u64, max_objects: u32, quota: u64) -> Self {
let min_debt = min_debt.max(1);
let threshold = next_threshold(0, GC_PAUSE, min_debt, 0, max_objects, quota);
Self {
auto,
debt: 0,
threshold,
min_debt,
live: 0,
used: 0,
collections: 0,
quota,
pause: GC_PAUSE,
stepmul: GC_STEPMUL,
stepsize: GC_STEPSIZE,
sched: -(threshold.min(i64::MAX as u64) as i64),
owed: 0,
full: None,
prepaid: 0,
work: 0,
cycle_work: 0,
trace: 0,
generational: false,
minormul: GC_MINORMUL,
majormul: GC_MAJORMUL,
major_base: 0,
major_objects: 0,
bad: 0,
minors: 0,
}
}
#[inline]
pub(crate) fn fits(&self, amount: u64) -> bool {
self.used.saturating_add(amount) <= self.quota
}
#[inline]
pub(crate) fn headroom(&self) -> u64 {
self.quota.saturating_sub(self.used)
}
#[inline]
pub(crate) fn charge(&mut self, amount: u64) {
self.used = self.used.saturating_add(amount);
self.debt = self.debt.saturating_add(amount);
self.sched = self
.sched
.saturating_add(amount.min(i64::MAX as u64) as i64);
}
#[inline]
pub(crate) fn due(&self) -> bool {
self.auto && self.sched > 0
}
pub(crate) fn step_bytes(&self) -> u64 {
if self.stepsize < 63 {
1u64 << self.stepsize
} else {
u64::MAX
}
}
pub(crate) fn work_for(&self, bytes: u64) -> u64 {
let stepmul = (u64::from(self.stepmul) * 4) | 1;
(u128::from(bytes).saturating_mul(u128::from(stepmul)) / 1024)
.min(u128::from(u64::MAX))
.max(1) as u64
}
pub(crate) fn schedule_step(&mut self, room: u64) {
let bytes = u64::try_from(self.sched.max(0))
.unwrap_or(0)
.saturating_add(self.step_bytes());
let share = (u128::from(self.cycle_work)
.saturating_mul(u128::from(bytes))
.saturating_mul(2)
/ u128::from(room.max(1)))
.min(u128::from(u64::MAX)) as u64;
let work = self.work_for(bytes).max(share);
self.owed = self.owed.saturating_add(work);
self.sched = -(self.step_bytes().min(i64::MAX as u64) as i64);
}
pub(crate) fn cycle_done(&mut self, live: u64, debt: u64, objects: u32, max_objects: u32) {
self.collections = self.collections.saturating_add(1);
self.live = live;
self.debt = debt;
self.owed = 0;
self.threshold = next_threshold(
live,
self.pause,
self.min_debt,
objects,
max_objects,
self.quota,
);
self.sched = debt.min(i64::MAX as u64) as i64 - self.threshold.min(i64::MAX as u64) as i64;
}
pub(crate) fn minor_done(&mut self, live: u64, objects: u32, max_objects: u32) {
self.minors = self.minors.saturating_add(1);
self.live = live;
self.debt = 0;
self.owed = 0;
self.threshold = self.minor_threshold(live, objects, max_objects);
self.sched = -(self.threshold.min(i64::MAX as u64) as i64);
}
pub(crate) fn major_done(&mut self, live: u64, debt: u64, objects: u32, max_objects: u32) {
self.collections = self.collections.saturating_add(1);
self.live = live;
self.debt = debt;
self.owed = 0;
self.major_base = live;
self.major_objects = objects;
self.threshold = self.minor_threshold(live, objects, max_objects);
self.sched = debt.min(i64::MAX as u64) as i64 - self.threshold.min(i64::MAX as u64) as i64;
}
fn minor_threshold(&self, live: u64, objects: u32, max_objects: u32) -> u64 {
let debt =
(u128::from(live) * u128::from(self.minormul) / 100).min(u128::from(u64::MAX)) as u64;
let debt = debt.max(self.min_debt);
let headroom = u64::from(max_objects.saturating_sub(objects));
debt.min(cost::OBJECT * headroom / 2)
.min(self.quota.saturating_sub(live) / 2)
.max(cost::OBJECT)
}
pub(crate) fn major_growth(&self, max_objects: u32) -> u64 {
let percent = u128::from(self.majormul) * 4;
let growth = (u128::from(self.major_base) * percent / 100).min(u128::from(u64::MAX)) as u64;
let headroom = u64::from(max_objects.saturating_sub(self.major_objects));
let average = (self.major_base / u64::from(self.major_objects.max(1))).max(cost::OBJECT);
growth
.max(self.min_debt.saturating_mul(2))
.min(average.saturating_mul(headroom) / 4 * 3)
.min(self.quota.saturating_sub(self.major_base) / 4 * 3)
}
pub(crate) fn major_due(&self, max_objects: u32) -> bool {
self.used
> self
.major_base
.saturating_add(self.major_growth(max_objects))
}
pub(crate) fn note(&mut self, event: u64) {
self.trace = (self.trace ^ event)
.wrapping_mul(0x0100_0000_01b3)
.rotate_left(7)
^ self.work;
}
}
pub(crate) fn next_threshold(
live: u64,
pause: u8,
min_debt: u64,
objects: u32,
max_objects: u32,
quota: u64,
) -> u64 {
let pause = u64::from(pause) * 4;
let base = (u128::from(live) * u128::from(pause) / 100).min(u128::from(u64::MAX)) as u64;
let mut debt = base.saturating_sub(live);
if pause > 100 {
debt = debt.max(min_debt);
}
let headroom = u64::from(max_objects.saturating_sub(objects));
debt.min(cost::OBJECT * headroom / 2)
.min(quota.saturating_sub(live) / 2)
.max(cost::OBJECT)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum InsertError {
NoTable,
Memory,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Status {
Ready = 1,
LuaSuspended = 2,
Waiting = 3,
Completed = 4,
Failed = 5,
}
impl Status {
pub(crate) fn from_u8(tag: u8) -> Option<Self> {
Some(match tag {
1 => Self::Ready,
2 => Self::LuaSuspended,
3 => Self::Waiting,
4 => Self::Completed,
5 => Self::Failed,
_ => return None,
})
}
pub(crate) fn tag(self) -> u8 {
self as u8
}
}
#[derive(Clone, Debug)]
pub(crate) enum Pending {
Prepared {
sequence: u64,
symbol: String,
arg: i64,
dest: u8,
},
Waiting {
sequence: u64,
symbol: String,
arg: i64,
dest: u8,
wait_key: u64,
},
Resuming {
child: Handle<ThreadObj>,
dest: u8,
nresults: u8,
},
NativePrepared { sequence: u64 },
NativeWaiting {
sequence: Option<u64>,
wait_key: u64,
},
Capability {
sequence: u64,
wait_key: u64,
completed: bool,
},
Assigning { src: u32, nvalues: u16, next: u16 },
Deferred,
}
#[derive(Clone, Debug)]
pub(crate) enum AssignTarget {
Register(u32),
Field { table: Value, key: Value },
}
#[derive(Clone, Debug)]
pub(crate) struct Frame {
pub(crate) closure: Handle<ClosureObj>,
pub(crate) pc: u32,
pub(crate) base: u32,
pub(crate) limit: u32,
pub(crate) vararg_len: u32,
pub(crate) nresults: u8,
pub(crate) flags: u8,
pub(crate) cold: Option<Box<FrameCold>>,
}
#[cfg(target_pointer_width = "64")]
const _: () = assert!(std::mem::size_of::<Frame>() == 40);
#[derive(Clone, Debug, Default)]
pub(crate) struct FrameCold {
pub(crate) pending: Option<Pending>,
pub(crate) wait_request: Option<HostWait>,
pub(crate) targets: Vec<AssignTarget>,
pub(crate) meta: Option<MetaCall>,
pub(crate) boundary: Option<Boundary>,
}
impl FrameCold {
pub(crate) fn is_empty(&self) -> bool {
self.pending.is_none()
&& self.wait_request.is_none()
&& self.targets.is_empty()
&& self.meta.is_none()
&& self.boundary.is_none()
}
fn clear(&mut self) {
self.pending = None;
self.wait_request = None;
self.targets.clear();
self.meta = None;
self.boundary = None;
}
pub(crate) fn into_box(self) -> Option<Box<Self>> {
if self.is_empty() {
None
} else {
Some(Box::new(self))
}
}
pub(crate) fn with_boundary(
boundary: Boundary,
spare: &mut Option<Box<Self>>,
) -> Option<Box<Self>> {
let mut cold = spare.take().unwrap_or_default();
debug_assert!(cold.is_empty());
cold.boundary = Some(boundary);
Some(cold)
}
}
impl Frame {
pub(crate) const TAIL: u8 = 1;
pub(crate) fn is_tail(&self) -> bool {
self.flags & Self::TAIL != 0
}
pub(crate) fn cold_mut(&mut self, spare: &mut Option<Box<FrameCold>>) -> &mut FrameCold {
self.cold.get_or_insert_with(|| {
let cold = spare.take().unwrap_or_default();
debug_assert!(cold.is_empty());
cold
})
}
pub(crate) fn release_cold(&mut self, spare: &mut Option<Box<FrameCold>>) {
if self.cold.as_ref().is_some_and(|cold| cold.is_empty()) {
self.recycle_cold(spare);
}
}
pub(crate) fn recycle_cold(&mut self, spare: &mut Option<Box<FrameCold>>) {
if let Some(mut cold) = self.cold.take() {
cold.clear();
*spare = Some(cold);
}
}
pub(crate) fn pending(&self) -> Option<&Pending> {
self.cold.as_ref()?.pending.as_ref()
}
pub(crate) fn pending_mut(&mut self) -> Option<&mut Pending> {
self.cold.as_mut()?.pending.as_mut()
}
pub(crate) fn meta(&self) -> Option<&MetaCall> {
self.cold.as_ref()?.meta.as_ref()
}
pub(crate) fn meta_mut(&mut self) -> Option<&mut MetaCall> {
self.cold.as_mut()?.meta.as_mut()
}
pub(crate) fn boundary(&self) -> Option<&Boundary> {
self.cold.as_ref()?.boundary.as_ref()
}
pub(crate) fn boundary_mut(&mut self) -> Option<&mut Boundary> {
self.cold.as_mut()?.boundary.as_mut()
}
pub(crate) fn wait_request(&self) -> Option<&HostWait> {
self.cold.as_ref()?.wait_request.as_ref()
}
pub(crate) fn targets(&self) -> &[AssignTarget] {
self.cold.as_ref().map_or(&[], |cold| &cold.targets)
}
pub(crate) fn set_pending(
&mut self,
value: Option<Pending>,
spare: &mut Option<Box<FrameCold>>,
) {
if value.is_some() {
self.cold_mut(spare).pending = value;
} else {
self.clear_pending(spare);
}
}
#[inline(always)]
pub(crate) fn clear_pending(&mut self, spare: &mut Option<Box<FrameCold>>) {
if let Some(cold) = &mut self.cold {
cold.pending = None;
self.release_cold(spare);
}
}
pub(crate) fn set_meta(&mut self, value: Option<MetaCall>, spare: &mut Option<Box<FrameCold>>) {
if value.is_some() {
self.cold_mut(spare).meta = value;
} else if let Some(cold) = &mut self.cold {
cold.meta = None;
self.release_cold(spare);
}
}
pub(crate) fn set_wait_request(
&mut self,
value: Option<HostWait>,
spare: &mut Option<Box<FrameCold>>,
) {
if value.is_some() {
self.cold_mut(spare).wait_request = value;
} else if let Some(cold) = &mut self.cold {
cold.wait_request = None;
self.release_cold(spare);
}
}
pub(crate) fn clear_targets(&mut self, spare: &mut Option<Box<FrameCold>>) {
if let Some(cold) = &mut self.cold {
cold.targets.clear();
self.release_cold(spare);
}
}
pub(crate) fn take_meta(&mut self, spare: &mut Option<Box<FrameCold>>) -> Option<MetaCall> {
let value = self.cold.as_mut()?.meta.take();
self.release_cold(spare);
value
}
pub(crate) fn take_wait_request(
&mut self,
spare: &mut Option<Box<FrameCold>>,
) -> Option<HostWait> {
let value = self.cold.as_mut()?.wait_request.take();
self.release_cold(spare);
value
}
}
#[derive(Clone, Debug)]
pub(crate) struct HostWait {
pub(crate) operation: String,
pub(crate) payload: Vec<Value>,
}
#[derive(Clone, Debug)]
pub(crate) enum Boundary {
Protect {
func: u32,
advance_caller: bool,
handler: Option<Value>,
},
Handler {
slot: u32,
protect: u32,
target: u32,
depth: u8,
fault: crate::id::LuaFault,
},
Builtin {
func: u32,
passed: u32,
advance_caller: bool,
task: Task,
},
Native {
func: u32,
passed: u32,
advance_caller: bool,
symbol: u32,
tag: u32,
kept: u32,
sequence: Option<u64>,
error: Option<(crate::id::LuaFault, Value)>,
resuming: bool,
no_yield: bool,
},
Finalizer {
func: u32,
saved_top: u32,
},
Hook {
func: u32,
saved_top: u32,
target: u32,
instruction: Option<(usize, u32, u8)>,
after: crate::runtime::hooks::AfterHook,
},
HookNative {
func: u32,
passed: u32,
callee: Value,
advance_caller: bool,
phase: u8,
produced: u32,
result: u32,
},
}
impl Boundary {
pub(crate) fn catches(&self) -> bool {
match self {
Self::Protect { .. } => true,
Self::Handler { .. } | Self::Hook { .. } | Self::HookNative { .. } => false,
Self::Builtin { task, .. } => task.catches(),
Self::Native { .. } | Self::Finalizer { .. } => true,
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub(crate) enum Task {
ToString,
Print { next: u32 },
Pairs,
Ipairs { index: i64 },
Load { source: Vec<u8> },
HostLoad(Box<crate::runtime::hostload::HostLoad>),
DoFile,
Lib(Box<crate::library::LibTask>),
Collect {
result: u8,
wait: bool,
ended: bool,
left: u32,
},
Io(Box<crate::iolib::IoWork>),
}
impl Task {
pub(crate) fn wants(&self) -> u8 {
match self {
Self::Pairs => 3,
Self::DoFile => crate::opcode::COUNT_OPEN,
Self::Lib(task) if matches!(task.wait, crate::library::Wait::Pair { .. }) => 2,
_ => 1,
}
}
pub(crate) fn scratch(&self) -> u32 {
match self {
Self::Lib(task) => task.work.scratch(),
Self::Io(work) => work.scratch(),
_ => 0,
}
}
pub(crate) fn held_bytes(&self) -> usize {
match self {
Self::Load { source } => source.len(),
Self::HostLoad(work) => work.held_bytes(),
Self::Io(work) => work.held_bytes(),
Self::Lib(task) => match &task.work {
crate::library::Work::Concat { text, .. } => text.len(),
crate::library::Work::Str(work) => work.held_bytes(),
crate::library::Work::Utf8(work) => work.held_bytes(),
crate::library::Work::Os(work) => work.out.len(),
crate::library::Work::Package(work) => work.held_bytes(),
crate::library::Work::Debug(work) => work.held_bytes(),
_ => 0,
},
_ => 0,
}
}
pub(crate) fn yieldable(&self) -> bool {
matches!(self, Self::Pairs | Self::DoFile)
}
pub(crate) fn catches(&self) -> bool {
matches!(self, Self::Load { .. })
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct Unwind {
pub(crate) error: Option<(crate::id::LuaFault, Value)>,
pub(crate) phase: UnwindPhase,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum UnwindPhase {
Raised,
Popping { target: Option<u32> },
}
#[derive(Clone, Debug)]
pub(crate) struct MetaCall {
pub(crate) event: MetaEvent,
pub(crate) slot: u32,
pub(crate) nargs: u8,
pub(crate) phase: MetaPhase,
pub(crate) close: Option<Box<Closing>>,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct Closing {
pub(crate) from: u32,
pub(crate) next: CloseNext,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum MetaEvent {
Store { dst: u8 },
Truth { dst: u8, negate: bool },
NewIndex,
NewIndexAssign,
Close,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) enum CloseNext {
Advance,
Return { src: u32, produced: u32 },
Unwind(Unwind),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum MetaPhase {
Running,
NativePrepared { sequence: u64 },
NativeWaiting {
sequence: Option<u64>,
wait_key: u64,
},
Idle,
}
#[derive(Clone, Debug)]
pub(crate) struct StringObj {
pub(crate) id: ObjectId,
pub(crate) bytes: crate::table::KeyString,
}
impl StringObj {
#[inline]
pub(crate) fn hash(&self) -> u64 {
self.bytes.hash()
}
}
#[derive(Clone, Debug)]
pub(crate) struct TableObj {
pub(crate) id: ObjectId,
pub(crate) table: Table,
pub(crate) metatable: Option<Handle<TableObj>>,
pub(crate) finalize: bool,
}
#[derive(Clone, Debug)]
pub(crate) struct FieldHints {
pub(crate) name: std::cell::Cell<u32>,
pub(crate) index: std::cell::Cell<u32>,
}
#[derive(Clone, Debug)]
pub(crate) struct Proto {
pub(crate) id: ObjectId,
pub(crate) ops: Vec<Op>,
pub(crate) field_hints: Box<[FieldHints]>,
pub(crate) byte_consts: Vec<Vec<u8>>,
pub(crate) byte_hashes: Vec<u64>,
pub(crate) const_strings: Vec<Handle<StringObj>>,
pub(crate) captures: Vec<Capture>,
pub(crate) children: Vec<Handle<Proto>>,
pub(crate) max_reg: u8,
pub(crate) params: u8,
pub(crate) vararg: bool,
pub(crate) debug: Option<Box<crate::debuginfo::DebugInfo>>,
pub(crate) source: Option<Handle<StringObj>>,
}
impl Proto {
pub(crate) fn empty_field_hints(ops: &[Op]) -> Box<[FieldHints]> {
if ops
.iter()
.any(|op| matches!(op, Op::GetField { .. } | Op::SetField { .. }))
{
vec![
FieldHints {
name: std::cell::Cell::new(u32::MAX),
index: std::cell::Cell::new(u32::MAX),
};
ops.len()
]
.into_boxed_slice()
} else {
Box::default()
}
}
}
#[derive(Clone, Debug)]
pub(crate) enum UpvalueState {
Open {
thread: Handle<ThreadObj>,
slot: u32,
},
Closed(Value),
}
#[derive(Clone, Debug)]
pub(crate) struct UpvalueObj {
pub(crate) id: ObjectId,
pub(crate) state: UpvalueState,
}
#[derive(Clone, Debug)]
pub(crate) struct ClosureObj {
pub(crate) id: ObjectId,
pub(crate) proto: Handle<Proto>,
pub(crate) upvalues: Vec<Handle<UpvalueObj>>,
}
#[derive(Clone, Debug)]
pub(crate) struct NativeClosureObj {
pub(crate) id: ObjectId,
pub(crate) native: u32,
pub(crate) values: Vec<Value>,
pub(crate) state: Vec<i64>,
}
#[derive(Clone, Default)]
pub(crate) struct Stack {
pub(crate) values: Vec<Value>,
pub(crate) len: usize,
}
impl Stack {
#[inline(always)]
pub(crate) fn len(&self) -> usize {
self.len
}
#[inline(always)]
pub(crate) fn get(&self, index: usize) -> Option<&Value> {
if index < self.len {
self.values.get(index)
} else {
None
}
}
#[inline(always)]
pub(crate) fn get_mut(&mut self, index: usize) -> Option<&mut Value> {
if index < self.len {
self.values.get_mut(index)
} else {
None
}
}
#[inline(always)]
pub(crate) fn truncate(&mut self, len: usize) {
self.len = self.len.min(len);
}
#[inline(always)]
pub(crate) fn grow_to(&mut self, len: usize) -> bool {
if len <= self.len {
return false;
}
if len > self.values.len() {
self.grow_physical(len);
return true;
}
self.values[self.len..len].fill(Value::Nil);
self.len = len;
false
}
#[cold]
#[inline(never)]
fn grow_physical(&mut self, len: usize) {
self.values[self.len..].fill(Value::Nil);
grow_values(&mut self.values, len);
self.len = len;
}
pub(crate) fn clear(&mut self) {
self.len = 0;
}
pub(crate) fn extend_from_slice(&mut self, values: &[Value]) -> bool {
let old = self.len;
let grew = self.grow_to(old + values.len());
self.values[old..self.len].copy_from_slice(values);
grew
}
pub(crate) fn as_slice(&self) -> &[Value] {
self
}
#[cfg(test)]
pub(crate) fn physical_len(&self) -> usize {
self.values.len()
}
}
#[cold]
#[inline(never)]
pub(crate) fn grow_values(values: &mut Vec<Value>, len: usize) {
values.resize(len, Value::Nil);
}
impl From<Vec<Value>> for Stack {
fn from(values: Vec<Value>) -> Self {
let len = values.len();
Self { values, len }
}
}
impl std::ops::Deref for Stack {
type Target = [Value];
#[inline(always)]
fn deref(&self) -> &[Value] {
&self.values[..self.len]
}
}
impl std::ops::DerefMut for Stack {
#[inline(always)]
fn deref_mut(&mut self) -> &mut [Value] {
&mut self.values[..self.len]
}
}
impl<'a> IntoIterator for &'a Stack {
type Item = &'a Value;
type IntoIter = std::slice::Iter<'a, Value>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl std::fmt::Debug for Stack {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
#[derive(Clone, Default)]
pub(crate) struct Frames {
pub(crate) slots: Vec<Frame>,
pub(crate) depth: usize,
}
impl Frames {
#[inline(always)]
pub(crate) fn len(&self) -> usize {
self.depth
}
#[inline(always)]
pub(crate) fn is_empty(&self) -> bool {
self.depth == 0
}
#[inline(always)]
pub(crate) fn last(&self) -> Option<&Frame> {
self.slots.get(self.depth.wrapping_sub(1))
}
#[inline(always)]
pub(crate) fn last_mut(&mut self) -> Option<&mut Frame> {
self.slots.get_mut(self.depth.wrapping_sub(1))
}
#[inline(always)]
pub(crate) fn get(&self, index: usize) -> Option<&Frame> {
if index < self.depth {
self.slots.get(index)
} else {
None
}
}
#[inline(always)]
pub(crate) fn push(&mut self, frame: Frame) -> bool {
let depth = self.depth;
self.depth = depth + 1;
if let Some(slot) = self.slots.get_mut(depth) {
debug_assert!(slot.cold.is_none());
*slot = frame;
false
} else {
self.slots.push(frame);
true
}
}
#[inline(always)]
pub(crate) fn push_hot(
&mut self,
closure: Handle<ClosureObj>,
base: u32,
limit: u32,
nresults: u8,
) -> bool {
let depth = self.depth;
if let Some(slot) = self.slots.get_mut(depth) {
debug_assert!(slot.cold.is_none());
slot.closure = closure;
slot.pc = 0;
slot.base = base;
slot.limit = limit;
slot.vararg_len = 0;
slot.nresults = nresults;
slot.flags = 0;
self.depth = depth + 1;
false
} else {
self.push_physical(Frame {
closure,
pc: 0,
base,
limit,
vararg_len: 0,
nresults,
flags: 0,
cold: None,
});
true
}
}
#[cold]
#[inline(never)]
fn push_physical(&mut self, frame: Frame) {
self.slots.push(frame);
self.depth = self.slots.len();
}
pub(crate) fn pop(&mut self) -> Option<Frame> {
let depth = self.depth.checked_sub(1)?;
self.depth = depth;
let slot = &mut self.slots[depth];
Some(Frame {
cold: slot.cold.take(),
..*slot
})
}
#[inline(always)]
pub(crate) fn pop_hot(&mut self) {
let depth = self.depth - 1;
self.depth = depth;
let slot = &mut self.slots[depth];
if slot.cold.is_some() {
slot.cold = None;
}
}
pub(crate) fn truncate(&mut self, depth: usize) {
if depth < self.depth {
for slot in &mut self.slots[depth..self.depth] {
slot.cold = None;
}
self.depth = depth;
}
}
pub(crate) fn clear(&mut self) {
self.truncate(0);
}
pub(crate) fn as_mut_slice(&mut self) -> &mut [Frame] {
self
}
#[cfg(test)]
pub(crate) fn physical_len(&self) -> usize {
self.slots.len()
}
pub(crate) fn stale_slots_hold_no_cold(&self) -> bool {
self.slots[self.depth..]
.iter()
.all(|slot| slot.cold.is_none())
}
}
impl From<Vec<Frame>> for Frames {
fn from(slots: Vec<Frame>) -> Self {
let depth = slots.len();
Self { slots, depth }
}
}
impl std::ops::Deref for Frames {
type Target = [Frame];
#[inline(always)]
fn deref(&self) -> &[Frame] {
&self.slots[..self.depth]
}
}
impl std::ops::DerefMut for Frames {
#[inline(always)]
fn deref_mut(&mut self) -> &mut [Frame] {
&mut self.slots[..self.depth]
}
}
impl<'a> IntoIterator for &'a Frames {
type Item = &'a Frame;
type IntoIter = std::slice::Iter<'a, Frame>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl std::fmt::Debug for Frames {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
#[inline(always)]
pub(crate) fn charge_slots_to(charged_slots: &mut u32, len: usize, gc: &mut GcState) -> bool {
let len = u32::try_from(len).unwrap_or(u32::MAX);
if len > *charged_slots {
gc.charge(cost::STACK_SLOT * u64::from(len - *charged_slots));
*charged_slots = len;
return true;
}
false
}
#[derive(Clone, Debug)]
pub(crate) struct ThreadObj {
pub(crate) id: ObjectId,
pub(crate) status: Status,
pub(crate) stack: Stack,
pub(crate) top: u32,
pub(crate) frames: Frames,
pub(crate) open_upvalues: Vec<(u32, Handle<UpvalueObj>)>,
pub(crate) open_above: u32,
pub(crate) resumed_by: Option<Handle<ThreadObj>>,
pub(crate) host_results: Vec<Value>,
pub(crate) unwind: Option<Box<Unwind>>,
pub(crate) error: Option<(crate::id::LuaFault, Value)>,
pub(crate) coroutine: bool,
pub(crate) closing: bool,
pub(crate) tbc: Vec<u32>,
pub(crate) charged_slots: u32,
pub(crate) charged_held: u64,
}
impl ThreadObj {
#[inline]
pub(crate) fn push_open(&mut self, slot: u32, upvalue: Handle<UpvalueObj>) {
self.open_upvalues.push((slot, upvalue));
self.open_above = self.open_above.max(slot + 1);
}
pub(crate) fn close_open_from(&mut self, min_slot: u32) {
self.open_upvalues.retain(|(slot, _)| *slot < min_slot);
self.open_above = self
.open_upvalues
.iter()
.map(|(slot, _)| slot + 1)
.max()
.unwrap_or(0);
}
pub(crate) fn charge_slots(&mut self, len: usize, gc: &mut GcState) {
charge_slots_to(&mut self.charged_slots, len, gc);
}
pub(crate) fn extent(&self) -> u32 {
let stack = u32::try_from(self.stack.len()).unwrap_or(u32::MAX);
self.frames
.iter()
.map(|frame| frame.limit)
.fold(stack, u32::max)
}
pub(crate) fn held_bytes(&self) -> u64 {
self.frames
.iter()
.map(|frame| {
let task = match frame.boundary() {
Some(Boundary::Builtin { task, .. }) => task.held_bytes() as u64,
_ => 0,
};
task + frame.wait_request().map_or(0, |wait| {
wait.operation.len() as u64 + cost::STACK_SLOT * wait.payload.len() as u64
})
})
.sum()
}
}
#[derive(Debug)]
pub(crate) struct UserdataObj {
pub(crate) id: ObjectId,
pub(crate) metatable: Option<Handle<TableObj>>,
pub(crate) user_values: Box<[Value]>,
pub(crate) payload: crate::userdata::Payload,
pub(crate) charge: u64,
pub(crate) finalize: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum FinRef {
Table(Handle<TableObj>),
Userdata(Handle<UserdataObj>),
}
impl FinRef {
pub(crate) fn value(self) -> Value {
match self {
Self::Table(handle) => Value::Table(handle),
Self::Userdata(handle) => Value::Userdata(handle),
}
}
pub(crate) fn trace(self) -> TraceRef {
match self {
Self::Table(handle) => TraceRef {
kind: Kind::Table,
index: handle.index,
},
Self::Userdata(handle) => TraceRef {
kind: Kind::Userdata,
index: handle.index,
},
}
}
}
#[derive(Clone, Debug, Default)]
pub(crate) struct Finalizers {
pub(crate) registered: Vec<FinRef>,
pub(crate) old_until: u32,
pub(crate) new_from: u32,
pub(crate) pending: std::collections::VecDeque<FinRef>,
pub(crate) running: bool,
pub(crate) closing: bool,
pub(crate) closed: Option<Status>,
pub(crate) close_closure: Option<Handle<ClosureObj>>,
pub(crate) exit: Option<ExitState>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum ExitPhase {
Scopes = 1,
Finalizers = 2,
Terminal = 3,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct ExitState {
pub(crate) status: crate::ExitStatus,
pub(crate) close: bool,
pub(crate) phase: ExitPhase,
}
pub(crate) trait LogicalSize: Identified {
fn logical_size(&self) -> u64;
}
pub(crate) trait Identified {
fn object_id(&self) -> ObjectId;
#[cfg(feature = "counters")]
fn allocation_bytes(&self) -> u64;
}
macro_rules! identified {
($($ty:ty),*) => {
$(impl Identified for $ty {
#[cfg(feature = "counters")]
fn allocation_bytes(&self) -> u64 { self.logical_size() }
fn object_id(&self) -> ObjectId {
self.id
}
})*
};
}
identified!(
StringObj,
TableObj,
Proto,
UpvalueObj,
ClosureObj,
ThreadObj,
NativeClosureObj,
UserdataObj
);
impl LogicalSize for StringObj {
fn logical_size(&self) -> u64 {
cost::OBJECT + self.bytes.len() as u64
}
}
impl LogicalSize for TableObj {
fn logical_size(&self) -> u64 {
cost::OBJECT + cost::ENTRY * self.table.slot_len() as u64
}
}
impl LogicalSize for Proto {
fn logical_size(&self) -> u64 {
let refs =
self.ops.len() + self.byte_consts.len() + self.captures.len() + self.children.len();
cost::OBJECT
+ cost::REF * refs as u64
+ self.debug.as_ref().map_or(0, |debug| debug.logical_size())
}
}
impl LogicalSize for UpvalueObj {
fn logical_size(&self) -> u64 {
cost::OBJECT
}
}
impl LogicalSize for ClosureObj {
fn logical_size(&self) -> u64 {
cost::OBJECT + cost::REF * self.upvalues.len() as u64
}
}
impl LogicalSize for ThreadObj {
fn logical_size(&self) -> u64 {
cost::THREAD + cost::STACK_SLOT * u64::from(self.charged_slots) + self.charged_held
}
}
impl LogicalSize for NativeClosureObj {
fn logical_size(&self) -> u64 {
native_closure_cost(self.values.len(), self.state.len())
}
}
impl LogicalSize for UserdataObj {
fn logical_size(&self) -> u64 {
userdata_cost(self.user_values.len(), self.charge)
}
}
pub(crate) mod mark {
pub(crate) const WHITE0: u8 = 0;
pub(crate) const GRAY: u8 = 2;
pub(crate) const BLACK: u8 = 3;
pub(crate) const FREE: u8 = 4;
#[inline]
pub(crate) fn is_white(mark: u8) -> bool {
mark < GRAY
}
}
pub(crate) mod age {
pub(crate) const NEW: u8 = 0;
pub(crate) const SURVIVAL: u8 = 1;
pub(crate) const OLD1: u8 = 3;
pub(crate) const OLD: u8 = 4;
pub(crate) const TOUCHED1: u8 = 5;
pub(crate) const TOUCHED2: u8 = 6;
#[inline]
pub(crate) fn is_old(age: u8) -> bool {
age > SURVIVAL
}
pub(crate) fn valid(age: u8) -> bool {
matches!(age, NEW | SURVIVAL | OLD1 | OLD | TOUCHED1 | TOUCHED2)
}
}
struct Slot<T> {
generation: u32,
retired: bool,
value: Option<T>,
}
pub(crate) struct Arena<T> {
slots: Vec<Slot<T>>,
marks: Vec<u8>,
ages: Vec<u8>,
free: Vec<u32>,
live: u32,
marked: u32,
dead: u32,
barrier: bool,
strict: bool,
alloc_mark: u8,
again: Vec<u32>,
queued: Vec<u64>,
by_id: std::cell::RefCell<Option<std::collections::HashMap<ObjectId, u32>>>,
young: Vec<u32>,
generational: bool,
_ty: PhantomData<fn() -> T>,
}
impl<T> Arena<T> {
fn new() -> Self {
Self {
slots: Vec::new(),
marks: Vec::new(),
ages: Vec::new(),
free: Vec::new(),
live: 0,
marked: 0,
dead: 0,
barrier: false,
strict: false,
alloc_mark: mark::WHITE0,
again: Vec::new(),
queued: Vec::new(),
by_id: std::cell::RefCell::new(None),
young: Vec::new(),
generational: false,
_ty: PhantomData,
}
}
pub(crate) fn live(&self) -> u32 {
self.live - self.dead
}
pub(crate) fn physical(&self) -> u32 {
self.live
}
pub(crate) fn alloc(&mut self, value: T) -> Result<Handle<T>, TerminationReason>
where
T: Identified,
{
if self.live() >= OBJECTS_CEILING {
return Err(TerminationReason::MemoryLimit);
}
let id = value.object_id();
let mark = self.alloc_mark;
let index = if let Some(index) = self.free.pop() {
let slot = &mut self.slots[index as usize];
debug_assert!(slot.value.is_none() && !slot.retired);
slot.value = Some(value);
index
} else {
if self.slots.len() >= 2 * OBJECTS_CEILING as usize {
return Err(TerminationReason::MemoryLimit);
}
self.slots.push(Slot {
generation: 1,
retired: false,
value: Some(value),
});
self.marks.push(mark::FREE);
self.ages.push(age::NEW);
(self.slots.len() - 1) as u32
};
self.marks[index as usize] = mark;
self.ages[index as usize] = age::NEW;
if let Some(by_id) = self.by_id.get_mut() {
by_id.insert(id, index);
}
if self.generational {
self.young.push(index);
}
self.live += 1;
if !mark::is_white(mark) {
self.marked += 1;
if mark == mark::GRAY {
self.push_again(index);
}
}
#[cfg(feature = "counters")]
crate::counters::allocated(
std::any::type_name::<T>(),
self.slots[index as usize]
.value
.as_ref()
.expect("allocated")
.allocation_bytes(),
);
Ok(Handle::new(index, self.slots[index as usize].generation))
}
pub(crate) fn get(&self, handle: Handle<T>) -> Option<&T> {
let slot = self.slots.get(handle.index as usize)?;
if slot.generation != handle.generation {
return None;
}
slot.value.as_ref()
}
#[inline]
pub(crate) fn get_mut(&mut self, handle: Handle<T>) -> Option<&mut T> {
self.get_mut_storing(handle, true)
}
#[inline]
pub(crate) fn get_mut_storing(
&mut self,
handle: Handle<T>,
references: bool,
) -> Option<&mut T> {
let index = handle.index as usize;
if self.slots.get(index)?.generation != handle.generation {
return None;
}
if self.barrier && (references || self.strict) && self.marks[index] == mark::BLACK {
self.touch(handle.index);
}
self.slots[index].value.as_mut()
}
#[cold]
#[inline(never)]
fn touch(&mut self, index: u32) {
self.marks[index as usize] = mark::GRAY;
queue(&mut self.queued, &mut self.again, index);
let age = &mut self.ages[index as usize];
if age::is_old(*age) {
*age = age::TOUCHED1;
}
}
pub(crate) fn free(&mut self, index: u32) -> u64
where
T: LogicalSize,
{
let dead = self.dead_mark();
let Some(slot) = self.slots.get_mut(index as usize) else {
return 0;
};
let Some(value) = slot.value.take() else {
return 0;
};
let size = value.logical_size();
if let Some(by_id) = self.by_id.get_mut() {
by_id.remove(&value.object_id());
}
drop(value);
self.live = self.live.saturating_sub(1);
let mark = std::mem::replace(&mut self.marks[index as usize], mark::FREE);
if !mark::is_white(mark) {
self.marked = self.marked.saturating_sub(1);
} else if Some(mark) == dead {
self.dead = self.dead.saturating_sub(1);
}
if slot.generation == u32::MAX {
slot.retired = true;
return size;
}
slot.generation += 1;
self.free.push(index);
size
}
pub(crate) fn physical_bytes(&self) -> u64
where
T: LogicalSize,
{
self.slots
.iter()
.filter_map(|slot| slot.value.as_ref())
.map(LogicalSize::logical_size)
.sum()
}
fn dead_mark(&self) -> Option<u8> {
(self.dead > 0).then_some(self.alloc_mark ^ 1)
}
#[inline]
pub(crate) fn find_id_hint(&self, id: ObjectId, hint: Handle<T>) -> Option<Handle<T>>
where
T: Identified,
{
if self.get(hint).is_some_and(|value| value.object_id() == id)
&& self.dead_mark() != Some(self.marks[hint.index as usize])
{
return Some(hint);
}
self.find_id(id)
.map(|(index, generation)| Handle::new(index, generation))
}
pub(crate) fn find_id(&self, id: ObjectId) -> Option<(u32, u32)>
where
T: Identified,
{
let mut by_id = self.by_id.borrow_mut();
let index = *by_id
.get_or_insert_with(|| {
self.slots
.iter()
.enumerate()
.filter_map(|(index, slot)| {
slot.value
.as_ref()
.map(|value| (value.object_id(), index as u32))
})
.collect()
})
.get(&id)?;
let slot = &self.slots[index as usize];
let value = slot.value.as_ref()?;
(value.object_id() == id && self.dead_mark() != Some(self.marks[index as usize]))
.then_some((index, slot.generation))
}
pub(crate) fn iter(&self) -> impl Iterator<Item = (u32, u32, &T)> {
let dead = self.dead_mark();
self.slots
.iter()
.zip(&self.marks)
.enumerate()
.filter_map(move |(index, (slot, mark))| {
if dead == Some(*mark) {
return None;
}
slot.value
.as_ref()
.map(|value| (index as u32, slot.generation, value))
})
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn slot_count(&self) -> usize {
self.slots.len()
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn slot_is_occupied(&self, index: u32) -> bool {
self.slots
.get(index as usize)
.and_then(|slot| slot.value.as_ref())
.is_some()
}
pub(crate) fn slot_value(&self, index: u32) -> Option<&T> {
self.slots
.get(index as usize)
.and_then(|slot| slot.value.as_ref())
}
pub(crate) fn raw_mut(&mut self, index: u32) -> Option<&mut T> {
self.slots
.get_mut(index as usize)
.and_then(|slot| slot.value.as_mut())
}
#[inline]
pub(crate) fn mark_of(&self, index: u32) -> Option<u8> {
self.marks
.get(index as usize)
.copied()
.filter(|mark| *mark != mark::FREE)
}
#[inline]
pub(crate) fn set_mark(&mut self, index: u32, to: u8) {
let Some(mark) = self.marks.get_mut(index as usize) else {
return;
};
if *mark == mark::FREE {
return;
}
match (mark::is_white(*mark), mark::is_white(to)) {
(true, false) => self.marked += 1,
(false, true) => self.marked -= 1,
_ => {}
}
*mark = to;
}
#[inline]
pub(crate) fn mark_white(&mut self, index: u32, to: u8) -> bool {
match self.marks.get_mut(index as usize) {
Some(mark) if mark::is_white(*mark) => {
*mark = to;
self.marked += 1;
true
}
_ => false,
}
}
pub(crate) fn marked(&self) -> u32 {
self.marked
}
pub(crate) fn set_policy(&mut self, barrier: bool, strict: bool, alloc_mark: u8) {
self.barrier = barrier;
self.strict = strict;
self.alloc_mark = alloc_mark;
}
pub(crate) fn condemn(&mut self) {
self.dead = self.live - self.marked;
}
pub(crate) fn clear_dead(&mut self) {
self.dead = 0;
}
pub(crate) fn sweep_some(
&mut self,
from: &mut u32,
white: u8,
limit: u64,
resets: bool,
freed: &mut u64,
) -> u64
where
T: LogicalSize,
{
let mut passed = 0;
while passed < limit {
let Some(&mark) = self.marks.get(*from as usize) else {
break;
};
let index = *from;
*from += 1;
if resets {
self.ages[index as usize] = age::NEW;
}
if mark == mark::FREE || mark == white {
continue;
}
if mark::is_white(mark) {
*freed = freed.saturating_add(self.free(index));
} else {
self.marks[index as usize] = white;
self.marked -= 1;
}
passed += 1;
}
passed
}
pub(crate) fn sweep_old_some(
&mut self,
from: &mut u32,
white: u8,
limit: u64,
freed: &mut u64,
) -> u64
where
T: LogicalSize,
{
let mut passed = 0;
while passed < limit {
let Some(&mark) = self.marks.get(*from as usize) else {
break;
};
let index = *from;
*from += 1;
if mark == mark::FREE || mark == white || self.ages[index as usize] != age::NEW {
continue;
}
if mark::is_white(mark) {
*freed = freed.saturating_add(self.free(index));
} else {
self.ages[index as usize] = if mark == mark::GRAY {
age::TOUCHED1
} else {
age::OLD
};
}
passed += 1;
}
passed
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn sweep_young_some(
&mut self,
pos: &mut u32,
white: u8,
limit: u64,
references: bool,
freed: &mut u64,
promoted: &mut u64,
revisit: &mut Vec<u32>,
) -> u64
where
T: LogicalSize,
{
let mut passed = 0;
while passed < limit {
let Some(&index) = self.young.get(*pos as usize) else {
break;
};
let at = *pos as usize;
*pos += 1;
if index == crate::gc::TOMB {
continue;
}
let Some(&found) = self.marks.get(index as usize) else {
self.young[at] = crate::gc::TOMB;
continue;
};
if found == mark::FREE {
self.young[at] = crate::gc::TOMB;
continue;
}
if found == white {
continue;
}
passed += 1;
if mark::is_white(found) {
*freed = freed.saturating_add(self.free(index));
self.young[at] = crate::gc::TOMB;
continue;
}
let age = &mut self.ages[index as usize];
match *age {
age::NEW => {
*age = age::SURVIVAL;
self.marks[index as usize] = white;
self.marked -= 1;
}
age::SURVIVAL => {
self.young[at] = crate::gc::TOMB;
*promoted += 1;
if !references {
*age = age::OLD;
} else if found == mark::BLACK {
*age = age::OLD1;
revisit.push(index);
} else {
*age = age::TOUCHED1;
}
}
_ => self.young[at] = crate::gc::TOMB,
}
}
passed
}
#[inline]
pub(crate) fn age_of(&self, index: u32) -> u8 {
self.ages.get(index as usize).copied().unwrap_or(age::NEW)
}
#[inline]
pub(crate) fn set_age(&mut self, index: u32, to: u8) {
if let Some(age) = self.ages.get_mut(index as usize) {
*age = to;
}
}
pub(crate) fn set_gen(&mut self, on: bool) {
self.generational = on;
}
pub(crate) fn young(&self) -> &[u32] {
&self.young
}
pub(crate) fn young_mut(&mut self) -> &mut Vec<u32> {
&mut self.young
}
pub(crate) fn clear_again(&mut self) {
for index in std::mem::take(&mut self.again) {
self.queued[(index / 64) as usize] &= !(1u64 << (index % 64));
}
}
pub(crate) fn pop_again(&mut self) -> Option<u32> {
let index = self.again.pop()?;
self.queued[(index / 64) as usize] &= !(1u64 << (index % 64));
Some(index)
}
pub(crate) fn again(&self) -> &[u32] {
&self.again
}
pub(crate) fn push_again(&mut self, index: u32) {
queue(&mut self.queued, &mut self.again, index);
}
#[cfg(test)]
pub(crate) fn force_barrier(&mut self, on: bool) {
self.barrier = on;
}
#[cfg(test)]
pub(crate) fn force_generation_max(&mut self, index: u32) {
if let Some(slot) = self.slots.get_mut(index as usize) {
slot.generation = u32::MAX;
}
}
}
#[inline]
fn queue(queued: &mut Vec<u64>, again: &mut Vec<u32>, index: u32) {
let (word, bit) = ((index / 64) as usize, 1u64 << (index % 64));
if queued.len() <= word {
queued.resize(word + 1, 0);
}
if queued[word] & bit == 0 {
queued[word] |= bit;
again.push(index);
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(crate) struct TraceRef {
pub(crate) kind: Kind,
pub(crate) index: u32,
}
pub(crate) struct HostRoot {
pub(crate) kind: Kind,
pub(crate) index: u32,
pub(crate) generation: u32,
pub(crate) id: ObjectId,
}
macro_rules! on_arena {
($heap:expr, $kind:expr, $arena:ident => $body:expr) => {
match $kind {
Kind::String => {
let $arena = &$heap.strings;
$body
}
Kind::Table => {
let $arena = &$heap.tables;
$body
}
Kind::Proto => {
let $arena = &$heap.protos;
$body
}
Kind::Upvalue => {
let $arena = &$heap.upvalues;
$body
}
Kind::Closure => {
let $arena = &$heap.closures;
$body
}
Kind::Thread => {
let $arena = &$heap.threads;
$body
}
Kind::NativeClosure => {
let $arena = &$heap.native_closures;
$body
}
Kind::Userdata => {
let $arena = &$heap.userdata;
$body
}
}
};
(mut $heap:expr, $kind:expr, $arena:ident => $body:expr) => {
match $kind {
Kind::String => {
let $arena = &mut $heap.strings;
$body
}
Kind::Table => {
let $arena = &mut $heap.tables;
$body
}
Kind::Proto => {
let $arena = &mut $heap.protos;
$body
}
Kind::Upvalue => {
let $arena = &mut $heap.upvalues;
$body
}
Kind::Closure => {
let $arena = &mut $heap.closures;
$body
}
Kind::Thread => {
let $arena = &mut $heap.threads;
$body
}
Kind::NativeClosure => {
let $arena = &mut $heap.native_closures;
$body
}
Kind::Userdata => {
let $arena = &mut $heap.userdata;
$body
}
}
};
}
pub(crate) use on_arena;
pub(crate) struct Heap {
pub(crate) strings: Arena<StringObj>,
pub(crate) tables: Arena<TableObj>,
pub(crate) event_hints: [std::cell::Cell<u32>; 32],
pub(crate) protos: Arena<Proto>,
pub(crate) upvalues: Arena<UpvalueObj>,
pub(crate) closures: Arena<ClosureObj>,
pub(crate) threads: Arena<ThreadObj>,
pub(crate) hooks: crate::runtime::hooks::ThreadHooks,
pub(crate) native_closures: Arena<NativeClosureObj>,
pub(crate) userdata: Arena<UserdataObj>,
pub(crate) host_roots: Vec<HostRoot>,
pub(crate) api_roots: Option<std::rc::Rc<std::cell::RefCell<crate::api::roots::RootTable>>>,
pub(crate) next_object_id: u64,
pub(crate) globals: Option<Handle<TableObj>>,
pub(crate) registry: Option<Handle<TableObj>>,
pub(crate) natives: Vec<String>,
pub(crate) active: Option<Handle<ThreadObj>>,
pub(crate) entry: Option<Handle<ThreadObj>>,
pub(crate) working: Option<u32>,
pub(crate) gc: GcState,
pub(crate) library: crate::library::LibraryState,
pub(crate) type_metatables: [Option<Handle<TableObj>>; BASIC_TYPES],
pub(crate) finalizers: Finalizers,
pub(crate) collector: crate::gc::Collector,
pub(crate) reserved: Vec<Handle<StringObj>>,
pub(crate) max_string: usize,
}
impl Heap {
pub(crate) fn new() -> Self {
Self {
strings: Arena::new(),
tables: Arena::new(),
event_hints: std::array::from_fn(|_| std::cell::Cell::new(u32::MAX)),
protos: Arena::new(),
upvalues: Arena::new(),
closures: Arena::new(),
threads: Arena::new(),
hooks: Default::default(),
native_closures: Arena::new(),
userdata: Arena::new(),
host_roots: Vec::new(),
api_roots: None,
next_object_id: 1,
globals: None,
registry: None,
natives: Vec::new(),
active: None,
entry: None,
working: None,
gc: GcState::new(true, GC_MIN_DEBT, MAX_OBJECTS, MAX_LOGICAL_HEAP),
library: crate::library::LibraryState::new(0),
type_metatables: [None; BASIC_TYPES],
finalizers: Finalizers::default(),
collector: crate::gc::Collector::default(),
reserved: Vec::new(),
max_string: MAX_STRING_BYTES,
}
}
pub(crate) fn mark_of(&self, object: TraceRef) -> Option<u8> {
let index = object.index;
match object.kind {
Kind::String => self.strings.mark_of(index),
Kind::Table => self.tables.mark_of(index),
Kind::Proto => self.protos.mark_of(index),
Kind::Upvalue => self.upvalues.mark_of(index),
Kind::Closure => self.closures.mark_of(index),
Kind::Thread => self.threads.mark_of(index),
Kind::NativeClosure => self.native_closures.mark_of(index),
Kind::Userdata => self.userdata.mark_of(index),
}
}
pub(crate) fn set_mark(&mut self, object: TraceRef, to: u8) {
let index = object.index;
match object.kind {
Kind::String => self.strings.set_mark(index, to),
Kind::Table => self.tables.set_mark(index, to),
Kind::Proto => self.protos.set_mark(index, to),
Kind::Upvalue => self.upvalues.set_mark(index, to),
Kind::Closure => self.closures.set_mark(index, to),
Kind::Thread => self.threads.set_mark(index, to),
Kind::NativeClosure => self.native_closures.set_mark(index, to),
Kind::Userdata => self.userdata.set_mark(index, to),
}
}
pub(crate) fn age_of(&self, object: TraceRef) -> u8 {
on_arena!(self, object.kind, arena => arena.age_of(object.index))
}
pub(crate) fn set_age(&mut self, object: TraceRef, to: u8) {
on_arena!(mut self, object.kind, arena => arena.set_age(object.index, to))
}
#[cfg(test)]
pub(crate) fn force_barriers(&mut self, on: bool) {
self.strings.force_barrier(on);
self.tables.force_barrier(on);
self.protos.force_barrier(on);
self.upvalues.force_barrier(on);
self.closures.force_barrier(on);
self.threads.force_barrier(on);
self.native_closures.force_barrier(on);
self.userdata.force_barrier(on);
}
pub(crate) fn id_of(&self, object: TraceRef) -> Option<ObjectId> {
let index = object.index;
Some(match object.kind {
Kind::String => self.strings.slot_value(index)?.id,
Kind::Table => self.tables.slot_value(index)?.id,
Kind::Proto => self.protos.slot_value(index)?.id,
Kind::Upvalue => self.upvalues.slot_value(index)?.id,
Kind::Closure => self.closures.slot_value(index)?.id,
Kind::Thread => self.threads.slot_value(index)?.id,
Kind::NativeClosure => self.native_closures.slot_value(index)?.id,
Kind::Userdata => self.userdata.slot_value(index)?.id,
})
}
pub(crate) fn physical_objects(&self) -> u32 {
self.strings.physical()
+ self.tables.physical()
+ self.protos.physical()
+ self.upvalues.physical()
+ self.closures.physical()
+ self.threads.physical()
+ self.native_closures.physical()
+ self.userdata.physical()
}
pub(crate) fn live_objects(&self) -> u32 {
self.strings.live()
+ self.tables.live()
+ self.protos.live()
+ self.upvalues.live()
+ self.closures.live()
+ self.threads.live()
+ self.native_closures.live()
+ self.userdata.live()
}
pub(crate) fn alloc_id(&mut self) -> Result<ObjectId, TerminationReason> {
let raw = self.next_object_id;
self.next_object_id = self
.next_object_id
.checked_add(1)
.ok_or(TerminationReason::ObjectIdExhausted)?;
Ok(ObjectId(raw))
}
pub(crate) fn alloc_string(
&mut self,
bytes: Vec<u8>,
) -> Result<Handle<StringObj>, TerminationReason> {
let charge = cost::OBJECT + bytes.len() as u64;
if bytes.len() > self.max_string || !self.gc.fits(charge) {
return Err(TerminationReason::MemoryLimit);
}
let id = self.alloc_id()?;
let handle = self.strings.alloc(StringObj {
id,
bytes: crate::table::KeyString::new(bytes),
})?;
self.gc.charge(charge);
Ok(handle)
}
pub(crate) fn alloc_table(&mut self) -> Result<Handle<TableObj>, TerminationReason> {
if !self.gc.fits(cost::OBJECT) {
return Err(TerminationReason::MemoryLimit);
}
let id = self.alloc_id()?;
let handle = self.tables.alloc(TableObj {
id,
table: Table::new(),
metatable: None,
finalize: false,
})?;
self.gc.charge(cost::OBJECT);
Ok(handle)
}
#[inline]
pub(crate) fn metatable_of(&self, value: Value) -> Option<Handle<TableObj>> {
if let Value::Table(table) = value {
return self.tables.get(table)?.metatable;
}
self.other_metatable(value)
}
#[inline(never)]
fn other_metatable(&self, value: Value) -> Option<Handle<TableObj>> {
if let Value::Userdata(userdata) = value {
return self.userdata.get(userdata)?.metatable;
}
self.type_metatables[basic_type(value)]
}
pub(crate) fn set_metatable(
&mut self,
object: Value,
metatable: Option<Handle<TableObj>>,
) -> bool {
let finalizer = metatable.is_some_and(|metatable| {
self.tables.get(metatable).is_some_and(|table| {
!matches!(
table.table.get_view(crate::table::KeyView::string(b"__gc")),
None | Some(Value::Nil)
)
})
}) && !self.finalizers.closing;
let (registered, fin) = match object {
Value::Table(handle) => match self.tables.get_mut(handle) {
Some(table) => {
table.metatable = metatable;
(&mut table.finalize, FinRef::Table(handle))
}
None => return false,
},
Value::Userdata(handle) => match self.userdata.get_mut(handle) {
Some(userdata) => {
userdata.metatable = metatable;
(&mut userdata.finalize, FinRef::Userdata(handle))
}
None => return false,
},
_ => return false,
};
if finalizer && !*registered {
*registered = true;
self.finalizers.registered.push(fin);
}
true
}
pub(crate) fn unmark_finalize(&mut self, fin: FinRef) {
match fin {
FinRef::Table(handle) => {
if let Some(table) = self.tables.get_mut(handle) {
table.finalize = false;
}
}
FinRef::Userdata(handle) => {
if let Some(userdata) = self.userdata.get_mut(handle) {
userdata.finalize = false;
}
}
}
}
pub(crate) fn alloc_userdata(
&mut self,
max_objects: u32,
user_values: usize,
charge: u64,
make: impl FnOnce() -> crate::userdata::Payload,
) -> Result<Handle<UserdataObj>, TerminationReason> {
if user_values > crate::userdata::MAX_USER_VALUES
|| self.live_objects().saturating_add(1) > max_objects
{
return Err(TerminationReason::MemoryLimit);
}
let cost = userdata_cost(user_values, charge);
if !self.gc.fits(cost) {
return Err(TerminationReason::MemoryLimit);
}
let id = self.alloc_id()?;
let handle = self.userdata.alloc(UserdataObj {
id,
metatable: None,
user_values: vec![Value::Nil; user_values].into_boxed_slice(),
payload: make(),
charge,
finalize: false,
})?;
self.gc.charge(cost);
Ok(handle)
}
pub(crate) fn string_bytes(&self, handle: Handle<StringObj>) -> Option<&[u8]> {
self.strings
.get(handle)
.map(|object| object.bytes.as_slice())
}
pub(crate) fn object_id_of_value(&self, value: Value) -> Option<ObjectId> {
Some(match value {
Value::String(handle) => self.strings.get(handle)?.id,
Value::Table(handle) => self.tables.get(handle)?.id,
Value::Closure(handle) => self.closures.get(handle)?.id,
Value::Thread(handle) => self.threads.get(handle)?.id,
Value::NativeClosure(handle) => self.native_closures.get(handle)?.id,
Value::Userdata(handle) => self.userdata.get(handle)?.id,
_ => return None,
})
}
pub(crate) fn key_view(
&self,
value: Value,
) -> Result<crate::table::KeyView<'_>, crate::id::LuaFault> {
use crate::table::KeyView;
let bytes = if let Value::String(handle) = value {
let object = self.strings.get(handle).ok_or(crate::id::LuaFault::Type)?;
Some((object.bytes.as_slice(), object.hash()))
} else {
None
};
if let Some(view) = crate::table::value_view(value, bytes) {
return Ok(view);
}
match value {
Value::Nil => Err(crate::id::LuaFault::NilKey),
Value::Float(_) => Err(crate::id::LuaFault::NanKey),
_ => self
.object_id_of_value(value)
.map(KeyView::Object)
.ok_or(crate::id::LuaFault::Type),
}
}
pub(crate) fn table_get_view(
&self,
table: Handle<TableObj>,
key: crate::table::KeyView<'_>,
) -> Option<Value> {
Some(
self.tables
.get(table)?
.table
.get_view(key)
.unwrap_or(Value::Nil),
)
}
pub(crate) fn normalize_value(&self, value: Value) -> Result<TableKey, crate::id::LuaFault> {
if let Value::String(handle) = value {
let object = self.strings.get(handle).ok_or(crate::id::LuaFault::Type)?;
return Ok(TableKey::String(object.bytes.clone()));
}
let bytes = None;
let object_id = match value {
Value::Table(_)
| Value::Closure(_)
| Value::Thread(_)
| Value::NativeClosure(_)
| Value::Userdata(_) => Some(
self.object_id_of_value(value)
.ok_or(crate::id::LuaFault::Type)?,
),
_ => None,
};
crate::table::normalize_key(value, bytes, object_id)
}
pub(crate) fn table_get(&self, table: Handle<TableObj>, key: &TableKey) -> Option<Value> {
Some(self.tables.get(table)?.table.get(key))
}
pub(crate) fn update_string_key(
&mut self,
table: Handle<TableObj>,
key: Value,
value: Value,
) -> bool {
let Value::String(handle) = key else {
return false;
};
let Some(string) = self.strings.get(handle) else {
return false;
};
let view = crate::table::KeyView::cached_string(&string.bytes, string.hash());
let Some(object) = self.tables.get_mut_storing(table, true) else {
return false;
};
if matches!(value, Value::Nil) {
object.table.delete_view(view);
true
} else {
object.table.update_view(view, value)
}
}
pub(crate) fn table_insert(
&mut self,
table: Handle<TableObj>,
key: TableKey,
key_value: Value,
value: Value,
) -> Result<(), InsertError> {
let references =
crate::gc::value_ref(key_value).is_some() || crate::gc::value_ref(value).is_some();
let Some(object) = self.tables.get_mut_storing(table, references) else {
return Err(InsertError::NoTable);
};
if !matches!(value, Value::Nil)
&& !self.gc.fits(cost::ENTRY)
&& matches!(object.table.get(&key), Value::Nil)
{
return Err(InsertError::Memory);
}
let before = object.table.slot_len();
object.table.insert(key, key_value, value);
let after = object.table.slot_len();
self.gc
.charge(cost::ENTRY * after.saturating_sub(before) as u64);
if after < before {
self.give_back(cost::ENTRY * (before - after) as u64);
}
Ok(())
}
pub(crate) fn give_back(&mut self, amount: u64) {
self.gc.used = self.gc.used.saturating_sub(amount);
}
pub(crate) fn charge_held(&mut self, amount: u64) {
self.gc.charge(amount);
if let Some(thread) = self
.active
.and_then(|handle| self.threads.raw_mut(handle.index))
{
thread.charged_held = thread.charged_held.saturating_add(amount);
} else {
debug_assert!(false, "held bytes charged with no thread running");
}
}
pub(crate) fn find_by_id(&self, id: ObjectId) -> Option<(Kind, u32, u32)> {
let found = |kind: Kind, found: Option<(u32, u32)>| {
found.map(|(index, generation)| (kind, index, generation))
};
found(Kind::String, self.strings.find_id(id))
.or_else(|| found(Kind::Table, self.tables.find_id(id)))
.or_else(|| found(Kind::Proto, self.protos.find_id(id)))
.or_else(|| found(Kind::Upvalue, self.upvalues.find_id(id)))
.or_else(|| found(Kind::Closure, self.closures.find_id(id)))
.or_else(|| found(Kind::Thread, self.threads.find_id(id)))
.or_else(|| found(Kind::NativeClosure, self.native_closures.find_id(id)))
.or_else(|| found(Kind::Userdata, self.userdata.find_id(id)))
}
}
impl TableObj {
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn live_len(&self) -> usize {
self.table.live_len()
}
#[cfg(any(test, feature = "__measure"))]
pub(crate) fn dead_len(&self) -> usize {
self.table.dead_len()
}
}