1 /* SPDX-License-Identifier: LGPL-2.1+ */
6 #include "alloc-util.h"
8 #include "journald-rate-limit.h"
10 #include "random-util.h"
11 #include "string-util.h"
15 #define BUCKETS_MAX 127
16 #define GROUPS_MAX 2047
18 static const int priority_map
[] = {
29 typedef struct JournalRateLimitPool JournalRateLimitPool
;
30 typedef struct JournalRateLimitGroup JournalRateLimitGroup
;
32 struct JournalRateLimitPool
{
38 struct JournalRateLimitGroup
{
39 JournalRateLimit
*parent
;
42 JournalRateLimitPool pools
[POOLS_MAX
];
45 LIST_FIELDS(JournalRateLimitGroup
, bucket
);
46 LIST_FIELDS(JournalRateLimitGroup
, lru
);
49 struct JournalRateLimit
{
53 JournalRateLimitGroup
* buckets
[BUCKETS_MAX
];
54 JournalRateLimitGroup
*lru
, *lru_tail
;
61 JournalRateLimit
*journal_rate_limit_new(usec_t interval
, unsigned burst
) {
64 assert(interval
> 0 || burst
== 0);
66 r
= new0(JournalRateLimit
, 1);
70 r
->interval
= interval
;
73 random_bytes(r
->hash_key
, sizeof(r
->hash_key
));
78 static void journal_rate_limit_group_free(JournalRateLimitGroup
*g
) {
82 assert(g
->parent
->n_groups
> 0);
84 if (g
->parent
->lru_tail
== g
)
85 g
->parent
->lru_tail
= g
->lru_prev
;
87 LIST_REMOVE(lru
, g
->parent
->lru
, g
);
88 LIST_REMOVE(bucket
, g
->parent
->buckets
[g
->hash
% BUCKETS_MAX
], g
);
90 g
->parent
->n_groups
--;
97 void journal_rate_limit_free(JournalRateLimit
*r
) {
101 journal_rate_limit_group_free(r
->lru
);
106 _pure_
static bool journal_rate_limit_group_expired(JournalRateLimitGroup
*g
, usec_t ts
) {
111 for (i
= 0; i
< POOLS_MAX
; i
++)
112 if (g
->pools
[i
].begin
+ g
->parent
->interval
>= ts
)
118 static void journal_rate_limit_vacuum(JournalRateLimit
*r
, usec_t ts
) {
121 /* Makes room for at least one new item, but drop all
122 * expored items too. */
124 while (r
->n_groups
>= GROUPS_MAX
||
125 (r
->lru_tail
&& journal_rate_limit_group_expired(r
->lru_tail
, ts
)))
126 journal_rate_limit_group_free(r
->lru_tail
);
129 static JournalRateLimitGroup
* journal_rate_limit_group_new(JournalRateLimit
*r
, const char *id
, usec_t ts
) {
130 JournalRateLimitGroup
*g
;
131 struct siphash state
;
136 g
= new0(JournalRateLimitGroup
, 1);
144 siphash24_init(&state
, r
->hash_key
);
145 string_hash_func(g
->id
, &state
);
146 g
->hash
= siphash24_finalize(&state
);
148 journal_rate_limit_vacuum(r
, ts
);
150 LIST_PREPEND(bucket
, r
->buckets
[g
->hash
% BUCKETS_MAX
], g
);
151 LIST_PREPEND(lru
, r
->lru
, g
);
160 journal_rate_limit_group_free(g
);
164 static unsigned burst_modulate(unsigned burst
, uint64_t available
) {
167 /* Modulates the burst rate a bit with the amount of available
170 k
= u64log2(available
);
176 burst
= (burst
* (k
-16)) / 4;
192 int journal_rate_limit_test(JournalRateLimit
*r
, const char *id
, int priority
, uint64_t available
) {
194 JournalRateLimitGroup
*g
;
195 JournalRateLimitPool
*p
;
196 struct siphash state
;
204 * 0 → the log message shall be suppressed,
205 * 1 + n → the log message shall be permitted, and n messages were dropped from the peer before
212 if (r
->interval
== 0 || r
->burst
== 0)
215 burst
= burst_modulate(r
->burst
, available
);
217 ts
= now(CLOCK_MONOTONIC
);
219 siphash24_init(&state
, r
->hash_key
);
220 string_hash_func(id
, &state
);
221 h
= siphash24_finalize(&state
);
222 g
= r
->buckets
[h
% BUCKETS_MAX
];
224 LIST_FOREACH(bucket
, g
, g
)
225 if (streq(g
->id
, id
))
229 g
= journal_rate_limit_group_new(r
, id
, ts
);
234 p
= &g
->pools
[priority_map
[priority
]];
243 if (p
->begin
+ r
->interval
< ts
) {
254 if (p
->num
< burst
) {