Paper on dynamic memory allocation for real-time systems

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
"Dynamic memory allocation has been used for decades. However, it has
seldom been used in real-time systems since the worst case of spatial  
and temporal requirements for allocation and deallocation operations is  
either unbounded or bounded but with a very large bound.

In this paper, a new allocator called TLSF (Two Level Segregated Fit) is  
presented. TLSF is designed and implemented to accommodate real-time  
constraints. The proposed allocator exhibits time-bounded behaviour,  
O(1), and maintains a very good execution time. This paper describes in  
detail the data structures and functions provided by TLSF. We also  
compare TLSF with a representative set of allocators
regarding their temporal cost and fragmentation."

<http://www.gii.upv.es/tlsf/files/jrts2008.pdf

Re: Paper on dynamic memory allocation for real-time systems
On Thu, 19 Oct 2017 12:44:43 -0400, bitrex wrote:

Quoted text here. Click to load it


Never really understood why C had such a notorious issue with DMA (the  
free() function in particular) but I'm willing to be disabused of my  
outstanding ignorance of the matter if anyone knows.



--  
This message may be freely reproduced without limit or charge only via  
the Usenet protocol. Reproduction in whole or part through other  
We've slightly trimmed the long signature. Click to see the full one.
Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 09:38 AM, Cursitor Doom wrote:
Quoted text here. Click to load it
What? DMA has nothing to do with memory allocation...no matter the  
language, it's purely hardware driven, once set up by software.


Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 01:59 PM, Bill Martin wrote:
Quoted text here. Click to load it

Dynamic Memory Allocation DMA not Direct Memory Access DMA

Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 11:01 AM, bitrex wrote:
Quoted text here. Click to load it

Oh nooo, more overloading.. :-)


Re: Paper on dynamic memory allocation for real-time systems
Quoted text here. Click to load it

AIUI the issue is heap fragmentation when you don't have abundant RAM. A me
mory allocator has conflicting requirements: it needs to make efficient use
 of the available memory as well as being fast and general. As memory is al
located in odd-sized chunks and then freed in whatever order, the allocator
 has to try to combine the freed blocks into larger ones. In languages cont
aining pointers, the allocator can't move allocated blocks around, so the s
ize of the combined chunks depends sensitively on the allocated sizes and t
he order in which they're freed.  

When there's lots of memory available, this isn't a terrible problem, but s
eriously RAM-constrained systems such as MCUs are another story. If all the
 allocated blocks are the same size, it's easy.  

Cheers

Phil Hobbs

Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 02:16 PM, snipped-for-privacy@gmail.com wrote:
Quoted text here. Click to load it

The algorithm in the paper relies heavily on the "find first set bit in  
a word" CPU instruction which unfortunately most 8 bit processors at  
least don't have.

Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 02:26 PM, bitrex wrote:
Quoted text here. Click to load it

Forgot to add becauuuuse the only software-fallback that's going to have  
a deterministic execution time would is probably a full lookup table  
which is going to be a suck with a 16 bit pointer size

Re: Paper on dynamic memory allocation for real-time systems
On 10/22/2017 12:38 PM, Cursitor Doom wrote:
Quoted text here. Click to load it

It's not just C all non-garbage collected languages rely on the user to  
either use the default dynamic memory allocation algorithm (often just  
an interface to the kernel's implementation on a desktop processor) or  
come up with their own.

The implementations of malloc and free that come with C's standard  
library are always compromises between portability, speed, size, and  
fragmentation rate and aren't terribly suited to applications that have  
small heap sizes but also need lots of data structures allocated and  
de-allocated during execution.

This was an issue even back in the DOS days when you only had 640k of  
conventional memory; I remember an old video game where the authors had  
set aside 64k of conventional memory with some custom implementation of  
malloc to dynamically load scripts and objects as the game progressed.  
64k should've in theory been plenty to store every script the program  
needed at any given time, except for the fact that being humans in such  
a large project they made mistakes and forgot to free memory in the pool  
they had allocated, causing a leak.

Nothing more fun than when you're about to fight the big boss bad and  
get an "Out of heap space" fatal error.

The idea with this whitepaper is to address the fact that many dynamic  
allocation algorithms are unsuitable for real time systems (i.e. ones  
that don't run inside a managing OS and can't just say wait for the  
network card driver to handle sending packets in a timely manner when  
the app itself gets tied up) because their execution time is  
theoretically unbounded; _usually_ it works OK but you can't say  
mathematically with certainty when it it'll come up with a free block  
for your data or if it ever will.

Re: Paper on dynamic memory allocation for real-time systems
On Sun, 22 Oct 2017 14:23:40 -0400, bitrex wrote:

Quoted text here. Click to load it

Wasn't it Bill Gates <spit!> who once said 64k should be enough for  
anyone? Some futurist!



--  
This message may be freely reproduced without limit or charge only via  
the Usenet protocol. Reproduction in whole or part through other  
We've slightly trimmed the long signature. Click to see the full one.
Re: Paper on dynamic memory allocation for real-time systems
Quoted text here. Click to load it

640k, to give the d. his due.

Cheers

Phil Hobbs  

Re: Paper on dynamic memory allocation for real-time systems
On Sun, 22 Oct 2017 16:38:15 -0000 (UTC), Cursitor Doom

Quoted text here. Click to load it

I have often wondered, why C-programmers are so keen of using dynamic
memory allocation instead of stack allocation. Is it because some
early processors had a very limited stack, typically intended only for
return addresses ?

In Pascal, you could allocate short lived memory areas on  the stack
and pass a pointer to that stack area as a procedure parameter. Of
course, this was simplified by having source level nested procedures,
so you didn't have to explicitly pass these pointers to low level
procedures, since these allocations were readily visible on the outer
source code nesting level.


Re: Paper on dynamic memory allocation for real-time systems
On 23/10/17 06:17, snipped-for-privacy@downunder.com wrote:
Quoted text here. Click to load it

The programming environment (language+libraries) is key,
since they are the foundation which enables/limits what
it possible.

There are such C-based environments which attempt to
force stack-based allocation via forcing a particular
programming style, but in my experience they don't
bother to /clearly/ say that is the driving force.
That's annoying, since it makes /learning/ the style
more difficult.

Two examples of such are
1) the old Apple iphone environment Cocoa, which is
an event-based library on top of Objective-C (the
latter is Smalltalk based messaging on top of C)
2) protothreads, which are extremely lightweight
stackless threads designed for severely memory
constrained systems, such as small embedded systems

It is notable that Apple has finally given up on that
approach, and is using a modern language, Swift.

Re: Paper on dynamic memory allocation for real-time systems
On 23/10/17 07:17, snipped-for-privacy@downunder.com wrote:
Quoted text here. Click to load it

The two key points are memory fragmentation (which has already been
mentioned) and non-deterministic timing.  In embedded systems or other
software with constraints on timing, dynamic memory allocation and
deallocation can easily be a problem because it is very difficult to
predict the timing - sometimes the functions run quickly, sometimes they
can take a long time.

There is an additional challenge that has become more relevant in recent
times - it gets really complicated when you have multiple threads or
multiple processors trying to do such allocations.

Quoted text here. Click to load it

Many C programmers are quite happy with memory allocated on the stack.
There are two ways of doing it - VLAs and alloca().  These have the same
uses as stack allocated memory in Pascal - and the same advantages and
disadvantages regarding lifetime.



Re: Paper on dynamic memory allocation for real-time systems
On 10/23/2017 05:33 AM, David Brown wrote:

Quoted text here. Click to load it

Large stack allocations are discouraged by the CERT-C standard, for  
security reasons:

<https://www.securecoding.cert.org/confluence/display/CINT/MEM05-C.+Avoid+large+stack+allocations

"Stack overflow has been implicated in Toyota unintended acceleration  
cases, where Camry and other Toyota vehicles accelerated unexpectedly.  
Michael Barr testified at the trial that a stack overflow could corrupt  
the critical variables of the operating system, because they were  
located in memory adjacent to the top of the stack [Samek 2014]."

alloca() can be useful but it isn't ISO C so strictly speaking is  
non-portable. I've also read that unfortunately even the non-portable  
versions included with compilers for some architectures are buggy.



Re: Paper on dynamic memory allocation for real-time systems
On 23/10/17 18:00, bitrex wrote:
Quoted text here. Click to load it

Basically, the rule is "don't write buggy code".  If you don't know it
is safe to allocate something on the stack (with a VLA, an alloca, or
just any old variable), then don't do it.  The same applies to calling
the function "foo()", or doing anything else in a program.

Quoted text here. Click to load it

alloca() is in Posix, and thus is portable across a fast range of C
implementations.  It is also supported by most serious non-Posix
compilers and libraries.  Certainly a compiler can be standards
conforming and not support it, but such compilers will be rare.  (There
are certainly plenty of compilers that don't support alloca, but they
are highly unlikely to support C11, C99 or even C90 fully.)

I have not heard of compilers with buggy alloca.  But it is not a
function I have used, as far as I can remember (I have used VLAs
sometimes), and there are lots of compilers around.  However, it is not
a feature that is particularly hard to get right.



Re: Paper on dynamic memory allocation for real-time systems
On 24/10/17 09:19, David Brown wrote:
Quoted text here. Click to load it

Without commenting on the rest of your post, that sentiment
is unhelpful motherhood and apple pie.

I have simple rule which is very useful at cutting through
the spiel from salesmen and politicians. Simply invert the
statement, and if the result is manifest nonsense, then
the original statement carries no useful information.

In this case "write buggy code" would be manifest nonsense,
so "don't write buggy code", while true, is unhelpful.

Perhaps it would be better to choose a tool that gets the
job done with reduced ways of introducing tool-specific bugs.

Re: Paper on dynamic memory allocation for real-time systems
On 24/10/17 11:08, Tom Gardner wrote:
Quoted text here. Click to load it

Yes - but that is /precisely/ the point.

There is nothing wrong with allocating memory on the stack - done
properly, it is more efficient and safer (for some meanings of "safer")
than allocating memory on the heap or other memory pools.  There is no
reason whatsoever to suppose that Toyota's software here would have
worked correctly had the memory been allocated on the heap rather than
the stack.  Their problem was allocating memory of unknown size without
due care - /not/ that they were allocating memory on the stack.

And the way to avoid the kinds of troubles they had is not by arbitrary
rules such as "don't put big variables on the stack" - it is by using
good development practices which hinder or catch all sorts of bugs.
Code reviews, static analysis, testing methodologies, measurements, etc.
 It might well be that a code review spots a non-conformance with the
style guide when they allocate a large object on the stack - it might
well be that allocating a large object on the stack causes the static
analysis to through up an error.  But those are consequences of solving
the root issues.  Banning large stack allocations is just putting a
band-aid over a cancer tumour.



Quoted text here. Click to load it

I was going to snip this, but it's a nice rule that I plan to copy :-)

Quoted text here. Click to load it


Re: Paper on dynamic memory allocation for real-time systems
On 10/24/2017 05:08 AM, Tom Gardner wrote:
Quoted text here. Click to load it

Walking a tightrope with a net tends to make you careless and prone to  
accidents, so remove the net and just learn to be more careful!

Re: Paper on dynamic memory allocation for real-time systems
On 24/10/17 21:48, bitrex wrote:
Quoted text here. Click to load it

So remove airbags in cars, and replace them with spikes?

That would make things safer by slowing drivers down
unnecessarily, just as the probability of tool-induced
bugs slows down developers unnecessarily.

Site Timeline