Software memory management reengineering

Discussion in 'C Programming' started by jacob navia, Oct 13, 2007.

  1. jacob navia

    jacob navia Guest

    Suppose that you have a module that always allocates
    memory without ever releasing it because the guy that
    wrote it was lazy, as lazy as me.

    Now, you want to reuse it in a loop. What do you do?

    Contrary to some people that will start crying to that
    &@@""#~ programmer that wrote this sh!!!! you keep
    your cool and you do the following:

    1) Since the program always call malloc and never free()
    you allocate a big chunk of memory and each time that the
    program calls malloc, you replace those calls with another
    that allocates from that memory heap.

    2) When the program finishes you free all memory witha single
    free() call.

    Caveats. The program should never call directly
    realloc. Watch for calloc too.

    I have done this many times. Actually programs that use the
    lazy memory allocation strategy are very easy to convert to a heap
    based strategy if the need ever arises.

    Programs that leak memory but contain a lots of calls to free()
    are much harder to modify like this, since you would have to
    repeat the functionality of free().

    Of course, a lazy strategy is much easier to upgrade to a GC
    based one. In that case absolutely no code needs to be
    modified. malloc is replaced with GC_malloc or similar,
    and there is nothing else to do.

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 13, 2007
    #1
    1. Advertising

  2. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > Suppose that you have a module that always allocates
    > memory without ever releasing it because the guy that
    > wrote it was lazy, as lazy as me.
    >
    > Now, you want to reuse it in a loop. What do you do?
    >
    > Contrary to some people that will start crying to that
    > &@@""#~ programmer that wrote this sh!!!! you keep
    > your cool and you do the following:
    >
    > 1) Since the program always call malloc and never free()
    > you allocate a big chunk of memory and each time that the
    > program calls malloc, you replace those calls with another
    > that allocates from that memory heap.
    >

    How does that help if the new application calls leaky parts of the old
    one enough times to exhaust the heap?

    --
    Ian Collins.
     
    Ian Collins, Oct 13, 2007
    #2
    1. Advertising

  3. Ian Collins said:

    > jacob navia wrote:
    >> Suppose that you have a module that always allocates
    >> memory without ever releasing it because the guy that
    >> wrote it was lazy, as lazy as me.
    >>
    >> Now, you want to reuse it in a loop. What do you do?
    >>
    >> Contrary to some people that will start crying to that
    >> &@@""#~ programmer that wrote this sh!!!! you keep
    >> your cool and you do the following:
    >>
    >> 1) Since the program always call malloc and never free()
    >> you allocate a big chunk of memory and each time that the
    >> program calls malloc, you replace those calls with another
    >> that allocates from that memory heap.
    >>

    > How does that help if the new application calls leaky parts of the old
    > one enough times to exhaust the heap?


    It doesn't, obviously. The correct fix is to plough through the code,
    working out the right places to free up the memory - which would have been
    a lot easier (and therefore cheaper) if it had been done at the time the
    original code was written. Writing your own memory manager is not a fix -
    it's an error-prone bodge that doesn't address the real issue, as you
    rightly point out.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 13, 2007
    #3
  4. "Ian Collins" <> wrote in message
    >> 1) Since the program always call malloc and never free()
    >> you allocate a big chunk of memory and each time that the
    >> program calls malloc, you replace those calls with another
    >> that allocates from that memory heap.
    >>

    > How does that help if the new application calls leaky parts of the old
    > one enough times to exhaust the heap?
    >

    int lifeandmeaningofuniverse(long problem)
    {
    malloc(1000);
    return 42;
    }

    We need to call for lots of long problems, to get the list of results. But
    that means we will eventually run out of memory.

    So

    for(i=0;i<LONG_MAX, i++)
    {
    makeheap(1024); /* enough memory for program to allocatate;
    x = lifeandmeaningofuniverse(i);
    printf("%ld %d\n", i, x);
    killheap();
    }

    Now we need to hack into lifeandmeaningof theuinverse() to replace every
    malloc() with a mymalloc().

    It's a bit of a hack, but presented with something like this function that
    is so badly written and documented that you can't follow the allocation
    logic, it might be a viable solution. The real answer is to put in the
    matching frees(), but that means really knowing what the function does.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
     
    Malcolm McLean, Oct 13, 2007
    #4
  5. jacob navia

    Willem Guest

    jacob wrote:
    ) 1) Since the program always call malloc and never free()
    ) you allocate a big chunk of memory and each time that the
    ) program calls malloc, you replace those calls with another
    ) that allocates from that memory heap.
    ) <snip>
    ) Programs that leak memory but contain a lots of calls to free()
    ) are much harder to modify like this, since you would have to
    ) repeat the functionality of free().

    No, you just make free() a no-op. That will make it leak a lot more
    memory, but you've already fixed that, right ?


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Oct 13, 2007
    #5
  6. jacob navia

    Ben Pfaff Guest

    Richard Heathfield <> writes:

    > Writing your own memory manager is not a fix - it's an
    > error-prone bodge that doesn't address the real issue, as you
    > rightly point out.


    I'm rather a fan of pool-based memory allocation, as done in
    e.g. Apache: add memory blocks (and other resources) to a list,
    for convenient freeing in a group.

    Would you contend that this is also an "error-prone bodge"? If
    not, at what point does pool-based allocation descend to that
    level?
    --
    A competent C programmer knows how to write C programs correctly,
    a C expert knows enough to argue with Dan Pop, and a C expert
    expert knows not to bother.
     
    Ben Pfaff, Oct 13, 2007
    #6
  7. Ben Pfaff said:

    > Richard Heathfield <> writes:
    >
    >> Writing your own memory manager is not a fix - it's an
    >> error-prone bodge that doesn't address the real issue, as you
    >> rightly point out.

    >
    > I'm rather a fan of pool-based memory allocation, as done in
    > e.g. Apache: add memory blocks (and other resources) to a list,
    > for convenient freeing in a group.
    >
    > Would you contend that this is also an "error-prone bodge"? If
    > not, at what point does pool-based allocation descend to that
    > level?


    At the point where you try to retrofit it into a program (such as I
    described upthread) that was written without pool-based allocation in
    mind, in the hope of magically fixing the failure to deal with memory
    housekeeping properly. If pool-based allocation is part of a sensible,
    coherent design strategy that is part of the original program design,
    that's obviously a very different matter.

    The point is that you have to think about this stuff up front. To malloc
    all over the place and never bother to free is sloppy programming, and
    overlaying a customised memory manager on top of that mess is what I
    referred to as "an error-prone bodge".

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 13, 2007
    #7
  8. jacob navia

    jacob navia Guest

    Richard Heathfield wrote:
    > Ben Pfaff said:
    >

    [snip]
    >> ... at what point does pool-based allocation descend to that
    >> level?

    >
    > At the point where you try to retrofit it into a program (such as I
    > described upthread) that was written without pool-based allocation in
    > mind, in the hope of magically fixing the failure to deal with memory
    > housekeeping properly. If pool-based allocation is part of a sensible,
    > coherent design strategy that is part of the original program design,
    > that's obviously a very different matter.
    >

    This is wrong.

    In a pool managed memory allocation strategy you make a lot of
    allocations that go into the same pool, then release the pool.

    This is exactly the same as a program that is "retrofitted" to
    do this because it never frees any memory. The only part that is
    changed is that at the end of the program, instead of leaving the
    freeing of the pool to the operating system, it is done
    explicitely.

    Note that lazy allocation is always actually a pool based allocation
    since the operating system maintains a pool for each process.

    > The point is that you have to think about this stuff up front.


    This is wrong.

    There is absolutely no need to over engineer a program, making it manage
    memory up front. You allocate memory without freeing it. If this ever
    becomes a problem you add a pool based strategy or a garbage collector.

    The lazy allocation strategy is adapted to transient programs, where the
    memory pool is released by the operating system.

    Utilities that produce directory listings, linkers, compilers, filters,
    text searching tools, there are many examples of transient programs.
    In many of them, ignoring memory allocation problems makes them faster,
    leaner, and less error prone, since all the bugs associated with
    "free()" calls can be avoided.




    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 13, 2007
    #8
  9. jacob navia

    Guest

    jacob navia wrote:
    > Richard Heathfield wrote:
    > > The point is that you have to think about this stuff up front.

    >
    > This is wrong.
    >
    > There is absolutely no need to over engineer a program, making it manage
    > memory up front. You allocate memory without freeing it. If this ever
    > becomes a problem you add a pool based strategy or a garbage collector.


    Navia really would make a fascinating subject for a psychologist. He
    makes himself look like a complete fool by taking some utterly
    ludicrous position, then when he gets called on it he just digs
    himself further and further into the hole.

    The killer is that he comes out with this incompetence and dribbling
    nonsense and then has the chutzpah to write a tutorial trying to teach
    other people how to write C!
     
    , Oct 13, 2007
    #9
  10. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > Richard Heathfield wrote:
    >
    >> The point is that you have to think about this stuff up front.

    >
    > This is wrong.
    >
    > There is absolutely no need to over engineer a program, making it manage
    > memory up front. You allocate memory without freeing it. If this ever
    > becomes a problem you add a pool based strategy or a garbage collector.
    >

    I can see you have never worked on embedded systems.

    > Utilities that produce directory listings, linkers, compilers, filters,
    > text searching tools, there are many examples of transient programs.
    > In many of them, ignoring memory allocation problems makes them faster,
    > leaner, and less error prone, since all the bugs associated with
    > "free()" calls can be avoided.
    >

    You fail to realise that your leaky directory listing routine may get
    invoked recursively in something like a backup utility, or get called
    hundreds or even thousands of times in a test suite. Just clean up your
    mess, it isn't that hard.

    --
    Ian Collins.
     
    Ian Collins, Oct 13, 2007
    #10
  11. jacob navia

    jacob navia Guest

    Ian Collins wrote:
    > jacob navia wrote:
    >> Richard Heathfield wrote:
    >>
    >>> The point is that you have to think about this stuff up front.

    >> This is wrong.
    >>
    >> There is absolutely no need to over engineer a program, making it manage
    >> memory up front. You allocate memory without freeing it. If this ever
    >> becomes a problem you add a pool based strategy or a garbage collector.
    >>

    > I can see you have never worked on embedded systems.
    >


    I am speaking of transient programs, i.e. programs that do
    something, then exit. Embedded systems do have transient programs
    if they have an OS. Otherwise they don't.

    >> Utilities that produce directory listings, linkers, compilers, filters,
    >> text searching tools, there are many examples of transient programs.
    >> In many of them, ignoring memory allocation problems makes them faster,
    >> leaner, and less error prone, since all the bugs associated with
    >> "free()" calls can be avoided.
    >>

    > You fail to realise that your leaky directory listing routine may get
    > invoked recursively in something like a backup utility, or get called
    > hundreds or even thousands of times in a test suite.
    >


    A transient program, as I have explained several times already, leaves
    its cleanup to the operating system. Thus, it can be called thousands
    of times, it will always cleanup implicitly.

    I can repeat this again and again and apparently there will be always
    the same "argument"...

    Even in a recursive call if you call my program with some way like
    system("dodir"); or whatever, it will always cleanup! And this will not
    change even if it is called hundred billion times!


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 13, 2007
    #11
  12. jacob navia said:

    > Richard Heathfield wrote:
    >> Ben Pfaff said:
    >>

    > [snip]
    >>> ... at what point does pool-based allocation descend to that
    >>> level?

    >>
    >> At the point where you try to retrofit it into a program (such as I
    >> described upthread) that was written without pool-based allocation in
    >> mind, in the hope of magically fixing the failure to deal with memory
    >> housekeeping properly. If pool-based allocation is part of a sensible,
    >> coherent design strategy that is part of the original program design,
    >> that's obviously a very different matter.
    >>

    > This is wrong.


    No, it isn't. You need to learn to tell right from wrong. For the past few
    years, you appear to have got them mixed up with monotonous regularity.

    >
    > In a pool managed memory allocation strategy you make a lot of
    > allocations that go into the same pool, then release the pool.


    Fine, provided there's enough memory, which - in the example I gave - there
    wasn't.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 13, 2007
    #12
  13. jacob navia said:

    <snip>

    > A transient program, as I have explained several times already, leaves
    > its cleanup to the operating system. Thus, it can be called thousands
    > of times, it will always cleanup implicitly.


    I have already given an example, upthread, of what you call a "transient"
    program which became a "non-transient" program five years later. Skimp on
    the housekeeping now, and pay for it many times over in the future.

    > I can repeat this again and again and apparently there will be always
    > the same "argument"...


    No matter how many times you repeat an incorrect argument, it remains
    incorrect.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 13, 2007
    #13
  14. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > Ian Collins wrote:
    >> jacob navia wrote:
    >>> Richard Heathfield wrote:
    >>>
    >>>> The point is that you have to think about this stuff up front.
    >>> This is wrong.
    >>>
    >>> There is absolutely no need to over engineer a program, making it manage
    >>> memory up front. You allocate memory without freeing it. If this ever
    >>> becomes a problem you add a pool based strategy or a garbage collector.
    >>>

    >> I can see you have never worked on embedded systems.
    >>

    >
    > I am speaking of transient programs, i.e. programs that do
    > something, then exit. Embedded systems do have transient programs
    > if they have an OS. Otherwise they don't.
    >

    "Transient programs" contain components. Those components, if they are
    any use, will get reused. Unless you stick a great big fluorescent
    label on them "Danger, the authour was too slack to free memory" the
    component may be reused in something other than a "transient programs".

    >> You fail to realise that your leaky directory listing routine may get
    >> invoked recursively in something like a backup utility, or get called
    >> hundreds or even thousands of times in a test suite.

    >
    > A transient program, as I have explained several times already, leaves
    > its cleanup to the operating system. Thus, it can be called thousands
    > of times, it will always cleanup implicitly.
    >

    I wasn't talking about the program, I was talking about the leaky
    routine that reads a directory. Or do you write all of you code in main?

    --
    Ian Collins.
     
    Ian Collins, Oct 13, 2007
    #14
  15. jacob navia

    jacob navia Guest

    Ian Collins wrote:
    > I wasn't talking about the program, I was talking about the leaky
    > routine that reads a directory. Or do you write all of you code in main?
    >


    This is the problem. I am always talking about transient
    *program* and you are talking about some routine!

    I repeat:

    Lazy allocation can be done only at the program level. I have
    always maintained this.

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 13, 2007
    #15
  16. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > Ian Collins wrote:
    >> I wasn't talking about the program, I was talking about the leaky
    >> routine that reads a directory. Or do you write all of you code in main?
    >>

    >
    > This is the problem. I am always talking about transient
    > *program* and you are talking about some routine!
    >
    > I repeat:
    >
    > Lazy allocation can be done only at the program level. I have
    > always maintained this.
    >

    But what is is program if it isn't a collection of routines?

    --
    Ian Collins.
     
    Ian Collins, Oct 13, 2007
    #16
  17. jacob navia

    jacob navia Guest

    Ian Collins wrote:
    > jacob navia wrote:
    >> I repeat:
    >>
    >> Lazy allocation can be done only at the program level. I have
    >> always maintained this.
    >>

    > But what is is program if it isn't a collection of routines?
    >


    Maybe you haven't noticed it yet, but after a program finishes the
    operating system cleans up. Not so for a routine.

    And you know what?

    "There is no blinder person as the one that doesn't want to see".


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 13, 2007
    #17
  18. jacob navia

    Ian Collins Guest

    jacob navia wrote:
    > Ian Collins wrote:
    >> jacob navia wrote:
    >>> I repeat:
    >>>
    >>> Lazy allocation can be done only at the program level. I have
    >>> always maintained this.
    >>>

    >> But what is is program if it isn't a collection of routines?
    >>

    >
    > Maybe you haven't noticed it yet, but after a program finishes the
    > operating system cleans up. Not so for a routine.
    >

    So? Enough of this, I'm off to find an open pub and celebrate England's
    victory over France in the wold cup....

    --
    Ian Collins.
     
    Ian Collins, Oct 13, 2007
    #18
  19. jacob navia

    Guest

    jacob navia wrote:
    > And you know what?
    >
    > "There is no blinder person as the one that doesn't want to see".


    Said without the slightest trace of irony...
     
    , Oct 13, 2007
    #19
  20. jacob navia

    Willem Guest

    jacob wrote:
    ) This is the problem. I am always talking about transient
    ) *program* and you are talking about some routine!
    )
    ) I repeat:
    )
    ) Lazy allocation can be done only at the program level. I have
    ) always maintained this.

    Maybe I should butt in and also repeat:

    Programs often get reused and turned (partly) into routines.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Oct 13, 2007
    #20
    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. Floris van Haaster

    Project management / bug management

    Floris van Haaster, Sep 23, 2005, in forum: ASP .Net
    Replies:
    3
    Views:
    1,244
    Jon Paal
    Sep 23, 2005
  2. John
    Replies:
    0
    Views:
    1,032
  3. John
    Replies:
    0
    Views:
    1,046
  4. My Python
    Replies:
    7
    Views:
    521
    Miles Bader
    Jun 3, 2011
  5. Matt Oefinger
    Replies:
    0
    Views:
    217
    Matt Oefinger
    Jun 25, 2003
Loading...

Share This Page