Upvalues

Three concepts: the open/closed representation, sharing through the open list, and closing.

The previous chapter established what must happen: a captured variable is a box, and closures hold references to it. This chapter is where the box lives — and the answer is "on the stack, until it cannot be, and then on the heap."

That is Lua's design. It is the single cleverest mechanism in the reference implementation, it costs about eighty lines, and it makes closures free when they do not escape.

Concept 1: Open and Closed

1. Concept

An upvalue is a box holding a captured variable. It has two states:

• Open — the variable is still alive in a stack frame. The upvalue points at the stack slot.
• Closed — the frame is gone. The upvalue owns the value, on the heap.

#![allow(unused)]
fn main() {
pub enum Upvalue {
    Open(usize),        // an absolute index into the VM's value stack
    Closed(Value),      // the value, copied out of the dying slot
}
}

2. Problem

The naive design from the previous chapter — heap-allocate a box for every captured local at declaration — is correct and wasteful. It allocates even when no closure is ever created, and it turns every read of that local into a pointer chase for the enclosing function too, which never asked for one.

You want: zero cost while the variable is on the stack, and correctness after the frame dies.

3. Mental model

An open upvalue is a forwarding address. The variable is still where it always was — in the frame — and the upvalue just knows where. When the frame is about to die, you close the upvalue: copy the value out of the doomed slot into the upvalue itself. Everyone who was pointing at the upvalue keeps working, and nobody had to be told.

   WHILE make_counter IS RUNNING          AFTER IT RETURNS

   stack                                  stack
   ┌────────────────┐                     ┌──────────────┐
   │ ...            │                     │ ...          │
   │ [14] count = 3 │◀────┐               │  (truncated) │
   └────────────────┘     │               └──────────────┘
                          │
   heap                   │               heap
   ┌────────────────────┐ │               ┌────────────────────┐
   │ Upvalue::Open(14) ─┼─┘               │ Upvalue::Closed(3) │
   └────────▲───────────┘                 └────────▲───────────┘
            │                                      │
      ┌─────┴─────┐                          ┌─────┴─────┐
      │ inc   get │                          │ inc   get │
      └───────────┘                          └───────────┘

   The CLOSURES did not change. Only the upvalue's own contents did.

That last line is the trick. Closing is a mutation of one heap object; every reference to it — from closures, from other closures, from anywhere — is unaffected. No pointer needs updating.

4. Implementation

#![allow(unused)]
fn main() {
impl Vm {
    fn read_upvalue(&self, u: GcRef<Upvalue>) -> Value {
        match *self.heap.upvalue(u) {
            Upvalue::Open(slot) => self.stack[slot],   // still on the stack
            Upvalue::Closed(v)  => v,                  // owns it
        }
    }

    fn write_upvalue(&mut self, u: GcRef<Upvalue>, v: Value) {
        match &mut *self.heap.upvalue_mut(u) {
            Upvalue::Open(slot) => { let s = *slot; self.stack[s] = v; }
            Upvalue::Closed(c)  => *c = v,
        }
    }
}
}

GET_UPVAL and SET_UPVAL are those two functions. An open upvalue read is one extra indirection over GET_LOCAL; a closed one is two. Compare that with the naive design, where every access to a captured variable — including from the function that declared it — is an indirection forever.

Warning: Upvalue::Open(usize) stores an absolute stack index, not an offset from a frame's base. That is deliberate: the frame it refers to may not be the current one, so a relative index would need to know which frame, and frames come and go. The cost is that the index becomes meaningless if the stack is ever reallocated in a way that moves values between indices — which is why Ember's stack only ever grows, truncates, and writes in place. Never insert or remove from the middle. Write that invariant in a comment on the stack field.

5. Alternatives

6. Decision

B, after building A first.

Two reasons for that ordering, and the second is the pedagogical point of the whole lab:

1. A is correct and takes an hour; B takes an afternoon. Getting the semantics right first means that when B misbehaves you know it is a mechanism bug, not a misunderstanding.
2. The diff between A and B is the lesson. Keep it. git diff between the two commits, saved into docs/learning/10-upvalues.md, is worth more than any explanation in this book.

7. Tradeoffs

Concept 2: The Open List, and How Sharing Works

1. Concept

The VM keeps a list of all currently-open upvalues, sorted by stack index. Creating an upvalue for a slot searches that list first: if one already exists, it is reused.

2. Problem

local function inc() count = count + 1 end
local function get() return count end

Two CLOSURE instructions, both capturing the same slot. If each allocated its own box, they would be different variables and the counter example would print 1 2 3 then 0.

Sharing is not a property of closures; it is a property of the lookup.

3. Mental model

The open list is a registry of boxes, keyed by stack slot. "Give me the box for slot 14" is the only way to make one, so everyone asking for slot 14 gets the same box, automatically.

   open list (sorted by slot, descending — highest first)

     ┌──────────────┐   ┌──────────────┐   ┌──────────────┐
     │ Open(21)     │──▶│ Open(14)     │──▶│ Open(9)      │
     └──────────────┘   └──────▲───────┘   └──────────────┘
                               │
                     inc and get BOTH point here

Sorted descending is not decoration: closing walks from the head and stops at the first upvalue below the threshold, so closing a frame is O(number closed), not O(list length).

4. Implementation

#![allow(unused)]
fn main() {
/// Sorted DESCENDING by slot. Ember uses a Vec because the list is short
/// (one entry per captured variable currently live) and a Vec's locality beats
/// a linked list at these sizes. Lua uses an intrusive linked list threaded
/// through the UpVal objects themselves, which avoids the auxiliary allocation.
open_upvalues: Vec<GcRef<Upvalue>>,

fn find_or_create_open_upvalue(&mut self, slot: usize) -> Result<GcRef<Upvalue>> {
    // The list is sorted descending, so scan until we reach `slot` or pass it.
    for (i, &u) in self.open_upvalues.iter().enumerate() {
        match *self.heap.upvalue(u) {
            Upvalue::Open(s) if s == slot => return Ok(u),      // ← SHARING happens here
            Upvalue::Open(s) if s < slot  => {
                let new = self.heap.alloc_upvalue(Upvalue::Open(slot))?;
                self.open_upvalues.insert(i, new);
                return Ok(new);
            }
            _ => {}
        }
    }
    let new = self.heap.alloc_upvalue(Upvalue::Open(slot))?;
    self.open_upvalues.push(new);
    Ok(new)
}
}

One if — s == slot — is the entire sharing mechanism. Delete it and the counter example breaks. It is worth putting a comment on that line saying so, because it looks like an optimization and it is a semantic.

5–7. Alternatives, decision, tradeoffs

Decision: A. The list holds one entry per currently open captured variable, which in real code is a handful. Optimizing it before measuring would be exactly the mistake Section 7 forbids.

8. Production concerns

• The open list is a GC root set. An open upvalue is reachable from closures, but a newly created one — between alloc_upvalue and the closure being stored — is reachable only from this list. Miss it in enumerate_roots and a collection at the wrong moment frees a live upvalue. This is one of the seven root sets, and it is the one people forget.
• Open upvalues point into the stack, which is also a root set. That is fine — the stack keeps the value alive and the upvalue does not need to trace it — but a closed upvalue does own a Value and must be traced. Two states, two different tracing behaviors, in one match.
• The list must stay sorted. An insert at the wrong position makes close_upvalues miss entries, which leaves upvalues pointing at truncated stack slots. Add a debug assertion that the list is sorted after every mutation; it costs nothing and it catches this instantly.

Concept 3: Closing

1. Concept

Closing an upvalue copies the value out of its stack slot into the upvalue itself and marks it Closed. It happens when the slot is about to become invalid.

2. Problem

Two events invalidate a slot, and both must close:

1. A function returns — the whole frame's region is truncated.
2. A block ends — locals declared in it are popped, even though the frame lives on.

The second is the one people miss:

local fs = {}
for i = 1, 3 do
  local doubled = i * 2
  fs[i] = function() return doubled end     -- captures a per-iteration local
end                                          -- ← the block ends HERE, 3 times
print(fs[1](), fs[2](), fs[3]())             -- 2  4  6

If doubled were only closed at function return, all three closures would still point at one recycled slot and print 6 6 6.

3. Mental model

Close before you truncate. The value must be rescued from the slot while the slot still holds it. There is no error if you get the order wrong — the upvalue simply captures whatever the stack happens to contain next, which is usually plausible and occasionally correct.

4. Implementation

#![allow(unused)]
fn main() {
/// Close every open upvalue at or above `from`. The list is sorted descending,
/// so we can stop at the first one below the threshold.
fn close_upvalues(&mut self, from: usize) {
    while let Some(&u) = self.open_upvalues.first() {
        let slot = match *self.heap.upvalue(u) {
            Upvalue::Open(s) if s >= from => s,
            _ => break,                       // sorted: nothing below can qualify
        };
        let v = self.stack[slot];             // ← RESCUE the value...
        *self.heap.upvalue_mut(u) = Upvalue::Closed(v);
        self.open_upvalues.remove(0);
    }
}
}

Called in exactly two places:

#![allow(unused)]
fn main() {
// 1. Function return — BEFORE the truncate. Order is not optional.
fn do_return(&mut self, n: u8) -> Result<Option<Vec<Value>>> {
    let frame = self.frames.pop().unwrap();
    let results = self.stack[self.stack.len() - n as usize..].to_vec();
    self.close_upvalues(frame.base);          // ← BEFORE
    self.stack.truncate(frame.ret_to);        // ← the values are now unreachable
    // ...
}

// 2. Block exit — the compiler emits CLOSE_UPVALS instead of counting a
//    captured local into the plain POP. This is what `mark_captured` was for.
Op::CloseUpvals(s) => {
    let base = self.frame().base;
    self.close_upvalues(base + s as usize);
    self.stack.truncate(base + s as usize);
}
}

And the compiler side, which is where mark_captured from the capture-analysis pass pays off:

#![allow(unused)]
fn main() {
fn end_scope(&mut self, span: Span) {
    self.scope_depth -= 1;
    let mut plain_pops = 0u8;
    while let Some(l) = self.locals.last() {
        if l.depth <= self.scope_depth { break; }
        if l.captured {
            // Flush any pending plain pops FIRST, then close from this slot up.
            if plain_pops > 0 { self.emit(Op::Pop(plain_pops), span); plain_pops = 0; }
            self.emit(Op::CloseUpvals((self.locals.len() - 1) as u8), span);
        } else {
            plain_pops += 1;
        }
        self.locals.pop();
    }
    if plain_pops > 0 { self.emit(Op::Pop(plain_pops), span); }
}
}

5–7. Alternatives, decision, tradeoffs

8. Production concerns

• Error paths must close too. When a runtime error unwinds frames, every frame's upvalues must be closed on the way out — otherwise a closure that survives via pcall points at a truncated slot. Ember closes in the unwinding path, and the test is: capture a variable, raise inside the function, catch with pcall, then call the closure.
• break and return from inside a captured block must emit CLOSE_UPVALS for the scopes they jump out of, exactly as they emit POP for the uncaptured ones. Same bug as the missing break pop, one level nastier because the symptom is a wrong value rather than a wrong slot.
• Closing during a GC is forbidden. close_upvalues mutates heap objects and reads the stack. If a collection could run in the middle, it would see a half-updated state. Ember's collector only runs at allocation points, and close_upvalues allocates nothing — state that invariant, because it is what makes the function safe.
• The stack index must remain valid between capture and close. The invariant from Concept 1: the stack only grows, truncates, and writes in place. If Section 7 ever adds a stack-moving optimization, every open upvalue's index must be fixed up — the same problem a moving GC has, and worth noting as a reason Ember's collector is non-moving.

9. References

rg -n 'luaF_findupval|luaF_close|UpVal|upisopen' lfunc.c lfunc.h lobject.h
rg -n 'OP_CLOSE|luaF_close' lvm.c

• Lua's lfunc.c: luaF_findupval is find_or_create_open_upvalue (with the intrusive list), and luaF_close is close_upvalues. Read upisopen and the UpVal union in lobject.h alongside — Lua stores the open/closed state as a pointer that either points into the stack or at its own embedded value, which is a nice trick worth understanding even though Rust would rather you used an enum.
• The Implementation of Lua 5.0, §5, has the diagram this chapter's diagrams descend from.
• Crafting Interpreters, chapter 25, §25.4 ("Closing Upvalues") — the same algorithm in C, and the clearest alternative explanation available.

Things to Notice

• Closing mutates the box, not the pointers. Everyone referencing the upvalue keeps working because nothing about them changed. That is why this design is cheap.
• Sharing is one == in the lookup. It looks like a cache and it is a semantic.
• The open list must be sorted, and it is a GC root set. Both are easy to forget and both produce bugs that look like memory corruption.
• Close before truncate. No error, no warning, plausible wrong values.
• Block exit closes too, not just return. The per-iteration-local case is the one that catches an implementation that only closes on return.
• Open upvalues make the stack unmovable. That constraint is one of the reasons Ember's collector does not move objects — and it is the kind of coupling between subsystems worth recording in docs/architecture.md.

Validation / Self-check

1. Give the two states of an upvalue and what each holds.
2. Why does closing not require updating any closure?
3. Which single line implements sharing between two closures over one variable?
4. Why is the open list sorted descending? What does that buy close_upvalues?
5. Give the two events that trigger closing, and the program that only the second one handles correctly.
6. Why must closing happen before stack.truncate? What is the symptom of the wrong order?
7. Which compiler pass decides that a scope exit emits CLOSE_UPVALS instead of POP?
8. Name two GC-related facts about upvalues: one about roots, one about tracing.
9. Why does an open upvalue's stack index force the stack to be non-moving, and what does that imply about the collector?
10. Compare A (heap-allocate on declaration) and B (open/closed) on: allocations when no closure is created; cost of access from the declaring function; cost of access from a closure.

Next: Garbage Collection.