[squid-dev] [PATCH] Fix maybeMakeSpaceAvailable() logic

[Alex Rousskov]

On 05/15/2016 02:50 AM, Amos Jeffries wrote:
> On 14/05/2016 9:00 a.m., Alex Rousskov wrote:
>> Another subtle maybeMakeSpaceAvailable() problem was that the code
>> contained its own buffer capacity increase algorithm (n^2 growth).
>> However, increasing buffer capacity exponentially does not make much
>> sense because network read sizes are not going to increase
>> exponentially. Also, memAllocStringmemAllocate() overwrites n^2 growth
>> with its own logic. Besides, it is buffer _space_, not the total
>> capacity that should be increased.


> This last sentence is not right. The point of having buffer limits is
> that the buffer must not grow *capacity* past those limits. Capacity can
> be partially used resulting in less space available.

I do not see anything wrong with the last sentence. The method needs to
grow space -- the callers do not care about capacity. Capacity growth is
a possible (but, depending on implementation, not _required_)
side-effect of growing space. Yes, buffer capacity limits must be
observed when growing space, of course, but that is completely unrelated
to what that sentence is talking about.


> I think you mean MemBlob capacity is not strictly aligned with buffer
> size limits. Since the MemBlob may contain data from previous reads
> which has been processed and no longer considered "in the buffer".

I did not mean that. I meant that a method allocating space should
allocate space. Its algorithms should focus on how much space is
allocated. Yes, there are other limits/concerns, of course, and they
should be met/addressed, but the code should focus on providing space,
not capacity.

The old code lacked that focus. In the extreme hypothetical example, one
can double buffer capacity while not increasing buffer space at all. If
the code is written to grow capacity instead of space such mistakes are
not that unlikely.


> What we need is that the SBuf used as a buffer should guarantee (space +
> length) <= limit, regardless of the underlying MemBlob capacity. Without
> that guarantee we end up with each read cycle simply growing the
> buffered data towards infinity as it consumes "space".

The sentence you did not like was not about obeying limits. Obeying
limits is a separate issue. I agree that they should be obeyed, and I
believe the proposed code obeys them.


> in src/sbuf/SBuf.h:
> 
> * member initializers are one of the C++11 features GCC 4.8 has trouble
> with.

When I wrote and tested this code, I was using GCC 4.8. GCC
documentation matches my experience:
https://gcc.gnu.org/gcc-4.8/cxx0x_status.html

Why do you think that GCC 4.8 has trouble with member initializers?


> +    if (!mustRealloc && spaceSize() >= req.minSpace)
> +        return spaceSize(); // the caller is content with what we have
> +
> +    /* only reallocation can make the caller happy */
> +
> +    if (!mustRealloc && len_ >= req.maxCapacity)
> +        return spaceSize(); // but we cannot reallocate
> +


> * "if (!mustRealloc && len_ >= req.maxCapacity)" looks wrong.
>  - thats igoring how much empty space it currently present

You may have missed the if-statement above it. Here they are together:


> +    if (!mustRealloc && spaceSize() >= req.minSpace)
> +        return spaceSize(); // the caller is content with what we have

> +    if (!mustRealloc && len_ >= req.maxCapacity)
> +        return spaceSize();


The first if-statement checks whether the current amount of empty space
is sufficient. When the second if-statement is evaluated, we already
know that the [!mustRealloc] caller wants more space than is currently
present.

And if buffered content size is already bigger than req.maxCapacity, the
amount of empty space becomes irrelevant. We cannot satisfy caller's
requirements and must return.


>  - capacity overflow [...] is:
>     length() + spaceSize() >= req.maxCapacity

True but irrelevant here. [ I deleted your "SBuf (not MemBlob)"
qualification to avoid discussing that controversy. ]

The if-statement you dislike does not check whether we exceed
maxCapacity _now_. It checks whether we can satisfy the caller
requirements at all. If "length() + spaceSize()" exceeds maxCapacity, we
may still be able to satisfy caller's requirements. Note that this
if-statement is located in the area of the code marked with

  /* only reallocation can make the caller happy */

and reallocation may _decrease_ space.


> * likewise the min() calculations are wrong.
>  - It will increasingly over-allocate the bigger the buffer actually
> gets.

What makes you think that? AFAICT, my code will provide idealSpace until
it hits various limits. Where do you see over-allocation?


> For non-limited SBuf that could be very dangerous in the
> int-overflow kind of way.

I do not know what you mean by "non-limited SBuf", but the allocations
are limited by the minimum of req.maxCapacity and maxSize, among other
things.


>  - Should be:
>      wantedSpace = std::min(req.idealSpace, req.maxCapacity - length());
>      reserveC..(std::min(length() +wantedSpace, maxSize - length()));

If you expand everything, my code calls reserveCapacity() with a minimum of:

* len_ + req.idealSpace
* maxSize
* req.maxCapacity

Your code calls reserveCapacity() with a minimum of:

* len_ + req.idealSpace
* req.maxCapacity
* maxSize - len_

Thus, the difference is "maxSize" vs "maxSize - len_". Your variant does
not work well. Here is one hypothetical example to illustrate the
problem with your code: If SBuf already has maxSize bytes worth of
content and mustRealloc, your code will try to reserve a zero-byte
MemBlob to hold maxSize bytes, which makes no sense. My code will
correctly ask for a maxSize buffer. SBuf::cow() will fix your mistake,
but why make ii in the first place?

Also, my bullets are very natural: What we want ideally and two limits
on our desires. Your last bullet has no meaning that I can guess.



> in src/servers/Server.cc:

> + requirements.allowShared = true; // allow because inBuf is used immediately

> * comment reason for "allowShared = true" is wrong. 

I disagree. It is actually the _only_ correct reason if there is any.


> It is allowed
> because conceptually this SBuf is the base I/O buffer the caller 'owns'
> and all others sharing are just referencing sub-sections of that.

That theoretical concept is currently _not_ supported in the code! As I
explained, inBuf is currently a random SBuf, not owned by any single
object. It may change in "unpredictable" ways at "any" time. This is
bad, but not something I am trying to change/fix with this patch.
Writing a "we own inBuf so it is OK to share it" would be dangerously
misleading today.


> * now that reserve returns spaceSize() you can simplify the pattern:
>     inBuf.reserve(requirements);
>     if (!inBuf.spaceSize())
>  to just:
>     if (!inBuf.reserve(requirements))

I know, but, IMO, the current pattern is better because it emphasizes
that we are ignoring the reserve() result [except for debugging].

Also, I am not 100% happy with the reserve() result API -- it does not
tell the caller whether the reservation criteria were satisfied. I would
prefer not to use that result for now (unless necessary) in case we
decide to change that API later as we get more use cases.


> in src/tests/stub_SBuf.cc:
> 
>  * s/reserveCapacity/reserve/  (only for the added line.)

Will fix during commit if you withdraw your other objections.


Thank you,

Alex.