Closed Bug 931186 Opened 6 years ago Closed 6 years ago

Need a dirt simple token bucket for global rate-limiting

Categories

(Core :: WebRTC: Networking, defect)

x86
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla28
Tracking Status
firefox27 --- fixed
firefox28 --- fixed
b2g-v1.2 --- fixed

People

(Reporter: bwc, Assigned: bwc)

Details

Attachments

(1 file, 6 obsolete files)

Just a super simple token bucket. No timers, no buffering, no knowledge of network stuff, doesn't have to be threadsafe, etc.
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Attachment #822517 - Attachment is obsolete: true
Assignee: nobody → docfaraday
Status: NEW → ASSIGNED
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Minor tweaks
Attachment #822518 - Attachment is obsolete: true
Attachment #822523 - Flags: review?(ekr)
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Compiler already wasn't going to generate this.
Attachment #822523 - Attachment is obsolete: true
Attachment #822523 - Flags: review?(ekr)
Comment on attachment 822523 [details] [diff] [review]
Dirt simple token bucket class.

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

::: media/mtransport/simpletokenbucket.cpp
@@ +5,5 @@
> + * You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +/* Original author: bcampen@mozilla.com */
> +
> +#include "simpletokenbucket.h"

Please include what you use the relevant things.

@@ +19,5 @@
> +}
> +
> +size_t SimpleTokenBucket::getTokens(size_t num_requested_tokens) {
> +  // Only fill if there isn't enough to satisfy the request.
> +  if (num_requested_tokens > num_tokens_) {

Can you comment what happens in the case where you wait a really long time
and the interval timer rolls over? I think it's fine, but it's also worth
mentioning.

I'm also thinking about the computation here: don't we actually let you
write 2x the number of tokens initially? Like we do X tokens/second over
a S second range, but you start out with XS and then we replenish at
a rate of X/s, so over the next S seconds you can write 2X tokens, right?

Don't we really want to start with 0?

::: media/mtransport/simpletokenbucket.h
@@ +21,5 @@
> +#include "m_cpp_utils.h"
> +
> +namespace mozilla {
> +
> +class SimpleTokenBucket {

Style here is that public: is indented by 1 and the others are indented by 2.

@@ +27,5 @@
> +    /*
> +     *  Create a SimpleTokenBucket with a given maximum size and
> +     *  token replenishment rate.
> +     */
> +    SimpleTokenBucket(size_t bucket_size, size_t tokens_per_second);

Can you add some comments about how to use this.

If I understand correctly, if I want to have a rate of no more than X tokens per second over S seconds,
I call it with SimpleTokenBucket(XS, X);

Is that right?

@@ +44,5 @@
> +    uint64_t num_tokens_;
> +    size_t tokens_per_second_;
> +    PRIntervalTime last_time_tokens_added_;
> +
> +    SimpleTokenBucket() MOZ_DELETE;

Is this necessary? Defining any ctor should block the default ctor.

::: media/mtransport/test/simpletokenbucket_unittest.cpp
@@ +34,5 @@
> +}
> +
> +TEST(SimpleTokenBucketTest, TestGet) {
> +  TestSimpleTokenBucket b(10, 1);
> +  ASSERT_EQ(5U, b.getTokens(5));

There is a race condition here, right? But a prety unlikely one.

@@ +63,5 @@
> +  // counts as a full second)
> +  TestSimpleTokenBucket b(10, 1);
> +  ASSERT_EQ(5U, b.getTokens(5));
> +  b.fastForward(500);
> +  ASSERT_EQ(5U, b.getTokens(6));

Suggest using MAX_UINT32 for minimizing brittleness when you just want to ask how many

@@ +95,5 @@
> +  TestSimpleTokenBucket b(10, 1);
> +  ASSERT_EQ(10U, b.getTokens(10));
> +  ASSERT_EQ(0U, b.getTokens(1));
> +  b.fastForward(50000);
> +  ASSERT_EQ(10U, b.getTokens(11));

Why is this 10 if you are doing 1 token per second and this is 50 seconds? Do I need more caffeine?
Attachment #822523 - Attachment is obsolete: false
(In reply to Eric Rescorla (:ekr) from comment #5)
> Comment on attachment 822523 [details] [diff] [review]
> Dirt simple token bucket class.
> 
> Review of attachment 822523 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: media/mtransport/simpletokenbucket.cpp
> @@ +19,5 @@
> > +}
> > +
> > +size_t SimpleTokenBucket::getTokens(size_t num_requested_tokens) {
> > +  // Only fill if there isn't enough to satisfy the request.
> > +  if (num_requested_tokens > num_tokens_) {
> 
> Can you comment what happens in the case where you wait a really long time
> and the interval timer rolls over? I think it's fine, but it's also worth
> mentioning.
> 

  If we get a full rollover, there is a possibility that the bucket will not end up completely filled. Not too bad.

> I'm also thinking about the computation here: don't we actually let you
> write 2x the number of tokens initially? Like we do X tokens/second over
> a S second range, but you start out with XS and then we replenish at
> a rate of X/s, so over the next S seconds you can write 2X tokens, right?
> 
> Don't we really want to start with 0?
>

  Yeah, was not 100% sure how we wanted to manage that. Starting at 0 is going to have really annoying latency effects if we create the bucket as we're getting started. Not starting at zero lets us burst at double-speed once at the very beginning, but never again. This may very well be what we want?
 
> @@ +27,5 @@
> > +    /*
> > +     *  Create a SimpleTokenBucket with a given maximum size and
> > +     *  token replenishment rate.
> > +     */
> > +    SimpleTokenBucket(size_t bucket_size, size_t tokens_per_second);
> 
> Can you add some comments about how to use this.
> 
> If I understand correctly, if I want to have a rate of no more than X tokens
> per second over S seconds,
> I call it with SimpleTokenBucket(XS, X);
>

  That's the idea. 

> @@ +63,5 @@
> > +  // counts as a full second)
> > +  TestSimpleTokenBucket b(10, 1);
> > +  ASSERT_EQ(5U, b.getTokens(5));
> > +  b.fastForward(500);
> > +  ASSERT_EQ(5U, b.getTokens(6));
> 
> Suggest using MAX_UINT32 for minimizing brittleness when you just want to
> ask how many
>

  Good point, especially given that this is how I said I should do this in the header file.
Attachment #822523 - Attachment is obsolete: true
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Incorporate some feedback from ekr.
Attachment #822574 - Attachment is obsolete: true
Attached patch Dirt simple token bucket class. (obsolete) — Splinter Review
Add a test for checking the bucket size; other tests are explicitly about verifying that a realistic number that cannot be currently fulfilled is handled properly.
Attachment #822623 - Attachment is obsolete: true
Comment on attachment 822626 [details] [diff] [review]
Dirt simple token bucket class.

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

::: media/mtransport/simpletokenbucket.cpp
@@ +30,5 @@
> +  if (num_requested_tokens > num_tokens_) {
> +    PRIntervalTime now = PR_IntervalNow();
> +
> +    // If we roll over the max, since everything in this calculation is the same
> +    // unsigned type, this will still do the right thing.

Define "right thing"

@@ +37,5 @@
> +    uint32_t elapsed_milli_sec = PR_IntervalToMilliseconds(elapsed_ticks);
> +    size_t tokens_to_add = (elapsed_milli_sec * tokens_per_second_)/1000;
> +
> +    // Only update our timestamp if we added some tokens
> +    // ?bwc? Should we attempt to "save" leftover time here?

Remember convention here is "TODO(bcampen@mozilla.com)."
Attachment #822626 - Flags: review+
Fix nits.
Attachment #822626 - Attachment is obsolete: true
Comment on attachment 823597 [details] [diff] [review]
Dirt simple token bucket class.

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

Carry forward r+ from ekr. (nits fixed)
Attachment #823597 - Flags: review+
Attachment #823597 - Flags: checkin?(adam)
Comment on attachment 823597 [details] [diff] [review]
Dirt simple token bucket class.

https://hg.mozilla.org/integration/mozilla-inbound/rev/f31dc2d87066
Attachment #823597 - Flags: checkin?(adam) → checkin+
https://hg.mozilla.org/mozilla-central/rev/f31dc2d87066
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
Byron, can you please advise if this needs manual QA attention?
Flags: needinfo?(docfaraday)
No, the unit-tests should have this covered well.
Flags: needinfo?(docfaraday)
Flags: in-testsuite+
You need to log in before you can comment on or make changes to this bug.