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 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 "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 }