6,566
edits
How the Nasal GC works: Difference between revisions
Jump to navigation
Jump to search
Converted a large number of broken Gitorious links into functional and dynamically created SourceForge links using {{simgear source}} and {{flightgear source}}, and updated the line numbers for the newest code.
(→Status (02/2016): Switched to {{simgear source}} and {{flightgear source}} to remove the dead Gitorious links and point to the current SourceForge sources.) |
(Converted a large number of broken Gitorious links into functional and dynamically created SourceForge links using {{simgear source}} and {{flightgear source}}, and updated the line numbers for the newest code.) |
||
| Line 373: | Line 373: | ||
= Pool storage = | = Pool storage = | ||
A [http://en.wikipedia.org/wiki/Memory_pool memory pool] is basically a preallocated region of memory, which is dynamically resized. The Nasal GC works such that it manages a handful of global memory pools for all native Nasal types (strings, functions, vectors, hashes etc). At the moment, the hard coded defaults ensure that 25-50% of additional object "slots" (memory blocks) are kept available during each execution of reap() [ | A [http://en.wikipedia.org/wiki/Memory_pool memory pool] is basically a preallocated region of memory, which is dynamically resized. The Nasal GC works such that it manages a handful of global memory pools for all native Nasal types (strings, functions, vectors, hashes etc). At the moment, the hard coded defaults ensure that 25-50% of additional object "slots" (memory blocks) are kept available during each execution of reap() [{{simgear source|path=simgear/nasal/gc.c|line=287|full=1}}]. | ||
Whenever new memory is requested to create a new type (such as a vector or a string), the available memory in the corresponding pool will be checked, reachable objects will be marked, and dead objects will be removed from all pools using a mark/sweep collector, new memory blocks will be allocated if necessary. All of this happens atomically, i.e. single-threaded, in a "stop-the-world" fashion. | Whenever new memory is requested to create a new type (such as a vector or a string), the available memory in the corresponding pool will be checked, reachable objects will be marked, and dead objects will be removed from all pools using a mark/sweep collector, new memory blocks will be allocated if necessary. All of this happens atomically, i.e. single-threaded, in a "stop-the-world" fashion. | ||
| Line 385: | Line 385: | ||
A Nasal memory pool consists of memory blocks. | A Nasal memory pool consists of memory blocks. | ||
A memory block is a [http://en.wikipedia.org/wiki/Linked_list#Linear_and_circular_lists singly linked list]: | A memory block is a [http://en.wikipedia.org/wiki/Linked_list#Linear_and_circular_lists singly linked list]: {{simgear source|path=simgear/nasal/gc.c|line=10}}. | ||
[[File:NasalNewBlockCallgraph.png|thumb|400px|Callgraph for newBlock()]] | [[File:NasalNewBlockCallgraph.png|thumb|400px|Callgraph for newBlock()]] | ||
| Line 399: | Line 399: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
New memory blocks are allocated using newBlock() and the memory is initialized with 0: | New memory blocks are allocated using newBlock() and the memory is initialized with 0: {{simgear source|path=simgear/nasal/gc.c|line=167}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 435: | Line 435: | ||
For each of the 7 Nasal data types, there is a separate storage pool available, declared as part of the "Globals" structure. | For each of the 7 Nasal data types, there is a separate storage pool available, declared as part of the "Globals" structure. | ||
As can be seen, each storage pool is addressed by its enum index (0..6): | As can be seen, each storage pool is addressed by its enum index (0..6): {{simgear source|path=simgear/nasal/data.h|line=65}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
enum { T_STR, T_VEC, T_HASH, T_CODE, T_FUNC, T_CCODE, T_GHOST, NUM_NASAL_TYPES }; // V. important that this come last! | enum { T_STR, T_VEC, T_HASH, T_CODE, T_FUNC, T_CCODE, T_GHOST, NUM_NASAL_TYPES }; // V. important that this come last! | ||
| Line 446: | Line 446: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
The 7 storage pools are declared in code.h as part of the "Globals" structure | The 7 storage pools are declared in code.h as part of the "Globals" structure: {{simgear source|path=simgear/nasal/code.h|line=40}} | ||
The relevant part is: | The relevant part is: | ||
| Line 523: | Line 523: | ||
[[File:NasalnaPoolStruct.png|thumb|400px|Nasal naPool structure]] | [[File:NasalnaPoolStruct.png|thumb|400px|Nasal naPool structure]] | ||
The structure keeping all pool-related information is named "naPool", the layout of the naPool structure can be seen in data.h | The structure keeping all pool-related information is named "naPool", the layout of the naPool structure can be seen in data.h: {{simgear source|path=simgear/nasal/data.h|line=181}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
struct naPool { | struct naPool { | ||
| Line 537: | Line 537: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Each memory pool is initialized using naGC_init(): | Each memory pool is initialized using naGC_init(): {{simgear source|path=simgear/nasal/gc.c|line=192}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 553: | Line 553: | ||
As can be seen, "elemsz" just stores the size of each type-specific structure, so that it can be used for new allocations. | As can be seen, "elemsz" just stores the size of each type-specific structure, so that it can be used for new allocations. | ||
naGC_init is called in initGlobals() in code.c for each Nasal type (T_STR, T_VEC etc): | naGC_init is called in initGlobals() in code.c for each Nasal type (T_STR, T_VEC etc): {{simgear source|path=simgear/nasal/code.c|line=172}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
for(i=0; i<NUM_NASAL_TYPES; i++) | for(i=0; i<NUM_NASAL_TYPES; i++) | ||
| Line 560: | Line 560: | ||
The size of a memory pool is determined using poolsize(): | The size of a memory pool is determined using poolsize(): {{simgear source|path=simgear/nasal/gc.c|line=203}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 576: | Line 576: | ||
= Allocating Nasal types = | = Allocating Nasal types = | ||
All Nasal types (scalars, vectors, hashes, funcs, ghosts) are allocated via wrappers in | All Nasal types (scalars, vectors, hashes, funcs, ghosts) are allocated via wrappers in {{simgear source|path=simgear/nasal/misc.c|text=misc.c}}. | ||
These wrappers are: | These wrappers are: | ||
* naNewString(): | * naNewString(): {{simgear source|path=simgear/nasal/misc.c|line=77}} | ||
* naNewVector(): | * naNewVector(): {{simgear source|path=simgear/nasal/misc.c|line=87}} | ||
* naNewHash(): | * naNewHash(): {{simgear source|path=simgear/nasal/misc.c|line=94}} | ||
* naNewCode(): | * naNewCode(): {{simgear source|path=simgear/nasal/misc.c|line=101}} | ||
* naNewCCode(): | * naNewCCode(): {{simgear source|path=simgear/nasal/misc.c|line=106}} | ||
* naNewFunc(): | * naNewFunc(): {{simgear source|path=simgear/nasal/misc.c|line=131}} | ||
* naNewGhost(): | * naNewGhost(): {{simgear source|path=simgear/nasal/misc.c|line=140}} | ||
* naNewGhost2(): | * naNewGhost2(): {{simgear source|path=simgear/nasal/misc.c|line=154}} | ||
All of these wrappers are really just helpers on top of naNew(), they just set up type-specific information and initialize each Nasal type properly. | All of these wrappers are really just helpers on top of naNew(), they just set up type-specific information and initialize each Nasal type properly. | ||
| Line 605: | Line 605: | ||
= naNew() = | = naNew() = | ||
As can be seen, the key allocator function is | As can be seen, the key allocator function is {{simgear source|path=simgear/nasal/misc.c|line=66|text=naNew()}}. | ||
All memory allocations done via the naNew*() helpers will first of all set up memory using naNew(). | All memory allocations done via the naNew*() helpers will first of all set up memory using naNew(). | ||
| Line 614: | Line 614: | ||
{{FGCquote|1= Once listeners were added, scripts could be recursive: (script A sets property X which causes listener L to fire and cause script B to run) We need two or more contexts on the stack to handle that; a single global one won't work. I didn't like the fix though. Exposing the temporary bin as part of the Nasal public API is ugly; it's an internal design feature, not something users should tune. Instead, I just hacked at the FlightGear code to reinitialie this context every frame, thus cleaning it up. A "proper" fix would be to remove the global context entirely, but that would touch a bunch of code.|2= {{cite web | url = http://sourceforge.net/p/flightgear/mailman/message/15645369/ | title = <nowiki>[Flightgear-devel] Stutter/Nasal issue resolved (was: FlightGear/Plib periodic stutter notes)</nowiki> | author = <nowiki>Andy Ross</nowiki> | date = Oct 24th, 2007 }}}} | {{FGCquote|1= Once listeners were added, scripts could be recursive: (script A sets property X which causes listener L to fire and cause script B to run) We need two or more contexts on the stack to handle that; a single global one won't work. I didn't like the fix though. Exposing the temporary bin as part of the Nasal public API is ugly; it's an internal design feature, not something users should tune. Instead, I just hacked at the FlightGear code to reinitialie this context every frame, thus cleaning it up. A "proper" fix would be to remove the global context entirely, but that would touch a bunch of code.|2= {{cite web | url = http://sourceforge.net/p/flightgear/mailman/message/15645369/ | title = <nowiki>[Flightgear-devel] Stutter/Nasal issue resolved (was: FlightGear/Plib periodic stutter notes)</nowiki> | author = <nowiki>Andy Ross</nowiki> | date = Oct 24th, 2007 }}}} | ||
The naNew() function is also implemented in misc.c, see | The naNew() function is also implemented in misc.c, see {{simgear source|path=simgear/nasal/misc.c|line=66}}: | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 633: | Line 633: | ||
'''Note:''' naGC_get() is the only function which really manages all memory pools and which triggers the GC. Allocations via naNew()* will end up calling naNew() and naNew() ends up calling naGC_get() '''always'''. | '''Note:''' naGC_get() is the only function which really manages all memory pools and which triggers the GC. Allocations via naNew()* will end up calling naNew() and naNew() ends up calling naGC_get() '''always'''. | ||
For the time being, OBJ_CACHE_SZ can be ignored, it's defined in code.h | For the time being, OBJ_CACHE_SZ can be ignored, it's defined in code.h: {{simgear source|path=simgear/nasal/code.h|line=12}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
// Number of objects (per pool per thread) asked for using naGC_get(). | // Number of objects (per pool per thread) asked for using naGC_get(). | ||
| Line 673: | Line 673: | ||
TODO: | TODO: {{simgear source|path=simgear/nasal/data.h|line=204}} | ||
* void naGC_init(struct naPool* p, int type); | * void naGC_init(struct naPool* p, int type); | ||
| Line 693: | Line 693: | ||
For each native Nasal data type (scalars, vectors, hashes, funcs etc) , there are separate memory pools in globals->pools[n]. The index (n) is one of T_VEC, T_HASH, T_FUNC etc. | For each native Nasal data type (scalars, vectors, hashes, funcs etc) , there are separate memory pools in globals->pools[n]. The index (n) is one of T_VEC, T_HASH, T_FUNC etc. | ||
The naGC_get() pool "manager" is located in gc.nas | The naGC_get() pool "manager" is located in gc.nas: {{simgear source|path=simgear/nasal/gc.c|line=211}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 717: | Line 717: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
As can be seen, the garbage collector itself is triggered by setting the global "needGC" flag to 1 in the globals structure and then calling the bottleneck() function: | As can be seen, the garbage collector itself is triggered by setting the global "needGC" flag to 1 in the globals structure and then calling the bottleneck() function: {{simgear source|path=simgear/nasal/gc.c|line=105}}. | ||
The memory region from the global pool is cast back to a pointer (struct naObj**): {{simgear source|path=simgear/nasal/gc.c|line=226}} | |||
the "nout" parameter is just there to update c->nfree[type] with the amount of free memory. | the "nout" parameter is just there to update c->nfree[type] with the amount of free memory. | ||
| Line 824: | Line 824: | ||
Whenever new memory from one of the global pools is being requested via naGC_get(), naCheckBottleneck() will also be invoked: | Whenever new memory from one of the global pools is being requested via naGC_get(), naCheckBottleneck() will also be invoked: | ||
{{simgear source|path=simgear/nasal/gc.c|line=131}} | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 837: | Line 837: | ||
[[File:NasalBottleneckCallgraph.png|thumb|550px|Callgraph of bottleneck()]] | [[File:NasalBottleneckCallgraph.png|thumb|550px|Callgraph of bottleneck()]] | ||
{{simgear source|path=simgear/nasal/gc.c|line=100}} | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
// Must be called with the main lock. Engages the "bottleneck", where | // Must be called with the main lock. Engages the "bottleneck", where | ||
| Line 862: | Line 862: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
The actual garbage collection takes place in | The actual garbage collection takes place in {{simgear source|path=simgear/nasal/gc.c|line=114|text=line 114}} where dead objects from the memory pool are freed, and the garbageCollect() function is called if globals.needGC is true. | ||
= garbageCollect() = | = garbageCollect() = | ||
| Line 870: | Line 870: | ||
This is the function that does the mark/sweep part using mark() to recursively mark reachable objects, and reap() to collect unreachable objects. | This is the function that does the mark/sweep part using mark() to recursively mark reachable objects, and reap() to collect unreachable objects. | ||
{{simgear source|path=simgear/nasal/gc.c|line=35}} | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 917: | Line 917: | ||
For each invocation of garbageCollect(), the following takes place: | For each invocation of garbageCollect(), the following takes place: | ||
* For each context: | * For each context: | ||
** The counter for each type-specific pool will be reset to 0 | ** The counter for each type-specific pool will be reset to 0: {{simgear source|path=simgear/nasal/gc.c|line=43}} | ||
** for each stack frame of the given context, all reachable locals and functions will be marked as reachable | ** for each stack frame of the given context, all reachable locals and functions will be marked as reachable: {{simgear source|path=simgear/nasal/gc.c|line=45}} | ||
** All instructions in the opcode stack will be marked as reachable from top to bottom | ** All instructions in the opcode stack will be marked as reachable from top to bottom: {{simgear source|path=simgear/nasal/gc.c|line=49}} | ||
** mark(die->Arg) | ** mark(die->Arg) | ||
** temporary variables are marked reachable | ** temporary variables are marked reachable | ||
* root references (constants) are marked reachable | * root references (constants) are marked reachable: {{simgear source|path=simgear/nasal/gc.c|line=56}} | ||
* foreach Nasal data type: | * foreach Nasal data type: | ||
** unreachable objects are then collected | ** unreachable objects are then collected: {{simgear source|path=simgear/nasal/gc.c|line=63}} | ||
* dead blocks are freed and new memory is allocated | * dead blocks are freed and new memory is allocated: {{simgear source|path=simgear/nasal/gc.c|line=67}} | ||
* the needGC flag is set to 0 | * the needGC flag is set to 0 | ||
| Line 932: | Line 932: | ||
[[File:NasalMarkCallgraph.png|thumb|400px|Callgraph of mark()]] | [[File:NasalMarkCallgraph.png|thumb|400px|Callgraph of mark()]] | ||
All reachable objects are recursively marked using tagged naRef structures | All reachable objects are recursively marked using tagged naRef structures {{simgear source|path=simgear/nasal/data.h|line=50}}, so that unreachable objects can be collected (i.e. because the reftag bit is not set) and freed. | ||
TODO: {{simgear source|path=simgear/nasal/gc.c|line=223}} | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
| Line 990: | Line 990: | ||
[[File:NasalFreeelemCallgraph.png|thumb|Callgraph of freeelem()]] | [[File:NasalFreeelemCallgraph.png|thumb|Callgraph of freeelem()]] | ||
Frees individual elements and adds freed pointers to the globals free list, implemented in gc.c: | Frees individual elements and adds freed pointers to the globals free list, implemented in gc.c: {{simgear source|path=simgear/nasal/gc.c|line=153}} | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
static void freeelem(struct naPool* p, struct naObj* o) | static void freeelem(struct naPool* p, struct naObj* o) | ||
| Line 1,009: | Line 1,009: | ||
Will be called by freelem(), implemented for all native Nasal types: | Will be called by freelem(), implemented for all native Nasal types: | ||
* strings (T_STR): naStr_gcclean | * strings (T_STR): naStr_gcclean {{simgear source|path=simgear/nasal/string.c|line=113}} | ||
* vectors (T_VEC): naVec_gcclean | * vectors (T_VEC): naVec_gcclean {{simgear source|path=simgear/nasal/vector.c|line=22}} | ||
* hashes (T_HASH): naiGCHashClean | * hashes (T_HASH): naiGCHashClean {{simgear source|path=simgear/nasal/hash.c|line=221}} | ||
* code (T_CODE): naCode_gcclean | * code (T_CODE): naCode_gcclean {{simgear source|path=simgear/nasal/gc.c|line=136}} | ||
* ghosts (T_GHOST): naGhost_gcclean | * ghosts (T_GHOST): naGhost_gcclean {{simgear source|path=simgear/nasal/gc.c|line=147}} | ||
= Contexts = | = Contexts = | ||
| Line 1,051: | Line 1,051: | ||
<references/> | <references/> | ||
Also see: | Also see: {{flightgear source|path=src/Scripting/NasalSys.cxx}} (in FGNasalSys::update) | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
| Line 1,073: | Line 1,073: | ||
[[File:NasalContextStruct.png|thumb|500px|Nasal Context structure]] | [[File:NasalContextStruct.png|thumb|500px|Nasal Context structure]] | ||
{{simgear source|path=simgear/nasal/code.h|line=76}} | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
struct Context { | struct Context { | ||
| Line 1,143: | Line 1,143: | ||
= Stack frames = | = Stack frames = | ||
{{simgear source|path=simgear/nasal/code.h|line=33}} | |||
= Tagged structures = | = Tagged structures = | ||
{{simgear source|path=simgear/nasal/data.h|line=84}} | |||
= Core allocations = | = Core allocations = | ||
All core memory allocation takes place via wrappers in | All core memory allocation takes place via wrappers in {{simgear source|path=simgear/nasal/misc.c|line=8|text=misc.c}}: | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||