Fast, predictable memory allocator for embedded stuff

[DiTBho]

To be honest, you are right on one point: mine is a conservative approach that doesn't overestimate my analysis capability on a firmware that is already intrinsically complex for its-own algorithms.

[T3sl4co1l]

Kind of an interesting question to turn on its head: if your habit is to divide things into "eternal" vs. "present", why is that?

Only because I usually prefer to study things that I can describe in phase space, a space in which all possible states of a system are known and represented, and each possible state corresponds to one unique point in the phase space.

If you want a "predictable" memory allocator, the space space offers the best way to mathematically study and describe it.

To be clear, that should be read in a philosophical, not critical, tone.   And, indeed, phase space is a fascinating tool, quite literally sideways to our common thinking, difficult to grasp at first, but powerful once understood.

Downside here is, the space is discrete, the state-transformation function may be highly nonlinear, and the number of points is utterly intractable -- so you'll have to "study and describe it" in some way to hopefully reduce that to a more feasible scale.  (Relatively trivial case: the algorithm should be independent of allocated contents, reducing the space from "total memory", to a few kB or so of tables; depending on algorithm, size, and number of allocations.  ~kB still isn't exactly tractable, but I mean, at least it's not megs.)

Or, conversely: design in that simple, tractable structure from the beginning.  (More formally speaking: prove it by induction, start with a simple case then expand.)

For an analog example, that's how I design circuit boards: by laying everything out in a certain way (ground planes most importantly), I can maintain certain well-behaved assumptions about the EMC characteristics of the system.  It can be reasoned about, it's not a highly coupled system, and it's relatively easy to adjust/fix if better performance is needed (e.g., adding filters or shields).


On a much more tangential note: I feel this is where big numbers actually get scary.  Real numbers -- poorly named as they are, simply aren't real at all, nothing can be known to perfect precision; they are utterly unknowable, intangible.  We only know a few through their relatively trivial relationships with geometric objects (like pi and e), or computable by algorithm to arbitrary precision.  Whereas, we can count to all sorts of large numbers (integers, rationals, whatever, they're equal cardinality), and we use them on, not just a daily basis -- but in a very real sense, we are made of them!  Yet we can fully enumerate systems of only 48 bits or so, and that with difficulty (parallel processing and months of time?).  Much more than that is really not feasible to check exhaustively.  And yet that's a tiny, tiny amount of memory.  And there are only so many things we can do, to tame the combinatorial explosion; beyond which lies true madness, something utterly ungraspable by human mind alone.

Tim

[Doctorandus_P]

I also prefer to use static allocation for embedded software.
Guaranteed no fragmentation, even when the program runs for years.

Embedded software also tends to be small, so there is not much need for dynamic memory allocation.

Sometimes it's handy to declare a relatively big array, and then re-use that array for different sorts of data in different parts of the program. You can even use an array of a union if you want to use different types for your data in those different parts.

Edit:
This method does not work if those different parts of the program need that memory at the same time. (I thought this was so obvious that I did not have to mention it separately)

[PlainName]

and then re-use that array for different sorts of data in different parts of the program

The risk there is that the different parts might get to want the memory at the same time, perhaps after some later rework.

I think we might be flopping between extremes, assuming all allocation is either dynamic or static. Where I use dynamic allocation it is specifically where the design can cope with not getting it on demand (and code specifically written to handle that case). But the same design will have the usual statically allocated memory where it's assumed the memory will always be there. In essence, you use the right approach for the particular feature, not a global all or nothing per design.

I also think that re-use via a union or whatever is worse than dynamic allocation, since there is likely no mechanism to cope with the memory not being available when needed. However, having said that, I've used compilers that did code analysis and then overlaid function variables where those functions couldn't happen at the same time. But this - being done by compiler - is a lot different because it will change every time you compile to ensure no conflict, whereas manually doing it means the current programmer has to be au fait with the peculiarities of  the design and remember to fix any issue that may or may not occur.

[SiliconWizard]

and then re-use that array for different sorts of data in different parts of the program

The risk there is that the different parts might get to want the memory at the same time, perhaps after some later rework.

Absolutely. I was going to say the same.
Funny thing is, this is actually also a form of dynamic memory management. It's just an ad-hoc one.

In the same vein, declaring a static array of objects, and using it to store more or fewer objects in it at run-time *is* a form of dynamic allocation. It's actually equivalent to a pool allocator.

As I said, it looks like many people actually just have prejudices about what dynamic allocation is, and can't see past this. So if you talk about dynamic allocation, it's only going to be the standard heap and unreasoned use of a malloc-like function asking for more memory at any time in any order. Nope. That's just one particular way of doing it - the "easiest" way for general-purpose use. But there are many other ways of using memory dynamically, and as we saw, in some cases, people think they strictly use memory statically while this is actually not quite true.

Using unions for aliasing various data in the same memory area is a good example of that. Oh, I have done it as well, usually in contexts with very little RAM available. But was that without risks? Nope.

I think we might be flopping between extremes, assuming all allocation is either dynamic or static.

For one  yes, because it's always gonna be a mix of both.

But, yes, and not just that, as I tried to explain. Whatever is dynamic seems to also be ill-understood or at least defined in very restricted ways without necessarily looking at the bigger picture.
As I said just above, sometimes it even looks like many will be dead sure they only use "static allocation" as long as they never call a malloc() - or equivalent. This isn't the case. The extreme of this approach is bordering magical thinking again. Like: "If I'm not using malloc(), I'm safe with memory allocation. If I'm not using recursion, I'm safe with the stack." Sure.

This thread was trying to be about various dynamic allocation strategies, more dedicated to specific use cases than the general malloc(). It's a bit sad very few here haven't missed the point.
I also gave examples of what to look at, for instance how memory is managed in the Linux kernel, and actually in kernels of most OSs. I also mentioned "embedded" covers a wide range of systems.

Anyway, I talked about lifetime of objects in memory and how I think it's really all what it is about. As we just discussed, statically allocated objects are usually seen as having "permanent" lifetime - so it looks safer, because in this case you don't have to consider lifetime at all - but in actual software, this isn't exactly how things work. In particular when we deal with dynamically-filled arrays or unions.

In the end... talking about the topic a little bit more would be interesting, instead of just ranting about how we should not even talk about it. At least to me. Now if it doesn't interest anyone else here, that's life.

[SiliconWizard]

So anyway, to wrap it up a little at this point, here is what I've come up with so far. If anyone's interested.

I implemented a linear allocator with a mark/release feature and alignment request for each block allocated. Very simple but allows to control the lifetime of a group of objects, and free them all at once.
On top of that, I implemented a pool allocator. This is basically an allocator that can only allocate fixed-size blocks. More useful that one may think. It's very common, especially in "non-general-purpose" software to have to allocate/ free many objects of the same type. This kind of allocator is used in OS kernels, but also commonly in game engines.

Both are O(1). I've written test code for them. Now I'll write some real-use code to see what can really be done with just that, how useful it is and what would be missing.

I might also implement a buddy allocator after that - typical are the power-of-two ones. Can also be found in the Linux kernel. Benefit is that it allows to allocate and free blocks of non-fixed size in any order (as opposed to the linear allocator), it's also pretty fast, but drawback is that it makes less efficient use of memory. But I'm not even sure this kind of allocator would be needed.

The point is to have the flexibility of dynamic allocation when it is appropriate to use it - typically when you manipulate data that is dynamic in nature - while remaining simple, fast and predictable. Something that can complement simple static allocation while not having most of the drawbacks of general-purpose heap allocators.

For the two classes of examples we mentioned earlier, namely unions for reusing memory areas and fixed-size arrays used dynamically in your code, I think this would offer a more flexible and more elegant solution. One way of seeing it is, as we discussed above, that it's very common to implement ad-hoc dynamic allocation on top of statically allocated memory in practice (and still considering it static), but ad-hoc implementations imply writing the same kind of things over and over again, with the risk of getting it occasionally wrong. So a small, verified library should help limiting the amount of ad-hoc allocation schemes while improving corrrectness.

Of course, as I said, it's not meant for very small targets. There is some overhead, and this overhead has to be justified. I'd typically consider using this, as I said, when at least 1 MB of RAM or so is available.

Still interested in getting opinions about this. As long as they are not limited to "don't do it". Or when they are, at least give concrete examples we can further discuss and see what kind of approach would be more problematic.

[brucehoult]

Still interested in getting opinions about this. As long as they are not limited to "don't do it". Or when they are, at least give concrete examples we can further discuss and see what kind of approach would be more problematic.

I have a few opinions on this. (Don't I always?)

Relevant experience is writing the memory allocator/GC for a J2ME to native (ARM, mostly ARM7TDMI) compiler for mobile phones in 2006, running Java games (and other apps) on phones with sometimes as little as 390 KB, though 1 to 2 MB was more common.

A couple of quick points:

1) execution can be divided into two phases: app startup, and the event loop. It's good to be able to detect the boundary between them and free up as much as humanly possible of the junk from the startup phase.

2) patterns of allocation in the event loop phase are (duh) cyclical, and it's very very important that repeated patterns of the same allocations and deallocations don't continuously create fragmentation and new previously untouched memory to be used.

3) part of achieving 2) is if a large memory block if freed NEVER split it up and use it for smaller allocations. Assume that there WILL be a later allocation of the same size block that will reuse it.

4) avoid allocations of large randomly-sized memory blocks, especially with sizes determined by runtime data. Set a fixed maximum object size (256 bytes, 1K, 4K, whatever) and split larger arrays and strings into a list or tree of chunks if you can't just avoid them altogether. (simply ban very large structs -- that was no problem compiling Java where structs can contain only pointers to arrays, not embedded arrays)

[SiliconWizard]

Your input is always appreciated.
You're talking about a rather general purpose allocator, here, as far as I understand. So again that's not quite what I'm after. Sure we all would (or would we?) like a general-purpose allocator that is the perfect, O(1), non-fragmenting allocator and can allocate blocks of arbitrary size, but that just doesn't exist. So I'm considering and focusing on specialized allocators. Of course they do impose particular allocation patterns, which IMO here is a good thing, but it's also a significant constraint, thus that would be much harder to apply to more general-purpose "computing".

With that said, your points do confirm that it's pretty much all about object lifetime, and favoring fixed-size allocations, as I pointed out before. That's indeed the direction I'm taking.

[brucehoult]

Your input is always appreciated.
You're talking about a rather general purpose allocator, here, as far as I understand. So again that's not quite what I'm after.

No, not really.

I think there are very strong parallels to be drawn between games on restricted mobile devices and typical embedded applications. Both are structured around an event loop and run, potentially, forever, with cyclic patterns of allocations and deallocations and a fairly fixed upper bound on the total memory actually being used. The thing you absolutely want to avoid is a cyclic pattern repeated thousands or millions of times slowly growing the heap without bound.

This is very different -- and uses a different allocator -- from programs such as compilers, or business batch update tasks, or a process that is started up to service a web request.

[Nominal Animal]

Even more interesting is to, OTOH, find use cases for which dynamic allocation (done properly with the right allocators) could actually be safer than just relying on static allocation. Or even if not safer, could at least be the only reasonable way of implementing things.

One of my favourite examples is fgets() versus getline().  The former uses a fixed-size buffer (or one you can reallocate yourself), and the latter uses a dynamically allocated buffer.  And since the typical use case is

Code: [Select]

    char   *line = NULL;
    size_t  size = 0;
    ssize_t len;

    while (1) {
        len = getline(&line, &size, stdin);
        if (len < 0)
            break;

        /* Use line; the pointer may vary from iteration to iteration.
           If you steal the dynamically allocated buffer, set line=NULL, size=0.
        */
    }

    free(line);
    line = NULL;
    size = 0;

    if (ferror(stdin)) {
        /* Read error occurred */
    }
it's not like it's that much more code, either.  You can even detect embedded nul bytes in the input (strlen(line) != len).

With that said, [brucehoult's] points do confirm that it's pretty much all about object lifetime, and favoring fixed-size allocations, as I pointed out before. That's indeed the direction I'm taking.

I find myself doing that as well.  If I don't have specific knowledge of the object lifetime or size, I just use the default general-purpose one, until I know more.

In the past, I mentioned using pool allocators in service daemons; there, all objects allocated for the purpose of a specific request can be discarded when the request is completed.  For example, Apache uses this approach (see APR for details).

Fixed-size allocations do not suffer from fragmentation, never need to be split or coalesced; this alone is sufficient for accepting at least some "waste" (using larger fixed-size allocations to accommodate smaller sized requests).

In systems programming, like the getline() example above, realloc() is surprisingly often called.  (Obviously, there are workloads where almost all allocations are final, too; I just meant that it is worth it to examine how the allocation size changes in a specific workload during its entire lifetime.)  The only cases where an allocation is shrunk is very soon after populating it, with any further changes to the size extremely rare.  (Typical example is when reading a file or all input from a descriptor or socket.  As more and more data is read, the contiguous memory chunk is reallocated larger and larger.  When the end of input is reached, the data is padded/terminated with some nul bytes, and reallocated to a suitable final size.)

The bucket brigade approach –– for example, splitting larger objects like arrays and strings into a sequence of sub-objects containing a varying amount of data in a fixed-size container –– is more efficient, but programmatically much more complex.  The two main users I'm familiar with are Apache and the seq_file interface in the Linux kernel.  In the Linux kernel, it's often used with e.g. pseudofiles (the interfaces where the kernel provides run-time information using a file-like interface under /proc (procfs) or /sys (sysfs)).

(When musing about the various approaches to replacing the standard C library with a more useful API, the bucket brigade approach (and generators/iterators in particular) have been on my mind, but I do not think they warrant the increased complexity in the typical use cases.)

I think there are very strong parallels to be drawn between games on restricted mobile devices and typical embedded applications. Both are structured around an event loop and run, potentially, forever, with cyclic patterns of allocations and deallocations and a fairly fixed upper bound on the total memory actually being used. The thing you absolutely want to avoid is a cyclic pattern repeated thousands or millions of times slowly growing the heap without bound.

Fully agreed.  These often have rather unique patterns to the sizes of the allocations, too, so simple rules of thumb are unlikely to work.

Growing the heap (or memory-mapped pools) without bound does not imply a memory leak, either: all you need is a pattern of allocations and releases that interacts badly with your free space coalescing and allocator selection routines, and you end up with holes in your heap that are too small to use for new allocations, with releases only adding new holes (sufficient only for same-sized or smaller allocations).  Nasty.  (This is something I have not investigated myself, and have left for the general-purpose allocator designers and implementers to worry about.)

[brucehoult]

Growing the heap (or memory-mapped pools) without bound does not imply a memory leak, either: all you need is a pattern of allocations and releases that interacts badly with your free space coalescing and allocator selection routines, and you end up with holes in your heap that are too small to use for new allocations, with releases only adding new holes (sufficient only for same-sized or smaller allocations).  Nasty.  (This is something I have not investigated myself, and have left for the general-purpose allocator designers and implementers to worry about.)

As I said a couple of posts up: never take a free'd memory block and spit it up to satisfy a smaller memory allocation. Always assume that whatever needed that large memory block before will need another one the same size again later.

[Nominal Animal]

As I said a couple of posts up: never take a free'd memory block and spit it up to satisfy a smaller memory allocation. Always assume that whatever needed that large memory block before will need another one the same size again later.

Like I said, I haven't investigated this myself; it could indeed be that simple.

What really, really interests me in this topic, is whether usage hints to the allocator could make a measurable difference: in particular, that a specific allocation/reallocation is considered almost certainly "final"; likely to be grown; and whether it might be useful to obtain the actual allocated size; and if letting the allocator decide how much to grow an allocation when "more" memory is needed, with a minimum or hint given as a parameter.  The current dynamic memory management interfaces (malloc()/realloc()/free() or new()/delete()) are, in my opinion, rather simplistic.  At least a hint "will-grow" or "will-shrink" via a flag should be useful; maybe also grouping allocations (for pools or groups that can all be released at once).  Dunno for sure; I just find it interesting to try and work out.

Even an interface that takes an array of pointers, and optimizes those dynamically allocated regions, might come in handy: essentially an user-initiated memory defrag.

So, @SiliconWizard, do you already have an API or interface you want your implementation to conform to?  As shown by Apache development history (and the way Linux kernel seq_file_path() still does not escape backslashes in file names, making it possible to fake paths/mislead users re. paths containing backslashes), it is not always possible to get even the best developers to understand how to use the interfaces properly.

And then you get to the question of how much effort is appropriate here, considering how well already existing Garbage Collectors perform?  (I have no answer or opinion to that myself.)

[brucehoult]

The bucket brigade approach –– for example, splitting larger objects like arrays and strings into a sequence of sub-objects containing a varying amount of data in a fixed-size container –– is more efficient, but programmatically much more complex.  The two main users I'm familiar with are Apache and the seq_file interface in the Linux kernel.  In the Linux kernel, it's often used with e.g. pseudofiles (the interfaces where the kernel provides run-time information using a file-like interface under /proc (procfs) or /sys (sysfs)).

Those are solving different problems. In particular, the main problem being solved by the Apache data structure is efficiently inserting / deleting / replacing sequences of bytes within the "array". That's more like a rope/cord data structure: https://en.wikipedia.org/wiki/Rope_(data_structure)

Both of those are build on top of arbitrary-length arrays, which are probably just allocated with standard malloc() or similar.

The more fundamental task is to efficiently represent arbitrary-length arrays that are "large" with respect to the amount of memory available.

The data structure I've used in several projects to do this is a tree with exactly two levels, which I will call a SegArr:

1) a set of memory blocks containing the actual data, with every block except (possibly) the last one being of a fixed and known size, the largest size contiguous block you're prepared to allocate. All blocks except the last one are full.

2) a single memory block containing an array of pointers to the blocks with the data, plus at least one item of metadata: the number of data bytes currently allocated (which implies the number of data blocks, the size of the last block, and the number of pointers in the root block (and therefore the size of block allocated to hold it)

In any given program the block size and the metadata present will be the same for every SegArr object.

The block size should be big enough to hold enough pointers so the data blocks for an object can use as much of physical or virtual memory as you anticipate needing for the largest array/string you'd ever want. This is in general sqrt(MaxSize * sizeof(char*)).

For example, on a Cortex-M3 with 16 KB of RAM and 4 byte pointers, it might make sense for the block size to be sqrt(16384*4) = sqrt(65536) = 256 bytes. The maximum array/string you could have would then be 256 bytes of pointers, minus one for the metadata, equals 63 pointers. Each pointer (except maybe the last one) points to a block of 256 bytes. So the biggest object possible is 63*256 = 16182 bytes.

Your memory allocator would probably support blocks of size 16, 32, 64, 128, and 256 bytes. It would obtain these blocks from pages of 256 bytes, with each page split into blocks of equal sizes. Two bytes of metadata for each page is sufficient to hold a bitmap of which blocks are in use (with 16 byte blocks, there are 16 blocks in a page).



Accessing a single random value in the SegArr is a little more complex than for a normal C array, but not all that much. Ignoring metadata to make it more apples to apples, instead of...

Code: [Select]

char ch = ptr[idx];

... you need ...

Code: [Select]

char ch = ptr[idx/256][idx%256];

For loops that process a lot of data you use an iterator interface that loops over (ptr, len) pairs and you have barely any overhead (lines of code or instructions executed) compared to using a normal C array.

[brucehoult]

The current dynamic memory management interfaces (malloc()/realloc()/free() or new()/delete()) are, in my opinion, rather simplistic.  At least a hint "will-grow" or "will-shrink" via a flag should be useful; maybe also grouping allocations (for pools or groups that can all be released at once).  Dunno for sure; I just find it interesting to try and work out.

realloc() is evil. Don't use it. Don't try to grow things in place. (except if you know the memory allocator gave you N bytes and you know you're using only M, and you want to grow it to something else also less than N -- but that's for you to know, not the memory allocator.)

Use SegArr, as described in my most recent comment.

[Kalvin]

Without a proper memory consumption analysis and measurement, the system will have either too much of RAM or too little RAM. If the RAM size is estimated too low, the selected memory allocator will eventually fail. If the RAM size is estimated hugely too high, the system may become too expensive or the power consumption may be too high, or the memory allocator may just fail at later time. Of course, too much RAM is not a catastrophe from the technical point of view. But not knowing the RAM consumption is a huge system design failure.

Using a traditional malloc() is not a recommended approach for a system that needs to be reliable and deterministic, due to possible memory fragmentation issues.

Measuring and analyzing the overall memory consumption (stack and heap) and heap's memory block size usage for a typical use-case and for worst-case scenarios will give a good engineering information how much RAM will be needed and what kind of memory allocator is required.

The systems engineering has to be prepared that something unexpected may and will happen. A little paranoia will not hurt. It is a good engineering practice to expect, and to be prepared, that the memory allocation will fail anyway for some unexpected reason at some unknown point in time. Thus, there has to be a plan how to prevent excessive memory consumption in the first place, how to monitor memory consumption, and how to prevent the memory fragmentation. Also, there has to be a way and policy how to detect the memory allocation failures, and how the device shall handle those situations. Lastly, there shall be an analysis what will the consequences be if such event should ever happen.

I have used static allocation and memory pools successfully in embedded systems. Adding instrumentation in the system's application code is not too difficult, and it will give good inside information for the RAM usage of the use-cases that the system has executed. Since my applications has not been mission-critical in a sense that system failure will not result life-threating or catastrophic incident, I typically will just reboot the system in a controlled manner with some diagnostic code saved for later analysis, if something unexpected should happen.

[Kalvin]

Memory allocation failure may provide similar surprise like the issues with the Boeing 787 Dreamliner and Airbus A350, for example: It is required that the 787 Dreamliner shall be rebooted before the system's uptime exceeds 248 days. Same thing with Airbus A350 software bug, which forces airlines to turn planes off and on every 149 hours. These were not due to memory allocation failures, but due to the fact that a 32-bit timer will overflow after certain uptime, and cause "partial or total loss of some avionics systems or functions".

The common thing between memory allocation problems and the problems with these planes is that something unexpected is happening, which was not properly analyzed during systems design phase, and which went unnoticed until the product was manufactured and deliver to the customer.

[Nominal Animal]

realloc() is evil. Don't use it. Don't try to grow things in place.
Use SegArr, as described in my most recent comment.

I disagree: the SegArr just shifts the complexity to different code.

I would prefer an allocator that would let me make a tentative allocation whose size is likely to change, resize it as needed, and finally finalize its size (making it unlikely to change in size afterwards).  It is a common pattern, for example when reading input (especially from standard input, pipe, or socket).

One can do malloc()+free() instead (and I do that for example when resizing hash tables), and expecting oldptr==newptr after newptr=realloc(oldptr,size) is utterly silly (and I consider such a bug), but I refuse to consider realloc() evil per se.

In practice, my processes typically have at most one such growing allocation at a time, with all other realloc()s rare enough that I'd be happy to consider them as malloc()+free() instead, as long as that growing allocation will not cause memory fragmentation etc. issues.  I'd be happy to even let the realloc() round the new size up if it wants to, for efficiency.

I do not know how common those patterns are in embedded environments, though.  I'd expect anything that reads say human-readable configuration files to do something similar.

[SiliconWizard]

So, @SiliconWizard, do you already have an API or interface you want your implementation to conform to?

Absolutely not, and that's the beauty of it. At the moment I'm just trying to write a set of specialized allocators that can be used each for specific use cases. As you saw, I'm not trying to reinvent the wheel either; I've - at least for now - implemented well known allocators, such as linear (also called "arena") and pool allocators.

Since I'm considering their use in contexts in which either dynamic allocation is rarely used - for reasons we already exposed - or, if used (sometimes unproperly), just with standard allocators, I'm pretty much free to implement whatever interface is simple and does the job.

And then you get to the question of how much effort is appropriate here, considering how well already existing Garbage Collectors perform?  (I have no answer or opinion to that myself.)

The effort, actually - as you can guess - is not much about implementation. It took me just a couple hours at this point to get something working well. Sure it's just still a WIP. The effort is all about using allocation properly and choosing the "right" allocation patterns.

Sure using a garbage collector may look like an answer to everything, like 42. You can in theory just allocate things of any size at any time without ever having to worry about lifetime and freeing them. But that's kind of the opposite of what I'm looking for. GC can't be predictable by nature. Sure there are some implementations that allow configuring behavior so that you have more control over them, such as when they'll be collecting garbage, but in this case they real benefit becomes questionable. Keep in mind I'm not thinking about *general-purpose* use cases, for which I may tend to agree than GC is not so bad.

GCs, even the "best" ones, for anything timing-critical is frankly out of the question in general. I just want allocators - at this point at least - that are ideally O(1), the execution of which thus doesn't depend on state, such as what had already been allocated or freed.

The whole point here again is more about allocation patterns than about the allocators themselves, in the end. The required allocators are then just the right tools for the allocation patterns we decide to use. And as I said before, while specialized allocators may look very unflexible, that very constraint forces us to think about allocation patterns. Which IMO is a good thing. The pitfalls of general-purpose allocators come from their very flexibility: we want to use them without having to work on object lifetime whatsoever, the worst in that regard being GCs!

Now could this be a drop-in replacement for malloc (/new/...)? Absolutely not.
And yes, I'm not really reinventing any wheel either. This is already what is done in many kernels, game engines, and other applications. I'm just trying to apply that to "common" embedded development - for which, as you saw, dynamic allocation as such is usually rejected, while it seems that people rejecting them haven't taken a look at the above use cases - and see how that goes.

[SiliconWizard]

Your input is always appreciated.
You're talking about a rather general purpose allocator, here, as far as I understand. So again that's not quite what I'm after.

No, not really.

To me, it is. Of course I haven't seen what you implemented exactly. But any allocator that would allow to allocate and free arbitrary-size blocks without constraints is a general-purpose allocator.
This may of course be a matter of definition.

I think there are very strong parallels to be drawn between games on restricted mobile devices and typical embedded applications.

Of course, and I mentioned them as well!

Both are structured around an event loop and run, potentially, forever, with cyclic patterns of allocations and deallocations and a fairly fixed upper bound on the total memory actually being used. The thing you absolutely want to avoid is a cyclic pattern repeated thousands or millions of times slowly growing the heap without bound.

This is very different -- and uses a different allocator -- from programs such as compilers, or business batch update tasks, or a process that is started up to service a web request.

Again we're talking about allocation patterns here. The allocator itself may or may not be different, but  the main point is the allocation patterns, precisely.

If I needed to explain it again, I'll again say that in this thread, I'm not looking for a drop-in replacement (whatever it is) for a standard allocator. I admit this may have appeared to have shifted a bit from the initial title of the thread. But that's part of the thought process.

[brucehoult]

realloc() is evil. Don't use it. Don't try to grow things in place.
Use SegArr, as described in my most recent comment.

I disagree: the SegArr just shifts the complexity to different code.

That's what engineering is :-)

[SiliconWizard]

The current dynamic memory management interfaces (malloc()/realloc()/free() or new()/delete()) are, in my opinion, rather simplistic.  At least a hint "will-grow" or "will-shrink" via a flag should be useful; maybe also grouping allocations (for pools or groups that can all be released at once).  Dunno for sure; I just find it interesting to try and work out.

realloc() is evil. Don't use it. Don't try to grow things in place. (except if you know the memory allocator gave you N bytes and you know you're using only M, and you want to grow it to something else also less than N -- but that's for you to know, not the memory allocator.)

That's a bit drastic. It all depends on context - use case, underlying system, amount of free memory available, of course the type of allocator... If you're using the standard allocator, are on "general-purpose" system/OS and need a consecutive block, trying tro grow in place if free memory is available can make sense.

But the question of resizing allocations (growing/shrinking) efficiently is an interesting one anyway. In the context I'm working on here, that's the kind of allocation scheme I think should be avoided as much as possible though.

[Nominal Animal]

realloc() is evil. Don't use it. Don't try to grow things in place.
Use SegArr, as described in my most recent comment.

I disagree: the SegArr just shifts the complexity to different code.

That's what engineering is :-)

True. I currently just see realloc() as being the proper place of complexity for certain cases –– not for all, by any means.

At the moment I'm just trying to write a set of specialized allocators that can be used each for specific use cases. As you saw, I'm not trying to reinvent the wheel either; I've - at least for now - implemented well known allocators, such as linear (also called "arena") and pool allocators.

Right.  I asked, because I'm problem-solving oriented, and wanted to know if there was a *particular* problem you were trying to solve; or just building tools for solving a general class of problems.

None of this is reinventing the wheel, in my opinion.  I haven't found anything that discusses which types of allocators are best suited for what kind of use cases, except for in projects that are implementing their own –– and even then it tends to be on the order of "hey, I think *this* works better than what we have right now; here's the patch series".

And then you get to the question of how much effort is appropriate here, considering how well already existing Garbage Collectors perform?  (I have no answer or opinion to that myself.)

The effort, actually - as you can guess - is not much about implementation. It took me just a couple hours at this point to get something working well. Sure it's just still a WIP. The effort is all about using allocation properly and choosing the "right" allocation patterns.

I was thinking of entire projects, actually; not just implementing the allocator or GC itself.

And I'm definitely not criticizing, just pointing out that at one end of the toolbox are the GC's, at the other end static allocations only, and a whole plethora of tools in the middle.  I myself am very interested in the tools in the middle, and enjoy the discussion; just thought it was prudent to mention the GC end since the static end has already been mentioned.

I do believe I covered reallocation patterns already: in the use cases I know, there is usually only one that does not have a final size yet, and it would be useful to allocate it such that growing it would be cheap safe; with an API 'promise' that it will be either freed, or resized to a final size, using a separate call.  It does not matter if reallocating it really is a malloc()+copy+free(), what matters is that any repeated reallocations of it won't cause undue defragmentation, useless holes in the heap.

Fixed size allocations are nice, because fragmentation is not an issue.

It is tempting to think that using a generic allocator at first, and just checking what kind of allocations it makes and choosing an optimized version dedicated to it shuld lead to optimum results, but fact is, like you and others have already mentioned, we the programmers choose the allocation patterns when we implement our code.  For better results, we should know beforehand what kind of allocator we target.

As an example, let's say I'm writing a smart display appliance based on Teensy 4.x ($20) or NXP MIMXRT1062, running at up to 600 MHz, with 512k of tightly coupled RAM, another 512k on the MCU, let's say 8M of PSRAM, and graphics resources (icons et cetera) on an microSD card (FAT fs, SDIO, fast enough).  I have three 'zones', of which the TCM is more or less performance critical (so much so that the hottest code is best copied to TCM), with the 512k being "fast", 8M "slower".  And microSD cards have basically unpredictable latency.  I should do what companies do, and just rely on the hardware being fast enough that even bare-assed software works for the users... but I cannot. I don't think I would use a single allocator for the three RAM zones.  I think I would first have to do some test cases to decide how to best use the zones, before doing any systems integration.  The allocation patterns and allocator schemes would be critical for long-term stability; and really need to be designed in before writing the code that relies on them.  It does *feel* a bit bass-ackwards to me, but if that's what stability and efficiency requires, then that's what I'd do.

[T3sl4co1l]

GCs, even the "best" ones, for anything timing-critical is frankly out of the question in general. I just want allocators - at this point at least - that are ideally O(1), the execution of which thus doesn't depend on state, such as what had already been allocated or freed.

How about this:

Take the hash of the data.  Go to that address.  Write the data.

Doesn't even need to know the length of the data!

It's a hash map, so your memory utilization is stochastic, which does limit efficiency.  It also carries a random chance of overwriting previous data, but what are the chances that's going to happen?? ;-DD

Ok, so CS shitposting isn't exactly being helpful, but suffice it to make the point, I'm guessing you're looking for a deterministic, lossless one as well.

I just don't think I've seen this method suggested before; it's not quite a hash map, because that would do a check first, see if the slot (at given length) is actually available, and do something else if not.  As horrible as it sounds, there are some neat applications of lossy hash maps, for example to cache whether an item has been seen or not.  If the map is blank, definitely not; if it's nonzero, not necessarily so.  But that's good enough for a cache.

Tim

[Kalvin]

One could argue that using a single/one memory allocator (typically malloc()) in a system is sufficient. Using a general purpose, one-size-fits-all memory allocator [like malloc()] in an embedded system will not provide optimal results.

If a system implements multiple tasks that are using dynamic memory allocation (like malloc()), it would be better to organize the architecture in a such way that each task would also manage its own, separate heap. In that way each task can use whatever memory allocation algorithm is suitable for that particular task. The tasks that are time-sensitive and has high requirements for determinism can use faster memory allocators, for example.

Separating the heaps will give also give some flexibility for the unfortunate situation where one task or system runs out of its heap memory, for example. Typically, if the system runs into memory allocation problem, the system needs to restart itself, or enter some sort of reduced operating state, unless the system can recover itself from the heap exhaustion.

If each task manages its own memory heap, it may even possible to restart some of the less critical tasks. Since each task manages its own memory heap, each task can also reinitialize its own heap without affecting other tasks. That would not be possible using a single, system-wide heap manager like malloc().

Also, if the system or a critical task runs out of heap memory, this critical task can shutdown less critical task(s) and steal some memory from the shutdown task(s) in order to be able to shutdown the system in a controlled manner, or enter and operate in the reduced operation state. With the system-wide heap manager this will not an easy operation to do.

Using separate heaps may increase RAM requirements, if not done wisely. On the other hand, using separate heaps it will be easier to measure, control and fine-tune the memory usage and RAM requirements for each task. Thus, it may be even possible to reduce the RAM requirements, because we can control the RAM usage more closely.

[Kalvin]

I am using this practice/policy in my code shown below, which makes it very easy to change the memory allocator used in a module/task. All that is required is creating macros or an inline functions for malloc() and free() for each module/task.

Code: [Select]

//
// File mymodule.c
//

#define mymodule_malloc(N) malloc(N)
#define mymodule_free(P) free(P)

static bool mymodule_malloc_init()
{
    /* Nothing for standard malloc() */
   return true;
}

static void mymodule_malloc_cleanup()
{
    /* Nothing for standard free() */
}

It is now trivial to add instrumentation and debugging for the memory allocations for each module/task separately by redefining the module's/task's memory allocation macros/functions.

Using this convention it is possible to start with the evil general purpose malloc() and free(), and it is very easy to change the memory allocator at the later time if needed.