2

I know this question has been asked before, however it was asked two years ago and I have some other constraints to add.

(Previous question here) : Is using malloc() and free() a really bad idea on Arduino?

I understand that dynamically allocating and freeing memory can cause fragmentation, and without an operating system to manage the memory, this fragmentation can reach a point where no memory can be allocated because the current memory is a mess.

That being said, the only memory allocation I plan to do is for a linked list that I am using as a stack. This means that I will only even be adding or removing from one end of the linked list. In the case that the arduino malloc() implementation is 'next fit', is it safe to assume that I can use this linked list safely, since the only element I'll be removing is the next one that fit, and everything else will stay where it is?

tl;dr the two questions I'm asking:

Is the arduino malloc implementation 'next fit'? Where can I read up on this in detail?

AND

A single stack running in a 'next fit' environment will never cause fragmentation, correct?

closed as unclear what you're asking by Chris Stratton, MatsK, gre_gor, jose can u c, KIIV Jan 23 '18 at 14:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    In such a simple case there's no need for a malloc() style memory allocator, and no reason to suffer the overhead. Just eternally reserve the entire memory you want and track usage with the pointer of your custom stack. There's also no reason to make your list linked. – Chris Stratton Jan 13 '18 at 16:47
  • The stack will need to be of modular size. I could allocate a maximum size and expire stack entries, but that would require shifting the entire stack every time an entry is expired, I'm not sure but I would assume that's a fairly large overhead. – Brydon Gibson Jan 13 '18 at 16:49
  • You only have so much memory available on the chip. You can grab all that you'd be willing to let a malloc() try to use, and track varying partial usage of it yourself with a single number. No "shifting" of anything involved. Or else there's something you're not telling us. Take a minute and think about how an actual stack works - does that match what you are doing? If not, don't call it a stack. – Chris Stratton Jan 13 '18 at 16:50
  • 2
    Linked list and stack are two different data structures and it doesn't really make sense to use a linked list to implement a stack, a LIFO queue that is accessed from one end only. I'm not saying that you couldn't do it I'm just saying that from a performance and code stand point it doesn't make much sense. – Richard Chambers Jan 13 '18 at 17:37
  • I'm voting to close this question as unclear, since the asker has failed to specify what they are really trying to acomplish by using a linked list of dynamically allocated elements to emulate a stack. This smells strongly like an XY problem. – Chris Stratton Jan 14 '18 at 23:41
4

On my answer to the question you are referencing, I state that “If you use the heap like a stack (last in is first out), then it will behave like a stack and not fragment.” This seems to be exactly your usage pattern, thus you should not fear fragmentation. Of course, the caveat written in Michel Keijzers’ answer applies: you should make sure that no other part of your code, including libraries, is using malloc() and free().

Just to give some evidence, the avr-lic documentation provides some implementation details about malloc:

When allocating memory [...] If nothing could be found on the freelist, heap extension is attempted. [...] When deallocating the topmost chunk of memory, the size of the heap is reduced.

All this can be seen in action in the source code of malloc() and free(), which is abundantly commented and quite readable.


Edit 1: From the same section of the avr-libc documentation, we learn about how realloc() grows a memory chunk:

If [...] the old chunk is at the top of heap, and the above freelist walk did not reveal a large enough chunk on the freelist to satisfy the new request, an attempt is made to quickly extend this topmost chunk (and thus the heap), so no need arises to copy over the existing data.

Based on this, I would suggest you use an array, rather than a linked list, and use realloc() to adjust the size of the array. A linked list of n objects of size m has a memory cost n × (m+4): each objects has an overhead of 2 bytes for the linking pointer, plus 2 bytes for malloc()'s internal bookkeeping. The cost of an array would be only (n × m)+2.

In this case, however, it is essential that no other part of your code uses malloc(), otherwise realloc() could end up allocating a whole new array, which would be very costly.


Edit 2: I wrote a small test program that randomly grows and shrinks a memory buffer. Running the test on an Uno shows that the allocated memory chunk never changes address even though its size varies wildly.

void setup()
{
    Serial.begin(9600);
}

void loop()
{
    static void *p;
    static size_t sz;
    sz = random(max(sz, 22) - 20, min(sz + 20, 1536) + 1);
    p = realloc(p, sz);
    Serial.print((uintptr_t) p);
    Serial.print("  ");
    Serial.println(sz);
}
  • You really, really, really don't want to use realloc() for something of substantial size. In the case where it's safely exclusive, it's unnecessary, and in the case where it's unsafe it fails horribly since the chip likely can't fit a new copy of the whole thing. This really does not seem to be a situation where dynamic allocation is called for, but if it's going to be used and the allocation grown then a linked list should be used so that it doesn't have to be contiguous. Otherwise it should be a statically allocated array deterministically reserving the maximum needed size. – Chris Stratton Jan 14 '18 at 23:43
1

Probably it will not be a problem, since when you free memory, those memory sizes will be equal than the memory size you malloc. E.g. suppose one element of a linked list is 24 bytes, if this is freed, the next time when 24 bytes are requested by malloc, it will use that space.

So my assumption it works when you never use free or malloc, EXCEPT when using it for one single linked list with elements that are always equal size.

However, you have to make sure:

  • You do not free memory elsewhere (with different size)
  • You do not malloc memory elsewhere (with different size)
  • All libraries you use do not call a malloc/free under water.

Also, you can do an easy check by malloc/free and fill one item a lot of times one element (thus adding and removing it), and checking the memory usage is similar (or it does not crash to have a very simple test).

Btw, afaik Arduino pointers use 2 bytes, so this can cause quite some memory. If you use max. 256 elements, consider using indices, but in this case you have to write your own 'linked list' library (e.g. when removing, you have to move all subsequent indices).

  • 1
    That's a good point about the libraries, and I'll keep that in mind as I develop. – Brydon Gibson Jan 13 '18 at 16:40
  • I haven't checked Arduino libraries, but I assume these do not use malloc/free, but in your case it might be important. – Michel Keijzers Jan 13 '18 at 16:41
  • 3
    The standard Arduino String class uses realloc(). – Edgar Bonet Jan 13 '18 at 16:53
0

There are many implementations of malloc() and AFAIK, none is specified in the standard. So, while you could get lucky and and find that your preferred environment uses a malloc() algorithm compatible with your intended use, your code will not be known portable to another, unspecified, environment, and even a compiler or library revision to your preferred environment could break you code.

You'd be better off to write an allocator that works as you need it to work. Whether you need a linked-list or an array of fixed size blocks to accomplish your stack structure, using a getStackFrame(), freeStackFrame() pair of functions, written and controlled by you, will avoid some potential nasty surprises.

Not the answer you're looking for? Browse other questions tagged or ask your own question.