AVR, realloc() and heap fragmentation

[HwAoRrDk]

Can anyone tell me whether the following usage of AVR-libc's realloc() will result in any heap fragmentation?

Code: [Select]

void *ptr = NULL;
size_t size = 0;

// For brevity of example, no error handling here.
size = 1;
ptr = realloc(ptr, sizeof(uint16_t) * size);
size = 2;
ptr = realloc(ptr, sizeof(uint16_t) * size);
size = 7;
ptr = realloc(ptr, sizeof(uint16_t) * size);

That is, if multiple calls to realloc() are made, each in turn increasing the size of allocation (and never decreasing), is there any chance the allocator will fragment the heap? I would guess not, but I don't have any experience with how avr-libc's allocator works. I'm hoping someone with more experience can tell me what will happen. I don't want to inadvertently crash into the stack because I've caused the allocator to do something inappropriately excessive.

I'm thinking of using this approach to store a potentially sparse array of pointers to callback functions, where the index in the array is equal to an 'op-code'. (For example: index 0x0 = op-code 'foo' and contains pointer to a function implementing 'foo'; index 0xA = op-code 'bar' containing pointer to function implementing 'bar'; 0x1-0x9 remain NULL and not implemented.) The idea is that rather than waste memory with a fixed size 256-element array that may be mostly empty, I can dynamically allocate just the necessary amount of memory to store only the registered callback functions. If the op-codes/indices happen to be non-contiguous, then some memory will be wasted, but not as much as with a fixed-size array.

[Mechatrommer]

i dont know the answer to your question, but maybe you can setup a code to display on monitor or pin IO (serial comm output) what ptr value is each time you realloc. but my suspicion is for that simple code, it will not fragment your memory and ptr will always point to the same location, if there is enough room for reallocation.

[maginnovision]

In that example it shouldn't fragment since nothing new is declared and the free heap pointer only changes for realloc(). Why would you want a dynamic list of pointers where some are null? Are your adding new functions while it runs? If not I don't understand how you're saving anything. It's also safer to allocate these on the stack so that you know how much memory and flash space you have.

[dave j]

If you know the range the opcodes cover in advance, wouldn't it be easier to use a single allocation of memory for the pointers to cover that range and access them using:

opcode_pointers[opcode-FIRST_OPCODE]

[HwAoRrDk]

Thanks, glad to know it won't do something unexpected with the heap allocations.

Now, the primary reason why I'm not keen on statically allocating a fixed-size array is because it would take up a significant chunk of memory. If I want to cater for a maximum of 256 callback functions, it will require 512 bytes of memory. My microcontroller only has 2KB of RAM, so that would be 25% of all memory! And, in fact, I will not only be storing a 16 bit pointer, but also an 8-bit integer with each that notes how many argument values are to be passed to the function, which would make it 768 bytes! I don't think I can afford to reserve that much memory.

I understand that I could just simply size my fixed array to only what is required, but this is where my secondary reason comes in: that I'm trying to make this a more generic solution as part of a module that will be utilised again elsewhere in future, where there may be a wholly different set of callback functions. I just want to make it so that the only thing I have to worry about is making a call to something like a register_callback() function, and that's it. No messing about re-defining constants, etc.

I'm not too worried about safety, as the allocations will be a one-time operation on start-up, and will never be free()-ed.


Here's another question: can I make any assumptions about the default value of any memory allocated with realloc()? Given that calloc() exists, I would assume that realloc() does not do any initialisation of allocated memory, and so as a worst case scenario, might the allocated memory contain random garbage?

That would kind of complicate the scenario where I am allocating memory for a sparsely-populated array, because then any unpopulated op-code pointers in my array would not be null, and thus indistinguishable from a populated one. I would have to write some code to specifically zero-out any 'gaps' in the allocation.

[maginnovision]

That's right, realloc() won't touch the newly allocated memory. You would need to realloc() and memset() the newly acquired bits to null them. Not really a problem and even the overhead is small since it's one time. Since you won't be using any other dynamic memory the memory won't move and none of the previously set memory will be changed.

A problem is if you have this small amount of memory users will likely push it over. You might be better keeping the lookup in flash or eeprom(obviously this is slow).

[ledtester]

Concerning the behavior of calloc(), realloc() and malloc()...

Found this source for AVR libc:

https://github.com/vancegroup-mirrors/avr-libc

Looks current. The source for calloc.c shows that it calls memset to zero the reserved memory:

https://github.com/vancegroup-mirrors/avr-libc/blob/06cc6ff5e6120b36f1b246871728addee58d3f87/avr-libc/libc/stdlib/calloc.c#L45

As for relloc(), it can return a value from malloc() which doesn't do any initialization:

https://github.com/vancegroup-mirrors/avr-libc/blob/06cc6ff5e6120b36f1b246871728addee58d3f87/avr-libc/libc/stdlib/realloc.c#L148

[ledtester]

I can dynamically allocate just the necessary amount of memory to store only the registered callback functions.

I'm curious... why won't you know what the size of your call-back table is at compile time?

[amyk]

I think you're approaching this problem from the completely wrong direction. Dynamic allocation has significant overhead and I don't think it's suitable for a system with only 2KB of RAM. A lot of embedded coding guidelines prohibit it entirely.

[brucehoult]

omg.

Don't do that on *any* computer.

*Especially* don't do that on a computer with 2 KB of RAM.

That's just awful programming. It depends on all kinds of precise details of the memory allocator, which you can't know without reading the source code, but it's very likely to use N^2 memory and leave the old copies essentially unusable. If you're really lucky and that's the last thing allocated and you don't allocate anything else in between then your object *might* get expanded in place.

Here's a *much* better technique:

You say 256 is the maximum number of callback functions. OK, use a 2-level index to them. Make a global array of 16 pointers to 2nd level arrays. Each 2nd level array is also 16 pointers, and is malloc()'d as needed (or make the first one a global if you'll always have at least one callback function).

Access the pointers to the actual callback functions as callbackFns[n/16][n%16] (or callbackFns[n>>4][n&15] .. it will make the same machine code)

You'll be using a total of 32 bytes to store the first callback function, and that will stay the same up to 8 callback functions. If you get to 256 callback functions then you'll have a total of 17 arrays of 32 bytes each, for a total of 544 bytes instead of 512.

But actually this is probably completely unnecessary and counter-productive. If you're not using all 256 callbacks, what are you planning to use the saved memory for? And what are you going to do if you want to use memory for that other thing but you need 256 callbacks *also*? Fail.

On something as tiny as an AVR you're usually much better off deciding how much memory you need for each thing, worst case, and just allocate that as a global/static array.

[Kilrah]

Agreed that on such a small MCU, and if as it seems to be the case the set of callbacks will always be the same in a given application it makes no sense to waste any RAM at all nor get into the risks of dynamic allocation, just define all that stuff at compile time.

[T3sl4co1l]

The example is trivial: what's the point of using heap at all if you're only allocating one array ever?  Statically allocate the max and be done with it.

In other words, what else are you allocating, that will potentially interfere with the object in question and cause fragmentation?

Tim

[jhpadjustable]

I don't think that belongs in RAM. Consider implementing something like an .init section: A module declares an init function by creating a pointer-to-function variable and using a compiler pragma to specify that the variable should go into the .init section. The linker script defines a symbol for the beginning of the section. The crt0 startup calls each function pointer in the array located at that symbol until encountering a NULL (provided by the linker script). Instead, I imagine you would place structs in that section (with due care for word alignment, which the compiler may force).

[Psi]

Yep, this happens a lot when application programmers try MCU programming
They've had "global variables are evil" drilled into their brains from day 1 and that dynamic allocation is sexy and efficient.
Moving from 64bit application programming to a 8 bit mcu can be a bit of a shock.

[Kilrah]

The example is trivial: what's the point of using heap at all if you're only allocating one array ever?  Statically allocate the max and be done with it.

He said several times that statically allocating the max he wants would use up way too much of the available RAM.

[mikerj]

The example is trivial: what's the point of using heap at all if you're only allocating one array ever?  Statically allocate the max and be done with it.

He said several times that statically allocating the max he wants would use up way too much of the available RAM.

He has to size the heap for the maximum possible array size anyway, so if nothing else is dynamically allocated then there is no gain over static allocation.  If other stuff is being dynamically allocated, then fragmentation could be possible and the heap would then need to be even larger than the maximum array size.

The only reason that realloc would be needed (for a dynamically allocated array) is if the callback table is changing size at runtime, which seems a very odd requirement.

[T3sl4co1l]

Yeah, that's the real conceit of using a heap: it's statically allocated somewhere.

In an OS, the OS looks at how much memory is attached to the CPU, and says "mine".  Then it partitions that however it sees fit.  If a program requests more memory, and the OS has more available, great.  If not, then the OS tries to make room (swapping), and if that fails, the OS returns "sorry bub, all used up".

This scales great when you have a nearly-continuous amount available (gigs) and almost nothing uses even a fraction of that.  Or even just megs, or even so-and-so kB.  But as the available resources go down -- and when there are fewer and fewer tools available to manage it (CPUs with MMU and virtualization) -- it's harder and harder to offer flexible support without wasting a relatively lot of overhead to begin with, and harder or impossible to offload unused memory (virtualization and swapping).

So on an AVR, you are the OS, all the memory is implicitly yours, and it's up to you to carve up those 2kB however you see fit.

You can use the library allocation functions, absolutely; they're supported even on the 2kB AVR.  But if you can't predict how much you're going to need, you really need to consider what it is you're doing in the first place.  And if that isn't fruitful, your next question should be if this is an X-Y problem -- about the underlying problem X, not the envisaged solution Y.

Tim

[dave j]

I understand that I could just simply size my fixed array to only what is required, but this is where my secondary reason comes in: that I'm trying to make this a more generic solution as part of a module that will be utilised again elsewhere in future, where there may be a wholly different set of callback functions. I just want to make it so that the only thing I have to worry about is making a call to something like a register_callback() function, and that's it. No messing about re-defining constants, etc.

I'm not too worried about safety, as the allocations will be a one-time operation on start-up, and will never be free()-ed.

Can we clear something up? Do you expect to only use this for a table that once initialised is never changed or replaced within an application? If so, why not define the table statically and put it in relatively abundant Flash ROM rather than scarce RAM?

[Siwastaja]

Thanks, glad to know it won't do something unexpected with the heap allocations.

Now, the primary reason why I'm not keen on statically allocating a fixed-size array is because it would take up a significant chunk of memory. If I want to cater for a maximum of 256 callback functions, it will require 512 bytes of memory. My microcontroller only has 2KB of RAM, so that would be 25% of all memory! And, in fact, I will not only be storing a 16 bit pointer, but also an 8-bit integer with each that notes how many argument values are to be passed to the function, which would make it 768 bytes! I don't think I can afford to reserve that much memory.

So you need 3 bytes per function, and 256 total opcodes: a simple table is 768 bytes.

Seeing you think you can save memory by using heap and realloc, I assume the number of callback functions is small, and the problem is only that the array is sparse. If you actually had, say, 200 functions, the realloc wouldn't help, only make things significantly worse.

So let's assume you actually have max 20 functions:

Instead, only store an index to another table:

uint8_t idx_to_meta[256];

struct __attribute__((packed))
{
   uint8_t n_arguments;
   void* ptr;
} meta[20];

And now you are down to 256 + 3*20 = 316 bytes.

Usage is meta[idx_to_meta[opcode]].ptr();

If you can guarantee number of functions to <= 16, you can fit the index in 4 bits, and you are down to 128 + 16*3 = 176 bytes. This is without getting too hacky.

Getting rid of the index table, and storing the opcode in the struct, you save even more at the expense of speed; now you need to loop through the table whenever you get an opcode.

In all of these cases, you need to limit the maximum number of active opcodes (callback functions), but the same is true for the realloc, otherwise you'll run out of memory.

[T3sl4co1l]

Another nice part is you can store the index in PROGMEM, saving even more RAM.  Assuming it's written at the same time the functions are.

Tim

[amyk]

Yep, this happens a lot when application programmers try MCU programming
They've had "global variables are evil" drilled into their brains from day 1 and that dynamic allocation is sexy and efficient.
Moving from 64bit application programming to a 8 bit mcu can be a bit of a shock.

I do more application programming than embedded but I wish more of the former would've started with the latter; I come across things like malloc'ing one byte at the start of a function and then free'ing it at the end, useless obfuscating abstractions, and other disturbingly inefficient code far more common than I'd like to.

[brucehoult]

The example is trivial: what's the point of using heap at all if you're only allocating one array ever?  Statically allocate the max and be done with it.

He said several times that statically allocating the max he wants would use up way too much of the available RAM.

Which doesn't make sense.

If there is a possibility that space will be needed later then you have to make sure nothing else starts using it in the meantime, otherwise you're going to fail when you eventually need it. May as well allocate the maximum and let the other thing fail if it tries to encroach on it.

I'm a big big fan of dynamic allocation and garbage collection (and fairly expert on garbage collectors) but this doesn't seem like the place for it.

[SiliconWizard]

That is, if multiple calls to realloc() are made, each in turn increasing the size of allocation (and never decreasing), is there any chance the allocator will fragment the heap?

Well, if you can guarantee that there never be ANY other allocation between those realloc() calls, probably not. Although it would make assumptions about the allocation algorithm that I wouldn't necessarily be comfortable making. OTOH, if there could be any other allocation between two realloc() calls, then yes. Suddenly a realloc() to a larger size may not fit at its current position, and may need to be reallocated elsewhere, leaving a hole. There you go.

And if you can guarantee there is no other allocation between those successive realloc() calls, then you could definitely design your own allocation scheme, even statically, with ease. Think about it.

There are tons of ways to deal with what you want to do, other than using all-purpose dynamic allocation. You can use static overlays (very common with small-memory CPUs). You can also design your own allocator if that best suits your needs: just statically allocate a big buffer, and then implement your own allocator on top of it. The benefit? You will completely control it, and can guarantee that your assumptions about how it works are actually not guesses, but are how it's implemented.

Also, think about WHY you don't want to "waste" a fixed-size buffer here. It would just have the size needed for the worst case. If you want to keep more memory available instead and just allocate what's needed at some point, that MEANS you are contemplating using the rest for other needs. But what happens if you run into the worst case? Can you guarantee that when you need the maximum size for your table, you will need less memory for all the rest? It may make sense for a particular application, but not necessarily in general. Think about worst-cases and design accordingly.

[ejeffrey]

Thanks, glad to know it won't do something unexpected with the heap allocations.

Keep in mind that this is an implementation detail.  The library implementation is allowed to do almost anything.  I think it is unlikely that the simple allocation libraries used on microcontrollers would do something terribly surprising here but it isn't impossible.  Even then that this will only work if you can guarantee no intervening allocations.  The way you wrote it seems fine, but some library calls (particularly stdio calls) may occasionally call malloc() to allocate buffers.

Now, the primary reason why I'm not keen on statically allocating a fixed-size array is because it would take up a significant chunk of memory. If I want to cater for a maximum of 256 callback functions, it will require 512 bytes of memory. My microcontroller only has 2KB of RAM, so that would be 25% of all memory! And, in fact, I will not only be storing a 16 bit pointer, but also an 8-bit integer with each that notes how many argument values are to be passed to the function, which would make it 768 bytes! I don't think I can afford to reserve that much memory.

Well, if you want to be able to support 256 callbacks you need that much memory.  Unless you have some other way to use the memory that is also determined at runtime and varies independently of the # of callbacks I don't see what you are gaining here.

I understand that I could just simply size my fixed array to only what is required, but this is where my secondary reason comes in: that I'm trying to make this a more generic solution as part of a module that will be utilised again elsewhere in future, where there may be a wholly different set of callback functions. I just want to make it so that the only thing I have to worry about is making a call to something like a register_callback() function, and that's it. No messing about re-defining constants, etc.

Redefining a constant is easy!  Especially when you are talking about moving to another microcontroller with more memory.  Way trickier is handling an OOM error when you call register_callback too many times and realloc() fails.  Alternately since you are just doing this at initialization time why not just count the # of callbacks you need to register and then do a single malloc() call.

Here's another question: can I make any assumptions about the default value of any memory allocated with realloc()? Given that calloc() exists, I would assume that realloc() does not do any initialisation of allocated memory, and so as a worst case scenario, might the allocated memory contain random garbage?

Correct, you can make no assumptions about the contents of the newly allocated memory.  Assume it will be random garbage.  There could be zeros, some pattern like 0xDEADBEEF, or be random.  If you have a stack/heap collision it could contain stack data

That would kind of complicate the scenario where I am allocating memory for a sparsely-populated array, because then any unpopulated op-code pointers in my array would not be null, and thus indistinguishable from a populated one. I would have to write some code to specifically zero-out any 'gaps' in the allocation.

Yes, you should initialize/zero the newly allocated space when you call realloc() just like with malloc().

Also remember that realloc() eats the pointer to the original allocation if it fails.  So you have to store the pointer to a temporary value, call realloc(), check the result, and then if it fails restore the temporary variable and decide what to do (unless you just plan to hard-fault on failure).

There are tons of ways to deal with what you want to do, other than using all-purpose dynamic allocation. You can use static overlays (very common with small-memory CPUs). You can also design your own allocator if that best suits your needs: just statically allocate a big buffer, and then implement your own allocator on top of it. The benefit? You will completely control it, and can guarantee that your assumptions about how it works are actually not guesses, but are how it's implemented.

I wouldn't recommend anyone implement a custom dynamic allocator without a very good reason.  It is very easy to write something that doesn't guarantee what you think it does, or that is not very flexible and fails as soon as you try to use it in more complicated scenarios.  Also, "realloc() will always extend the current memory block if no intervening allocations" is not a very interesting constraint to add.  It is too easy to screw it up with accidental allocation and the need can almost always be avoided.

[westfw]

So... Supposed I have a source structure where I have callbacks for single-letter "commands":

Code: [Select]

class CmdClass {
  int (*callback)();
  int args;
  char cmdchar;
  CmdClass(char c, int (*cb)(), int arg) {
      cmdchar = c;
      callback = cb;
      args = arg;
      register_command(c, this, callback);
   }
   // blah
}
Where performance is critical, so register_command should end up allowing callbacks to happen as quickly as possible, and use as little RAM as possible.  Preferably, register_command() should happen at compile time.  (this isn't meant to be actual code; just the general idea.)

then I can have arbitrarily complex conditional compilation and file inclusion that defines just the commands needed:

Code: [Select]

#if IMPLEMENT_A  CmdClass cmd_a('a', cmd_a_function, 0);
  int cmd_a(CmdClass cmd, int arg) {
     // blah blah
  }
#endif
#if IMPLEMENT_Z
    CmdClass cmd_z('z', cmd_z_function, 0);
    int cmd_z(CmdClass cmd, int arg) {
       // blah blah
    }
#endif

Is there a standard trick for that?

I'm thinking of program memory tables filled with calls to weak symbols, until the symbols are defined (rather like the AVR interrupt vector table.)

But that's sort-of outside the "language" and into dirty assembler/linker tricks...