Line data Source code
1 : /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2 :
3 : /***
4 : This file is part of systemd.
5 :
6 : Copyright 2011 Lennart Poettering
7 :
8 : systemd is free software; you can redistribute it and/or modify it
9 : under the terms of the GNU Lesser General Public License as published by
10 : the Free Software Foundation; either version 2.1 of the License, or
11 : (at your option) any later version.
12 :
13 : systemd is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : Lesser General Public License for more details.
17 :
18 : You should have received a copy of the GNU Lesser General Public License
19 : along with systemd; If not, see <http://www.gnu.org/licenses/>.
20 : ***/
21 :
22 : #include <string.h>
23 : #include <errno.h>
24 :
25 : #include "journald-rate-limit.h"
26 : #include "list.h"
27 : #include "util.h"
28 : #include "hashmap.h"
29 : #include "random-util.h"
30 :
31 : #define POOLS_MAX 5
32 : #define BUCKETS_MAX 127
33 : #define GROUPS_MAX 2047
34 :
35 : static const int priority_map[] = {
36 : [LOG_EMERG] = 0,
37 : [LOG_ALERT] = 0,
38 : [LOG_CRIT] = 0,
39 : [LOG_ERR] = 1,
40 : [LOG_WARNING] = 2,
41 : [LOG_NOTICE] = 3,
42 : [LOG_INFO] = 3,
43 : [LOG_DEBUG] = 4
44 : };
45 :
46 : typedef struct JournalRateLimitPool JournalRateLimitPool;
47 : typedef struct JournalRateLimitGroup JournalRateLimitGroup;
48 :
49 : struct JournalRateLimitPool {
50 : usec_t begin;
51 : unsigned num;
52 : unsigned suppressed;
53 : };
54 :
55 : struct JournalRateLimitGroup {
56 : JournalRateLimit *parent;
57 :
58 : char *id;
59 : JournalRateLimitPool pools[POOLS_MAX];
60 : unsigned long hash;
61 :
62 : LIST_FIELDS(JournalRateLimitGroup, bucket);
63 : LIST_FIELDS(JournalRateLimitGroup, lru);
64 : };
65 :
66 : struct JournalRateLimit {
67 : usec_t interval;
68 : unsigned burst;
69 :
70 : JournalRateLimitGroup* buckets[BUCKETS_MAX];
71 : JournalRateLimitGroup *lru, *lru_tail;
72 :
73 : unsigned n_groups;
74 :
75 : uint8_t hash_key[16];
76 : };
77 :
78 0 : JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) {
79 : JournalRateLimit *r;
80 :
81 0 : assert(interval > 0 || burst == 0);
82 :
83 0 : r = new0(JournalRateLimit, 1);
84 0 : if (!r)
85 0 : return NULL;
86 :
87 0 : r->interval = interval;
88 0 : r->burst = burst;
89 :
90 0 : random_bytes(r->hash_key, sizeof(r->hash_key));
91 :
92 0 : return r;
93 : }
94 :
95 0 : static void journal_rate_limit_group_free(JournalRateLimitGroup *g) {
96 0 : assert(g);
97 :
98 0 : if (g->parent) {
99 0 : assert(g->parent->n_groups > 0);
100 :
101 0 : if (g->parent->lru_tail == g)
102 0 : g->parent->lru_tail = g->lru_prev;
103 :
104 0 : LIST_REMOVE(lru, g->parent->lru, g);
105 0 : LIST_REMOVE(bucket, g->parent->buckets[g->hash % BUCKETS_MAX], g);
106 :
107 0 : g->parent->n_groups --;
108 : }
109 :
110 0 : free(g->id);
111 0 : free(g);
112 0 : }
113 :
114 0 : void journal_rate_limit_free(JournalRateLimit *r) {
115 0 : assert(r);
116 :
117 0 : while (r->lru)
118 0 : journal_rate_limit_group_free(r->lru);
119 :
120 0 : free(r);
121 0 : }
122 :
123 0 : _pure_ static bool journal_rate_limit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
124 : unsigned i;
125 :
126 0 : assert(g);
127 :
128 0 : for (i = 0; i < POOLS_MAX; i++)
129 0 : if (g->pools[i].begin + g->parent->interval >= ts)
130 0 : return false;
131 :
132 0 : return true;
133 : }
134 :
135 0 : static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
136 0 : assert(r);
137 :
138 : /* Makes room for at least one new item, but drop all
139 : * expored items too. */
140 :
141 0 : while (r->n_groups >= GROUPS_MAX ||
142 0 : (r->lru_tail && journal_rate_limit_group_expired(r->lru_tail, ts)))
143 0 : journal_rate_limit_group_free(r->lru_tail);
144 0 : }
145 :
146 0 : static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
147 : JournalRateLimitGroup *g;
148 :
149 0 : assert(r);
150 0 : assert(id);
151 :
152 0 : g = new0(JournalRateLimitGroup, 1);
153 0 : if (!g)
154 0 : return NULL;
155 :
156 0 : g->id = strdup(id);
157 0 : if (!g->id)
158 0 : goto fail;
159 :
160 0 : g->hash = string_hash_func(g->id, r->hash_key);
161 :
162 0 : journal_rate_limit_vacuum(r, ts);
163 :
164 0 : LIST_PREPEND(bucket, r->buckets[g->hash % BUCKETS_MAX], g);
165 0 : LIST_PREPEND(lru, r->lru, g);
166 0 : if (!g->lru_next)
167 0 : r->lru_tail = g;
168 0 : r->n_groups ++;
169 :
170 0 : g->parent = r;
171 0 : return g;
172 :
173 : fail:
174 0 : journal_rate_limit_group_free(g);
175 0 : return NULL;
176 : }
177 :
178 0 : static unsigned burst_modulate(unsigned burst, uint64_t available) {
179 : unsigned k;
180 :
181 : /* Modulates the burst rate a bit with the amount of available
182 : * disk space */
183 :
184 0 : k = u64log2(available);
185 :
186 : /* 1MB */
187 0 : if (k <= 20)
188 0 : return burst;
189 :
190 0 : burst = (burst * (k-20)) / 4;
191 :
192 : /*
193 : * Example:
194 : *
195 : * <= 1MB = rate * 1
196 : * 16MB = rate * 2
197 : * 256MB = rate * 3
198 : * 4GB = rate * 4
199 : * 64GB = rate * 5
200 : * 1TB = rate * 6
201 : */
202 :
203 0 : return burst;
204 : }
205 :
206 0 : int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
207 : unsigned long h;
208 : JournalRateLimitGroup *g;
209 : JournalRateLimitPool *p;
210 : unsigned burst;
211 : usec_t ts;
212 :
213 0 : assert(id);
214 :
215 0 : if (!r)
216 0 : return 1;
217 :
218 0 : if (r->interval == 0 || r->burst == 0)
219 0 : return 1;
220 :
221 0 : burst = burst_modulate(r->burst, available);
222 :
223 0 : ts = now(CLOCK_MONOTONIC);
224 :
225 0 : h = string_hash_func(id, r->hash_key);
226 0 : g = r->buckets[h % BUCKETS_MAX];
227 :
228 0 : LIST_FOREACH(bucket, g, g)
229 0 : if (streq(g->id, id))
230 0 : break;
231 :
232 0 : if (!g) {
233 0 : g = journal_rate_limit_group_new(r, id, ts);
234 0 : if (!g)
235 0 : return -ENOMEM;
236 : }
237 :
238 0 : p = &g->pools[priority_map[priority]];
239 :
240 0 : if (p->begin <= 0) {
241 0 : p->suppressed = 0;
242 0 : p->num = 1;
243 0 : p->begin = ts;
244 0 : return 1;
245 : }
246 :
247 0 : if (p->begin + r->interval < ts) {
248 : unsigned s;
249 :
250 0 : s = p->suppressed;
251 0 : p->suppressed = 0;
252 0 : p->num = 1;
253 0 : p->begin = ts;
254 :
255 0 : return 1 + s;
256 : }
257 :
258 0 : if (p->num <= burst) {
259 0 : p->num++;
260 0 : return 1;
261 : }
262 :
263 0 : p->suppressed++;
264 0 : return 0;
265 : }
|
