[Libwebsockets] lwsac

Andy Green andy at warmcat.com
Tue Oct 16 03:50:59 CEST 2018

On 16/10/18 09:29, Per Bothner wrote:
> On 10/15/18 5:54 PM, Andy Green wrote:
>> 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,
>      "To free an object allocated in an obstack, use the function 
> obstack_free. Since the obstack is a stack of objects,
>      freeing one object automatically frees all other objects allocated 
> more recently in the same obstack."
> (https://www.gnu.org/software/libc/manual/html_node/Freeing-Obstack-Objects.html) 
>> or only the object last allocated in any chunk may be deallocated, 
>> which is what you are saying...
> No, that is not a restriction.

IIUI, it actually is.

>> 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?
> Freeing object 5 will automatically free objects 6-20 as well, and 
> possibly one of the chunks.
> You can later call obstack_free on object 3 - but a reference to object 
> 7 would be a dangling pointer,
> and so calling obstack_free on object 7 would be invalid.

I guess this is why it's a "stack"... you can basically pop yourself 
back to an earlier state freeing everything inbetween.  But as I say 
"only the object last allocated in any chunk may be deallocated" (along 
with as many others as you like) then...

>> 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".
> There are no holes in an obstack (except unused space at the end of a 
> chunk or due to alignment).
>> 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.
> Which is cool. You might not want to use obstacks for licensing reasons 
> (LGPL), anyway.

I already wrote my own implementation from scratch, including the 
conception... I don't need obstack.

> However, I do suggest adding a note like:
>    Lwsac is variant of the 
> [obstack](https://en.wikipedia.org/wiki/Obstack) data structure.

Eh... while I'm happy to acknowledge it pre-existed what I wrote...

> or:
>    GNU [obstack](https://en.wikipedia.org/wiki/Obstack) is an older 
> implementation of a similar idea.

... I never even heard of it until you mentioned it thismorning.  It's 
simply a case of a good idea getting evolved again independently.

I certainly owe Stallman, GNU for GCC and their other work, but I don't 
owe this any special acknowledgment.


More information about the Libwebsockets mailing list