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