On 18/10/2016 13:43, Makarius wrote:
On 17/10/16 23:58, David Matthews wrote:
Although the lack of garbage collection of code would mean that
repeatedly defining the same function would be a memory leak I would be
surprised if it was a serious problem. Is it likely that one would
repeatedly redefine the same function within a particular session?
This happens all the time in IDE interaction: things are compiled,
edited, re-compiled; thus old this become inaccessible.
You introduced that principle yourself many years ago, by providing the
very nice PolyML.Compiler interface.
That is one of the big assets of Poly/ML and consequently of Isabelle/ML.
Yes, but the actual memory needed for the function code is not going to
be large compared with the total heap size. We have heaps in the orders
of gigabytes but the whole of Isabelle is just tens of megabytes.
Perhaps I should explain why I made this change and what could be done
to mitigate the effects. There were two reasons. The first was to
simplify the code and avoid the contortions that were necessary and the
second was for security and long-term stability.
For the garbage collector to be able to compact the heap it has to be
able to find and modify all the addresses of heap cells. To do that
values are distinguished by a tag bit. If the bottom bit is set the
value is an integer and is ignored by the GC. Other values are
addresses. An address points always to the start of a cell so will be
word aligned, either XXXX00 (32-bit) or XXX000 (64-bit) in the bottom
bits. Before the start of a cell is a word containing the length of the
cell and some bits that indicate whether the cell is a tuple/vector
containing values (i.e. either tagged integers or addresses) or is byte
data, typically a string.
This is extended to cope with cells containing machine code. This is
just another type of cell. A code cell is not quite byte data because
it can contain addresses if there are values that are compile-time
Provided we're dealing with the entry point addresses of code cells this
all works fine. The complication comes when the code is actually
executed. If one function calls another, or even itself recursively, it
uses the X86 CALL instruction. It is important to use this instruction
and not try to do the function call any other way because among other
things the prefetching hardware recognises CALL/RET pairs. The CALL
instruction pushes the return address, the address of the next
instruction, to the stack.
This, though, causes problems for the GC. Return addresses are
inherently addresses into the middle of cells. They are also on an
arbitrary alignment since X86 instructions are not aligned in any way.
For the GC to be able to compact the heap it has to be able to find and
update the return addresses. If Poly/ML used "stack frames" it might be
possible to find return addresses using the frame pointer register but
using frame pointers requires an extra register and increases the cost
of every function call. Instead the code-generator added no-op
instructions before each CALL such that the return address after the
instruction was on a word+2 byte alignment i.e. XXX10 in the bottom
bits. This is neither an integer nor a word address so the GC can
recognise these as return addresses. There is still the problem of
finding the actual start of the code cell and to do this there is a zero
word at the end of each code cell. That requires that the
code-generator never generates a full word of zeros anywhere else in the
code, or at least not on a word boundary, so there are a few constraints
on the code to ensure that is the case.
Removing the code from the normal heap and using a separate, non-garbage
collected area means that these contortions are no longer needed. The
length word is retained since it is needed when copying the code to an
object file or saved state and when loading from a saved state.
The other reason for making the change is that having the code cells in
the normal heap requires the heap to be given read, write and execute
permissions. This is a problem for security and I was concerned that a
future operating system update might ban the use of both write and
execute permissions on the same area of memory. I think this is already
an issue with SELinux. Using a separate "code" area avoids this.
Although the code area needs to be writable to add new code cells to it
there are tricks that can be used to get round this.
It might be possible to use a non-compacting GC on the code area i.e. to
mark code cells that are no longer reachable and then reuse the space.
That can lead to fragmentation but would reduce the memory leak. In
almost all cases a code cell that is reachable will have at least one
address in the heap that points at the start. It is, though, possible
to construct pathological cases where the only reference is through a
return address. We're not going to change the return address since
we're not compacting so it might be possible to get round that by
assuming that any value on the stack that looks like it might be a
return address is a sufficient reason to keep the code cell, even if it
is actually an integer.
Sorry that's been rather long but I wanted to put on record the thinking
behind the change and maybe get some other ideas.
polyml mailing list