Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

github.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#51

Post by CyberDildonics »

okl wrote: post #38
CyberDildonics wrote: post #36

Earlier quoted context omitted.

What is the difference between allocating memory right when the program starts with malloc and using the same size in static unitialized byte arrays? There are differences of course, but that memory can be used in the same way, and so memory pools are orthogonal to how the memory is aquired.

If you use modules with opaque pointers, the types are incomplete and therefore their size is not known outside of the module. You can either make the type visible (against the idea of opaque pointers), modify the module to allocate a fixed set of instances (somewhat against the open/closed principle), or you let the module use malloc to allocate memory for new instances.

Why would someone be doing this while trying to fit within the boundaries of the MISRA standard? Also what do you mean by module?

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#52

Post by davidtgoldblatt »

felixguendling wrote: post #35

As some comments point out that this code might not be production ready, can anyone recommend other solutions that are able to manage a given block of memory? My understanding of libraries like jemalloc is that they are replacing malloc (using system calls brk and mmap [0]) but I can't hand it an already allocated block of memory to manage, right? Something like memory_manager m(some_buffer); allocation a = m.allocat…

Depending on what exactly you mean by "hand it a block of memory to manage", you can do this with jemalloc's extent hook functionality. Though that's meant for "I have some long-lived data structures, I want all their memory stored on hugepages" more than "I have this small-ish data structure, I want to batch its allocations together".

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#53

Post by okl »

CyberDildonics wrote: post #51
okl wrote: post #38

Earlier quoted context omitted.

If you use modules with opaque pointers, the types are incomplete and therefore their size is not known outside of the module. You can either make the type visible (against the idea of opaque pointers), modify the module to allocate a fixed set of instances (somewhat against the open/closed principle), or you let the module use malloc to allocate memory for new instances.

Why would someone be doing this while trying to fit within the boundaries of the MISRA standard? Also what do you mean by module?

The rule you are referring to is a "required" (not a "mandatory") rule. You can deviate from it and still be MISRA-C compliant. People write deviations for all kinds of reasons. Here are some rationales for deviations: https://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf (Rule 5 on page 10 on malloc) https://www.keil.com/pack/doc/CMSIS/Core/html/coreMISRA_Exce...

The unit of reuse that defines the type, example: http://c-faq.com/struct/sd1.html

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#54

Post by nuclx »

felixguendling wrote: post #35

As some comments point out that this code might not be production ready, can anyone recommend other solutions that are able to manage a given block of memory? My understanding of libraries like jemalloc is that they are replacing malloc (using system calls brk and mmap [0]) but I can't hand it an already allocated block of memory to manage, right? Something like memory_manager m(some_buffer); allocation a = m.allocat…

FreeRTOS features sone nice and simple allocators on fixed buffers [0]. I have used heap4 to implement memory management for a fully portable test suite requiring malloc. Really any toy allocator would have done the job for that use-case, since performance wasn't critical, but heap4 was fairly easy to integrate.

[0] https://www.freertos.org/a00111.html

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#55

Post by Nursie »

SlowRobotAhead wrote: post #6
Nursie wrote: post #3

That's cool. I've written small but less flexible things before based on arrays as used/freed block maps rather than lists, from embedded devices with 128K of RAM. This seems like it has some nice features. Though a 3K overhead could be important in such a constrained environment (I guess if it's only managing 128k that could reduce).

3k overhead where you’re trying to reduce from malloc is definitely a lot. One of my products have 8K total, not going to waste 3 of that replacing malloc. I’m fairly happy that mirsa C forbids malloc. I can’t use it even if I wanted to, so I need to be more careful about how memory is used. Annoying at first, makes a lot of sense later on though.

> I’m fairly happy that mirsa C forbids mallo

We wrote the system I mentioned above (128K of RAM, 256K of flash) without it, I agree, you can do everything you need without malloc when you're careful.

Unfortunately we had a third party dependency that required a malloc implementation to be able to run, so we had to implement a simple one.

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#56

Post by toxmeister »

abcd_f wrote: post #20

If I read the code correctly, ta_free() is O(n), whereby n is a number of allocated blocks. That's not very good. PS. Also the block alignment is aligning the wrong thing. It should be aligning the start of the public (returned) part, not the block size and that's done by padding Block struct as required (if required)... and not to the hardcoded 8 bytes. Otherwise you'll get SIGBUS on RISC boxes. PPS. At the risk of…

Hey, author here - this post/thread completely hit my by surprise, so apols for late reply:

1) ta_free() is only O(n) if block compaction is enabled, else it's O(1), i.e. a simple cons of the freed block addr to the free list (https://github.com/thi-ng/tinyalloc/blob/master/tinyalloc.c#...)

2) there's no hardcoded alignment (it's configurable via TA_ALIGN macro) and I'm confused about your other comment about not aligning the right address in general. that's a wrong observation and i think you misunderstood the diagram in the readme.

3) it's clearly stated in the readme that this is largely meant for memory constrained situations (or where not large numbers of blocks, realloc or multithreading is needed/available) and so it's not meant to be a replacement for dlmalloc / jemalloc caliber allocators etc. i needed something small & lightweight and it did it's job very well in several production projects on the ARM STM32 platform (where I have upto around 8MB managed). I also found it very useful for some ongoing JS/WASM interop projects (i.e. there's JS version here: https://github.com/thi-ng/umbrella/blob/master/packages/mall...)

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#57

Post by toxmeister »

Nursie wrote: post #3

That's cool. I've written small but less flexible things before based on arrays as used/freed block maps rather than lists, from embedded devices with 128K of RAM. This seems like it has some nice features. Though a 3K overhead could be important in such a constrained environment (I guess if it's only managing 128k that could reduce).

The overhead is not fixed and the 3KB are only for the default config and based on the max number of blocks one might have in flight (256 by default).

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#58

Post by CyberDildonics »

okl wrote: post #53
CyberDildonics wrote: post #51

Earlier quoted context omitted.

Why would someone be doing this while trying to fit within the boundaries of the MISRA standard? Also what do you mean by module?

The rule you are referring to is a "required" (not a "mandatory") rule. You can deviate from it and still be MISRA-C compliant. People write deviations for all kinds of reasons. Here are some rationales for deviations: https://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf (Rule 5 on page 10 on malloc) https://www.keil.com/pack/doc/CMSIS/Core/html/coreMISRA_Exce... The unit of reuse that defines the type, example: h…

So your solution, in a thread about using a fixed amount of memory, is to do nothing different and let anything use the heap at any time because it might be possible in some cases to get it past MISRA standards? I'm not really sure of what you are trying to say, it seems you keep skewing further from the original discussion.

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#59

Post by SlowRobotAhead »

Nursie wrote: post #55
SlowRobotAhead wrote: post #6

Earlier quoted context omitted.

3k overhead where you’re trying to reduce from malloc is definitely a lot. One of my products have 8K total, not going to waste 3 of that replacing malloc. I’m fairly happy that mirsa C forbids malloc. I can’t use it even if I wanted to, so I need to be more careful about how memory is used. Annoying at first, makes a lot of sense later on though.

> I’m fairly happy that mirsa C forbids mallo We wrote the system I mentioned above (128K of RAM, 256K of flash) without it, I agree, you can do everything you need without malloc when you're careful. Unfortunately we had a third party dependency that required a malloc implementation to be able to run, so we had to implement a simple one.

>Unfortunately we had a third party dependency that required a malloc implementation to be able to run, so we had to implement a simple one.

We ran into the same thing. Some open source compression code I wanted to use had malloc, dumped it for something else that didn't. Luckily we found a protobuffers instance that didn't use malloc, that saved some time on a different project.

First thing I do now when looking at example or source we might want to use is a quick scan for malloc.

Re: Tinyalloc: replacement for malloc/free in unmanaged, linear memory situations

#60

Post by Nursie »

SlowRobotAhead wrote: post #59
Nursie wrote: post #55

Earlier quoted context omitted.

> I’m fairly happy that mirsa C forbids mallo We wrote the system I mentioned above (128K of RAM, 256K of flash) without it, I agree, you can do everything you need without malloc when you're careful. Unfortunately we had a third party dependency that required a malloc implementation to be able to run, so we had to implement a simple one.

>Unfortunately we had a third party dependency that required a malloc implementation to be able to run, so we had to implement a simple one. We ran into the same thing. Some open source compression code I wanted to use had malloc, dumped it for something else that didn't. Luckily we found a protobuffers instance that didn't use malloc, that saved some time on a different project. First thing I do now when looking at…

Unfortunately for us, this was a certified/approved EMV payment kernel, and about the only one we could get for our architecture, so we had to live with it.

Sometimes you don't get to choose or do it yourself, more's the pity!

Post reply on HN