5 ms·

Could anyone explain the "self-healing" algorithm in simplistic terms? From what I gathered, when they compact a page of memory, moving all the objects within

by vsingh 16y ago

Could anyone explain the "self-healing" algorithm in simplistic terms? From what I gathered, when they compact a page of memory, moving all the objects within it to different locations, they will set a marker on all pointers to be "unset". Then, while program execution is still going on, the GC thread will be busily going through the pointers and correcting them to their new locations as necessary, then setting the marker flag. If, during this period, the executing code tries to use an unmarked pointer, a "read barrier" is hit in the VM, and the GC code corrects that pointer ("self-heals"), sets the marker, then allows execution to continue. Do I have this right? What about the initial unsetting of all these markers? It would seem to require going through all pointers before you want to compact a page, and I would suspect they're being more clever than that.

modeless 16y ago
You don't mark pointers, you unmap a page of virtual memory. This instantly invalidates all pointers to that page without touching them, and allows you to immediately reuse that physical memory by mapping it to a new virtual address. When you eventually dereference a pointer to an unmapped page the processor's MMU throws a page fault. The VM catches the fault and fixes up the pointer on the spot. What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this, and how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it.
- vsingh 16y ago
  Ah, that makes things clearer - thanks. > What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this. Me too. If you can't guarantee that, it seems that when you unmap a page of virtual memory, you'd have to make sure never to use that page again. You'd also have to keep around your table of "mappings from old pointers to new pointers" forever, just in case you encounter a lingering bad pointer and need to correct it.
  - modeless 16y ago
    Yes, exactly, in fact I was just editing my post to add that concern! Their garbage collector constantly scans the heap fixing up pointers so you don't have to wait for every reference to hit a page fault, but it seems difficult to guarantee that you're done if the program is twiddling references while the collector is doing its work. Perhaps there is also a write barrier which makes sure to never write a pointer to a collected page.
    - pdubroy 16y ago
      You're probably right. Although he doesn't mention the write barrier, this is usually required for a generation GC.
    - runT1ME 16y ago
      Most Generational GC's (including Hotspots, which is the origin of Azul's JVM) will have the JIT insert a write barriers for all pointer sets. This is to keep track of cross generational references (so you don't have to scan the entire heap). The hard part has always been dealing with reads, (which are much more common and expensive to put a software barrier around), and Azul has quite brilliantly figured a way to handle this both in their specialized hardware, and now their VM.
  - pdubroy 16y ago
    I think the trick is that after you complete the next mark phase, you have visited every possible pointer to the unmapped page.
    - modeless 16y ago
      Only if the program hasn't written a new reference to the unmapped page in that time. You need to check on writes too.
- bnoordhuis 16y ago
  > how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it. Maybe they don't. amd64 effectively has a 48-bit addressing limit. You can unmap 1,000 4K pages each second for over two years before you need to reuse a page address.
  - modeless 16y ago
    An interesting idea, but I'd imagine the tables you need to maintain to fixup pointers would become prohibitively large before you ran out of address space.
    - binaryfinery 16y ago
      Only if you had a very large number of undead per live instance.
    - bnoordhuis 16y ago
      Perhaps the VM doesn't use tables but a pointer remapping algorithm, something along the lines of (page_address * large_prime_number) mod 2^48.
      - modeless 16y ago
        The problem is you're not just moving whole pages, you're moving and compacting the objects within that page. Each object in the page has a new offset in the new page (or pages).
  - iwwr 16y ago
    So does that mean there are conceiveable advantages to using the full 64bit addressing scheme? What about 128 bits?
    - wingo 16y ago
      No, that means that only having 48 bits of physically addressable memory gives you the ability to have many times that amount of virtual memory -- and that virtual memory can be used to implement this fun page-faulting shenanigans without worrying about taking up any real memory address space. You have enough virtual memory for all your physical memory, and these tricks, and then some.
- cwp 16y ago
  The GC process does a full mark-and-sweep collection, so eventually it will have processed the entire heap. At that point, all garbage that existed when the collection started will have been collected, although new garbage will have been created by the program in the meantime. Similarly, all objects that survived the collection will have had their pointers fixed, and new objects will have had the correct pointers in the first place. The purpose of the read barrier is to allow the program to keep running while collection is happening. It lets the VM trap access to the parts of memory that the GC is working on, and do little bits of the collection algorithm in the program threads so they don't have to stop and wait for the GC thread to finish what it's doing.
  - modeless 16y ago
    I guess I don't understand how the mark phase can work while the program is running. If the program is constantly modifying references then how does the GC know when it's done marking? If the program modifies an object that's already been scanned during this mark phase, does the GC have to go back and re-scan that object? If so, then how can you guarantee the mark phase will complete without stopping the program at some point?
    - cwp 16y ago
      That's definitely the hard part. :-) From the interview: "We will find all the live objects in the heap in a single pass. We will never have to revisit any reference." So, no the GC never has to revisit any object, and it completes when it's scanned all live objects. The read-barrier is what prevents the program from interfering with the marking phase. That bit about unmapping virtual memory happens later when marked objects are being moved. As the GC walks through memory it's marking references by setting (or clearing) a bit in the pointer. Meanwhile the program goes about modifying objects by copying references - first reading them into a register and then writing them back out to the object's storage on the heap. The read triggers the read-barrier. If the reference being read has already been marked, great. If not, the trap handler marks the reference before allowing the program to continue. The write operation then writes a marked reference on to the heap, so no need for the GC thread to return to that object. Make sense?

by vsingh 16y ago

modeless 16y ago

You don't mark pointers, you unmap a page of virtual memory. This instantly invalidates all pointers to that page without touching them, and allows you to immediately reuse that physical memory by mapping it to a new virtual address. When you eventually dereference a pointer to an unmapped page the processor's MMU throws a page fault. The VM catches the fault and fixes up the pointer on the spot. What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this, and how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it.

vsingh 16y ago
Ah, that makes things clearer - thanks. > What I'd like to know is how you can guarantee that all garbage is eventually collected in a system like this. Me too. If you can't guarantee that, it seems that when you unmap a page of virtual memory, you'd have to make sure never to use that page again. You'd also have to keep around your table of "mappings from old pointers to new pointers" forever, just in case you encounter a lingering bad pointer and need to correct it.
- modeless 16y ago
  Yes, exactly, in fact I was just editing my post to add that concern! Their garbage collector constantly scans the heap fixing up pointers so you don't have to wait for every reference to hit a page fault, but it seems difficult to guarantee that you're done if the program is twiddling references while the collector is doing its work. Perhaps there is also a write barrier which makes sure to never write a pointer to a collected page.
  - pdubroy 16y ago
    You're probably right. Although he doesn't mention the write barrier, this is usually required for a generation GC.
  - runT1ME 16y ago
    Most Generational GC's (including Hotspots, which is the origin of Azul's JVM) will have the JIT insert a write barriers for all pointer sets. This is to keep track of cross generational references (so you don't have to scan the entire heap). The hard part has always been dealing with reads, (which are much more common and expensive to put a software barrier around), and Azul has quite brilliantly figured a way to handle this both in their specialized hardware, and now their VM.
- pdubroy 16y ago
  I think the trick is that after you complete the next mark phase, you have visited every possible pointer to the unmapped page.
  - modeless 16y ago
    Only if the program hasn't written a new reference to the unmapped page in that time. You need to check on writes too.
bnoordhuis 16y ago
> how you can guarantee that you've fixed up all pointers to an unmapped virtual page so you can reuse it. Maybe they don't. amd64 effectively has a 48-bit addressing limit. You can unmap 1,000 4K pages each second for over two years before you need to reuse a page address.
- modeless 16y ago
  An interesting idea, but I'd imagine the tables you need to maintain to fixup pointers would become prohibitively large before you ran out of address space.
  - binaryfinery 16y ago
    Only if you had a very large number of undead per live instance.
  - bnoordhuis 16y ago
    Perhaps the VM doesn't use tables but a pointer remapping algorithm, something along the lines of (page_address * large_prime_number) mod 2^48.
    - modeless 16y ago
      The problem is you're not just moving whole pages, you're moving and compacting the objects within that page. Each object in the page has a new offset in the new page (or pages).
- iwwr 16y ago
  So does that mean there are conceiveable advantages to using the full 64bit addressing scheme? What about 128 bits?
  - wingo 16y ago
    No, that means that only having 48 bits of physically addressable memory gives you the ability to have many times that amount of virtual memory -- and that virtual memory can be used to implement this fun page-faulting shenanigans without worrying about taking up any real memory address space. You have enough virtual memory for all your physical memory, and these tricks, and then some.
cwp 16y ago
The GC process does a full mark-and-sweep collection, so eventually it will have processed the entire heap. At that point, all garbage that existed when the collection started will have been collected, although new garbage will have been created by the program in the meantime. Similarly, all objects that survived the collection will have had their pointers fixed, and new objects will have had the correct pointers in the first place. The purpose of the read barrier is to allow the program to keep running while collection is happening. It lets the VM trap access to the parts of memory that the GC is working on, and do little bits of the collection algorithm in the program threads so they don't have to stop and wait for the GC thread to finish what it's doing.
- modeless 16y ago
  I guess I don't understand how the mark phase can work while the program is running. If the program is constantly modifying references then how does the GC know when it's done marking? If the program modifies an object that's already been scanned during this mark phase, does the GC have to go back and re-scan that object? If so, then how can you guarantee the mark phase will complete without stopping the program at some point?
  - cwp 16y ago
    That's definitely the hard part. :-) From the interview: "We will find all the live objects in the heap in a single pass. We will never have to revisit any reference." So, no the GC never has to revisit any object, and it completes when it's scanned all live objects. The read-barrier is what prevents the program from interfering with the marking phase. That bit about unmapping virtual memory happens later when marked objects are being moved. As the GC walks through memory it's marking references by setting (or clearing) a bit in the pointer. Meanwhile the program goes about modifying objects by copying references - first reading them into a register and then writing them back out to the object's storage on the heap. The read triggers the read-barrier. If the reference being read has already been marked, great. If not, the trap handler marks the reference before allowing the program to continue. The write operation then writes a marked reference on to the heap, so no need for the GC thread to return to that object. Make sense?