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         unsigned long 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
 149         assert(r);
 150         assert(id);
 151
 152         g = new0(JournalRateLimitGroup, 1);
 153         if (!g)
 154                 return NULL;
 155
 156         g->id = strdup(id);
 157         if (!g->id)
 158                 goto fail;
 159
 160         g->hash = string_hash_func(g->id, r->hash_key);
 161
 162         journal_rate_limit_vacuum(r, ts);
 163
 164         LIST_PREPEND(bucket, r->buckets[g->hash % BUCKETS_MAX], g);
 165         LIST_PREPEND(lru, r->lru, g);
 166         if (!g->lru_next)
 167                 r->lru_tail = g;
 168         r->n_groups ++;
 169
 170         g->parent = r;
 171         return g;
 172
 173 fail:
 174         journal_rate_limit_group_free(g);
 175         return NULL;
 176 }
 177
 178 static unsigned burst_modulate(unsigned burst, uint64_t available) {
 179         unsigned k;
 180
 181         /* Modulates the burst rate a bit with the amount of available
 182          * disk space */
 183
 184         k = u64log2(available);
 185
 186         /* 1MB */
 187         if (k <= 20)
 188                 return burst;
 189
 190         burst = (burst * (k-20)) / 4;
 191
 192         /*
 193          * Example:
 194          *
 195          *      <= 1MB = rate * 1
 196          *        16MB = rate * 2
 197          *       256MB = rate * 3
 198          *         4GB = rate * 4
 199          *        64GB = rate * 5
 200          *         1TB = rate * 6
 201          */
 202
 203         return burst;
 204 }
 205
 206 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
 207         unsigned long h;
 208         JournalRateLimitGroup *g;
 209         JournalRateLimitPool *p;
 210         unsigned burst;
 211         usec_t ts;
 212
 213         assert(id);
 214
 215         if (!r)
 216                 return 1;
 217
 218         if (r->interval == 0 || r->burst == 0)
 219                 return 1;
 220
 221         burst = burst_modulate(r->burst, available);
 222
 223         ts = now(CLOCK_MONOTONIC);
 224
 225         h = string_hash_func(id, r->hash_key);
 226         g = r->buckets[h % BUCKETS_MAX];
 227
 228         LIST_FOREACH(bucket, g, g)
 229                 if (streq(g->id, id))
 230                         break;
 231
 232         if (!g) {
 233                 g = journal_rate_limit_group_new(r, id, ts);
 234                 if (!g)
 235                         return -ENOMEM;
 236         }
 237
 238         p = &g->pools[priority_map[priority]];
 239
 240         if (p->begin <= 0) {
 241                 p->suppressed = 0;
 242                 p->num = 1;
 243                 p->begin = ts;
 244                 return 1;
 245         }
 246
 247         if (p->begin + r->interval < ts) {
 248                 unsigned s;
 249
 250                 s = p->suppressed;
 251                 p->suppressed = 0;
 252                 p->num = 1;
 253                 p->begin = ts;
 254
 255                 return 1 + s;
 256         }
 257
 258         if (p->num <= burst) {
 259                 p->num++;
 260                 return 1;
 261         }
 262
 263         p->suppressed++;
 264         return 0;
 265 }