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, 


A rt thread can interrupt the running program at any time. The only way, to
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).


I don"t understand this. How can a thread be the owner of memory? In my
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.  


In RTAI the rt threads are first created as normal posix pthreads. Later,
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, 


 A rt thread can interrupt the running program at any time. The only way, to
 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).


 I don"t understand this. How can a thread be the owner of memory? In my
 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?  


Normal desktop environment have a undeterministic timing. If I start a large
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.


After your first posting I realized, that it is an issue. If the rt task
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.


Now with the knowledge from you, I know that I have to try to create the rt
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/


I will go for it. I think the next few days are reserved for 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).


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.


 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.

// 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?


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