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
 116 static bool journal_rate_limit_group_expired(JournalRateLimitGroup *g, usec_t ts) {
 117         unsigned i;
 118
 119         assert(g);
 120
 121         for (i = 0; i < POOLS_MAX; i++)
 122                 if (g->pools[i].begin + g->parent->interval >= ts)
 123                         return false;
 124
 125         return true;
 126 }
 127
 128 static void journal_rate_limit_vacuum(JournalRateLimit *r, usec_t ts) {
 129         assert(r);
 130
 131         /* Makes room for at least one new item, but drop all
 132          * expored items too. */
 133
 134         while (r->n_groups >= GROUPS_MAX ||
 135                (r->lru_tail && journal_rate_limit_group_expired(r->lru_tail, ts)))
 136                 journal_rate_limit_group_free(r->lru_tail);
 137 }
 138
 139 static JournalRateLimitGroup* journal_rate_limit_group_new(JournalRateLimit *r, const char *id, usec_t ts) {
 140         JournalRateLimitGroup *g;
 141
 142         assert(r);
 143         assert(id);
 144
 145         g = new0(JournalRateLimitGroup, 1);
 146         if (!g)
 147                 return NULL;
 148
 149         g->id = strdup(id);
 150         if (!g->id)
 151                 goto fail;
 152
 153         g->hash = string_hash_func(g->id);
 154
 155         journal_rate_limit_vacuum(r, ts);
 156
 157         LIST_PREPEND(JournalRateLimitGroup, bucket, r->buckets[g->hash % BUCKETS_MAX], g);
 158         LIST_PREPEND(JournalRateLimitGroup, lru, r->lru, g);
 159         if (!g->lru_next)
 160                 r->lru_tail = g;
 161         r->n_groups ++;
 162
 163         g->parent = r;
 164         return g;
 165
 166 fail:
 167         journal_rate_limit_group_free(g);
 168         return NULL;
 169 }
 170
 171 static uint64_t u64log2(uint64_t n) {
 172         unsigned r;
 173
 174         if (n <= 1)
 175                 return 0;
 176
 177         r = 0;
 178         for (;;) {
 179                 n = n >> 1;
 180                 if (!n)
 181                         return r;
 182                 r++;
 183         }
 184 }
 185
 186 static unsigned burst_modulate(unsigned burst, uint64_t available) {
 187         unsigned k;
 188
 189         /* Modulates the burst rate a bit with the amount of available
 190          * disk space */
 191
 192         k = u64log2(available);
 193
 194         /* 1MB */
 195         if (k <= 20)
 196                 return burst;
 197
 198         burst = (burst * (k-20)) / 4;
 199
 200         /*
 201          * Example:
 202          *
 203          *      <= 1MB = rate * 1
 204          *        16MB = rate * 2
 205          *       256MB = rate * 3
 206          *         4GB = rate * 4
 207          *        64GB = rate * 5
 208          *         1TB = rate * 6
 209          */
 210
 211         return burst;
 212 }
 213
 214 int journal_rate_limit_test(JournalRateLimit *r, const char *id, int priority, uint64_t available) {
 215         unsigned h;
 216         JournalRateLimitGroup *g;
 217         JournalRateLimitPool *p;
 218         unsigned burst;
 219         usec_t ts;
 220
 221         assert(id);
 222
 223         if (!r)
 224                 return 1;
 225
 226         if (r->interval == 0 || r->burst == 0)
 227                 return 1;
 228
 229         burst = burst_modulate(r->burst, available);
 230
 231         ts = now(CLOCK_MONOTONIC);
 232
 233         h = string_hash_func(id);
 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 }