4 ms·
I guess the naive solution would be to walk the freelist/tree on free() to avoid duplicates. I have no idea what the real world impact would be though. Probably
by viraptor 7y ago
I guess the naive solution would be to walk the freelist/tree on free() to avoid duplicates. I have no idea what the real world impact would be though. Probably very workload-dependent. At least checking for duplicate would be free on insert in a tree, but in a list that's both a long walk and lots of thrashing.
- gpderetta 7y agoIt would completely defeat the purpose of using a free list.
- josefx 7y agoA call to free could write a gravestone into the freed memory, each free call could check for it and only check the free list if it sees that value. This would make a check of the free list rare, especially if malloc overrides the value again.
- anon4242 7y agoHow would you know it's a gravestone? What if what you consider a gravestone is a perfectly legit byte sequence for a certain program?
- josefx 7y agoThat is the reason you check the freelist in the unlikely case that you see it, the cost would average to near nothing except for the memory accesses to set, check and clear the value. You could also xor the memory location into the marker to avoid multiple collisions for applications that allocate a large amount of similar objects.
- laughinghan 7y agoBesides, what's the minimum chunk size? Can't be less than the 64-bit word size can it? The chances of a random 8-byte gravestone appearing in legit memory is practically nil. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.
- viraptor 7y agoThats a really cool idea!
- rkangel 7y agoIt also wouldn't work at all when free space is coalesced. Memory allocations vary in size (obviously). The simplest algorithm would be to take the block of memory and start allocating chunks from the beginning. The problem is that if your app does a lot of small allocations, frees them and then wants to do a large allocation, the free list might not contain a block large enough. The job of your allocator is to manage that fragmentation. There are a lot of approaches, but fundamentally at some point it has to put two deallocations 'back together' to make a larger one. If you free a chunk, and then that chunk is coalesced with some data just before it, then the free list will no longer contain a pointer that matches the one that you then try to double free.
- viraptor 7y agoI get that, but I believe this issue doesn't apply in this case (I could be wrong of course). Specifically this double-allocation seems to come directly from a freelist for a specific allocation size. Going with the description from the link I posted about the allocator, this exploit should work only if the freed space is not coalesced - otherwise you wouldn't be guaranteed that the same memory is returned twice.
- Someone 7y agofree on insert in a tree isn’t really free, as the only reason to replace insert in a list by insert in a tree would be this check. I think it also would make the memory manager less cache-friendly, as reusing just freed memory blocks would be impossible.