malloc/free algorithms

Op Wed, 24 Feb 2010 07:48:35 +0100 schreef D Yuniskis :

Non-deterministic malloc/free implementations tend to be inefficient (i.e., unpredictable timing).

What are you implying here? The user seems to be required to supply a pointer to a "fragment selector function". What is that supposed to do?

Have different heaps with different algorithms.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

D Yuniskis wrote:

That is well-known. My point is, those attempts at producing (quasi)deterministic algorithms usually work at the expense of wasting memory (c.a.e)

Obviously: select the "best" fragment to fit the request!

I currently support multiple heaps. The post was intended to show how *any* heap could support a choice of algorithms (hence the selector function) -- which could be applied to a single heap as well as multiple heaps.

I'm afraid cannot be as simple as that.

I understand that the function argument is a pointer to an array of fragments. Is it sorted by size? Does it contain fragments that are too small? What if some other thread releases a "perfect fit" fragment within an acceptable time-frame?

Why not just specify a size and a time-out, and let the malloc algorithm do the rest?

do?

But Don, this is far from being the "best" approach, that stuff has been analyzed in the early days of OSs and seems to have been well forgotten today. The best approach by a good margin is the worst-fit allocate strategy, that is, you always allocate at the beginning of the largest contiguous block you have. This results in the least possible fragmentation over time of all known approaches. This is how DPS does it for both system memory and disk space - slightly modified, actually, when allocating more space to a file it is first checked if it can be allocated so that the file remains contiguous. The overhead for discovering the largest contiguous block is constant (and nothing too huge) so the time to allocate is also more or less constant. This has been so since day one of DPS - (that day was > 15 years ago... how can that be, I could swear it was yesterday :-) ). A few years back I made an object - DPS has its runtime object handler and tree of objects - which I call "memory_pool", very convenient to be used by other objects and accessed from shell scripts. It also uses worst-fit allocate, of course :-) . Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

The classic contract with malloc(3) makes *no* guarantees other than "you will get a block of memory that will completely hold an object of 'size' -- or you will get nothing".

How it picks that fragment is entirely up to it's (malloc's) implementor.

I contend that the user (programmer) often has knowledge of how he *will* be using memory -- what sorts of allocations he will request as well as when and in what pattern. By hiding all of the allocation mechanisms inside malloc(3), you do the developer no justice.

I am advocating augmenting the interface to malloc -- call it nalloc if you like -- so that the user can influence the decision making process based on *his* intimate knowledge of

Because malloc has *no* information about the application itself. And, because the resource that it manages (memory) is typically pervasive throughout the application.

Any "static" allocation algorithm has to make assumptions about how memory will be used. OTOH, the programmer

In one of the applications I am working on currently, crt0 builds the "system heap". My "init" task then allocates blocks of memory for use by the RTOS. These contain static data structures, etc. Some are small, some are large. THEY WILL NEVER BE FREED.

Interspersed among these allocations, there are often numerous other allocations (which *will* be freed, typically).

A naive malloc will treat all of these the same -- since the only information that it has at its disposal is the

I, on the other hand, know which allocations will be static. I can pass a selector() to malloc which will bias its choice of how (and "where") it selects its fragment.

For example, the static allocations might be, BY CONVENTION, selected from the "back" of the heap (highest addresses). So, the top end of the heap slowly disappears as these (static) allocations are satisfied. Once they have all been satisfied, the memory footprint looks like the heap was just smaller than you originally thought (because the "back" has been *permanently* consumed)

Meanwhile, other allocations can proceed (again, by convention) to be satisfied from the *front* of the heap. Their dynamic nature doesn't result in any fragments embedded among the "static" allocations at the "back" of the heap.

As each task is created, I allocate a stack for that task off the system heap. For some tasks, I allocate a heap at the far end of that stack segment for the exclusive use of that task (i.e., that task's memory requirements are constrained; alternatively, that task's memory requirements are *guaranteed*!)

How each of these malloc's ideally behave would obviously be related to the needs of their clients. But, their clients would obviously be more knowledgeable about those needs than the "standard library" would! :>

When I am working in paged memory environments, I manage memory differently than when I have no MMU support. So,

If the user can provide more information to malloc to bias the selection algorithm(s), then you can also get more deterministic behavior (in some classes of applications and memory usage patterns) than you could with a "boilerplate" malloc.

My point is, instead of relying on one algorithm and *hoping* it satisfies all your requests "good enough", why not provide hints to malloc that could make it more efficient? Best fit, worst fit, first fit, last fit, smallest containing, etc.

What I hoped to glean from this post was pointers to research as to the efficacy of various allocation algorithms wrt their temporal behaviors.

Hi Don,

I was referring to dynamic allocate, whether paged or not, DPS uses static allocate on boot time for pieces which will never be released (there is a setup.syst file, one can install device drivers using it so they get stuck together on a .l basis rather than being cluster aligned etc.). Then DPS also has an area of "BAT translated" memory, one needs it in MMU systems to place IRQ handlers in it so an IRQ does not cause a page fault (so the DSI exception can run without masking IRQ). Now this is also statically allocated, default or via setup.syst. But all that static allocate - which DPS does by simply adding to the heap before calling it a boot and allocating the entire so far taken heap in the CAT (Cluster Allocation Table).

I now get some of your point. Of course this is so. I did not get what exactly you were after because I don't use C (I regard it as being "write only" and generally a waste of my time) and so when programming I have access to all of the allocate facilities (I use VPA, Virtual Processor Assembly, which I based on 68k assembly and took forward, meanwhile quite a distance forward; I have yet to encounter someone matching my efficiency using some other language :-) ).

Well if the language would allow to pass malloc not just the requested size but also some more info it could choose which system facility to use - if I get what you are after. E.g. give me that much memory but guarantee it will be contiguous - one needs this for buffers used by say DMA; or allocate that much memory at this fixed address - one may need this and well, may be denied it :-); etc. etc.

But I am not sure I get exactly what you are after since I have long since decided I will not let HLL restrictions stand in my way, life is too short :-).

Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

Original message:

Yes, sorry, I think we are cross-communicating. By "static" I meant the algorithm used *in* malloc. I.e., if it DOESN'T CHANGE (which was the goal of my "selector" function), then the way that it allocates remains constant (static) throughout its use.

I.e., it will always use the same heuristics to allocate a block of size N (which is the only parameter that it can receive from the "application")

But, you can only do a static allocation (using C's concept of static vs. dynamic) if you know the sizes of those items. If they can vary in size, then you rely on malloc (sbrk, etc.) to set aside the memory that they require.

This is "wired down" memory (not pageable)

Some of us have to write things that others will maintain :>

Yes. The classic malloc(3) has a very narrowly defined interface. Of course, how it works "behind the scenes" is up for grabs -- so long as it implements the functionality advertised.

I am suggesting a different malloc (call it something else) and features that would be helpful in such a malloc with particular emphasis on how it could be applied to providing some degree of determinism that a "classic" malloc implementation can't (note my initial comments regarding how quasi-deterministic implementations of malloc are inefficient in their handling of memory *and* that c.a.e type applications tend to be concerned with needless waste in that area)

Yes. One could change the selector to accept a va_list and, for some of the selectors, that list could include arguments like "make the allocated region adjoin the region containing *this* address, etc."

Hi Don,

Aha, thanks for the name (I did not know it).

Not having many more ideas to contribute I guess the following triggered some more or less related output from me:

In DPS, it is called allocm (LOL). Actually it is allocm$, but the $ is just to make the call name difficult to duplicate.

It is - just looked it up - the very first DPS call I have written all these years ago :-). You pass in D2 the amount of memory you want, you get in A1 the address of the piece you got and in D1 the actual size (which will obviously be cluster aligned).

Oh well, I guess I mentioned what flavours of it I have done over the years, not sure if they relate to a C function (I guess they do if one implements a compiler for DPS which I have not done yet). Another related detail is the way memory gets deallocated. The allocm$ leaves it to the application to deallocate upon exit or forced kill; it can choose to leave the piece allocated (say, having installed some device driver or object descriptor). Then I also have the allmr$ - allocate registered - which will be deallocated by the system upon task kill. And then I remember chasing a bug at the dawn of DPS which was occasionally crashing me - I was deallocating the task's system stack a little too early upon kill - and the system being without a MMU (a proud 68340 with 1M RAM...)tolerated that as long as no other task got that too early deallocated - and still in use - piece of memory.... :-).

Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

Original message:

Like prepending "_" in C, etc.

I've taken very different approaches over the years (and, varying based on project needs/resources, etc.)

Currently, I am leaving much to the application -- e.g., I don't protect heaps with dedicated mutexes (since that makes the call more non-deterministic and often isn't needed as the application *knows* how/when it is using the dynamic store). But, I *do* "clean up" after a task terminates as it is relatively easy to do (if the task has been given its own private heap -- I *don't* track per task requests made on the system heap!).

This was a common bug in early uses of realloc()...