Git designed for AI agents.
package limiter
import (
"context"
"errors"
"fmt"
"strconv"
"sync"
"testing"
"time"
"github.com/feder-cr/git-ai/internal/structerr"
"github.com/feder-cr/git-ai/internal/testhelper"
"github.com/feder-cr/git-ai/proto/go/gitalypb"
"github.com/stretchr/testify/assert"
"github.com/stretchr/testify/require"
"google.golang.org/grpc/codes"
"google.golang.org/protobuf/types/known/durationpb"
)
type counter struct {
sync.Mutex
max int
current int
queued int
dequeued int
enter int
exit int
droppedSize int
droppedTime int
}
func (c *counter) up() {
c.Lock()
defer c.Unlock()
c.current = c.current + 1
if c.current > c.max {
c.max = c.current
}
}
func (c *counter) down() {
c.Lock()
defer c.Unlock()
c.current = c.current - 1
}
func (c *counter) currentVal() int {
c.Lock()
defer c.Unlock()
return c.current
}
func (c *counter) Queued(context.Context, string, int) {
c.Lock()
defer c.Unlock()
c.queued++
}
func (c *counter) Dequeued(context.Context) {
c.Lock()
defer c.Unlock()
c.dequeued++
}
func (c *counter) Enter(context.Context, int, time.Duration) {
c.Lock()
defer c.Unlock()
c.enter++
}
func (c *counter) Exit(context.Context) {
c.Lock()
defer c.Unlock()
c.exit++
}
func (c *counter) Dropped(_ context.Context, _ string, _ int, _ int, _ time.Duration, reason string) {
c.Lock()
defer c.Unlock()
switch reason {
case "max_time":
c.droppedTime++
case "max_size":
c.droppedSize++
}
}
func TestLimiter_static(t *testing.T) {
t.Parallel()
ctx := testhelper.Context(t)
// Limiter works with static limits regardless of semaphore implementation
testLimiterStatic(t, ctx)
}
func testLimiterStatic(t *testing.T, ctx context.Context) {
tests := []struct {
name string
concurrency int
maxConcurrency int
iterations int
buckets int
wantMonitorCalls bool
}{
{
name: "single",
concurrency: 1,
maxConcurrency: 1,
iterations: 1,
buckets: 1,
wantMonitorCalls: true,
},
{
name: "two-at-a-time",
concurrency: 100,
maxConcurrency: 2,
iterations: 10,
buckets: 1,
wantMonitorCalls: true,
},
{
name: "two-by-two",
concurrency: 100,
maxConcurrency: 2,
iterations: 4,
buckets: 2,
wantMonitorCalls: true,
},
{
name: "no-limit",
concurrency: 10,
maxConcurrency: 0,
iterations: 200,
buckets: 1,
wantMonitorCalls: false,
},
{
name: "wide-spread",
concurrency: 1000,
maxConcurrency: 2,
// We use a long delay here to prevent flakiness in CI. If the delay is
// too short, the first goroutines to enter the critical section will be
// gone before we hit the intended maximum concurrency.
iterations: 40,
buckets: 50,
wantMonitorCalls: true,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
t.Parallel()
expectedGaugeMax := tt.maxConcurrency * tt.buckets
if tt.maxConcurrency <= 0 {
expectedGaugeMax = tt.concurrency
}
gauge := &counter{}
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("staticLimit", AdaptiveSetting{Initial: tt.maxConcurrency}),
0,
0,
gauge,
)
wg := sync.WaitGroup{}
wg.Add(tt.concurrency)
full := sync.NewCond(&sync.Mutex{})
// primePump waits for the gauge to reach the minimum
// expected max concurrency so that the limiter is
// "warmed" up before proceeding with the test
primePump := func() {
full.L.Lock()
defer full.L.Unlock()
gauge.up()
if gauge.max >= expectedGaugeMax {
full.Broadcast()
return
}
full.Wait() // wait until full is broadcast
}
// We know of an edge case that can lead to the rate limiter
// occasionally letting one or two extra goroutines run
// concurrently.
for c := 0; c < tt.concurrency; c++ {
go func(counter int) {
for i := 0; i < tt.iterations; i++ {
lockKey := strconv.Itoa((i ^ counter) % tt.buckets)
_, err := limiter.Limit(ctx, lockKey, func() (interface{}, error) {
primePump()
current := gauge.currentVal()
require.True(t, current <= expectedGaugeMax, "Expected the number of concurrent operations (%v) to not exceed the maximum concurrency (%v)", current, expectedGaugeMax)
require.True(t, limiter.countSemaphores() <= tt.buckets, "Expected the number of semaphores (%v) to be lte number of buckets (%v)", limiter.countSemaphores(), tt.buckets)
gauge.down()
return nil, nil
})
require.NoError(t, err)
}
wg.Done()
}(c)
}
wg.Wait()
assert.Equal(t, expectedGaugeMax, gauge.max, "Expected maximum concurrency")
assert.Equal(t, 0, gauge.current)
assert.Equal(t, 0, limiter.countSemaphores())
var wantMonitorCallCount int
if tt.wantMonitorCalls {
wantMonitorCallCount = tt.concurrency * tt.iterations
} else {
wantMonitorCallCount = 0
}
assert.Equal(t, wantMonitorCallCount, gauge.enter)
assert.Equal(t, wantMonitorCallCount, gauge.exit)
assert.Equal(t, wantMonitorCallCount, gauge.queued)
assert.Equal(t, wantMonitorCallCount, gauge.dequeued)
})
}
}
func TestLimiter_dynamic(t *testing.T) {
t.Parallel()
ctx := testhelper.Context(t)
testLimiterDynamic(t, ctx)
}
func testLimiterDynamic(t *testing.T, ctx context.Context) {
t.Run("increase dynamic limit when there is no queuing request", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
// Update the limit to 7
limit.Update(7)
// 2 more requests acquired the token. This proves the limit is expanded
release2, waitAfterRelease2 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 2)
require.Equal(t, 7, gauge.enter)
close(release1)
close(release2)
waitAfterRelease1()
waitAfterRelease2()
require.Equal(t, 7, gauge.exit)
})
t.Run("decrease dynamic limit when there is no queuing request", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// 3 requests acquired the tokens, 2 slots left
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 3)
require.Equal(t, 3, gauge.enter)
require.Equal(t, 3, gauge.queued)
// Update the limit to 3
limit.Update(3)
// 2 requests are put in queue, meaning the limit shrinks down
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 2)
require.Equal(t, 3, gauge.enter)
require.Equal(t, 5, gauge.queued)
// Release first 3 requests
close(release1)
waitAfterRelease1()
// Now the last 2 requests can acquire token
waitAcquired2()
require.Equal(t, 5, gauge.enter)
require.Equal(t, 5, gauge.queued)
require.Equal(t, 3, gauge.exit)
// Release the last patch
close(release2)
waitAfterRelease2()
require.Equal(t, 5, gauge.exit)
})
t.Run("increase dynamic limit more than the number of queuing requests", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
// 2 requests waiting in the queue
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 2)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 7, gauge.queued)
// Update the limit to 7
limit.Update(7)
// Wait for the other 2 requests acquired the token. This proves the limiter is expanded
waitAcquired2()
require.Equal(t, 7, gauge.enter)
close(release1)
close(release2)
waitAfterRelease1()
waitAfterRelease2()
require.Equal(t, 7, gauge.exit)
})
t.Run("increase dynamic limit less than the number of queuing requests", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
// 2 requests waiting in the queue
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 2)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 7, gauge.queued)
// 5 more requests waiting in the queue
waitAcquired3, release3, waitAfterRelease3 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 12, gauge.queued)
// Update the limit to 7.
limit.Update(7)
// Release first 5 requests, all requests should fit in the queue now.
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
waitAcquired2()
waitAcquired3()
require.Equal(t, 12, gauge.enter)
// Now release all requests
close(release2)
close(release3)
waitAfterRelease2()
waitAfterRelease3()
require.Equal(t, 12, gauge.exit)
})
t.Run("decrease dynamic limit less than the number of concurrent requests", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
// Update the limit to 3
limit.Update(3)
// 3 requests are put in queue
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 3)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 8, gauge.queued)
// Release the first 5 requests
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
// Now the last 3 requests acquire the tokens
waitAcquired2()
require.Equal(t, 8, gauge.enter)
// 1 more request is put in queue, meaning the limit has correctly shrunk down to 3.
waitAcquired3, release3, waitAfterRelease3 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 1)
require.Equal(t, 8, gauge.enter)
require.Equal(t, 9, gauge.queued)
// Release the second 3 requests
close(release2)
waitAfterRelease2()
require.Equal(t, 8, gauge.exit)
// The last request acquires the token
waitAcquired3()
require.Equal(t, 9, gauge.enter)
// Release the last request
close(release3)
waitAfterRelease3()
require.Equal(t, 9, gauge.exit)
})
t.Run("increase and decrease dynamic limit multiple times", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 10, 0, gauge)
// Update the limit to 7
limit.Update(7)
// 5 requests acquired the tokens
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
// Update the limit to 3
limit.Update(3)
// 3 requests are put in queue
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 3)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 8, gauge.queued)
// Update the limit to 10
limit.Update(10)
// All existing requests acquire the tokens
waitAcquired2()
require.Equal(t, 8, gauge.enter)
// 2 more requests
release3, waitAfterRelease3 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 2)
require.Equal(t, 10, gauge.enter)
// Update the limit to 1
limit.Update(1)
// Now release all of them
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
close(release2)
waitAfterRelease2()
require.Equal(t, 8, gauge.exit)
close(release3)
waitAfterRelease3()
require.Equal(t, 10, gauge.exit)
})
t.Run("increase the limit when the queue is full", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 1, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
// Mind the queue length here
limiter := NewConcurrencyLimiter(limit, 5, 0, gauge)
// 1 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 1)
require.Equal(t, 1, gauge.enter)
require.Equal(t, 1, gauge.queued)
// 5 requests queuing for the tokens, the queue is full now
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 1, gauge.enter)
require.Equal(t, 6, gauge.queued)
// Limiter rejects new request
ensureOperationsRejectedWhenQueueFull(t, ctx, "1", limiter)
// Update the limit
limit.Update(6)
waitAcquired2()
require.Equal(t, 6, gauge.enter)
// 5 requests queuing for the tokens, the queue is full now
waitAcquired3, release3, waitAfterRelease3 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 6, gauge.enter)
require.Equal(t, 11, gauge.queued)
// Limiter rejects new request
ensureOperationsRejectedWhenQueueFull(t, ctx, "1", limiter)
// Clean up
close(release1)
close(release2)
waitAfterRelease1()
waitAfterRelease2()
require.Equal(t, 6, gauge.exit)
waitAcquired3()
require.Equal(t, 11, gauge.enter)
close(release3)
waitAfterRelease3()
})
t.Run("decrease the limit when the queue is full", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
// Mind the queue length here
limiter := NewConcurrencyLimiter(limit, 3, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 5, gauge.queued)
// 3 requests queuing for the tokens, the queue is full now
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 3)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 8, gauge.queued)
// Limiter rejects new request
ensureOperationsRejectedWhenQueueFull(t, ctx, "1", limiter)
// Update the limit.
limit.Update(3)
// The queue is still full
ensureOperationsRejectedWhenQueueFull(t, ctx, "1", limiter)
// Release first 5 requests and let the last 3 requests in
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
waitAcquired2()
require.Equal(t, 8, gauge.enter)
// Another 3 requests in queue. The queue is still full, meaning the concurrency is 3 and the queue is still 3.
waitAcquired3, release3, waitAfterRelease3 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 3)
require.Equal(t, 8, gauge.enter)
require.Equal(t, 11, gauge.queued)
ensureOperationsRejectedWhenQueueFull(t, ctx, "1", limiter)
// Clean up
close(release2)
waitAfterRelease2()
require.Equal(t, 8, gauge.exit)
waitAcquired3()
require.Equal(t, 11, gauge.enter)
close(release3)
waitAfterRelease3()
require.Equal(t, 11, gauge.exit)
})
t.Run("dynamic limit works without queuing", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
// No maxQueueLength, it means the limiter accepts unlimited requests to be queued
limiter := NewConcurrencyLimiter(limit, 0, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 5, gauge.queued)
// 5 more requests
waitAcquired2, release2, waitAfterRelease2 := spawnAndWaitQueued(t, ctx, "1", limiter, gauge, 5)
// Update the limit.
limit.Update(10)
// All of them acquired the tokens
waitAcquired2()
require.Equal(t, 10, gauge.enter)
// Clean up
close(release1)
close(release2)
waitAfterRelease1()
waitAfterRelease2()
require.Equal(t, 10, gauge.exit)
})
t.Run("dynamic limit works with context timeout", func(t *testing.T) {
ctxWithTimeout, cancel, simulateTimeout := testhelper.ContextWithSimulatedTimeout(ctx)
defer cancel()
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 0, 1*time.Millisecond, gauge)
limiter.SetWaitTimeoutContext = func() context.Context { return ctxWithTimeout }
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 5, gauge.queued)
errors := make(chan error, 10)
// 5 requests in queue
spawnQueuedAndCollectErrors(ctxWithTimeout, "1", limiter, gauge, 5, errors)
// Decrease the limit
limit.Update(3)
// 5 more requests in queue
spawnQueuedAndCollectErrors(ctxWithTimeout, "1", limiter, gauge, 5, errors)
// Trigger timeout event
simulateTimeout()
for i := 0; i < 10; i++ {
require.EqualError(t, <-errors, "maximum time in concurrency queue reached")
}
// Other goroutines exit as normal
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
})
t.Run("dynamic limit works with context cancellation", func(t *testing.T) {
ctx2, cancel := context.WithCancel(ctx)
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 0, 0, gauge)
// 5 requests acquired the tokens, the limiter is full now
release1, waitAfterRelease1 := spawnAndWaitAcquired(t, ctx, "1", limiter, gauge, 5)
require.Equal(t, 5, gauge.enter)
require.Equal(t, 5, gauge.queued)
errors := make(chan error, 10)
// 5 requests in queue
spawnQueuedAndCollectErrors(ctx2, "1", limiter, gauge, 5, errors)
// Decrease the limit
limit.Update(3)
// 5 more requests in queue
spawnQueuedAndCollectErrors(ctx2, "1", limiter, gauge, 5, errors)
// Trigger context cancellation
cancel()
for i := 0; i < 10; i++ {
require.EqualError(t, <-errors, "unexpected error when dequeueing request: context canceled")
}
// Other goroutines exit as normal
close(release1)
waitAfterRelease1()
require.Equal(t, 5, gauge.exit)
})
t.Run("dynamic limit works with multiple buckets", func(t *testing.T) {
limit := NewAdaptiveLimit("dynamicLimit", AdaptiveSetting{Initial: 5, Max: 10, Min: 1})
gauge := &blockingQueueCounter{queuedCh: make(chan struct{})}
limiter := NewConcurrencyLimiter(limit, 5, 0, gauge)
var releaseChans []chan struct{}
var waitAcquireFuncs, waitReleaseFuncs []func()
// 5 * 5 requests acquired tokens
for i := 1; i <= 5; i++ {
release, waitAfterRelease := spawnAndWaitAcquired(t, ctx, fmt.Sprintf("%d", i), limiter, gauge, 5)
releaseChans = append(releaseChans, release)
waitReleaseFuncs = append(waitReleaseFuncs, waitAfterRelease)
}
require.Equal(t, 25, gauge.enter)
// 1 + 2 + 3 + 4 + 5 requests are in queue
for i := 1; i <= 5; i++ {
waitAcquired, release, waitAfterRelease := spawnAndWaitQueued(t, ctx, fmt.Sprintf("%d", i), limiter, gauge, i)
waitAcquireFuncs = append(waitAcquireFuncs, waitAcquired)
releaseChans = append(releaseChans, release)
waitReleaseFuncs = append(waitReleaseFuncs, waitAfterRelease)
}
require.Equal(t, 25, gauge.enter)
require.Equal(t, 40, gauge.queued)
// Update limit, enough for all requests
limit.Update(10)
// All requests acquired tokens now
for _, wait := range waitAcquireFuncs {
wait()
}
require.Equal(t, 40, gauge.enter)
// Release all
for _, release := range releaseChans {
close(release)
}
for _, wait := range waitReleaseFuncs {
wait()
}
require.Equal(t, 40, gauge.exit)
})
}
// spawnAndWaitAcquired spawns N goroutines that wait for the limiter. They wait until all of them acquire the limiter
// token before exiting. This function returns a channel to control token release and a function to wait until all
// goroutines finish.
func spawnAndWaitAcquired(t *testing.T, ctx context.Context, bucket string, limiter *ConcurrencyLimiter, gauge *blockingQueueCounter, n int) (chan struct{}, func()) {
var acquireWg, releaseWg sync.WaitGroup
release := make(chan struct{})
for i := 0; i < n; i++ {
acquireWg.Add(1)
releaseWg.Add(1)
go func() {
defer releaseWg.Done()
_, err := limiter.Limit(ctx, bucket, func() (resp interface{}, err error) {
acquireWg.Done()
<-release
return nil, nil
})
require.NoError(t, err)
}()
}
for i := 0; i < n; i++ {
<-gauge.queuedCh
gauge.queued++
}
acquireWg.Wait()
return release, releaseWg.Wait
}
// spawnAndWaitQueued spawns N goroutines that wait for the limiter. They wait until all of them are queued. This
// function returns a function to wait for channel to acquire the token, a channel to control token release, and a
// function to wait until all goroutines finish.
func spawnAndWaitQueued(t *testing.T, ctx context.Context, bucket string, limiter *ConcurrencyLimiter, gauge *blockingQueueCounter, n int) (func(), chan struct{}, func()) {
var acquireWg, releaseWg sync.WaitGroup
release := make(chan struct{})
for i := 0; i < n; i++ {
acquireWg.Add(1)
releaseWg.Add(1)
go func() {
defer releaseWg.Done()
_, err := limiter.Limit(ctx, bucket, func() (resp interface{}, err error) {
acquireWg.Done()
<-release
return nil, nil
})
require.NoError(t, err)
}()
}
for i := 0; i < n; i++ {
<-gauge.queuedCh
gauge.queued++
}
return acquireWg.Wait, release, releaseWg.Wait
}
// spawnQueueAndCollectErrors spawns N goroutines that should error when attempting to wait for the limiter. Errors are
// collected into the input errors channel. The function returned after N goroutines are already waiting the queue.
func spawnQueuedAndCollectErrors(ctx context.Context, bucket string, limiter *ConcurrencyLimiter, gauge *blockingQueueCounter, n int, errors chan error) {
for i := 0; i < n; i++ {
go func() {
_, err := limiter.Limit(ctx, bucket, func() (interface{}, error) {
return nil, fmt.Errorf("should not call")
})
errors <- err
}()
}
for i := 0; i < n; i++ {
<-gauge.queuedCh
gauge.queued++
}
}
func ensureOperationsRejectedWhenQueueFull(t *testing.T, ctx context.Context, bucket string, limiter *ConcurrencyLimiter) {
_, err := limiter.Limit(ctx, bucket, func() (interface{}, error) {
return nil, fmt.Errorf("should not call")
})
require.EqualError(t, err, "maximum queue size reached")
}
type blockingQueueCounter struct {
counter
queuedCh chan struct{}
}
// Queued will block on a channel. We need a way to synchronize on when a Limiter has attempted to acquire
// a semaphore but has not yet. The caller can use the channel to wait for many requests to be queued
func (b *blockingQueueCounter) Queued(context.Context, string, int) {
b.queuedCh <- struct{}{}
}
func TestConcurrencyLimiter_queueLimit(t *testing.T) {
queueLimit := 10
ctx := testhelper.Context(t)
monitorCh := make(chan struct{})
monitor := &blockingQueueCounter{queuedCh: monitorCh}
ch := make(chan struct{})
limiter := NewConcurrencyLimiter(NewAdaptiveLimit("staticLimit", AdaptiveSetting{Initial: 1}), queueLimit, 0, monitor)
// occupied with one live request that takes a long time to complete
go func() {
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
ch <- struct{}{}
<-ch
return nil, nil
})
require.NoError(t, err)
}()
<-monitorCh
<-ch
var wg sync.WaitGroup
// fill up the queue
for i := 0; i < queueLimit; i++ {
wg.Add(1)
go func() {
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
return nil, nil
})
require.NoError(t, err)
wg.Done()
}()
}
var queued int
for range monitorCh {
queued++
if queued == queueLimit {
break
}
}
errChan := make(chan error, 1)
go func() {
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
return nil, nil
})
errChan <- err
}()
err := <-errChan
assert.Error(t, err)
var structErr structerr.Error
require.True(t, errors.As(err, &structErr))
details := structErr.Details()
require.Len(t, details, 1)
limitErr, ok := details[0].(*gitalypb.LimitError)
require.True(t, ok)
assert.Equal(t, ErrMaxQueueSize.Error(), limitErr.GetErrorMessage())
assert.Equal(t, durationpb.New(0), limitErr.GetRetryAfter())
assert.Equal(t, monitor.droppedSize, 1)
close(ch)
wg.Wait()
}
type blockingDequeueCounter struct {
counter
dequeuedCh chan struct{}
}
// Dequeued will block on a channel. We need a way to synchronize on when a Limiter has successfully
// acquired a semaphore but has not yet. The caller can use the channel to wait for many requests to
// be queued
func (b *blockingDequeueCounter) Dequeued(context.Context) {
b.dequeuedCh <- struct{}{}
}
func TestLimitConcurrency_queueWaitTime(t *testing.T) {
t.Parallel()
ctx := testhelper.Context(t)
limiterCtx, cancel, simulateTimeout := testhelper.ContextWithSimulatedTimeout(ctx)
defer cancel()
dequeuedCh := make(chan struct{})
monitor := &blockingDequeueCounter{dequeuedCh: dequeuedCh}
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("staticLimit", AdaptiveSetting{Initial: 1}),
0,
1*time.Millisecond,
monitor,
)
limiter.SetWaitTimeoutContext = func() context.Context { return limiterCtx }
ch := make(chan struct{})
var wg sync.WaitGroup
wg.Add(1)
go func() {
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
<-ch
return nil, nil
})
require.NoError(t, err)
wg.Done()
}()
<-dequeuedCh
simulateTimeout()
errChan := make(chan error)
go func() {
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
return nil, nil
})
errChan <- err
}()
<-dequeuedCh
err := <-errChan
var structErr structerr.Error
require.True(t, errors.As(err, &structErr))
details := structErr.Details()
require.Len(t, details, 1)
limitErr, ok := details[0].(*gitalypb.LimitError)
require.True(t, ok)
testhelper.RequireGrpcCode(t, err, codes.ResourceExhausted)
assert.Equal(t, ErrMaxQueueTime.Error(), limitErr.GetErrorMessage())
assert.Equal(t, durationpb.New(0).AsDuration(), limitErr.GetRetryAfter().AsDuration())
assert.Equal(t, monitor.droppedTime, 1)
close(ch)
wg.Wait()
}
func TestLimitConcurrency_queueWaitTimeRealTimeout(t *testing.T) {
t.Parallel()
ctx := testhelper.Context(t)
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("staticLimit", AdaptiveSetting{Initial: 1}),
0,
// This test setups two requests:
// - The first one is eligible. It enters the handler and blocks the queue.
// - The second request is blocked until timeout.
// Both of them share this timeout. Internally, the limiter creates a context
// deadline to reject timed-out requests. If it's set too low, there's a tiny
// possibility that the context reaches the deadline when the limiter checks the
// request. Thus, setting a reasonable timeout here and adding some retry
// attempts below make the test stable.
100*time.Millisecond,
&counter{},
)
waitAcquire := make(chan struct{})
release := make(chan struct{})
var wg sync.WaitGroup
wg.Add(1)
go func() {
defer wg.Done()
// Retry a couple of time, just in case the test runs on a very slow machine that invalidates
// the test. If the limiter still cannot permit the request after 3 times, something must go
// wrong horribly.
for i := 0; i < 3; i++ {
if _, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
close(waitAcquire)
<-release
return nil, nil
}); err == nil {
return
}
}
require.FailNow(t, "the first request is supposed to enter the test server's handler")
}()
<-waitAcquire
_, err := limiter.Limit(ctx, "key", func() (interface{}, error) {
return nil, nil
})
var structErr structerr.Error
require.True(t, errors.As(err, &structErr))
details := structErr.Details()
require.Len(t, details, 1)
limitErr, ok := details[0].(*gitalypb.LimitError)
require.True(t, ok)
testhelper.RequireGrpcCode(t, err, codes.ResourceExhausted)
assert.Equal(t, ErrMaxQueueTime.Error(), limitErr.GetErrorMessage())
assert.Equal(t, durationpb.New(0).AsDuration(), limitErr.GetRetryAfter().AsDuration())
close(release)
}
// TestConcurrencyLimiter_globalLimit asserts that a limiter carrying both a per-key and a global
// budget admits a call only when it fits within both, and rejects it on whichever of the two runs
// out of room first.
func TestConcurrencyLimiter_globalLimit(t *testing.T) {
// The blocking monitors synchronize these tests, so they must not run in parallel.
ctx := testhelper.Context(t)
requireMaxQueueSize := func(t *testing.T, err error) {
t.Helper()
require.Error(t, err)
var structErr structerr.Error
require.True(t, errors.As(err, &structErr))
details := structErr.Details()
require.Len(t, details, 1)
limitErr, ok := details[0].(*gitalypb.LimitError)
require.True(t, ok)
require.Equal(t, ErrMaxQueueSize.Error(), limitErr.GetErrorMessage())
}
t.Run("the global budget binds across keys", func(t *testing.T) {
perKeyMonitor := &counter{}
globalCh := make(chan struct{})
globalMonitor := &blockingQueueCounter{queuedCh: globalCh}
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("perKey", AdaptiveSetting{Initial: 5}), 5, 0, perKeyMonitor,
WithGlobalLimit(NewAdaptiveLimit("global", AdaptiveSetting{Initial: 1}), 1, 0, globalMonitor),
)
var wg sync.WaitGroup
ch := make(chan struct{})
// The first key takes the only global concurrency token.
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.1", func() (interface{}, error) {
ch <- struct{}{}
<-ch
return nil, nil
})
assert.NoError(t, err)
}()
<-globalCh
<-ch
// A second key fills the single global queue slot.
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.2", func() (interface{}, error) {
return nil, nil
})
assert.NoError(t, err)
}()
<-globalCh
// A third key has a per-key budget of its own but still finds the global budget
// full.
errChan := make(chan error, 1)
go func() {
_, err := limiter.Limit(ctx, "192.0.2.3", func() (interface{}, error) {
return nil, nil
})
errChan <- err
}()
requireMaxQueueSize(t, <-errChan)
assert.Equal(t, 1, globalMonitor.droppedSize)
assert.Equal(t, 0, perKeyMonitor.droppedSize)
close(ch)
wg.Wait()
})
t.Run("the per-key budget binds within one key", func(t *testing.T) {
perKeyCh := make(chan struct{})
perKeyMonitor := &blockingQueueCounter{queuedCh: perKeyCh}
globalMonitor := &counter{}
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("perKey", AdaptiveSetting{Initial: 1}), 1, 0, perKeyMonitor,
WithGlobalLimit(NewAdaptiveLimit("global", AdaptiveSetting{Initial: 10}), 10, 0, globalMonitor),
)
var wg sync.WaitGroup
ch := make(chan struct{})
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.1", func() (interface{}, error) {
ch <- struct{}{}
<-ch
return nil, nil
})
assert.NoError(t, err)
}()
<-perKeyCh
<-ch
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.1", func() (interface{}, error) {
return nil, nil
})
assert.NoError(t, err)
}()
<-perKeyCh
// The global budget has ample room, but the key has exhausted its own.
errChan := make(chan error, 1)
go func() {
_, err := limiter.Limit(ctx, "192.0.2.1", func() (interface{}, error) {
return nil, nil
})
errChan <- err
}()
requireMaxQueueSize(t, <-errChan)
assert.Equal(t, 1, perKeyMonitor.droppedSize)
assert.Equal(t, 0, globalMonitor.droppedSize)
// Only the running call ever reached the global budget.
assert.Equal(t, 1, globalMonitor.enter)
close(ch)
wg.Wait()
})
t.Run("a per-key limit of zero leaves the global budget applying alone", func(t *testing.T) {
perKeyMonitor := &counter{}
globalCh := make(chan struct{})
globalMonitor := &blockingQueueCounter{queuedCh: globalCh}
limiter := NewConcurrencyLimiter(
NewAdaptiveLimit("perKey", AdaptiveSetting{Initial: 0}), 0, 0, perKeyMonitor,
WithGlobalLimit(NewAdaptiveLimit("global", AdaptiveSetting{Initial: 1}), 1, 0, globalMonitor),
)
var wg sync.WaitGroup
ch := make(chan struct{})
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.1", func() (interface{}, error) {
ch <- struct{}{}
<-ch
return nil, nil
})
assert.NoError(t, err)
}()
<-globalCh
<-ch
wg.Add(1)
go func() {
defer wg.Done()
_, err := limiter.Limit(ctx, "192.0.2.2", func() (interface{}, error) {
return nil, nil
})
assert.NoError(t, err)
}()
<-globalCh
errChan := make(chan error, 1)
go func() {
_, err := limiter.Limit(ctx, "192.0.2.3", func() (interface{}, error) {
return nil, nil
})
errChan <- err
}()
requireMaxQueueSize(t, <-errChan)
assert.Equal(t, 1, globalMonitor.droppedSize)
// No per-key semaphore is ever created when the per-key limit is zero.
assert.Equal(t, 0, limiter.countSemaphores())
assert.Equal(t, 0, perKeyMonitor.queued)
close(ch)
wg.Wait()
})
}