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

41–50 of 60 posts

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

#41

Post by monocasa »

CyberDildonics wrote: post #37
monocasa wrote: post #29

Earlier quoted context omitted.

Yeah, but it's nicer to define that kind of stuff in your linker script IMO, where sizes of large memory regions can be thought of holistically.

The parent post was talking about using malloc once at the start of the program, are you talking about defining that with your linker script? Also if the goal is to get one chunk of memory with a single call, why use malloc at all? Why not use the direct memory mapping command?

I don't think he's talking about using malloc "once", he's talking about only using it during init. In practice you end calling it a bunch in that model, the last design I shipped like that ended up making a few hundred malloc (well new operator because this was C++) calls at init.

Under that system malloc/new was just a pointer bump, and an assert if there wasn't enough room. Free wasn't linked, and delete asserted. That heap region (or mine had several heaps that lived in different memory with different characteristics that could be specified with a new overload) is way easier to define in your linker.

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

#42

Post by ksherlock »

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…

SQLite memory system 5:

https://www.sqlite.org/src/artifact/9bf955937b07f8c3

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

#44

Post by smileypete »

If handles and setters/getters can be used, then it opens up the possibility of defragging or 'garbage collecting' the memory.

A neat trick could be to be able to 'trim' the data used by the handle, then when it comes to defrag time just deal with the remaining part and free up the trimmed space.

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

#45

Post by Const-me »

okl wrote: post #7
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).

That concept is called a memory pool or storage pool. Very useful, but their greatest disadvantage compared to malloc() is that you waste a lot of memory if your allocation size varies greatly (for example a network protocol where packet size can range from few bytes to KB).

In my experience, best way to implement a network protocol on a small embedded chip is fixed length statically allocated circular buffer, not malloc.

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

#46

Post by zik »

howard941 wrote: post #43

How does it stack up to dlmalloc?

It's a tiny allocator designed for tiny embedded systems. It's not intended for large desktop machines like dlmalloc() is. dlmalloc() can't run on tiny embedded systems because it has relatively high overhead. This provides a lot less features but has a very small memory footprint. It's really intended for cases where your embedded program mostly allocates memory once on startup and doesn't usually free() much at all.

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

#47

Post by dividuum »

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…

This TLSF implementation should be able to do that: https://github.com/mattconte/tlsf

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

#48

Post by okl »

Const-me wrote: post #45
okl wrote: post #7

Earlier quoted context omitted.

That concept is called a memory pool or storage pool. Very useful, but their greatest disadvantage compared to malloc() is that you waste a lot of memory if your allocation size varies greatly (for example a network protocol where packet size can range from few bytes to KB).

In my experience, best way to implement a network protocol on a small embedded chip is fixed length statically allocated circular buffer, not malloc.

That would be like a "first-fit-or-die" malloc, wouldn't it? Which mechanism to choose always depends on your (de-)allocation profile and available memory. If you can free out-of-order, the circular buffer will fragment quickly.

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

#49

Post by Const-me »

okl wrote: post #48
Const-me wrote: post #45

Earlier quoted context omitted.

In my experience, best way to implement a network protocol on a small embedded chip is fixed length statically allocated circular buffer, not malloc.

That would be like a "first-fit-or-die" malloc, wouldn't it? Which mechanism to choose always depends on your (de-)allocation profile and available memory. If you can free out-of-order, the circular buffer will fragment quickly.

> If you can free out-of-order, the circular buffer will fragment quickly.

Right, just when coding a network protocol for embedded, often you can free in the same order, i.e. it’s often a good idea to limit parallelism to a small number of FIFO streams (ideally a single one).

That’s only for small chips. When they aren’t small e.g. you have a quad-core ARM with a gig of RAM you usually have OS anyway and the programming is totally different, much higher level and you guaranteed to have a fast malloc and lots more.

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

#50

Post by srcmap »

Unklejoe wrote: post #11
srcmap wrote: post #9

Earlier quoted context omitted.

Did similar implementation 15 years ago. I needed a implementation that works in SMP environment and it didn't use lock. I use atomic increment to allocate block index, atomic dec to free the block index. It worked very well with good performance in SMP environment. It was implement as share library and the same code can be link statically in the kernel module. Linux Kernel can allocate the block and pass the pointer…

Cool. How did you deal with the case where a block gets freed out of order? For example, Thread1 allocate (block index++) Thread2 allocate (block index++) Thread1 free (block index--) Thread3 allocate (block index++) Now thread 3 has a block that is actually still owned by thread 2.

The blocks were actually fix in pre-allocated blocks.

When a thread, process, kernel thread "allocated" a block. It actually acquired and owned the "index" via atomic inc from the free list.

When it free the block, it put the block's index back to the "free" list.

The "free" list is actually a array. Thus the list index can be allocated and free with atomic inc, dec. Thus it can do SMP safe alloc, free operations without any locks and guarantee the correctness.

This was actually a IPC, DIPC library to support TCP session redundancy in a network router product. Other programmers call this library from user, kernel and TCP stack, etc.

Since the blocks and index are all in share memory, there are huge potential for share memory corruptions. In debug mode, there are memory space before and after each block, every allocate, free are checked for ownership, double free, and border space corruption. There are regression tests to cover all aspect of API calls that were run 24/7 check for every commit. When not compile with debug mode, the operations were much faster but there were still quite a bit of assertions check in place.

There were a debug trace system that track all system activities (including Linux, QNX, vxwork context switches.) The log is actually in special region of memory that preserved over warm boot. If the system was completely hang, in 99% of cases, I can recover the memory to do post mordem analysis and know exactly the last user, kernel space threads that were running before the system crash. It was more useful for vxWork, less useful for Linux as majority of code were in user space and didn't take down the system.

The regression test coverage code and the debug mode validations were 80% of code. The actually implementations were very small.

Post reply on HN