diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/260825-code-gc.md | 311 | ||||
| -rw-r--r-- | notes/index.md | 1 |
2 files changed, 312 insertions, 0 deletions
diff --git a/notes/260825-code-gc.md b/notes/260825-code-gc.md new file mode 100644 index 0000000..9593d15 --- /dev/null +++ b/notes/260825-code-gc.md @@ -0,0 +1,311 @@ +# Memory management of code + +_August 2026_ + +If you're implementing an interpreter for a homoiconic language like +Lisp that is also garbage collected, there's the issue that, since +code is data, code is subject to GC. + +That's a problem if you care about GC efficiency, because a program +isn't likely to have its code change much after it's been loaded up. +You may be modifying a module of code at run-time, meaning that some +parts of the module's code become dead, but that's a rare exception. + +So, most of the time, you'd be scanning lists that make up the code +over and over again, even though they are very unlikely to ever die. + +A generational GC makes this less bad, since the lists making up the +code will be promoted to some "ancient" generation eventually, but +perhaps there's a good solution that doesn't have to rely on that. + +As part of my plan to transform code expressions into an optimized +form that's similar to bytecode, I will already be changing the type +tags on NaN-packed representations of code forms. The GC might then +simply ignore these. + +Let's consider the consequences... + +Start by looking at the in-memory representation of a module after +said optimization has been performed: + + { + name = 0x1111 -> <list: (my cool module)> + version = 1234 + bindings = 0x2222 -> <hash_table: [ + { + key = 0x1234 -> <identifier: foo> + val = 0x2345 -> <box: 0x3333> -> <code: (let ((a b)) c)> + } + { + key = 0x3456 -> <identifier: bar> + val = 0x4567 -> <box: 0x4444> -> <array: [x y z]> + } + { + key = 0x5678 -> <identifier: MY_CONSTANT> + val = 0x6789 -> <box: <fixnum: 12345678>> + } + ]> + } + +Hopefully that's somewhat reasonable of a graphic. The module is +presumably something like a struct, that may have a name and version +and whatnot, and then a pointer to a hash table which maps identifier +(pointer) keys to box (pointer) values. The boxing of the values is +so that other modules have a stable address to point to; the binding +table getting resized and having all its contents moved won't break +references to this module's bindings from an importing module, and +neither will rebinding an identifier cause breakage. If a binding +gets removed, it should not really be removed from the table but +rather have its value box be overridden with some kind of dummy +"undefined" value; otherwise things become unsafe. + +In this example, the bindings include a code form, an array, and a +fixnum constant. + +The GC would walk the bindings table, making sure to mark the array, +and traverse it too if it's a Value array, but it would skip over the +pointer to the optimized code form, which it refuses to traverse. + +This means the entire graph of objects that make up a code form must +not be collected, and must not contain pointers to outside the graph. +It's a self-contained object graph that's "pinned" in memory. + +Another way to look at this is in terms of ownership semantics: All +objects in the code form graph are owned by the module, exclusively. +They may not be shared. + +Given this invariant, modifying the module by rebinding 'foo' to new +code can safely explicitly deallocate the old code form. We can have +manual memory management in the runtime for this particular case. + +But how to ensure the invariant? There are three concerns: + +1. Code forms must not contain direct pointers to the values of the + bindings of another module; not even to the boxes. + + This is solved by having a dedicated NaN representation for these + kinds of module binding references, that aren't seen as a pointer + by the GC. The current NaN-packing scheme doesn't actually have + room for this, but I'm thinking of using a trick where a module's + top-level is considered a lexical environment and any procedure + that references its bindings is a closure; our NaN packing scheme + has a dedicated representation for "reference to lexical variable + capture" so that works elegantly. + + (define foo (list x y z)) + + (define (bar) (print foo)) + + In the above, `bar` is bound to a code form containing a lexical + variable reference to `foo`; the recursive `free()` calls on the + code form graph skips over these lexical references. + + The same principle applies to imported bindings; they are simply + considered part of the top-level lexical environment of a module, + within which a procedure definition is simply a matter of binding + an identifier to the result of a lambda expression. + +2. Programmers must not abuse datum labels to construct code forms + whose object graph shares some structure with code/data forms + outside the code form. If you do that, it's your fault: + + (define (foo a b) (* 2 #%1234=(+ a b))) + + (define (bar a b) (* 4 #%1234%)) + + I mean, come on... Use a macro. If you do this, then rebind the + `bar` procedure, the runtime will recursively free the old graph, + leading `foo` to be left with a dangling pointer. Exciting, or + rather terrifying! This really isn't how you write code on the + regular, so I don't think it would happen to anyone by accident + during serious software development. + +3. Programmers must not manually construct code forms whose object + graph has shared references. If you do that, it's your fault: + + ;; foo refers to some heap object from elsewhere + (let ((code `(lambda () ,foo))) + (module-bind! '(my module) 'foo (eval code))) + + To be honest, this isn't an unlispy thing to do. What if someone + unwittingly does it, not realizing it's illegal? I don't see any + way to check against it; maybe we just have to live with certain + foot-guns like this in the language for the sake of efficiency? + + Is there at least a way the programmer can fix this code? Yes, + using an explicit copy operation on foo. + +I think this covers all pathological cases. Given the above rules, +code forms should be possible to be excluded from GC logic. + +I've thought about whether it would make sense to apply this to any +top-level binding to a heap object, but I don't think so. Consider: + + (define full-data '(foo bar (baz bat))) + + (define part (list-ref full-data 2)) ;shortcut to (baz bat) + +Now, if you redefine `full-data` you almost certainly want to also +redefine `part`, but the thing is, if `full-data` is redefined while +`part` isn't yet, for whatever reason, you don't want a segfault or +silently have `part` start pointing to arbitrary data that just so +happened to fill the spot in memory that `(baz bat)` used to occupy. +There's no clean solution but to have these objects be GC-managed. + +At least until a module is "frozen" which I will get to now. + + +## Generalizing + +This idea could actually be generalized to entire modules. This may +make it unnecessary to special-case code forms in the GC logic. + +Modules would have a "frozen" or "sealed" flag which, when enabled, +causes the entire module to be treated as a closed graph that is +skipped by GC traversal and pinned in memory. + +It could still be swapped out entirely, manually freeing the entire +old object graph of the module. This requires similar invariants as +above, just applied to the whole module. + +This would resolve two issues from above: Since code forms can now +have pointers to other objects in the module, immutable top-level +bindings can have their value copied directly into the code of a +procedure. The value in question may still be a pointer, but one +indirection layer is removed, and the lexical capture array of the +procedure is shortened. The second resolved issue is insignificant, +because it's just the datum label crap. Nobody needs that, but hey, +it would be possible. + +The issue with manually constructed code forms remains: If you do +that, then freeze the module, then swap the entire thing for a new +version, then the old graph of objects will be manually freed, which +may include an object you had a reference to from outside the module. + +Now that I think about it, perhaps `module-bind!` or whatever should +simply perform an implicit copy on the object it's provided. That's +fairly clean of a solution, I guess. There could be some override, +which skips the copying, for those who like to live dangerously (or +maybe even know what they're doing). + + +## Combining + +It may be useful to always apply this optimization to code forms, +regardless of whether a module is frozen, but then also allow this +module freezing optimization, since it adds further value. + +I've also thought about the ability to "statically link" modules in +the past; let's see how that might interact with this optimization: + +For a module that's being linked to dynamically, being frozen or not +merely affects internal optimizations within that module: Whether the +immutable top-level bindings can be copied by value into code forms. +There's just one catch: Swapping out the entire frozen module for a +new version must reuse the boxes of the binding table, or else other +modules pointing to these end up with dangling pointers. And if some +binding doesn't exist in the new version, it must be created anyway, +with a dummy "undefined" value inside the box, so that the code of +other modules trying to resolve that binding will cleanly error, and +not segfault or be corrupted by silently starting to point to some +arbitrary object that happened to take the position of the old box. + +As for static linking, let's consider what that means in terms of +language semantics first: It's almost like copy-pasting the code of +the statically linked module into the linking module, just with one +major difference, which is that mutable state is shared with other +modules that statically link the same version of the same module. + +In other words, if module S defines `foo` as a binding to a mutable +heap object, then modules A and B that statically link to S must be +able to observe mutations to said heap object. + +How does that interact with freezing? + +For frozen modules, it's simple: Instead of referring to the binding +boxes of the linked module, you get freedom to refer directly to the +values of the bindings, since they are frozen. The module must also +have its current version be permanently pinned in memory, so if the +whole thing gets swapped out, any modules that had statically linked +the old version continue working. They just don't observe the swap. + +I'm trying to think about how statically linking a non-frozen module +would behave, and it leaves me a confused mess. A non-frozen module +can't even refer to its own top-level bindings by value, so any other +module obviously can't either. Either static linking should not be +allowed on non-frozen modules, or it should create a frozen version +pinned in memory... Probably best to just disallow it. + + +## Private bindings + +In some previous note, I had shown an example like this: + + (define foo 1) + + (let bar 2) + + (define (test) (print foo) (print bar)) + + ;; --- becomes optimized into --- + + (define foo 1) + + (define (test) (print foo) (print 2)) + +Here, the `let` forms create private bindings, and as an optimization +they get copied into code that references them. That could still be +viable, but only if the private binding has a non-heap value, since +copying in a pointer to a heap value would cause that heap value to +become freed if the procedure is freed, as part of the manual memory +management of top-level procedures. + +If it's a pointer to immutable data, then the entire data could be +copied in, but that's a topic for another day, because I don't yet +know how to deal with mutability and immutability of heap types, +except for some like interned strings that are always immutable. + + +## Summary + +* Modules are normally GC roots, and their binding table is traversed + normally. + +* Except for code forms, which are skipped by the GC, and have their + whole object graph pinned in memory. They are freed if redefined, + with recursive `free()` on the entire object graph; as such, they + must not have pointers to shared data in their graph, except for + their lexical captures array that is freed non-recursively. + +* As a small optimization, references to private non-heap values can + still be copied into code forms by value, and possibly immutable + heap objects (by deep copy) as well. + +* Modules can be frozen, which pins the entire object graph of the + module in memory, and deregisters the module from GC roots. This + enables optimization of internal top-level references. The entire + frozen module can be swapped out, which frees it recursively, but + the new version must reuse binding boxes for existing identifiers, + even creating dummy ones with "undefined" for removed bindings. + +* Frozen modules can be statically linked, which ensures that it will + remain pinned in memory even if swapped out for a new version; any + references to its bindings can now be optimized by copying the box + value (could still be a pointer) rather than having to point to the + box to observe changes from having the entire module swapped out. + +How do we detect that a statically linked module can be freed due to +all linking modules being gone as well? There's a few options: + +1. Don't. Statically linked means stays in memory forever. Eh... + +2. Reference counting. Must disallow cycles, or they leak. May be + acceptable to disallow cyclic static linking. + +3. Just have a dedicated mark & sweep for modules? + +This article ended up being *way* longer than I expected, so I think +I'll call it quits here. I think a simple little mark & sweep of a +global modules list would be quite fine though. To be clear I don't +mean going into the modules; just the modules themselves. So this +would be a very quick and easy operation. diff --git a/notes/index.md b/notes/index.md index d303d5a..b81f20b 100644 --- a/notes/index.md +++ b/notes/index.md @@ -40,3 +40,4 @@ * [Virtual memory overcommit](260821-overcommit.html) * [Releasing vmem, reloaded](260821-release2.html) * [Releasing vmem, again](260822-release3.html) +* [Memory management of code](260825-code-gc.html) |