Avoiding malloc

Discussion in 'C Programming' started by John Devereux, May 12, 2006.

  1. 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
     
    John Devereux, May 12, 2006
    #1
    1. Advertising

  2. John Devereux

    Ian Collins Guest

    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.
     
    Ian Collins, May 12, 2006
    #2
    1. Advertising

  3. "John Devereux" <> wrote in message
    news:...
    : 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
     
    Ivan Vecerina, May 12, 2006
    #3
  4. John Devereux

    Flash Gordon Guest

    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
     
    Flash Gordon, May 12, 2006
    #4
  5. Ian Collins <> 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, May 12, 2006
    #5
  6. "Ivan Vecerina" <> writes:

    > "John Devereux" <> wrote in message
    > news:...
    > : 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, May 12, 2006
    #6
  7. Flash Gordon <> 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
     
    John Devereux, May 12, 2006
    #7
  8. John Devereux

    Ben Hetland Guest

    Ivan Vecerina wrote:
    > "John Devereux" <> wrote in message
    > news:...

    [...]
    > : 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-+-
     
    Ben Hetland, May 12, 2006
    #8
  9. 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
     
    those who know me have no need of my name, May 12, 2006
    #9
  10. Ben Hetland <> writes:

    > Ivan Vecerina wrote:
    >> "John Devereux" <> wrote in message
    >> news:...

    > [...]
    >> : 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
     
    John Devereux, May 12, 2006
    #10
  11. John Devereux

    Joe Smith Guest

    "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
     
    Joe Smith, May 12, 2006
    #11
  12. "John Devereux" <> wrote in message
    news:...
    > Flash Gordon <> 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 ***
     
    Stephen Sprunk, May 12, 2006
    #12
  13. "Stephen Sprunk" <> writes:

    > "John Devereux" <> wrote in message
    > news:...
    >> Flash Gordon <> 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
     
    John Devereux, May 12, 2006
    #13
  14. John Devereux

    Ben Hetland Guest

    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-+-
     
    Ben Hetland, May 12, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John
    Replies:
    13
    Views:
    710
  2. ravi
    Replies:
    0
    Views:
    457
  3. Peter
    Replies:
    34
    Views:
    1,969
    Richard Tobin
    Oct 22, 2004
  4. porting non-malloc code to malloc

    , Feb 18, 2005, in forum: C Programming
    Replies:
    3
    Views:
    485
    Walter Roberson
    Feb 19, 2005
  5. Johs32

    to malloc or not to malloc??

    Johs32, Mar 30, 2006, in forum: C Programming
    Replies:
    4
    Views:
    328
    Captain Winston
    Mar 30, 2006
Loading...

Share This Page