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