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;
75 JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) {
78 assert(interval > 0 || burst == 0);
80 r = new0(JournalRateLimit, 1);
84 r->interval = interval;
90 static void journal_rate_limit_group_free(JournalRateLimitGroup *g) {
94 assert(g->parent->n_groups > 0);
96 if (g->parent->lru_tail == g)
97 g->parent->lru_tail = g->lru_prev;
99 LIST_REMOVE(JournalRateLimitGroup, lru, g->parent->lru, g);
100 LIST_REMOVE(JournalRateLimitGroup, bucket, g->parent->buckets[g->hash % BUCKETS_MAX], g);
102 g->parent->n_groups --;
109 void journal_rate_limit_free(JournalRateLimit *r) {
113 journal_rate_limit_group_free(r->lru);
118 static bool journal_rate_limit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
123 for (i = 0; i < POOLS_MAX; i++)
124 if (g->pools[i].begin + g->parent->interval >= ts)
130 static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
133 /* Makes room for at least one new item, but drop all
134 * expored items too. */
136 while (r->n_groups >= GROUPS_MAX ||
137 (r->lru_tail && journal_rate_limit_group_expired(r->lru_tail, ts)))
138 journal_rate_limit_group_free(r->lru_tail);
141 static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
142 JournalRateLimitGroup *g;
147 g = new0(JournalRateLimitGroup, 1);
155 g->hash = string_hash_func(g->id);
157 journal_rate_limit_vacuum(r, ts);
159 LIST_PREPEND(JournalRateLimitGroup, bucket, r->buckets[g->hash % BUCKETS_MAX], g);
160 LIST_PREPEND(JournalRateLimitGroup, lru, r->lru, g);
169 journal_rate_limit_group_free(g);
173 static uint64_t u64log2(uint64_t n) {
188 static unsigned burst_modulate(unsigned burst, uint64_t available) {
191 /* Modulates the burst rate a bit with the amount of available
194 k = u64log2(available);
200 burst = (burst * (k-20)) / 4;
216 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
218 JournalRateLimitGroup *g;
219 JournalRateLimitPool *p;
228 if (r->interval == 0 || r->burst == 0)
231 burst = burst_modulate(r->burst, available);
233 ts = now(CLOCK_MONOTONIC);
235 h = string_hash_func(id);
236 g = r->buckets[h % BUCKETS_MAX];
238 LIST_FOREACH(bucket, g, g)
239 if (streq(g->id, id))
243 g = journal_rate_limit_group_new(r, id, ts);
248 p = &g->pools[priority_map[priority]];
257 if (p->begin + r->interval < ts) {
268 if (p->num <= burst) {