Reduce the complexity of WebSocketThrottle's wakeup code

Reduce the complexity of WebSocketThrottle's wakeup code

Currently, job removing code and wakeup code are separate.

With the wait queue algorithm employed by WakeupSocketIfNecessary, we
have O(N^2 log N) total complexity for shutting down all pending jobs.
So, it can make IO thread busy for long time. To prevent such situation
occurring for bogus web app,
- integrate wakeup code into job removing code so that we can build a
  list of wakeup candidates from removing process and check only jobs
  in it. Total complexity for shutdown will then be O(N log N)
- have some reasonable limit for the maximum number of WebSocketJob
  instances pending in the WebSocketThrottle.

The number of WebSocketJob instances pending in WebSocketThrottle will
be limited up to 1k.

Also, the number of active SocketStream instances should be limited.
When huge number of WebSocket instances are created, it pressures the
browser process. It'll be limited up to 16k.

BUG=259005
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=212235

[szym, 2013-07-11 17:00:07]

The correct solution is to fix the O(N lg N) complexity in Wakeup (assuming map
lookups take logarithmic time). Right now, shutdown can take O(N^2 lg N) time,
so setting N = 16k is not going to fix it.

Ignoring tests, WakeupSocketIfNecessary is called only immediately after
RemoveFromQueue.

The logic of Wakeup could be integrated into Remove so that it's only O(1)
amortized.

When deleting the |address_queue_iter|, check if it's the front, and if so, take
the new front and if it's waiting, save it in a set of jobs to wake-up.

This way the worst-case Remove is still O(lg N) and total shutdown time is O(N
lg N).

[yhirano, 2013-07-12 02:03:10]

Can you write a unittest for too many pending jobs?

[tyoshino (SeeGerritForStatus), 2013-07-12 05:44:38]

On 2013/07/11 17:00:07, szym wrote:
> The correct solution is to fix the O(N lg N) complexity in Wakeup (assuming
map
> lookups take logarithmic time). Right now, shutdown can take O(N^2 lg N) time,
> so setting N = 16k is not going to fix it.

It's 1k.

> 
> Ignoring tests, WakeupSocketIfNecessary is called only immediately after
> RemoveFromQueue.
> 
> The logic of Wakeup could be integrated into Remove so that it's only O(1)
> amortized.
> 

Thanks for the suggestion. If we do so, we'll ignore the original ordering
between B and C e.g. for the following case.

q for resolved address x: address A, address B
q for resolved address y: address A, address C

When A goes away, B and C will be queued into the set of jobs to wake-up. But
without checking their position in queue_, we cannot guarantee FIFO model.

But it's not a big problem. Everything moves forward so it doesn't cause any
starvation. So, I'll take this approach.

> When deleting the |address_queue_iter|, check if it's the front, and if so,
take
> the new front and if it's waiting, save it in a set of jobs to wake-up.
> 
> This way the worst-case Remove is still O(lg N) and total shutdown time is O(N
> lg N).

[tyoshino (SeeGerritForStatus), 2013-07-12 05:44:45]

On 2013/07/12 02:03:10, yhirano wrote:
> Can you write a unittest for too many pending jobs?

done

[yhirano, 2013-07-12 09:00:15]

I have an elementary question.
Can dead-lock occur in this algorithm?

If jobA precedes jobB in addressX and jobB precedes jobA in address Y, they seem
never be waken up.
Is there such a case?

[tyoshino (SeeGerritForStatus), 2013-07-12 10:59:22]

On 2013/07/12 09:00:15, yhirano wrote:
> I have an elementary question.
> Can dead-lock occur in this algorithm?
> 
> If jobA precedes jobB in addressX and jobB precedes jobA in address Y, they
seem
> never be waken up.
> Is there such a case?

Good question but it never occurs. Addition to queues is serialized, and all
per-address queues are also FIFO. So, if jobA is put to WebSocketThrottle
before jobB, for all per-address queues, jobA precedes jobB.

[szym, 2013-07-12 15:31:05]

LGTM!
Don't forget to update CL description.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_job_unittest.cc (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_job_unittest.cc:985: if (i ==
kMaxWebSocketJobsThrottled)
suggest >=

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.cc (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.cc:100: was_front = per_address_queue_iter ==
per_address_queue->begin();
suggest parentheses

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.h (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:45: // of |job|, and then wakes up jobs that
are now resume establishing a
fix grammar, I think "are" => "can"

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:60: // job can resume establishing a
connection, so wakes up the job.5D
5D?
:)

[jochen (gone - plz use gerrit), 2013-07-12 19:45:27]

lgtm

[yhirano, 2013-07-16 02:08:56]

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.cc (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.cc:61: } else {
DCHECK(!iter->second->empty()) would be helpful.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.h (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:51: typedef std::map<IPEndPoint,
ConnectingQueue*> ConnectingAddressMap;
Can we use std::map<IPEndPoint, ConnectingQueue> instead of std::map<IPEndPoint,
ConnectingQueue*> ?

[tyoshino (SeeGerritForStatus), 2013-07-17 06:58:26]

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_job_unittest.cc (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_job_unittest.cc:985: if (i ==
kMaxWebSocketJobsThrottled)
On 2013/07/12 15:31:05, szym wrote:
> suggest >=

Done.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.cc (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.cc:61: } else {
On 2013/07/16 02:08:56, yhirano wrote:
> DCHECK(!iter->second->empty()) would be helpful.

Done.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.cc:100: was_front = per_address_queue_iter ==
per_address_queue->begin();
On 2013/07/12 15:31:05, szym wrote:
> suggest parentheses

Done.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
File net/websockets/websocket_throttle.h (right):

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:45: // of |job|, and then wakes up jobs that
are now resume establishing a
On 2013/07/12 15:31:05, szym wrote:
> fix grammar, I think "are" => "can"

Yes, thanks. Done.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:51: typedef std::map<IPEndPoint,
ConnectingQueue*> ConnectingAddressMap;
On 2013/07/16 02:08:56, yhirano wrote:
> Can we use std::map<IPEndPoint, ConnectingQueue> instead of
std::map<IPEndPoint,
> ConnectingQueue*> ?

Done.

https://codereview.chromium.org/18932005/diff/15001/net/websockets/websocket_...
net/websockets/websocket_throttle.h:60: // job can resume establishing a
connection, so wakes up the job.5D
On 2013/07/12 15:31:05, szym wrote:
> 5D?
> :)

oh!

[yhirano, 2013-07-17 07:21:21]

lgtm

[tyoshino (SeeGerritForStatus), 2013-07-17 07:24:25]

On 2013/07/12 15:31:05, szym wrote:
> LGTM!
> Don't forget to update CL description.

Yes. It's up to date and explaining the algorithm optimization change.

[commit-bot: I haz the power, 2013-07-17 07:26:35]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/tyoshino@chromium.org/18932005/39001

[commit-bot: I haz the power, 2013-07-17 07:59:21]

Sorry for I got bad news for ya.
Compile failed with a clobber build on android_dbg.
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=android_db...
Your code is likely broken or HEAD is junk. Please ensure your
code is not broken then alert the build sheriffs.
Look at the try server FAQ for more details.

[commit-bot: I haz the power, 2013-07-17 19:36:14]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/tyoshino@chromium.org/18932005/63002

[commit-bot: I haz the power, 2013-07-17 20:38:03]

Step "update" is always a major failure.
Look at the try server FAQ for more details.
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_rel&nu...

[commit-bot: I haz the power, 2013-07-17 22:08:23]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/tyoshino@chromium.org/18932005/63002

[commit-bot: I haz the power, 2013-07-18 04:02:05]

Change committed as 212235