1 /*
2 * This file is part of the rsyslog runtime library.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 * -or-
10 * see COPYING.ASL20 in the source distribution
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 #include <stdlib.h>
20 #include <string.h>
21 #include <stdint.h>
22 #include <stdbool.h>
23 #include <math.h>
24 #include <assert.h>
25 #include "perctile_ringbuf.h"
26
min(uint64_t a,uint64_t b)27 static uint64_t min(uint64_t a, uint64_t b) {
28 return a < b ? a : b;
29 }
30
31 /*
32 * circ buf macros derived from linux/circ_buf.h
33 */
34
35 /* Return count in buffer. */
36 #define CIRC_CNT(head,tail,size) (((head) - (tail)) & ((size)-1))
37
38 /* Return space available, 0..size-1. We always leave one free char
39 as a completely full buffer has head == tail, which is the same as
40 empty. */
41 #define CIRC_SPACE(head,tail,size) CIRC_CNT((tail),((head)+1),(size))
42
43 /* Return count up to the end of the buffer. Carefully avoid
44 accessing head and tail more than once, so they can change
45 underneath us without returning inconsistent results. */
46 #define CIRC_CNT_TO_END(head,tail,size) \
47 ({int end = (size) - (tail); \
48 int n = ((head) + end) & ((size)-1); \
49 n < end ? n : end;})
50
51 /* Return space available up to the end of the buffer. */
52 #define CIRC_SPACE_TO_END(head,tail,size) \
53 ({int end = (size) - 1 - (head); \
54 int n = (end + (tail)) & ((size)-1); \
55 n <= end ? n : end+1;})
56
57 /* Move head by size. */
58 #define CIRC_ADD(idx, size, offset) (((idx) + (offset)) & ((size) - 1))
59
60 // simple use of the linux defined circular buffer.
61
ringbuf_new(size_t count)62 ringbuf_t* ringbuf_new(size_t count) {
63 // use nearest power of 2
64 double x = ceil(log2(count));
65 size_t bufsize = pow(2, x);
66
67 ringbuf_t *rb = calloc(1, sizeof(ringbuf_t));
68 // Note: count needs to be a power of 2, otherwise our macros won't work.
69 ITEM *pbuf = calloc(bufsize, sizeof(ITEM));
70 rb->cb.buf = pbuf;
71 rb->cb.head = rb->cb.tail = 0;
72 rb->size = bufsize;
73
74 return rb;
75 }
76
ringbuf_del(ringbuf_t * rb)77 void ringbuf_del(ringbuf_t *rb) {
78 if (rb) {
79 if (rb->cb.buf) {
80 free(rb->cb.buf);
81 }
82 free(rb);
83 }
84 }
85
ringbuf_append(ringbuf_t * rb,ITEM item)86 int ringbuf_append(ringbuf_t *rb, ITEM item) {
87 // lock it and add
88 int head = rb->cb.head,
89 tail = rb->cb.tail;
90
91 if (!CIRC_SPACE(head, tail, rb->size)) {
92 return -1;
93 } else {
94 /* insert item into buffer */
95 rb->cb.buf[head] = item;
96 // move head
97 rb->cb.head = CIRC_ADD(head, rb->size, 1);
98 }
99 return 0;
100 }
101
ringbuf_append_with_overwrite(ringbuf_t * rb,ITEM item)102 int ringbuf_append_with_overwrite(ringbuf_t *rb, ITEM item) {
103 int head = rb->cb.head,
104 tail = rb->cb.tail;
105 int ret = 0;
106
107 if (!CIRC_SPACE(head, tail, rb->size)) {
108 rb->cb.tail = CIRC_ADD(tail, rb->size, 1);
109 }
110 ret = ringbuf_append(rb, item);
111 assert(ret == 0); // we shouldn't fail due to no space.
112 return ret;
113 }
114
ringbuf_read(ringbuf_t * rb,ITEM * buf,size_t count)115 int ringbuf_read(ringbuf_t *rb, ITEM *buf, size_t count) {
116 int head = rb->cb.head,
117 tail = rb->cb.tail;
118 size_t copy_size = 0;
119
120 if (!CIRC_CNT(head, tail, rb->size)) {
121 return 0;
122 }
123
124 // copy to end of buffer
125 copy_size = min((size_t)CIRC_CNT_TO_END(head, tail, rb->size), count);
126 memcpy(buf, rb->cb.buf+tail, copy_size*sizeof(ITEM));
127
128 rb->cb.tail = CIRC_ADD(rb->cb.tail, rb->size, copy_size);
129 return copy_size;
130 }
131
ringbuf_read_to_end(ringbuf_t * rb,ITEM * buf,size_t count)132 size_t ringbuf_read_to_end(ringbuf_t *rb, ITEM *buf, size_t count) {
133 size_t nread = 0;
134 nread += ringbuf_read(rb, buf, count);
135 if (nread == 0) {
136 return nread;
137 }
138 // read the rest if buf circled around
139 nread += ringbuf_read(rb, buf + nread, count - nread);
140 assert(nread <= count);
141 return nread;
142 }
143
ringbuf_peek(ringbuf_t * rb,ITEM * item)144 bool ringbuf_peek(ringbuf_t *rb, ITEM *item) {
145 if (CIRC_CNT(rb->cb.head, rb->cb.tail, rb->size) == 0) {
146 return false;
147 }
148
149 *item = rb->cb.buf[rb->cb.tail];
150 return true;
151 }
152
ringbuf_capacity(ringbuf_t * rb)153 size_t ringbuf_capacity(ringbuf_t *rb) {
154 return rb->size;
155 }
156
157 /* ---- RINGBUFFER TESTS ---- */
ringbuf_init_test(void)158 void ringbuf_init_test(void) {
159 size_t count = 4;
160 ringbuf_t *rb = ringbuf_new(count);
161 // verify ringbuf empty state
162 assert(rb->cb.head == 0);
163 assert(rb->cb.tail == 0);
164 assert(rb->size == 4);
165 ringbuf_del(rb);
166 }
167
ringbuf_simple_test(void)168 void ringbuf_simple_test(void) {
169 size_t count = 3;
170 ITEM item = 0;
171 ringbuf_t *rb = ringbuf_new(count);
172 assert(ringbuf_append(rb, 1) == 0);
173 assert(ringbuf_append(rb, 2) == 0);
174 assert(ringbuf_append(rb, 3) == 0);
175
176 item = 0;
177 assert(ringbuf_peek(rb, &item) == 0);
178 assert(item == 1);
179 }
180
ringbuf_append_test(void)181 void ringbuf_append_test(void) {
182 size_t count = 4;
183 ringbuf_t *rb = ringbuf_new(count);
184
185 assert(ringbuf_append(rb, 1) == 0);
186 assert(ringbuf_append(rb, 2) == 0);
187 assert(ringbuf_append(rb, 3) == 0);
188
189 // check state of ringbuffer:
190 // {1, 2, 3, X}
191 // T H
192 assert(rb->cb.buf[0] == 1);
193 assert(rb->cb.buf[1] == 2);
194 assert(rb->cb.buf[2] == 3);
195 assert(rb->cb.buf[3] == 0);
196 assert(rb->cb.head == 3);
197 assert(rb->cb.tail == 0);
198
199 ringbuf_del(rb);
200 }
201
ringbuf_append_wrap_test(void)202 void ringbuf_append_wrap_test(void) {
203 size_t count = 4;
204 ITEM item = 0;
205
206 ringbuf_t *rb = ringbuf_new(count);
207 assert(ringbuf_append(rb, 1) == 0);
208 assert(ringbuf_append(rb, 2) == 0);
209 assert(ringbuf_append(rb, 3) == 0);
210 assert(ringbuf_append(rb, 4) != 0);
211
212 // check state of ringbuffer:
213 // {1, 2, 3, X}
214 // T H
215 assert(rb->cb.buf[0] == 1);
216 assert(rb->cb.buf[1] == 2);
217 assert(rb->cb.buf[2] == 3);
218 assert(rb->cb.head == 3);
219 assert(rb->cb.tail == 0);
220
221 item = 0;
222 assert(ringbuf_read(rb, &item, 1) == 1);
223 assert(item == 1);
224
225 assert(ringbuf_append(rb, 4) == 0);
226
227 // state of ringbuffer:
228 // {1, 2, 3, 4}
229 // H T
230 assert(rb->cb.buf[0] == 1);
231 assert(rb->cb.buf[1] == 2);
232 assert(rb->cb.buf[2] == 3);
233 assert(rb->cb.buf[3] == 4);
234 assert(rb->cb.head == 0);
235 assert(rb->cb.tail == 1);
236
237 item = 0;
238 assert(ringbuf_read(rb, &item, 1) == 1);
239 assert(item == 2);
240
241 // test wraparound
242 assert(ringbuf_append(rb, 5) == 0);
243
244 // state of ringbuffer:
245 // {1, 2, 3, 4}
246 // H T
247 assert(rb->cb.buf[0] == 5);
248 assert(rb->cb.buf[1] == 2);
249 assert(rb->cb.buf[2] == 3);
250 assert(rb->cb.buf[3] == 4);
251 assert(rb->cb.head == 1);
252 assert(rb->cb.tail == 2);
253
254 ringbuf_del(rb);
255 }
256
ringbuf_append_overwrite_test(void)257 void ringbuf_append_overwrite_test(void) {
258 size_t count = 4;
259 ringbuf_t *rb = ringbuf_new(count);
260 assert(ringbuf_append_with_overwrite(rb, 1) == 0);
261 assert(ringbuf_append_with_overwrite(rb, 2) == 0);
262 assert(ringbuf_append_with_overwrite(rb, 3) == 0);
263 assert(ringbuf_append_with_overwrite(rb, 4) == 0);
264
265 // check state of ringbuffer:
266 // {1, 2, 3, 4}
267 // H T
268 assert(rb->cb.buf[0] == 1);
269 assert(rb->cb.buf[1] == 2);
270 assert(rb->cb.buf[2] == 3);
271 assert(rb->cb.buf[3] == 4);
272 assert(rb->cb.head == 0);
273 assert(rb->cb.tail == 1);
274
275 assert(ringbuf_append_with_overwrite(rb, 5) == 0);
276 // check state of ringbuffer:
277 // {5, 2, 3, 4}
278 // H T
279 assert(rb->cb.buf[0] == 5);
280 assert(rb->cb.buf[1] == 2);
281 assert(rb->cb.buf[2] == 3);
282 assert(rb->cb.buf[3] == 4);
283 assert(rb->cb.head == 1);
284 assert(rb->cb.tail == 2);
285
286 ringbuf_del(rb);
287 }
288
ringbuf_read_test(void)289 void ringbuf_read_test(void) {
290 size_t count = 4;
291 ringbuf_t *rb = ringbuf_new(count);
292 ITEM item_array[3];
293 ITEM expects[] = {1, 2, 3};
294 ITEM expects2[] = {4};
295
296 assert(ringbuf_append_with_overwrite(rb, 1) == 0);
297 assert(ringbuf_append_with_overwrite(rb, 2) == 0);
298 assert(ringbuf_append_with_overwrite(rb, 3) == 0);
299
300 assert(ringbuf_read(rb, item_array, count) == 3);
301 assert(memcmp(item_array, expects, 3) == 0);
302
303 // check state of ringbuffer:
304 // {X, X, X, X}
305 // H
306 // T
307 assert(rb->cb.head == 3);
308 assert(rb->cb.tail == 3);
309
310 assert(ringbuf_append_with_overwrite(rb, 4) == 0);
311 assert(ringbuf_read(rb, item_array, count) == 1);
312 assert(memcmp(item_array, expects2, 1) == 0);
313 assert(rb->cb.head == 0);
314 assert(rb->cb.tail == 0);
315
316 ringbuf_del(rb);
317 }
318
ringbuf_read_to_end_test(void)319 void ringbuf_read_to_end_test(void) {
320 size_t count = 4;
321 ringbuf_t *rb = ringbuf_new(count);
322 ITEM item_array[3];
323 ITEM expects[] = {1, 2, 3};
324 ITEM expects2[] = {4};
325
326 assert(ringbuf_append_with_overwrite(rb, 1) == 0);
327 assert(ringbuf_append_with_overwrite(rb, 2) == 0);
328 assert(ringbuf_append_with_overwrite(rb, 3) == 0);
329
330 // state of ringbuffer:
331 // {1, 2, 3, X}
332 // T H
333 assert(ringbuf_read_to_end(rb, item_array, 3) == 3);
334 assert(memcmp(item_array, expects, 3) == 0);
335
336 // check state of ringbuffer:
337 // {1, 2, 3, X}
338 // H
339 // T
340 assert(rb->cb.head == 3);
341 assert(rb->cb.tail == 3);
342
343 assert(ringbuf_append_with_overwrite(rb, 4) == 0);
344 // state of ringbuffer:
345 // {1, 2, 3, 4}
346 // H T
347 assert(ringbuf_read_to_end(rb, item_array, count) == 1);
348
349 // check state of ringbuffer (empty):
350 // {1, 2, 3, 4}
351 // H
352 // T
353 assert(memcmp(item_array, expects2, 1) == 0);
354 assert(rb->cb.head == 0);
355 assert(rb->cb.tail == 0);
356
357 ringbuf_del(rb);
358 }
359 /* ---- END RINGBUFFER TESTS ---- */
360
361