[LTP] [RFC PATCH 1/9] lib: Add support for guarded buffers

[Cyril Hrubis]

Hi!
> >> If we have runtime free then we need to figure out which map the
> >> address belongs to or what its offset is (if any).
> >
> > That's easy, we will store the returned pointer to the map structure
> > and use it for comparsion...
> 
> So that free() is an O(n) operation where n is the number of maps or you
> will use a hash map to make it O(1)?

I doubt that we will ever allocate more than a few buffers, so it's
perfectly fine that way. Also if you keep allocating and freeing buffer
in a loop it would be at the start of the list, so it would be O(1) as
well.

The only patological case would be allocating thousands of buffers and
then freeing them in a reversed order, which would be O(n^2).

Other options would be storing the pointer to the map before the buffer,
just as malloc does, but I doubt that we will ever need that.

-- 
Cyril Hrubis
chrubis@suse.cz