diff options
| -rw-r--r-- | lib/ringbuf.c | 104 | ||||
| -rw-r--r-- | lib/ringbuf.h | 100 | ||||
| -rw-r--r-- | lib/subdir.am | 2 | ||||
| -rw-r--r-- | tests/Makefile.am | 4 | ||||
| -rw-r--r-- | tests/lib/test_ringbuf.c | 175 | ||||
| -rw-r--r-- | tests/lib/test_ringbuf.py | 4 |
6 files changed, 389 insertions, 0 deletions
diff --git a/lib/ringbuf.c b/lib/ringbuf.c new file mode 100644 index 0000000000..fee5b5d691 --- /dev/null +++ b/lib/ringbuf.c @@ -0,0 +1,104 @@ +/* + * Circular buffer implementation. + * Copyright (C) 2017 Cumulus Networks + * Quentin Young + * + * This program 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; either version 2 of the License, or (at your option) + * any later version. + * + * This program 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 have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#include <zebra.h> + +#include "ringbuf.h" +#include "memory.h" + +DEFINE_MTYPE_STATIC(LIB, RINGBUFFER, "Ring buffer") + +struct ringbuf *ringbuf_new(size_t size) +{ + struct ringbuf *buf = XCALLOC(MTYPE_RINGBUFFER, sizeof(struct ringbuf)); + buf->data = XCALLOC(MTYPE_RINGBUFFER, size); + buf->size = size; + buf->empty = true; + return buf; +} + +void ringbuf_del(struct ringbuf *buf) +{ + XFREE(MTYPE_RINGBUFFER, buf->data); + XFREE(MTYPE_RINGBUFFER, buf); +} + +size_t ringbuf_remain(struct ringbuf *buf) +{ + ssize_t diff = buf->end - buf->start; + diff += ((diff == 0) && !buf->empty) ? buf->size : 0; + diff += (diff < 0) ? buf->size : 0; + return (size_t)diff; +} + +size_t ringbuf_space(struct ringbuf *buf) +{ + return buf->size - ringbuf_remain(buf); +} + +size_t ringbuf_put(struct ringbuf *buf, const void *data, size_t size) +{ + const uint8_t *dp = data; + size_t space = ringbuf_space(buf); + size_t copysize = MIN(size, space); + size_t tocopy = copysize; + if (tocopy > buf->size - buf->end) { + size_t ts = buf->size - buf->end; + memcpy(buf->data + buf->end, dp, ts); + buf->end = 0; + tocopy -= ts; + dp += ts; + } + memcpy(buf->data + buf->end, dp, tocopy); + buf->end += tocopy; + buf->empty = (buf->start == buf->end) && (buf->empty && !copysize); + return copysize; +} + +size_t ringbuf_get(struct ringbuf *buf, void *data, size_t size) +{ + uint8_t *dp = data; + size_t remain = ringbuf_remain(buf); + size_t copysize = MIN(remain, size); + size_t tocopy = copysize; + if (tocopy > buf->size - buf->start) { + size_t ts = buf->size - buf->start; + memcpy(dp, buf->data + buf->start, ts); + buf->start = 0; + tocopy -= ts; + dp += ts; + } + memcpy(dp, buf->data + buf->start, tocopy); + buf->start = buf->start + tocopy; + buf->empty = (buf->start == buf->end) && (buf->empty || copysize); + return copysize; +} + +void ringbuf_reset(struct ringbuf *buf) +{ + buf->start = buf->end = 0; + buf->empty = true; +} + +void ringbuf_wipe(struct ringbuf *buf) +{ + memset(buf->data, 0x00, buf->size); + ringbuf_reset(buf); + buf->empty = true; +} diff --git a/lib/ringbuf.h b/lib/ringbuf.h new file mode 100644 index 0000000000..af07c93a66 --- /dev/null +++ b/lib/ringbuf.h @@ -0,0 +1,100 @@ +/* + * Circular buffer implementation. + * Copyright (C) 2017 Cumulus Networks + * Quentin Young + * + * This program 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; either version 2 of the License, or (at your option) + * any later version. + * + * This program 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 have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#ifndef _FRR_RINGBUF_H_ +#define _FRR_RINGBUF_H_ + +#include <zebra.h> +#include <stdint.h> + +#include "memory.h" + +struct ringbuf { + size_t size; + ssize_t start; + ssize_t end; + bool empty; + uint8_t *data; +}; + +/* + * Creates a new ring buffer. + * + * @param size buffer size, in bytes + * @return the newly created buffer + */ +struct ringbuf *ringbuf_new(size_t size); + +/* + * Deletes a ring buffer and frees all associated resources. + * + * @param buf the ring buffer to destroy + */ +void ringbuf_del(struct ringbuf *buf); + +/* + * Get amount of data left to read from the buffer. + * + * @return number of readable bytes + */ +size_t ringbuf_remain(struct ringbuf *buf); + +/* + * Get amount of space left to write to the buffer + * + * @return number of writeable bytes + */ +size_t ringbuf_space(struct ringbuf *buf); + + +/* + * Put data into the ring buffer. + * + * @param data the data to put in the buffer + * @param size how much of data to put in + * @return number of bytes written; will be less than size if there was not + * enough space + */ +size_t ringbuf_put(struct ringbuf *buf, const void *data, size_t size); + +/* + * Get data from the ring buffer. + * + * @param data where to put the data + * @param size how much of data to get + * @return number of bytes read into data; will be less than size if there was + * not enough data to read + */ +size_t ringbuf_get(struct ringbuf *buf, void *data, size_t size); + +/* + * Reset buffer. Does not wipe. + * + * @param buf + */ +void ringbuf_reset(struct ringbuf *buf); + +/* + * Reset buffer. Wipes. + * + * @param buf + */ +void ringbuf_wipe(struct ringbuf *buf); + +#endif /* _FRR_RINGBUF_H_ */ diff --git a/lib/subdir.am b/lib/subdir.am index c8eddc8e25..44870917bd 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -51,6 +51,7 @@ lib_libfrr_la_SOURCES = \ lib/privs.c \ lib/ptm_lib.c \ lib/qobj.c \ + lib/ringbuf.c \ lib/routemap.c \ lib/sbuf.c \ lib/sha256.c \ @@ -130,6 +131,7 @@ pkginclude_HEADERS += \ lib/pw.h \ lib/qobj.h \ lib/queue.h \ + lib/ringbuf.h \ lib/routemap.h \ lib/sbuf.h \ lib/sha256.h \ diff --git a/tests/Makefile.am b/tests/Makefile.am index 2ee05fa935..f4ab2a126a 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -64,6 +64,7 @@ check_PROGRAMS = \ lib/test_memory \ lib/test_nexthop_iter \ lib/test_privs \ + lib/test_ringbuf \ lib/test_srcdest_table \ lib/test_segv \ lib/test_sig \ @@ -116,6 +117,7 @@ lib_test_nexthop_iter_SOURCES = lib/test_nexthop_iter.c helpers/c/prng.c lib_test_privs_SOURCES = lib/test_privs.c lib_test_srcdest_table_SOURCES = lib/test_srcdest_table.c \ helpers/c/prng.c +lib_test_ringbuf_SOURCES = lib/test_ringbuf.c lib_test_segv_SOURCES = lib/test_segv.c lib_test_sig_SOURCES = lib/test_sig.c lib_test_stream_SOURCES = lib/test_stream.c @@ -156,6 +158,7 @@ lib_test_heavy_LDADD = $(ALL_TESTS_LDADD) -lm lib_test_memory_LDADD = $(ALL_TESTS_LDADD) lib_test_nexthop_iter_LDADD = $(ALL_TESTS_LDADD) lib_test_privs_LDADD = $(ALL_TESTS_LDADD) +lib_test_ringbuf_LDADD = $(ALL_TESTS_LDADD) lib_test_srcdest_table_LDADD = $(ALL_TESTS_LDADD) lib_test_segv_LDADD = $(ALL_TESTS_LDADD) lib_test_sig_LDADD = $(ALL_TESTS_LDADD) @@ -196,6 +199,7 @@ EXTRA_DIST = \ lib/cli/test_cli.py \ lib/cli/test_cli.refout \ lib/test_nexthop_iter.py \ + lib/test_ringbuf.py \ lib/test_srcdest_table.py \ lib/test_stream.py \ lib/test_stream.refout \ diff --git a/tests/lib/test_ringbuf.c b/tests/lib/test_ringbuf.c new file mode 100644 index 0000000000..c689563dd6 --- /dev/null +++ b/tests/lib/test_ringbuf.c @@ -0,0 +1,175 @@ +/* + * Circular buffer tests. + * Copyright (C) 2017 Cumulus Networks + * Quentin Young + * + * This program 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; either version 2 of the License, or (at your option) + * any later version. + * + * This program 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 have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#include <zebra.h> +#include <memory.h> +#include "ringbuf.h" + +static void validate_state(struct ringbuf *buf, size_t size, size_t contains) +{ + assert(buf->size == size); + assert(ringbuf_remain(buf) == contains); + assert(ringbuf_space(buf) == buf->size - contains); + assert(buf->empty != (bool)contains); +} + +int main(int argc, char **argv) +{ + struct ringbuf *soil = ringbuf_new(BUFSIZ); + + validate_state(soil, BUFSIZ, 0); + + /* verify reset functionality on clean buffer */ + printf("Validating reset on empty buffer...\n"); + ringbuf_reset(soil); + + validate_state(soil, BUFSIZ, 0); + + /* put one byte */ + printf("Validating write...\n"); + uint8_t walnut = 47; + assert(ringbuf_put(soil, &walnut, sizeof(walnut)) == 1); + + validate_state(soil, BUFSIZ, 1); + + /* validate read limitations */ + printf("Validating read limits...\n"); + uint8_t nuts[2]; + assert(ringbuf_get(soil, &nuts, sizeof(nuts)) == 1); + + /* reset */ + printf("Validating reset on full buffer...\n"); + ringbuf_reset(soil); + validate_state(soil, BUFSIZ, 0); + + /* copy stack garbage to buffer */ + printf("Validating big write...\n"); + uint8_t compost[BUFSIZ]; + assert(ringbuf_put(soil, &compost, sizeof(compost)) == BUFSIZ); + + validate_state(soil, BUFSIZ, BUFSIZ); + assert(soil->start == 0); + assert(soil->end == BUFSIZ); + + /* read 15 bytes of garbage */ + printf("Validating read...\n"); + assert(ringbuf_get(soil, &compost, 15) == 15); + + validate_state(soil, BUFSIZ, BUFSIZ - 15); + assert(soil->start == 15); + assert(soil->end == BUFSIZ); + + /* put another 10 bytes and validate wraparound */ + printf("Validating wraparound...\n"); + assert(ringbuf_put(soil, &compost[BUFSIZ / 2], 10) == 10); + + validate_state(soil, BUFSIZ, BUFSIZ - 15 + 10); + assert(soil->start == 15); + assert(soil->end == 10); + + /* put another 15 bytes and validate state */ + printf("Validating size limits...\n"); + assert(ringbuf_put(soil, &compost, 15) == 5); + validate_state(soil, BUFSIZ, BUFSIZ); + + /* read entire buffer */ + printf("Validating big read...\n"); + assert(ringbuf_get(soil, &compost, BUFSIZ) == BUFSIZ); + + validate_state(soil, BUFSIZ, 0); + assert(soil->empty = true); + assert(soil->start == soil->end); + assert(soil->start == 15); + + /* read empty buffer */ + printf("Validating empty read...\n"); + assert(ringbuf_get(soil, &compost, 1) == 0); + validate_state(soil, BUFSIZ, 0); + + /* reset, validate state */ + printf("Validating reset...\n"); + ringbuf_reset(soil); + validate_state(soil, BUFSIZ, 0); + assert(soil->start == 0); + assert(soil->end == 0); + + /* wipe, validate state */ + printf("Validating wipe...\n"); + memset(&compost, 0x00, sizeof(compost)); + ringbuf_wipe(soil); + assert(memcmp(&compost, soil->data, sizeof(compost)) == 0); + + /* validate maximum write */ + printf("Validating very big write...\n"); + const char flower[BUFSIZ * 2]; + assert(ringbuf_put(soil, &flower, sizeof(flower)) == BUFSIZ); + + validate_state(soil, BUFSIZ, BUFSIZ); + + /* wipe, validate state */ + printf("Validating wipe...\n"); + memset(&compost, 0x00, sizeof(compost)); + ringbuf_wipe(soil); + assert(memcmp(&compost, soil->data, sizeof(compost)) == 0); + + /* validate simple data encode / decode */ + const char *organ = "seed"; + printf("Encoding: '%s'\n", organ); + ringbuf_put(soil, organ, strlen(organ)); + char water[strlen(organ) + 1]; + ringbuf_get(soil, &water, strlen(organ)); + water[strlen(organ)] = '\0'; + printf("Retrieved: '%s'\n", water); + + validate_state(soil, BUFSIZ, 0); + + /* validate simple data encode / decode across ring boundary */ + soil->start = soil->size - 2; + soil->end = soil->start; + const char *phloem = "root"; + printf("Encoding: '%s'\n", phloem); + ringbuf_put(soil, phloem, strlen(phloem)); + char xylem[strlen(phloem) + 1]; + ringbuf_get(soil, &xylem, 100); + xylem[strlen(phloem)] = '\0'; + printf("Retrieved: '%s'\n", xylem); + + printf("Deleting...\n"); + ringbuf_del(soil); + + printf("Creating new buffer...\n"); + soil = ringbuf_new(15); + soil->start = soil->end = 7; + + /* validate data encode of excessive data */ + const char *twenty = "vascular plants----"; + char sixteen[16]; + printf("Encoding: %s\n", twenty); + assert(ringbuf_put(soil, twenty, strlen(twenty)) == 15); + assert(ringbuf_get(soil, sixteen, 20)); + sixteen[15] = '\0'; + printf("Retrieved: %s\n", sixteen); + assert(!strcmp(sixteen, "vascular plants")); + + printf("Deleting...\n"); + ringbuf_del(soil); + + printf("Done.\n"); + return 0; +} diff --git a/tests/lib/test_ringbuf.py b/tests/lib/test_ringbuf.py new file mode 100644 index 0000000000..860d872f86 --- /dev/null +++ b/tests/lib/test_ringbuf.py @@ -0,0 +1,4 @@ +import frrtest + +class TestRingbuf(frrtest.TestExitNonzero): + program = './test_ringbuf' |