[ECOS] Scheduler lock in Doug Lea's malloc implementation

[ECOS] Scheduler lock in Doug Lea's malloc implementation

[bob.koninckx]

Hello list,

A couple of weeks ago, I posted the question below without any reaction so far. However, I can hardly imagine that none of the eCos maintainers can give some insight on this, so I guess the question went unnoticed somehow. I guess it doesn't hurt to ask again.

Thanks,

Bob


Hi,

Can someone explain me why the default memory allocator locks the scheduler? I would expect it to be legitimate for a low priority thread with no real time constraints to do dynamic memory allocation without influencing the real-time behaviour of threads with real-time constraints, as long as they have a higher priority. We experienced timing problems with high priority real-time threads that do not touch the heap because of dynamic memory allocation in a lower priority thread without real-time constraints and traced it down to the code snippet from packages/services/memalloc/common/current/include/mempolt2.inl below

// get some memory; wait if none available
template <class T>
inline cyg_uint8 *
Cyg_Mempolt2<T>::alloc( cyg_int32 size )
{
    CYG_REPORT_FUNCTION();


    // Prevent preemption
    Cyg_Scheduler::lock();
    CYG_ASSERTCLASS( this, "Bad this pointer");


    cyg_uint8 *ret;
    ret = pool.try_alloc( size );
    if ( ret ) {
        Cyg_Scheduler::unlock();
        CYG_ASSERTCLASS( this, "Bad this pointer");
        CYG_REPORT_RETVAL( ret );
        return ret;
    }


    Cyg_Thread *self = Cyg_Thread::self();


    Mempolt2WaitInfo waitinfo( size );


    CYG_MEMALLOC_FAIL(size);


    self->set_wait_info( (CYG_ADDRWORD)&waitinfo );
    self->set_sleep_reason( Cyg_Thread::WAIT );
    self->sleep();
    queue.enqueue( self );


    CYG_ASSERT( 1 == Cyg_Scheduler::get_sched_lock(),
                "Called with non-zero scheduler lock");


    // Unlock scheduler and allow other threads to run
    Cyg_Scheduler::unlock();
[...]

Thanks,

Bob





--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation

[Bart Veer]

>>>>> "Bob" == bob koninckx <bob.koninckx@o-3s.com> writes:

    Bob> Can someone explain me why the default memory allocator locks
    Bob> the scheduler ? I would expect it to be legitimate for a low
    Bob> priority thread with no real time constraints to do dynamic
    Bob> memory allocation without influencing the real-time behaviour
    Bob> of threads with real-time constraints, as long as they have a
    Bob> higher priority.

I was not involved in the initial implementation of the memory
allocators, so this is not gospel. I do remember that the uITRON
compatibility layer imposed various requirements.

I believe the theory is that the memory allocators should be very
fast. If you use an alternative locking mechanism like a mutex, both
the lock and unlock functions will themselves lock and unlock the
scheduler. When you have a memory allocator that takes a comparable
amount of time to a mutex operation, you are better off locking the
scheduler around the memory allocation rather than going through mutex
lock and unlock calls.

If you are using a fixed block memory pool as per mfiximpl.hxx then
that theory may well be correct. If you are using some other allocator
such as dlmalloc then I suspect the theory is wrong and for such
allocators the code should use a mutex instead, but I have not done
any measurements. There are going to be complications, e.g.
average vs. maximum times.

Bart

-- 
Bart Veer                       eCos Configuration Architect
http://www.ecoscentric.com/     The eCos and RedBoot experts

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation - be real careful

[Roy E Richardson]

----- Original Message ----- 
From: "Bart Veer" <bartv@ecoscentric.com>
To: <bob.koninckx@o-3s.com>
Cc: <ecos-discuss@sources.redhat.com>
Sent: Thursday, September 07, 2006 12:40 PM
Subject: Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation


>>>>>> "Bob" == bob koninckx <bob.koninckx@o-3s.com> writes:
>
>    Bob> Can someone explain me why the default memory allocator locks
>    Bob> the scheduler ? I would expect it to be legitimate for a low
>    Bob> priority thread with no real time constraints to do dynamic
>    Bob> memory allocation without influencing the real-time behaviour
>    Bob> of threads with real-time constraints, as long as they have a
>    Bob> higher priority.
>
> I was not involved in the initial implementation of the memory
> allocators, so this is not gospel. I do remember that the uITRON
> compatibility layer imposed various requirements.
>
> I believe the theory is that the memory allocators should be very
> fast. If you use an alternative locking mechanism like a mutex, both
> the lock and unlock functions will themselves lock and unlock the
> scheduler. When you have a memory allocator that takes a comparable
> amount of time to a mutex operation, you are better off locking the
> scheduler around the memory allocation rather than going through mutex
> lock and unlock calls.
>
> If you are using a fixed block memory pool as per mfiximpl.hxx then
> that theory may well be correct. If you are using some other allocator
> such as dlmalloc then I suspect the theory is wrong and for such
> allocators the code should use a mutex instead, but I have not done
> any measurements. There are going to be complications, e.g.
> average vs. maximum times.
>
> Bart
>
> -- 
> Bart Veer                       eCos Configuration Architect
> http://www.ecoscentric.com/     The eCos and RedBoot experts
>
> -- 

The data that describes what portion(s) of the pool is common to all threads 
accessing the pool.
Each successful allocate/deallocate request results at least 1 instance of a 
read of a portion of that common data,
a varying quantifty of instructions to evaluate, and finally updates to the 
affected data value(s).

The above "read/process/write" sequence is commonly referred to as a 
"critical instruction sequence" that requires
a guaratee that absolutely precludes any potential of a 2nd operation from 
occurring while a prior one is in progress.
To not do so allows for sporatic, unpredictable timing errors that are 
extremely difficult to recognize, let alone identify and correct.

For Mr. Lee's malloc, the use of "scheduler lock/unlock" sequences is a 
minimal protection, valid ONLY IF one can be certain that no interrupt 
routine uses either allocate or dellocate.  As I recall, there is a 
reference to this in the source comments, but I don't recall that free() / 
malloc() requests during an ISR will generate an exception if attempted.

> Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
> and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss
>
> 



-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss

Re: [ECOS] Scheduler lock in Doug Lea's malloc implementation - be real careful

[Tim michals]

IMHO, you should use memory pools
http://ecos.sourceware.org/docs-latest/ref/memalloc.html,
also my understanding is that most OS do the same
allocation scheme.  Thus if realtime is required, each
task must control its own memory allocation pool.  

--- Roy E Richardson <eng_at_play@cox.net> wrote:

> 
> ----- Original Message ----- 
> From: "Bart Veer" <bartv@ecoscentric.com>
> To: <bob.koninckx@o-3s.com>
> Cc: <ecos-discuss@sources.redhat.com>
> Sent: Thursday, September 07, 2006 12:40 PM
> Subject: Re: [ECOS] Scheduler lock in Doug Lea's
> malloc implementation
> 
> 
> >>>>>> "Bob" == bob koninckx <bob.koninckx@o-3s.com>
> writes:
> >
> >    Bob> Can someone explain me why the default
> memory allocator locks
> >    Bob> the scheduler ? I would expect it to be
> legitimate for a low
> >    Bob> priority thread with no real time
> constraints to do dynamic
> >    Bob> memory allocation without influencing the
> real-time behaviour
> >    Bob> of threads with real-time constraints, as
> long as they have a
> >    Bob> higher priority.
> >
> > I was not involved in the initial implementation
> of the memory
> > allocators, so this is not gospel. I do remember
> that the uITRON
> > compatibility layer imposed various requirements.
> >
> > I believe the theory is that the memory allocators
> should be very
> > fast. If you use an alternative locking mechanism
> like a mutex, both
> > the lock and unlock functions will themselves lock
> and unlock the
> > scheduler. When you have a memory allocator that
> takes a comparable
> > amount of time to a mutex operation, you are
> better off locking the
> > scheduler around the memory allocation rather than
> going through mutex
> > lock and unlock calls.
> >
> > If you are using a fixed block memory pool as per
> mfiximpl.hxx then
> > that theory may well be correct. If you are using
> some other allocator
> > such as dlmalloc then I suspect the theory is
> wrong and for such
> > allocators the code should use a mutex instead,
> but I have not done
> > any measurements. There are going to be
> complications, e.g.
> > average vs. maximum times.
> >
> > Bart
> >
> > -- 
> > Bart Veer                       eCos Configuration
> Architect
> > http://www.ecoscentric.com/     The eCos and
> RedBoot experts
> >
> > -- 
> 
> The data that describes what portion(s) of the pool
> is common to all threads 
> accessing the pool.
> Each successful allocate/deallocate request results
> at least 1 instance of a 
> read of a portion of that common data,
> a varying quantifty of instructions to evaluate, and
> finally updates to the 
> affected data value(s).
> 
> The above "read/process/write" sequence is commonly
> referred to as a 
> "critical instruction sequence" that requires
> a guaratee that absolutely precludes any potential
> of a 2nd operation from 
> occurring while a prior one is in progress.
> To not do so allows for sporatic, unpredictable
> timing errors that are 
> extremely difficult to recognize, let alone identify
> and correct.
> 
> For Mr. Lee's malloc, the use of "scheduler
> lock/unlock" sequences is a 
> minimal protection, valid ONLY IF one can be certain
> that no interrupt 
> routine uses either allocate or dellocate.  As I
> recall, there is a 
> reference to this in the source comments, but I
> don't recall that free() / 
> malloc() requests during an ISR will generate an
> exception if attempted.
> 
> > Before posting, please read the FAQ:
> http://ecos.sourceware.org/fom/ecos
> > and search the list archive:
> http://ecos.sourceware.org/ml/ecos-discuss
> >
> > 
> 
> 
> 
> -- 
> Before posting, please read the FAQ:
> http://ecos.sourceware.org/fom/ecos
> and search the list archive:
> http://ecos.sourceware.org/ml/ecos-discuss
> 
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss