src/libdlog/loglimiter.c

   1 /*
   2  * DLOG
   3  * Copyright (c) 2013 Samsung Electronics Co., Ltd.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the License);
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 #include <stddef.h>
  19 #include <limits.h>
  20 #include <sys/types.h>
  21 #include <errno.h>
  22 #include <stdbool.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <fcntl.h>
  26 #include <unistd.h>
  27 #include <string.h>
  28 #include <ctype.h>
  29 #include <pthread.h>
  30 #include <sys/time.h>
  31 #include <time.h>
  32
  33 /* Included for priorities level */
  34 #include <dlog.h>
  35 #include "loglimiter.h"
  36
  37 /* Defines maximal meaningful tag length */
  38 #define TAG_REASONABLE_LEN        32
  39
  40 /* Some random big odd number to make hash more diverse */
  41 #define HASH_MAGIC_THINGY         5237231
  42
  43 #define TIME_FRAME                60
  44
  45 struct rule{
  46         /* TODO: List element handle, the list could be embedded
  47                  into structure some day, like kernel lists */
  48         struct rule* prev;
  49
  50         unsigned hash;
  51         int prio;
  52         int limit;
  53         int hit;
  54         time_t start;
  55         char tag[TAG_REASONABLE_LEN];
  56 };
  57
  58 typedef int (*hash_cmp_func_t)(struct rule*, struct rule*);
  59 typedef int (*hash_match_func_t)(struct rule*, unsigned, const char*, int);
  60
  61 struct hashmap {
  62         hash_cmp_func_t cmp;
  63         hash_match_func_t match;
  64         int size;
  65         void* bucket[];
  66 };
  67
  68 struct hashmap* rules_hashmap = NULL;
  69
  70 /* Keep rules table as single-linked list */
  71 struct rule* rules_table = NULL;
  72
  73 #define HASHMAP_MASK(hm)          ((int)(hm->size - 1))
  74 #define HASHMAP_LINEAR_PROBE_LEAP 1
  75
  76 static void rules_destroy(struct rule* rlist)
  77 {
  78         struct rule* r;
  79
  80         if (NULL == rlist) {
  81                 return;
  82         }
  83
  84         while ((r = rlist)) {
  85                 rlist = rlist->prev;
  86                 free(r);
  87         }
  88 }
  89
  90 void __log_limiter_rules_purge(void)
  91 {
  92         rules_destroy(rules_table);
  93         rules_table = NULL;
  94 }
  95
  96 static int rule_compare(struct rule* r1, struct rule* r2)
  97 {
  98         if (r1->hash == r2->hash) {
  99                 if (r1->prio == r2->prio) {
 100                         return strncmp(r1->tag, r2->tag, strlen(r2->tag));
 101                 } else {
 102                         return (r1->prio > r2->prio ? 1 : (-1));
 103                 }
 104         }
 105
 106         return (r1->hash > r2->hash ? 1 : (-1));
 107 }
 108
 109 static int rule_match(struct rule* r1, unsigned key, const char* s, int prio)
 110 {
 111         if (r1->hash == key) {
 112                 if (r1->prio == prio) {
 113                         return strncmp(r1->tag, s, strlen(s));
 114                 } else {
 115                         return (r1->prio > prio ? 1 : (-1));
 116                 }
 117         }
 118
 119         return (r1->hash > key ? 1 : (-1));
 120 }
 121
 122 /* Translate fancy priority notation into common denominator */
 123 static int util_prio_to_char(int prio)
 124 {
 125         static const char pri_table[DLOG_PRIO_MAX] = {
 126                 [DLOG_VERBOSE] = 'V',
 127                 [DLOG_DEBUG] = 'D',
 128                 [DLOG_INFO] = 'I',
 129                 [DLOG_WARN] = 'W',
 130                 [DLOG_ERROR] = 'E',
 131                 [DLOG_FATAL] = 'F',
 132                 [DLOG_SILENT] = 'S',
 133         };
 134
 135         if (DLOG_PRIO_MAX > prio && prio >= 0) {
 136                 return pri_table[prio];
 137         } else {
 138                 switch (prio) {
 139                         case 'V': case 'v': case '1':
 140                         case 'D': case 'd': case '2':
 141                         case 'I': case 'i': case '3':
 142                         case 'W': case 'w': case '4':
 143                         case 'E': case 'e': case '5':
 144                         case 'F': case 'f': case '6':
 145                         case 'S': case 's': case '7':
 146                         case '*':
 147                                 return prio;
 148
 149                         default:
 150                                 ;;
 151                 }
 152         }
 153
 154         return '?';
 155 }
 156
 157 /* The key is built from TAG and priority by DJB algorithm (Dan Bernstein).
 158  * Key is only 31 bits long. Negative values are keep to hold NULL bucket */
 159 static unsigned util_hash_key(const char* s, int c)
 160 {
 161         unsigned hash = (unsigned)c;
 162
 163         hash = ((hash << 5) + hash) + c;
 164
 165         if (!s || !s[0]) {
 166                 goto finish;
 167         }
 168
 169         while ('\0' != (c = *s++)) {
 170                 hash = ((hash << 5) + hash) + c;
 171         }
 172
 173 finish:
 174         /* Makes the hash more diverse */
 175         hash *= HASH_MAGIC_THINGY;
 176
 177         return hash;
 178 }
 179
 180 /* Create hashmap, it's internal interface. */
 181 static struct hashmap* hashmap_create(int size, hash_cmp_func_t cmp_func,
 182                                       hash_match_func_t match_func)
 183 {
 184         struct hashmap* hm = NULL;
 185         /* please keep hashmap fill ratio around 50% */
 186         int internal_size = size << 1;
 187
 188         if (!cmp_func || !match_func || !size) {
 189                 return NULL;
 190         }
 191
 192
 193         /* Round up the lines counter to next power of two. */
 194         internal_size--;
 195         internal_size |= internal_size >> 1;
 196         internal_size |= internal_size >> 2;
 197         internal_size |= internal_size >> 4;
 198         internal_size |= internal_size >> 8;
 199         internal_size |= internal_size >> 16;
 200         internal_size++;
 201
 202         hm = malloc(sizeof(struct hashmap) + internal_size * sizeof(void*));
 203         if (!hm) {
 204                 return NULL;
 205         }
 206         /* Initialize hash field to correct value */
 207         memset((void*)hm, 0, sizeof(struct hashmap) + internal_size * sizeof(void*));
 208
 209         hm->size = internal_size;
 210         hm->cmp = cmp_func;
 211         hm->match = match_func;
 212
 213         return hm;
 214 }
 215
 216 static void hashmap_destroy(struct hashmap* hm)
 217 {
 218         if (hm) {
 219                 hm->size = 0;
 220                 free(hm);
 221         }
 222 }
 223
 224 static void hashmap_add(struct hashmap* hm, struct rule* r)
 225 {
 226         unsigned b = (r->hash & HASHMAP_MASK(hm));
 227
 228         while (hm->bucket[b]) {
 229                 if (!hm->cmp(r, (struct rule*)hm->bucket[b])) {
 230                         break;
 231                 }
 232                 b = (b + 1) & HASHMAP_MASK(hm);
 233         }
 234
 235         hm->bucket[b] = r;
 236 }
 237
 238 static struct rule* hashmap_search(struct hashmap* hm, unsigned key,
 239                                    const char* tag, int prio)
 240 {
 241         unsigned b = (key & HASHMAP_MASK(hm));
 242         unsigned b0 = b;
 243
 244         while (hm->bucket[b]) {
 245                 if (!hm->match(hm->bucket[b], key, tag, prio)) {
 246                         break;
 247                 }
 248
 249                 b = (b + 1) & HASHMAP_MASK(hm);
 250
 251                 if (b0 == b) {
 252                         return NULL;
 253                 }
 254         }
 255
 256         if (!hm->bucket[b]) {
 257                 return NULL;
 258         }
 259
 260         return hm->bucket[b];
 261 }
 262
 263 /* Must be always executed after __log_config_read() */
 264 int __log_limiter_initialize(void)
 265 {
 266         int hm_size;
 267         struct rule* rlist = NULL;
 268
 269         /* logconfig.c module had to initialize this correctly */
 270         if (NULL == rules_table) {
 271                 return (-1);
 272         }
 273
 274         /* Count rules in the table */
 275         hm_size = 0;
 276         rlist = rules_table;
 277         while (rlist) {
 278                 hm_size++;
 279                 rlist = rlist->prev;
 280         }
 281
 282         /* Allocate hashmap */
 283         rules_hashmap = (struct hashmap*) hashmap_create(hm_size,
 284                                                          &rule_compare,
 285                                                          &rule_match);
 286         if (NULL == rules_hashmap || !rules_hashmap->size) {
 287                 goto bailout;
 288         }
 289
 290         /* Add rule to hashmap */
 291         rlist = rules_table;
 292         while (rlist) {
 293                 hashmap_add(rules_hashmap, rlist);
 294                 rlist = rlist->prev;
 295         }
 296
 297         return 0;
 298
 299 bailout:
 300         hashmap_destroy(rules_hashmap);
 301         rules_destroy(rules_table);
 302         rules_table = NULL;
 303         rules_hashmap = NULL;
 304
 305         return (-1);
 306 }
 307
 308 void __log_limiter_destroy(void)
 309 {
 310         hashmap_destroy(rules_hashmap);
 311         rules_destroy(rules_table);
 312         rules_table = NULL;
 313         rules_hashmap = NULL;
 314 }
 315
 316 int __log_limiter_add_rule(const char* tag, int prio, int limit)
 317 {
 318         struct rule* r;
 319
 320         if (!tag) {
 321                 return (-1);
 322         }
 323
 324         r = (struct rule*) malloc(sizeof(struct rule));
 325         if (NULL == r) {
 326                 return (-1);
 327         }
 328         memset(r, 0, sizeof(struct rule));
 329
 330         snprintf(r->tag, TAG_REASONABLE_LEN, "%s", tag);
 331         r->prio = util_prio_to_char(prio);
 332         r->hash = util_hash_key(tag, r->prio);
 333         r->limit = limit;
 334         r->start = time(NULL);
 335         r->hit = 0;
 336
 337         r->prev = rules_table;
 338         rules_table = r;
 339
 340         return 0;
 341 }
 342
 343
 344 /* Function implement logic needed to decide,
 345    whenever message is written to log or not.
 346
 347    Possible return values are:
 348         0  - to indicate that message is deny to write into log.
 349         (-1) - to indicate that limit of the messages is reached.
 350         1  - to indicate that message is allowed to write into log.
 351 */
 352 int __log_limiter_pass_log(const char* tag, int prio)
 353 {
 354         unsigned key = 0;
 355         struct rule* r = NULL;
 356         time_t now = 0;
 357
 358         key = util_hash_key(tag, util_prio_to_char(prio));
 359         r = hashmap_search(rules_hashmap, key, tag, util_prio_to_char(prio));
 360
 361         if (!r) {
 362                 /* Rule not found, let's check general rule TAG:* */
 363                 key = util_hash_key(tag, '*');
 364                 r = hashmap_search(rules_hashmap, key, tag, '*');
 365                 if (!r) {
 366                         /* Rule TAG:* not found,
 367                            let check general rule *:priority */
 368                         key = util_hash_key("*", util_prio_to_char(prio));
 369                         r = hashmap_search(rules_hashmap, key, "*",
 370                                                        util_prio_to_char(prio));
 371                         if (!r) {
 372                                 /* All known paths were exhausted,
 373                                    use global rule *:* */
 374                                 key = util_hash_key("*", '*');
 375                                 r = hashmap_search(rules_hashmap, key, "*", '*');
 376
 377                                 /* *:* is not defined, so pass message through */
 378                                 if (!r) {
 379                                         return 1;
 380                                 }
 381                         }
 382                 }
 383         }
 384
 385         if (!r->limit) {
 386                 return 0;
 387         } else if (__LOG_LIMITER_LIMIT_MAX < r->limit) {
 388                 return 1;
 389         }
 390
 391         /* Decide, if it should go through or stop */
 392         now = time(NULL);
 393
 394         if (0 > now) {
 395                 return 1;
 396         }
 397
 398         if (now - r->start <= TIME_FRAME) {
 399                 if (r->hit >= 0) {
 400                         if (r->hit < r->limit) {
 401                                 r->hit++;
 402                                 return 1;
 403                         }
 404                         r->hit = INT_MIN+1;
 405                         return (-1);
 406                 } else {
 407                         r->hit++;
 408                         return 0;
 409                 }
 410
 411         } else {
 412                 r->start = now;
 413                 r->hit = 0;
 414                 return 1;
 415         }
 416
 417         /* If everything failed, then pass message through */
 418         return 1;
 419 }