src/journal/journald-rate-limit.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2 /***
   3   This file is part of systemd.
   4
   5   Copyright 2011 Lennart Poettering
   6
   7   systemd is free software; you can redistribute it and/or modify it
   8   under the terms of the GNU Lesser General Public License as published by
   9   the Free Software Foundation; either version 2.1 of the License, or
  10   (at your option) any later version.
  11
  12   systemd is distributed in the hope that it will be useful, but
  13   WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17   You should have received a copy of the GNU Lesser General Public License
  18   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  19 ***/
  20
  21 #include <errno.h>
  22 #include <string.h>
  23
  24 #include "alloc-util.h"
  25 #include "hashmap.h"
  26 #include "journald-rate-limit.h"
  27 #include "list.h"
  28 #include "random-util.h"
  29 #include "string-util.h"
  30 #include "util.h"
  31
  32 #define POOLS_MAX 5
  33 #define BUCKETS_MAX 127
  34 #define GROUPS_MAX 2047
  35
  36 static const int priority_map[] = {
  37         [LOG_EMERG]   = 0,
  38         [LOG_ALERT]   = 0,
  39         [LOG_CRIT]    = 0,
  40         [LOG_ERR]     = 1,
  41         [LOG_WARNING] = 2,
  42         [LOG_NOTICE]  = 3,
  43         [LOG_INFO]    = 3,
  44         [LOG_DEBUG]   = 4
  45 };
  46
  47 typedef struct JournalRateLimitPool JournalRateLimitPool;
  48 typedef struct JournalRateLimitGroup JournalRateLimitGroup;
  49
  50 struct JournalRateLimitPool {
  51         usec_t begin;
  52         unsigned num;
  53         unsigned suppressed;
  54 };
  55
  56 struct JournalRateLimitGroup {
  57         JournalRateLimit *parent;
  58
  59         char *id;
  60         JournalRateLimitPool pools[POOLS_MAX];
  61         uint64_t hash;
  62
  63         LIST_FIELDS(JournalRateLimitGroup, bucket);
  64         LIST_FIELDS(JournalRateLimitGroup, lru);
  65 };
  66
  67 struct JournalRateLimit {
  68         usec_t interval;
  69         unsigned burst;
  70
  71         JournalRateLimitGroup* buckets[BUCKETS_MAX];
  72         JournalRateLimitGroup *lru, *lru_tail;
  73
  74         unsigned n_groups;
  75
  76         uint8_t hash_key[16];
  77 };
  78
  79 JournalRateLimit *journal_rate_limit_new(usec_t interval, unsigned burst) {
  80         JournalRateLimit *r;
  81
  82         assert(interval > 0 || burst == 0);
  83
  84         r = new0(JournalRateLimit, 1);
  85         if (!r)
  86                 return NULL;
  87
  88         r->interval = interval;
  89         r->burst = burst;
  90
  91         random_bytes(r->hash_key, sizeof(r->hash_key));
  92
  93         return r;
  94 }
  95
  96 static void journal_rate_limit_group_free(JournalRateLimitGroup *g) {
  97         assert(g);
  98
  99         if (g->parent) {
 100                 assert(g->parent->n_groups > 0);
 101
 102                 if (g->parent->lru_tail == g)
 103                         g->parent->lru_tail = g->lru_prev;
 104
 105                 LIST_REMOVE(lru, g->parent->lru, g);
 106                 LIST_REMOVE(bucket, g->parent->buckets[g->hash % BUCKETS_MAX], g);
 107
 108                 g->parent->n_groups--;
 109         }
 110
 111         free(g->id);
 112         free(g);
 113 }
 114
 115 void journal_rate_limit_free(JournalRateLimit *r) {
 116         assert(r);
 117
 118         while (r->lru)
 119                 journal_rate_limit_group_free(r->lru);
 120
 121         free(r);
 122 }
 123
 124 _pure_ static bool journal_rate_limit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
 125         unsigned i;
 126
 127         assert(g);
 128
 129         for (i = 0; i < POOLS_MAX; i++)
 130                 if (g->pools[i].begin + g->parent->interval >= ts)
 131                         return false;
 132
 133         return true;
 134 }
 135
 136 static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
 137         assert(r);
 138
 139         /* Makes room for at least one new item, but drop all
 140          * expored items too. */
 141
 142         while (r->n_groups >= GROUPS_MAX ||
 143                (r->lru_tail && journal_rate_limit_group_expired(r->lru_tail, ts)))
 144                 journal_rate_limit_group_free(r->lru_tail);
 145 }
 146
 147 static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
 148         JournalRateLimitGroup *g;
 149         struct siphash state;
 150
 151         assert(r);
 152         assert(id);
 153
 154         g = new0(JournalRateLimitGroup, 1);
 155         if (!g)
 156                 return NULL;
 157
 158         g->id = strdup(id);
 159         if (!g->id)
 160                 goto fail;
 161
 162         siphash24_init(&state, r->hash_key);
 163         string_hash_func(g->id, &state);
 164         g->hash = siphash24_finalize(&state);
 165
 166         journal_rate_limit_vacuum(r, ts);
 167
 168         LIST_PREPEND(bucket, r->buckets[g->hash % BUCKETS_MAX], g);
 169         LIST_PREPEND(lru, r->lru, g);
 170         if (!g->lru_next)
 171                 r->lru_tail = g;
 172         r->n_groups++;
 173
 174         g->parent = r;
 175         return g;
 176
 177 fail:
 178         journal_rate_limit_group_free(g);
 179         return NULL;
 180 }
 181
 182 static unsigned burst_modulate(unsigned burst, uint64_t available) {
 183         unsigned k;
 184
 185         /* Modulates the burst rate a bit with the amount of available
 186          * disk space */
 187
 188         k = u64log2(available);
 189
 190         /* 1MB */
 191         if (k <= 20)
 192                 return burst;
 193
 194         burst = (burst * (k-16)) / 4;
 195
 196         /*
 197          * Example:
 198          *
 199          *      <= 1MB = rate * 1
 200          *        16MB = rate * 2
 201          *       256MB = rate * 3
 202          *         4GB = rate * 4
 203          *        64GB = rate * 5
 204          *         1TB = rate * 6
 205          */
 206
 207         return burst;
 208 }
 209
 210 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
 211         uint64_t h;
 212         JournalRateLimitGroup *g;
 213         JournalRateLimitPool *p;
 214         struct siphash state;
 215         unsigned burst;
 216         usec_t ts;
 217
 218         assert(id);
 219
 220         /* Returns:
 221          *
 222          * 0     → the log message shall be suppressed,
 223          * 1 + n → the log message shall be permitted, and n messages were dropped from the peer before
 224          * < 0   → error
 225          */
 226
 227         if (!r)
 228                 return 1;
 229
 230         if (r->interval == 0 || r->burst == 0)
 231                 return 1;
 232
 233         burst = burst_modulate(r->burst, available);
 234
 235         ts = now(CLOCK_MONOTONIC);
 236
 237         siphash24_init(&state, r->hash_key);
 238         string_hash_func(id, &state);
 239         h = siphash24_finalize(&state);
 240         g = r->buckets[h % BUCKETS_MAX];
 241
 242         LIST_FOREACH(bucket, g, g)
 243                 if (streq(g->id, id))
 244                         break;
 245
 246         if (!g) {
 247                 g = journal_rate_limit_group_new(r, id, ts);
 248                 if (!g)
 249                         return -ENOMEM;
 250         }
 251
 252         p = &g->pools[priority_map[priority]];
 253
 254         if (p->begin <= 0) {
 255                 p->suppressed = 0;
 256                 p->num = 1;
 257                 p->begin = ts;
 258                 return 1;
 259         }
 260
 261         if (p->begin + r->interval < ts) {
 262                 unsigned s;
 263
 264                 s = p->suppressed;
 265                 p->suppressed = 0;
 266                 p->num = 1;
 267                 p->begin = ts;
 268
 269                 return 1 + s;
 270         }
 271
 272         if (p->num < burst) {
 273                 p->num++;
 274                 return 1;
 275         }
 276
 277         p->suppressed++;
 278         return 0;
 279 }