1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package clientlimit
4
5import (
6 "context"
7 "slices"
8 "sync"
9 "time"
10
11 "bnema.dev/ermite/internal/ports"
12)
13
14// Submission windows of the public issue form.
15const (
16 // HourWindow and DayWindow are the sliding windows of the limits
17 // PerHour and PerDay.
18 HourWindow = time.Hour
19 DayWindow = 24 * time.Hour
20
21 // PerHour and PerDay are the submissions one client may make in each
22 // window. They are the limits of the form (PerHour and
23 // PerDay), repeated here because this package may not import
24 // the domain; a test keeps them equal.
25 PerHour = 3
26 PerDay = 10
27
28 submissionSweepInterval = HourWindow / 4
29)
30
31// SubmissionLimiter limits the submissions of the public issue form per client
32// (an IPv4 address or an IPv6 /64, see Key): PerHour in a sliding
33// hour and PerDay in a sliding day. It also counts the
34// submissions of all clients in the last hour. It lives in memory, is bounded
35// like Limiter, and is safe for concurrent use.
36type SubmissionLimiter struct {
37 now func() time.Time
38
39 mu sync.Mutex
40 subs map[string][]time.Time // oldest first, all within DayWindow
41 global []time.Time // oldest first, all within HourWindow
42 lastSweep time.Time
43}
44
45var _ ports.SubmissionLimiter = (*SubmissionLimiter)(nil)
46
47// NewSubmissionLimiter builds a limiter. now defaults to time.Now.
48func NewSubmissionLimiter(now func() time.Time) *SubmissionLimiter {
49 if now == nil {
50 now = time.Now
51 }
52 return &SubmissionLimiter{now: now, subs: make(map[string][]time.Time)}
53}
54
55// Reserve checks the limits for addr and, if it may submit now, counts a
56// submission, atomically: concurrent callers cannot all pass the check. When
57// addr may not submit, retryAfter is how long until the oldest submission that
58// counts leaves its window and release is a no-op. Otherwise release refunds
59// the reservation; call it only if the submission was not stored.
60func (l *SubmissionLimiter) Reserve(_ context.Context, addr string) (ok bool, retryAfter time.Duration, release func()) {
61 key := limiterKey(addr)
62 now := l.now()
63 l.mu.Lock()
64 defer l.mu.Unlock()
65 l.maintain(now)
66 ts := l.prune(key, now)
67 var wait time.Duration
68 if h := withinWindow(ts, now, HourWindow); len(h) >= PerHour {
69 wait = h[len(h)-PerHour].Add(HourWindow).Sub(now)
70 }
71 if len(ts) >= PerDay {
72 wait = max(wait, ts[len(ts)-PerDay].Add(DayWindow).Sub(now))
73 }
74 if wait > 0 {
75 return false, max(wait, time.Second), func() {}
76 }
77 ts = append(ts, now)
78 if len(ts) > PerDay*2 {
79 ts = ts[len(ts)-PerDay*2:] // enough to compute the wait
80 }
81 l.subs[key] = ts
82 l.global = append(l.pruneGlobal(now), now)
83 if len(l.global) > maxTracked {
84 l.global = l.global[len(l.global)-maxTracked:] // bound the memory
85 }
86 var once sync.Once
87 return true, 0, func() { once.Do(func() { l.refund(key, now) }) }
88}
89
90// refund removes one reservation made at t for key.
91func (l *SubmissionLimiter) refund(key string, t time.Time) {
92 l.mu.Lock()
93 defer l.mu.Unlock()
94 if ts := l.subs[key]; ts != nil {
95 l.subs[key] = removeLast(ts, t)
96 if len(l.subs[key]) == 0 {
97 delete(l.subs, key)
98 }
99 }
100 l.global = removeLast(l.global, t)
101}
102
103// removeLast removes the last element of ts equal to t, if any.
104func removeLast(ts []time.Time, t time.Time) []time.Time {
105 for i := len(ts) - 1; i >= 0; i-- {
106 if ts[i].Equal(t) {
107 return slices.Delete(ts, i, i+1)
108 }
109 }
110 return ts
111}
112
113// Recent returns the submissions of addr and of all clients in the last hour.
114func (l *SubmissionLimiter) Recent(_ context.Context, addr string) (perAddr, global int) {
115 key := limiterKey(addr)
116 now := l.now()
117 l.mu.Lock()
118 defer l.mu.Unlock()
119 return len(withinWindow(l.prune(key, now), now, HourWindow)), len(l.pruneGlobal(now))
120}
121
122// withinWindow returns the tail of ts (oldest first) that is within window.
123func withinWindow(ts []time.Time, now time.Time, window time.Duration) []time.Time {
124 cut := now.Add(-window)
125 i, _ := slices.BinarySearchFunc(ts, cut, func(t, c time.Time) int {
126 if t.After(c) {
127 return 1
128 }
129 return -1
130 })
131 return ts[i:]
132}
133
134// prune drops the submissions of key older than DayWindow. The caller holds mu.
135func (l *SubmissionLimiter) prune(key string, now time.Time) []time.Time {
136 ts := withinWindow(l.subs[key], now, DayWindow)
137 if len(ts) == 0 {
138 delete(l.subs, key)
139 return nil
140 }
141 l.subs[key] = ts
142 return ts
143}
144
145// pruneGlobal drops the global submissions older than HourWindow. The caller
146// holds mu.
147func (l *SubmissionLimiter) pruneGlobal(now time.Time) []time.Time {
148 l.global = withinWindow(l.global, now, HourWindow)
149 return l.global
150}
151
152// maintain keeps the table small: expired entries go at most once per
153// submissionSweepInterval, and a table at its bound loses its oldest tenth.
154// The caller holds mu.
155func (l *SubmissionLimiter) maintain(now time.Time) {
156 if now.Sub(l.lastSweep) >= submissionSweepInterval {
157 l.lastSweep = now
158 for key := range l.subs {
159 l.prune(key, now)
160 }
161 }
162 if len(l.subs) < maxTracked {
163 return
164 }
165 drop := len(l.subs) - (maxTracked - maxTracked/evictFraction)
166 type entry struct {
167 key string
168 last time.Time
169 }
170 all := make([]entry, 0, len(l.subs))
171 for key, ts := range l.subs {
172 all = append(all, entry{key, ts[len(ts)-1]})
173 }
174 slices.SortFunc(all, func(a, b entry) int { return a.last.Compare(b.last) })
175 for _, e := range all[:drop] {
176 delete(l.subs, e.key)
177 }
178}