[Libwebsockets] lwsac

Per Bothner per at bothner.com
Tue Oct 16 03:29:40 CEST 2018

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."


> or only the object last allocated in any chunk may be deallocated, which is what you are saying...

No, that is not a restriction.

> 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.
> 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.

However, I do suggest adding a note like:
   Lwsac is variant of the [obstack](https://en.wikipedia.org/wiki/Obstack) data structure.
   GNU [obstack](https://en.wikipedia.org/wiki/Obstack) is an older implementation of a similar idea.
	--Per Bothner
per at bothner.com   http://per.bothner.com/

More information about the Libwebsockets mailing list