Branch data 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 : : }
|
