[squid-dev] [PATCH] mime unfolding

[Amos Jeffries]

On 20/05/2016 5:14 a.m., Alex Rousskov wrote:
> On 05/19/2016 07:29 AM, Amos Jeffries wrote:
>> On 19/05/2016 1:59 p.m., Alex Rousskov wrote:
> 
> (A)
> 
>>>     while (!tk.atEnd()) {
>>>         const SBuf all = tk.remaining();
>>>         const auto crLen = tk.skipOne(CR); // may not be there
>>>         const auto lfLen = tk.skipOne(LF); // may not be there
>>>         if (lfLen && tk.skipAll(WSP)) // obs-fold!
>>>             result += ' '; // replace one obs-fold with one SP
>>>         else
>>>             result += all.substr(0, crLen+lfLen + tk.skipAll(notCRLF));
>>>     }
> 
> - a little too complex
> + only one expensive operation (+=) per iteration
> + elegant / symmetric / succinct
> 
> 
> (B)
> 
>>  while (!tk.atEnd()) {
>>    SBuf line;
>>    if (tk.prefix(line, nonCRLF))
>>         result += line;
>>
>>    const SBuf all = tk.remaining();
>>
>>    const auto crLen = tk.skipOne(CR); // may not be there
>>    const auto lfLen = tk.skipOne(LF); // may not be there
>>    if (lfLen && tk.skipAll(WSP)) // obs-fold!
>>      result += ' '; // replace one obs-fold with one SP
>>    else // bare-CR or CRLF
>>      result += all.substr(0, crLen+lfLen);
>>  }
> 
> - a little too complex
> - two expensive operations (+=) per iteration
> * considered clearer by some but not others
> 
> On a performance-sensitive path, (A) would have been a clear winner.
> Since we are not dealing with that path, please pick (A) or (B) given
> the factors above.
> 
> 
> FYI: The "may not be there" comments became a little misleading in (B)
> because either CR or LF has to be there now (in LF-terminated MIME), but
> I cannot suggest a better way to phrase them without making them too
> long/confusing. Not important.
> 

Perhapse, I was going to remove it on the LF. But the case you mentioned
earlier where the mime block does not end with CRLF will not have a LF
on the last cycle. It makes sense to have them all if we assume the
block being dealt with is potentially not terminated.


Just to be sure, and since I've been measuring everything about this
change I counted the loops and append()/copy too.

For my test which has 6 regular headers, one bare-CR header and one
folded 7 different ways.
* (A) cycles 24 times for its 1x copy per cycle. -> 24 copies
* (B) cycles 16 times for its 2x copy per cycle. -> 32 copies

So I tried handling the blob characters the same as crLen. That does
require an extra append() in the obs-fold path. So that the non-fold
cycles can be single-copy and the fold cycles can be double-copy.

That results in 16 cycles doing 20 copies. Better than both, at least in
terms of discreet copy/append operations.


I suspect it could be made to do even less by continuing to accumulate
across cycles. That would make it actually be doing your 1*(blob
obs-fold) syntax. But that is more complexity again and may not be
faster latency wise anyway, so so leaving it for a later commit if needed.
 e.g.:

  SBuf::size_type blobLen = 0;
  while (!tk.atEnd()) {
    const SBuf all = tk.remaining();
    blobLen += tk.skipAll(notCRLF);
    const auto crLen = tk.skipOne(CR); // may not be there
    const auto lfLen = tk.skipOne(LF); // may not be there
    if (lfLen && tk.skipAll(WSP)) { // obs-fold!
        result += all.substr(0, blobLen);
        result += ' '; // replace one obs-fold with one SP
        blobLen = 0;
    } else
        blobLen += crLen + lfLen;
  }

It is worth keeping in mind that the amount of data copied is fixed in
all these cases anyway. All that is changing is the size of the discreet
blocks moved each iteration. So the savings is by removing each cycles
stack setup/teardown overheads.


There was still danger here that a remote endpoint can craft mime blocks
to cause a series of worst-case reallocations which slow the proxy and
lower the DoS threshold. Difficulty on that is quite low.

I've put a reserveSpace() call after the clear() to prevent that
happening. Realloc should happen exactly once now no matter what the
remote end sends.


> 
>> + * \param containsObsFold will be set to true if obs-fold pattern is found. Otherwise not changed.
> 
> Please fix the "otherwise" part: A reasonable API must always set
> containsObsFold. It is trivial (and not expensive) to clear it at the
> beginning of the function, of course.
> 

Done.

> Please feel free to commit when you are comfortable with the results.
> 
> Alex.
> 

Applied as trunk rev.14677.

Thank you for the time and effort put into reviewing this.

Amos