Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Avoiding malloc (http://www.velocityreviews.com/forums/t442714-avoiding-malloc.html)

John Devereux 05-12-2006 07:49 AM

Avoiding malloc
 

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 05-12-2006 08:21 AM

Re: Avoiding malloc
 
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 05-12-2006 08:36 AM

Re: Avoiding malloc
 
"John Devereux" <jdREMOVE@THISdevereux.me.uk> wrote in message
news:873bff7kdl.fsf@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 05-12-2006 09:00 AM

Re: Avoiding malloc
 
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 05-12-2006 09:55 AM

Re: Avoiding malloc
 
Ian Collins <ian-news@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 05-12-2006 10:03 AM

Re: Avoiding malloc
 
"Ivan Vecerina" <INVALID_use_webform@ivan.vecerina.com> writes:

> "John Devereux" <jdREMOVE@THISdevereux.me.uk> wrote in message
> news:873bff7kdl.fsf@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 05-12-2006 10:11 AM

Re: Avoiding malloc
 
Flash Gordon <spam@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 05-12-2006 11:53 AM

Re: Avoiding malloc
 
Ivan Vecerina wrote:
> "John Devereux" <jdREMOVE@THISdevereux.me.uk> wrote in message
> news:873bff7kdl.fsf@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 05-12-2006 12:31 PM

Re: Avoiding malloc
 
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 05-12-2006 12:32 PM

Re: Avoiding malloc
 
Ben Hetland <ben.a.hetland@sintef.no> writes:

> Ivan Vecerina wrote:
>> "John Devereux" <jdREMOVE@THISdevereux.me.uk> wrote in message
>> news:873bff7kdl.fsf@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


All times are GMT. The time now is 07:58 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.