vendor/golang.org/x/time/rate/rate_test.go

   1 // Copyright 2015 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // +build go1.7
   6
   7 package rate
   8
   9 import (
  10         "context"
  11         "math"
  12         "runtime"
  13         "sync"
  14         "sync/atomic"
  15         "testing"
  16         "time"
  17 )
  18
  19 func TestLimit(t *testing.T) {
  20         if Limit(10) == Inf {
  21                 t.Errorf("Limit(10) == Inf should be false")
  22         }
  23 }
  24
  25 func closeEnough(a, b Limit) bool {
  26         return (math.Abs(float64(a)/float64(b)) - 1.0) < 1e-9
  27 }
  28
  29 func TestEvery(t *testing.T) {
  30         cases := []struct {
  31                 interval time.Duration
  32                 lim      Limit
  33         }{
  34                 {0, Inf},
  35                 {-1, Inf},
  36                 {1 * time.Nanosecond, Limit(1e9)},
  37                 {1 * time.Microsecond, Limit(1e6)},
  38                 {1 * time.Millisecond, Limit(1e3)},
  39                 {10 * time.Millisecond, Limit(100)},
  40                 {100 * time.Millisecond, Limit(10)},
  41                 {1 * time.Second, Limit(1)},
  42                 {2 * time.Second, Limit(0.5)},
  43                 {time.Duration(2.5 * float64(time.Second)), Limit(0.4)},
  44                 {4 * time.Second, Limit(0.25)},
  45                 {10 * time.Second, Limit(0.1)},
  46                 {time.Duration(math.MaxInt64), Limit(1e9 / float64(math.MaxInt64))},
  47         }
  48         for _, tc := range cases {
  49                 lim := Every(tc.interval)
  50                 if !closeEnough(lim, tc.lim) {
  51                         t.Errorf("Every(%v) = %v want %v", tc.interval, lim, tc.lim)
  52                 }
  53         }
  54 }
  55
  56 const (
  57         d = 100 * time.Millisecond
  58 )
  59
  60 var (
  61         t0 = time.Now()
  62         t1 = t0.Add(time.Duration(1) * d)
  63         t2 = t0.Add(time.Duration(2) * d)
  64         t3 = t0.Add(time.Duration(3) * d)
  65         t4 = t0.Add(time.Duration(4) * d)
  66         t5 = t0.Add(time.Duration(5) * d)
  67         t9 = t0.Add(time.Duration(9) * d)
  68 )
  69
  70 type allow struct {
  71         t  time.Time
  72         n  int
  73         ok bool
  74 }
  75
  76 func run(t *testing.T, lim *Limiter, allows []allow) {
  77         for i, allow := range allows {
  78                 ok := lim.AllowN(allow.t, allow.n)
  79                 if ok != allow.ok {
  80                         t.Errorf("step %d: lim.AllowN(%v, %v) = %v want %v",
  81                                 i, allow.t, allow.n, ok, allow.ok)
  82                 }
  83         }
  84 }
  85
  86 func TestLimiterBurst1(t *testing.T) {
  87         run(t, NewLimiter(10, 1), []allow{
  88                 {t0, 1, true},
  89                 {t0, 1, false},
  90                 {t0, 1, false},
  91                 {t1, 1, true},
  92                 {t1, 1, false},
  93                 {t1, 1, false},
  94                 {t2, 2, false}, // burst size is 1, so n=2 always fails
  95                 {t2, 1, true},
  96                 {t2, 1, false},
  97         })
  98 }
  99
 100 func TestLimiterBurst3(t *testing.T) {
 101         run(t, NewLimiter(10, 3), []allow{
 102                 {t0, 2, true},
 103                 {t0, 2, false},
 104                 {t0, 1, true},
 105                 {t0, 1, false},
 106                 {t1, 4, false},
 107                 {t2, 1, true},
 108                 {t3, 1, true},
 109                 {t4, 1, true},
 110                 {t4, 1, true},
 111                 {t4, 1, false},
 112                 {t4, 1, false},
 113                 {t9, 3, true},
 114                 {t9, 0, true},
 115         })
 116 }
 117
 118 func TestLimiterJumpBackwards(t *testing.T) {
 119         run(t, NewLimiter(10, 3), []allow{
 120                 {t1, 1, true}, // start at t1
 121                 {t0, 1, true}, // jump back to t0, two tokens remain
 122                 {t0, 1, true},
 123                 {t0, 1, false},
 124                 {t0, 1, false},
 125                 {t1, 1, true}, // got a token
 126                 {t1, 1, false},
 127                 {t1, 1, false},
 128                 {t2, 1, true}, // got another token
 129                 {t2, 1, false},
 130                 {t2, 1, false},
 131         })
 132 }
 133
 134 // Ensure that tokensFromDuration doesn't produce
 135 // rounding errors by truncating nanoseconds.
 136 // See golang.org/issues/34861.
 137 func TestLimiter_noTruncationErrors(t *testing.T) {
 138         if !NewLimiter(0.7692307692307693, 1).Allow() {
 139                 t.Fatal("expected true")
 140         }
 141 }
 142
 143 func TestSimultaneousRequests(t *testing.T) {
 144         const (
 145                 limit       = 1
 146                 burst       = 5
 147                 numRequests = 15
 148         )
 149         var (
 150                 wg    sync.WaitGroup
 151                 numOK = uint32(0)
 152         )
 153
 154         // Very slow replenishing bucket.
 155         lim := NewLimiter(limit, burst)
 156
 157         // Tries to take a token, atomically updates the counter and decreases the wait
 158         // group counter.
 159         f := func() {
 160                 defer wg.Done()
 161                 if ok := lim.Allow(); ok {
 162                         atomic.AddUint32(&numOK, 1)
 163                 }
 164         }
 165
 166         wg.Add(numRequests)
 167         for i := 0; i < numRequests; i++ {
 168                 go f()
 169         }
 170         wg.Wait()
 171         if numOK != burst {
 172                 t.Errorf("numOK = %d, want %d", numOK, burst)
 173         }
 174 }
 175
 176 func TestLongRunningQPS(t *testing.T) {
 177         if testing.Short() {
 178                 t.Skip("skipping in short mode")
 179         }
 180         if runtime.GOOS == "openbsd" {
 181                 t.Skip("low resolution time.Sleep invalidates test (golang.org/issue/14183)")
 182                 return
 183         }
 184
 185         // The test runs for a few seconds executing many requests and then checks
 186         // that overall number of requests is reasonable.
 187         const (
 188                 limit = 100
 189                 burst = 100
 190         )
 191         var numOK = int32(0)
 192
 193         lim := NewLimiter(limit, burst)
 194
 195         var wg sync.WaitGroup
 196         f := func() {
 197                 if ok := lim.Allow(); ok {
 198                         atomic.AddInt32(&numOK, 1)
 199                 }
 200                 wg.Done()
 201         }
 202
 203         start := time.Now()
 204         end := start.Add(5 * time.Second)
 205         for time.Now().Before(end) {
 206                 wg.Add(1)
 207                 go f()
 208
 209                 // This will still offer ~500 requests per second, but won't consume
 210                 // outrageous amount of CPU.
 211                 time.Sleep(2 * time.Millisecond)
 212         }
 213         wg.Wait()
 214         elapsed := time.Since(start)
 215         ideal := burst + (limit * float64(elapsed) / float64(time.Second))
 216
 217         // We should never get more requests than allowed.
 218         if want := int32(ideal + 1); numOK > want {
 219                 t.Errorf("numOK = %d, want %d (ideal %f)", numOK, want, ideal)
 220         }
 221         // We should get very close to the number of requests allowed.
 222         if want := int32(0.999 * ideal); numOK < want {
 223                 t.Errorf("numOK = %d, want %d (ideal %f)", numOK, want, ideal)
 224         }
 225 }
 226
 227 type request struct {
 228         t   time.Time
 229         n   int
 230         act time.Time
 231         ok  bool
 232 }
 233
 234 // dFromDuration converts a duration to a multiple of the global constant d
 235 func dFromDuration(dur time.Duration) int {
 236         // Adding a millisecond to be swallowed by the integer division
 237         // because we don't care about small inaccuracies
 238         return int((dur + time.Millisecond) / d)
 239 }
 240
 241 // dSince returns multiples of d since t0
 242 func dSince(t time.Time) int {
 243         return dFromDuration(t.Sub(t0))
 244 }
 245
 246 func runReserve(t *testing.T, lim *Limiter, req request) *Reservation {
 247         return runReserveMax(t, lim, req, InfDuration)
 248 }
 249
 250 func runReserveMax(t *testing.T, lim *Limiter, req request, maxReserve time.Duration) *Reservation {
 251         r := lim.reserveN(req.t, req.n, maxReserve)
 252         if r.ok && (dSince(r.timeToAct) != dSince(req.act)) || r.ok != req.ok {
 253                 t.Errorf("lim.reserveN(t%d, %v, %v) = (t%d, %v) want (t%d, %v)",
 254                         dSince(req.t), req.n, maxReserve, dSince(r.timeToAct), r.ok, dSince(req.act), req.ok)
 255         }
 256         return &r
 257 }
 258
 259 func TestSimpleReserve(t *testing.T) {
 260         lim := NewLimiter(10, 2)
 261
 262         runReserve(t, lim, request{t0, 2, t0, true})
 263         runReserve(t, lim, request{t0, 2, t2, true})
 264         runReserve(t, lim, request{t3, 2, t4, true})
 265 }
 266
 267 func TestMix(t *testing.T) {
 268         lim := NewLimiter(10, 2)
 269
 270         runReserve(t, lim, request{t0, 3, t1, false}) // should return false because n > Burst
 271         runReserve(t, lim, request{t0, 2, t0, true})
 272         run(t, lim, []allow{{t1, 2, false}}) // not enought tokens - don't allow
 273         runReserve(t, lim, request{t1, 2, t2, true})
 274         run(t, lim, []allow{{t1, 1, false}}) // negative tokens - don't allow
 275         run(t, lim, []allow{{t3, 1, true}})
 276 }
 277
 278 func TestCancelInvalid(t *testing.T) {
 279         lim := NewLimiter(10, 2)
 280
 281         runReserve(t, lim, request{t0, 2, t0, true})
 282         r := runReserve(t, lim, request{t0, 3, t3, false})
 283         r.CancelAt(t0)                               // should have no effect
 284         runReserve(t, lim, request{t0, 2, t2, true}) // did not get extra tokens
 285 }
 286
 287 func TestCancelLast(t *testing.T) {
 288         lim := NewLimiter(10, 2)
 289
 290         runReserve(t, lim, request{t0, 2, t0, true})
 291         r := runReserve(t, lim, request{t0, 2, t2, true})
 292         r.CancelAt(t1) // got 2 tokens back
 293         runReserve(t, lim, request{t1, 2, t2, true})
 294 }
 295
 296 func TestCancelTooLate(t *testing.T) {
 297         lim := NewLimiter(10, 2)
 298
 299         runReserve(t, lim, request{t0, 2, t0, true})
 300         r := runReserve(t, lim, request{t0, 2, t2, true})
 301         r.CancelAt(t3) // too late to cancel - should have no effect
 302         runReserve(t, lim, request{t3, 2, t4, true})
 303 }
 304
 305 func TestCancel0Tokens(t *testing.T) {
 306         lim := NewLimiter(10, 2)
 307
 308         runReserve(t, lim, request{t0, 2, t0, true})
 309         r := runReserve(t, lim, request{t0, 1, t1, true})
 310         runReserve(t, lim, request{t0, 1, t2, true})
 311         r.CancelAt(t0) // got 0 tokens back
 312         runReserve(t, lim, request{t0, 1, t3, true})
 313 }
 314
 315 func TestCancel1Token(t *testing.T) {
 316         lim := NewLimiter(10, 2)
 317
 318         runReserve(t, lim, request{t0, 2, t0, true})
 319         r := runReserve(t, lim, request{t0, 2, t2, true})
 320         runReserve(t, lim, request{t0, 1, t3, true})
 321         r.CancelAt(t2) // got 1 token back
 322         runReserve(t, lim, request{t2, 2, t4, true})
 323 }
 324
 325 func TestCancelMulti(t *testing.T) {
 326         lim := NewLimiter(10, 4)
 327
 328         runReserve(t, lim, request{t0, 4, t0, true})
 329         rA := runReserve(t, lim, request{t0, 3, t3, true})
 330         runReserve(t, lim, request{t0, 1, t4, true})
 331         rC := runReserve(t, lim, request{t0, 1, t5, true})
 332         rC.CancelAt(t1) // get 1 token back
 333         rA.CancelAt(t1) // get 2 tokens back, as if C was never reserved
 334         runReserve(t, lim, request{t1, 3, t5, true})
 335 }
 336
 337 func TestReserveJumpBack(t *testing.T) {
 338         lim := NewLimiter(10, 2)
 339
 340         runReserve(t, lim, request{t1, 2, t1, true}) // start at t1
 341         runReserve(t, lim, request{t0, 1, t1, true}) // should violate Limit,Burst
 342         runReserve(t, lim, request{t2, 2, t3, true})
 343 }
 344
 345 func TestReserveJumpBackCancel(t *testing.T) {
 346         lim := NewLimiter(10, 2)
 347
 348         runReserve(t, lim, request{t1, 2, t1, true}) // start at t1
 349         r := runReserve(t, lim, request{t1, 2, t3, true})
 350         runReserve(t, lim, request{t1, 1, t4, true})
 351         r.CancelAt(t0)                               // cancel at t0, get 1 token back
 352         runReserve(t, lim, request{t1, 2, t4, true}) // should violate Limit,Burst
 353 }
 354
 355 func TestReserveSetLimit(t *testing.T) {
 356         lim := NewLimiter(5, 2)
 357
 358         runReserve(t, lim, request{t0, 2, t0, true})
 359         runReserve(t, lim, request{t0, 2, t4, true})
 360         lim.SetLimitAt(t2, 10)
 361         runReserve(t, lim, request{t2, 1, t4, true}) // violates Limit and Burst
 362 }
 363
 364 func TestReserveSetBurst(t *testing.T) {
 365         lim := NewLimiter(5, 2)
 366
 367         runReserve(t, lim, request{t0, 2, t0, true})
 368         runReserve(t, lim, request{t0, 2, t4, true})
 369         lim.SetBurstAt(t3, 4)
 370         runReserve(t, lim, request{t0, 4, t9, true}) // violates Limit and Burst
 371 }
 372
 373 func TestReserveSetLimitCancel(t *testing.T) {
 374         lim := NewLimiter(5, 2)
 375
 376         runReserve(t, lim, request{t0, 2, t0, true})
 377         r := runReserve(t, lim, request{t0, 2, t4, true})
 378         lim.SetLimitAt(t2, 10)
 379         r.CancelAt(t2) // 2 tokens back
 380         runReserve(t, lim, request{t2, 2, t3, true})
 381 }
 382
 383 func TestReserveMax(t *testing.T) {
 384         lim := NewLimiter(10, 2)
 385         maxT := d
 386
 387         runReserveMax(t, lim, request{t0, 2, t0, true}, maxT)
 388         runReserveMax(t, lim, request{t0, 1, t1, true}, maxT)  // reserve for close future
 389         runReserveMax(t, lim, request{t0, 1, t2, false}, maxT) // time to act too far in the future
 390 }
 391
 392 type wait struct {
 393         name   string
 394         ctx    context.Context
 395         n      int
 396         delay  int // in multiples of d
 397         nilErr bool
 398 }
 399
 400 func runWait(t *testing.T, lim *Limiter, w wait) {
 401         start := time.Now()
 402         err := lim.WaitN(w.ctx, w.n)
 403         delay := time.Now().Sub(start)
 404         if (w.nilErr && err != nil) || (!w.nilErr && err == nil) || w.delay != dFromDuration(delay) {
 405                 errString := "<nil>"
 406                 if !w.nilErr {
 407                         errString = "<non-nil error>"
 408                 }
 409                 t.Errorf("lim.WaitN(%v, lim, %v) = %v with delay %v ; want %v with delay %v",
 410                         w.name, w.n, err, delay, errString, d*time.Duration(w.delay))
 411         }
 412 }
 413
 414 func TestWaitSimple(t *testing.T) {
 415         lim := NewLimiter(10, 3)
 416
 417         ctx, cancel := context.WithCancel(context.Background())
 418         cancel()
 419         runWait(t, lim, wait{"already-cancelled", ctx, 1, 0, false})
 420
 421         runWait(t, lim, wait{"exceed-burst-error", context.Background(), 4, 0, false})
 422
 423         runWait(t, lim, wait{"act-now", context.Background(), 2, 0, true})
 424         runWait(t, lim, wait{"act-later", context.Background(), 3, 2, true})
 425 }
 426
 427 func TestWaitCancel(t *testing.T) {
 428         lim := NewLimiter(10, 3)
 429
 430         ctx, cancel := context.WithCancel(context.Background())
 431         runWait(t, lim, wait{"act-now", ctx, 2, 0, true}) // after this lim.tokens = 1
 432         go func() {
 433                 time.Sleep(d)
 434                 cancel()
 435         }()
 436         runWait(t, lim, wait{"will-cancel", ctx, 3, 1, false})
 437         // should get 3 tokens back, and have lim.tokens = 2
 438         t.Logf("tokens:%v last:%v lastEvent:%v", lim.tokens, lim.last, lim.lastEvent)
 439         runWait(t, lim, wait{"act-now-after-cancel", context.Background(), 2, 0, true})
 440 }
 441
 442 func TestWaitTimeout(t *testing.T) {
 443         lim := NewLimiter(10, 3)
 444
 445         ctx, cancel := context.WithTimeout(context.Background(), d)
 446         defer cancel()
 447         runWait(t, lim, wait{"act-now", ctx, 2, 0, true})
 448         runWait(t, lim, wait{"w-timeout-err", ctx, 3, 0, false})
 449 }
 450
 451 func TestWaitInf(t *testing.T) {
 452         lim := NewLimiter(Inf, 0)
 453
 454         runWait(t, lim, wait{"exceed-burst-no-error", context.Background(), 3, 0, true})
 455 }
 456
 457 func BenchmarkAllowN(b *testing.B) {
 458         lim := NewLimiter(Every(1*time.Second), 1)
 459         now := time.Now()
 460         b.ReportAllocs()
 461         b.ResetTimer()
 462         b.RunParallel(func(pb *testing.PB) {
 463                 for pb.Next() {
 464                         lim.AllowN(now, 1)
 465                 }
 466         })
 467 }
 468
 469 func BenchmarkWaitNNoDelay(b *testing.B) {
 470         lim := NewLimiter(Limit(b.N), b.N)
 471         ctx := context.Background()
 472         b.ReportAllocs()
 473         b.ResetTimer()
 474         for i := 0; i < b.N; i++ {
 475                 lim.WaitN(ctx, 1)
 476         }
 477 }