src/journal/journal-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 General Public License as published by
  10   the Free Software Foundation; either version 2 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   General Public License for more details.
  17
  18   You should have received a copy of the GNU 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 "journal-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 uint64_t u64log2(uint64_t n) {
 174         unsigned r;
 175
 176         if (n <= 1)
 177                 return 0;
 178
 179         r = 0;
 180         for (;;) {
 181                 n = n >> 1;
 182                 if (!n)
 183                         return r;
 184                 r++;
 185         }
 186 }
 187
 188 static unsigned burst_modulate(unsigned burst, uint64_t available) {
 189         unsigned k;
 190
 191         /* Modulates the burst rate a bit with the amount of available
 192          * disk space */
 193
 194         k = u64log2(available);
 195
 196         /* 1MB */
 197         if (k <= 20)
 198                 return burst;
 199
 200         burst = (burst * (k-20)) / 4;
 201
 202         /*
 203          * Example:
 204          *
 205          *      <= 1MB = rate * 1
 206          *        16MB = rate * 2
 207          *       256MB = rate * 3
 208          *         4GB = rate * 4
 209          *        64GB = rate * 5
 210          *         1TB = rate * 6
 211          */
 212
 213         return burst;
 214 }
 215
 216 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
 217         unsigned h;
 218         JournalRateLimitGroup *g;
 219         JournalRateLimitPool *p;
 220         unsigned burst;
 221         usec_t ts;
 222
 223         assert(id);
 224
 225         if (!r)
 226                 return 1;
 227
 228         if (r->interval == 0 || r->burst == 0)
 229                 return 1;
 230
 231         burst = burst_modulate(r->burst, available);
 232
 233         ts = now(CLOCK_MONOTONIC);
 234
 235         h = string_hash_func(id);
 236         g = r->buckets[h % BUCKETS_MAX];
 237
 238         LIST_FOREACH(bucket, g, g)
 239                 if (streq(g->id, id))
 240                         break;
 241
 242         if (!g) {
 243                 g = journal_rate_limit_group_new(r, id, ts);
 244                 if (!g)
 245                         return -ENOMEM;
 246         }
 247
 248         p = &g->pools[priority_map[priority]];
 249
 250         if (p->begin <= 0) {
 251                 p->suppressed = 0;
 252                 p->num = 1;
 253                 p->begin = ts;
 254                 return 1;
 255         }
 256
 257         if (p->begin + r->interval < ts) {
 258                 unsigned s;
 259
 260                 s = p->suppressed;
 261                 p->suppressed = 0;
 262                 p->num = 1;
 263                 p->begin = ts;
 264
 265                 return 1 + s;
 266         }
 267
 268         if (p->num <= burst) {
 269                 p->num++;
 270                 return 1;
 271         }
 272
 273         p->suppressed++;
 274         return 0;
 275 }