File: leaky-bucket.c

package info (click to toggle)
mcelog 104-1
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 996 kB
  • ctags: 1,508
  • sloc: ansic: 7,739; sh: 481; makefile: 87
file content (220 lines) | stat: -rw-r--r-- 5,400 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
/* Copyright (C) 2009 Intel Corporation 
   Author: Andi Kleen
   Leaky bucket algorithm. This is used for all error triggers.

   mcelog is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public
   License as published by the Free Software Foundation; version
   2.

   mcelog is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should find a copy of v2 of the GNU General Public License somewhere
   on your Linux system; if not, write to the Free Software Foundation, 
   Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
#define _GNU_SOURCE 1
#include <stdio.h>
#include <ctype.h>
#include "leaky-bucket.h"

time_t __attribute__((weak)) bucket_time(void)
{
	return time(NULL);
}

static void bucket_age(const struct bucket_conf *c, struct leaky_bucket *b,
			time_t now)
{
	long diff;
	diff = now - b->tstamp;
	if (diff >= c->agetime) { 
		unsigned age = (diff / (double)c->agetime) * c->capacity;
		b->tstamp = now;
		if (age > b->count)
			b->count = 0;
		else
			b->count -= age;
		b->excess = 0;
	}
}

/* Account increase in leaky bucket. Return 1 if bucket overflowed. */
int __bucket_account(const struct bucket_conf *c, struct leaky_bucket *b, 
		   unsigned inc, time_t t)
{
	if (c->capacity == 0)
		return 0;
	bucket_age(c, b, t);
	b->count += inc; 
	if (b->count >= c->capacity) {
		b->excess += b->count;
		/* should disable overflow completely in the same time unit */
		b->count = 0;
		return 1;
	}
	return 0;
}

int bucket_account(const struct bucket_conf *c, struct leaky_bucket *b, 
		   unsigned inc) 
{
	return __bucket_account(c, b, inc, bucket_time());
}

static int timeconv(char unit, int *out)
{
	unsigned corr = 1;
	switch (unit) { 
	case 'd': corr *= 24;
	case 'h': corr *= 60;
	case 'm': corr *= 60;
	case 0:   break;
	default: return -1;
	}
	*out = corr;
	return 0;
}

/* Format leaky bucket as a string. Caller must free string */
char *bucket_output(const struct bucket_conf *c, struct leaky_bucket *b)
{
	char *buf;
	if (c->capacity == 0) {
		asprintf(&buf, "not enabled");
	} else { 
		int unit = 0;
		//bucket_age(c, b, bucket_time());
		timeconv(c->tunit, &unit);
		asprintf(&buf, "%u in %u%c", b->count + b->excess, 
			c->agetime/unit, c->tunit);
	}
	return buf;
}

/* Parse user specified capacity / rate string */
/* capacity / time 
   time: number [hmds]
   capacity: number [kmg] */
static int parse_rate(const char *rate, struct bucket_conf *c)
{
	char cunit[2], tunit[2];
	unsigned cap, t;
	int n;
	int unit;

	cunit[0] = 0;
	tunit[0] = 0;
	n = sscanf(rate, "%u %1s / %u %1s", &cap, cunit, &t, tunit);
	if (n != 4)  { 
		cunit[0] = 0;
		tunit[0] = 0;
		if (n <= 2) {
			n = sscanf(rate, "%u / %u %1s", &cap, &t, tunit);
			if (n < 2)
				return -1;
		} else
			return -1;
	}
	if (t == 0 || cap == 0)
		return -1;
	switch (tolower(cunit[0])) { 
	case 'g': cap *= 1000;
	case 'm': cap *= 1000;
	case 'k': cap *= 1000;
	case 0:   break;
	default:  return -1;
	}
	c->tunit = tolower(tunit[0]);
	if (timeconv(c->tunit, &unit) < 0)
		return -1;
	c->agetime = unit * t;
	c->capacity = cap;
	return 0;
}

/* Initialize leaky bucket conf for given user rate/capacity string. <0 on error */
int bucket_conf_init(struct bucket_conf *c, const char *rate)
{
	if (parse_rate(rate, c) < 0)
		return -1;
	c->trigger = NULL;
	return 0;
}

/* Initialize leaky bucket instance. */
void bucket_init(struct leaky_bucket *b)
{
	b->count = 0;
	b->excess = 0;
	b->tstamp = bucket_time();
}


#ifdef TEST_LEAKY_BUCKET
/* Stolen from the cpp documentation */
#define xstr(_s) str(_s)
#define str(_s) #_s

#define THRESHOLD_EVENTS_PER_PERIOD 100
#define EVENTS_PER_LOGGED_EVENT 10
#define SECONDS_PER_EVENT 86
/* Needs to be SECONDS_PER_EVENT * EVENTS_PER_LOGGED_EVENT * THRESHOLD_EVENTS_PER_PERIOD */
#define THRESHOLD_PERIOD 86000
#if THRESHOLD_PERIOD != (SECONDS_PER_EVENT * EVENTS_PER_LOGGED_EVENT * THRESHOLD_EVENTS_PER_PERIOD)
#  error THRESHOLD_PERIOD is Wrong!
#endif
#define RATE_STRING xstr(THRESHOLD_EVENTS_PER_PERIOD) " / " xstr(THRESHOLD_PERIOD)

#define EVENTS_PER_PERIOD_IN_TEST (THRESHOLD_EVENTS_PER_PERIOD * EVENTS_PER_LOGGED_EVENT)

#define PERIODS_TO_TEST 3
#define TOTAL_SECONDS_FOR_TEST (PERIODS_TO_TEST * THRESHOLD_PERIOD)
#define TOTAL_EVENTS (PERIODS_TO_TEST * EVENTS_PER_PERIOD_IN_TEST)

int main(int argc, char **argv)
{
	struct bucket_conf c;
	struct leaky_bucket b;
	time_t start_time;
	time_t event_time;
	int ret;
	int i;

#ifdef TEST_LEAKY_BUCKET_DEBUG
	printf("Testing with a rate of " RATE_STRING "\n");
#endif
	ret = bucket_conf_init(&c, RATE_STRING);
	if (ret)
		return ret;

	bucket_init(&b);
	start_time = b.tstamp;

	for (i = 1; i <= TOTAL_EVENTS; i++) {
		event_time = start_time + i * SECONDS_PER_EVENT;
		ret = __bucket_account(&c, &b, 1, event_time);

#ifdef TEST_LEAKY_BUCKET_DEBUG
		if (ret)
			printf("Logging entry %d at %ld %ld\n", i, event_time - start_time, b.tstamp);
#else
		if (i < THRESHOLD_EVENTS_PER_PERIOD) {
			if (!ret){
				fprintf(stderr, "Did not log initial events - FAIL.\n");
				return -1;
			}
		} else {
			if (!(i % EVENTS_PER_LOGGED_EVENT) && !ret) {
				fprintf(stderr, "Did not log initial events - FAIL.\n");
				return -1;
			}
		}
#endif
	}

	return 0;
}
#endif