1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3// Package clientlimit counts failed authentications per client address and
4// finds the address of a request behind trusted proxies. The HTTP adapters
5// that authenticate callers (smart HTTP, the API) share it.
6package clientlimit
7
8import (
9 "context"
10 "net"
11 "net/http"
12 "net/netip"
13 "slices"
14 "strings"
15 "sync"
16 "time"
17
18 "github.com/bnema/zerowrap"
19)
20
21// Limiter defaults: 10 failed authentications in 10 minutes block the client
22// address until the oldest failure leaves the window.
23const (
24 // MaxFailures is the number of failures in Window that blocks an address.
25 MaxFailures = 10
26 // Window is how long a failure counts.
27 Window = 10 * time.Minute
28
29 // sweepInterval is the least time between two sweeps of expired entries.
30 sweepInterval = Window / 10
31 // maxTracked bounds memory: when the table reaches it, expired entries
32 // are dropped and then the oldest tenth of the rest, in one pass.
33 maxTracked = 100_000
34 // evictFraction is the share of maxTracked evicted at once, so that the
35 // cost of an eviction pass is spread over many failures.
36 evictFraction = 10
37
38 // ipv6Prefix is the width at which IPv6 clients are grouped: one network
39 // (a /64) is what a single subscriber gets, so it counts as one client.
40 ipv6Prefix = 64
41)
42
43// Limiter counts failed authentications per client, in memory. Clients are
44// IPv4 addresses and IPv6 /64 networks. It is safe for concurrent use.
45//
46// Blocked and Fail are O(1) amortized: they touch one entry, a sweep of the
47// expired entries runs at most once per sweepInterval, and a full table is
48// trimmed by a tenth in one pass.
49type Limiter struct {
50 now func() time.Time
51
52 mu sync.Mutex
53 failures map[string][]time.Time // oldest first, all within Window
54 lastSweep time.Time
55}
56
57// NewLimiter builds a limiter. now defaults to time.Now.
58func NewLimiter(now func() time.Time) *Limiter {
59 if now == nil {
60 now = time.Now
61 }
62 return &Limiter{now: now, failures: make(map[string][]time.Time)}
63}
64
65// limiterKey is the identity the limiter counts: an IPv4 address (also when
66// mapped into IPv6), or the /64 network of an IPv6 address. Anything that is
67// not an IP address is used as is.
68func limiterKey(addr string) string {
69 a, err := netip.ParseAddr(addr)
70 if err != nil {
71 return addr
72 }
73 a = a.Unmap()
74 if a.Is4() {
75 return a.String()
76 }
77 return netip.PrefixFrom(a, ipv6Prefix).Masked().String()
78}
79
80// Key returns the identity under which a client address is counted, by the
81// limiter and by the other per-client limits: an IPv4 address, or the /64
82// network of an IPv6 address.
83func Key(addr string) string { return limiterKey(addr) }
84
85// Blocked reports whether addr has used up its failures, and how long until
86// it may try again.
87func (l *Limiter) Blocked(_ context.Context, addr string) (bool, time.Duration) {
88 key := limiterKey(addr)
89 now := l.now()
90 l.mu.Lock()
91 defer l.mu.Unlock()
92 fs := l.prune(key, now)
93 if len(fs) < MaxFailures {
94 return false, 0
95 }
96 // Free again when the failure that makes it MaxFailures leaves the window.
97 wait := fs[len(fs)-MaxFailures].Add(Window).Sub(now)
98 return true, max(wait, time.Second)
99}
100
101// Fail records a failed authentication from addr.
102func (l *Limiter) Fail(ctx context.Context, addr string) {
103 key := limiterKey(addr)
104 now := l.now()
105 l.mu.Lock()
106 defer l.mu.Unlock()
107 l.maintain(now)
108 fs := append(l.prune(key, now), now)
109 if len(fs) > MaxFailures*2 {
110 fs = fs[len(fs)-MaxFailures*2:] // enough to compute the wait
111 }
112 l.failures[key] = fs
113 if len(fs) == MaxFailures {
114 log := zerowrap.FromCtx(ctx)
115 log.Warn().Str("client", key).Msg("client blocked after repeated failed authentications")
116 }
117}
118
119// maintain keeps the table small without a pass per call: expired entries
120// go at most once per sweepInterval, and a table at its bound is trimmed.
121// The caller holds mu.
122func (l *Limiter) maintain(now time.Time) {
123 if now.Sub(l.lastSweep) >= sweepInterval {
124 l.sweep(now)
125 }
126 if len(l.failures) >= maxTracked {
127 l.sweep(now) // a full table may hold expired entries the interval kept
128 l.evictOldest()
129 }
130}
131
132// prune drops the expired failures of key and returns the rest. The caller
133// holds mu.
134func (l *Limiter) prune(key string, now time.Time) []time.Time {
135 fs := l.failures[key]
136 cut := now.Add(-Window)
137 i := 0
138 for i < len(fs) && !fs[i].After(cut) {
139 i++
140 }
141 if i == len(fs) {
142 delete(l.failures, key)
143 return nil
144 }
145 if i > 0 {
146 fs = fs[i:]
147 l.failures[key] = fs
148 }
149 return fs
150}
151
152// sweep drops every expired entry. The caller holds mu.
153func (l *Limiter) sweep(now time.Time) {
154 l.lastSweep = now
155 for key := range l.failures {
156 l.prune(key, now)
157 }
158}
159
160// evictOldest drops the entries whose last failure is the oldest, enough to
161// leave the table a tenth under maxTracked. It is a single pass plus a sort.
162// The caller holds mu.
163func (l *Limiter) evictOldest() {
164 drop := len(l.failures) - (maxTracked - maxTracked/evictFraction)
165 if drop <= 0 {
166 return
167 }
168 type entry struct {
169 key string
170 last time.Time
171 }
172 all := make([]entry, 0, len(l.failures))
173 for key, fs := range l.failures {
174 all = append(all, entry{key, fs[len(fs)-1]})
175 }
176 slices.SortFunc(all, func(a, b entry) int { return a.last.Compare(b.last) })
177 for _, e := range all[:drop] {
178 delete(l.failures, e.key)
179 }
180}
181
182// ClientAddr returns the address a request is attributed to: the host of
183// RemoteAddr, or, when that peer is in one of the trusted proxy networks, the
184// right-most X-Forwarded-For entry that is not itself a trusted proxy. An
185// untrusted peer cannot choose its address: its X-Forwarded-For is ignored.
186// A header that does not parse falls back to the peer.
187func ClientAddr(r *http.Request, trusted []netip.Prefix) string {
188 host, _, err := net.SplitHostPort(r.RemoteAddr)
189 if err != nil {
190 host = r.RemoteAddr
191 }
192 peer, err := netip.ParseAddr(host)
193 if err != nil {
194 return host
195 }
196 peer = peer.Unmap()
197 if len(trusted) == 0 || !isTrusted(peer, trusted) {
198 return peer.String()
199 }
200 var entries []string
201 for _, h := range r.Header.Values("X-Forwarded-For") {
202 for e := range strings.SplitSeq(h, ",") {
203 entries = append(entries, strings.TrimSpace(e))
204 }
205 }
206 for i := len(entries) - 1; i >= 0; i-- {
207 a, err := netip.ParseAddr(entries[i])
208 if err != nil {
209 return peer.String() // garbage from a trusted proxy: do not guess
210 }
211 a = a.Unmap()
212 if !isTrusted(a, trusted) {
213 return a.String()
214 }
215 }
216 return peer.String()
217}
218
219func isTrusted(a netip.Addr, trusted []netip.Prefix) bool {
220 for _, p := range trusted {
221 if p.Contains(a) {
222 return true
223 }
224 }
225 return false
226}