1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
2
3 #include <errno.h>
4
5 #include "alloc-util.h"
6 #include "hashmap.h"
7 #include "journald-rate-limit.h"
8 #include "list.h"
9 #include "random-util.h"
10 #include "string-util.h"
11 #include "time-util.h"
12
13 #define POOLS_MAX 5
14 #define BUCKETS_MAX 127
15 #define GROUPS_MAX 2047
16
17 static const int priority_map[] = {
18 [LOG_EMERG] = 0,
19 [LOG_ALERT] = 0,
20 [LOG_CRIT] = 0,
21 [LOG_ERR] = 1,
22 [LOG_WARNING] = 2,
23 [LOG_NOTICE] = 3,
24 [LOG_INFO] = 3,
25 [LOG_DEBUG] = 4
26 };
27
28 typedef struct JournalRateLimitPool JournalRateLimitPool;
29 typedef struct JournalRateLimitGroup JournalRateLimitGroup;
30
31 struct JournalRateLimitPool {
32 usec_t begin;
33 unsigned num;
34 unsigned suppressed;
35 };
36
37 struct JournalRateLimitGroup {
38 JournalRateLimit *parent;
39
40 char *id;
41
42 /* Interval is stored to keep track of when the group expires */
43 usec_t interval;
44
45 JournalRateLimitPool pools[POOLS_MAX];
46 uint64_t hash;
47
48 LIST_FIELDS(JournalRateLimitGroup, bucket);
49 LIST_FIELDS(JournalRateLimitGroup, lru);
50 };
51
52 struct JournalRateLimit {
53
54 JournalRateLimitGroup* buckets[BUCKETS_MAX];
55 JournalRateLimitGroup *lru, *lru_tail;
56
57 unsigned n_groups;
58
59 uint8_t hash_key[16];
60 };
61
journal_ratelimit_new(void)62 JournalRateLimit *journal_ratelimit_new(void) {
63 JournalRateLimit *r;
64
65 r = new0(JournalRateLimit, 1);
66 if (!r)
67 return NULL;
68
69 random_bytes(r->hash_key, sizeof(r->hash_key));
70
71 return r;
72 }
73
journal_ratelimit_group_free(JournalRateLimitGroup * g)74 static void journal_ratelimit_group_free(JournalRateLimitGroup *g) {
75 assert(g);
76
77 if (g->parent) {
78 assert(g->parent->n_groups > 0);
79
80 if (g->parent->lru_tail == g)
81 g->parent->lru_tail = g->lru_prev;
82
83 LIST_REMOVE(lru, g->parent->lru, g);
84 LIST_REMOVE(bucket, g->parent->buckets[g->hash % BUCKETS_MAX], g);
85
86 g->parent->n_groups--;
87 }
88
89 free(g->id);
90 free(g);
91 }
92
journal_ratelimit_free(JournalRateLimit * r)93 void journal_ratelimit_free(JournalRateLimit *r) {
94 assert(r);
95
96 while (r->lru)
97 journal_ratelimit_group_free(r->lru);
98
99 free(r);
100 }
101
journal_ratelimit_group_expired(JournalRateLimitGroup * g,usec_t ts)102 static bool journal_ratelimit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
103 unsigned i;
104
105 assert(g);
106
107 for (i = 0; i < POOLS_MAX; i++)
108 if (g->pools[i].begin + g->interval >= ts)
109 return false;
110
111 return true;
112 }
113
journal_ratelimit_vacuum(JournalRateLimit * r,usec_t ts)114 static void journal_ratelimit_vacuum(JournalRateLimit *r, usec_t ts) {
115 assert(r);
116
117 /* Makes room for at least one new item, but drop all
118 * expored items too. */
119
120 while (r->n_groups >= GROUPS_MAX ||
121 (r->lru_tail && journal_ratelimit_group_expired(r->lru_tail, ts)))
122 journal_ratelimit_group_free(r->lru_tail);
123 }
124
journal_ratelimit_group_new(JournalRateLimit * r,const char * id,usec_t interval,usec_t ts)125 static JournalRateLimitGroup* journal_ratelimit_group_new(JournalRateLimit *r, const char *id, usec_t interval, usec_t ts) {
126 JournalRateLimitGroup *g;
127
128 assert(r);
129 assert(id);
130
131 g = new0(JournalRateLimitGroup, 1);
132 if (!g)
133 return NULL;
134
135 g->id = strdup(id);
136 if (!g->id)
137 goto fail;
138
139 g->hash = siphash24_string(g->id, r->hash_key);
140
141 g->interval = interval;
142
143 journal_ratelimit_vacuum(r, ts);
144
145 LIST_PREPEND(bucket, r->buckets[g->hash % BUCKETS_MAX], g);
146 LIST_PREPEND(lru, r->lru, g);
147 if (!g->lru_next)
148 r->lru_tail = g;
149 r->n_groups++;
150
151 g->parent = r;
152 return g;
153
154 fail:
155 journal_ratelimit_group_free(g);
156 return NULL;
157 }
158
burst_modulate(unsigned burst,uint64_t available)159 static unsigned burst_modulate(unsigned burst, uint64_t available) {
160 unsigned k;
161
162 /* Modulates the burst rate a bit with the amount of available
163 * disk space */
164
165 k = log2u64(available);
166
167 /* 1MB */
168 if (k <= 20)
169 return burst;
170
171 burst = (burst * (k-16)) / 4;
172
173 /*
174 * Example:
175 *
176 * <= 1MB = rate * 1
177 * 16MB = rate * 2
178 * 256MB = rate * 3
179 * 4GB = rate * 4
180 * 64GB = rate * 5
181 * 1TB = rate * 6
182 */
183
184 return burst;
185 }
186
journal_ratelimit_test(JournalRateLimit * r,const char * id,usec_t rl_interval,unsigned rl_burst,int priority,uint64_t available)187 int journal_ratelimit_test(JournalRateLimit *r, const char *id, usec_t rl_interval, unsigned rl_burst, int priority, uint64_t available) {
188 JournalRateLimitGroup *g, *found = NULL;
189 JournalRateLimitPool *p;
190 unsigned burst;
191 uint64_t h;
192 usec_t ts;
193
194 assert(id);
195
196 /* Returns:
197 *
198 * 0 → the log message shall be suppressed,
199 * 1 + n → the log message shall be permitted, and n messages were dropped from the peer before
200 * < 0 → error
201 */
202
203 if (!r)
204 return 1;
205
206 ts = now(CLOCK_MONOTONIC);
207
208 h = siphash24_string(id, r->hash_key);
209 g = r->buckets[h % BUCKETS_MAX];
210
211 LIST_FOREACH(bucket, i, g)
212 if (streq(i->id, id)) {
213 found = i;
214 break;
215 }
216
217 if (!found) {
218 found = journal_ratelimit_group_new(r, id, rl_interval, ts);
219 if (!found)
220 return -ENOMEM;
221 } else
222 found->interval = rl_interval;
223
224 if (rl_interval == 0 || rl_burst == 0)
225 return 1;
226
227 burst = burst_modulate(rl_burst, available);
228
229 p = &found->pools[priority_map[priority]];
230
231 if (p->begin <= 0) {
232 p->suppressed = 0;
233 p->num = 1;
234 p->begin = ts;
235 return 1;
236 }
237
238 if (p->begin + rl_interval < ts) {
239 unsigned s;
240
241 s = p->suppressed;
242 p->suppressed = 0;
243 p->num = 1;
244 p->begin = ts;
245
246 return 1 + s;
247 }
248
249 if (p->num < burst) {
250 p->num++;
251 return 1;
252 }
253
254 p->suppressed++;
255 return 0;
256 }
257