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