2 This file is part of systemd.
4 Copyright 2011 Lennart Poettering
6 systemd is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version.
11 systemd is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License
17 along with systemd; If not, see <http://www.gnu.org/licenses/>.
23 #include "alloc-util.h"
25 #include "journald-rate-limit.h"
27 #include "random-util.h"
28 #include "string-util.h"
32 #define BUCKETS_MAX 127
33 #define GROUPS_MAX 2047
35 static const int priority_map
[] = {
46 typedef struct JournalRateLimitPool JournalRateLimitPool
;
47 typedef struct JournalRateLimitGroup JournalRateLimitGroup
;
49 struct JournalRateLimitPool
{
55 struct JournalRateLimitGroup
{
56 JournalRateLimit
*parent
;
59 JournalRateLimitPool pools
[POOLS_MAX
];
62 LIST_FIELDS(JournalRateLimitGroup
, bucket
);
63 LIST_FIELDS(JournalRateLimitGroup
, lru
);
66 struct JournalRateLimit
{
70 JournalRateLimitGroup
* buckets
[BUCKETS_MAX
];
71 JournalRateLimitGroup
*lru
, *lru_tail
;
78 JournalRateLimit
*journal_rate_limit_new(usec_t interval
, unsigned burst
) {
81 assert(interval
> 0 || burst
== 0);
83 r
= new0(JournalRateLimit
, 1);
87 r
->interval
= interval
;
90 random_bytes(r
->hash_key
, sizeof(r
->hash_key
));
95 static void journal_rate_limit_group_free(JournalRateLimitGroup
*g
) {
99 assert(g
->parent
->n_groups
> 0);
101 if (g
->parent
->lru_tail
== g
)
102 g
->parent
->lru_tail
= g
->lru_prev
;
104 LIST_REMOVE(lru
, g
->parent
->lru
, g
);
105 LIST_REMOVE(bucket
, g
->parent
->buckets
[g
->hash
% BUCKETS_MAX
], g
);
107 g
->parent
->n_groups
--;
114 void journal_rate_limit_free(JournalRateLimit
*r
) {
118 journal_rate_limit_group_free(r
->lru
);
123 _pure_
static bool journal_rate_limit_group_expired(JournalRateLimitGroup
*g
, usec_t ts
) {
128 for (i
= 0; i
< POOLS_MAX
; i
++)
129 if (g
->pools
[i
].begin
+ g
->parent
->interval
>= ts
)
135 static void journal_rate_limit_vacuum(JournalRateLimit
*r
, usec_t ts
) {
138 /* Makes room for at least one new item, but drop all
139 * expored items too. */
141 while (r
->n_groups
>= GROUPS_MAX
||
142 (r
->lru_tail
&& journal_rate_limit_group_expired(r
->lru_tail
, ts
)))
143 journal_rate_limit_group_free(r
->lru_tail
);
146 static JournalRateLimitGroup
* journal_rate_limit_group_new(JournalRateLimit
*r
, const char *id
, usec_t ts
) {
147 JournalRateLimitGroup
*g
;
148 struct siphash state
;
153 g
= new0(JournalRateLimitGroup
, 1);
161 siphash24_init(&state
, r
->hash_key
);
162 string_hash_func(g
->id
, &state
);
163 g
->hash
= siphash24_finalize(&state
);
165 journal_rate_limit_vacuum(r
, ts
);
167 LIST_PREPEND(bucket
, r
->buckets
[g
->hash
% BUCKETS_MAX
], g
);
168 LIST_PREPEND(lru
, r
->lru
, g
);
177 journal_rate_limit_group_free(g
);
181 static unsigned burst_modulate(unsigned burst
, uint64_t available
) {
184 /* Modulates the burst rate a bit with the amount of available
187 k
= u64log2(available
);
193 burst
= (burst
* (k
-16)) / 4;
209 int journal_rate_limit_test(JournalRateLimit
*r
, const char *id
, int priority
, uint64_t available
) {
211 JournalRateLimitGroup
*g
;
212 JournalRateLimitPool
*p
;
213 struct siphash state
;
222 if (r
->interval
== 0 || r
->burst
== 0)
225 burst
= burst_modulate(r
->burst
, available
);
227 ts
= now(CLOCK_MONOTONIC
);
229 siphash24_init(&state
, r
->hash_key
);
230 string_hash_func(id
, &state
);
231 h
= siphash24_finalize(&state
);
232 g
= r
->buckets
[h
% BUCKETS_MAX
];
234 LIST_FOREACH(bucket
, g
, g
)
235 if (streq(g
->id
, id
))
239 g
= journal_rate_limit_group_new(r
, id
, ts
);
244 p
= &g
->pools
[priority_map
[priority
]];
253 if (p
->begin
+ r
->interval
< ts
) {
264 if (p
->num
< burst
) {