Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #28708

Re: Dynamic allocation and newlib-nano

Show all headers | View raw

Il 27/06/2019 16:47, Niklas Holsti ha scritto:
> On 19-06-27 16:59 , pozz wrote:
>> Il 27/06/2019 13:42, upsidedown@downunder.com ha scritto:
>>> On Thu, 27 Jun 2019 13:08:20 +0200, pozz <pozzugno@gmail.com> wrote:
> 
>   [snip]
> 
>>>> However the dynamic allocation algorithm appears very strange to me. I
>>>> expected that malloc() returns always the start of the heap if the heap
>>>> is completely free. It is so at the beginning, however when some
>>>> allocations and deallocations happen, even if the heap is completely
>>>> deallocated (all the allocations were freed), a new allocation doesn't
>>>> return the start of the heap.
>>>> How to explain this behaviour?
>>>
>>> malloc() needs to store the actual allocated size (user requested
>>> size+possible align to word/longword boundary), [...snip...]  thus 
>>> the user
>>> receiver never starts at the start of heap, but after this descriptor.
>>
>> Yes, I know.  When I wrote that malloc() returns a different address
>> than the start of the heap, I meant it is *very* different.
>>
>> In other words, if the heap is at 0x1000, after many
>> allocations/deallocations, when the heap is again completely free,
>> malloc() returns 0x1100, 256 bytes from the start of the heap.
> 
> If it is always 256 bytes, whatever the pattern of allocations and 
> releases, then I would guess that your heap manager allocates a 256-byte 
> block for its own use, on first call, and keeps that block allocated 
> thereafter.

No, it isn't my case.


> If the offset varies depending on the size and order of allocations and 
> releases, your are probably seeing an effect of the allocation algorithm 
> which tries to find the "best" (or a "good enough") free block to 
> allocate. Even if all heap blocks have been released, this "good" block 
> may not be at the start of the heap, probably because the allocation 
> algorithm does not coalesce all adjacent free blocks.

Oh bad!


> It is quite complex (and can be processor-heavy) to structure and manage 
> the heap area in such a way that releasing all allocated blocks returns 
> the heap to its original state as a single, large, empty area. 

Complex? Really?


> Instead, 
> the heap area tends to be left as a collection of "free" blocks, of 
> various sizes, and the next malloc() call picks one of these blocks to 
> use for the new allocation. 

However is strange to me. If I have some allocated and freed blocks 
scattered on the heap space, I could understand.  But when there aren't 
allocated blocks, but only free blocks, I think it's very simple to 
fallback to an initial state without *any* free blocks.


> But the details depend on the particular 
> allocation algorithm, and there are _many_ different algorithms.

I'm using newlib and I think the allocator is this[1].


> The only heap-allocation algorithm I know that always returns the heap 
> to its initial state is the "buddy algorithm" 
> (https://en.wikipedia.org/wiki/Buddy_memory_allocation) but there may be 
> other, newer ones.

I tried to use mbedTLS buffer memory allocator[2] and it seems it works 
better than newlib allocator.

I had a problem during a TLS connection that was caused by an out of 
memory. After some allocations/deallocations, the heap was completely 
free. mbedTLS requests two allocations: 300 and 1300 bytes. I had around 
2000 bytes of heap space, but the malloc failed. The 300-bytes block was 
allocated at an offset of 500 bytes from the beginning of the heap. Of 
course, 1300 bytes couldn't be allocated.

Increasing heap space solved the problem.  But using mbedTLS allocator, 
solved the issue too.


[1] 
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=newlib/libc/stdlib/nano-mallocr.c;h=13b72c99ffd7007b53c2e3270a56da237857742a;hb=HEAD

[2] 
https://github.com/ARMmbed/mbedtls/blob/development/library/memory_buffer_alloc.c

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Dynamic allocation and newlib-nano pozz <pozzugno@gmail.com> - 2019-06-27 13:08 +0200
  Re: Dynamic allocation and newlib-nano upsidedown@downunder.com - 2019-06-27 14:42 +0300
    Re: Dynamic allocation and newlib-nano pozz <pozzugno@gmail.com> - 2019-06-27 15:59 +0200
      Re: Dynamic allocation and newlib-nano Niklas Holsti <niklas.holsti@tidorum.invalid> - 2019-06-27 17:47 +0300
        Re: Dynamic allocation and newlib-nano pozz <pozzugno@gmail.com> - 2019-06-27 18:37 +0200
          Re: Dynamic allocation and newlib-nano Niklas Holsti <niklas.holsti@tidorum.invalid> - 2019-06-27 21:23 +0300
            Re: Dynamic allocation and newlib-nano pozz <pozzugno@gmail.com> - 2019-06-28 11:38 +0200
        Re: Dynamic allocation and newlib-nano George Neuner <gneuner2@comcast.net> - 2019-06-27 17:02 -0400
  Re: Dynamic allocation and newlib-nano Joe Chisolm <jchisolm6@earthlink.net> - 2019-06-27 12:09 -0500
  Re: Dynamic allocation and newlib-nano Paul Rubin <no.email@nospam.invalid> - 2019-06-27 14:23 -0700
    Re: Dynamic allocation and newlib-nano pozz <pozzugno@gmail.com> - 2019-06-28 08:42 +0200

csiph-web