[cap-talk] small notes re: waterken
Raoul Duke
while reading through
http://www.hpl.hp.com/techreports/2010/HPL-2010-89.pdf
(a) the argument that RMI takes 2 round-trips vs. Waterken taking 1
seems like over-selling since the difference is really afaics one
single message. (the bit about asynchronousitude is separate.)
(b) when i tried
https://sha-256-hl6w2x74ixy6pi5n.yurl.net:4445/-/tutbucks/#s=ashzre7yp5wauo
of course the first thing i tried was to take out more than was in the
purse in the first place -- that doesn't seem to have been handled
well ;-)
sincerely.
_______________________________________________
cap-talk mailing list
cap-...@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/cap-talk
Raoul Duke
> (so far, not done yet... :-)
ok done, with the following additional thoughts/questions/worries :-)
* don’t like the asymmetries e.g. manually marking promises but not proxies.
* don’t like Serialized interface, what about upgrades in either
the app or the jvm?
* why is PurseX.deposit() not a transaction?
* casting from interface to concrete type smells like a java
anti-pattern. certainly don’t want to have to do that to get security.
* do when/transactions compose well like stm?
* i don't grok the overall transactional nature semantics syntax
yet, obviously
Marc Stiegler
> https://sha-256-hl6w2x74ixy6pi5n.yurl.net:4445/-/tutbucks/#s=ashzre7yp5wauo
> of course the first thing i tried was to take out more than was in the
> purse in the first place -- that doesn't seem to have been handled
> well ;-)
My choices in creating the tutorial are controversial in more than one
way, as you'll note when I reply to your second message on this
topic :-)
For this particular criticism, I actually find the behavior of the
program to be not unreasonable: it returns a broken promise for the
Purse. Aside from that, the only other alternative would be to return a
valid purse with zero balance. I can argue both ways on which one is
preferable.
Though on reflection, I'd guess you probably mean the user interface
does something weird when it gets a broken purse for the promise. Sigh.
I suppose we could upgrade the ui code shipped with Waterken.
--marcs
Marc Stiegler
> On Tue, Mar 1, 2011 at 4:35 PM, Raoul Duke <rao...@gmail.com> wrote:
> > (so far, not done yet... :-)
>
> ok done, with the following additional thoughts/questions/worries :-)
>
> * don’t like the asymmetries e.g. manually marking promises but not proxies.
Tell it to the JavaSoft people who put type erasure in the jvm; I
believe that was the reason Tyler couldn't remove the need for
Promise<T>.
>
> * don’t like Serialized interface, what about upgrades in either
> the app or the jvm?
JVM upgrades have not so far been a problem, and are unlikely to be a
problem given the strong focus on upwards compatibility in java
development. As for app upgrades, what would work better? The big issue
is, when you upgrade the app, what happens when deserializing an old
vat? Upgrade of a live persistent system is one of the great unsolved
mysteries of our time. With Java serialization, simple upgrades are
moderately simple, and some complex upgrades are possible. It falls
short of Alan Kay's requirements, but I know of nothing that works
better; doing everything by hand as in E is not an improvement :-)
>
> * why is PurseX.deposit() not a transaction?
I do not understand. PurseX.deposit(purse) is a transaction. The
checkpoint at the end of the turn captures the changes to both purse
balances; if the server crashes during the turn no checkpoint is taken
and neither purse balance is changed. If an exception could be thrown in
the middle of the turn, after one balance had been changed but the other
had not, that would be bad: a checkpoint would be taken with the one
change, and the exception would be returned in the broken promise. In
the code as it stands, the only place it can throw an exception is in
the first line with the cast operation, which does not violate the rule
that the balances must change together.
>
> * casting from interface to concrete type smells like a java
> anti-pattern. certainly don’t want to have to do that to get security.
My mechanism for achieving security here is controversial, and is the
result of a strict set of tradeoffs. The goal of the tutorial is not to
teach object capability security. The goal is to teach waterken
programming while pointing out as many cool features as I could on the
way. The first priority was that the app work correctly when used as
directed in the tutorial. Following closely on the heals of this
priority was that the code be easy to understand and that the amount of
code be absolutely minimal. Everything else comes much lower in
priority.
The objection to the code that I sympathize with most is that this
implementation only works correctly if there is only one currency in a
vat. If there are 2 currencies in the vat, then the cast operation
cannot distinguish between the currencies. This could be fixed with a
mere 3 additional lines of code. But those 3 lines would require an
obscure explanation of why they were required for security. So those 3
lines would have violated both priorities 2 and 3. Meanwhile, the code
as it stands does indeed meet priority 1, i.e., when used as specified
in the tutorial the code does work correctly.
There is also an objection that I don't deal explicitly with overflow
and underflow in the integers. This would also have violated priorities
2 and 3; meanwhile, the code as it stands does indeed meet priority 1,
i.e., when used as specified in the tutorial the code does work
correctly (the currency is endowed with a fixed amount of money at
creation that cannot be changed, rendering underflow/overflow
impossible).
I sympathize with your objection, that the cast looks like an
anti-pattern. One could implement the sealer/unsealer pattern as in the
original E purse system instead. This would, however, fiercely violate
priorities 2 and 3. More interesting, however, is that I have
reluctantly come to accept the casting technique as a legitimate
strategy for allowing different objects to hold different authorities on
one another. In Java, it takes less code, and the code is easier to
understand, than a sealer/unsealer system which is quite clumsy
(exercise for the reader: rewrite this purse in Java using a
sealer/unsealer and see how much you like the result). And though the
casting technique still makes me uncomfortable, it does indeed work
correctly when used correctly.
>
> * do when/transactions compose well like stm?
Yes. There's a delightful academic paper for someone to write some day
comparing the two.
>
> * i don't grok the overall transactional nature semantics syntax
> yet, obviously
Alas. I do not yet understand your confusion well enough to try to help.
If when you do get to the point where you understand it, you were to
still understand how you were confused and could articulate it, it would
be very helpful to all of us if you could write it up for the list
here.
Tyler Close
> On Wed, 2011-03-02 at 00:54 +0000, Raoul Duke wrote:
>> On Tue, Mar 1, 2011 at 4:35 PM, Raoul Duke <rao...@gmail.com> wrote:
>> > (so far, not done yet... :-)
>>
>> ok done, with the following additional thoughts/questions/worries :-)
>>
>> * don’t like the asymmetries e.g. manually marking promises but not proxies.
>
> Tell it to the JavaSoft people who put type erasure in the jvm; I
> believe that was the reason Tyler couldn't remove the need for
> Promise<T>.
This one is not the fault of type erasure, but of the mixed support
for virtualization in Java. For concrete types, such as String,
there's no way to create an alternate implementation that behaves like
a promise. So you have to instead use an object of type
Promise<String>. For interfaces types, the ref_send library can
dynamically construct implementations that behave like a promise. So
for an interface Foo, a promise can also be of type Foo. This is nice
since an eventual invocation is expressed in concise syntax like:
Eventual _ = ...
Deferred<Foo> fooD = _.defer();
Foo foo_ = cast(Foo.class, fooD.promise);
foo_.bar(1, "Hello World!", anotherRef);
The foo_ variable is a promise for a Foo and is also of type Foo.
For a concrete type:
Deferred<String> textD = _.defer();
Promise<String> text = textD.promise;
The text variable is a promise for a String, but is of type Promise<String>.
The asymmetry in promise types is the same asymmetry between classes
and interfaces in Java.
--Tyler
--
"Waterken News: Capability security on the Web"
http://waterken.sourceforge.net/recent.html
Karp, Alan H
> For concrete types, such as String,
> there's no way to create an alternate implementation that behaves like
> a promise. So you have to instead use an object of type
> Promise<String>.
One thing I tried was defining an interface type for each concrete type, e.g., StringHolder, IntegerHolder, etc. The tradeoff comes when you need to use the value in some way, e.g.,
IntegerHolder c = new IntegerHolder(a.get() + b.get())
or even better
IntegerHolder c = new IntegerHolder(a.plus(b))
because a and b can be promises.
Ya pays yer money and ya makes yer choice.
________________________
Alan Karp
Principal Scientist
Virus Safe Computing Initiative
Hewlett-Packard Laboratories
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-7029
http://www.hpl.hp.com/personal/Alan_Karp
Raoul Duke
> Though on reflection, I'd guess you probably mean the user interface
> does something weird when it gets a broken purse for the promise. Sigh.
> I suppose we could upgrade the ui code shipped with Waterken.
Ja. The first thing I did was use the demo UI. It seemed happy to let
me remove more than was in the purse. Later, seeing the code farther
along in the tutorial, it says an exception would be thrown which was
surprising to me since that didn't appear to be what the UI was
showing.
sincerely.
Raoul Duke
> Ya pays yer money and ya makes yer choice.
...and starts to far-off dream of using some language on the JVM other
than Java, perhaps :-)
Raoul Duke
>> * i don't grok the overall transactional nature semantics syntax
>> yet, obviously
>
> Alas. I do not yet understand your confusion well enough to try to help.
> If when you do get to the point where you understand it, you were to
> still understand how you were confused and could articulate it, it would
> be very helpful to all of us if you could write it up for the list
> here.
thanks for your replies, i am percolating them!
sincerely.
Raoul Duke
On Wed, Mar 2, 2011 at 1:41 PM, Marc Stiegler <marc.d....@hp.com> wrote:
>> * why is PurseX.deposit() not a transaction?
>
> I do not understand. PurseX.deposit(purse) is a transaction. The
> checkpoint at the end of the turn captures the changes to both purse
> balances; if the server crashes during the turn no checkpoint is taken
> and neither purse balance is changed. If an exception could be thrown in
> the middle of the turn, after one balance had been changed but the other
> had not, that would be bad: a checkpoint would be taken with the one
> change, and the exception would be returned in the broken promise. In
> the code as it stands, the only place it can throw an exception is in
> the first line with the cast operation, which does not violate the rule
> that the balances must change together.
I think:
* I forgot that processing the message/turn was single-threaded.
* But I'm still all too easily confused and probably still missing
some fundamental ah-hah or two. I thought the Purse was a proxy to
something living in another vat, so how are the 2 kept in
transactional lock-step if e.g. there is a 3rd involved? As a specific
example the 2 lines
int amount = realPurse.balance;
realPurse.balance = 0;
seem like a race, because couldn't an entirely other vat have done a
realPurse.deposit(x>0) in between, which would then be lost when the
balance is zero'd out? Related / in other words, you can still have
races and deadlock in Erlang, it is just usually at a higher level of
abstraction.
* I still fear some arbitrary runtime exception or error in there
since there's no try-catch. So it seems like there are potential, even
if far-fetched situations, that could break the
checkpoint/transactional nature. (Could there e.g. be a runtime
exception from the remotely proxied thing if the communications
channel dies part-way through the turn?)
* Trying to summarize, I think the tutorial needs to be more explicit,
even if only as an aside, about how a Java person looking at the code
could have alarm bells going off based on a Java perspective, but that
those alarm bells are (perhaps) not accurate in the Waterken world. In
other words it should sort of delineate the boundaries of the willing
suspension of disbelief that a Java person needs to employ?
sincerely.
Marc Stiegler
course, is cleaner, but it is running an interpreter on top of the jvm,
which is a pretty serious price to pay; I do not see how to make E work
with Waterken well enough to enable E to exploit the additional
reliability provided by the Waterken checkpointing protocol (I was just
recently contemplating writing a scalable data center application with
Erlang or E, and suddenly realized that I was shocked at the frightening
cost it would be to have to write all the network and node failure
handling code correctly without the Waterken protocol. I was aghast; how
could people imagine that they could live like that, and write
applications that worked?! :-).
Scala, which bids fair to be my favorite language for many applications
at this time, works well with Waterken but cannot beat the promise/proxy
problem.
--marcs
Mark S. Miller
Using a different language on the jvm would not necessarily help. E, of
course, is cleaner, but it is running an interpreter on top of the jvm,
which is a pretty serious price to pay; I do not see how to make E work
with Waterken well enough to enable E to exploit the additional
reliability provided by the Waterken checkpointing protocol
(I was just
recently contemplating writing a scalable data center application with
Erlang or E, and suddenly realized that I was shocked at the frightening
cost it would be to have to write all the network and node failure
handling code correctly without the Waterken protocol. I was aghast; how
could people imagine that they could live like that, and write
applications that worked?! :-).
Scala, which bids fair to be my favorite language for many applications
at this time, works well with Waterken but cannot beat the promise/proxy
problem.
--marcs
On Wed, 2011-03-02 at 23:04 +0000, Raoul Duke wrote:
> On Wed, Mar 2, 2011 at 2:58 PM, Karp, Alan H <alan...@hp.com> wrote:
> > Ya pays yer money and ya makes yer choice.
>
> ...and starts to far-off dream of using some language on the JVM other
> than Java, perhaps :-)
> _______________________________________________
> cap-talk mailing list
> cap-...@mail.eros-os.org
> http://www.eros-os.org/mailman/listinfo/cap-talk
_______________________________________________
cap-talk mailing list
cap-...@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/cap-talk
--
Cheers,
--MarkM
Marc Stiegler
> * I forgot that processing the message/turn was single-threaded.
>
> * But I'm still all too easily confused and probably still missing
> some fundamental ah-hah or two. I thought the Purse was a proxy to
> something living in another vat, so how are the 2 kept in
> transactional lock-step if e.g. there is a 3rd involved? As a specific
> example the 2 lines
> int amount = realPurse.balance;
> realPurse.balance = 0;
> seem like a race, because couldn't an entirely other vat have done a
> realPurse.deposit(x>0) in between, which would then be lost when the
> balance is zero'd out? Related / in other words, you can still have
> races and deadlock in Erlang, it is just usually at a higher level of
> abstraction.
Aha, yes, 2 interesting ways to get confused. Java programmers get
confused because they think there may be multiple threads. Erlang
programmers get confused for a different reason: I showed the Purse
system to a hardcore Erlang programmer once, and though he immediately
understood that the turn was single threaded, he could not understand
how this code could work across purses which are of course all separate
concurrent actors. But we are working here with vats, not actors, and
vats can (and often must) contain multiple objects that make blocking,
immediate calls to one another. We know that all the purses in the Purse
system are in the same vat because the purses are manufactured with a
"new Purse" statement, not with a "q.spawn(label, classPath, args)"
statement. All the purses share a single vat and a single thread and
make blocking immediate calls to one another.
>
> * I still fear some arbitrary runtime exception or error in there
> since there's no try-catch. So it seems like there are potential, even
> if far-fetched situations, that could break the
> checkpoint/transactional nature. (Could there e.g. be a runtime
> exception from the remotely proxied thing if the communications
> channel dies part-way through the turn?)
You are both exactly correct and wrong :-) It is right and proper to be
terrified of an exception in the middle of a turn, when the internal
state is inconsistent. Unless the code is so short and sweet that you
can do a whopping good analysis of the exception-with-inconsistency
risks, you should wrap stuff in a try catch. In practice, I do the
try-catch wrap surprisingly rarely, sometimes because I am not
disciplined enough, but usually because the part of the turn in which
the state is being modified is short and sweet even if the turn itself
is not: typical state-changing turns can be naturally expressed as a
prolog in which you are figuring something out, a set of state changes
that are short and sweet and hard to get wrong, and an epilog. Failures
in the prolog or epilog need to be handled somewhere by someone, but not
necessarily with a big wrapping try catch.
However, you cannot in Waterken get a runtime exception from the
remotely proxied thing in the channel dies. That is what the Waterken
platform is all about, masking that sort of problem. The message through
the proxy to the remote vat doesn't even get kicked off until after the
turn is over and the checkpoint is taken; if the channel is lost,
waterken doesn't come back with a result until it has fixed the problem
and gotten an answer. One of the crucial points with all these
turn-based systems (including E) is that failures of communication can
not impact the current turn. In E, you will get a broken promise for the
answer if the channel is broken. In waterken, you will get a long wait
while the channel is being re-acquired.
>
> * Trying to summarize, I think the tutorial needs to be more explicit,
> even if only as an aside, about how a Java person looking at the code
> could have alarm bells going off based on a Java perspective, but that
> those alarm bells are (perhaps) not accurate in the Waterken world. In
> other words it should sort of delineate the boundaries of the willing
> suspension of disbelief that a Java person needs to employ?
Thank you. This conversation has been helpful to me in preparing to
write another of my near-future technical reports, an introduction to
clusterken programming :-)
--marcs
Marc Stiegler
>
>
> On Wed, Mar 2, 2011 at 3:42 PM, Marc Stiegler <marc.d....@hp.com>
> wrote:
> Using a different language on the jvm would not necessarily
> help. E, of
> course, is cleaner, but it is running an interpreter on top of
> the jvm,
> which is a pretty serious price to pay; I do not see how to
> make E work
> with Waterken well enough to enable E to exploit the
> additional
> reliability provided by the Waterken checkpointing protocol
>
>
> I haven't thought about it, so I don't know if this is trivial,
> impossible, or anything in between. What problems do you foresee?
>
I no longer remember what my conclusions were during my one quick and
dirty assessment of the problem. It would be amusing to try to build the
Purse+CookieShop tutorial app using E on Waterken. If we could do that,
we would have all the hard questions answered. Alas. While this would be
fun, I'm not so sure it would be important.
--marcs
David Barbour
> More interesting, however, is that I have reluctantly come to accept
> the casting technique as a legitimate strategy for allowing different
> objects to hold different authorities on one another. In Java, it takes
> less code, and the code is easier to understand, than a sealer/unsealer
I grant there is a strong relationship between types and sealers. And
it is true that downcasting to 'open' a type is a lot easier than
mucking around with sealers (though use of sealers is far closer to
first-class). But I think there's something to be said for that bit of
extra difficulty.
The whole reason capabilities work for security is because developers
make it explicit in the code when they're granting authority. They
can reason: "I didn't explicitly give you permission XYZ via a
reference, so you don't have it."
With downcasting, the whole POLA aspect is far less clear - i.e. there
is no place in the code where you grant a 'downcasting' capability.
(For parametric ADTs, it's even worse: there isn't even a place in the
code where you explicitly amplify your rights through downcasting.
This leads easily to confused deputy problems.)
Anyhow, I don't really buy this argument that downcasting should be
considered legit.
>
> though the casting technique still makes me uncomfortable, it
> does indeed work correctly when used correctly.
My understanding is that security is about controlling damage even
when such techniques are abused.
David Wagner
> * I still fear some arbitrary runtime exception or error in there
> since there's no try-catch. So it seems like there are potential, even
> if far-fetched situations, that could break the
> checkpoint/transactional nature.
For what it's worth, I had the same reaction as I was reading this
set of email messages, so you're not the only one...
Here is one good thing about Joe-E, which (I think) takes care of one case
you might be worried about. In Joe-E, all VirtualMachineErrors are fatal.
That is important, because those errors could be thrown at any time,
for unpredictable reasons. Because Joe-E makes them fatal, I'd presume
one does not need to worry about one of them happening in the middle of a
transaction and causing state to be checkpointed in an inconsistent state.
(This includes OutOfMemoryError and StackOverflowError.)
But your general point remains. Exceptions can sometimes happen at
unexpected places in Java code, and it would be easy to overlook that
a particular piece of Java code can cause an exception to be thrown.
There are some cases that might not jump out at your eye. For example,
when using generics, ClassCastExceptions can be thrown at places you
might not expect, due to the existence of heap pollution.
Raoul Duke
> Scala, which bids fair to be my favorite language for many applications
> at this time, works well with Waterken but cannot beat the promise/proxy
> problem.
i do not know what i am talking about, but could Scala Manifests help
out at all?
sincerely.
Marc Stiegler
Joe-E to make those errors fatal?
For waterken, I've been trying to persuade tyler that Errors (as opposed
to Exceptions) should crash the server. Currently the server does
something more complicated that is quite hard to recover from.
--marcs
David Wagner
> Since Joe-E is a verifier, not a rewriter, what exactly do you do in
> Joe-E to make those errors fatal?
Joe-E statically enforces restrictions on code which ensure that:
- Joe-E code cannot catch any Error
- finally clauses are prohibited
The goal is that after an error is thrown, no Joe-E code should be able
to run. This goal is achieved in a pure Joe-E program.
In a pure Joe-E program, all that can happen is that the Error propagates
up the stack, unwinding stack frames as it goes, until it reaches the top
level and the program is terminated. No Joe-E code can execute during
this process, as the stack unwinds. As far as the Joe-E code can tell,
this is basically equivalent to killing the program as soon as the Error
is thrown.
However, there is an important caveat for programs that are constructed
as a mixture of Java and Joe-E code. Java code is not subject to these
restrictions, so Java code can catch Errors or introduce finally clauses
that might execute after an Error is thrown. Consequently, in a mixed
Java+Joe-E program, we cannot guarantee that errors are immediately
fatal, since for all we know, the Java code might catch the error.
However, if the Java code is written appropriately, then the property
that Errors are always fatal can be preserved.
My recollection is that Waterken is structured as follows: there is
a main loop, written in Java, which calls Joe-E code for each turn.
I believe there is a top-level exception handler in the main loop which
catches any exceptions or errors thrown by the Joe-E code and handles them
appropriately. I am hoping it handles VirtualMachineErrors by aborting
the turn and rolling back its state, or something else equally fatal,
rather than exposing the inconsistent state of the Joe-E code to others.
However, I haven't verified that this is indeed the case and I might be
totally confused. Hopefully Tyler can correct any mistakes in the above.
I don't know what the tradeoffs are with making Errors fatal. Perhaps the
main loop could add an exception handler that catches all Errors, so that
if an Error occurs, the turn is aborted and the state is rolled back to
that before the turn was attempted? I'm speculating wildly here...
More detail on Joe-E's handling of errors can be found here:
http://www.cs.berkeley.edu/~daw/papers/joe-e-ndss10.pdf
(Section 4.3, starting at paragraph 4)
http://www.cs.berkeley.edu/~daw/joe-e/spec-20090918.pdf
(Section 4.8)
Rob Meijer
> Raoul Duke wrote:
>> * I still fear some arbitrary runtime exception or error in there
>> since there's no try-catch. So it seems like there are potential, even
>> if far-fetched situations, that could break the
>> checkpoint/transactional nature.
>
> For what it's worth, I had the same reaction as I was reading this
> set of email messages, so you're not the only one...
>
> Here is one good thing about Joe-E, which (I think) takes care of one case
> you might be worried about. In Joe-E, all VirtualMachineErrors are fatal.
> That is important, because those errors could be thrown at any time,
> for unpredictable reasons. Because Joe-E makes them fatal, I'd presume
> one does not need to worry about one of them happening in the middle of a
> transaction and causing state to be checkpointed in an inconsistent state.
> (This includes OutOfMemoryError and StackOverflowError.)
While I believe that Joe-E indeed fixes a lot of loop-holes in Java, there
seems to be one big design flaw in Java (and any JVM dependant language,
and some other modern languages), and that is the fact that the often
praised concept of garbage collection breaks resource management. When a
language has support for (real) destructor, this enables a resource
management idiom called RAII (Resource Acquisition Is Initialization). The
usage of RAII allows the developer of a class that manages a resource (for
example a transaction) to take full responsibility for that resource. The
use of 'finally' that is often proposed as alternative ends up moving the
responsibility to somewhere it does not belong, and somewhere where it is
easy to forget about responsibility one may not even know one has.
I find it sad that garbage collection is so overvalued. One of the few
languages that got garbage collection right (python) doesn't even realize
what a gem they created by calling their way to do it 'an implementation
detail', and building a JVM based version of the language that basically
brakes the language. It is probably impossible, but if Joe-E could fix
this last big loophole in Java and provide some trustworthy destructor
like construct that enabled RAII, than Joe-E would truly have fixed Java,
and problems like discussed above could never arise.
Ben Kloosterman
> On Thu, March 3, 2011 18:33, David Wagner wrote:
> > Raoul Duke wrote:
> >> * I still fear some arbitrary runtime exception or error in there
> >> since there's no try-catch. So it seems like there are potential,
> >> even if far-fetched situations, that could break the
> >> checkpoint/transactional nature.
> >
> > For what it's worth, I had the same reaction as I was reading this set
> > of email messages, so you're not the only one...
> >
> > Here is one good thing about Joe-E, which (I think) takes care of one
> > case you might be worried about. In Joe-E, all VirtualMachineErrors are
> fatal.
> > That is important, because those errors could be thrown at any time,
> > for unpredictable reasons. Because Joe-E makes them fatal, I'd
> > presume one does not need to worry about one of them happening in the
> > middle of a transaction and causing state to be checkpointed in an
> inconsistent state.
> > (This includes OutOfMemoryError and StackOverflowError.)
>
> While I believe that Joe-E indeed fixes a lot of loop-holes in Java, there
> seems to be one big design flaw in Java (and any JVM dependant language,
> and some other modern languages), and that is the fact that the often
> praised concept of garbage collection breaks resource management. When a
> language has support for (real) destructor, this enables a resource
> management idiom called RAII (Resource Acquisition Is Initialization).
Why is this an issue in most cases the GC is trusted code and can release
memory when needed if you want to do something like RAII in .NET you just
use a using block (other resources like file handles , locks etc are
normally released in a finalizer before the current object is collected) .
The GC will release the resources at the end but may delay unless there is
an urgent need now , in the case where there is a need now a collect will
be forced ASAP freeing far more memory than the current routine.
I don't see any issue with this and in fact a GC can communicate better with
a resource manager and hand back memory when needed ( at the cost of using
more memory for normal operation)
Ben
William ML Leslie
> One of the few
> languages that got garbage collection right (python) doesn't even realize
> what a gem they created by calling their way to do it 'an implementation
> detail', and building a JVM based version of the language that basically
> brakes the language. It is probably impossible, but if Joe-E could fix
> this last big loophole in Java and provide some trustworthy destructor
> like construct that enabled RAII, than Joe-E would truly have fixed Java,
> and problems like discussed above could never arise.
The correct way to do RAII in python is to use a context manager in a
with statement; but I'm not sure I understand the perspective where
you distinguish 'with' or __del__ from finally statements here (except
in the obvious way where __del__ is unreliable because correct
implementation requires knowledge that cpython is not reasonably able
to discover, namely, a sensible order in which to call __del__ on
objects involved in cycles where such a sensible order exists). There
is one situation that you might consider a difference, namely, that
some languages permit swallowing the exception within the finally
block, which obviously has to be dealt with just as regular except
blocks are. Are there any *interesting* semantic differences?
--
William Leslie
Rob Meijer
> On 4 March 2011 19:25, Rob Meijer <capi...@xs4all.nl> wrote:
>> One of the few
>> languages that got garbage collection right (python) doesn't even
>> realize
>> what a gem they created by calling their way to do it 'an implementation
>> detail', and building a JVM based version of the language that basically
>> brakes the language. It is probably impossible, but if Joe-E could fix
>> this last big loophole in Java and provide some trustworthy destructor
>> like construct that enabled RAII, than Joe-E would truly have fixed
>> Java,
>> and problems like discussed above could never arise.
>
> The correct way to do RAII in python is to use a context manager in a
> with statement; but I'm not sure I understand the perspective where
> you distinguish 'with' or __del__ from finally statements here (except
> in the obvious way where __del__ is unreliable because correct
> implementation requires knowledge that cpython is not reasonably able
> to discover, namely, a sensible order in which to call __del__ on
> objects involved in cycles where such a sensible order exists). There
> is one situation that you might consider a difference, namely, that
> some languages permit swallowing the exception within the finally
> block, which obviously has to be dealt with just as regular except
> blocks are. Are there any *interesting* semantic differences?
>
I disagree that the correct way to do RAII in python would be to use a
context manager in a with statement. It may be the only way to do a bit of
RAII in the (broken) JVM and .NET implementation of python, but the base
use of __del__ combined with variable scope (as in C++ RAII) to me is the
correct way to do RAII without shifting undue knowledge to the user of an
object in cPython.
I distinguish that between __del__ and finaly for the reason that finaly
often braiks the principle of least knowledge while __del__ does not, and
for the reason that finaly spreads responsibility for a resource all the
way up the tree from where it is being initially acquired, thus 'finally'
in fact brakes encapsulation principles. Let me give a simple example.
Lets say Alice acquires a new Bob and a new Carol. Now Bob acquires a Dave
and Carol acquires an Eve. Now Dave acquires a resource lets say a lock.
Alice invokes a method of Carol who invokes a method of Eve and this last
method throws an exception.
With __del__, when the exception travels up, the exception will let Bob go
out of scope, bob gets destroyed, its member Dave with it. Dave's
destructo gets called and the lock will get released promptly.
Now look at the finaly solution. Dave will need a 'release' method so that
Bob can ask it to release its lock resource (should Dave know there is a
lock resource?). Bob will also need a 'release' method so that Alice can
ask Bob to ask Dave to release the lock. Now with that in place, Alice can
invoke Bob.release() in its finaly for invocation of Carol.somemethod().
This basicaly means two things to me. Alice and Bob become responsible for
resource management of a resource held by Dave. This brakes the principle
of least knowledge and makes the whole system brittle by spreading
responsibility and breaking encapsulation.
I hope the above example clarifies my argument.
Raoul Duke
> context manager in a with statement. It may be the only way to do a bit of
> RAII in the (broken) JVM and .NET implementation of python, but the base
> use of __del__ combined with variable scope (as in C++ RAII) to me is the
> correct way to do RAII without shifting undue knowledge to the user of an
> object in cPython.
word. this has bugged me about a lot of gc languages for a long time.
i asked about it wrt alice ml a while back and they were not
interested :-). the C# idiom sucks less than the java stuff, but it
still sucks vs. RAII in C++ (shudder, i said i liked something about
C++?!). clearly i'm not a vm/gc author, but as a programmer interested
in things being more correct than not, i've wanted a gc (i have to go
look at python now) that checks for zero ref-counts and frees those
then and there. if that sucks performance wise, at least do it for
those things that are tagged as being non-simple-memory-gcable
resources e.g. via the C# IDisposable interface or whatever.
sincerely.
Marc Stiegler
that reference counting has reasonable performance as long as there are
not multiple threads, in which case ref counting has serious problems.
But, oh, wait -- vats only have single threads! Ha!
--marcs
Kevin Reid
> One of the world's great gc experts, Hans Boehm, once observed to me
> that reference counting has reasonable performance as long as there
> are
> not multiple threads, in which case ref counting has serious problems.
I have heard, as a bit of semi-common surprising wisdom, that
reference counting (plus a memory allocator) is slower than a good GC
because of the overhead of adjusting the reference counts and of
managing freeing individual blocks of memory. Not true?
--
Kevin Reid <http://switchb.org/kpreid/>
James A. Donald
>> https://sha-256-hl6w2x74ixy6pi5n.yurl.net:4445/-/tutbucks/#s=ashzre7yp5wauo
sha-256-hl6w2x74ixy6pi5n.yurl.net looks like a yurl
Now if yurls were really implemented, then when the browser attempted to
access
httpy://sha-256-hl6w2x74ixy6pi5n.somedomain, what would happen is that
it would get the network address, and upon contacting the domain,
receive a public key and a rule endorsing that public key, whose sha-256
has was hl6w2x74ixy6pi5n, and from this information, together with the
information in its request, construct a shared secret,
used to encrypt subsequent communications.
This would have the considerable advantage that since no intermediate
trusted authorities are involved, the user would not see complicated
mystery error messages and would not be trained to click through those
mystery error messages, nor would the authorities be able to mim
websites by suborning one of innumerable certificate authorities that no
one has ever heard of.
That this looks like yurl implies that something is implemented, though
I suspect considerably less than a full yurl implementation. What is
actually implemented and working today?
James A. Donald
> word. this has bugged me about a lot of gc languages for a
> long time. i asked about it wrt alice ml a while back and
> they were not interested :-). the C# idiom sucks less than
> the java stuff, but it still sucks vs. RAII in C++
> (shudder, i said i liked something about C++?!). clearly
> i'm not a vm/gc author, but as a programmer interested in
> things being more correct than not, i've wanted a gc (i
> have to go look at python now) that checks for zero
> ref-counts and frees those then and there.
It seems to me that the only reliable way to have RAII
working is to destroy a variable when it goes out of scope,
and if another variable has a reference to that variable,
generate an error at that moment in the code.
This also corrects the propensity of programs written in GC
languages to develop memory leaks, due an ever growing web of
variables referencing each other.
Of course this would not play nice with closures, nor 101
other features of garbage collected languages. The RAII
idiom is a situation where you really do need to have
reliable and direct control over memory allocation, so any
attempt to support RAII in a garbage collected language is going
to be problematic.
David Barbour
> On Mar 4, 2011, at 13:41, Marc Stiegler wrote:
>
>> One of the world's great gc experts, Hans Boehm, once observed
>> to me that reference counting has reasonable performance as long
>> as there are not multiple threads, in which case ref counting has
>> serious problems.
>
>
> I have heard, as a bit of semi-common surprising wisdom, that
> reference counting (plus a memory allocator) is slower than a
> good GC because of the overhead of adjusting the reference
> counts and of managing freeing individual blocks of memory.
> Not true?
Both of your statements are true. They aren't contradictory.
Jonathan S. Shapiro
On Mar 4, 2011, at 13:41, Marc Stiegler wrote:I have heard, as a bit of semi-common surprising wisdom, that
> One of the world's great gc experts, Hans Boehm, once observed to me
> that reference counting has reasonable performance as long as there
> are
> not multiple threads, in which case ref counting has serious problems.
reference counting (plus a memory allocator) is slower than a good GC
because of the overhead of adjusting the reference counts and of
managing freeing individual blocks of memory. Not true?
David Barbour
> word. this has bugged me about a lot of gc languages for a long time.
You should avoid depending upon GC-based finalizers. Even assuming
that order of destruction isn't a problem for you, the highest
performance real-time or concurrent GCs allow a certain epsilon of
'floating' garbage that will never be collected.
>
> i've wanted a gc that checks for zero ref-counts and frees those
> then and there [...] at least do it for those things that are tagged
> as being non-simple-memory-gcable resources e.g. via the C#
> IDisposable interface or whatever.
That sounds feasible, though it is usually preferable if you know
precisely where something is freed. Some sort of linear programming
feature, i.e. where you statically prove/enforce that there is only
one thread holding the reference in one place, would be sufficient to
give you C++ idioms.
Jonathan S. Shapiro
But reference counting doesn't handle cycles. Some other mechanism - which usually turns out to be GC - is needed for that.
Jonathan S. Shapiro
On Fri, Mar 4, 2011 at 9:43 AM, Raoul Duke <rao...@gmail.com> wrote:You should avoid depending upon GC-based finalizers.
> word. this has bugged me about a lot of gc languages for a long time.
Even assuming
that order of destruction isn't a problem for you, the highest
performance real-time or concurrent GCs allow a certain epsilon of
'floating' garbage that will never be collected.
> i've wanted a gc that checks for zero ref-counts and frees those
> then and there [...] at least do it for those things that are tagged
> as being non-simple-memory-gcable resources e.g. via the C#
> IDisposable interface or whatever.
That sounds feasible...
Dan Bornstein
On Mar 4, 2011 5:33 PM, "Jonathan S. Shapiro" <sh...@eros-os.org> wrote:
>> I have heard, as a bit of semi-common surprising wisdom, that
>> reference counting (plus a memory allocator) is slower than a good GC
>> because of the overhead of adjusting the reference counts and of
>> managing freeing individual blocks of memory. Not true?
>
> For single threaded applications, it proves that most pointer copies are to temporaries, and a suitable optimizer can eliminate the up and down counting on those. For multithreaded applications this optimization is invalid, because races between the threads can cause the counts to go to zero if this optimization is undertaken.
Also, in a multi-core world, concurrent gc is one way to get at least a bit more parallel execution out of an app "for free:" Looking at the app (mutator) threads, the barrier overhead imposed by concurrent gc (e.g. write barrier prior to each salient heap update) can reasonably be expected to be much less costly than the refcount accounting overhead imposed by a refcount-based heap. And with concurrent gc, as the name implies, much/most of the heap management work can happen without any involvement from the app threads, possibly on a separate CPU core and hence not even competing with the app threads for CPU time.
-dan (to be clear, not actually a gc expert)
David Barbour
>> Even assuming that order of destruction isn't a problem for you,
>> the highest performance real-time or concurrent GCs allow a
>> certain epsilon of 'floating' garbage that will never be collected.
>
> Can you source that statement? Such a collector would, by its nature, be
> imprecise, and there are just a hoard of issues with an imprecise collector
> of any sort.
The term 'floating garbage' is sourced
http://www.memorymanagement.org/glossary/f.html
The statement that the highest performance collectors will have
'floating garbage' is based on my own research, though I should have
been more precise: I'm talking about performance in large-scale,
concurrent, real-time garbage-collection where most of the 'image' is
on disk. It is infeasible to run a sweep across all of data in such
systems. You preferentially favor collecting 'regions' that are
mostly in-cache or in-memory. But, because you collect only part of a
system at a time, you will have floating garbage. Good design can keep
floating garbage down to an epsilon (e.g. you guarantee a maximum of
10% floating garbage).
I am curious what 'hoard of issues' you anticipate. My understanding
is that the epsilon bound takes care of most issues. E.g. you can
still support real-time and bounded-space programming. The only major
problems with it I know of are: (a) you cannot depend on gc-triggered
finalizers, and (b) you might be concerned about passwords and such
hanging around too long or making it into long-term memory.
In the gc/allocation system I was designing, (a) was handled by other
design, and (b) was handled by some guarantees that small and
short-lived things are properly collected before ever making it to
disk.
>
> I'm not aware of any true-parallel concurrent and incremental collector, for
> example, that allows garbage to survive for more than two generations.
It is true that whole-memory GCs will be precise. Perhaps the
region-based variations never came up in your research?
I.e. I don't even use whole-system 'generations'. I have a couple
generations per a processor, but a processor doesn't even bother doing
a larger collection if its small collections (each processor has a
rotating nursery and 1st gen pages it 'owns') are getting the job
done. (This fits the epsilon requirement since no new floating garbage
is being introduced, but it also means that no 'old' garbage is being
destroyed.)
>
> Feasible, but you don't want it, because you don't want to take the latency
> consequences of the chain of deletes that can result from this.
Yeah, unpredictable spikes in latency are a problem for real-time
programming. You need to keep your latency spikes predictable.
Regards,
Dave
Tyler Close
> My recollection is that Waterken is structured as follows: there is
> a main loop, written in Java, which calls Joe-E code for each turn.
> I believe there is a top-level exception handler in the main loop which
> catches any exceptions or errors thrown by the Joe-E code and handles them
> appropriately. I am hoping it handles VirtualMachineErrors by aborting
> the turn and rolling back its state, or something else equally fatal,
> rather than exposing the inconsistent state of the Joe-E code to others.
> However, I haven't verified that this is indeed the case and I might be
> totally confused. Hopefully Tyler can correct any mistakes in the above.
>
> I don't know what the tradeoffs are with making Errors fatal. Perhaps the
> main loop could add an exception handler that catches all Errors, so that
> if an Error occurs, the turn is aborted and the state is rolled back to
> that before the turn was attempted? I'm speculating wildly here...
That's exactly what the Waterken server does... the Error rollback,
not the speculating wildly. ;)
As a consequence of this implementation, the source vat that
originated the call that resulted in an Error is no longer able to
successfully send any further messages to the destination vat. Other
vats can still successfully message with the destination vat. This is
useful in that a browser talking to a Waterken server vat might send a
request that causes an Error, but this won't prevent other browsers
from successfully exchanging messages with the server (modulo the DOS
issues). One case that is unfortunate is when the application itself
is buggy and so causes an Error in one of its own local asynchronous
calls. This prevents the local event queue from making further
progress. External clients can still message with the vat, but having
the local event queue permanently stalled might prevent the
application from making progress.
--Tyler
--
"Waterken News: Capability security on the Web"
http://waterken.sourceforge.net/recent.html
Tyler Close
>>> (b) when i tried
>>> https://sha-256-hl6w2x74ixy6pi5n.yurl.net:4445/-/tutbucks/#s=ashzre7yp5wauo
>
> sha-256-hl6w2x74ixy6pi5n.yurl.net looks like a yurl
>
> Now if yurls were really implemented, then when the browser attempted to
> access
> httpy://sha-256-hl6w2x74ixy6pi5n.somedomain, what would happen is that
> it would get the network address, and upon contacting the domain,
> receive a public key and a rule endorsing that public key, whose sha-256
> has was hl6w2x74ixy6pi5n, and from this information, together with the
> information in its request, construct a shared secret,
> used to encrypt subsequent communications.
>
> This would have the considerable advantage that since no intermediate
> trusted authorities are involved, the user would not see complicated
> mystery error messages and would not be trained to click through those
> mystery error messages, nor would the authorities be able to mim
> websites by suborning one of innumerable certificate authorities that no
> one has ever heard of.
>
> That this looks like yurl implies that something is implemented, though
> I suspect considerably less than a full yurl implementation. What is
> actually implemented and working today?
The Waterken server implements full YURL semantics and so for
distributed apps composed of Waterken servers talking to each other
you have the security properties described above. Much of the work
MarcS and Alan have been doing involves Waterken servers talking to
each other, so it works out for them.
The longstanding gap in the system is compatibility with the Web
browser. A Web browser will initially pop an annoying dialog when
navigating to a YURL. Even after clicking through the dialog to accept
the certificate, the browser still allows the site to be impersonated
by a certificate from a recognized CA. None of the browsers make it
easy to fix this problem, so it'll require someone sitting down for a
few weeks to crank out the needed code. Somehow, I've always had other
things higher up on the TODO list.
--Tyler
--
"Waterken News: Capability security on the Web"
http://waterken.sourceforge.net/recent.html
_______________________________________________
Rob Meijer
If I understand correctly that is also how cPython works. Reference
counting as base paradigm and gc for the very rare cases where cycles
hapen.
I feel this construct, that still allows for C++ style destructor based
RAII should be the way that object capability languages work. IMO the
principle of least authority favours destructor based RAII over 'finaly'
constructs (see my example earlier) AND favours message passing concurency
over shared state concurency. The combination of these two seems like a
good fit for using a RAII/destructor compatible cPython style way of
reference counted collection.
David Barbour
> I feel this construct, that still allows for C++ style destructor based
> RAII should be the way that object capability languages work.
I feel we should more broadly reconsider the whole notion of resource
acquisition and resource management from a security perspective. I've
said before that, rather than associating memory with 'regions', we
should instead be associating them with a 'purse'. I have a lot of
Nick Szabo's research in this area (cf.
http://szabo.best.vwh.net/scarce.html). But that research is still
immature. Even without jumping to a full market-based solution,
though, I feel we could avoid explicit 'acquire/release' patterns in
ocap systems. (They're fairly problematic for distributed programming
and orthogonal persistence in any case.)
William ML Leslie
> I distinguish that between __del__ and finaly for the reason that finaly
> often braiks the principle of least knowledge while __del__ does not, and
> for the reason that finaly spreads responsibility for a resource all the
> way up the tree from where it is being initially acquired, thus 'finally'
> in fact brakes encapsulation principles. Let me give a simple example.
>
> Lets say Alice acquires a new Bob and a new Carol. Now Bob acquires a Dave
> and Carol acquires an Eve. Now Dave acquires a resource lets say a lock.
>
> Alice invokes a method of Carol who invokes a method of Eve and this last
> method throws an exception.
>
> With __del__, when the exception travels up, the exception will let Bob go
> out of scope, bob gets destroyed, its member Dave with it. Dave's
> destructo gets called and the lock will get released promptly.
>
> Now look at the finaly solution. Dave will need a 'release' method so that
> Bob can ask it to release its lock resource (should Dave know there is a
> lock resource?). Bob will also need a 'release' method so that Alice can
> ask Bob to ask Dave to release the lock. Now with that in place, Alice can
> invoke Bob.release() in its finaly for invocation of Carol.somemethod().
> This basicaly means two things to me. Alice and Bob become responsible for
> resource management of a resource held by Dave. This brakes the principle
> of least knowledge and makes the whole system brittle by spreading
> responsibility and breaking encapsulation.
>
> I hope the above example clarifies my argument.
I see.
And yet, tying resource management to object lifetime (in the
refcounting or gc sense) is potentially confusing* and composes
awkwardly. How does Alice know that she is using this resource and
must not cache Bob? Is she expected to do that "DisTasteful =
Nothing" that you frequently see in VB code before calling other
methods that may require a resource? Idiomatically?
If Dave cannot acquire the lock as a with statement because it is
expected to be held across several calls, the appropriate interface
would be to return a closable that the caller invokes those methods
within context of.
For those situations where this sort of pattern is not possible, I
would like to have an interface to consistently access either
dynamically scoped (in the 'with' sense) or transaction scoped objects
that assist in lifecycle management of such resources. While this
approach still has some composition related overhead (you must
explicitly create a new lifecycle context when Alice is to be passed a
closure by Bob in the above example, with which he tags resources
associated with the return value, etc), it means that the programmer
is not constrained by an implicit stack discipline (inflexible B&D) or
a ref-counting algorithm (fragile and difficult to reason about). It
puts lifecycle management in the hands of the programmers.
On the other hand, that idea seems to share some symmetry with
explicit region annotation, applied to abstract resources rather than
just memory. Hard to say if it would feel just similarly complicated.
* I believe it was Tim Peters who said that __del__ is responsible for
burning more brain cells than every other python language feature
combined (including descriptors and metaclasses). From my (possibly
very biased!) circle; weakref callbacks seem to be the generally
preferred interface over __del__. Because they provide fewer and
simpler guarantees, you are forced to understand what you are doing.
Much like the difference between threads and processes or asynchronous
message sends. Where asynchronous sends force you to structure your
application, weakref callbacks force you to think about what
conditions need to be preserved when your finaliser is called.
--
William Leslie
Sandro Magi
> But reference counting doesn't handle cycles. Some other mechanism -
> which usually turns out to be GC - is needed for that.
Referencing counting is GC, but does need a cycle collection algorithm
(like Bacon's Recycler) to be "complete". Perhaps by "GC", you meant it
turns out to be "tracing", which I agree, cycle collection is a form of
local tracing.
On 2011-03-04 9:41 PM, Dan Bornstein wrote:
> Also, in a multi-core world, concurrent gc is one way to get at least a
> bit more parallel execution out of an app "for free:" Looking at the app
> (mutator) threads, the barrier overhead imposed by concurrent gc (e.g.
> write barrier prior to each salient heap update) can reasonably be
> expected to be much less costly than the refcount accounting overhead
> imposed by a refcount-based heap.
Perhaps of naive ref-counting implementations. See Bacon and Petrank's
on-the-fly ref-counting GC. Increment/decrement elision techniques
significantly improve performance, and deferred ref-counting schemes
scale fairly well in concurrent scenarios.
> And with concurrent gc, as the name
> implies, much/most of the heap management work can happen without any
> involvement from the app threads, possibly on a separate CPU core and
> hence not even competing with the app threads for CPU time.
Indeed, see "on-the-fly" GC. There are reference counting and mark-sweep
variants available. The pause times are very low (soft real-time), but
the throughput isn't quite as good as stop-the-world GCs.
Sandro
Mark S. Miller
Dan Bornstein
On Mar 5, 2011 9:18 AM, "Sandro Magi" <naas...@higherlogics.com> wrote:
> On 2011-03-04 9:41 PM, Dan Bornstein wrote:
> > Also, in a multi-core world, concurrent gc is one way to get at least a
> > bit more parallel execution out of an app "for free:" Looking at the app
> > (mutator) threads, the barrier overhead imposed by concurrent gc (e.g.
> > write barrier prior to each salient heap update) can reasonably be
> > expected to be much less costly than the refcount accounting overhead
> > imposed by a refcount-based heap.
>
> Perhaps of naive ref-counting implementations. See Bacon and Petrank's
> on-the-fly ref-counting GC. Increment/decrement elision techniques
> significantly improve performance, and deferred ref-counting schemes
> scale fairly well in concurrent scenarios.
I wasn't previously aware of that work. Thanks!
Near as I could tell from a quick skim of the paper (<http://www.research.ibm.com/people/d/dfb/papers/Paz05Efficient.pdf>), the dedcribed scheme is at best a wash compared to concurrent tracing, depending on workload.
It also doesn't seem to guarantee collection being particularly prompter, since there's always the risk of having to wait for the cycle collector before seeing memory/resources get reclaimed. I thought the point of advocating for refcounting in the context of RAII was specifically about the guarantees, so it's not clear to me what the real advantage of "on-the-fly" is, in this case.
My high-level take is that the paper shows there is still plenty of room for gc innovation, not that one technique is objectively superior.
-dan
Sandro Magi
> Near as I could tell from a quick skim of the paper
> (<http://www.research.ibm.com/people/d/dfb/papers/Paz05Efficient.pdf>),
> the dedcribed scheme is at best a wash compared to concurrent tracing,
> depending on workload.
Indeed, though the two orders of magnitude lower pause times are a great
selling point. This GC would provide hard real-time bounds for programs
executing in CPS form, though it's the sliding views and not the
ref-counting that matters here. Petrank's mark-sweep based on sliding
views has essentially the same advantages.
> It also doesn't seem to guarantee collection being particularly
> prompter, since there's always the risk of having to wait for the cycle
> collector before seeing memory/resources get reclaimed. I thought the
> point of advocating for refcounting in the context of RAII was
> specifically about the guarantees, so it's not clear to me what the real
> advantage of "on-the-fly" is, in this case.
Yes, prompt reclamation was not the goal. This sort of GC has three
advantages that I can see:
1. More efficient in tighter heaps (discussed in the paper).
2. Friendlier to virtual memory, unlike tracing. Major collections of
large heaps in tracing GC may involve lots of paging. You can imagine
how a ref-counting scheme with local cycle collection is less likely to
page in objects that are not being operated on.
3. No "stop the world", ie. mutators and collectors are all running
concurrently, resulting in very low latency (~2ms IIRC).
David Barbour
> 2) Releasing an external resource, or more generally, reliably bracketing
> arbitrary code with an acquire action and a release action.
Your "more generally" is the error in reasoning, here. Bracketing code
in this manner requires that you know, statically, the scope in which
a resource might be used. More generally, you must manage resources
where the scope for holding the resource is not statically known. For
example, the 'with(resource-controller, action)' idiom would not work
so well if some interactions with the resource wait on a promise (when
block). Data-streams are relatively common cases where the lifetime of
a resource is not known statically.
It is with these broader cases in mind that GC-triggered finalization
code (e.g. destructors or an IDisposable action) become more flexible
than try/finally and with blocks. Basically, since you lack static
knowledge for the scope of a resource, you are relying upon a GC
service to provide conservatively estimated feedback about maximum
scope of a resource.
Rob Meijer
> #2 is where I think I must be missing something. Let's take the familiar
> case of opening a file to get a stream, doing stuff with the stream, and
> then reliably closing the stream when we're done with it, whether by
> normal
> or exceptional exit. I understand how to code this in RAII. But why isn't
> the following just as good in a language without RAII:
>
> The equivalent of defining a given RAII abstraction:
>
> ? def withInputStream(file, func) {
> > def stream := file.inputStream()
> > try {
> > return func(stream)
> > } finally {
> > stream.close()
> > }
> > }
>
> The equivalent of using it:
>
> ? withInputStream(<file:index.html>, fn stream { stream.available() })
> # value: 1510
>
> where "stream.available()" is an example of "arbitrary code that uses the
> stream", as one might have coded in a C++ RAII block.
>
> I did see a comment in this thread that try/finally isn't as good as RAII,
> but I don't understand why. What am I missing?
What I think you may be missing is the combination with 'encapsulation'
that I tried to give an example of. Lets say your file handle resource is
a deeper encapsulated resource. With RAII the knowledge that there is a
file resource that needs closing stops with the file class. Once an object
with a deeply encapsulated resource goes out of scope 'close()' will get
invoked on the file handle. With 'finaly', the close() method will need to
be copied by the encapsulating object and any object encapsulating the
encapsulating object, etc.
James A. Donald
> The equivalent of defining a given RAII abstraction:
>
> ? def withInputStream(file, func) {
> > def stream := file.inputStream()
> > try {
> > return func(stream)
> > } finally {
> > stream.close()
> > }
> > }
>
> The equivalent of using it:
>
> ? withInputStream(<file:index.html>, fn stream {
> stream.available() }) # value: 1510
>
> where "stream.available()" is an example of "arbitrary code
> that uses the stream", as one might have coded in a C++
> RAII block.
>
> I did see a comment in this thread that try/finally isn't
> as good as RAII, but I don't understand why. What am I
> missing?
In your example there is only one resource, and not much
code, so it is easy to make sure that for the one open, there
is always the one close.
Suppose, however, there are thousands of files each
containing thousands of lines of code and hundreds of
resources written by hundreds of people over a period of a
decade or two.
Suppose your code, your little procedure that runs for a few
milliseconds in a gigantic program written by hundreds of
people that runs for weeks at a time, grabs a mutex. Then
something unexpected and bad happens, possibly in a routine
written by someone else years ago, which routine does all
sorts of strange stuff unknown to you. Whatever your code
was doing is now aborted, so obviously the mutex has to be
released. An exception is thrown, possibly in someone else's
code, and handled at much higher level in the code, also
someone else's code - a high level in the code that cannot
possibly know whether the mutex was grabbed or not, and
should not even know that the mutex exists.
Dan Bornstein
> Yes, prompt reclamation was not the goal. ["On-the-fly" refcounting] GC has three
> advantages that I can see: [...]
> 2. Friendlier to virtual memory, unlike tracing.
This isn't clear to me. A generational copying tracing gc (I think
that's a reasonably accurate, if glib, description of the dominant gc
paradigm) has pretty friendly virtual memory behavior.
> Major collections of
> large heaps in tracing GC may involve lots of paging.
My impression is that the "on-the-fly" cycle collection work would
involve similar amounts of memory access.
> 3. No "stop the world", ie. mutators and collectors are all running
> concurrently, resulting in very low latency (~2ms IIRC).
State-of-the-art concurrent tracing collectors are nearly pauseless as
well. For example, my understanding is that the much-lauded Azul gc
only pauses one thread at a time, and only to do a root set scan. My
impression is that such pauses are in the low-to-fractional msec range
on Azul's hardware.
At the other end of the sophistication scale, as of the Gingerbread
release (late 2010), Dalvik (the application-running virtual machine
that the Android project uses) includes a fairly straightforward
non-generational concurrent tracing gc. On currently produced Android
hardware — which is quite wimpy compared to modern desktop / server
hardware — we see typical "stop the world" pause times in the 2–4msec
range (with two such pauses per full heap trace[*]), and the high end
of that is usually because the process got preempted during the pause.
-dan
[*] The first pause is to queue up the root set. The second pause is
to scan the "card table" and rescan any memory that experienced
pointer updates during the concurrent scan.
David-Sarah Hopwood
> Rob Meier (I think) wrote:
>>
>> While I believe that Joe-E indeed fixes a lot of loop-holes in Java, there
>> seems to be one big design flaw in Java (and any JVM dependant language,
>> and some other modern languages), and that is the fact that the often
>> praised concept of garbage collection breaks resource management. When a
>> language has support for (real) destructor, this enables a resource
>> management idiom called RAII (Resource Acquisition Is Initialization).
>
> Why is this an issue in most cases the GC is trusted code and can release
> memory when needed if you want to do something like RAII in .NET you just
> use a using block ...
I agree. A "with"/"using" construct in practice has all the advantages of
RAII, but without placing any constraints on memory management techniques.
Only a small minority of object types need timely disposal, so it is a
mistake to place constraints on the memory management by conflating disposal
with memory reclamation for all objects.
I also find a "with" construct clearer when reading code -- the use of this
construct makes it explicit that disposal at the end of the "with" scope is
a correctness requirement, whereas it is not a correctness requirement for
objects that are initialized without using "with".
> (other resources like file handles, locks etc. are normally released in
> a finalizer before the current object is collected) .
If a file handle or lock hasn't been closed or released explicitly and
is still open/acquired in its finalizer, that's an application bug, and
should be at least logged as such. There's a case for treating it as a
fatal error, so that it can't be ignored and is more likely to be caught
during testing.
--
David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com
Sandro Magi
> This isn't clear to me. A generational copying tracing gc (I think
> that's a reasonably accurate, if glib, description of the dominant gc
> paradigm) has pretty friendly virtual memory behavior.
I disagree:
http://lambda-the-ultimate.org/node/2391
> State-of-the-art concurrent tracing collectors are nearly pauseless as
> well. For example, my understanding is that the much-lauded Azul gc
> only pauses one thread at a time, and only to do a root set scan. My
> impression is that such pauses are in the low-to-fractional msec range
> on Azul's hardware.
Sure, emphasis being "on Azul's hardware". The on-the-fly collectors
have this exact behaviour without requiring special hardware, and still
exhibit an order of magnitude lower latency than even the JVM's new, and
much lauded, tunable "garbage first" algorithm.
Also, the 2ms latency of the on-the-fly was on a 550Mhz PIII, so scale
accordingly to current CPU speeds. We have at least 5.5 times more
transistors, so we're looking at < 0.5ms on current hardware.
> At the other end of the sophistication scale, as of the Gingerbread
> release (late 2010), Dalvik (the application-running virtual machine
> that the Android project uses) includes a fairly straightforward
> non-generational concurrent tracing gc. On currently produced Android
> hardware — which is quite wimpy compared to modern desktop / server
> hardware — we see typical "stop the world" pause times in the 2–4msec
> range (with two such pauses per full heap trace[*]), and the high end
> of that is usually because the process got preempted during the pause.
It's not clear how to compare these times due to the differences in
architecture; how does a 1GHz Hummingbird CPU compare to the 550MHz PIII
Xeon used in the paper?
Would be nice to have these benchmarks compare cycles or instructions
instead of execution times. The former could at least give us some idea
how this scales with increasing processor speed and across architectures.
I suspect the low pause times in the Dalvik GC are due to the different
heaps on Android devices: small applications with relatively small
heaps. But, I haven't read up on Dalvik's GC, so perhaps the difference
isn't as significant as I believe.
In any case, for soft real-time purposes, as long as you can guarantee
less than ~3ms, I think it's generally good enough for audio work, which
is a pretty demanding domain.
Sandro
Mark S. Miller
David-Sarah Hopwood
> On Sat, March 5, 2011 18:52, Mark S. Miller wrote:
>
>> #2 is where I think I must be missing something. Let's take the familiar
>> case of opening a file to get a stream, doing stuff with the stream, and
>> then reliably closing the stream when we're done with it, whether by
>> normal
>> or exceptional exit. I understand how to code this in RAII. But why isn't
>> the following just as good in a language without RAII:
>>
>> The equivalent of defining a given RAII abstraction:
>>
>> ? def withInputStream(file, func) {
>> > def stream := file.inputStream()
>> > try {
>> > return func(stream)
>> > } finally {
>> > stream.close()
This is wrong because 'stream.close()' may throw an exception that would
replace an exception thrown by 'func(stream)', but that's a general problem
with "finally" and is easily fixed.
>> > }
>> > }
>>
>> The equivalent of using it:
>>
>> ? withInputStream(<file:index.html>, fn stream { stream.available() })
>> # value: 1510
>>
>> where "stream.available()" is an example of "arbitrary code that uses the
>> stream", as one might have coded in a C++ RAII block.
>>
>> I did see a comment in this thread that try/finally isn't as good as RAII,
>> but I don't understand why. What am I missing?
>
> What I think you may be missing is the combination with 'encapsulation'
> that I tried to give an example of. Lets say your file handle resource is
> a deeper encapsulated resource. With RAII the knowledge that there is a
> file resource that needs closing stops with the file class. Once an object
> with a deeply encapsulated resource goes out of scope 'close()' will get
> invoked on the file handle. With 'finaly', the close() method will need to
> be copied by the encapsulating object and any object encapsulating the
> encapsulating object, etc.
That's not a problem. close() has side-effects and therefore should always be
performed explicitly. If some outer resource holds a reference to an inner
resource, then the correct point at which to dispose the inner resource
will depend on the outer resource's specification. It is not necessarily
the case that the inner resource should be disposed when the outer resource
is (but if that *is* the case, it's trivial to do so explicitly). If the
application forgets about the outer resource without disposing it, that's
an application bug. If the outer resource forgets about the inner resource
without disposing it, that's a bug in the implementation of the outer
resource.
In any case, RAII only handles the cases that are trivial. The resource
leaks that are problematic in practice are those for resources with dynamic
lifetimes where RAII doesn't help.
David-Sarah Hopwood
> Suppose your code, your little procedure that runs for a few
> milliseconds in a gigantic program written by hundreds of
> people that runs for weeks at a time, grabs a mutex. Then
> something unexpected and bad happens, possibly in a routine
> written by someone else years ago, which routine does all
> sorts of strange stuff unknown to you. Whatever your code
> was doing is now aborted, so obviously the mutex has to be
> released.
No, not obviously!
Not releasing the mutex will cause a deadlock if any other code
tries to acquire that resource, which is a better failure mode
than releasing the mutex for a resource that is in an inconsistent
state. The mutex was there for a reason; attempting to use the
object after the failure may cause a much worse failure.
It is possible to do better than causing a deadlock, but silently
releasing the mutex is certainly the wrong thing.
David-Sarah Hopwood
I don't think that this composability argument is valid:
Define a "resource" to be an object abstraction that requires explicit
disposal. That is, the correctness of the application depends on choosing
precisely when the object is disposed. For example, if a file handle is
opened for writing, then closing the handle will flush buffered writes,
and it is (almost always) important for that to be done at a particular
time.
Suppose that we have an outer object that is not a resource, but which
holds a reference to an inner resource. Then I claim that either:
a) the classification of the outer object as a non-resource was incorrect,
because it does require explicit disposal, or
b) the point at which the inner object should be disposed is not the
point at which the outer object goes out of scope, but some earlier
point in the lifetime of the outer object.
In case a), the application needed to be aware of when the outer object
should be disposed; it is wrong for it to be disposed implicitly by RAII
(in the sense that it would lead to error-prone and unmaintainable code).
In case b), RAII disposes the inner object too late.
So I think that we cannot avoid classifying each object abstraction as
a resource or non-resource as part of its specification; it is not an
implementation detail.
James A. Donald
> In any case, RAII only handles the cases that are trivial.
Most resource allocation bugs *are* trivial.
James A. Donald
> On 2011-03-06 01:09, James A. Donald wrote:
>> Suppose your code, your little procedure that runs for a few
>> milliseconds in a gigantic program written by hundreds of
>> people that runs for weeks at a time, grabs a mutex. Then
>> something unexpected and bad happens, possibly in a routine
>> written by someone else years ago, which routine does all
>> sorts of strange stuff unknown to you. Whatever your code
>> was doing is now aborted, so obviously the mutex has to be
>> released.
>
> No, not obviously!
>
> Not releasing the mutex will cause a deadlock if any other code
> tries to acquire that resource, which is a better failure mode
> than releasing the mutex for a resource that is in an inconsistent
> state.
OK then, consider the following sequence:
Lock down resource. Examine the state of the resource.
Do various things depending on the state of the resource - which things
can fail, because they involve calling other people's code, which you
have not read, and is likely to change without anyone telling you..
Update resource to reflect what has been done. Release resource.
Hard to do it without RAII. You can of course explicitly provide for
unexpected failure in your code, but you probably will not, and if you
should have provided for unexpected failure, but did not, the bug will
never be detected until after three thousand copies have shipped.
Dan Bornstein
>> only pauses one thread at a time, and only to do a root set scan. My
>> impression is that such pauses are in the low-to-fractional msec range
>> on Azul's hardware.
>
> Sure, emphasis being "on Azul's hardware". The on-the-fly collectors
> have this exact behaviour without requiring special hardware
I believe the techniques used by Azul are applicable on more
traditional CPUs. I was just trying to be specific, since, as you
pointed out explicitly, timings are going to depend on the actual CPU
(among other things).
> I suspect the low pause times in the Dalvik GC are due to the different
> heaps on Android devices: small applications with relatively small
> heaps.
That's an accurate assessment. I didn't mean to imply otherwise. A
typical Android app will have a heap size on the order of small tens
of megabytes. Over time, this will of course grow, and as the target
heap size increases, we will have to modify the gc in order to
continue to meet the other constraints.
> In any case, for soft real-time purposes, as long as you can guarantee
> less than ~3ms, I think it's generally good enough for audio work, which
> is a pretty demanding domain.
For Android, the similar thrust is to be able to do smooth user
interaction at up to 60 frames/sec, which means that each frame can
take no more than about 16msec before you start dropping frames.
[Warning: The following is pretty well off-topic.]
In case it's not clear, I'm coming at this discussion from a mostly
practical point of view. If a novel gc technique has a demonstrated
ability to do significantly better than the status quo, while still
maintaining the same API at the programmer level (that is, the same
code could run in the new environment as old), then I'm absolutely
interested in investigating it, though, for practical reasons it
wouldn't be something I'd consider pursuing seriously until it was
more thoroughly proven. (That is, Android isn't a research project.)
For Android, what we care about are app/mutator pause times (per
above), memory overhead (RAM is perennially more limited than one
would like), and overall CPU work required (increased CPU usage means
the battery gets drained faster). We don't actually care about paging,
since the Android platform doesn't use swap space (as doing so leads
to poor user experience and dead flash RAM), so that's merely an
academic point as far as I'm concerned, at least with my Android hat
on.
The surprising Android concern has to do with the treatment of heap
memory that gets shared amongst all active applications, called the
"Zygote heap" in the context of Android. This memory has a bunch of
objects in it that don't typically get written to, and the memory is
shared-copy-on-write with the expectation that most of the pages will
remain shared for the full life of a process. This arrangement is done
so that a greater number of processes can be running simultaneously
(compared to if they all had totally separate heap memory). In a
typical gc system, the gc's metadata (e.g. mark bits or refcounts) is
interspersed with the objects (e.g. in object headers), and so the
first full gc would immediately cause the entire Zygote heap to become
unshared. For Dalvik, we keep the gc metadata separate and avoid that
problem. It's as yet unclear to me if a refcount-based gc could be
made to work well with this constraint.
-dan
James A. Donald
>> Suppose your code, your little procedure that runs for a few
>> milliseconds in a gigantic program written by hundreds of
>> people that runs for weeks at a time, grabs a mutex. Then
>> something unexpected and bad happens, possibly in a routine
>> written by someone else years ago, which routine does all
>> sorts of strange stuff unknown to you. Whatever your code
>> was doing is now aborted, so obviously the mutex has to be
>> released.
> Not releasing the mutex will cause a deadlock if any other code
> tries to acquire that resource, which is a better failure mode
> than releasing the mutex for a resource that is in an inconsistent
> state. The mutex was there for a reason; attempting to use the
> object after the failure may cause a much worse failure.
Typical case: create an item and add it to the linked list. Creating
the item may fail. linking it in will not.
David Wagner
> Ok, thanks all. I think I see what I was missing. I was only considering an
> RAII initializing a stack local variable, where by itself it does seem equiv
> to try/finally. But since these can also be allocated within objects that
> are themselves destructed by RAII logic, it composes in a way that simple
> try/finally does not.
Thanks. This discussion has been fascinating.
For folks who are disagreeing with MarkM's analysis above,
here's another example to ponder:
Say some method creates a stack-allocated collection (say, a set),
and fills it with a number of objects (resources) that need to be
explicitly disposed. RAII will ensure all of the resources in the set
are destructed/disposed by the time execution leaves the method, even
if an exception occurs in the middle of the method. And in this case,
we would not say it is the responsibility of the set class to know to
dispose its elements when freed.
David Barbour
<david...@jacaranda.org> wrote:
>
> No, not obviously!
>
> Not releasing the mutex will cause a deadlock if any other code
For some values of 'better' ;-)
I think you struck an important point, there.
Full system failure is a relatively easy case - you don't have many
options. Partial failure, however, is one of the big, ongoing research
problems. We cannot assume any particular answer is 'better' in
general. You're probably used to thinking about resources such as
mutexes and file handles. But many other things can be considered
'resources': power to a tractor device, arming of a weapon, control
over a region of the video, subscriptions, et cetera. What is 'better'
may be different in each case.
Our language semantics should make it relatively easy for developers
on the resource-side to recognize when a controller-side failure has
occurred, in order that the appropriate failure and recovery policy be
executed. I find RAII semantics to be a less-than-ideal for this
purpose, as it requires the dying controller to tell the resource that
he is dying. (In Monty Python, Search for the Holy Grail, there is a
scene where a knight reads the final death-grunts from where they were
etched into the wall by its dying author. RAII reminds me of this: a
thread attempting to etch its dying actions unto its environment.)
Rob Meijer
> On 2011-03-06 02:31, Mark S. Miller wrote:
>> Ok, thanks all. I think I see what I was missing. I was only considering
>> an
>> RAII initializing a stack local variable, where by itself it does seem
>> equiv
>> to try/finally. But since these can also be allocated within objects
>> that
>> are themselves destructed by RAII logic, it composes in a way that
>> simple
>> try/finally does not.
>
> I don't think that this composability argument is valid:
>
> Define a "resource" to be an object abstraction that requires explicit
> disposal. That is, the correctness of the application depends on choosing
> precisely when the object is disposed. For example, if a file handle is
> opened for writing, then closing the handle will flush buffered writes,
> and it is (almost always) important for that to be done at a particular
> time.
I don't believe this definition is correct. 'when' is always important,
its 'before the resource is exhausted'. GC works on a single type of
resource, 'memory' and it makes disposal implicit for that resource only.
RAII in C++ is used for memory, but also for all other resources and it
makes disposal implicit (with some programming effort). With cPython
reference counted GC makes GC based memory disposal work implicitly
without programming effort, and allows for using RAII in order to make
other resources disposal implicit.
> Suppose that we have an outer object that is not a resource, but which
> holds a reference to an inner resource. Then I claim that either:
>
> a) the classification of the outer object as a non-resource was incorrect,
> because it does require explicit disposal
Using this reasoning breaks a lot of OO basics IMO.
For example, lets say we have an AbstractPriorityQue. In a GC language the
MemoryBasedPriorityQueue would be a non resource while the
FileSystemBasedPriorityQueue may be a resource. This would mean that we
should treat AbstractPriorityQue as a resource (with explicit disposal).
In fact any Abstract* would need to be treated as a resource.
I feel the implicit/explicit argument is flawed. At some level memory
needs explicit disposal. For memory RAII and GC are equivalent. GC
languages choose to make disposal implicit only for memory and not for
other resources. I think GC is a great concept, its just a big shame that
it isn't used as a generic resource management mechanism in the way that
RAII is in CPP. The use of 'finaly' and 'with' are IMHO just hacks to
compensate for the fact that GC is applied just to memory, and as I
explained above, 'finaly' breaks encapsulation principles for deep
resources.
Ben Kloosterman
> > release memory when needed if you want to do something like RAII in
> > .NET you just use a using block ...
>
> I agree. A "with"/"using" construct in practice has all the advantages of RAII,
> but without placing any constraints on memory management techniques.
> Only a small minority of object types need timely disposal, so it is a mistake to
> place constraints on the memory management by conflating disposal with
> memory reclamation for all objects.
>
> I also find a "with" construct clearer when reading code -- the use of this
> construct makes it explicit that disposal at the end of the "with" scope is a
> correctness requirement, whereas it is not a correctness requirement for
> objects that are initialized without using "with".
The other argument mentioned was exposing knowledge of descendants , in .NET anyway you implement IDisposable ( like a C++ destructor) if you have any resources and it will get called when a using block finishes , which may be long before its collected. The implementer does not need to expose any knowledge , the convention is if you have resources to automatically clean up you clean them up in Dispose ( just like a destructor in C++) and Dispose can clean up the children . You could mimic the behavior of C++ by using a "using/with" block whenever a secure RAII is desired. The only difference being the object is invalid after dispose but still in memory and access will generate an object disposed exception.
So I don’t think this is a GC issue , it is however a JVM issue.
Ben
Bill Frantz
and trying to extend RAII beyond its original use.
The contract for GC is that it will recover the space for
unreachable objects before signaling an out of space condition.
I distinctly remember a data-entry application written for the
Apple ][ in basic. It went out to lunch for several seconds
every so often to garbage collect to storage used for strings.
Nothing says that any particular unreachable object will be
collected before its space is needed, even if you call gc().
I had to look up RAII to find what it was. The Wikipedia article
mentions its use for items allocated on the stack in C++. Since
C++, like most languages, unwinds the stack as part of
processing an exception, it is clear that stack-allocated
objected are being deallocated, and that their destructors
should be called. Extending this logic to heap-allocated objects
is a bit of a reach.
Of course, these observations ignore the problem of getting
files closed, mutexes released, etc. during exception
processing. A few observations:
The issue with closing input files is AFAICS, running out of
file handles. One could imagine garbage collecting file handles,
since the only real state to preserve is the file name and
cursor. However doing it is probably a can of worms. I like
explicit closure (at EOF when reading sequentially) or treating
them like output files (below).
Output files, on the other hand, need to have their buffers
flushed etc. Except for log files, output files generally aren't
shared, so they can be registered with a "cleanup" object which
colses them after an exception.
I think that if a mutex is being held, then all bets are off.
The serialized object(s) must be assumed to be in an
inconsistant state. If they act as a cache for state stored
definitively somewhere else, they can be thrown out and
reinitialized, but this situation is rare.
---------------------------------------------------------------------------
Bill Frantz |"We used to quip that "password" is the most common
408-356-8506 | password. Now it's 'password1.' Who said
users haven't
www.periwinkle.com | learned anything about security?" -- Bruce Schneier
James A. Donald
> That is, the correctness of the application depends on choosing
> precisely when the object is disposed. For example, if a file handle is
> opened for writing, then closing the handle will flush buffered writes,
> and it is (almost always) important for that to be done at a particular
> time.
>
> Suppose that we have an outer object that is not a resource, but which
> holds a reference to an inner resource. Then I claim that either:
>
> a) the classification of the outer object as a non-resource was incorrect,
> because it does require explicit disposal, or
> b) the point at which the inner object should be disposed is not the
> point at which the outer object goes out of scope, but some earlier
> point in the lifetime of the outer object.
>
> In case a), the application needed to be aware of when the outer object
> should be disposed; it is wrong for it to be disposed implicitly by RAII
> (in the sense that it would lead to error-prone and unmaintainable code).
> In case b), RAII disposes the inner object too late.
If the resource is represented by a variable with particular scope, then
we ensure the scope of the resource with a single line of code, rather
than two lines quite distant from each other, which two lines have to be
kept in agreement, and probably will drift out of agreement as the code
gets bigger and bigger and more and more people work on the code.
William ML Leslie
This discussion started out on the assumption that some resource
lifetimes *cannot* be represented as a variable with a particular
scope. In the cases it can, a with statement is sufficient and
explicit.
It is the other cases that are interesting.
--
William Leslie
Rob Meijer
The problem with finaly/with in these cases comes with the fact that for
the finaly/with solution being a resource that requires this solution to
be used is transitive to composition. David-Sarah argues that this
transitive property is correct, I argue that it brakes encapsulation.
For these cases C++ stile RAII allows for full encapsulation of the
knowledge of the presence of deep resources.
> It is the other cases that are interesting.
The other cases are where C++ RAII also breaks down. I tried to argue that
cPython (reference counted GC) shows that a combination of reference
counted GC with RAII can be a good solution there.
William ML Leslie
> The problem with finaly/with in these cases comes with the fact that for
> the finaly/with solution being a resource that requires this solution to
> be used is transitive to composition. David-Sarah argues that this
> transitive property is correct, I argue that it brakes encapsulation.
> For these cases C++ stile RAII allows for full encapsulation of the
> knowledge of the presence of deep resources.
It does break encapsulation if you implement it as an IDisposable that
delegates dispose to its attributes; but that doesn't necessarily
solve the problems we are talking about - such as correctly sequencing
the release of resources. I don't think anyone here is advocating
that as a one-size-fits-all solution. It doesn't work when you want
to return one of those attributes from the function that will dispose
of this object, the example I gave.
>> It is the other cases that are interesting.
>
> The other cases are where C++ RAII also breaks down. I tried to argue that
> cPython (reference counted GC) shows that a combination of reference
> counted GC with RAII can be a good solution there.
It works for a certain subset of resource usage, and file usage is one
case where it has worked fairly well traditionally. But, as the zen of
python says, explicit is better than implicit. And especially where
the GC is concerned, because programmers have difficulty reasoning
about its behaviour in even small projects.
--
William Leslie
Rob Meijer
>> This discussion started out on the assumption that some resource
>> lifetimes *cannot* be represented as a variable with a particular
>> scope. In the cases it can, a with statement is sufficient and
>> explicit.
>
> The problem with finaly/with in these cases comes with the fact that for
> the finaly/with solution being a resource that requires this solution to
> be used is transitive to composition.
I just noticed, re-reading my own sentence, I had trouble parsing it
myself. So for clarity reasons let me rephrase it:
The problem with finaly/with in these cases comes from the fact that:
Being 'a resource that requires finaly/with to be used' is transitive to
Rob Meijer
An other controversial aspect of C++ that I find rather interesting with
respect to this is 'auto_ptr'. Basic consensus amongst C++ people is that
auto_ptr should mostly be avoided for the reason that a copy transfers
ownership (and is in fact a move). I think however that this property is
pretty interesting from a POLA and message passing concurrency point of
view. The fact that a copy transfers ownership (and makes the original
unusable) seems an interesting way to further reduce the problems of
shared resources. The C++ peoples dislike for auto_ptr is probably
justified, but it exposes one interesting flaw (from a POLA point of view)
in current languages: The lack of convenient 'move' semantics. I believe
the upcoming C++0x standard is somehow addressing move semantics in a way
that is probably pretty low level and incompatible with most other
languages. I'm not sure if move semantics could for example be made
compatible with GC languages at all. If it could, it might be very
interesting an addition to the least authority arsenal of o-cap languages
indeed.
I haven't thought it trough much, but possibly adding some form of move
semantics to the mix might either reduce the amount of type 2 problems or
might help in solving them. Just a wild thought.
David Barbour
> whose sha-256 has was hl6w2x74ixy6pi5n
I'm left wondering how someone fit 256 bits of hash into 80 bits of data...
Kenneth Hamer-Hodges
Although we have never met I read your mail consistently and find it constantly refreshing to have someone who can clarify complex issues as clearly as you do.
Thank you!
Ken Hamer-Hodges
_______________________________________________
Rob Meijer
wrong. At this moment I am not yet willing to accept that. I rather
believe that the below uses the wrong premise that the implicit/explicit
concept is relevant for defining what is a resource.
> David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com
David Barbour
> The problem is that IMHO if David-Sarah is right , than polymorphism is
> wrong. At this moment I am not yet willing to accept that.
I do not believe your humble opinion is correct, but perhaps you could
explain to me your logic?
Rob Meijer
release, and the property of 'being a resource' is ,as what I understand
from what David-Saray claims, transitive to composition, than any form of
polymorphism would require the assumption of 'being a resource'. This in
term would mean that each and every interface would need to include a
'release()'.
IMO this very premise is thus in sharp contrast with the base principles
of polymorphism and encapsulation. In C++ RAII shows that you can choose
for polymorphism and encapsulation by making all resources (not just
memory) release implicit, while Java without distructors and with its
'finaly' shows you can choose to distinguish between implicitly released
resources (memory) and explicitly released resources that are transitive
to composition (that is, anything (potentialy) implemented using a
resource that requires an explicit release becomes something that requires
an implicit release.
That basicaly means any abstract (interface) class would require to be
implemented somethinf like:
class Resource {
public:
void release()=0;
};
class AbstractFoo: public Resource {
public:
void someMethod(...);
};
Thus David-Sarahs claim seems to be right when we assume Java to be right
in the way it offers resource management. I however feel that the fact
that Java choose to offer resource management only for memory makes us
paying a verry large price for the automatic implicit resource management
for memory, the break down of polymorpism and encapsulation.
Ben Kloosterman
in RAII/ C++ ... And it doesn't break encapsulation / polymorphism in
general only for the specific case for resources that need to be quickly
closed ( and hence explicitly) , which for a few classes is no big deal.
Interesting that .NET has dispose at the object level and hence all objects
/ interfaces have an implementation ( which is normally empty).
I suppose this may be a bigger issue in some capability programing models as
normally it only comes up for a few things eg file handles, sql connections
, and some threading resources. Then again if Capabilities don't need to be
disposed quickly its no issue ...so this would probably be important in an
object capability design.
Ben
> Thus David-Sarahs claim seems to be right when we assume Java to be right
> in the way it offers resource management. I however feel that the fact
that
> Java choose to offer resource management only for memory makes us
> paying a verry large price for the automatic implicit resource management
for
> memory, the break down of polymorpism and encapsulation.
>
_______________________________________________
David Barbour
> If, as David-Saray claims a resource is anything that requires explicit
> release, and the property of 'being a resource' is ,as what I understand
> from what David-Saray claims, transitive to composition, than any form of
> polymorphism would require the assumption of 'being a resource'. This in
> term would mean that each and every interface would need to include a
> 'release()'.
That isn't the case. Supposing Alice holds a resource, Alice could
present Bob with an abstraction that accesses the resource but does
not expose a 'release()' authority. Under these circumstances, Alice
is holding a resource and Bob is holding some alternative service. The
property of 'being a resource', hence, is not transitive across
composition. Resources may be encapsulated by the facet pattern.
Indeed, the 'with(resource,action)' pattern that obtains the resource
but hides the facet for releasing it... is, indeed, an example of this
encapsulation, but limited to stack scope.
David-Sarah's argument is that 'being a resource' is a property of the
abstraction and protocol we are presented. I don't agree with his
particular choice of abstraction and protocol, but the underlying
position is sound. After all, the very notion of 'resource' is an
abstraction.
Rob Meijer
> If you agree with David conclusions ( and they seem correct) its also
> wrong
> in RAII/ C++ ... And it doesn't break encapsulation / polymorphism in
> general only for the specific case for resources that need to be quickly
> closed ( and hence explicitly) , which for a few classes is no big deal.
And for any interface that could for any conceivable or unconceivable way
be implemented in such a way that it uses such a resource internaly. So if
you accept David-Sarah's premise, this basically means that either:
1) Give up on encapsulation/polymorphism
2) Make any abstract (interface) into a resource just in case.
IMO it all comes down to what abstraction do we want to keep.
Either we give up on the 'eternal objects' abstraction for garbage
collection, or we give up on encapsulation and polymorphism.
I would definetely opt to give up on the 'eternal objects' abstraction,
the price we pay for it (encapsulation and polymorphism) is simply to
high.
Its kind of sad, that in Java, that offers us a rather good 'free'
resource management for memory, you will end up actualy writing and
thinking more about resource management than in C++, a language that
doen't even implement the simplest form of garbage collection for the
simplest resource (memory).
I think we need to face the simple fact, the 'eternal objects' abstraction
was a mistake. C++/RAII shows that all types of resources can be properly
encapsulated and can keep polymorphism intact. These lessons need to be
taken back to GC languages, so we can do proper 'resource' management
rather than making things easy for just 'memory'. IMHO memory, file
handles, database connections, threads, diskspace, and even locks are
simply resources that can get exausted. A lock is simply a resource pool
of one.
In retrospect, fixing resource management for only one of these resources
seems to have been a mistake. The distinctions between resources that are
more scarse than memory and resources that are not is artificial and
results in nullifying the positive efects of automated memory management.
Rob Meijer
> On Sun, Mar 20, 2011 at 3:02 AM, Rob Meijer <capi...@xs4all.nl> wrote:
>> If, as David-Saray claims a resource is anything that requires explicit
>> release, and the property of 'being a resource' is ,as what I understand
>> from what David-Saray claims, transitive to composition, than any form
>> of
>> polymorphism would require the assumption of 'being a resource'. This in
>> term would mean that each and every interface would need to include a
>> 'release()'.
>
> That isn't the case. Supposing Alice holds a resource, Alice could
> present Bob with an abstraction that accesses the resource but does
> not expose a 'release()' authority. Under these circumstances, Alice
> is holding a resource and Bob is holding some alternative service. The
> property of 'being a resource', hence, is not transitive across
> composition. Resources may be encapsulated by the facet pattern.
> Indeed, the 'with(resource,action)' pattern that obtains the resource
> but hides the facet for releasing it... is, indeed, an example of this
> encapsulation, but limited to stack scope.
The problem arises when Bob has a (the last) reference to Alice.
Bob could not allow this reference to go out of scope without asking Alice
to release any resources Alice may hold.
Lets make Alice a container of some sort, lets say a priority queue. Now
lets say there are two types of concrete classes that implement an
AbstractPriorityQueue. a simple memory only one, and complex distributed
one that holds all kinds of remote and local resources that need to be
explicitly released. So we have a MemoryPriorityQueue and a
ComplicatedResourcesPriorityQueue. Now Bob has his own
AbstractPriorityQueue that could be either. This basically menas that
AbstractPriorityQueue requires a 'release' method for bob to call before
Bob allows this priority queue to go out of scope.
This IMO breaks encapsulation, this IMO breaks polymorphism.
David Barbour
>
> The problem arises when Bob has a (the last) reference to Alice.
> Bob could not allow this reference to go out of scope without asking Alice
> to release any resources Alice may hold.
Since you present a scenario where Bob must treat Alice as a resource,
you are begging the question.
The point remains that Bob and Alice can be independent agents, and
Alice can provide Bob services using her own resources... without
providing Bob a resource abstraction. This is sufficient to reject
your position that polymorphism and encapsulation are broken.
>
> we have a MemoryPriorityQueue and a ResourcesPriorityQueue.
> AbstractPriorityQueue that could be either. AbstractPriorityQueue
> requires a 'release' method for bob to call before Bob allows this
> priority queue to go out of scope. [cut to the essentials]
It isn't clear to me why the AbstractPriorityQueue needs a 'release'
method. Wouldn't a 'foreach' method suffice?
David Barbour
> I think we need to face the simple fact, the 'eternal objects' abstraction
> was a mistake.
I would agree that resources should not be associated with
non-volatile objects. I came to a similar conclusion from a different
direction: orthogonal persistence needs the ability to restore
activities (sound, video, UI, server and p2p connections). But,
whereas you conclude that 'eternal objects' are the mistake, my
conclusion was that 'naked message passing' is the mistake - that a
more connection-oriented design is superior. Connections give us
semi-volatile objects with which we can associate resources and other
connections.
>
> C++/RAII shows that all types of resources can be properly encapsulated
> and can keep polymorphism intact.
David-Sarah's def. of resource was incomplete (only covered
conservative resources). C++/RAII doesn't help with time and energy
and a number of other resources...
Tyler Close
> On Fri, Mar 4, 2011 at 4:40 PM, James A. Donald <jam...@echeque.com> wrote:
>> whose sha-256 has was hl6w2x74ixy6pi5n
>
> I'm left wondering how someone fit 256 bits of hash into 80 bits of data...
One doesn't. The genkey.jar program in the Waterken server that's used
to generate a new certificate and corresponding hostname truncates the
hash to a shorter length depending on the public key size the user
specifies. By default, genkey.jar generates a 1024 bit RSA keypair and
so truncates the hash to 80 bits. Longer hashes are used for longer
public keys: 112 for 2048, 128 for 3072 and above. I took these
numbers off of a page on the RSA site that equated RSA key lengths to
corresponding symmetric key lengths.
--Tyler
--
"Waterken News: Capability security on the Web"
http://waterken.sourceforge.net/recent.html
David Barbour
One doesn't. The genkey.jar program in the Waterken server that's usedOn Fri, Mar 11, 2011 at 12:27 AM, David Barbour <dmba...@gmail.com> wrote:
> On Fri, Mar 4, 2011 at 4:40 PM, James A. Donald <jam...@echeque.com> wrote:
>> whose sha-256 has was hl6w2x74ixy6pi5n
>
> I'm left wondering how someone fit 256 bits of hash into 80 bits of data...
to generate a new certificate and corresponding hostname truncates the
hash to a shorter length depending on the public key size the user
specifies. By default, genkey.jar generates a 1024 bit RSA keypair and
so truncates the hash to 80 bits. Longer hashes are used for longer
public keys: 112 for 2048, 128 for 3072 and above. I took these
numbers off of a page on the RSA site that equated RSA key lengths to
corresponding symmetric key lengths.
Tyler Close
These yurl.net hostnames do not assume any extra security from either
the DNS or CAs.
I figure the attacker can put his computational resources into
cracking the public key to find a corresponding private key, or into
finding a hash collision on the public key fingerprint. It doesn't
make sense to make one of those tasks significantly easier or harder
than the other.
--Tyler
David Barbour
cracking the public key to find a corresponding private key, or intoI figure the attacker can put his computational resources into
finding a hash collision on the public key fingerprint. It doesn't
make sense to make one of those tasks significantly easier or harder
than the other.
David-Sarah Hopwood
> On Fri, Mar 11, 2011 at 12:27 AM, David Barbour <dmba...@gmail.com> wrote:
>> On Fri, Mar 4, 2011 at 4:40 PM, James A. Donald <jam...@echeque.com> wrote:
>>> whose sha-256 has was hl6w2x74ixy6pi5n
>>
>> I'm left wondering how someone fit 256 bits of hash into 80 bits of data...
>
> One doesn't. The genkey.jar program in the Waterken server that's used
> to generate a new certificate and corresponding hostname truncates the
> hash to a shorter length depending on the public key size the user
> specifies. By default, genkey.jar generates a 1024 bit RSA keypair and
> so truncates the hash to 80 bits. Longer hashes are used for longer
> public keys: 112 for 2048, 128 for 3072 and above. I took these
> numbers off of a page on the RSA site that equated RSA key lengths to
> corresponding symmetric key lengths.
Hmm, those correspondences are only approximate. Unlike attacks
against RSA, hash preimage attacks are perfectly parallelizable and
require negligable memory. Also, multi-target attacks are possible
(for example, finding a preimage for any of 2^20 80-bit hashes would
take 2^60 work, not 2^80).
Tyler Close
<david...@jacaranda.org> wrote:
> On 21/04/11 18:24, Tyler Close wrote:
>> On Fri, Mar 11, 2011 at 12:27 AM, David Barbour <dmba...@gmail.com> wrote:
>>> On Fri, Mar 4, 2011 at 4:40 PM, James A. Donald <jam...@echeque.com> wrote:
>>>> whose sha-256 has was hl6w2x74ixy6pi5n
>>>
>>> I'm left wondering how someone fit 256 bits of hash into 80 bits of data...
>>
>> One doesn't. The genkey.jar program in the Waterken server that's used
>> to generate a new certificate and corresponding hostname truncates the
>> hash to a shorter length depending on the public key size the user
>> specifies. By default, genkey.jar generates a 1024 bit RSA keypair and
>> so truncates the hash to 80 bits. Longer hashes are used for longer
>> public keys: 112 for 2048, 128 for 3072 and above. I took these
>> numbers off of a page on the RSA site that equated RSA key lengths to
>> corresponding symmetric key lengths.
>
> Hmm, those correspondences are only approximate. Unlike attacks
> against RSA, hash preimage attacks are perfectly parallelizable and
> require negligable memory.
Are you saying the RSA estimates would not have taken those factors
into account?
> Also, multi-target attacks are possible
> (for example, finding a preimage for any of 2^20 80-bit hashes would
> take 2^60 work, not 2^80).
Which is only relevant to someone who is operating 2^20 servers. From
the perspective of an individual server operator, their odds of being
cracked are still 1 in 2^80. If they don't like those odds, they just
specify a higher level of security to the genkey program.
BTW, I misspoke earlier when I said the key size determines the hash
length. It's actually the other way around: the command line argument
is the number of bits of hash to use in the hostname and that
determines the RSA key length:
final int strength = 0 < args.length ? Integer.parseInt(args[0]) : 80;
final int keysize =
80 >= strength
? 1024
: 112 >= strength
? 2048
: 128 >= strength
? 3072
: 4096;
So an operator hosting 2^20 servers could specify 100 on the command
line to get a longer fingerprint and so maintain 1 in 2^80 odds. Does
that seem sensible to you, or do you think the algorithm above needs
tweaking?