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

11–20 of 60 posts

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

#11

Post by Unklejoe »

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

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.

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

#12

Post by benj111 »

lbj wrote: post #5

Its a nifty tool, but I can't help feeling a little disappointed that we're still having to deal directly with issues such as memory allocation in 2019.

You don't necessarily.

Don't forget that theres memory managed languages that compile to c. They still use malloc under the hood.

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

#13

Post by okl »

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.

Freeing is usually easy (for free() and memory pool) because the pointer can be used to compute the index into the bool array or bitfield. Allocating is more difficult since you have to search. You can use a linear search that starts at the last block that was allocated (for memory pools that's usually good enough). You can also use a bloom filter to accelerate the search. Example:

256 blocks of memory, you use 8 words of 32 bits to to indicate used/free status. 1 means free, 0 means occupied. To quickly find a free block you compare the words with zero.

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

#14

Post by CyberDildonics »

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

It is quite possible (and it can be reasonable) to deviate from that rule. For example you could write a wrapper for malloc that only allows dynamic allocation in the initialization phase of your program. This can be useful to allocate memory for opaque-pointer-style types.

There are other ways to get chunks of memory separate from the stack - static uninitialized byte arrays.

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

#15

Post by okl »

CyberDildonics wrote: post #14
okl wrote: post #8

Earlier quoted context omitted.

It is quite possible (and it can be reasonable) to deviate from that rule. For example you could write a wrapper for malloc that only allows dynamic allocation in the initialization phase of your program. This can be useful to allocate memory for opaque-pointer-style types.

There are other ways to get chunks of memory separate from the stack - static uninitialized byte arrays.

Of course, but then we are back to memory pools.

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

#16

Post by asveikau »

lbj wrote: post #5

Its a nifty tool, but I can't help feeling a little disappointed that we're still having to deal directly with issues such as memory allocation in 2019.

Somebody's got to deal with it so that you may have the luxury of not dealing with it.

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

#17

Post by blattimwind »

chrisseaton wrote: post #10
lbj wrote: post #5

Its a nifty tool, but I can't help feeling a little disappointed that we're still having to deal directly with issues such as memory allocation in 2019.

How do you think we should be dealing with memory allocation instead?

    addr = getrandom(8);
    mem = mmap(addr, len, PROT_RWX, MAP_FIXED|MAP_ANON, -1, 0);

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

#20

Post by abcd_f »

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 stating the obvious, this is nothing more than a toy allocator, with lots of loose ends. A lab exercise in a second-third year of an average CS course - maybe, but this is not something suitable for production. Perhaps it works for some specific cases, but these aren't specified. So seeing this massively upvoted and at the top of HN is a bit strange.

Post reply on HN