src/journal/journald-rate-limit.c

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