In fairness I should state that here at Bremen we do not currently need Haskell finalizers. I was thinking of another application altogether, but I don't particularly want to go into details of that. There are however particular reasons (such as galloping concurrency) why I think Alastair's proposed hooks would be impractical in that case, even if they were provided by both garbage collectors, which they wouldn't be. I don't think we are coming any nearer to a solution on this. There seem to be three proposals: (1) Alastair's: keep the signature as it is, with the restriction. Add miscellaneous hooks allowing C to do things to the Haskell world without actually entering it. (2) Mine: keep the signature as it is, but remove the restriction, at least so that if implementations decide to impose the restriction anyway, they have to document it very clearly. (EG "Hugs implements the FFI standard [ref]" with the restriction that finalizers may not call back into Haskell (see paragraph [whatever]"). (3) Manuel's: reverse the change altogether. Ideally I'd like Manuel's solution, except that we obviously can't force Hugs and NHC to comply with it. I think therefore I prefer my solution in that it makes clear you can write simple portable FFI code which runs on any implementation with or without the restriction, but non-trivial use involving interaction with foreign garbage collectors and the like is likely to fall over. I don't deny that it is likely to be possible to write non-trivial applications involving finalizers in several languages even in Hugs, but you will have to provide various hooks which are in general quite inappropriate. Other choices might be some kind of lock which could be operated from both the Haskell and C world (since then it would be possible, painfully, for a C finalizer to arrange for a Haskell thread sleeping on the lock to wake up, if enough scheduling points arise). Or as Alastair suggested, you can at least arrange for some Haskell functions, like freeStablePtr, to be made available in the C world. Such things might be a good idea in Hugs or NHC (obviously it's not for me to say), if Haskell finalizers really are impossible. But in general I think it is simply absolutely inappropriate for such solutions to be specified in the standard, since they seem to assume too much and impose too much work on the user, if the user is happy to use GHC.
Some comments on the question of finalisers. Firstly, a retraction. In nhc98, it *is* possible to implement Haskell finalisers, by creating a `pending' list of finalisers during the GC, and then running them immediately the GC finishes. I see several messages in the archive where I claimed the latter was impossible. I was wrong. (The key issue is deciding when GC has really finished - not as obvious as it looks, but I got there in the end.) What is more, I am now pretty convinced that it is relatively trivial to permit those finalisers to call foreign code that calls back into Haskell, possibly triggering a further GC, and for everything still to play nicely. (A mutex lock is required to ensure that the pending queue is not traversed more than once, but that is all I think.) At the moment nhc98 still has the ability, as per recent changes in the FFI spec, to call a foreign language finaliser (FunPtr (Ptr a -> IO ())) rather than a Haskell one. However, our GC currently calls such a finaliser immediately it finds it, i.e. in the middle of the GC cycle. I am now certain that this is wrong, because the foreign code could call back into Haskell, which of course would be disastrous in the middle of a GC. So just like with a Haskell finaliser, a foreign code finaliser must be placed on a `pending' list and run only after GC has finished. Hence, I think the really key issue for the safety of finalisers is not what language the finaliser is written in, but when it is run. Now, how about concurrency? nhc98 has no concurrency model, so all its interactions with foreign code must be within a single thread. This is true even if the foreign code has concurrent threads internally. Because nhc98 produces only sequential code, all interaction with the Haskell program must take place within that thread alone. The sequential Haskell RTS simply has to ensure is that when a Haskell GC is in progress, no foreign code can run in the same thread. (This is the reason for delaying any finalisers until the GC is complete.) For systems that do have concurrency, George points out that a concurrent foreign thread might call into Haskell at any moment, even when the Haskell RTS is in the middle of a GC. True enough. But this has nothing to do with finalisation per se, it is just a general feature of any concurrent system where there is a combination of languages. Just apply the usual mechanism in the Haskell RTS to exclude other activity during a GC. I understand that there are more tricky issues in concurrency, to do with shared access to resources, and scheduling policy. However I am still not sure of all the details, so Alastair's concerns are probably well-founded. I *think* the problem in Hugs is that the scheduler is co-operative, so the GC cannot simply place a triggered finaliser into a new thread and ignore it. (The co-operative scheduler might delay the running of the finaliser thread for an arbitrarily long time.) The GC also cannot make the triggered finaliser into a new thread and start running it immediately GC is finished. (This would amount to overriding the scheduler - pre-empting it in fact.) Is this a fair characterisation Alastair? If so, then I have two questions: (1) Why is it a disaster for a finaliser to be delayed for an arbitrary amount of time? As things stand, there is no guarantee on when a finaliser will run anyway, just that it will do so before the end of the computation. (2) Why is it a disaster to have an occasional change of scheduling policy (from co-operative multi-tasking to pre-emption)? Does it change the semantics of the concurrency model? Does it lead to a possible loss of termination? Does it disrupt some in-built assumptions in the runtime system? Regards, Malcolm
(A mutex lock is required to ensure that the pending queue is not traversed more than once, but that is all I think.)
I don't understand how this would work in single-threaded systems (like I understand NHC to be). Using mutexes in single-threaded systems results in either no protection or deadlock. Which outcome happens depends on what happens when a thread tries to take a lock it already holds (if it increments a counter and succeeds, you get no protection; if it blocks the thread, you get deadlock).
I understand that there are more tricky issues in concurrency, to do with shared access to resources, and scheduling policy. However I am still not sure of all the details, so Alastair's concerns are probably well-founded. I *think* the problem in Hugs is that the scheduler is co-operative, so the GC cannot simply place a triggered finaliser into a new thread and ignore it.
I'd say that the problem in Hugs is the same as that in NHC. That is, the problem is not that the scheduler is cooperative but that it does not have a preemptive scheduler. Not having a preemptive scheduler means: 1) That the code was not written under the additional constraints of worrying about atomicity of data structure modifications. Here, the code referred to is mostly the C code used to implement the Hugs runtime system and large chunks of the standard libraries. 2) That there is no blocking mechanism handy with which to implement the mutexes needed to make data structure modifications atomic. Here the code referred to is both C code in Hugs and Haskell code written by the users of Hugs.
Is this a fair characterisation Alastair?
Sort of. I find it a bit misleading because it seems to suggest that NHC will not suffer from the same problem because NHC doesn't have a cooperative scheduler. If execution of finalizers is not synchronized with the main IO thread (e.g., by having the Haskell programmer explicitly call a 'runFinalizersNow' IO function, then finalizers are, effectively, executed in a preemptive thread and you (and NHC users) will need to start using many of the programming techniques we know and hate from writing concurrent programs.
(1) Why is it a disaster for a finaliser to be delayed for an arbitrary amount of time?
It's a little unclear what you mean by 'arbitrary'. I'd certainly be unhappy if finalizers never got run before the program ended because of the massive space leak that could easily result. My favourite example of image-trackers based on live video feeds would tend to die very quickly and tends to take my Linux kernel with it (640 x 400 x 32 bits at 30 fps exhausts my desktop's 512Mb in just 17 seconds). Having an explicit runFinalizersNow function in the IO monad would provide some control over this but it'd still lead to some hard-to-resolve space leaks, it'd be ugly and it'd be fragile. Of course, we can make it easy to fix the space leaks [and people are bound to try this] by using unsafePerformIO to avoid the use of the IO monad. runFinalizers' :: a -> a runFinalizers' x = unsafePerformIO $ do{ runFinalizersNow; return x } but this makes it effectively impossible to reason about when the finalizers run relative to code that they share data structures with. So, in fixing the space leaks, we introduce race conditions. The shared data structures, and hence, the races are in parts of the Haskell system's runtime system and standard libraries and, more importantly, in user's code. We can fix the race conditions by using mutexes but, as outlined above, use of mutexes in single-threaded systems provides no protection or causes deadlock. We can achieve protection and avoid deadlock by providing preemptive threads - but that is a very high cost to pay.
As things stand, there is no guarantee on when a finaliser will run anyway, just that it will do so before the end of the computation.
It'd be nice to have a portable, easily reasoned about guarantee but, in the absence of that, we can still learn to avoid using particular compilers, take care to enable/disable various optimization and profiling options, etc to get reasonably timely execution of finalizers.
(2) Why is it a disaster to have an occasional change of scheduling policy (from co-operative multi-tasking to pre-emption)? Does it change the semantics of the concurrency model? Does it lead to a possible loss of termination? Does it disrupt some in-built assumptions in the runtime system?
Cooperative multitasking is harder to reason about than single-threaded systems but it is vastly easier to reason about than preemptive multi-threaded systems because most of the code is still atomic. More importantly though, once you start providing some small form of premption (i.e., Haskell finalizers whose execution is not synchronized with execution of C code), you have to finish the job. That is, you have to provide mutexes (because the only useful finalizers are those that access shared mutable data structures). Providing mutexes requires that you are able to save the execution context (i.e., stack, etc.) of a finalizer, continue executing the main thread until it releases the mutex, then switch back to executing the finalizer (because waiting until the main thread terminated or took another lock would be unacceptable). How easy would it be to support that in NHC? I believe it would be hard. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/
Alastair Reid <alastair@reid-consulting-uk.ltd.uk> writes:
(A mutex lock is required to ensure that the pending queue is not traversed more than once, but that is all I think.)
I don't understand how this would work in single-threaded systems (like I understand NHC to be).
Sorry, I am probably abusing the terminology. What I mean is that in the following single-threaded situation: * GC has just completed * the pending finaliser queue is being run * a finaliser has sufficient allocation to trigger another GC * after that GC, the pending finaliser queue is run again the final step is excluded. i.e. the second time the RTS enters the pending queue, it realises the queue is already in progress and returns immediately without doing any work. No blocking involved.
Not having a preemptive scheduler means:
1) That the code was not written under the additional constraints of worrying about atomicity of data structure modifications.
Here, the code referred to is mostly the C code used to implement the Hugs runtime system and large chunks of the standard libraries.
So are you saying that if a GC were to occur in the middle of a C-implemented Hugs primitive, it could be bad news? Surely there must be some mechanism for ensuring that allocation during a primitive call is safe? For instance, any primitives in nhc98's RTS that allocate on the heap exclude the possibility of GC by checking there is enough free space before doing anything. (By contrast, FFI calls (a) cannot heap-allocate, and (b) do not copy any heap pointers, so a GC would be harmless.)
2) That there is no blocking mechanism handy with which to implement the mutexes needed to make data structure modifications atomic.
Let's see if I grasp this right. With a non-preemptive scheduler, data structure modifications are guaranteed to be atomic, because all context switches are explicit (e.g. at certain IO calls). If anything breaks this assumption (e.g. if the GC runs a finaliser pre-empting the main thread), then atomicity is lost. Ok, fair enough, I think I see the problem.
I find it a bit misleading because it seems to suggest that NHC will not suffer from the same problem because NHC doesn't have a cooperative scheduler.
nhc98 doesn't have a scheduler at all. However, I think the point you are getting at is atomicity. I'm afraid I have been rather slow to see that we are talking about /global variables/! Protection of data structure access is guaranteed in a single-threaded system by simple referential transparency. But you are suggesting that the main use for finalisers is to fiddle "behind the scenes" with data structures that are shared with other parts of the program. Eeek. Suddenly I'm not surprised that there are difficulties.
That is, you have to provide mutexes (because the only useful finalizers are those that access shared mutable data structures).
I'm afraid I don't agree that the /only/ useful finalisers manipulate global variables. I can think of plenty of more tractable situations, e.g. releasing the various pieces of storage for a foreign value built of several components, where a finaliser written in Haskell would be preferable to one in C. However, given that you do want to manipulate shared global variables, I still have a question. Why not build a queue of pending finalisers, make each one into a co-operative thread, and add those threads to the pool of threads being managed by Hugs' normal scheduler? It seems to me that this guarantees the atomicity you need. The only downside is:
(because waiting until the main thread terminated or took another lock would be unacceptable).
So why is this unacceptable? You need to delay the finaliser for correctness. By the assumptions of the co-operative scheduling model, the only safe moment to run the finaliser is when the current thread releases control. But now you seem to say that this is bad, because you want efficiency/timeliness, and efficiency means you need pre-emption. Make your mind up! Either you accept the co-operative scheduling model and put up with lack of timeliness, or you decide that timeliness is more important and move to pre-emption. Regards, Malcolm
So are you saying that if a GC were to occur in the middle of a C-implemented Hugs primitive, it could be bad news?
It's possible. It's something we never had to consider when writing the Hugs primitives so we never took care to protect against it.
Surely there must be some mechanism for ensuring that allocation during a primitive call is safe? For instance, any primitives in nhc98's RTS that allocate on the heap exclude the possibility of GC by checking there is enough free space before doing anything.
Using a conservative GC saves us from most of that though we need to take some care with some of the more complex primops like array allocation.
(By contrast, FFI calls (a) cannot heap-allocate, and (b) do not copy any heap pointers, so a GC would be harmless.)
Of course, safe FFI calls can heap allocate...
2) That there is no blocking mechanism handy with which to implement the mutexes needed to make data structure modifications atomic.
I find it a bit misleading because it seems to suggest that NHC will not suffer from the same problem because NHC doesn't have a cooperative scheduler.
That is, you have to provide mutexes (because the only useful finalizers are those that access shared mutable data structures).
I'm afraid I don't agree that the /only/ useful finalisers manipulate global variables. I can think of plenty of more tractable situations, e.g. releasing the various pieces of storage for a foreign value built of several components, where a finaliser written in Haskell would be preferable to one in C.
Do those really occur? We're talking about finalizers for C objects (i.e., things of type '[Foreign]Ptr a') here. If it was a finalizer for a Haskell object, I could easily imagine a finalizer like this: finalizeFoo (Foo x y) = finalize x >> finalize y but it's a C object. I guess it might contain a pointer to a Haskell object. That would be a StablePtr, of course, so I'd call void hs_freeStablePtr( HsStablePtr a ); from C which would tell the GC that we're done with the object. [I think I've previously mentioned the need to add hs_freeStablePtr before and the need to be specify that unsafe ffi calls and finalizers can safely call it.]
However, given that you do want to manipulate shared global variables, I still have a question. Why not build a queue of pending finalisers, make each one into a co-operative thread, and add those threads to the pool of threads being managed by Hugs' normal scheduler? It seems to me that this guarantees the atomicity you need. The only downside is:
(because waiting until the main thread terminated or took another lock would be unacceptable).
So why is this unacceptable? You need to delay the finaliser for correctness. By the assumptions of the co-operative scheduling model, the only safe moment to run the finaliser is when the current thread releases control. But now you seem to say that this is bad, because you want efficiency/timeliness, and efficiency means you need pre-emption. Make your mind up! Either you accept the co-operative scheduling model and put up with lack of timeliness, or you decide that timeliness is more important and move to pre-emption.
This would delay execution of the finalizer far longer than is necessary. With your proposal, finalizers which might possibly conflict would be delayed until control returned to the main thread and executed one of those IO actions which can cause preemption. This could take a very long time (it might not even happen until the program terminates) and you will hold onto space during all that time. In GHC, using a mutex to protect a data structure from finalizers only delays execution of the finalizers if the data structure is currently being accessed and only delays them until the thread leaves the critical section. [Actually, this isn't quite true: there's a delay caused by the length of time slices and by GHC not having a priority scheduler. This could be significant in some programs.] With my proposal, Hugs and NHC can call the finalizer during GC and that finalizer can release any stable pointers it may hold during that GC. Space is released very quickly and, in particular, the time taken to release that garbage is independent of how much time you spend in the IO monad. [It'd be nicer still if releasing those StablePtrs instantly triggered release of more ForeignPtrs which released more StablePtrs, etc. so that a single GC run released all unnecessary heap space but I think this would require substantial reengineering.] -- Alastair
On Wed, Oct 09, 2002 at 02:02:35PM +0100, Alastair Reid wrote:
So are you saying that if a GC were to occur in the middle of a C-implemented Hugs primitive, it could be bad news?
It's possible. It's something we never had to consider when writing the Hugs primitives so we never took care to protect against it.
I thought you did. Every time you allocate a cell in Hugs, it's a potential GC, and Hugs is very careful that any heap pointers in use will be visible to the garbage collector. What hasn't been required is for the various data structures to be in a consistent state at that point, and Haskell finalizers might trip over those if run after GC. SimonM's patch ran them at a different point, though.
What hasn't been required is for the various data structures to be in a consistent state at that point, and Haskell finalizers might trip over those if run after GC. SimonM's patch ran them at a different point, though.
It calls them in eval doesn't it? eval is called by nearly every primitive in Hugs. Most calls are benign since the calls are at the start of the primop before any data structures have been fiddled with. It's even possible that none have any problems. All I'm saying that we will have to look over the code before we know if there is a problem (while others are claiming that there couldn't possibly be a problem). What is definitely a problem is the issue of atomicity of user-written Haskell finalizers. -- Alastair
On Wed, Oct 09, 2002 at 04:09:07PM +0100, Alastair Reid wrote:
What hasn't been required is for the various data structures to be in a consistent state at that point, and Haskell finalizers might trip over those if run after GC. SimonM's patch ran them at a different point, though.
It calls them in eval doesn't it? eval is called by nearly every primitive in Hugs. Most calls are benign since the calls are at the start of the primop before any data structures have been fiddled with.
It's even possible that none have any problems. All I'm saying that we will have to look over the code before we know if there is a problem (while others are claiming that there couldn't possibly be a problem).
OK, so the problem is to find a place in Hugs that is passed frequently enough, but at which the internal data structures are consistent. How about the start of primPass (called to enter the continuation argument of >>= in the IO monad)? Seems like a safe place to do an IO action. (I don't know why the IO furniture is primitive, but since it's there ...) The top-level loop is presumably another safe place.
OK, so the problem is to find a place in Hugs that is passed frequently enough, but at which the internal data structures are consistent.
How about the start of primPass (called to enter the continuation argument of >>= in the IO monad)? Seems like a safe place to do an IO action. (I don't know why the IO furniture is primitive, but since it's there ...) The top-level loop is presumably another safe place.
I don't think >>= is frequent enough. Pure code that manipulates big C objects (remember that image processing example of mine?) can generate a lot of garbage C objects without once going into the IO monad. More importantly though, this does nothing at all to guarantee atomicity of Haskell code that manipulates global variables. Consider a data structure consisting of a list of objects. The main thread might add to this list and do searches in the list and the finalizer removes objects from the list: type State = IORef [Object] -- used by main newObject :: Object -> IO () newObject o = do os <- readIORef state writeIORef state (o:os) -- used by finalizer killObject :: Object -> IO () killObject o = do os <- readIORef state writeIORef state (filter (/= 0) os) Some possible interleavings of the IO actions in these functions can result in an object not being added to or removed from the object list. Debugging this would be next to impossible since it would be hard to repeat. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/
I don't think >>= is frequent enough. Pure code that manipulates big C objects (remember that image processing example of mine?) can generate a lot of garbage C objects without once going into the IO monad.
Also, thanks to unsafePerformIO, >>= can be invoked during execution of a primitive even if the arguments of the primop do not involve IO. This is somewhat beside the point though - the main worry is about race conditions in user-written code. -- Alastair
participants (4)
-
Alastair Reid -
George Russell -
Malcolm Wallace -
Ross Paterson