luna_core/runtime/
string.rs

1//! Lua strings: immutable byte sequences allocated in one block (header +
2//! inline bytes). Short strings (≤ 40 bytes, PUC LUAI_MAXSHORTLEN) are
3//! interned in the heap's string table: equality is pointer equality. Long
4//! strings hash lazily, seeded per-heap (hash-flooding defense for hostile
5//! script workloads (script host)).
6
7use std::alloc::{Layout, alloc, dealloc, handle_alloc_error};
8use std::cell::Cell;
9use std::ptr;
10use std::slice;
11
12use crate::runtime::heap::{GcHeader, ObjTag};
13
14/// Strings up to this byte length are interned in the heap's string table;
15/// longer strings are heap-individual and hashed lazily.
16pub const MAX_SHORT_LEN: usize = 40;
17
18/// Lua string object — header plus inline byte payload. Byte-clean (Lua
19/// strings are arbitrary byte sequences, not necessarily UTF-8). Access the
20/// bytes via `Gc<LuaStr>::as_bytes`.
21#[repr(C)]
22pub struct LuaStr {
23    pub(crate) hdr: GcHeader,
24    /// string-table bucket chain (short strings only)
25    hnext: *mut LuaStr,
26    /// for long strings this holds the heap seed until the hash is computed
27    hash: Cell<u32>,
28    hashed: Cell<bool>,
29    short: bool,
30    len: u32,
31    // `len` bytes follow the struct
32}
33
34impl LuaStr {
35    /// Byte length of the string (not character count).
36    pub fn len(&self) -> usize {
37        self.len as usize
38    }
39
40    /// True when the string is zero bytes long.
41    pub fn is_empty(&self) -> bool {
42        self.len == 0
43    }
44
45    pub(crate) fn is_short(&self) -> bool {
46        self.short
47    }
48}
49
50/// Field offsets the JIT reads from a `LuaStr` in compiled code.
51pub mod jit_layout {
52    use super::LuaStr;
53
54    /// Byte offset of the `bool` that is true exactly for interned
55    /// (short) strings. Two distinct interned strings are unequal.
56    pub const STR_SHORT_OFFSET: usize = std::mem::offset_of!(LuaStr, short);
57}
58
59/// Inline-bytes access MUST go through a pointer carrying the provenance of
60/// the original allocation — a `&LuaStr` only covers the header, so deriving
61/// the tail from it is UB (caught by miri). `Gc` stores the allocation
62/// pointer, hence these live on `Gc<LuaStr>`.
63impl crate::runtime::heap::Gc<LuaStr> {
64    /// Borrow the underlying bytes of this Lua string.
65    pub fn as_bytes(&self) -> &[u8] {
66        // SAFETY: `self.as_ptr()` is the start of this `LuaStr`'s header which was allocated with the trailing bytes / hash fields in the same allocation by `StringTable::intern`.
67        unsafe { bytes_of(self.as_ptr()) }
68    }
69
70    /// Cached hash of the string (computed lazily for long strings).
71    pub fn hash(&self) -> u32 {
72        // SAFETY: `self.as_ptr()` is the start of this `LuaStr`'s header which was allocated with the trailing bytes / hash fields in the same allocation by `StringTable::intern`.
73        unsafe { hash_of(self.as_ptr()) }
74    }
75}
76
77/// SAFETY: `p` must point to a live string allocation (with its tail).
78pub(crate) unsafe fn bytes_of<'a>(p: *const LuaStr) -> &'a [u8] {
79    unsafe { slice::from_raw_parts(p.add(1) as *const u8, (*p).len as usize) }
80}
81
82/// SAFETY: as `bytes_of`.
83pub(crate) unsafe fn hash_of(p: *const LuaStr) -> u32 {
84    unsafe {
85        if !(*p).hashed.get() {
86            (*p).hash.set(lua_hash(bytes_of(p), (*p).hash.get()));
87            (*p).hashed.set(true);
88        }
89        (*p).hash.get()
90    }
91}
92
93/// PUC luaS_hash (all bytes, no step — post-5.3 flooding fix).
94pub(crate) fn lua_hash(bytes: &[u8], seed: u32) -> u32 {
95    let mut h = seed ^ bytes.len() as u32;
96    for &b in bytes {
97        h ^= h
98            .wrapping_shl(5)
99            .wrapping_add(h.wrapping_shr(2))
100            .wrapping_add(b as u32);
101    }
102    h
103}
104
105/// Longest string a `LuaStr` can describe (its length is a `u32`). Code
106/// that builds a string from script-controlled pieces checks against it.
107pub(crate) const MAX_LEN: usize = u32::MAX as usize;
108
109fn layout(len: usize) -> Layout {
110    Layout::new::<LuaStr>()
111        .extend(Layout::array::<u8>(len).expect("string size overflows layout"))
112        .expect("string size overflows layout")
113        .0
114        .pad_to_align()
115}
116
117fn alloc_str(bytes: &[u8], short: bool, hash: u32, hashed: bool) -> *mut LuaStr {
118    let layout = layout(bytes.len());
119    // SAFETY: layout is built from the header size + trailing bytes length we just computed; deallocation will use the same layout in `Heap::sweep_strings`.
120    unsafe {
121        let p = alloc(layout) as *mut LuaStr;
122        if p.is_null() {
123            handle_alloc_error(layout);
124        }
125        p.write(LuaStr {
126            hdr: GcHeader::new(ObjTag::Str),
127            hnext: ptr::null_mut(),
128            hash: Cell::new(hash),
129            hashed: Cell::new(hashed),
130            short,
131            len: bytes.len() as u32,
132        });
133        ptr::copy_nonoverlapping(bytes.as_ptr(), p.add(1) as *mut u8, bytes.len());
134        p
135    }
136}
137
138pub(crate) fn alloc_long(bytes: &[u8], seed: u32) -> *mut LuaStr {
139    debug_assert!(bytes.len() > MAX_SHORT_LEN);
140    alloc_str(bytes, false, seed, false)
141}
142
143/// SAFETY: `p` must come from `alloc_str` and not be freed twice.
144pub(crate) unsafe fn free(p: *mut LuaStr) {
145    unsafe {
146        let l = layout((*p).len as usize);
147        ptr::drop_in_place(p);
148        dealloc(p as *mut u8, l);
149    }
150}
151
152/// Open hashing with per-string chains (PUC stringtable shape).
153pub(crate) struct StringTable {
154    buckets: Vec<*mut LuaStr>,
155    count: usize,
156}
157
158impl StringTable {
159    pub(crate) fn new() -> StringTable {
160        StringTable {
161            buckets: vec![ptr::null_mut(); 64],
162            count: 0,
163        }
164    }
165
166    /// Find or create an interned short string. Returns `(ptr, newly_created)`.
167    pub(crate) fn intern(&mut self, bytes: &[u8], seed: u32) -> (*mut LuaStr, bool) {
168        debug_assert!(bytes.len() <= MAX_SHORT_LEN);
169        let h = lua_hash(bytes, seed);
170        let b = h as usize & (self.buckets.len() - 1);
171        let mut cur = self.buckets[b];
172        // SAFETY: `self.as_ptr()` is the start of this `LuaStr`'s header which was allocated with the trailing bytes / hash fields in the same allocation by `StringTable::intern`.
173        unsafe {
174            while !cur.is_null() {
175                if (*cur).len as usize == bytes.len() && bytes_of(cur) == bytes {
176                    return (cur, false);
177                }
178                cur = (*cur).hnext;
179            }
180        }
181        if self.count >= self.buckets.len() {
182            self.grow();
183        }
184        let b = h as usize & (self.buckets.len() - 1);
185        let p = alloc_str(bytes, true, h, true);
186        // SAFETY: Gc<T> is NonNull<T> over the GC heap; the heap is single-threaded and the pointer is live as long as it is reachable from active roots (see heap.rs:5-7).
187        unsafe {
188            (*p).hnext = self.buckets[b];
189        }
190        self.buckets[b] = p;
191        self.count += 1;
192        (p, true)
193    }
194
195    fn grow(&mut self) {
196        let mut nb = vec![ptr::null_mut(); self.buckets.len() * 2];
197        let mask = nb.len() - 1;
198        for &head in &self.buckets {
199            let mut cur = head;
200            while !cur.is_null() {
201                // SAFETY: Gc<T> is NonNull<T> over the GC heap; the heap is single-threaded and the pointer is live as long as it is reachable from active roots (see heap.rs:5-7).
202                unsafe {
203                    let next = (*cur).hnext;
204                    let b = (*cur).hash.get() as usize & mask;
205                    (*cur).hnext = nb[b];
206                    nb[b] = cur;
207                    cur = next;
208                }
209            }
210        }
211        self.buckets = nb;
212    }
213
214    /// Unlink a dying interned string (called from sweep).
215    pub(crate) fn remove(&mut self, p: *mut LuaStr) {
216        // SAFETY: Gc<T> is NonNull<T> over the GC heap; the heap is single-threaded and the pointer is live as long as it is reachable from active roots (see heap.rs:5-7).
217        unsafe {
218            let b = (*p).hash.get() as usize & (self.buckets.len() - 1);
219            let mut cur: *mut *mut LuaStr = &mut self.buckets[b];
220            while !(*cur).is_null() {
221                if *cur == p {
222                    *cur = (*p).hnext;
223                    self.count -= 1;
224                    return;
225                }
226                cur = &mut (**cur).hnext;
227            }
228            unreachable!("interned string missing from string table");
229        }
230    }
231}
232
233/// Allocation footprint of a string of `len` bytes (heap accounting).
234pub(crate) fn alloc_size(len: usize) -> usize {
235    layout(len).size()
236}
237
238#[cfg(test)]
239mod tests {
240    use crate::runtime::heap::Heap;
241
242    #[test]
243    fn short_strings_are_interned() {
244        let mut heap = Heap::new();
245        let a = heap.intern(b"hello");
246        let b = heap.intern(b"hello");
247        let c = heap.intern(b"world");
248        assert!(a.ptr_eq(b));
249        assert!(!a.ptr_eq(c));
250        assert_eq!(heap.live_objects(), 2);
251        assert_eq!(a.as_bytes(), b"hello");
252    }
253
254    #[test]
255    fn long_strings_are_not_interned() {
256        let mut heap = Heap::new();
257        let bytes = [0xAAu8; 64]; // non-UTF-8 long content
258        let a = heap.intern(&bytes);
259        let b = heap.intern(&bytes);
260        assert!(!a.ptr_eq(b));
261        assert_eq!(a.as_bytes(), b.as_bytes());
262        // lazy hash agrees for equal content
263        assert_eq!(a.hash(), b.hash());
264    }
265
266    #[test]
267    fn arbitrary_bytes_roundtrip() {
268        let mut heap = Heap::new();
269        let bytes: Vec<u8> = (0..=255).collect();
270        let s = heap.intern(&bytes);
271        assert_eq!(s.as_bytes(), &bytes[..]);
272        assert_eq!(s.len(), 256);
273    }
274
275    #[test]
276    fn interning_survives_table_growth() {
277        let mut heap = Heap::new();
278        let first = heap.intern(b"key000");
279        // push way past the initial 64 buckets to force grow()
280        for i in 0..2000 {
281            heap.intern(format!("key{i:03}").as_bytes());
282        }
283        let again = heap.intern(b"key000");
284        assert!(first.ptr_eq(again));
285    }
286}
luna_core/runtime/string.rs

luna_core/runtime/
string.rs
