src/journal/journald-rate-limit.c

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