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 General Public License as published by
10 the Free Software Foundation; either version 2 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 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
25 #include "journal-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) {