3 * Copyright (c) 2013 Samsung Electronics Co., Ltd.
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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include <sys/types.h>
33 /* Included for priorities level */
35 #include "loglimiter.h"
37 /* Defines maximal meaningful tag length */
38 #define TAG_REASONABLE_LEN 32
40 /* Some random big odd number to make hash more diverse */
41 #define HASH_MAGIC_THINGY 5237231
46 /* TODO: List element handle, the list could be embedded
47 into structure some day, like kernel lists */
55 char tag[TAG_REASONABLE_LEN];
58 typedef int (*hash_cmp_func_t)(struct rule*, struct rule*);
59 typedef int (*hash_match_func_t)(struct rule*, unsigned, const char*, int);
63 hash_match_func_t match;
68 struct hashmap* rules_hashmap = NULL;
70 /* Keep rules table as single-linked list */
71 struct rule* rules_table = NULL;
73 #define HASHMAP_MASK(hm) ((int)(hm->size - 1))
74 #define HASHMAP_LINEAR_PROBE_LEAP 1
76 static void rules_destroy(struct rule* rlist)
90 void __log_limiter_rules_purge(void)
92 rules_destroy(rules_table);
96 static int rule_compare(struct rule* r1, struct rule* r2)
98 if (r1->hash == r2->hash) {
99 if (r1->prio == r2->prio) {
100 return strncmp(r1->tag, r2->tag, TAG_REASONABLE_LEN);
102 return (r1->prio > r2->prio ? 1 : (-1));
106 return (r1->hash > r2->hash ? 1 : (-1));
109 static int rule_match(struct rule* r1, unsigned key, const char* s, int prio)
111 if (r1->hash == key) {
112 if (r1->prio == prio) {
113 return strncmp(r1->tag, s, TAG_REASONABLE_LEN);
115 return (r1->prio > prio ? 1 : (-1));
119 return (r1->hash > key ? 1 : (-1));
122 /* Translate fancy priority notation into common denominator */
123 static int util_prio_to_char(int prio)
125 static const char pri_table[DLOG_PRIO_MAX] = {
126 [DLOG_VERBOSE] = 'V',
135 if (DLOG_PRIO_MAX > prio && prio >= 0) {
136 return pri_table[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':
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)
161 unsigned hash = (unsigned)c;
163 hash = ((hash << 5) + hash) + c;
169 while ('\0' != (c = *s++)) {
170 hash = ((hash << 5) + hash) + c;
174 /* Makes the hash more diverse */
175 hash *= HASH_MAGIC_THINGY;
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)
184 struct hashmap* hm = NULL;
185 /* please keep hashmap fill ratio around 50% */
186 int internal_size = size << 1;
188 if (!cmp_func || !match_func || !size) {
193 /* Round up the lines counter to next power of two. */
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;
202 hm = malloc(sizeof(*hm) + internal_size * sizeof(void*));
207 hm->size = internal_size;
209 hm->match = match_func;
210 /* Initialize hash field to correct value */
211 memset((void*)hm + sizeof(*hm), 0, hm->size * sizeof(void*));
216 static void hashmap_destroy(struct hashmap* hm)
224 static void hashmap_add(struct hashmap* hm, struct rule* r)
226 unsigned b = (r->hash & HASHMAP_MASK(hm));
228 while (hm->bucket[b]) {
229 if (!hm->cmp(r, (struct rule*)hm->bucket[b])) {
232 b = (b + 1) & HASHMAP_MASK(hm);
238 static struct rule* hashmap_search(struct hashmap* hm, unsigned key,
239 const char* tag, int prio)
241 unsigned b = (key & HASHMAP_MASK(hm));
244 while (hm->bucket[b]) {
245 if (!hm->match(hm->bucket[b], key, tag, prio)) {
249 b = (b + 1) & HASHMAP_MASK(hm);
256 if (!hm->bucket[b]) {
260 return hm->bucket[b];
263 /* Must be always executed after __log_config_read() */
264 int __log_limiter_initialize(void)
267 struct rule* rlist = NULL;
269 /* logconfig.c module had to initialize this correctly */
270 if (NULL == rules_table) {
274 /* Count rules in the table */
282 /* Allocate hashmap */
283 rules_hashmap = (struct hashmap*) hashmap_create(hm_size,
286 if (NULL == rules_hashmap || !rules_hashmap->size) {
290 /* Add rule to hashmap */
293 hashmap_add(rules_hashmap, rlist);
300 hashmap_destroy(rules_hashmap);
301 rules_destroy(rules_table);
303 rules_hashmap = NULL;
308 void __log_limiter_destroy(void)
310 hashmap_destroy(rules_hashmap);
311 rules_destroy(rules_table);
313 rules_hashmap = NULL;
316 int __log_limiter_add_rule(const char* tag, int prio, int limit)
324 r = (struct rule*) malloc(sizeof(*r));
328 memset(r, 0, sizeof(*r));
330 strncpy(r->tag, tag, TAG_REASONABLE_LEN);
331 r->prio = util_prio_to_char(prio);
332 r->hash = util_hash_key(tag, r->prio);
334 r->start = time(NULL);
337 r->prev = rules_table;
344 /* Function implement logic needed to decide,
345 whenever message is written to log or not.
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.
352 int __log_limiter_pass_log(const char* tag, int prio)
355 struct rule* r = NULL;
358 key = util_hash_key(tag, util_prio_to_char(prio));
359 r = hashmap_search(rules_hashmap, key, tag, util_prio_to_char(prio));
362 /* Rule not found, let's check general rule TAG:* */
363 key = util_hash_key(tag, '*');
364 r = hashmap_search(rules_hashmap, key, tag, '*');
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));
372 /* All known paths were exhausted,
373 use global rule *:* */
374 key = util_hash_key("*", '*');
375 r = hashmap_search(rules_hashmap, key, "*", '*');
377 /* *:* is not defined, so pass message through */
387 } else if (__LOG_LIMITER_LIMIT_MAX < r->limit) {
391 /* Decide, if it should go through or stop */
398 if (now - r->start <= TIME_FRAME) {
400 if (r->hit < r->limit) {
417 /* If everything failed, then pass message through */