Fast (real-time) memory allocation wanted.

Fast (real-time) memory allocation wanted.

Post by Ma » Thu, 25 Apr 2002 20:48:15



Hi. I am using RTAI and need a replacement for malloc/free (actually, new/delete
operators). I suppose malloc uses linked lists of small blocks and so it leads
to fragmentation related problems and eventual performance loss due to it having
to traversing linked list after a block of adequate size. I am thinking of using
memory pools and overload new/delete to use the pools but I would like to listen
to alternate ideas if available. I learned of hoard but I suppose it suffers of
malloc's very same problems in uniprocessor systems.

BTW my stuff is going to run in userspace under lxrt so kmalloc/kfree are out of
question AFAIK.

Note: I am not very experienced on Linux system programming so the assumptions
above come from a guy who's developed DOS like systems. Please correct me should
I making wrong assumptions.

TIA.

Elder.

 
 
 

Fast (real-time) memory allocation wanted.

Post by AKA Uncle B » Thu, 25 Apr 2002 22:41:23



> Hi. I am using RTAI and need a replacement for malloc/free (actually, new/delete

This is a slightly more complex problem than it seems at first sight.
There are some blindingly fast algorithms you can use if, for example,
all the blocks you need to allocate are about the same size. It's also
possible to go very fast if you simply need to do a slew of allocates
then free the whole lot at once. Can you tell us a bit more about the
application?

--
I am Robert Billing, Christian, inventor, traveller, cook and animal
lover, I live near 0:46W 51:22N.  http://www.tnglwood.demon.co.uk/
"It burned me from within. It quickened; I was with book as a woman
is with child." CS Lewis - Till we have faces, Ch 21.

 
 
 

Fast (real-time) memory allocation wanted.

Post by CBFalcone » Thu, 25 Apr 2002 22:53:41



> Hi. I am using RTAI and need a replacement for malloc/free (actually, new/delete
> operators). I suppose malloc uses linked lists of small blocks and so it leads
> to fragmentation related problems and eventual performance loss due to it having
> to traversing linked list after a block of adequate size. I am thinking of using
> memory pools and overload new/delete to use the pools but I would like to listen
> to alternate ideas if available. I learned of hoard but I suppose it suffers of
> malloc's very same problems in uniprocessor systems.

You can take a look at:

  <http://cbfalconer.home.att.net/download/nmalloc.zip>

for an implementation.  It does not lose performance, since all
operations are O(1).  The debugging macros, which also serve as
comments, depend on GNU extensions.  I had a choice of that or C99
usage, and since I had GCC and did/do not have a C99 compiler, I
chose the extension.  Obviously fragmentation can occur.  You can
hand it an initial block to manage with the first call on sbrk,
and fail further calls, if you want it to manage all available
memory.

Note the licencing.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

 
 
 

Fast (real-time) memory allocation wanted.

Post by Robert Kais » Fri, 26 Apr 2002 17:23:06




Quote:> Hi. I am using RTAI and need a replacement for malloc/free (actually, new/delete
> operators). I suppose malloc uses linked lists of small blocks and so it leads
> to fragmentation related problems and eventual performance loss due to it having
> to traversing linked list after a block of adequate size. I am thinking of using
> memory pools and overload new/delete to use the pools but I would like to listen
> to alternate ideas if available. I learned of hoard but I suppose it suffers of
> malloc's very same problems in uniprocessor systems.

> BTW my stuff is going to run in userspace under lxrt so kmalloc/kfree are out of
> question AFAIK.

There are several fast allocator algorithms. Am IMHO good one that seems
to be what you are looking for is described here:

http://www.usenix.org/publications/library/proceedings/bos94/bonwick....

Actually, the linux kernel contains an implementation of this "slab
allocator" algorithm that is not too hard to rip and use in a user
space environment.

However, be warned that (IMHO) all methods of dynamic memory allocation
cause problems when used in a real-time environment. They may be fast
on average, but their worst-case execution time can be quite long and
you cannot predict when such delays will happen. In real-time, it is
usually better to stay away from dynamic allocations altogether.

Rob

----------------------------------------------------------------
Robert Kaiser                     email: rkaiser AT sysgo DOT de
SYSGO RTS GmbH                    http://www.elinos.com
Klein-Winternheim / Germany       http://www.sysgo.de

 
 
 

Fast (real-time) memory allocation wanted.

Post by AKA Uncle B » Fri, 26 Apr 2002 20:32:35



> However, be warned that (IMHO) all methods of dynamic memory allocation
> cause problems when used in a real-time environment. They may be fast
> on average, but their worst-case execution time can be quite long and
> you cannot predict when such delays will happen. In real-time, it is
> usually better to stay away from dynamic allocations altogether.

In general this is true. However I have made memory allocation
algorithms for use in TV broadcasting with very short and predictable
worst-case times. However this has usually involved a penalty in another
direction, such as imposing a very low ceiling on the size of the blocks
that can be allocated.

On occasion this doesn't matter. If you're allocating I/O buffers or
message packets of fixed sizes it's perfectly acceptable. If you need a
general replacement for malloc() it isn't.

The only answer I can give without knowing the problem in detail is a
definite maybe.

--
I am Robert Billing, Christian, inventor, traveller, cook and animal
lover, I live near 0:46W 51:22N.  http://www.tnglwood.demon.co.uk/
"It burned me from within. It quickened; I was with book as a woman
is with child." CS Lewis - Till we have faces, Ch 21.

 
 
 

Fast (real-time) memory allocation wanted.

Post by Michael Schnel » Fri, 26 Apr 2002 20:41:58


AFAIK, traditionally, malloc is a two-step process.

The first stage works only in the user program itself (implemented e.g. in
libc). This stage works on a block of memory of contiguous bytes in virtual
address space) and assigns solid chunks of same with malloc(), unassigns
them with free() and knows about the gaps. Those memory chunks are never
moved physically, so there is no maintenance to reduce fragmentation. The
first stage is independent from the OS and does not affect any other
processes.

If malloc() needs more space than available in a gap, the second stage is
called. Here the big block is increased by having the OS assign more
physical memory to the end of it (explicitly via a system call or implicitly
by accessing the an unassigned memory location and having the system
automatically increase the allocated space, if the OS supports auto-growing
blocks). I suppose this memory is not freed before the program terminates.

This system call can take a huge time and might block _all_ user processes
temporarily.

Hope that helps.

-Michael Schnell, Lumino GmbH,
 Oppumer Stra?e 81-83, D-47799 Krefeld, Germany.

 Tel.: +49-2151-8196-72  Fax: +49-2151-8196-66-72

 
 
 

Fast (real-time) memory allocation wanted.

Post by CBFalcone » Sat, 27 Apr 2002 06:28:20



... snip ...

> There are several fast allocator algorithms. Am IMHO good one that
> seems to be what you are looking for is described here:

> http://www.usenix.org/publications/library/proceedings/bos94/bonwick....

> Actually, the linux kernel contains an implementation of this
> "slab allocator" algorithm that is not too hard to rip and use in
> a user space environment.

> However, be warned that (IMHO) all methods of dynamic memory
> allocation cause problems when used in a real-time environment.
> They may be fast on average, but their worst-case execution time
> can be quite long and you cannot predict when such delays will
> happen. In real-time, it is usually better to stay away from
> dynamic allocations altogether.

As I pointed out in my earlier posting on this thread, my nmalloc
system has all algorithms O(1), and no searches are needed.  The
real-time problem is not the possibility of extra time, but the
possibility of failure.  If the client software can cope with
that, there is no actual real-time impediment.  However, that is a
fairly large IF.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

 
 
 

Fast (real-time) memory allocation wanted.

Post by Ma » Sat, 27 Apr 2002 08:19:05



Quote:

> In general this is true. However I have made memory allocation
> algorithms for use in TV broadcasting with very short and predictable
> worst-case times. However this has usually involved a penalty in another
> direction, such as imposing a very low ceiling on the size of the blocks
> that can be allocated.

This is more or less what I was thinking of when I posted my question.

Quote:

> On occasion this doesn't matter. If you're allocating I/O buffers or
> message packets of fixed sizes it's perfectly acceptable. If you need a
> general replacement for malloc() it isn't.

Actually, the idea is allocating small chunks of memory for internal
data exchange (between objects) and inter process communication.
Dynamic allocation by overloading new and delete will facilitate
things a lot (we have much software already written) but it must be
deterministic. I was thinking of buffer pools as you proposed but
wanted to know if there could be pret a porter alternatives as I am
farly inexperienced regarding Linux programming.

Regards.

Elder.

 
 
 

Fast (real-time) memory allocation wanted.

Post by AKA Uncle B » Sat, 27 Apr 2002 15:19:32



> Actually, the idea is allocating small chunks of memory for internal
> data exchange (between objects) and inter process communication.

In which case I'd simply allocate a lump of memory at startup, divide it
into buffers, bung them on a linked list, then allocate by taking them
off the list and free by putting them back on.

Incidentally if you take from one end of the list and put at the other
so that you delay as far as possible reusing buffers you may find that
having old data* about in freed buffers is a useful aid to
debugging. The freed buffers are a sort of "flight recorder" of what the
program's done.

--
I am Robert Billing, Christian, inventor, traveller, cook and animal
lover, I live near 0:46W 51:22N.  http://www.veryComputer.com/
"It burned me from within. It quickened; I was with book as a woman
is with child." CS Lewis - Till we have faces, Ch 21.

 
 
 

Fast (real-time) memory allocation wanted.

Post by Rufus V. Smit » Sat, 27 Apr 2002 09:51:37




> ... snip ...

> > There are several fast allocator algorithms. Am IMHO good one that
> > seems to be what you are looking for is described here:

> > http://www.usenix.org/publications/library/proceedings/bos94/bonwick....

> > Actually, the linux kernel contains an implementation of this
> > "slab allocator" algorithm that is not too hard to rip and use in
> > a user space environment.

> > However, be warned that (IMHO) all methods of dynamic memory
> > allocation cause problems when used in a real-time environment.
> > They may be fast on average, but their worst-case execution time
> > can be quite long and you cannot predict when such delays will
> > happen. In real-time, it is usually better to stay away from
> > dynamic allocations altogether.

> As I pointed out in my earlier posting on this thread, my nmalloc
> system has all algorithms O(1), and no searches are needed.  The
> real-time problem is not the possibility of extra time, but the
> possibility of failure.  If the client software can cope with
> that, there is no actual real-time impediment.  However, that is a
> fairly large IF.

What is most important is that when a request is received, it is
honored.  Otherwise it's a failure.  But you should also have a
buffer zone where the application is aware there is a pending
crisis, and deal with it in some way, before there is a true failure.
This could mean pre-allocating 3 or 4  (or some number) blocks
to be used in case of failure, simultaneously setting in operation
procedures to ameliorate the situation.

Rufus

 
 
 

Fast (real-time) memory allocation wanted.

Post by Roman Fietz » Mon, 29 Apr 2002 04:38:05



Quote:> In which case I'd simply allocate a lump of memory at startup,
> divide it into buffers, bung them on a linked list, then allocate by
> taking them off the list and free by putting them back on.

That's what I do using gcc on a 68K pSOS system. I take a bunch of
equal sized blocks and put them in a single linked list. It's all
hidden below malloc/free, so all dynamic memory opertions below a
certain size are deterministic. An improvement in terms of memory
waste would evt. be to have two or more lists with different block
sizes, in case you can predict your maximum memory usage per size.

I also built in a very simple memory tagging mechanism tagging all
"allocated" memory with 0xAA55 and untagging it before I free it, so
finding memory leaks or double frees are relatively easy to find,
because I can turn on/off tagging while the program is running using
an emulator.

Roman

--

It's not a bug of my MUA that I have only two lines of signature!

 
 
 

Fast (real-time) memory allocation wanted.

Post by Michael Schnel » Wed, 01 May 2002 15:49:49



21:38

Quote:> I take a bunch of
>equal sized blocks and put them in a single linked list.


Does this really help a lot over just forcing the blocks requested by
malloc() to a multiple of a fixed size (eventually corrected by the amount
of bytes per block used by malloc to create multiples of the really used
block size) ?

-Michael Schnell, Lumino GmbH,
 Oppumer Stra?e 81-83, D-47799 Krefeld, Germany.

 Tel.: +49-2151-8196-72  Fax: +49-2151-8196-66-72

 
 
 

Fast (real-time) memory allocation wanted.

Post by Ma » Wed, 01 May 2002 19:16:26




> > In which case I'd simply allocate a lump of memory at startup,
> > divide it into buffers, bung them on a linked list, then allocate by
> > taking them off the list and free by putting them back on.

> That's what I do using gcc on a 68K pSOS system. I take a bunch of
> equal sized blocks and put them in a single linked list. It's all
> hidden below malloc/free, so all dynamic memory opertions below a
> certain size are deterministic. An improvement in terms of memory
> waste would evt. be to have two or more lists with different block
> sizes, in case you can predict your maximum memory usage per size.

That's what I intend to do:
1- malloc a big chunk of memory.
2- split in small blocks.
3- initialize these blocks with control structures. Built into these
structures is information about bool, signatures etc. I will use
several block sizes according to my system's needs.
4- create several memory pools on a per size basis using RTAI msg
queues as linked lists so I don't have to worry about race conditions.
5- wrap everything withing an myAlloc() (which will chose which pool
to take a block from) and myFree() and overload new/delete.

Quote:

> I also built in a very simple memory tagging mechanism tagging all
> "allocated" memory with 0xAA55 and untagging it before I free it, so
> finding memory leaks or double frees are relatively easy to find,
> because I can turn on/off tagging while the program is running using
> an emulator.

I have implemented a similar scheme in a previous design (real mode
x86, home made cooperative non preemptive pseudo operating system).
Helped me to find many bugs. It seems I will reuse it again somewhat
modified.

Regards.

Elder.

 
 
 

Fast (real-time) memory allocation wanted.

Post by AKA Uncle B » Wed, 01 May 2002 20:32:24



> Does this really help a lot over just forcing the blocks requested by
> malloc() to a multiple of a fixed size (eventually corrected by the amount

I think you'll find it does because it enforces a top limit on the time
an allocation can take.

--
I am Robert Billing, Christian, inventor, traveller, cook and animal
lover, I live near 0:46W 51:22N.  http://www.tnglwood.demon.co.uk/
"It burned me from within. It quickened; I was with book as a woman
is with child." CS Lewis - Till we have faces, Ch 21.

 
 
 

Fast (real-time) memory allocation wanted.

Post by VictorV » Wed, 01 May 2002 23:59:51


The malloc function is usu. too slow compared to an array of blocks.

> Does this really help a lot over just forcing the blocks requested by
> malloc() to a multiple of a fixed size (eventually corrected by the amount
> of bytes per block used by malloc to create multiples of the really used
> block size) ?

 
 
 

1. Fast Fundas Series - Real-Time (Realtime) Systems

Hello,

Here is a simple introduction to the Real time systems. Hope the beginners
find it useful.

http://www.dinkercharak.com/comp/fastfundas/rts.htm

Regards,
Dinker

---

Contents
1 Introduction to Realtime Systems
1.1 Understanding Realtime Systems
2 Some Basic Concepts and Definitions
2.1 POSIX
2.2 Process
2.3 Thread
2.4 Task
2.5 Job
2.6 Multi-Tasking
2.6.1 Cooperative Multitasking
2.6.2 Preemptive Multitasking
2.7 Finite State machine
2.8 State
2.9 State Transitions
2.10 Preemption
2.11 Context Switch
2.12 Context Switch Overhead
2.13 Synchronization
3 Scheduling
3.1 Round-Robin Scheduling
3.2 Priority Scheduling
3.3 Fixed-Priority Preemptive Round-Robin Scheduling
3.4 Rate-Monotonic Scheduling
3.5 Dynamic-Priority Preemptive Scheduling
3.6 Deadline-Monotonic Scheduling
4 Inter-Task Communication
4.1 Mutual Exclusion
4.2 Inter-Task Communication Methods
4.2.1 Shared Memory
4.2.2 Semaphores
4.2.2.1 Mutual Exclusion Using Binary Semaphores
4.2.2.2 Synchronization Using Binary Semaphores
4.2.3 Signals
4.2.3.1 Synchronization Using Signals
4.3 Priority Inversion

2. OSS for ESS1688: Recording volume?

3. Solaris2.0/2.1 Real time "Fast" timing/scheduling

4. Need help on modem setup

5. About dynamic memory database or real-time database

6. nroff 'xerox' driver

7. "Real-Time" Time Display in Console

8. Job Offer: IP storage startup Silicon Valley startup

9. Mixed Time-Share & real-Time scheduling

10. real-time vs. user-time

11. Real-time (RT) process slipping time - any ideas?

12. HELP: memory allocation debugger wanted

13. Memory allocation and de-allocation