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