[Caml-list] Freeing dynamically loaded code

[Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

So, I went down the dirty depths of Dynlink and friends, and bytecomp
and byterun, and all that - and I think I have a rather good image of
the problem.

I would wish for Dynlinkable code to be garbage collected.
==========================================================

When a file is loaded with Dynlink.loadfile, most of what's read and
executed and handled is stored in the normal OCaml heap - and hence
garbage collected properly when there are no references anymore.

But, the actual executable code isn't. Basically what is done to that
is that the buffer is allocated by Meta.static_alloc, the code is read
there, and then Meta.reify_bytecode is invoked on it - which merely
wraps the pointer in a Closure_tag block it allocates.

So, this means that the code is allocated outside Ocaml heap - and as
such ignored by the garbage collector. Huge thanks to Olivier Andrieu
for helping me out in IRC sorting out this stuff.

What could be done to fix the situation then?
=============================================

I can think of two solutions, neither sound too easy right now though.

The first choice would be to add the statically alloced block to a
"special" list of code blocks - and when the garbage collector
encounters references to blocks outside Ocaml heap, it would handle
these blocks specially and manually free them when there are no
references - a bit like custom blocks, but having it all implicit,
since there's no block header or anything.

The problem is that closure code pointers into the statically
allocated block most likely will not point to the beginning of it -
but instead somewhere inside the allocated block. Which would mean
that the garbage collector would have to check if the pointer is
*inside* a certain range, or somehow add all possible pointer places
from inside the block with annotations of the start of the block to
the list. And both sound rather horrible in many ways.

The second choice would be to allocate all of the code actually inside
the Ocaml heap somehow, and let the garbage collector handle it like
everything else. But right now I don't have too good of an idea how
this should be done.

And it also has the same problem - what to do with pointers that fall
inside the code block, and not at the start of it where the headers
are. I see there's some code for Infix tags, which look like they
would be tags inside blocks that tell where the actual block header
lies - but this was starting to go quite a bit over my comprehension.

Ofcourse there's a bunch of "yet another choices" - like making a
special area for loaded code, and special-case that once again - and
so on.

===

So, I'd very much like to hear any comments on the matter - I am still
very new to Ocaml, so I'm way over my head here.

- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Alain.Frisch]

On Fri, 12 Dec 2003, Nuutti Kotivuori wrote:

> I would wish for Dynlinkable code to be garbage collected.

I submitted a similar feature wish to the caml team a while ago
(in french:
http://caml.inria.fr/bin/caml-bugs/wish%20not%20granted?id=445
)

The request has been transferred to the "wish not granted" section of the
BTS with the comment "Too hard to implement.  No can do.", so I'm afraid
there is no hope to see unloading/garbage collection of dynlink'ed code in
the near future.

-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Alain Frisch wrote:
> On Fri, 12 Dec 2003, Nuutti Kotivuori wrote:
>
>> I would wish for Dynlinkable code to be garbage collected.
>
> I submitted a similar feature wish to the caml team a while ago
> (in french:
> http://caml.inria.fr/bin/caml-bugs/wish%20not%20granted?id=445)

So it seems :-)

My french knowledge is close to nil, but with the advances of
babelfish and creative reading, I think I was able to catch most of
that.

> The request has been transferred to the "wish not granted" section
> of the BTS with the comment "Too hard to implement.  No can do.", so
> I'm afraid there is no hope to see unloading/garbage collection of
> dynlink'ed code in the near future.

Well, like Xavier Leroy said at the end of the mail - *he* probably
isn't doing it. That doesn't mean there wouldn't be someone else crazy
enough to try :-)

And atleast I'm not dropping the investigation just yet. But expect no
commitment ofcourse, I might grow disinterested in the matter any
moment and just leave it. Or I might just settle for a workaround of
manually freeing the blocks after ensuring there are no external
references.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Alain.Frisch]

On Fri, 12 Dec 2003, Nuutti Kotivuori wrote:

> Well, like Xavier Leroy said at the end of the mail - *he* probably
> isn't doing it. That doesn't mean there wouldn't be someone else crazy
> enough to try :-)
>
> And atleast I'm not dropping the investigation just yet.

Thinking again about the technical challenge (put the dynlink'ed code
under GC control), I think the following approach is worth a try.

The question is how to let the GC know that the code block cannot be freed
as long as there is some accessible closure pointing into this block. We
can think of using something similar to InfixTag, but this is a heavy
solution as it requires to modify the GC in many places.

I propose to avoid creating "bad" closures that points to the loaded code.
We simulate a bad closure by a closure to a generic stub. In addition to
the normal environment, we put two additional slots into this closure: a
pointer to the code block and an offset. This closure is fully under the
control of the GC. The stub is made of a single instruction (or maybe two,
see next paragraph), say a new bytecode CALL_DYN, which computes the real
destination from the closure and jumps to it. We also need a new
CLOSURE_DYN bytecode that behaves as CLOSURE but create a faked closure
instead of a bad one. Dynlink changes CLOSURE to CLOSURE_DYN when it loads
a module. We need to take care of GRAB, RESTART and CLOSUREREC similarly.

We also need to make sure that the "active" code blocks (the ones which
have an active stack frame) are accessible by the GC. We have to be
careful since the faked closure may become inacessible even if it
is currently running (because of an in-place modification). So CALL_DYN
should keep its closure on the stack (which contains a pointer to the
code block) and call the real function. The bytecode following CALL_DYN
would just pop the closure after the function returns.

These changes does not affect the GC at all, and are simple additions to
the bytecode interpreter (interp.c). The cost of calling closures to
dynlink'ed modules is increased, but we don't really care since:
1) this is bytecode, so anyway ...
2) non dynlink'ed code is not affected at all


Any comment on this?

  Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Alain Frisch wrote:
> I propose to avoid creating "bad" closures that points to the loaded
> code.  We simulate a bad closure by a closure to a generic stub. In
> addition to the normal environment, we put two additional slots into
> this closure: a pointer to the code block and an offset. This
> closure is fully under the control of the GC. The stub is made of a
> single instruction (or maybe two, see next paragraph), say a new
> bytecode CALL_DYN, which computes the real destination from the
> closure and jumps to it. We also need a new CLOSURE_DYN bytecode
> that behaves as CLOSURE but create a faked closure instead of a bad
> one. Dynlink changes CLOSURE to CLOSURE_DYN when it loads a
> module. We need to take care of GRAB, RESTART and CLOSUREREC
> similarly.

Hmm. Quite ingenious. I read through the CLOSURE and CLOSUREREC calls
and considered modifying those when linking, but never came up with a
proper solution. That sounds like it.

> We also need to make sure that the "active" code blocks (the ones
> which have an active stack frame) are accessible by the GC. We have
> to be careful since the faked closure may become inacessible even if
> it is currently running (because of an in-place modification). So
> CALL_DYN should keep its closure on the stack (which contains a
> pointer to the code block) and call the real function. The bytecode
> following CALL_DYN would just pop the closure after the function
> returns.

Right. If we are unlucky, there might be some other places around the
code where code is expected to be around without registering
references to it.

> These changes does not affect the GC at all, and are simple
> additions to the bytecode interpreter (interp.c).

Yeah, sounds good.

> The cost of calling closures to dynlink'ed modules is increased, but
> we don't really care since:

> 1) this is bytecode, so anyway ...
> 2) non dynlink'ed code is not affected at all

Actually... I think we might care. If I didn't misunderstand
something, this does not only change the calls *to* dynlink'ed
modules, but for *every* call of a function inside that dynlink'ed
module. And since function calls do not seem to be inlined in bytecode
at all, this might seriously affect performance. But, this is mere
speculation as I don't really know the function call overhead in
bytecode, nor how much it would be increased by this.

But if it is a problem - I'm not sure how to avoid it. Internal
closure calls inside the code-file do not need this hackery, but
separating those closures that are to be called from the outside
doesn't seem trivial. The external closure pointers held will be
either closures stored in the module interface posted with SETGLOBAL,
or just closure pointers given as parameters to external closures - or
is there still something else?

I'm not sure of your needs for this - but for me it would be no
problem to for example require special compilation flags for
dynlinkable files, and require special syntax or something for
declaring exported closures - as long as safety is preserved, that a
file is actually incapable of giving out closures that would break in
GC.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[skaller]

On Sat, 2003-12-13 at 08:26, Alain.Frisch@ens.fr wrote:
> On Fri, 12 Dec 2003, Nuutti Kotivuori wrote:
> 
> > Well, like Xavier Leroy said at the end of the mail - *he* probably
> > isn't doing it. That doesn't mean there wouldn't be someone else crazy
> > enough to try :-)
> >
> > And atleast I'm not dropping the investigation just yet.
> 
> Thinking again about the technical challenge (put the dynlink'ed code
> under GC control), I think the following approach is worth a try.
> 
> The question is how to let the GC know that the code block cannot be freed
> as long as there is some accessible closure pointing into this block.

That is not enough. It is not necessary for some code to be
active in order that it may later *become* active as
a result of a subroutine call or jump. It would be necessary
to find all code addresses and which blocks they point to,
and build a dependency graph, and add the roots of that graph
to the gc memory graph as well.

Otherwise, after you say

	#load xxxx

the collector would immediately free it :-)


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

skaller@ozemail.com.au wrote:
> That is not enough. It is not necessary for some code to be
> active in order that it may later *become* active as
> a result of a subroutine call or jump. It would be necessary
> to find all code addresses and which blocks they point to,
> and build a dependency graph, and add the roots of that graph
> to the gc memory graph as well.
>
> Otherwise, after you say
>
> 	#load xxxx
>
> the collector would immediately free it :-)

Actually no. The way to access code that is not "active" as you say,
is through global variables. Eg. if you do

   #load "test.cmo"

then there's an entry Test in the global table that holds pointers for
all functions defined in that file. And the global table is inside the
ocaml heap, so those all will be referenced.

The only way for that to become unloaded is that the global Test is
replaced or removed by something - either by some unload module or
loading a newer source on top of it - and then no references point to
Test. And if no references point to the file, it really cannot be
accessed anymore by any means, and hence can be removed.

Ofcourse, right now there might be also other external references to
the code in the heap, I am not sure - but those would have to be
either removed or made Weak somehow. But that is to be solved after
this immediate problem is resolved.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Nuutti Kotivuori wrote:
> Alain Frisch wrote:
>> I propose to avoid creating "bad" closures that points to the
>> loaded code.  We simulate a bad closure by a closure to a generic
>> stub. In addition to the normal environment, we put two additional
>> slots into this closure: a pointer to the code block and an
>> offset. This closure is fully under the control of the GC. The stub
>> is made of a single instruction (or maybe two, see next paragraph),
>> say a new bytecode CALL_DYN, which computes the real destination
>> from the closure and jumps to it. We also need a new CLOSURE_DYN
>> bytecode that behaves as CLOSURE but create a faked closure instead
>> of a bad one. Dynlink changes CLOSURE to CLOSURE_DYN when it loads
>> a module. We need to take care of GRAB, RESTART and CLOSUREREC
>> similarly.
>
> Hmm. Quite ingenious. I read through the CLOSURE and CLOSUREREC
> calls and considered modifying those when linking, but never came up
> with a proper solution. That sounds like it.

Ha!

I got it!

There was a problem I was pondering out with that suggestion. And it
was basically that the functions from the dynamically linked module
must appear as normal closures taking the appropriate number of
arguments - and yet would have to be called throug CALL_DYN - which
would mean either patching the code of *all* modules, or having an
intermediate code block which does the call to CALL_DYN. And this
didn't sound nice.

But then I got the idea.

If we are going to be mangling the bytecode anyway, why not mangle it
a bit more?

Let's make sure every closure generated from the library has an extra
local variable in it's environment, pointing to the head of the block
where that closure's code resides. This local variable need not even
be used, as long as it doesn't break the other locals in the function.

So then every closure will carry an extra local variable, and those
are seen by the garbage collector, so the main codefile will exist as
long as any of those closures do.

The bytecode manipulation might not be entirely trivial though, but
certainly seems easier than anything else we've talked about yet.

What do you think? Have I got it all wrong?

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Alain.Frisch]

On Sat, 13 Dec 2003, Nuutti Kotivuori wrote:

> There was a problem I was pondering out with that suggestion. And it
> was basically that the functions from the dynamically linked module
> must appear as normal closures taking the appropriate number of
> arguments - and yet would have to be called throug CALL_DYN - which
> would mean either patching the code of *all* modules, or having an
> intermediate code block which does the call to CALL_DYN. And this
> didn't sound nice.

I was proposing to have an intermediate code block (made of CALL_DYN).

> Let's make sure every closure generated from the library has an extra
> local variable in it's environment, pointing to the head of the block
> where that closure's code resides. This local variable need not even
> be used, as long as it doesn't break the other locals in the function.
>
> So then every closure will carry an extra local variable, and those
> are seen by the garbage collector, so the main codefile will exist as
> long as any of those closures do.

I have been considering this idea too, but I think it does'nt work: sure,
the GC won't free the code block, but it can still move it without
updating the code pointer in the closure. Maybe this can be addressed
by using a different GC tag to denote "movable" closures, so that the
GC knows that the code pointer has to be translated by the same amount
as the last slot (which is the pointer to the code block).

-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Alain Frisch wrote:
> I was proposing to have an intermediate code block (made of
> CALL_DYN).

Ah yes, I see it now. I didn't really understand your proposal fully
in the beginning. And to be honest, I still am not sure of the actual
implementation.

I'll read it once more and probably ask some questions - I have yet
another idea which might be what you mean as well, or then again it
might not be - if you have the patience for me :-)

> I have been considering this idea too, but I think it does'nt work:
> sure, the GC won't free the code block, but it can still move it
> without updating the code pointer in the closure. Maybe this can be
> addressed by using a different GC tag to denote "movable" closures,
> so that the GC knows that the code pointer has to be translated by
> the same amount as the last slot (which is the pointer to the code
> block).

You are obviously right. I didn't even consider the GC moving the
block. Well that's it for the cleanliness of that idea - if there
needs to be a new block type or touching the GD, it's not really
better than the other suggestions, except in a performance sense.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Alain Frisch wrote:
> I propose to avoid creating "bad" closures that points to the loaded
> code.  We simulate a bad closure by a closure to a generic stub. In
> addition to the normal environment, we put two additional slots into
> this closure: a pointer to the code block and an offset. This
> closure is fully under the control of the GC. The stub is made of a
> single instruction (or maybe two, see next paragraph), say a new
> bytecode CALL_DYN, which computes the real destination from the
> closure and jumps to it. We also need a new CLOSURE_DYN bytecode
> that behaves as CLOSURE but create a faked closure instead of a bad
> one. Dynlink changes CLOSURE to CLOSURE_DYN when it loads a
> module. We need to take care of GRAB, RESTART and CLOSUREREC
> similarly.

Okay, now I finally think I know what you mean. I'll try to spell it
out in a verbose manner here.

So, if a normal closure would be something like this:

                +-----+--------+-----------------+
  static alloc  | ... | <code> | ...             |
                +-----+--------+-----------------+
                          ^
                      ,---'
                      |                       
  +-------------+----------+----------+----------+
  | Closure_tag | Code_val | Field(1) | Field(2) |
  +-------------+----------+----------+----------+

This would be transformed to:

  +-------------+-----+--------+-----------------+  +--------------+
  | String_tag  | ... | <code> | ...             |  | CALLDYN...   |
  +-------------+-----+--------+-----------------+  +--------------+
        ^`-------+-------'                                 ^
        |        |                                         |
        |        `-----------------------------------------|-----.
        |             ,------------------------------------'     |
        `-------------|-------------------------------.       <offset>
                      |                               |          |
  +-------------+----------+----------+----------+----------+----------+
  | Closure_tag | Code_val | Field(1) | Field(2) | Field(3) | Field(4) |
  +-------------+----------+----------+----------+----------+----------+

And this CALLDYN instruction would do something like:

  pc = Field(env, Wosize_val(env) - 2) +
       Field(env, Wosize_val(env) - 1);
  /* env already points correctly */
  goto check_stacks;

Am I on the right track?

Now I have no idea what GRAB and RESTART do, and what would be need to
fix them. They look scary. On CLOSUREREC I have an idea what it's
supposed to do, but I have no idea how the Infix headers really work
there - and what we'd need to do to fix that.

Now, to get the file to produce these kind of wacky closures, we would
need to do a few things. First of all we'd obviously need the CALLDYN
parts allocated somewhere statically. Then, before reifying the
bytecode, we'd wish to substitute all calls to CLOSURE with
CLOSUREDYN, right? And GRABDYN, RESTARTDYN, CLOSURERECDYN if
necessary. This would mean that we would have to go through the
bytecode, pretty much like dumpobj.ml does - so we know how many
parameters each instruction takes so we can find the correct
instructions to modify. If we don't have to touch the parameters on
anything, we don't need to recalculate any jump offsets, which is
good. One thing which I am pondering though when thinking about
CLOSUREDYN calls. All the information it has is the offset of the code
to be referenced from the current position. How do we pass the
knowledge where the start of the block is where this code resides, so
it can place that pointer in the env and calculate the offset there as
well? And it can't be a global variable temporarily or anything since
every CLOSUREDYN instruction needs to create references to the
codeblock that CLOSUREDYN instruction resides in. Well, I hope this
can be solved with some hackery.

Now the open questions that I am thinking about are that is anything
bothered by having two more variables in it's env than it is expecting
to have? Does anyone look at the size of the env block? Can we
implement all of CLOSUREDYN, CLOSURERECDYN, GRABDYN and RESTARTDYN so
that they produce compatible results? What about OFFSETCLOSURE and
friends, did they do anything evil?

Though sometimes I wonder how nice it could be if *all* code would
have this calling convention. No more hacking with these special
instructions, APPLY and friends would already do it. Though the cost
would be one more word in size for closures everywhere.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Basile Starynkevitch]

On Fri, Dec 12, 2003 at 09:04:24PM +0200, Nuutti Kotivuori wrote:
> So, I went down the dirty depths of Dynlink and friends, and bytecomp
> and byterun, and all that - and I think I have a rather good image of
> the problem.
> 
> I would wish for Dynlinkable code to be garbage collected.
> ==========================================================
> 
> When a file is loaded with Dynlink.loadfile, most of what's read and
> executed and handled is stored in the normal OCaml heap - and hence
> garbage collected properly when there are no references anymore.
> 
> But, the actual executable code isn't. Basically what is done to that
> is that the buffer is allocated by Meta.static_alloc, the code is read
> there, and then Meta.reify_bytecode is invoked on it - which merely
> wraps the pointer in a Closure_tag block it allocates.
> 

Please note that for code to be GC-ed, the garbage collector has to
handle specially every closure, looking into the code pointed by the
GC, etc. This might slow down the GC significantly (given that the
pointer to code is usually in the body of the code chunk, not to its
beginning).

Also both the bytecode and the native compiler should share a common
behavior on this.

Besides, most of the runtime (including the bytecode interpreter) rely
upon the fact that code is not moved (ie remains at a fixed
address). If it was moved, the GC would have to update the code
pointer referenced in closures which would be difficult. (Also, for
moving machine code in ocamlopt, you'll have to flush -in a system
dependent way- the instruction cache, which is expensive). Not moving
code means that you cannot copy or compact it, as the GC does for most
values. 

I understand your wish (and in an ideal world I do share it) but I
also think that making code garbage collected would impact a big part
of the ocaml runtime system (and would, for example, probably make
ocaml's GC slower, even for most of the applications which don't load
any code).

FWIW, some old versions of SML/NJ (maybe 0.93...) did actually
garbage-collect and move machine code, so this is in principle doable,
but it is difficult and involve a serie of tradeoffs (different from
those of Ocaml3). Also, most of Common Lisp implementations probably
collect code (even in machine code form).

So I would believe that to make code GC-able would require a big lot
of work, and I understand that it is not currently a top priority of
the Cristal team.

Making code garbageable is a big design decision which should be done
when starting to implement a language. It cannot be made afterwards
without lot of pains.

-- 
Basile STARYNKEVITCH -- basile dot starynkevitch at inria dot fr
Project cristal.inria.fr - INRIA Rocquencourt
http://cristal.inria.fr/~starynke --- all opinions are only mine 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Basile Starynkevitch wrote:
> On Fri, Dec 12, 2003 at 09:04:24PM +0200, Nuutti Kotivuori wrote:
>> So, I went down the dirty depths of Dynlink and friends, and
>> bytecomp and byterun, and all that - and I think I have a rather
>> good image of the problem.
>>
>> I would wish for Dynlinkable code to be garbage collected.
>> ==========================================================
>>
>> When a file is loaded with Dynlink.loadfile, most of what's read
>> and executed and handled is stored in the normal OCaml heap - and
>> hence garbage collected properly when there are no references
>> anymore.
>>
>> But, the actual executable code isn't. Basically what is done to
>> that is that the buffer is allocated by Meta.static_alloc, the code
>> is read there, and then Meta.reify_bytecode is invoked on it -
>> which merely wraps the pointer in a Closure_tag block it allocates.

Thanks for your input on this matter.

> Please note that for code to be GC-ed, the garbage collector has to
> handle specially every closure, looking into the code pointed by the
> GC, etc. This might slow down the GC significantly (given that the
> pointer to code is usually in the body of the code chunk, not to its
> beginning).

Not necessarily at all - if code pointers are handled as pointers to
the start of a block and an offset, the GC can work exactly as it
did. This ofcourse introduces runtime overhead in calling closures. If
the GC is augmented to handle blocks of type Closure_tag specially,
but still so that they contain a pointer to the start of the
memoryblock as well, then there will be no runtime overhead in calling
closures, minimal overhead in garbage collection (update of two
pointers instead of one when moving a block), and only an increased
storage of one word for each closure.

> Also both the bytecode and the native compiler should share a common
> behavior on this.

Um, I believe this concerns only interpreting bytecode. We are talking
about dynamic linking - loading code at runtime. If the code is
statically loaded - there hardly is any need to garbage collect it. It
could result in small gains in code size for code parts that are
executed only once and then never again, but that's minimal. Same
thing for the native compiler - there's no need to free actual code
pages from the executable if we are running native code. And
dynamically linking nativecode - that is, taking in a .o file to a
running executable, resolving it's unresolved symbol references at
runtime, and being able to access it - doesn't seem feasible at
all. And dynamically linking native code to a bytecode executable
seems even less feasible. Dynamically loading bytecode from an
executable compiled natively with ocamlopt doesn't seem to work
directly, but Asmdynlink (part of CDK) seems to do it with some
hacking, so it shouldn't be impossible - but this should not break it
either.

So, for this thing we are *only* talking about dynamically linking
bytecode - and being able to free the code when it is no longer
required.

> Besides, most of the runtime (including the bytecode interpreter)
> rely upon the fact that code is not moved (ie remains at a fixed
> address). If it was moved, the GC would have to update the code
> pointer referenced in closures which would be difficult. (Also, for
> moving machine code in ocamlopt, you'll have to flush -in a system
> dependent way- the instruction cache, which is expensive). Not
> moving code means that you cannot copy or compact it, as the GC does
> for most values.

GC would only have to update the Code pointer in closures if that's a
plain pointer to the actual code address to jump to. If for example
_every_ closure would have a pointer to the start of an allocated
block, and an offset from it - the GC would not have to be modified at
all. The runtime cost in this case example would be two loads and an
add compared to one load.

And as already mentioned, moving machine code is not meaningful as the
code pages are not linked or allocated by us, but by the OS (or
libc/ELF runtime).

> I understand your wish (and in an ideal world I do share it) but I
> also think that making code garbage collected would impact a big
> part of the ocaml runtime system (and would, for example, probably
> make ocaml's GC slower, even for most of the applications which
> don't load any code).

Doing it only for dynamically linked bytecode, and accepting a runtime
performance cost for them compared to others, I believe it is doable
without impacting other performance at all. And the changes could be
rather well localized.

> FWIW, some old versions of SML/NJ (maybe 0.93...) did actually
> garbage-collect and move machine code, so this is in principle
> doable, but it is difficult and involve a serie of tradeoffs
> (different from those of Ocaml3). Also, most of Common Lisp
> implementations probably collect code (even in machine code form).

I believe Common Lisp is a bit different in this respect, because it
actually generates code at runtime - something that I don't think
OCaml does at all.

> So I would believe that to make code GC-able would require a big lot
> of work, and I understand that it is not currently a top priority of
> the Cristal team.

I understand. However, even if the Cristal team is not interested in
spending effort towards making this happen, for the moment, I am.

Alain Frisch and me have been discussing a possibility of implementing
this with a rather minimal change to the runtime system, without
touching garbage collection at all - or more like Alain has been
describing his idea, and I have been trying to understand.

If we can figure out the final implementation plan on this - I will
probably start implementing this rather soon.

> Making code garbageable is a big design decision which should be
> done when starting to implement a language. It cannot be made
> afterwards without lot of pains.

Yes, achieving true garbage collection on all parts of the code
without incurring a runtime cost nor making the garbage collector
exceedingly inefficient is indeed a hard thing to get proper. However,
adding limited garbage collection for some parts of the code might
still be doable.

Best wishes,
-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Jacques Garrigue]

From: Alain.Frisch@ens.fr
> > Let's make sure every closure generated from the library has an extra
> > local variable in it's environment, pointing to the head of the block
> > where that closure's code resides. This local variable need not even
> > be used, as long as it doesn't break the other locals in the function.
> >
> > So then every closure will carry an extra local variable, and those
> > are seen by the garbage collector, so the main codefile will exist as
> > long as any of those closures do.
> 
> I have been considering this idea too, but I think it does'nt work: sure,
> the GC won't free the code block, but it can still move it without
> updating the code pointer in the closure. Maybe this can be addressed
> by using a different GC tag to denote "movable" closures, so that the
> GC knows that the code pointer has to be translated by the same amount
> as the last slot (which is the pointer to the code block).

The variable doesn't need to point directly to the code block: it can
point to a finalized stub. The code is still statically allocated, but
when the stub is garbage collected the code is freed.

So this should work.
But I'm not candidate to try it :-)

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Nuutti Kotivuori wrote:

[...]

> Now I have no idea what GRAB and RESTART do, and what would be need
> to fix them. They look scary. On CLOSUREREC I have an idea what it's
> supposed to do, but I have no idea how the Infix headers really work
> there - and what we'd need to do to fix that.

Okay, I think I now know how GRAB and RESTART work, and they should be
doable. And I have a better idea how CLOSUREREC works as well - but
that seems to be nasty. Considering that it has several code pointers,
and none of those have a local environment but the whole closure only
has one - every one of those code pointers would have to point to
something like CALLRECDYN or something, and the environment of the
CLOSUREREC should have offsets for every subfunction and then the code
block address. CALLRECDYN would then have to find the correct offset
for the correct closure in the CLOSUREREC block, and call
that. Eww. But possibly doable.

Another thing which struck me. What about objects? All they have is a
virtual table as the first pointer, which carries loads of code
pointers that aren't embedded in a closure. And if we can't touch the
callers, calling any of those would have to still be compatible, so
where on earth could the actual offsets be stored then? Mucho
problems.


[...]

> How do we pass the knowledge where the start of the block is where
> this code resides, so it can place that pointer in the env and
> calculate the offset there as well?

One very hackish way to implement this would be to add a semi-global
variable to the interpreter, that has this pointer - then the calldyn
instruction could update it for the current block always, so any
closures created inside a calldyn'd instruction would have the right
pointer. Or something.

[...]

This is starting to get muddier and muddier - and not looking too
good. But I will continue thinking about the problems for now - if
something comes up that is really impossible to do, then we can just
drop this approach since it isn't going to work and move on to
something else.

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Freeing dynamically loaded code

[Nuutti Kotivuori]

Jacques Garrigue wrote:
> The variable doesn't need to point directly to the code block: it
> can point to a finalized stub. The code is still statically
> allocated, but when the stub is garbage collected the code is freed.
>
> So this should work.
> But I'm not candidate to try it :-)

Hmmmmmmmm...

So then the pointers wouldn't ever get invalid since the block is
statically allocated. And if every closure referenced the finalized
block, when the last reference goes, the block would get freed.

Then the block wouldn't be in the normal heap compaction at all - but
it would be handled as malloc handles these things. And since it's not
like we are mallocing for every local variable, but just for loading
new code files, malloc will do a rather good job at it as well.

Rather nice. Rather nice indeed.

So then, while the code is running - I would expect the current env
will always have to be traversed by the GC - and while executing
subfunctions, the old env is probably on the stack, so that's handled
as well.

Hmm. If it all works, then the only thing to ensure is that every
closure has the abstract block referenced. Grab and restart are
irrelevant, since the closures they create reference the original
closure - and the code pointers will stay valid. Closurerec can have
the pointer in the local environment as well. That leaves us with
objects, which would have to have the pointer in their member
variables as well - and that shouldn't be a problem either.

So yes, can't find a damn thing wrong with that proposal. Now the
problem is just to get the variables there, either by mangling
bytecode, or the interpreter.

Thanks for the suggestion, I'll look into it!

-- Naked

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners