[squid-dev] [PATCH] Http::Stream ID numbering

[Amos Jeffries]

On 4/02/2016 4:40 a.m., Alex Rousskov wrote:
> On 02/03/2016 04:29 AM, Amos Jeffries wrote:
>
>>>>> Pipeline class is updated to use the ID number to manage its contents
>>>>> rather than Pointer value matching. It is also updated to drop the
>>>>> HTTP/1 specific assumptions within the Pipeline implementation. As a
>>>>> behavioural requirement the sequential flow is now left for the Server
>>>>> and ClientHttpRequest Jobs to ensure correctness.
>>>>
>>>>
>>>> The new Pipeline::popById() method is a bad idea IMO: Linear search is
>>>> wrong for both HTTP/1 and HTTP/2.
>>>>
>>>
>>> Do you have a better algorithm? it needs to pop using only an ID (HTTP/2
>>> limit due to framing) and works on linear/list storage (optimal for
>>> HTTP/1 sequentialism).
> 
> I am sure I can create a solution, but I was hoping to avoid doing that.
> I can start by suggesting that if what you are saying is true, then you
> probably need to either

I mean algorithm, if you can name one I can look up that would be fine
and I investigate using it as opposed to search. What I've used is the
best I can think of so far.

The use-case is to process a new HTTP/2 frame arriving and associate it
to the stream. So a map might work, but would grow to perhapse 2^32
entries unless we could also find a good way to purge entries. With only
a small / limited number active at any time the search/walk should be
"fast enough" and is replaceable if that better algorithm appears
tomorrow or next year.


> 
> * configure Pipeline to use one of the two different storage structures
> with the same API (optimal but often more difficult to design right) or
> 

This is kind of the direction why I picked list as the type for Pipeline
to begin with. std::queue is apparently implemented as a std::list with
cutdown API in the first place.

Going with just std::list then HTTP/1.x can use it as if it were a
strict FIFO queue, while HTTP/2 can use it as a list very roughly
"sorted" by priority (aka. FIFO but not a strict queue access ordering).

Since the API type is a list, the Server class is made responsible for
implementing the right semantics on the pipeline. For example;
HTTP/1.x-only logics not doing a walk unless its by repeatedly
pop()'ing, etc.

>
> For the first bullet, please note HTTP/1 can internally do a
> simple/efficient "pop(void)" and only then check the popped ID, even
> though its public API can be exactly the same "removeById()" API used by
> HTTP/2.

Sounds okay. I will look at adding that with version indicators in the
method docs so we can see the dual-API separation and see how that goes.


> * always use one Pipeline storage structure with two indices (worse
> performance, more RAM, and messier code but possibly easier to shovel
> into Squid).
> 
> BTW, "Pipeline" does not sound like the right name for a class managing
> mostly independent components each of which can be removed at any time
> without significant effect on others (as is the case with HTTP/2 streams).

"pipeline" is the RFC term for the set of transactions sent/received on
a single connection, so I went with the flow. (pun intended, have a nice
day).

Amos