www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Exception on dynamic memory allocation

reply Frank Benoit <frank nix.de> writes:
Hi all

In a RTAI real-time app, I use D in so called user space hard real-time
threads. I have to be sure, I don't use dynamic memory allocation in the
real-time threads. There is no problem with using that in the
non-real-time threads.
The user of this app will use it as programming environment and will
contribute source code, running mixed in non-rt and rt. So I need the
possibility to check at runtime, there is no memory allocation for
anything in the rt threads.

So my question:
How to generate an exception if memory allocation is done in particular
sections of the code?

Something like:
	enterNoAlloc();
		// stuff to do
		int[2] a;
		a.dup; // Oooops! throws NotAllowedAllocation
	leaveNoAlloc();
	a.dup; // Ok, alloc allowed

I thing, implementing the "new" for paricular classes is no solution,
since I want to detect unexpected allocations.

Can I provide my own gc by inherenting the standard gc? How to do that?

Frank
Dec 20 2005
parent reply Sean Kelly <sean f4.ca> writes:
Frank Benoit wrote:
 Hi all
 
 In a RTAI real-time app, I use D in so called user space hard real-time
 threads. I have to be sure, I don't use dynamic memory allocation in the
 real-time threads. There is no problem with using that in the
 non-real-time threads.
 The user of this app will use it as programming environment and will
 contribute source code, running mixed in non-rt and rt. So I need the
 possibility to check at runtime, there is no memory allocation for
 anything in the rt threads.
 
 So my question:
 How to generate an exception if memory allocation is done in particular
 sections of the code?
 
 Something like:
 	enterNoAlloc();
 		// stuff to do
 		int[2] a;
 		a.dup; // Oooops! throws NotAllowedAllocation
 	leaveNoAlloc();
 	a.dup; // Ok, alloc allowed
 
 I thing, implementing the "new" for paricular classes is no solution,
 since I want to detect unexpected allocations.
 
 Can I provide my own gc by inherenting the standard gc? How to do that?

I've been considering doing something like this for Ares. You really have three concerns: preventing the RT thread from being suspended during "stop the world" collections, preventing the RT thread from allocating GCed memory, and preventing the RT thread from being the sole owner of GCed memory (say a pointer is passed from user code). std.thread currently doesn't support the idea of "detached" threads so you'll need to either alter it or write your RT thread using C threading calls. As for the rest, you'll need to modify the GC and supply a few more methods for the std.gc interface. The easiest thing would be to store thread id's of threads that are real-time and check against this list in the malloc call. Sean
Dec 20 2005
parent reply Frank Benoit <frank_DELETE_ _DELETE_drealtime.com> writes:
Sean Kelly wrote:
 I've been considering doing something like this for Ares.  You really
 have three concerns: 
 preventing the RT thread from being suspended 
 during "stop the world" collections, 

prevent this interrupting is to disable the hardware interupts. This is possible, but should not exceed few machine cycles. If I block interupts while complite a collection cycle is running, the timing is not more deterministic and that is the whole thing of real-time.
 preventing the RT thread from  
 allocating GCed memory, 

 and preventing the RT thread from being the sole 
 owner of GCed memory (say a pointer is passed from user code).

understanding, the reference to it or the GC is the owner if the memory was allocated with him.
 std.thread currently doesn't support the idea of "detached" threads so
 you'll need to either alter it or write your RT thread using C threading
 calls.  

with a call to RTAI function rt_make_hard_real_time(), the thread is given to the rt scheduler and no longer under linux scheduling control (linux by itself is running as idle task in the rt scheduler). But the memory is not changed.
 As for the rest, you'll need to modify the GC and supply a few 
 more methods for the std.gc interface.  The easiest thing would be to
 store thread id's of threads that are real-time and check against this
 list in the malloc call.

This sounds good. I found the sources of the gc in the internal directory of the phobos source. How can I bring my own implementation? There is a function setGCHandle(), but if I call it in main() it is too late. All static ctors where called and probably had malloced memory. I think it is possible to make this real-time playing good with D if I could provide a RTAI-GC which differs from the standard one in: - have enterRtThread, incr rt-section-counter, set rt-section-entered - have leaveRtThread, decr rt-section-counter - throw exception if malloc while rt-section counter >0 - the collection cycle have to be modified - before scanning reset the rt-section-entered - surround the "freeing" statements with interrupts lock/release, this should be short running blocks (interrupt latency) - immidiate before freeing test rt-section-entered, if set -> do not free and repeat scanning (with the risk of an endless loop, if interrupt rate is permanent to high (fast timer irq)) I wonder why there is no interface to implement an own GC and to inherent from a standard one. Or is there such an interface? Frank -- D and real-time: www.drealtime.com
Dec 20 2005
parent reply Sean Kelly <sean f4.ca> writes:
Frank Benoit wrote:
 Sean Kelly wrote:
 I've been considering doing something like this for Ares.  You really
 have three concerns: 
 preventing the RT thread from being suspended 
 during "stop the world" collections, 

prevent this interrupting is to disable the hardware interupts. This is possible, but should not exceed few machine cycles. If I block interupts while complite a collection cycle is running, the timing is not more deterministic and that is the whole thing of real-time.

Are you saying that an RT thread that has been suspended (via a call to SuspendThread or through some signal mechanism on POSIX) may actually wake up on its own? My real concern here is that the current thread implementation necessarily suspends all user threads (created as instances od std.Thread) during a GC run. But if RT threads are somehow exempt from this then I guess it's not an issue.
 preventing the RT thread from  
 allocating GCed memory, 

 and preventing the RT thread from being the sole 
 owner of GCed memory (say a pointer is passed from user code).

understanding, the reference to it or the GC is the owner if the memory was allocated with him.

Consider this code: // normal thread void passData() { char* buf = new char[100]; // fill buf enqueue( buf ); } // RT thread char* buf = dequeue(); Assume a GC run is triggered after the RT thread dequeues buf. In this case, the RT thread is the only thread that has a reference to this data (which was allocated on the GCed heap). With typical "stop the world" GCs, the GC will: 1. Stop all running threads 2. Scan the stack segment of each thread for references to heap data 3. clean up unreferenced data 4. Restart all threads As I expect the RT thread will neither be suspended nor scanned, its stack will not be checked for references to the GC heap, and therefore any data it references that is not also referenced by a "normal" thread is eligible for collection. This is what I meant by the RT thread being the sole "owner" of a memory block--it is the only thread with a live reference to the data.
 As for the rest, you'll need to modify the GC and supply a few 
 more methods for the std.gc interface.  The easiest thing would be to
 store thread id's of threads that are real-time and check against this
 list in the malloc call.

This sounds good. I found the sources of the gc in the internal directory of the phobos source. How can I bring my own implementation? There is a function setGCHandle(), but if I call it in main() it is too late. All static ctors where called and probably had malloced memory.

You will have to modify Phobos to link in a new GC. The GC lives in internal/gc and is relatively well separated from the rest of Phobos. You'll need to search for any extern (C) functions and implement them in your replacement code. Most or all of these can be found in gc.d and gcx.d. Also, if you're not married to Phobos functionality, you might find Ares to be a bit easier to play with: http://www.dsource.org/projects/ares/ Ares is composed of three component libraries: - The compiler runtime (dmdrt.lib) - The garbage collector (dmdrt.lib) - The user-accessible standard library (ares.lib) The runtime and GC are the low-level portions of Phobos, but have been altered to allow them to be separated cleanly. The standard library is very sparse at the moment and contains mostly thread code and a solid set of C headers. My next project is to clean up the GC interface and separate it out a bit more cleanly (as I haven't yet formalized the GC interface or how it's called by the runtime code), but it should still provide a reasonable starting point. I've actually been reading papers recently on GC implementations and am planning to take a stab at one that's more aimed at concurrent programming, but I have no timeline for that particular project. However, one thing I discovered was that it is possible to write a hard RT application that uses garbage collection. The kicker is that is seems to require incremental collection, and that's something DMD doesn't currently support (as it seems to require GC interaction any time pointer data is modified). However, I think the spec is loose enough that incremental GC support could be added by way of some additional code generation, though this may not be optimal for the general case.
 I think it is possible to make this real-time playing good with D if I could
 provide a RTAI-GC which differs from the standard one in:
 - have enterRtThread, incr rt-section-counter, set rt-section-entered
 - have leaveRtThread, decr rt-section-counter
 - throw exception if malloc while rt-section counter >0
 - the collection cycle have to be modified
         - before scanning reset the rt-section-entered
         - surround the "freeing" statements with 
            interrupts lock/release, this should be short 
            running blocks (interrupt latency)
         - immidiate before freeing test rt-section-entered, 
            if set -> do not free and repeat scanning 
            (with the risk of an endless loop, if interrupt
            rate is permanent to high (fast timer irq))

Seems reasonable, though I don't understand RT threading enough to say for sure. From the above however, it seems like you are marking certain segments of a thread execution as being real-time. Is this correct? How do you account for things taking an indeterminate amount of time when they aren't in RT code?
 I wonder why there is no interface to implement an own GC and to inherent
 from a standard one. Or is there such an interface?

Not really. There is the setGCHandle call you mentioned, but I'm undecided on whether overriding the GC at run time is actually a good idea. The alternative is what I mentioned above: figure out how the runtime interacts with the GC and replace it. At the moment, that takes some digging (though this should be easier with Ares when I formalize things in a few weeks). Sean
Dec 20 2005
parent reply Frank Benoit <frank_DELETE_ _DELETE_drealtime.com> writes:
Sean Kelly wrote:
 Are you saying that an RT thread that has been suspended (via a call to
 SuspendThread or through some signal mechanism on POSIX) may actually
 wake up on its own?  

program, others can hang for seconds. If you want to make timing very exact and reliable you need special help from the OS. In case of RTAI, there is a software layer installed between hardware and the linux kernel. A real-time OS, commonly called RTOS, makes the scheduling. Linux with all inside is running in the idle task of the RTOS. Every interrupt from hardware is first seen from the RTOS. If it has processed it, then the interrupt is carried to linux. If I want to make a task, executed exactly every millisecond, I create a rt task, let the RTOS create a timer based on cpu machine cycles, and in the task I call rt_sleep_until( timeofnextcycle ). With that, I have an accuracy of less than 10 microsecods. But if I have the need for such timings, I cannot wait for any gc in linux :) The timing of the rt task has ultimate priority. This for sure means, that a program fault can be worse. Leaving no time for linux means, that it freezes completely. In the past, rt task have to run in kernel space. With a new technology, called lxrt, it is possible to make programs having rt out of user space. The rt task run like a normal linux pthread, but it is not scheduled from linux. A call to a RTAI function transfers the execution control to RTAI and RTAI gives it back at a certain time or an event like interrupt, signaled semaphore, received message etc.
 My real concern here is that the current thread 
 implementation necessarily suspends all user threads (created as
 instances od std.Thread) during a GC run.  But if RT threads are somehow
 exempt from this then I guess it's not an issue.

moves a reference, while gc is running, it could happen, it misses the reference. But because of the rt requirements, blocking these tasks is not possible. Because of that, I suggested the "rt-section-entered" flag in the gc.
 Assume a GC run is triggered after the RT thread dequeues buf.  In this
 case, the RT thread is the only thread that has a reference to this data
 (which was allocated on the GCed heap).  With typical "stop the world"
 GCs, the GC will:
 
 1. Stop all running threads
 2. Scan the stack segment of each thread for references to heap data
 3. clean up unreferenced data
 4. Restart all threads
 
 As I expect the RT thread will neither be suspended nor scanned, its
 stack will not be checked for references to the GC heap, and therefore
 any data it references that is not also referenced by a "normal" thread
 is eligible for collection.  This is what I meant by the RT thread being
 the sole "owner" of a memory block--it is the only thread with a live
 reference to the data.

task with the std.thread. I think this should be possible, because RTAI and std.thread both uses the pthread API. I have to analyse the exact parameters RTAI uses, and if they are compatible with the one std.thread uses. If not, if have to provide an own version of std.thread too. Then the stacks of the rt thread are visible for the gc. In case of interrupted gc, the gc has to do a rescan.
 http://www.dsource.org/projects/ares/

 However, one thing I discovered was that it is possible to write a hard
 RT application that uses garbage collection.  The kicker is that is
 seems to require incremental collection, and that's something DMD
 doesn't currently support (as it seems to require GC interaction any
 time pointer data is modified).

fast cyclic rt tasks, allways interrupting the gc, so it has to restart and so it never ends. (.. it is possible to detect that and throw an error, but that does not really solve the problem). I have to measure the maximum time the gc needs for scanning.
 Seems reasonable, though I don't understand RT threading enough to say
 for sure.  From the above however, it seems like you are marking certain
 segments of a thread execution as being real-time.  Is this correct?

to sleep. A rt task can be interrupted (preempt multitasking or hardware interrupt) by another rt task, but linux is only activated if all rt task went to sleep. Because of that, I can place calls to the gc, to inform him, about entering/leaving rt. // started with pthread_create void thread(void*) { // let RTAI take this thread out of linux's scheduler // and put it under RTAI's control rt_make_hard_real_time(); gc.enterRtSection(); // get current time in ns long time = rt_get_time_ns(); while( !stop ) { time += PERIOD; gc.leaveRtSection(); rt_sleep_until( time ); // <- linux runs only here gc.enterRtSection(); // Do the real timed work } gc.leaveRtSection(); // give this thread back to linux rt_make_soft_real_time(); }
 How do you account for things taking an indeterminate amount of time
 when they aren't in RT code?

question correct? Frank -- D and real-time: www.drealtime.com
Dec 20 2005
parent reply Sean Kelly <sean f4.ca> writes:
Frank Benoit wrote:
 Sean Kelly wrote:

 However, one thing I discovered was that it is possible to write a hard
 RT application that uses garbage collection.  The kicker is that is
 seems to require incremental collection, and that's something DMD
 doesn't currently support (as it seems to require GC interaction any
 time pointer data is modified).

Yes, that was the thing I wrote with the risk of infinite loop. If you have fast cyclic rt tasks, allways interrupting the gc, so it has to restart and so it never ends. (.. it is possible to detect that and throw an error, but that does not really solve the problem). I have to measure the maximum time the gc needs for scanning.

Restarts are not a problem so long as the GC is coded carefully enough. For example, see this paper: ftp://ftp.cs.utexas.edu/pub/garbage/johnstone-dissertation-body.ps.gz The last ~10 pages contain info on the GC some discussion of comparable soft real-time GCs that have been implemented.
 Seems reasonable, though I don't understand RT threading enough to say
 for sure.  From the above however, it seems like you are marking certain
 segments of a thread execution as being real-time.  Is this correct?

Because of the explicit calls to the RTOS I know where the rt task is going to sleep. A rt task can be interrupted (preempt multitasking or hardware interrupt) by another rt task, but linux is only activated if all rt task went to sleep. Because of that, I can place calls to the gc, to inform him, about entering/leaving rt.

Understood. I didn't realize that Linux proper effectively runs in user-mode when RT threads are present, though the idea makes sense now that you've explained it.
 // started with pthread_create
 void thread(void*)
 {
         // let RTAI take this thread out of linux's scheduler
         // and put it under RTAI's control
         rt_make_hard_real_time();
         gc.enterRtSection();
         // get current time in ns
         long time = rt_get_time_ns();
         while( !stop )
         {
                 time += PERIOD;
                 gc.leaveRtSection();
                 rt_sleep_until( time ); // <- linux runs only here
                 gc.enterRtSection();
                 // Do the real timed work
         }
         gc.leaveRtSection();
         // give this thread back to linux
         rt_make_soft_real_time();
 }
 
 
 How do you account for things taking an indeterminate amount of time
 when they aren't in RT code?

Does the above code answer this? I don't know if I have understood the question correct?

Yes it does. Though it looks like you will indeed need to replace the current GC implementation, as I can't think of a way to guarantee that it will make sufficient progress in the time slice provided by the RT thread. Sean
Dec 20 2005
parent reply Georg Wrede <georg.wrede nospam.org> writes:
Sean Kelly wrote:
 Frank Benoit wrote:

[interesting, good, and informative discussion deleted] For the general case, all the [deleted] points are important and valid. OTOH, Frank mentioned that he's developing a specific application. In a specific case one might try to restrict or refactor the things going on. For example, if it is possible to guarantee that some thread, never allocates, then (at least at first thought) such a thread may interrupt the GC without side effects, thus removing the need to restart the GC. Further (at this same First Thought :-) ), if such a thread deallocates removes the last reference, thus making the target eligible for GC collection, this should not have an adverse effect on GC. (Not being an RT-guru, I'm using imprecise and wrong vocabulary here, I know.) The only result is that the target is found collectable on the next GC run, as opposed to the current GC run. Then again, this may be "elementary", for all I know. For example, anything that ultimately risks allocating memory, inherently takes an undecideable time (other stuff may have to be swapped out, etc.). --- The D GC is non-reallocating. That's why the above suggestion.
Dec 23 2005
parent Frank Benoit <frank_DELETE_ _DELETE_drealtime.com> writes:
That was my first thought too. But not allocating in rt is not sufficient.
There could be race conditions. If you have one reference (refa) to an
object and *move* this to another reference (refb) in the rt-thread, one
can think about the following scenario...
- start of gc collecting cycle
- gc scans refb, which is null
- interrupt, switch to rt
- in rt thread refb = refa; refa = null;
- switch back to non-rt, gc continues ('thinking' refb is null)
- scans refa, which is null 
-> GC: Oh, no ref to obj, I can free it!

This can happen, for example when refences are passed between rt and non rt
(or vice versa) through queues. So I think it is not so rare, that this
race condition exists. And think about, how hard it will be to find or even
reproduce this bug :))

Frank
Dec 25 2005