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