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