src/journal/journald-rate-limit.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2011 Lennart Poettering
   7
   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.
  12
  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.
  17
  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/>.
  20 ***/
  21
  22 #include <string.h>
  23 #include <errno.h>
  24
  25 #include "journald-rate-limit.h"
  26 #include "list.h"
  27 #include "util.h"
  28 #include "hashmap.h"
  29 #include "random-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         siphash24_finalize((uint8_t*)&g->hash, &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-20)) / 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         if (!r)
 220                 return 1;
 221
 222         if (r->interval == 0 || r->burst == 0)
 223                 return 1;
 224
 225         burst = burst_modulate(r->burst, available);
 226
 227         ts = now(CLOCK_MONOTONIC);
 228
 229         siphash24_init(&state, r->hash_key);
 230         string_hash_func(id, &state);
 231         siphash24_finalize((uint8_t*)&h, &state);
 232         g = r->buckets[h % BUCKETS_MAX];
 233
 234         LIST_FOREACH(bucket, g, g)
 235                 if (streq(g->id, id))
 236                         break;
 237
 238         if (!g) {
 239                 g = journal_rate_limit_group_new(r, id, ts);
 240                 if (!g)
 241                         return -ENOMEM;
 242         }
 243
 244         p = &g->pools[priority_map[priority]];
 245
 246         if (p->begin <= 0) {
 247                 p->suppressed = 0;
 248                 p->num = 1;
 249                 p->begin = ts;
 250                 return 1;
 251         }
 252
 253         if (p->begin + r->interval < ts) {
 254                 unsigned s;
 255
 256                 s = p->suppressed;
 257                 p->suppressed = 0;
 258                 p->num = 1;
 259                 p->begin = ts;
 260
 261                 return 1 + s;
 262         }
 263
 264         if (p->num <= burst) {
 265                 p->num++;
 266                 return 1;
 267         }
 268
 269         p->suppressed++;
 270         return 0;
 271 }