Avoiding malloc

[John Devereux]

Hi,

For a resource constrained embedded system I want to avoid malloc.

Currently I have various "library" modules that hide their data behind
opaque pointers. Because I read that was a good thing.

For example in the interface foo.h

typedef struct foo_t *foo_t;
foo_t fooNew(void);

Then in the implementation foo.c

struct foo_t
{
int private_field;
...
};
At startup (only) the application creates foo objects using the
function provided by the foo module:

foo_t bob = fooNew();

fooNew currently allocates storage by calling malloc, it knows how
much space to allocate since it has access to the private definition
of foo_t.

This all works well and is pretty standard stuff I think, but I now
would like to use some of these modules in a smaller system. The
provided malloc takes up too much space, both in code and data. Also
it is difficult to know ahead of time how much storage is being used
by the application.

What I would like to do is statically allocate storage at the
"application" level, instead of dynamically from inside the library
module. E.g.

static unsigned char bob_private_data[sizeof *foo_t];

foo_t bob = fooInit(bob_private_data);

I don't mind rewriting the modules to support this. But I can't see
how to do it at all without exposing the representation of foo_t.

I think I am just going to have to put the "private" structure
definition in the interface header, but this goes against everything I
have read about.

I am guessing it is impossible, perhaps that is why C++[cough] has to
put its "private" definitions in the headers too.

--

John Devereux

[Ian Collins]

John Devereux wrote:

Hi,

For a resource constrained embedded system I want to avoid malloc.

Currently I have various "library" modules that hide their data behind
opaque pointers. Because I read that was a good thing.

At startup (only) the application creates foo objects using the
function provided by the foo module:

foo_t bob = fooNew();

fooNew currently allocates storage by calling malloc, it knows how
much space to allocate since it has access to the private definition
of foo_t.

This all works well and is pretty standard stuff I think, but I now
would like to use some of these modules in a smaller system. The
provided malloc takes up too much space, both in code and data. Also
it is difficult to know ahead of time how much storage is being used
by the application.

What I would like to do is statically allocate storage at the
"application" level, instead of dynamically from inside the library
module. E.g.

static unsigned char bob_private_data[sizeof *foo_t];

foo_t bob = fooInit(bob_private_data);

I don't mind rewriting the modules to support this. But I can't see
how to do it at all without exposing the representation of foo_t.

If you know how many objects you are going to use, why not create an
array (pool) of them and return pointers to the array elements in the
same way malloc would return a pointer to allocated memory?

--
Ian Collins.

[Ivan Vecerina]

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk...
: For a resource constrained embedded system I want to avoid malloc.
:
: Currently I have various "library" modules that hide their data behind
: opaque pointers. Because I read that was a good thing.

This approach is a means of providing storong encapsulation - this
is good indeed, especially if you distribute a library in binary form,
or need to be able to replace the library without recompiling
all applications (e.g. for the Linux kernel or an OS-level library).

But it has drawbacks too for some applications (e.g. does create
overhead, requiring memory allocations that could be unnecessary).
So this solution is not fit for all applications.

: This all works well and is pretty standard stuff I think, but I now
: would like to use some of these modules in a smaller system. The
: provided malloc takes up too much space, both in code and data. Also
: it is difficult to know ahead of time how much storage is being used
: by the application.

Well, you could provide your own malloc with less storage overhead -
this can be simple enough if all your allocations were done at
start-up, or are done in a simple stack-like fashion ...

But seriously, if your target platform is really tight on resources
(e.g. a microcontroller with 4Kb of RAM, like I have been using),
there is no point in going through hoops to provide a high level
of encapsulation.

: I think I am just going to have to put the "private" structure
: definition in the interface header, but this goes against everything I
: have read about.

Hominem unius libri timeo. Get some other books ;)
.... and don't worry about it too much.

: I am guessing it is impossible, perhaps that is why C++[cough] has to
: put its "private" definitions in the headers too.

If you want stack-based objects, the object size at least has to
be exposed and known by user code. This does limit encapsulation.
The alternative is to accept the overhead of using heap-allocated
objects -- a solution that C++ supports well, among other idioms.
Kind regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Flash Gordon]

John Devereux wrote:

Hi,

For a resource constrained embedded system I want to avoid malloc.

Currently I have various "library" modules that hide their data behind
opaque pointers. Because I read that was a good thing.

For example in the interface foo.h

typedef struct foo_t *foo_t;
foo_t fooNew(void);
<snip>
At startup (only) the application creates foo objects using the
function provided by the foo module:

foo_t bob = fooNew();

fooNew currently allocates storage by calling malloc, it knows how
<snip>
What I would like to do is statically allocate storage at the
"application" level, instead of dynamically from inside the library
module. E.g.

static unsigned char bob_private_data[sizeof *foo_t];

foo_t bob = fooInit(bob_private_data);

I don't mind rewriting the modules to support this. But I can't see
how to do it at all without exposing the representation of foo_t.

<snip>

What might work is to have:

/* foo.c */
#include "app_config.h"
#include "foo.h"

/* define type foo_t */

static foo_t foo_private_data[APP_FOOS_REQUIRED];
....

/* app_config.h */
#define APP_FOOS_REQUIRED 10
....

Then foo_t can still be an opaque type for the application. The downside
is the library has to be rebuilt for each application against a new
app_config.h. Life is full of compromises.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[John Devereux]

Ian Collins <ia******@hotmail.com> writes:

John Devereux wrote:

Hi,

For a resource constrained embedded system I want to avoid malloc.

If you know how many objects you are going to use, why not create an
array (pool) of them and return pointers to the array elements in the
same way malloc would return a pointer to allocated memory?

The problem is that the library modules do not know how many (if any)
of their objects will be used. In fact the same library modules are
used by different "applications" with different numbers needed. (That
is the whole point of libraries, I guess!).

I suppose I could define the number needed in a application header
that is #included by the library module (my build system already has
provision for this, for tuning the libraries to the application
requirements). It does mean that I could retain the interface as-is,
with fooNew allocating from "internal" module storage rather than via
malloc.

app.h:

#define APP_FOO_QTY 2

foo.c:

#include "app.h"

#ifdef APP_FOO_QTY
#define APP_FOO_QTY 0
#endif

static struct foo_t pool[NUM_FOOS];
static int allocated;

foo_t fooNew()
{
assert(APP_FOO_QTY>allocated);
return pool[allocated++];
}

or something like that. Or I could even revert to the malloc way if
APP_FOO_QTY was not defined.

--

John Devereux

[John Devereux]

"Ivan Vecerina" <IN*****************@ivan.vecerina.com> writes:

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk...
: For a resource constrained embedded system I want to avoid malloc.
Well, you could provide your own malloc with less storage overhead -
this can be simple enough if all your allocations were done at
start-up, or are done in a simple stack-like fashion ...
Yes, actually this looks like a good solution. I should be able to
replace malloc with a trivial allocator (very much like sbrk).
But seriously, if your target platform is really tight on resources
(e.g. a microcontroller with 4Kb of RAM, like I have been using),
there is no point in going through hoops to provide a high level
of encapsulation.
It actually has 8kB of RAM total. The current malloc uses 1k+ for some
kind of hash table, then calls sbrk with 4k requests!
: I think I am just going to have to put the "private" structure
: definition in the interface header, but this goes against everything I
: have read about.

Hominem unius libri timeo. Get some other books ;)
... and don't worry about it too much.
It's just that I have several well developed modules that are well
encapsulated and I am already using on other projects. I wanted to
avoid duplicating the code just to break them all down and shoehorn
them into this new system.
: I am guessing it is impossible, perhaps that is why C++[cough] has to
: put its "private" definitions in the headers too.

If you want stack-based objects, the object size at least has to
be exposed and known by user code. This does limit encapsulation.
The alternative is to accept the overhead of using heap-allocated
objects -- a solution that C++ supports well, among other idioms.

Thanks,

--

John Devereux

[John Devereux]

Flash Gordon <sp**@flash-gordon.me.uk> writes:

What might work is to have:

/* foo.c */
#include "app_config.h"
#include "foo.h"

/* define type foo_t */

static foo_t foo_private_data[APP_FOOS_REQUIRED];
...

/* app_config.h */
#define APP_FOOS_REQUIRED 10
...

Then foo_t can still be an opaque type for the application. The
downside is the library has to be rebuilt for each application against
a new app_config.h. Life is full of compromises.

That is *amazingly* close to what I just posted as a reply to Ian
Collins suggestion of the same thing. It sent it before reading your
post, honest!

I already #include an app.h for some libraries that need fine-tuning
for the particular application, so the infrastructure is there to do
what you suggest.

--

John Devereux

[Ben Hetland]

Ivan Vecerina wrote:

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk... [...] : I am guessing it is impossible, perhaps that is why C++[cough] has to
: put its "private" definitions in the headers too.

If you want stack-based objects, the object size at least has to
be exposed and known by user code. This does limit encapsulation.

Nothing is impossible ... ;-)

If the point is to be flexible about the amount of RAM used, or only
allocate or reserve the memory at startup time, then it is possible to
encapsulate the library's definitions as follows:

1. Let the application query each library in turn about how much memory
they need, providing as input the various parameters (P) that the
library needs to determine this.

2. The main application sums up the total amount of memory, and
allocates (or by other means reserves from its pool of available memory)
this memory, so it has a starting address (a) and a size (s).

3. Complete the initialization of each library in turn, something like
the following pseudo-code:

char *q = a;
for (each library L) {
init-L( P, q, &n); // (A)
q = n;
}

At (A), the library can reserve its memory and set any pointers into
that memory block, starting at the starting address 'q' given. As memory
is "grabbed", the pointer is increased accordingly to the next available
address. (Essentially a no-overhead allocation.)

Of course the library should not "allocate" more memory during the
"init" than it initially indicated in step (1). One may or may not
bother to check that... :-)
Gained:
- The main application knows nothing about the private data used by the
libraries.
- Application can be flexible regarding memory usage.
- No "malloc overhead" (except possibly for 1 allocation).

Loss:
- Somewhat more complex ("two-stage") initialization process.
- The "size" of the objects is still known to the application, but it
doesn't have to be static (known at compile time), so it is of
relatively little use to the application.
HTH, regards,
--
-+-Ben-+-

[those who know me have no need of my name]

in comp.lang.c i read:

Hi,

For a resource constrained embedded system I want to avoid malloc.

Currently I have various "library" modules that hide their data behind
opaque pointers. Because I read that was a good thing.

For example in the interface foo.h

typedef struct foo_t *foo_t;
foo_t fooNew(void);

Then in the implementation foo.c

struct foo_t
{
int private_field;
...
};
At startup (only) the application creates foo objects using the
function provided by the foo module:

foo_t bob = fooNew();

fooNew currently allocates storage by calling malloc, it knows how
much space to allocate since it has access to the private definition
of foo_t.

This all works well and is pretty standard stuff I think, but I now
would like to use some of these modules in a smaller system. The
provided malloc takes up too much space, both in code and data. Also
it is difficult to know ahead of time how much storage is being used
by the application.
What I would like to do is statically allocate storage at the
"application" level, instead of dynamically from inside the library I don't mind rewriting the modules to support this. But I can't see
how to do it at all without exposing the representation of foo_t.
if you don't mind a pre-processor step to compute the size of the
foo_t:

foo.h:
#define LIBX_FOO_T_SIZE 48 /* perhaps via compiler option */
struct foo_fake { char goaway[LIBX_FOO_T_SIZE]; };
typedef struct foo_fake foo_t;

of course this implies that the implementation have the real definition and
that some tool would inspect it so as to obtain the size:

foo.c:
/* @SIZEME:FOO_T@ */ struct foo_real { /* your stuff here */ };
I think I am just going to have to put the "private" structure
definition in the interface header, but this goes against everything I
have read about.

that is often the easiest way. document that foo_t's structure isn't to be
inspected, then keep your whip handy for offenders. a mild alternative
that still exposes the data but in a round-about fashion that should help
expose code that is peeking (i.e., just search for uses of foo_real):

foo.h:
struct foo_real { /* your stuff here */ };
struct foo_fake { char goaway[sizeof(struct foo_real)]; };
typedef struct foo_fake foo_t;

either of these approaches has annoyance for your implementation -- in that
it is common to #include "foo.h" in foo.c, and thus it cannot use foo_t,
rather you would have to use struct foo_real and the occasional cast.

--
a signature

[John Devereux]

Ben Hetland <be***********@sintef.no> writes:

Ivan Vecerina wrote:

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk...

[...]

: I am guessing it is impossible, perhaps that is why C++[cough] has to
: put its "private" definitions in the headers too.

If you want stack-based objects, the object size at least has to
be exposed and known by user code. This does limit encapsulation.

Nothing is impossible ... ;-)

If the point is to be flexible about the amount of RAM used, or only
allocate or reserve the memory at startup time, then it is possible to
encapsulate the library's definitions as follows:

1. Let the application query each library in turn about how much memory
they need, providing as input the various parameters (P) that the
library needs to determine this.

2. The main application sums up the total amount of memory, and
allocates (or by other means reserves from its pool of available memory)
this memory, so it has a starting address (a) and a size (s).

3. Complete the initialization of each library in turn, something like
the following pseudo-code:

char *q = a;
for (each library L) {
init-L( P, q, &n); // (A)
q = n;
}

At (A), the library can reserve its memory and set any pointers into
that memory block, starting at the starting address 'q' given. As memory
is "grabbed", the pointer is increased accordingly to the next available
address. (Essentially a no-overhead allocation.)

Of course the library should not "allocate" more memory during the
"init" than it initially indicated in step (1). One may or may not
bother to check that... :-)
Gained:
- The main application knows nothing about the private data used by the
libraries.
- Application can be flexible regarding memory usage.
- No "malloc overhead" (except possibly for 1 allocation).

Loss:
- Somewhat more complex ("two-stage") initialization process.
- The "size" of the objects is still known to the application, but it
doesn't have to be static (known at compile time), so it is of
relatively little use to the application.

Interesting, thanks!

Thinking about this, it seems to me that I could just as well use the
existing scheme, replacing malloc itself by a trivial "allocate-only"
version. (My implementation should let me do this, but I could use a
different named function for clc purposes).

--

John Devereux

[Joe Smith]

"John Devereux":

Ben Hetland :

Ivan Vecerina wrote:

"John Devereux" :

If the point is to be flexible about the amount of RAM used, or only
allocate or reserve the memory at startup time, then it is possible to
encapsulate the library's definitions as follows:

1. Let the application query each library in turn about how much memory
they need, providing as input the various parameters (P) that the
library needs to determine this.

2. The main application sums up the total amount of memory, and
allocates (or by other means reserves from its pool of available memory)
this memory, so it has a starting address (a) and a size (s).

3. Complete the initialization of each library in turn, something like
the following pseudo-code:

char *q = a;
for (each library L) {
init-L( P, q, &n); // (A)
q = n;
}

At (A), the library can reserve its memory and set any pointers into
that memory block, starting at the starting address 'q' given. As memory
is "grabbed", the pointer is increased accordingly to the next available
address. (Essentially a no-overhead allocation.)

Of course the library should not "allocate" more memory during the
"init" than it initially indicated in step (1). One may or may not
bother to check that... :-)
Gained:
- The main application knows nothing about the private data used by the
libraries.
- Application can be flexible regarding memory usage.
- No "malloc overhead" (except possibly for 1 allocation).

Loss:
- Somewhat more complex ("two-stage") initialization process.
- The "size" of the objects is still known to the application, but it
doesn't have to be static (known at compile time), so it is of
relatively little use to the application.

Interesting, thanks!

Thinking about this, it seems to me that I could just as well use the
existing scheme, replacing malloc itself by a trivial "allocate-only"
version. (My implementation should let me do this, but I could use a
different named function for clc purposes).

--

John Devereux

What a good question! I think to have read a few ways to re-think the
problem, with the easiest for your implementation downthread. If one
queried the libraries with an eye to making

char *q = a;
for (each library L) {
init-L( P, q, &n); // (A)
q = n;

eventually more meaningful than a string of zeros and ones, how would one do
it? Joe

[Stephen Sprunk]

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk...

Flash Gordon <sp**@flash-gordon.me.uk> writes:

What might work is to have:

/* foo.c */
#include "app_config.h"
#include "foo.h"

/* define type foo_t */

static foo_t foo_private_data[APP_FOOS_REQUIRED];
...

/* app_config.h */
#define APP_FOOS_REQUIRED 10
...

Then foo_t can still be an opaque type for the application. The
downside is the library has to be rebuilt for each application against
a new app_config.h. Life is full of compromises.

That is *amazingly* close to what I just posted as a reply to Ian
Collins suggestion of the same thing. It sent it before reading your
post, honest!

I already #include an app.h for some libraries that need fine-tuning
for the particular application, so the infrastructure is there to do
what you suggest.

I was mentally writing the exact same code (well, I used a different macro
name) so I'd say it's the idiomatic way of doing what you want portably.

That said, if your implementation allows you to replace malloc(), that's
probably a better choice. Just don't forget to replace free() and realloc()
as well or you'll get bitten when your library (or another one added later)
tries to dispose of objects.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
*** Posted via a free Usenet account from http://www.teranews.com ***

[John Devereux]

"Stephen Sprunk" <st*****@sprunk.org> writes:

"John Devereux" <jd******@THISdevereux.me.uk> wrote in message
news:87************@cordelia.devereux.me.uk...

Flash Gordon <sp**@flash-gordon.me.uk> writes:

What might work is to have:

/* foo.c */
#include "app_config.h"
#include "foo.h"

/* define type foo_t */

static foo_t foo_private_data[APP_FOOS_REQUIRED];
...

/* app_config.h */
#define APP_FOOS_REQUIRED 10
...

I was mentally writing the exact same code (well, I used a different
macro name) so I'd say it's the idiomatic way of doing what you want
portably.

That said, if your implementation allows you to replace malloc(),
that's probably a better choice. Just don't forget to replace free()
and realloc() as well or you'll get bitten when your library (or
another one added later) tries to dispose of objects.

Actually I was planning to replace them alright - with assert(0). I
don't want to have dynamic allocation/free activity during the main
program execution. I would be worried about fragmentation and running
out of heap space. The idea is that library modules get just once
chance to allocate the memory they need, during startup of the
program.

--

John Devereux

[Ben Hetland]

John Devereux wrote:

Actually I was planning to replace them alright - with assert(0). I
don't want to have dynamic allocation/free activity during the main
program execution.
In that case maybe you should consider "replacing" you malloc
implementation with an assert(0) as well? That way you're sure that none
of your libraries have a hidden malloc somewhere in there. Then you
could "hide" your real allocation in a routine called something
different, like malloc_once or whatever...

The idea is that library modules get just once
chance to allocate the memory they need, during startup of the
program.

....and that would also assure that you don't silently "grow" your
allocated space during runtime (after init), causing the program to
exhaust its resources eventually if left to run long enough.

--
-+-Ben-+-