[Libwebsockets] lwsac

Andy Green andy at warmcat.com
Tue Oct 16 02:54:22 CEST 2018



On 16/10/18 08:43, Per Bothner wrote:
> On 10/15/18 3:47 PM, Andy Green wrote:
> 
>> It's indeed similar, but obstacks troubles itself to track the 
>> sub-allocations
> 
> I pretty sure it doesn't - unless we're talking about different things.
> 
>> "...When all the objects in a chunk become free, the obstack library 
>> automatically frees the chunk (see Preparing for Obstacks). Then other 
>> obstacks, or non-obstack allocation, can reuse the space of the chunk. 
>> ..."
>>
>> https://www.gnu.org/software/libc/manual/html_node/Freeing-Obstack-Objects.html#Freeing-Obstack-Objects 
>>
>>
>> lwsac has literally zero overhead for aligned sub-allocations in the 
>> chunks... a million individual void * just take up the space of a 
>> million void * plus the per-chunk overhead you can control by 
>> selecting the chunk size.
> 
> Likewise with obstacks.
> 
>> There is no "objects in a chunk become free", they are allocated for 
>> the lifetime of the lwsac.  Only the lwsac itself gets freed.
>>
>> It's not as flexible as individual object malloc (obstacks, since it 
>> lets you free objects, demanding tracking overhead is just a variety 
>> of that) but for cases where you weren't going to destroy anything in 
>> this container until you were going to destroy the container, it's 
>> potentially very advantageous.  There's no per-object overhead and no 
>> destroy unwinding, plus it can grow as needed like obstacks.
> 
> Obstack's "tracking" is just the "high-water mark" of lwsac.  "Freeing" 
> an object just means adjusting the
> high-water mark to an old value - plus freeing any chunks allocated since.

I haven't looked at the obstack implementation... but if you read what 
they wrote, it does not make any restriction that objects must be 
deallocated in reverse order, or only the object last allocated in any 
chunk may be deallocated, which is what you are saying...

 >> "...When all the objects in a chunk become free, the obstack library
 >> automatically frees the chunk (see Preparing for Obstacks). Then other
 >> obstacks, or non-obstack allocation, can reuse the space of the chunk.
 >> ..."

Consider you ended up with two chunks, after 20 sub-allocations... if no 
tracking, and I "free" say objects 3, 5, 7, a naive high-water mark 
reduction per-chunk isn't going to do anything useful, is it?

In fact the user code has no idea which chunk an allocation went in, he 
can't order his frees targeting making a particular chunk having zero 
high-water mark even if he wanted to.  "Object frees" that freed space 
behind the current high-water mark for the chunk are invisible to such a 
scheme and it will fail to understand when the last allocation in the 
chunk does get freed out-of-order, that the allocations behind it were 
already freed.  That requires bloaty per sub-allocation tracking to 
follow the "holes".

Anyway lwsac was written to support a particular, intense, case that 
will be coming along presently, where you can imagine for yourself the 
effect of the bloat it's avoiding.

-Andy


More information about the Libwebsockets mailing list