TLSFMem O(1) Memory Allocator

[platon42]

TLSFMem is an implementation of a very new memory allocation system called TLSF (two level segregated fit). TLSF was described in a paper in 2005 by the three italian researchers M. Masmano, I. Ripoll, A. Crespo. Originally designed for Realtime Operating Systems, all allocation and free operations run with constant time complexity (O(1)). This is a major improvement over the original AmigaOS memory system, which gets slower while memory gets fragmented (O(m) where m is the number of fragments).

Moreover, the old AmigaOS allocator uses a first fit strategy, which causes the memory to fragment pretty quickly. TLSF is an exact fit allocator for memory blocks smaller than 512 bytes and a good fit allocator for all other sizes: It will always find a free block which is always smaller than 103% of the requested block.

TLSFMem is blindly fast and will reduce memory fragmentation significantly!

TLSFMem was written in optimized assembly language, but more importantly, it uses these clever constant time algorithms.

This software comes as freeware, but as I spent a lot of time in developing it, you are welcome to donate something.

Download it here.

Chris Hodges

[platon42]

@ChrisH

I disagree with this, and most likely would disagree with the magical O(1)
claim of this new allocator too (once I get around to reading how it
works). In OS4's case, you only get O(1) performance if there is a mix of
allocations & deallocations, otherwise you'll likely get O(n) performance
(but should get O(log(n)) performance if they changed the
implementation).)

You get O(1) guaranteed for each single operation (except for AllocAbs,
which will likely be O(1)). Not O(n), not O(n log n), but O(1). Worst
case. Every case. No mix of operations needed. There are no loops in the
code (except for looping over the existing memory headers, see docs for
detail).

Regarding the "inefficiency" of 103% is about the good fit properties, it
doesn't waste memory (but I don't know about the OS4 allocator).

[platon42]

> But is it any better than MemOptimizer?
> Or Poolmem?

Yes.

[platon42]

> Is there any way to rewrite MuForce, MuGuardianAngel, MungWall, etc. to work with the new ChrisHodges(tm) TLSF patch?

MuForce magically seems to circumvent the patches (calling the original ones (however it gets their pointers)), and thus will immediately cause havok on attempting to free TLSF allocated memory.

> I dont see any reason why MuForce and MungWall wouldnt work with this utility.

MungWall trashes the freed memory, but TLSF stores administration data in the freed memory. I still could add intrinsic MungWall functionality to TLSFMem.

[platon42]

> Hey, do you think that this bug could explain the (urg!..) partition trashing experiences that i had with PoolMem and AllocP?? (No problems with MemOptimizer, so far)
> What are the expected consequences of this? I do know that you provide a bug-fix, but i still would like to know.

Could be a result indeed. Whatever application gets access to this memory by allocating it first and using it could cause all kind of weird behaviour -- and as the important pointers (io_Data, io_Offset and io_Length) are in the back part of the structure, partition trashing could occur.

> Oh, another (important, i believe) question please: Many ppl like me are using the IDEFix package which patches/replaces the standard scsi.device. What's the case with this one? Is there a need for a fix? Which one from the ScsiBugfix directory?

I don't think that the idefix drivers are derivates from the Commodore ones, hence they should not have this bug.

[platon42]

> Forgive me for being a bit dense, but I don't quite get it. What does this do to my system? Would I be correct in thinking that it makes memory access faster? Significantly?

It doesn't speed up memory access -- this is hardware bound. But programs that use the exec memory functions for reserving and freeing dynamic memory will benefit from the new routines. Significantly.

For example, when I run my backup script on my harddisk, which will use lha to scan a partition with >80000 files, it will create over 5000 memory fragments of 8 bytes size. This sucks and makes my system *crawl*. In the past, I just called AllocFrags at regular intervals which will remove the 8 byte fragments, but after the backup process, my memory is a piece of swiss cheese (and lha needs about a minute to release its memory).

With TLSFMem, this fragmentation is gone and will speed up these tenthousands of memory operations significantly.

[platon42]

> Are the sources included in the archive?

No. I don't think that ~2000 lines of 68k-asm would be helpful for AROS either. There is that paper and at least two open source implementations of TLSF in C on the internet.

[platon42]

> But I don't see how that will happen when it can't be run with debugging software such as MuGuardianAngel.

Well, developers will usually have their "debugging setup". I'm not running MuGuardianAngel during the normal system operation

> What can we do to make MuGuardianAngel cooperate with TSLFMem?

MuGuardianAngel *replaces* the exec.library functions, just as TLSFMem does. But as it does, it will bork because the old memory headers are nearly empty (thus no free memory) and a free memory check on the TLSF memory headers will cause a (recoverable) guru, because it doesn't contain any chunks, but the MH_FREE field is not 0. Also I would expect MuGuardianAngel to return MMU page aligned allocations to protect them from harm -- this is currently not supported in TLSFMem.

[platon42]

But the "good fit properties" of 103% means that it uses (up to) 3% more memory than necessary, so it *is* an inefficiency. OS4 has a similar wastage of (up to) 12.5%. BTW, the proper name for this is "internal fragmentation", unless I misunderstand you.

No, thats exactly NOT what it means. Good fit means that *if* there is a memory block of at least that size category, it will find it in O(1) -- otherwise the next bigger block is returned (also in O(1)). If the sizes are exactly the same, it will allocate and eat it, if the free block was bigger, it will split it accordingly AND NO MEMORY IS WASTED. The 103% only means that a "size category" is between 100% and 103% of the requested size, and it will not distinguish between a set of different free blocks within a category. I suggest to have a look at the paper describing TLSF.

Good fit means, that it will find a free block that will have a size /close/ to the requested block. Best/Exact fit would mean, the algorithm had to search *all* the free memory chunks for a block that fits exactly.

In any case, if there's only bigger chunk of free memory than requested, the memory block is split. And the remaining block is still available to the system. No memory is wasted.

Thus TLSFMem does not have internal fragmentation except for its alignment and allocation sizes need to be multiples of 16. If the OS4 allocator has internal fragmentation and if it's really up to 12,5%, it sucks.

[platon42]

For my own (very old) FolderSync program, I was able to gain a 70 times speed-up by writing my own custom memory allocation system. The reason is that (a) AmigaOS 3.x has a very old & slow memory allocation system, and (b) FolderSync made very many (small) memory allocations.

Isn't that what memory pools, introduced with OS 2.0 is for? Small allocations, pooled into puddles? Unfortunately, there are still programs, that don't use them, way past the OS 2.0 release date...

[platon42]

I have found a serious problem with your patch:
Every WOS and PUP progs i have tried so far, refuses to work when TLSFMem is installed.

So.. Is there anyone with a PPC board who confirms this?

Seems to be true. I guess PUP and WarpOS have their own allocation routines for PPC, which are of course not patched with TLSFMem, and as TLSFMem grabs most available memory, they will at least suffer from "out of memory" problems.