[PATCH] malloc on top to consider already available memory

[Petter Österlund]

Hi,

The version that Doug Lea changed the behavior I refer to is in
version 2.7.0 located here:

   ftp://g.oswego.edu/pub/misc/
   ftp://g.oswego.edu/pub/misc/malloc-2.7.0.c

Between the 2.6.x series and 2.7.x there are quite some changes
besides this one though. The function malloc_extend_top in 2.6.x has
been refactored into sYSMALLOc. In this function one can see the
beginning of the fix to include what is already on top (line 2890):

----
  /*
    If contiguous, we can subtract out existing space that we hope to
    combine with new space. We add it back later only if
    we don't actually get contiguous space.
  */

  if (contiguous(av))
    size -= old_size;
----

And later (more than one place) the case is handled when the new
sbrk() memory was not contiguous and a second sbrk() is made to adjust
for this fact (line 3016 et al):

----
        /*
          If this isn't adjacent to existing space, then we will not
          be able to merge with old_top space, so must add to 2nd request.
        */

        correction += old_size;
----

A difference with my patch compared to above is that the fix is
handled outside the sYSMALLOc / malloc_extend_top function and a test
after checks if it succeeded or failed and if so falls back on old
behavior.

An alternative to my patch would be to consider the 2.7.0 or even
other more recent versions - but that would be include quite much more
changes.


br Petter



Den 2016-02-15 kl. 14:44, skrev Corinna Vinschen:
> Hi Petter, hi guys,
> 
> On Feb 12 16:23, Petter Österlund wrote:
>> 
>> Hi,
>> 
>> This is my fist post. I suggest a patch for malloc considering
>> already available memory available on the top instead of always
>> extending top with the allocation request size when there is not
>> enough space, which may cause near double memory requirements in
>> some cases. For an MCU with small memory it may be quite crucial
>> and for anyone it is a bit unexpected behavior.
>> 
>> An example of the problem; Do malloc(30000); free();
>> malloc(40000); free();  then without this patch then peak memory
>> will become 70KB but with the patch it will be only 40KB as
>> second extend will only be for 10KB extra  not 40K.
>> 
>> Newer versions of Doug Lea malloc, starting with version 2.7.0, 
>> already contains similar fix since several years ago and it would
>> be nice if this fix could be included in Newlib also.
> 
> Can you point to this patch?
> 
>> The patch below first try and extend top with the diff of what
>> should be needed, if that fails to extend top large enough for
>> some reason the behavior falls back on old behavior (a failure
>> may happen if there are intervening sbrk() or if out of memory).
>> 
>> br Petter
>> 
>> $ diff -up newlib-2.3.0.20160104/newlib/libc/stdlib/mallocr.c 
>> newlib-patch/newlib/libc/stdlib/mallocr.c ---
>> newlib-2.3.0.20160104/newlib/libc/stdlib/mallocr.c  2016-02-12 
>> 15:32:05.380345800 +0100 +++
>> newlib-patch/newlib/libc/stdlib/mallocr.c   2016-02-12 
>> 15:36:17.184029400 +0100 @@ -2572,7 +2572,20 @@ Void_t*
>> mALLOc(RARG bytes) RDECL size_t #endif
>> 
>> /* Try to extend */ -    malloc_extend_top(RCALL nb); +    if
>> (bytes > chunksize(top)) { +      /* extend including whats
>> available on top */ +      INTERNAL_SIZE_T nb_diff  =
>> request2size(long_sub_size_t(bytes, chunksize(top))); +
>> malloc_extend_top(RCALL nb_diff); +      remainder_size =
>> long_sub_size_t(chunksize(top), nb); +      if (chunksize(top) <
>> nb || remainder_size < (long)MINSIZE) +      { +        /* top
>> not large enough; failure or intervening sbrk() */ +
>> malloc_trim(RCALL 0); +        malloc_extend_top(RCALL nb); +
>> } +    } +    else +      malloc_extend_top(RCALL nb); 
>> remainder_size = long_sub_size_t(chunksize(top), nb); if
>> (chunksize(top) < nb || remainder_size < (long)MINSIZE) {
> 
> Can anybody here using the newlib malloc give this a whirl?
> Cygwin is using its own malloc, so I can't test this easily.
> 
> 
> Thanks, Corinna
>