819734 - Token Bucket for Network Bursts

Status: RESOLVED FIXED

(Core :: Networking: HTTP, enhancement)

Description

[Patrick McManus [:mcmanus]]

A network trace of a highly sharded site, like pinterest, shows large runs of of both SYNs and then later on GETs that are all sent simultaneously.

The ethernet/wifi driver is going to place those packets on the 'wire' as quickly as it can serialize them and when they hit the cable-modem (or equivalent) that steps down the upstream bandwidth from LAN speeds to ISP-upstream speed a queue will form. At some point we're going to overflow that queue and you can see from the linked bugs exactly that happening (packet loss requiring handshakes and requests to be resent).

By smoothing that data out a little bit (allowing a burst but bounding it, and then pacing the remainder of the flight) we ought to be able to shift the queueing into the browser and get better network behavior. I'd suggest we start by trying to subject SYNs and HTTP request headers to this.

Its worth experimenting with anyhow - I don't expect we would actually need to delay things very long in terms of pacing beacuse the problem is one of instantaneous queue size and that queue will empty fairly quickly. This should also have the symmetric (and desirable) property of smoothing out when the reply data arrives (which can also induce loss with itself).

Comment 1

[Patrick McManus [:mcmanus]]

I've been able to improve the pinterest.com/all usecase, which suffers from this problem, subtantially without appearing to impact other use cases which rely on the extreme parallelism without causing as much packet loss. (i.e. sites transferring smaller files, or using smaller congestion windows).

I can improve it a bit further by rate limiting things more aggressively, but that tends to impact the other (no congestion) use cases negatively. Perhaps 813715 can help some more in those cases without incurring a big tradeoff.

My rate limiter has 3 parameters - burst, hz, and min-parallelism.

Min-Parallelism is the amount of active connections that have to be in use in order for the rate limiter to be used.. i.e. a min-parallelism of 6 means we'll never delay a transaction if less than 6 other transactions are in current flight regardless of how many transactions we have processed lately (i.e. regardless of rate limiter semantics).

Burst - If you conceptualize the rate limiter as a token bucket that fills with tokens as time passes (at the rate of hz) then burst is the maximum number of tokens the bucket can fill to. It starts full. A burst of 32 essentially means a token bucket will admit the first 32 transactions immediately even if they are all presented to it instantaneously - additional transactions will be admitted at the hz rate. Pages with less subresources than the burst are essentially not impacted by the rate limiter.

Hz - the rate at which the token bucket earns credits and therefore the rate at which transactions are admitted once the bucket is empty.

After fussing around with a lot of values, burst=32, hz=100, min-parallelism=6 do pretty well.

The use case is pretty extreme - 128 parallel connections are typically made, many carrying significantly sized images, and using a CDN that is configured for IW=10. That results in a lot of chaos on the wire.

This is the breakdown for pinterest.com/all from my desktop using that configuration.

Percentile      DOMInteractive (1/10s)    DOMComplete (1/10s)
25th                   12                       60
50th                   15                       67
75th                   17                       69
90th                   19                       70

This is the same testcase using the nightly my patches are based off of

Percentile      DOMInteractive (1/10s)    DOMComplete (1/10s)
25th                   12                       75
50th                   14                       97
75th                   16                       112
90th                   17                       124

The first thing to notice is that DOMInteractive isn't helped.. it looks hurt, but I think that's just noise in this case.. I say that because the blocking elements of the head (the js and css) are excluded from the rate limiter explicitly and from staring at these traces the HTML has a pretty significant and variable "think time" of up to several hundred miliseconds that the other resources on this page don't see (probably database load.) So there really is no basis to expect anything to change.

But you can see that DOMComplete benefits greatly. And there is more than that.. it just feels better. Its probably something that the webpage.org speed index might capture, but I don't have a good metric for.. the page simply appears loaded even faster because we are loading the stuff above the fold reliably earlier.. i.e. we are loading the right stuff.

It took me a minute to figure out why that is, but I think its driven by the large amount of sharding going on for this page. Normally (i.e. with the release channel) we will just load pretty much all of these objects in parallel because they use so many different hostnames.. technically they get loaded in appearance order of the html, but in practice because there is no queuing with all the sharding they get loaded from the network basically in parallel.. so the stuff at the top is sharing bandwidth with the stuff at the bottom and when losses occur they appear more or less randomly to various objects.. but when we shift the model to rate limiting, some queuing is reintroduced a clear preference is given to the objects at the top of the page.. which gives a much better feel to what is going on. I really wish I had a metric I could apply to that.

I've run my benchmark against other sites that rely on sharding for performance.. flickr, etsy, facebook, usmagazine.. none of them appear to be harmed and flickr in particular seems to benefit (again, it is sharding with large data items instead of small thumbnails and such). I can see some harm if I make the rate limiter doubly as aggressive.

I had hoped to be able to validate this a little further using stoneridge, but it doesn't look like its quite ready for that kind of complexity yet. Instead I guess I'll have to devise some kind of A/B test instead of just checking it in - though its always hard to figure out if the data is really comparable or not because of url/cache diversity and how to control for that.

I guess this should have been a blog post :) - I'll do that too (eventually).

Comment 2

[Patrick McManus [:mcmanus]]

Attachment: patch 0

This needs more testing and a better evaluation framework - but the patch represents the core of the actual implementation. I'll post it in case comments are in order.

Comment 3

[Patrick McManus [:mcmanus]]

Attachment: patch rev 1

Comment 4

[Patrick McManus [:mcmanus]]

Attachment: abtest rev 1

The base patch was posted pref'd off.

This is a followon patch that
 1] prefs it on in nightly and aurora
 2] adds a pref (default true) for an ab[cdef] test for nightly and aurora

The test has 7 different randomly selected profiles, including one that is essentially "off", and tracks PLT against them.

Comment 5

[Patrick McManus [:mcmanus]]

Attachment: patch rev 2

update the patch for a couple windows treat warnings-as-errors problems.

Comment 6

[Patrick McManus [:mcmanus]]

I forgot this was going to need timeBeginPeriod/timeEndPeriod on windows.. it was on my list but somehow I missed it.

I think you can still review the patches though, just assume the *Period patches will be a followon requirement.

the patches also depend on the nsitimer threadsafety patches, but that's a different bug. (and maybe irrelevant now that the delaytimer has been removed - I haven't studied it again)

Comment 7

[Patrick McManus [:mcmanus]]

Attachment: part 2 (v1) - windows timer resolution

manipulate the OS resoltion through timeBeginPeriod()/timeEndPeriod() .. similar approach to the one taken by nsRefreshDriver - we increase the resolution only when we need it and turn it off 90 seconds after we don't need it any more.

The net effect is that it won't be running at increased resolution terribly often - pretty much only when you're clicking on new page loads which is when you want it. AJAX'y things won't trigger the logic because of the busrt parameter.

It would be nice for this to be integrated into the timer code itself but I wasn't really comfortable setting policies there for when it should be used and then turned off without more context.

Comment 8

[Honza Bambas (:mayhemer)]

I've started the review..

Comment 9

[Honza Bambas (:mayhemer)]

(In reply to Patrick McManus [:mcmanus] from comment #7)
> manipulate the OS resoltion through timeBeginPeriod()/timeEndPeriod() ..
> similar approach to the one taken by nsRefreshDriver - we increase the
> resolution only when we need it and turn it off 90 seconds after we don't
> need it any more.

Why 90 seconds?  That is a horribly long time.  I would return to the normal scheduling when not needed immediately.  Also, you could experiment with using a time (resolution) closer just to the resolution you need and not force maximum resolution of 1ms.

"it can also reduce overall system performance, because the thread scheduler switches tasks more often. High resolutions can also prevent the CPU power management system from entering power-saving modes"

I've never experimented with this, but I believe it's a bad think to do.

Comment 10

[Patrick McManus [:mcmanus]]

(In reply to Honza Bambas (:mayhemer) from comment #9)
> (In reply to Patrick McManus [:mcmanus] from comment #7)
> > manipulate the OS resoltion through timeBeginPeriod()/timeEndPeriod() ..
> > similar approach to the one taken by nsRefreshDriver - we increase the
> > resolution only when we need it and turn it off 90 seconds after we don't
> > need it any more.
> 
> Why 90 seconds?  That is a horribly long time.  I would return to the normal
> scheduling when not needed immediately.  

Its the same policy used by the animations refresh driver.. I just wanted to be consistent..

http://mxr.mozilla.org/mozilla-central/source/layout/base/nsRefreshDriver.cpp

I read a caution somewhere (which I cannot find now) about calling begin/end too often, so the cushion was put in when I saw the refresh driver was doing the same thing. But the advice wasn't based on anything or from anything official - it might very well have been made up. I don't mind removing that logic if you like. It certainly removes a bunch of code. You can make the call as I don't care a lot.

fwiw, this isn't that big of a deal in practice.. my win7 laptop is running at 1ms right now (even with firefox closed) and on battery and is doing just fine. So the difference of whether it stays on for a couple minutes vs a couple seconds probably isn't going to impact things very much imo.

> Also, you could experiment with
> using a time (resolution) closer just to the resolution you need and not
> force maximum resolution of 1ms.

That's pretty much what I need. If I have 10ms timers, 1ms is already a 10% miss.

> 
> "it can also reduce overall system performance, because the thread scheduler
> switches tasks more often. High resolutions can also prevent the CPU power
> management system from entering power-saving modes"
> 
> I've never experimented with this, but I believe it's a bad think to do.

If this were for long periods of time (i.e. anytime firefox is active) I would also be conservative. I'm not that freaked out about just doing it during big page loads.. css animations (which already do this) are actually a much bigger exposure (while the page is rendered, not just loading), right? And we're not going to be going into deep sleeps during load anyhow, right?

And, while it really doesn't bear on what to do, its ridiculous to have 15ms granularity on a modern OS. That's an eternity! I just had to get that off my chest. The utility I'm using to look at what my system resolution is currently running at suggests my win7 laptop could actually do 0.5ms resolution even though I haven't seen documentation to reflect that. Linux is pretty neat this way - it doesn't need a fixed tick to pull this stuff off at very precise granularities..

Comment 11

[Honza Bambas (:mayhemer)]

I think it deps also on OS.  Unfortunately now I have an XP machine that IMO will be affected most only on a virtual box, so hard to say how precise are any measurements I may do going to be.

I've never made any testing of timeBeginPeriod and its affect on performance.  Anyway it's clear that (except that windows thread scheduling is from stone edge..) the context switch logic overhead will raise significantly over thread run time.

Maybe ask the refresh driver people what was the read reason they turn it of in 90 seconds (horrible IMO!).  Maybe it only has effect on rendering perceptiveness.  What you need is just to get the timer closely as possible the short time bellow 15.6 ms.  As I understand you want to put thinks on the wire in the correct time, right?  Did you try to trace whether PR_Write is actually called in the desired rate?  Or did you do the checks using Wireshark?


Another topic: I don't know how much you are dependent on nsITimer thread safety and the filter being removed.  However, I wouldn't be against to have your own thread or to adjust sts thread (if possible) to give you the timer of your need.

Comment 12

[Patrick McManus [:mcmanus]]

(In reply to Honza Bambas (:mayhemer) from comment #11)
> perceptiveness.  What you need is just to get the timer closely as possible
> the short time bellow 15.6 ms.

yes.. even timers above 15ms have considerable inaccuracy when 15ms is the precision.

>  As I understand you want to put thinks on
> the wire in the correct time, right? 

yes.. the basic idea is to evenly space request start times a small bit apart to take some of the pressure off l2/l3 buffers before congestion control kicks in... and 10ms looks like a pretty interesting interval from some hand testing. using a 15ms tick that means that my 10ms timer could really go off after 24+ms (if the next tick were 9+ms away when it was armed), which would create 2 events bunched together.

> Did you try to trace whether PR_Write
> is actually called in the desired rate?  Or did you do the checks using
> Wireshark?
>

I've done it with both.. the result is considerably more precise on linux, but its pretty decent on win 7 with the *period changes. (and actually I had to boot it on a vista vm to see it run badly with 15ms granularity - my win7 box is always at granularity 1, I don't know what I have running that makes that happen.. its not firefox and I closed all windowed applications.. so its some service and I don't have many.) If there is some platform that still doesn't get accurate its probably ok - we won't be any worse off than we are now because the scheduler will send out "clumps" based on elapsed time.. so its not like we'll cumulatively add the error to the total page load time or anything.
 
> 
> Another topic: I don't know how much you are dependent on nsITimer thread
> safety and the filter being removed.  However, I wouldn't be against to have
> your own thread or to adjust sts thread (if possible) to give you the timer
> of your need.

well the filter is already gone (in the last few days that landed), so I'm in good shape there as long as it sticks. The delay filter introduced wild inaccuracy of dozens or even 100+) of ms. If it doesn't stick I've got a set of patches in my back pocket to create another thread as a backup plan..

Comment 13

[Honza Bambas (:mayhemer)]

For record: My Win7 box runs at standard setting.  Only Firefox (Aurora, no local patches) makes it run for first 90 seconds after start with resolution of 1.  It raises again to 1 on a new tab opening (no other way to raise it found).  I honestly don't understand this behavior well, however, it doesn't seem to be affecting performance in any visible way for me.

Comment 14

[Honza Bambas (:mayhemer)]

Comment on attachment 729806 [details] [diff] [review]
patch rev 2

Review of attachment 729806 [details] [diff] [review]:
-----------------------------------------------------------------

Overall, this is a good idea.


Check splinter for white spaces.

I did some small testing and I don't see any negative impact.  On pinterest I can see easily comparable improvement (checked against aurora with even pipelining on!): images load faster and online radio playback didn't choke.


This is close to r+ but I think some threading nits has to be addressed first.  r- just to refer the review comment.

::: modules/libpref/src/init/all.js
@@ +982,5 @@
>  pref("network.http.spdy.send-buffer-size", 131072);
>  
>  pref("network.http.diagnostics", false);
>  
> +pref("network.http.pacing.requests.enabled", false);

Do you plan more options under network.http.pacing ?  I'm curious why namespacing with "requests" otherwise.

::: netwerk/base/src/EventTokenBucket.cpp
@@ +34,5 @@
> +  nsCOMPtr<nsIIOService> ioService = do_GetIOService(&rv);
> +  if (NS_SUCCEEDED(rv))
> +    sts = do_GetService(NS_SOCKETTRANSPORTSERVICE_CONTRACTID, &rv);
> +  if (NS_SUCCEEDED(rv))
> +    mTimer->SetTarget(sts);

Maybe create the timer here?

@@ +63,5 @@
> +    SOCKET_LOG(("  burstSize out of range\n"));
> +    mMaxCredit = kUsecPerSec * 60 * 15;
> +  }
> +  mCredit = mMaxCredit;
> +  mLastUpdate = TimeStamp::Now();

These all are set on the main thread (when pref changes) and read on the socket thread.  Maybe post the set to socket thread?

But see also other comments about pref changes.

@@ +149,5 @@
> +  NS_ADDREF(*cancelable = cancelEvent.get());
> +
> +  if (mPaused || !TryToDispatch(cancelEvent.get())) {
> +    // queue it
> +    SOCKET_LOG(("   queued\n", this));

|this| is excessive, but logged would be nice

@@ +169,5 @@
> +
> +  mCredit -= mCost;
> +  event->mComplete = true;
> +
> +  event->mEvent->OnTokenBucketAdmitted();

This is example of a potentially unsafe code:  when mComplete on the event was already true you may call on a released pointer.

@@ +219,5 @@
> +  SOCKET_LOG(("EventTokenBucket::UpdateTimer %p for %dms\n",
> +              this, msecWait));
> +  mTimerArmed = true;
> +  mTimer->InitWithCallback(this, static_cast<uint32_t>(msecWait),
> +                           nsITimer::TYPE_ONE_SHOT);

rv = mTimer->Init...
mTimerArmed = NS_SUCCEEDED(rv)

?

@@ +225,5 @@
> +
> +NS_IMETHODIMP
> +EventTokenBucket::Notify(nsITimer *timer)
> +{
> +  // This runs on the socket thread todo verify

Yes, please verify.  Probably most of the methods here.

@@ +230,5 @@
> +  SOCKET_LOG(("EventTokenBucket::Notify() %p\n", this));
> +  if (mStopped)
> +    return NS_OK;
> +
> +  mTimerArmed = false;

Before mStopped check?

@@ +264,5 @@
> +NS_IMETHODIMP
> +TokenBucketCancelable::Cancel(nsresult reason)
> +{
> +  mComplete = true;
> +  return NS_OK;

Should definitely be called only on one thread (socket).

::: netwerk/base/src/EventTokenBucket.h
@@ +24,5 @@
> +    5ms gaps (i.e. up to 200hz). Token buckets with rates greater than 200hz will admit
> +    multiple events with 5ms gaps between them. 10000hz is the maximum rate and 1hz is
> +    the minimum rate.
> +
> +  + The burst size controls the limit of 'credist' that a token bucket can accumulate

'credist'

@@ +37,5 @@
> +
> +  + An event is submitted to the token bucket asynchronously through Submit().
> +    The OnTokenBucketAdmitted() method of the submitted event is used as a callback
> +    when the event is ready to run. A cancelable event is returned to the Submit() caller
> +    in case they do not wish to hang around for the callback.

Honestly, from this your description I really couldn't understand how token buckets and this impl work.  Could you be more schematic please?

@@ +49,5 @@
> +  virtual void OnTokenBucketAdmitted() = 0;
> +};
> +
> +class TokenBucketCancelable : public nsICancelable
> +{

I think this can be defined in the cpp file.

@@ +60,5 @@
> +
> +private:
> +  friend class EventTokenBucket;
> +  ATokenBucketEvent *mEvent;
> +  bool               mComplete;

Instead of having the mComplete flag, rather drop mEvent to null when 'canceled'.  (According the implementation the mEvent member can be invalid when mComplete is set, right?)  That way you will make clear this object is actually a weak proxy and that mEvent can be invalid while this object may live on.

Also, a Fire() multiple-call-safe method would be nice.

@@ +101,5 @@
> +  const static uint64_t kUsecPerSec =  1000000;
> +  const static uint64_t kUsecPerMsec = 1000;
> +  const static uint64_t kMaxHz = 10000;
> +
> +  uint64_t mCost;   // usec of credit needed for 1 event (from eventsPerSecond)

This should be named mOneEventCost.  I found my self looking in what this member actually means at one moment.

@@ +117,5 @@
> +  // setting of mTimerArmed (that variable covers the period of time when
> +  // we have generated an event for the main thread that will arm the timer
> +  // but it has not actually run yet). ::Notify is consequently executed on
> +  // the main thread, but it just posts an event back to the socket
> +  // thread to run TimerNotifyOnSocketThread()

This comment is not correct.  Timer is first invoked from:

>	xul.dll!mozilla::net::EventTokenBucket::UpdateTimer()  Line 249	C++
 	xul.dll!mozilla::net::EventTokenBucket::SubmitEvent(mozilla::net::ATokenBucketEvent * event=0x00000000, nsICancelable * * cancelable=0x1158efdc)  Line 178	C++
 	xul.dll!nsHttpTransaction::SubmitPacedRequest()  Line 1641 + 0x35 bytes	C++
 	xul.dll!nsHttpConnectionMgr::TryDispatchTransaction(nsHttpConnectionMgr::nsConnectionEntry * ent=0x0d7d7660, bool onlyReusedConnection=false, nsHttpTransaction * trans=0x1158ede0)  Line 1604	C++

on the the socket thread.  Notify() is called also on the socket thread.  It is IMO much better then to chase it through the main thread.  But needs thread safe timers...

::: netwerk/protocol/http/nsHttpConnection.cpp
@@ +1241,5 @@
>          }
>          else {
>              if (!mReportedSpdy) {
>                  mReportedSpdy = true;
> +                gHttpHandler->ConnMgr()->ReportSpdyConnection(this, mEverUsedSpdy);

Please add a comment why you are changing this.

::: netwerk/protocol/http/nsHttpConnectionMgr.cpp
@@ +1593,5 @@
> +    // It will only be actually submitted to the
> +    // token bucket once, and if possible it is granted admission synchronously.
> +    // It is important to leave a transaction in the pending queue when blocked by
> +    // pacing so it can be found on cancel if necessary.
> +    // Transactions that are cause blocking or bypass it (e.g. js/css) are not rate

that are cause blocking

@@ +1596,5 @@
> +    // pacing so it can be found on cancel if necessary.
> +    // Transactions that are cause blocking or bypass it (e.g. js/css) are not rate
> +    // limited.
> +    if (gHttpHandler->UseRequestTokenBucket() &&
> +        (mNumActiveConns - mNumSpdyActiveConns) >= gHttpHandler->RequestTokenBucketMinParallelism() &&

First: uint16 - uint32.  Second: if it happens that mNumSpdyActiveConns > mNumActiveConns when from some reason the counting is wrong we may loose the initial burst what means some slowdown.

At least the subtraction should have a signed result?

@@ +1599,5 @@
> +    if (gHttpHandler->UseRequestTokenBucket() &&
> +        (mNumActiveConns - mNumSpdyActiveConns) >= gHttpHandler->RequestTokenBucketMinParallelism() &&
> +        !(caps & (NS_HTTP_LOAD_AS_BLOCKING | NS_HTTP_LOAD_UNBLOCKED))) {
> +        trans->SubmitPacedRequest();
> +        if (!trans->PassedRatePacing()) {

if (trans->SubmitPacedRequest()) {
  return ...;
}

seems a bit less cumbersome to me, but up to you.

::: netwerk/protocol/http/nsHttpConnectionMgr.h
@@ +617,5 @@
>      // Total number of connections in mHalfOpens ConnectionEntry objects
>      // that are accessed from mCT connection table
>      uint32_t mNumHalfOpenConns;
> +    // Total number of spdy connections which are a subset of the active conns
> +    uint32_t mNumSpdyActiveConns;

Should be uint16 or should we change mNumActiveConns to uint32?

::: netwerk/protocol/http/nsHttpHandler.cpp
@@ +347,5 @@
>      }
>  
> +    mRequestTokenBucket = new mozilla::net::EventTokenBucket();
> +    mRequestTokenBucket->SetRate(mRequestTokenBucketHz,
> +                                 mRequestTokenBucketBurst);

You are first getting call to nsHttpHandler::PrefsChanged before nsHttpHandler::Init(), thus you throw away the old bucket and create a new one here, always.  I don't know whether it's on purpose to throw away the token bucket on pref change or not, but it seems a bit odd to me.  Can you explain please?

@@ +1246,5 @@
> +    }
> +    if (requestTokenBucketUpdated) {
> +        mRequestTokenBucket = new mozilla::net::EventTokenBucket();
> +        mRequestTokenBucket->SetRate(mRequestTokenBucketHz,
> +                                     mRequestTokenBucketBurst);

This happens on the main thread.  You throw mRequestTokenBucket that could be used on the socket thread potentially..


I also got the following stacktrace:

 	xul.dll!mozilla::net::EventTokenBucket::~EventTokenBucket()  Line 90	C++
 	xul.dll!mozilla::net::EventTokenBucket::`scalar deleting destructor'()  + 0xf bytes	C++
 	xul.dll!mozilla::net::EventTokenBucket::Release()  Line 20 + 0xa6 bytes	C++
 	xul.dll!nsCOMPtr<nsITimerCallback>::assign_assuming_AddRef(nsITimerCallback * newPtr=0x00000000)  Line 480	C++
 	xul.dll!nsCOMPtr<nsITimerCallback>::assign_with_AddRef(nsISupports * rawPtr=0x00000000)  Line 1156	C++
 	xul.dll!nsCOMPtr<nsITimerCallback>::operator=(nsITimerCallback * rhs=0x00000000)  Line 625	C++
>	xul.dll!nsTimerImpl::Fire()  Line 574	C++
 	xul.dll!nsTimerEvent::Run()  Line 632	C++
 	xul.dll!nsThread::ProcessNextEvent(bool mayWait=true, bool * result=0x034afdb3)  Line 627 + 0x19 bytes	C++
 	xul.dll!NS_ProcessNextEvent(nsIThread * thread=0x02be1888, bool mayWait=true)  Line 238 + 0x17 bytes	C++
 	xul.dll!nsSocketTransportService::Run()  Line 649 + 0xb bytes	C++


It looks like there may be more then one bucket running at a time.

@@ +1552,5 @@
> +nsHttpHandler::SubmitPacedRequest(mozilla::net::ATokenBucketEvent *event,
> +                                  nsICancelable **cancel)
> +{
> +    return mRequestTokenBucket->SubmitEvent(event, cancel);
> +}

Nit: methods like this are usually inlined in this class.

::: netwerk/protocol/http/nsHttpHandler.h
@@ +40,5 @@
> +
> +namespace mozilla { namespace net {
> +class ATokenBucketEvent;
> +class EventTokenBucket;
> +}}

Please as:

n m {
n n {

c ATB;
c ETB;

}
}

@@ +421,5 @@
> +    // For Rate Pacing of requests
> +    bool           mRequestTokenBucketEnabled;
> +    uint32_t       mRequestTokenBucketMinParallelism;
> +    uint32_t       mRequestTokenBucketHz;
> +    uint32_t       mRequestTokenBucketBurst;

Some comments please.

::: netwerk/protocol/http/nsHttpTransaction.h
@@ +322,5 @@
> +private:
> +    bool mSubmittedRatePacing;
> +    bool mPassedRatePacing;
> +    bool mSynchronousRatePaceRequest;
> +    nsCOMPtr<nsICancelable> mTokenBucketCancel;

This all needs good comments.  Please add them.

Comment 15

[Honza Bambas (:mayhemer)]

Comment on attachment 729592 [details] [diff] [review]
abtest rev 1

Review of attachment 729592 [details] [diff] [review]:
-----------------------------------------------------------------

r+ but this again suffers from the threading issues when preferences change on the main thread.

::: netwerk/base/public/nsPILoadGroupInternal.idl
@@ +23,5 @@
> +     *
> +     * @param aDefaultChanel
> +     *        The request channel for the base apge
> +
> +     */

excessive blank line

@@ +24,5 @@
> +     * @param aDefaultChanel
> +     *        The request channel for the base apge
> +
> +     */
> +    void EndPageLoad(in nsIChannel aDefaultChannel);

If this is a callback then OnEndPageLoad

::: netwerk/base/src/nsLoadGroup.cpp
@@ +637,4 @@
>                  ++mCachedRequests;
> +            }
> +            else {
> +                mTimedNonCachedRequestsSinceEndPageLoad++;

Is the name correct?  It more seems like it reflects non cached *till* end page load.

@@ +778,5 @@
> +nsLoadGroup::EndPageLoad(nsIChannel *aDefaultChannel)
> +{
> +    // On page load of a page with at least 32 resources we want to record
> +    // telemetry on which rate pacing algorithm was used to load the page and
> +    // the PLT

PLT? no cryptic abbrevs in comments please.

::: netwerk/protocol/http/nsHttpHandler.cpp
@@ +788,5 @@
> +    { 32, 1, 8, Telemetry::HTTP_PLT_RATE_PACING_4 },   // allow only min-parallelism
> +    { 32, 1, 16, Telemetry::HTTP_PLT_RATE_PACING_5 },  // allow only min-parallelism (larger)
> +    { 1000, 1000, 1000, Telemetry::HTTP_PLT_RATE_PACING_6 }, // unlimited
> +};
> +        

ws

@@ +1381,5 @@
> +                
> +                if (randomGenerator &&
> +                    NS_SUCCEEDED(randomGenerator->GenerateRandomBytes(4, &buffer))) {
> +                    // just taking the remainder is not perfectly uniform - it doesn't
> +                    // matter here.

You should use crt rand().  This is too expensive.

::: netwerk/protocol/http/nsIHttpChannelInternal.idl
@@ +172,5 @@
>       */
>      attribute boolean loadUnblocked;
> +
> +    /**
> +     * bug 819734 we implements experimental rate pacing strategies for pages

implement

@@ +177,5 @@
> +     * with large numbers of subresources. Several experimental profiles are
> +     * available and this attribute corresponds to the profile used for this
> +     * channel. (or at least the one active when it is queried.)
> +     */
> +     readonly attribute uint32_t pacingTelemetryID;

indent

Comment 16

[Honza Bambas (:mayhemer)]

Comment on attachment 730238 [details] [diff] [review]
part 2 (v1) - windows timer resolution

Review of attachment 730238 [details] [diff] [review]:
-----------------------------------------------------------------

::: netwerk/base/src/EventTokenBucket.cpp
@@ +342,5 @@
> +    if (mFineGrainResetTimerArmed)
> +      return;
> +
> +    TimeDuration elapsed(TimeStamp::Now() - mLastFineGrainTimerUse);
> +    static const TimeDuration ninetySeconds = TimeDuration::FromSeconds(90);

Please change this to 5 or 10 seconds.  You really don't need 90 seconds here.

@@ +365,5 @@
> +                "Will reset timer granularity after delay", this));
> +
> +    mFineGrainResetTimer->
> +      InitWithCallback(this,
> +                       static_cast<uint32_t>((ninetySeconds - elapsed).ToMilliseconds()) + 10,

I think 10 may be too few.  100ms?

@@ +367,5 @@
> +    mFineGrainResetTimer->
> +      InitWithCallback(this,
> +                       static_cast<uint32_t>((ninetySeconds - elapsed).ToMilliseconds()) + 10,
> +                       nsITimer::TYPE_ONE_SHOT);
> +    mFineGrainResetTimerArmed = true;

Indention of the whole block.

Comment 17

[Patrick McManus [:mcmanus]]

(In reply to Honza Bambas (:mayhemer) from comment #14)

> I can see easily comparable improvement (checked against aurora with even
> pipelining on!): images load faster and online radio playback didn't choke.

That's really good to hear. The bit about radio playback is pretty interesting in particular and a good sign.

> >  
> > +pref("network.http.pacing.requests.enabled", false);
> 
> Do you plan more options under network.http.pacing ?  I'm curious why
> namespacing with "requests" otherwise.

maybe! Two candidates are SYN and DNS, neither or which is congestion controlled and can create huge runs. I briefly played with a crude SYN implementation when I was doing this patch but didn't manage to see any improvement when also doing the request rate limiting.. but I think the door is still open - for instance maybe we would change the request rate limits so that they never counted handshakes and then we could do the handshake earlier on a rate limited transaction but perhaps limit the handshakes separately at a different pace - presumably faster. That doesn't sound like its needed if we have 10ms spacing.. but if we end up with 50ms spacing it might be more interesting. DNS is just a hypothesis at this point.

> 
> @@ +63,5 @@
> > +    SOCKET_LOG(("  burstSize out of range\n"));
> > +    mMaxCredit = kUsecPerSec * 60 * 15;
> > +  }
> > +  mCredit = mMaxCredit;
> > +  mLastUpdate = TimeStamp::Now();
> 
> These all are set on the main thread (when pref changes) and read on the
> socket thread.  Maybe post the set to socket thread?
> 
> But see also other comments about pref changes.

I think its an API problem (which I'll fix). When the pref changes the implementation actually creates a new token bucket that it initializes with the new prefs.. (admittedly not atomically) so this should be easily fixable by merging SetRate() with the ctor (atomic!)


> 
> @@ +169,5 @@
> > +
> > +  mCredit -= mCost;
> > +  event->mComplete = true;
> > +
> > +  event->mEvent->OnTokenBucketAdmitted();
> 
> This is example of a potentially unsafe code:  when mComplete on the event
> was already true you may call on a released pointer.

This is actually ok because the function (TryToDispatch) is only called synchronously from SubmitEvent() which created the canceleable event and set mcomplete to false. I'll rename it to TryImmediateDispatch to make things more clear. It could also be inlined, it was just logically separate in my mind.
most of the methods here.

> 
> @@ +117,5 @@
> > +  // setting of mTimerArmed (that variable covers the period of time when
> > +  // we have generated an event for the main thread that will arm the timer
> > +  // but it has not actually run yet). ::Notify is consequently executed on
> > +  // the main thread, but it just posts an event back to the socket
> > +  // thread to run TimerNotifyOnSocketThread()
> 
> This comment is not correct.  Timer is first invoked from:


you're right. the code is correct and the comment out of date.. the comment reflected an early design. comment fixed. We need to keep the main thread out of this because the latencies of delivering things on that thread can be extremely poor. I can see that reading this comment would really have skewed how you expected the code to work - sorry about the oversight!

> 
> ::: netwerk/protocol/http/nsHttpConnection.cpp
> @@ +1241,5 @@
> >          }
> >          else {
> >              if (!mReportedSpdy) {
> >                  mReportedSpdy = true;
> > +                gHttpHandler->ConnMgr()->ReportSpdyConnection(this, mEverUsedSpdy);
> 
> Please add a comment why you are changing this.

I don't think it helps the readability of the code, so I'll just explain it here. 
1] The argument to ReportSpdyConnection() has always been a bool, so this change fixes the mismatch
2] The semantics of ReportSpdyConnection() want to know if the server has negotiated spdy (which is what mEverUsedSpdy says), not whether or not spdy is currently being used.. the latter can actually be "undone" at the end of a connection, where mEverUsedSpdy is persistent. This is more of a robustness change than anything else - I don't think the current code could ever report the wrong thing.
3] I made the change in this patch because I needed to count spdy active connections and was using conn->EverUsedSpdy() as the decrement for that (mEverUsedSpdy) and I wanted to make sure it was perfectly symmetric against the ReportSpdyConnction() variable that was used for the increment side.

> 
> @@ +1596,5 @@
> > +    // pacing so it can be found on cancel if necessary.
> > +    // Transactions that are cause blocking or bypass it (e.g. js/css) are not rate
> > +    // limited.
> > +    if (gHttpHandler->UseRequestTokenBucket() &&
> > +        (mNumActiveConns - mNumSpdyActiveConns) >= gHttpHandler->RequestTokenBucketMinParallelism() &&
> 
> First: uint16 - uint32.  Second: if it happens that mNumSpdyActiveConns >
> mNumActiveConns when from some reason the counting is wrong we may loose the
> initial burst what means some slowdown.
> 
> At least the subtraction should have a signed result?

I changed mNumSpdyActiveConns to be u16, its a subset of the other u16 after all. I also added a check, just for robustness, that activeconns >= spdyactiveconns.

> ::: netwerk/protocol/http/nsHttpHandler.cpp
> @@ +347,5 @@
> >      }
> >  
> > +    mRequestTokenBucket = new mozilla::net::EventTokenBucket();
> > +    mRequestTokenBucket->SetRate(mRequestTokenBucketHz,
> > +                                 mRequestTokenBucketBurst);
> 
> You are first getting call to nsHttpHandler::PrefsChanged before
> nsHttpHandler::Init(), thus you throw away the old bucket and create a new
> one here, always.  I don't know whether it's on purpose to throw away the
> token bucket on pref change or not, but it seems a bit odd to me.  Can you
> explain please?

Its intentional. Dealing with a configuration change atomically across threads is pretty ugly, and requires the introduction of all kinds of locks that normally aren't necessary. Its not even clear how to deal with some things like mCredit which is credits earned at a particular rate during idle time. By making those hz/burst immutable those problems pretty much go away (which of course means move them to the ctor). Given that the pref change is a pretty darn unusual event that seemed like a reasonable tradeoff for both runtime and code complexity. We do throw away one of these during startup, but I don't see a reason to care very much.

if we absolutely needed to enforce the limit policy at every moment for the sake of correctness this would be a bad strategy, but the changeover is very ephemeral and its just an optimization.

> 
> It looks like there may be more then one bucket running at a time.

that could happen in the sense that one could be shutting itself down (and completing queued events) and another fresh one could be ratelimiting new events.


> ::: netwerk/protocol/http/nsHttpTransaction.h
> @@ +322,5 @@
> > +private:
> > +    bool mSubmittedRatePacing;
> > +    bool mPassedRatePacing;
> > +    bool mSynchronousRatePaceRequest;
> > +    nsCOMPtr<nsICancelable> mTokenBucketCancel;
> 
> This all needs good comments.  Please add them.

Comment 18

[Patrick McManus [:mcmanus]]

(In reply to Honza Bambas (:mayhemer) from comment #15)
> Comment on attachment 729592 [details] [diff] [review]
> abtest rev 1
> 
> Review of attachment 729592 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> r+ but this again suffers from the threading issues when preferences change
> on the main thread.


I think the changes in the base patch resolved this. I'll post the merged version of this if you want to take a look.

Comment 19

[Patrick McManus [:mcmanus]]

Attachment: abtest rev2

Comment 20

[Patrick McManus [:mcmanus]]

Attachment: patch rev 3

Comment 21

[Honza Bambas (:mayhemer)]

(In reply to Patrick McManus [:mcmanus] from comment #17)
> (In reply to Honza Bambas (:mayhemer) from comment #14)
> > You are first getting call to nsHttpHandler::PrefsChanged before
> > nsHttpHandler::Init(), thus you throw away the old bucket and create a new
> > one here, always.  I don't know whether it's on purpose to throw away the
> > token bucket on pref change or not, but it seems a bit odd to me.  Can you
> > explain please?
> 
> Its intentional. Dealing with a configuration change atomically across
> threads is pretty ugly, and requires the introduction of all kinds of locks
> that normally aren't necessary. Its not even clear how to deal with some
> things like mCredit which is credits earned at a particular rate during idle
> time. By making those hz/burst immutable those problems pretty much go away
> (which of course means move them to the ctor). Given that the pref change is
> a pretty darn unusual event that seemed like a reasonable tradeoff for both
> runtime and code complexity. We do throw away one of these during startup,
> but I don't see a reason to care very much.
> 
> if we absolutely needed to enforce the limit policy at every moment for the
> sake of correctness this would be a bad strategy, but the changeover is very
> ephemeral and its just an optimization.

I have nothing against that you throw away one instance and create a new one.  I complain about how you do it.  When you nullify the member in http handler, you may effectively throw the object away when it's not referenced by anything but this member.  But consumers are using the pointer directly on the socket w/o adding a reference for the time of its use.  So, you can delete the object while socket thread is just using it.  That is the bad thing.  If you set the members mRequestTokenBucket* on the main thread and then post an event to the socket thread with copy of the mRequestTokenBucket* values and do replacement of mRequestTokenBucket there, then we are OK.

Otherwise, you are adding unstable code to the tree.

Comment 22

[Honza Bambas (:mayhemer)]

Comment on attachment 732079 [details] [diff] [review]
patch rev 3

Review of attachment 732079 [details] [diff] [review]:
-----------------------------------------------------------------

r+ but the pref setting thread issue is still there.

::: netwerk/base/src/EventTokenBucket.cpp
@@ +40,5 @@
> +
> +NS_IMETHODIMP
> +TokenBucketCancelable::Cancel(nsresult reason)
> +{
> +  NS_ABORT_IF_FALSE(!NS_IsMainThread(), "should be socket thread");

Nit: MOZ_ASSERT(NS_IsMainThread(), "should be socket thread"); is probably working these days and does the same job.  And it's less cumbersome.

You could use PR_GetCurrentThread() == gSocketThread.

@@ +91,5 @@
> +}
> +
> +void
> +EventTokenBucket::SetRate(uint32_t eventsPerSecond,
> +                          uint32_t burstSize)

Nit: I would expect dtor right after ctor as used to at all other files.

@@ +122,5 @@
> +  SOCKET_LOG(("EventTokenBucket::dtor %p events=%d\n",
> +              this, mEvents.GetSize()));
> +
> +  MOZ_COUNT_DTOR(EventTokenBucket);
> +  if (mTimerArmed)

&& mTimer ?

::: netwerk/base/src/EventTokenBucket.h
@@ +114,5 @@
> +  nsDeque  mEvents;
> +  bool     mTimerArmed;
> +  TimeStamp mLastUpdate;
> +
> +  // The timer is created the main thread, but is armed and executes Notify()

created on the

::: netwerk/protocol/http/nsHttpHandler.h
@@ +423,5 @@
> +    // For Rate Pacing of HTTP/1 requests through a netwerk/base/src/EventTokenBucket
> +    // Active requests <= *MinParallelism are not subject to the rate pacing
> +    bool           mRequestTokenBucketEnabled;
> +    uint16_t       mRequestTokenBucketMinParallelism;
> +    uint32_t       mRequestTokenBucketHz;  //EventTokenBucket HZ

// EventTokenBucket HZ

@@ +439,5 @@
> +    // Socket thread only
> +    nsresult SubmitPacedRequest(mozilla::net::ATokenBucketEvent *event,
> +                                nsICancelable **cancel)
> +    {
> +        return mRequestTokenBucket->SubmitEvent(event, cancel);

Nothing against, but null check wouldn't be bad ;)

::: netwerk/protocol/http/nsHttpTransaction.cpp
@@ +1648,5 @@
> +    mPassedRatePacing = true;
> +    mTokenBucketCancel = nullptr;
> +
> +    if (!mSynchronousRatePaceRequest)
> +        gHttpHandler->ConnMgr()->ProcessPendingQ(mConnInfo);

Nit: to remove need of the mSynchronousRatePaceRequest member flag, the callback could indicate it self whether it's synchronous or not.  But the flag as is may be safer.  We really want to prevent ProcessPendingQ being called when TryToRunPacedRequest() is on the stack.

Comment 23

[Patrick McManus [:mcmanus]]

(In reply to Honza Bambas (:mayhemer) from comment #21)
>e a new
> one.  I complain about how you do it.  When you nullify the member in http
> handler, you may effectively throw the object away when it's not referenced
> by anything but this member.  But consumers are using the pointer directly
> on the socket w/o adding a reference for the time of its use.  So, you can

you're right!

Comment 24

[Patrick McManus [:mcmanus]]

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/ecf37b2b9a96
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/1d2790a22f3d
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/0aab2bb76b45

Comment 25

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/ecf37b2b9a96
https://hg.mozilla.org/mozilla-central/rev/1d2790a22f3d
https://hg.mozilla.org/mozilla-central/rev/0aab2bb76b45