src/journal/journald-rate-limit.c

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