diff options
Diffstat (limited to 'ratelimiter')
| -rw-r--r-- | ratelimiter/ratelimiter.go | 149 | ||||
| -rw-r--r-- | ratelimiter/ratelimiter_test.go | 98 |
2 files changed, 247 insertions, 0 deletions
diff --git a/ratelimiter/ratelimiter.go b/ratelimiter/ratelimiter.go new file mode 100644 index 0000000..006900a --- /dev/null +++ b/ratelimiter/ratelimiter.go @@ -0,0 +1,149 @@ +package ratelimiter + +/* Copyright (C) 2015-2017 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + +/* This file contains a port of the rate-limiter from the linux kernel version */ + +import ( + "net" + "sync" + "time" +) + +const ( + packetsPerSecond = 20 + packetsBurstable = 5 + garbageCollectTime = time.Second + packetCost = 1000000000 / packetsPerSecond + maxTokens = packetCost * packetsBurstable +) + +type RatelimiterEntry struct { + mutex sync.Mutex + lastTime time.Time + tokens int64 +} + +type Ratelimiter struct { + mutex sync.RWMutex + stop chan struct{} + tableIPv4 map[[net.IPv4len]byte]*RatelimiterEntry + tableIPv6 map[[net.IPv6len]byte]*RatelimiterEntry +} + +func (rate *Ratelimiter) Close() { + rate.mutex.Lock() + defer rate.mutex.Unlock() + + if rate.stop != nil { + close(rate.stop) + } +} + +func (rate *Ratelimiter) Init() { + rate.mutex.Lock() + defer rate.mutex.Unlock() + + // stop any ongoing garbage collection routine + + if rate.stop != nil { + close(rate.stop) + } + + rate.stop = make(chan struct{}) + rate.tableIPv4 = make(map[[net.IPv4len]byte]*RatelimiterEntry) + rate.tableIPv6 = make(map[[net.IPv6len]byte]*RatelimiterEntry) + + // start garbage collection routine + + go func() { + timer := time.NewTimer(time.Second) + for { + select { + case <-rate.stop: + return + case <-timer.C: + func() { + rate.mutex.Lock() + defer rate.mutex.Unlock() + + for key, entry := range rate.tableIPv4 { + entry.mutex.Lock() + if time.Now().Sub(entry.lastTime) > garbageCollectTime { + delete(rate.tableIPv4, key) + } + entry.mutex.Unlock() + } + + for key, entry := range rate.tableIPv6 { + entry.mutex.Lock() + if time.Now().Sub(entry.lastTime) > garbageCollectTime { + delete(rate.tableIPv6, key) + } + entry.mutex.Unlock() + } + }() + timer.Reset(time.Second) + } + } + }() +} + +func (rate *Ratelimiter) Allow(ip net.IP) bool { + var entry *RatelimiterEntry + var KeyIPv4 [net.IPv4len]byte + var KeyIPv6 [net.IPv6len]byte + + // lookup entry + + IPv4 := ip.To4() + IPv6 := ip.To16() + + rate.mutex.RLock() + + if IPv4 != nil { + copy(KeyIPv4[:], IPv4) + entry = rate.tableIPv4[KeyIPv4] + } else { + copy(KeyIPv6[:], IPv6) + entry = rate.tableIPv6[KeyIPv6] + } + + rate.mutex.RUnlock() + + // make new entry if not found + + if entry == nil { + rate.mutex.Lock() + entry = new(RatelimiterEntry) + entry.tokens = maxTokens - packetCost + entry.lastTime = time.Now() + if IPv4 != nil { + rate.tableIPv4[KeyIPv4] = entry + } else { + rate.tableIPv6[KeyIPv6] = entry + } + rate.mutex.Unlock() + return true + } + + // add tokens to entry + + entry.mutex.Lock() + now := time.Now() + entry.tokens += now.Sub(entry.lastTime).Nanoseconds() + entry.lastTime = now + if entry.tokens > maxTokens { + entry.tokens = maxTokens + } + + // subtract cost of packet + + if entry.tokens > packetCost { + entry.tokens -= packetCost + entry.mutex.Unlock() + return true + } + entry.mutex.Unlock() + return false +} diff --git a/ratelimiter/ratelimiter_test.go b/ratelimiter/ratelimiter_test.go new file mode 100644 index 0000000..37339ee --- /dev/null +++ b/ratelimiter/ratelimiter_test.go @@ -0,0 +1,98 @@ +package ratelimiter + +import ( + "net" + "testing" + "time" +) + +type RatelimiterResult struct { + allowed bool + text string + wait time.Duration +} + +func TestRatelimiter(t *testing.T) { + + var ratelimiter Ratelimiter + var expectedResults []RatelimiterResult + + Nano := func(nano int64) time.Duration { + return time.Nanosecond * time.Duration(nano) + } + + Add := func(res RatelimiterResult) { + expectedResults = append( + expectedResults, + res, + ) + } + + for i := 0; i < packetsBurstable; i++ { + Add(RatelimiterResult{ + allowed: true, + text: "inital burst", + }) + } + + Add(RatelimiterResult{ + allowed: false, + text: "after burst", + }) + + Add(RatelimiterResult{ + allowed: true, + wait: Nano(time.Second.Nanoseconds() / packetsPerSecond), + text: "filling tokens for single packet", + }) + + Add(RatelimiterResult{ + allowed: false, + text: "not having refilled enough", + }) + + Add(RatelimiterResult{ + allowed: true, + wait: 2 * (Nano(time.Second.Nanoseconds() / packetsPerSecond)), + text: "filling tokens for two packet burst", + }) + + Add(RatelimiterResult{ + allowed: true, + text: "second packet in 2 packet burst", + }) + + Add(RatelimiterResult{ + allowed: false, + text: "packet following 2 packet burst", + }) + + ips := []net.IP{ + net.ParseIP("127.0.0.1"), + net.ParseIP("192.168.1.1"), + net.ParseIP("172.167.2.3"), + net.ParseIP("97.231.252.215"), + net.ParseIP("248.97.91.167"), + net.ParseIP("188.208.233.47"), + net.ParseIP("104.2.183.179"), + net.ParseIP("72.129.46.120"), + net.ParseIP("2001:0db8:0a0b:12f0:0000:0000:0000:0001"), + net.ParseIP("f5c2:818f:c052:655a:9860:b136:6894:25f0"), + net.ParseIP("b2d7:15ab:48a7:b07c:a541:f144:a9fe:54fc"), + net.ParseIP("a47b:786e:1671:a22b:d6f9:4ab0:abc7:c918"), + net.ParseIP("ea1e:d155:7f7a:98fb:2bf5:9483:80f6:5445"), + net.ParseIP("3f0e:54a2:f5b4:cd19:a21d:58e1:3746:84c4"), + } + + ratelimiter.Init() + + for i, res := range expectedResults { + time.Sleep(res.wait) + for _, ip := range ips { + allowed := ratelimiter.Allow(ip) + if allowed != res.allowed { + t.Fatal("Test failed for", ip.String(), ", on:", i, "(", res.text, ")", "expected:", res.allowed, "got:", allowed) + } + } + } +} |