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