Very Computer

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.

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.

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!

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

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.

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

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!

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.

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.

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

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!

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

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.

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.

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