Channel Patch

[Chris Rapier]

Damien Miller wrote:

> Before you go any further with this diff, please understand that it 
> almost no chance of being incorporated unless it follows the 
> style of the existing code[1].

That is understood. These aren't being put forward as actual patches for 
consideration for inclusion at this time. Its really just research at 
this point as I'm not sure it actually has any real merit to it in terms 
of performance. As such, I didn't want to develop this in a vacuum and 
wanted to get community insight on it.

Basically, in the course of other work I ran ssh/sshd against a profiler 
(oprofiler) and found that in some operations a lot of time was being 
spent in the channel_handling code. My hope was that by reducing the 
amount of time spent there more resources would be freed up for other 
operations.

> We also prefer to use the queue[2] macros instead of hand-rolled
> linked list implementations, though I'm not sure that a linked list is
> the right data structure (remember you need to support by-id lookups
> too), whether you need to change the data structure at all or whether
> traversing an array of a few dozen elements is worth optimising.

Which is, for the most part, the question I'm trying to answer with 
this. After some playing around with things I'm not sure if its that 
there is no merit to the idea of limiting the looping or if my code just 
sucks :)

> It seems you could avoid most of the channel array scans by simply
> tracking the number of channels actually used and stopping the loop
> after seeing that many open channels (this would work very well unless
> the entries were fragmented across the array).

Thats the problem that I was trying to avoid with the linked lists. From 
the code it seems that channels can be added to or removed from the 
channels array arbitrarily. In the first iteration of the patch I simply 
  compacted the array and broke the loop at the first null. This worked 
but it seemed to be somewhat limiting - I still needed all of the test 
statements and I had to make changes to the data in the channel struct - 
which is something I wanted to avoid doing. By moving to a linked list I 
was able to avoid that but I lost the ability to do an index lookup on 
the array (as you mentioned). I was able to addresses that but it does 
necessitate looping through the linked list. So I'm not sure how much a 
win it would be. Depends on how frequently the function is called. I'll 
look at the queue macros. Thank you for the pointers.

Actually, thinking a bit more about it I do think I'll try your 
suggestion. It won't help in every situation but I think it will in a 
significant percentage of them. In the remaining situations it shouldn't 
impose a penalty.

> If you wanted to be
> tricky, you could add a precomputed skip step to the channels array that
> would point to the next allocated channel, allowing the loop to skip
> past unused channels.

One thing I'm not is tricky. I always end up confusing myself. Mostly I 
just write this stuff as research projects in the hope that it interests 
someone else enough to actual code things properly :)

> -d
> 
> [1] http://www.openbsd.org/cgi-bin/man.cgi?query=style&sektion=9
> [2] http://www.openbsd.org/cgi-bin/man.cgi?query=queue&sektion=3