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/// Inline-bytes access MUST go through a pointer carrying the provenance of
51/// the original allocation — a `&LuaStr` only covers the header, so deriving
52/// the tail from it is UB (caught by miri). `Gc` stores the allocation
53/// pointer, hence these live on `Gc<LuaStr>`.
54impl crate::runtime::heap::Gc<LuaStr> {
55    /// Borrow the underlying bytes of this Lua string.
56    pub fn as_bytes(&self) -> &[u8] {
57        // 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`.
58        unsafe { bytes_of(self.as_ptr()) }
59    }
60
61    /// Cached hash of the string (computed lazily for long strings).
62    pub fn hash(&self) -> u32 {
63        // 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`.
64        unsafe { hash_of(self.as_ptr()) }
65    }
66}
67
68/// SAFETY: `p` must point to a live string allocation (with its tail).
69pub(crate) unsafe fn bytes_of<'a>(p: *const LuaStr) -> &'a [u8] {
70    unsafe { slice::from_raw_parts(p.add(1) as *const u8, (*p).len as usize) }
71}
72
73/// SAFETY: as `bytes_of`.
74pub(crate) unsafe fn hash_of(p: *const LuaStr) -> u32 {
75    unsafe {
76        if !(*p).hashed.get() {
77            (*p).hash.set(lua_hash(bytes_of(p), (*p).hash.get()));
78            (*p).hashed.set(true);
79        }
80        (*p).hash.get()
81    }
82}
83
84/// PUC luaS_hash (all bytes, no step — post-5.3 flooding fix).
85pub(crate) fn lua_hash(bytes: &[u8], seed: u32) -> u32 {
86    let mut h = seed ^ bytes.len() as u32;
87    for &b in bytes {
88        h ^= h
89            .wrapping_shl(5)
90            .wrapping_add(h.wrapping_shr(2))
91            .wrapping_add(b as u32);
92    }
93    h
94}
95
96/// Longest string a `LuaStr` can describe (its length is a `u32`). Code
97/// that builds a string from script-controlled pieces checks against it.
98pub(crate) const MAX_LEN: usize = u32::MAX as usize;
99
100fn layout(len: usize) -> Layout {
101    Layout::new::<LuaStr>()
102        .extend(Layout::array::<u8>(len).expect("string size overflows layout"))
103        .expect("string size overflows layout")
104        .0
105        .pad_to_align()
106}
107
108fn alloc_str(bytes: &[u8], short: bool, hash: u32, hashed: bool) -> *mut LuaStr {
109    let layout = layout(bytes.len());
110    // SAFETY: layout is built from the header size + trailing bytes length we just computed; deallocation will use the same layout in `Heap::sweep_strings`.
111    unsafe {
112        let p = alloc(layout) as *mut LuaStr;
113        if p.is_null() {
114            handle_alloc_error(layout);
115        }
116        p.write(LuaStr {
117            hdr: GcHeader::new(ObjTag::Str),
118            hnext: ptr::null_mut(),
119            hash: Cell::new(hash),
120            hashed: Cell::new(hashed),
121            short,
122            len: bytes.len() as u32,
123        });
124        ptr::copy_nonoverlapping(bytes.as_ptr(), p.add(1) as *mut u8, bytes.len());
125        p
126    }
127}
128
129pub(crate) fn alloc_long(bytes: &[u8], seed: u32) -> *mut LuaStr {
130    debug_assert!(bytes.len() > MAX_SHORT_LEN);
131    alloc_str(bytes, false, seed, false)
132}
133
134/// SAFETY: `p` must come from `alloc_str` and not be freed twice.
135pub(crate) unsafe fn free(p: *mut LuaStr) {
136    unsafe {
137        let l = layout((*p).len as usize);
138        ptr::drop_in_place(p);
139        dealloc(p as *mut u8, l);
140    }
141}
142
143/// Open hashing with per-string chains (PUC stringtable shape).
144pub(crate) struct StringTable {
145    buckets: Vec<*mut LuaStr>,
146    count: usize,
147}
148
149impl StringTable {
150    pub(crate) fn new() -> StringTable {
151        StringTable {
152            buckets: vec![ptr::null_mut(); 64],
153            count: 0,
154        }
155    }
156
157    /// Find or create an interned short string. Returns `(ptr, newly_created)`.
158    pub(crate) fn intern(&mut self, bytes: &[u8], seed: u32) -> (*mut LuaStr, bool) {
159        debug_assert!(bytes.len() <= MAX_SHORT_LEN);
160        let h = lua_hash(bytes, seed);
161        let b = h as usize & (self.buckets.len() - 1);
162        let mut cur = self.buckets[b];
163        // 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`.
164        unsafe {
165            while !cur.is_null() {
166                if (*cur).len as usize == bytes.len() && bytes_of(cur) == bytes {
167                    return (cur, false);
168                }
169                cur = (*cur).hnext;
170            }
171        }
172        if self.count >= self.buckets.len() {
173            self.grow();
174        }
175        let b = h as usize & (self.buckets.len() - 1);
176        let p = alloc_str(bytes, true, h, true);
177        // 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).
178        unsafe {
179            (*p).hnext = self.buckets[b];
180        }
181        self.buckets[b] = p;
182        self.count += 1;
183        (p, true)
184    }
185
186    fn grow(&mut self) {
187        let mut nb = vec![ptr::null_mut(); self.buckets.len() * 2];
188        let mask = nb.len() - 1;
189        for &head in &self.buckets {
190            let mut cur = head;
191            while !cur.is_null() {
192                // 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).
193                unsafe {
194                    let next = (*cur).hnext;
195                    let b = (*cur).hash.get() as usize & mask;
196                    (*cur).hnext = nb[b];
197                    nb[b] = cur;
198                    cur = next;
199                }
200            }
201        }
202        self.buckets = nb;
203    }
204
205    /// Unlink a dying interned string (called from sweep).
206    pub(crate) fn remove(&mut self, p: *mut LuaStr) {
207        // 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).
208        unsafe {
209            let b = (*p).hash.get() as usize & (self.buckets.len() - 1);
210            let mut cur: *mut *mut LuaStr = &mut self.buckets[b];
211            while !(*cur).is_null() {
212                if *cur == p {
213                    *cur = (*p).hnext;
214                    self.count -= 1;
215                    return;
216                }
217                cur = &mut (**cur).hnext;
218            }
219            unreachable!("interned string missing from string table");
220        }
221    }
222}
223
224/// Allocation footprint of a string of `len` bytes (heap accounting).
225pub(crate) fn alloc_size(len: usize) -> usize {
226    layout(len).size()
227}
228
229#[cfg(test)]
230mod tests {
231    use crate::runtime::heap::Heap;
232
233    #[test]
234    fn short_strings_are_interned() {
235        let mut heap = Heap::new();
236        let a = heap.intern(b"hello");
237        let b = heap.intern(b"hello");
238        let c = heap.intern(b"world");
239        assert!(a.ptr_eq(b));
240        assert!(!a.ptr_eq(c));
241        assert_eq!(heap.live_objects(), 2);
242        assert_eq!(a.as_bytes(), b"hello");
243    }
244
245    #[test]
246    fn long_strings_are_not_interned() {
247        let mut heap = Heap::new();
248        let bytes = [0xAAu8; 64]; // non-UTF-8 long content
249        let a = heap.intern(&bytes);
250        let b = heap.intern(&bytes);
251        assert!(!a.ptr_eq(b));
252        assert_eq!(a.as_bytes(), b.as_bytes());
253        // lazy hash agrees for equal content
254        assert_eq!(a.hash(), b.hash());
255    }
256
257    #[test]
258    fn arbitrary_bytes_roundtrip() {
259        let mut heap = Heap::new();
260        let bytes: Vec<u8> = (0..=255).collect();
261        let s = heap.intern(&bytes);
262        assert_eq!(s.as_bytes(), &bytes[..]);
263        assert_eq!(s.len(), 256);
264    }
265
266    #[test]
267    fn interning_survives_table_growth() {
268        let mut heap = Heap::new();
269        let first = heap.intern(b"key000");
270        // push way past the initial 64 buckets to force grow()
271        for i in 0..2000 {
272            heap.intern(format!("key{i:03}").as_bytes());
273        }
274        let again = heap.intern(b"key000");
275        assert!(first.ptr_eq(again));
276    }
277}
luna_core/runtime/string.rs

luna_core/runtime/
string.rs
