1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2011 Lennart Poettering
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.
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.
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/>.
25 #include "journald-rate-limit.h"
31 #define BUCKETS_MAX 127
32 #define GROUPS_MAX 2047
34 static const int priority_map[] = {
45 typedef struct JournalRateLimitPool JournalRateLimitPool;
46 typedef struct JournalRateLimitGroup JournalRateLimitGroup;
48 struct JournalRateLimitPool {
54 struct JournalRateLimitGroup {
55 JournalRateLimit *parent;
58 JournalRateLimitPool pools[POOLS_MAX];
61 LIST_FIELDS(JournalRateLimitGroup, bucket);
62 LIST_FIELDS(JournalRateLimitGroup, lru);
65 struct JournalRateLimit {
69 JournalRateLimitGroup* buckets[BUCKETS_MAX];
70 JournalRateLimitGroup *lru, *lru_tail;
77 JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) {
80 assert(interval > 0 || burst == 0);
82 r = new0(JournalRateLimit, 1);
86 r->interval = interval;
89 random_bytes(r->hash_key, sizeof(r->hash_key));
94 static void journal_rate_limit_group_free(JournalRateLimitGroup *g) {
98 assert(g->parent->n_groups > 0);
100 if (g->parent->lru_tail == g)
101 g->parent->lru_tail = g->lru_prev;
103 LIST_REMOVE(lru, g->parent->lru, g);
104 LIST_REMOVE(bucket, g->parent->buckets[g->hash % BUCKETS_MAX], g);
106 g->parent->n_groups --;
113 void journal_rate_limit_free(JournalRateLimit *r) {
117 journal_rate_limit_group_free(r->lru);
122 _pure_ static bool journal_rate_limit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
127 for (i = 0; i < POOLS_MAX; i++)
128 if (g->pools[i].begin + g->parent->interval >= ts)
134 static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
137 /* Makes room for at least one new item, but drop all
138 * expored items too. */
140 while (r->n_groups >= GROUPS_MAX ||
141 (r->lru_tail && journal_rate_limit_group_expired(r->lru_tail, ts)))
142 journal_rate_limit_group_free(r->lru_tail);
145 static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
146 JournalRateLimitGroup *g;
151 g = new0(JournalRateLimitGroup, 1);
159 g->hash = string_hash_func(g->id, r->hash_key);
161 journal_rate_limit_vacuum(r, ts);
163 LIST_PREPEND(bucket, r->buckets[g->hash % BUCKETS_MAX], g);
164 LIST_PREPEND(lru, r->lru, g);
173 journal_rate_limit_group_free(g);
177 static unsigned burst_modulate(unsigned burst, uint64_t available) {
180 /* Modulates the burst rate a bit with the amount of available
183 k = u64log2(available);
189 burst = (burst * (k-20)) / 4;
205 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
207 JournalRateLimitGroup *g;
208 JournalRateLimitPool *p;
217 if (r->interval == 0 || r->burst == 0)
220 burst = burst_modulate(r->burst, available);
222 ts = now(CLOCK_MONOTONIC);
224 h = string_hash_func(id, r->hash_key);
225 g = r->buckets[h % BUCKETS_MAX];
227 LIST_FOREACH(bucket, g, g)
228 if (streq(g->id, id))
232 g = journal_rate_limit_group_new(r, id, ts);
237 p = &g->pools[priority_map[priority]];
246 if (p->begin + r->interval < ts) {
257 if (p->num <= burst) {