From e0dd92729e68e0005866a890d8209ddcf3568805 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Tue, 13 May 2014 20:08:18 +0200 Subject: [PATCH] shared: add ring buffer New "struct ring" object that implements a basic ring buffer for arbitrary byte-streams. A new basic runtime test is also added. This will be needed for our pty helpers for systemd-console and friends. --- .gitignore | 1 + Makefile.am | 9 ++ src/shared/ring.c | 208 +++++++++++++++++++++++++++++++++++++++++++ src/shared/ring.h | 59 ++++++++++++ src/test/test-ring.c | 135 ++++++++++++++++++++++++++++ 5 files changed, 412 insertions(+) create mode 100644 src/shared/ring.c create mode 100644 src/shared/ring.h create mode 100644 src/test/test-ring.c diff --git a/.gitignore b/.gitignore index 03f1b7235..83fbe7479 100644 --- a/.gitignore +++ b/.gitignore @@ -180,6 +180,7 @@ /test-path-util /test-prioq /test-replace-var +/test-ring /test-rtnl /test-sched-prio /test-sleep diff --git a/Makefile.am b/Makefile.am index c54d35760..653fcfcda 100644 --- a/Makefile.am +++ b/Makefile.am @@ -801,6 +801,8 @@ libsystemd_shared_la_SOURCES = \ src/shared/clean-ipc.c \ src/shared/login-shared.c \ src/shared/login-shared.h \ + src/shared/ring.c \ + src/shared/ring.h \ src/shared/async.c \ src/shared/async.h @@ -1198,6 +1200,7 @@ tests += \ test-utf8 \ test-ellipsize \ test-util \ + test-ring \ test-tmpfiles \ test-namespace \ test-date \ @@ -1325,6 +1328,12 @@ test_util_SOURCES = \ test_util_LDADD = \ libsystemd-core.la +test_ring_SOURCES = \ + src/test/test-ring.c + +test_ring_LDADD = \ + libsystemd-core.la + test_tmpfiles_SOURCES = \ src/test/test-tmpfiles.c diff --git a/src/shared/ring.c b/src/shared/ring.c new file mode 100644 index 000000000..8ae61234c --- /dev/null +++ b/src/shared/ring.c @@ -0,0 +1,208 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +/*** + This file is part of systemd. + + Copyright 2014 David Herrmann + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include +#include +#include +#include +#include +#include "macro.h" +#include "ring.h" + +#define RING_MASK(_r, _v) ((_v) & ((_r)->size - 1)) + +void ring_flush(struct ring *r) { + assert(r); + + r->start = 0; + r->used = 0; +} + +void ring_clear(struct ring *r) { + free(r->buf); + zero(*r); +} + +/* + * Get data pointers for current ring-buffer data. @vec must be an array of 2 + * iovec objects. They are filled according to the data available in the + * ring-buffer. 0, 1 or 2 is returned according to the number of iovec objects + * that were filled (0 meaning buffer is empty). + * + * Hint: "struct iovec" is defined in and looks like this: + * struct iovec { + * void *iov_base; + * size_t iov_len; + * }; + */ +size_t ring_peek(struct ring *r, struct iovec *vec) { + assert(r); + + if (r->used == 0) { + return 0; + } else if (r->start + r->used <= r->size) { + if (vec) { + vec[0].iov_base = &r->buf[r->start]; + vec[0].iov_len = r->used; + } + return 1; + } else { + if (vec) { + vec[0].iov_base = &r->buf[r->start]; + vec[0].iov_len = r->size - r->start; + vec[1].iov_base = r->buf; + vec[1].iov_len = r->used - (r->size - r->start); + } + return 2; + } +} + +/* + * Copy data from the ring buffer into the linear external buffer @buf. Copy + * at most @size bytes. If the ring buffer size is smaller, copy less bytes and + * return the number of bytes copied. + */ +size_t ring_copy(struct ring *r, void *buf, size_t size) { + size_t l; + + assert(r); + assert(buf); + + if (size > r->used) + size = r->used; + + if (size > 0) { + l = r->size - r->start; + if (size <= l) { + memcpy(buf, &r->buf[r->start], size); + } else { + memcpy(buf, &r->buf[r->start], l); + memcpy((uint8_t*)buf + l, r->buf, size - l); + } + } + + return size; +} + +/* + * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise + * ring operations will behave incorrectly. + */ +static int ring_resize(struct ring *r, size_t nsize) { + uint8_t *buf; + size_t l; + + assert(r); + assert(nsize > 0); + + buf = malloc(nsize); + if (!buf) + return -ENOMEM; + + if (r->used > 0) { + l = r->size - r->start; + if (r->used <= l) { + memcpy(buf, &r->buf[r->start], r->used); + } else { + memcpy(buf, &r->buf[r->start], l); + memcpy(&buf[l], r->buf, r->used - l); + } + } + + free(r->buf); + r->buf = buf; + r->size = nsize; + r->start = 0; + + return 0; +} + +/* + * Resize ring-buffer to provide enough room for @add bytes of new data. This + * resizes the buffer if it is too small. It returns -ENOMEM on OOM and 0 on + * success. + */ +static int ring_grow(struct ring *r, size_t add) { + size_t need; + + assert(r); + + if (r->size - r->used >= add) + return 0; + + need = r->used + add; + if (need <= r->used) + return -ENOMEM; + else if (need < 4096) + need = 4096; + + need = ALIGN_POWER2(need); + if (need == 0) + return -ENOMEM; + + return ring_resize(r, need); +} + +/* + * Push @len bytes from @u8 into the ring buffer. The buffer is resized if it + * is too small. -ENOMEM is returned on OOM, 0 on success. + */ +int ring_push(struct ring *r, const void *u8, size_t size) { + int err; + size_t pos, l; + + assert(r); + assert(u8); + + if (size == 0) + return 0; + + err = ring_grow(r, size); + if (err < 0) + return err; + + pos = RING_MASK(r, r->start + r->used); + l = r->size - pos; + if (l >= size) { + memcpy(&r->buf[pos], u8, size); + } else { + memcpy(&r->buf[pos], u8, l); + memcpy(r->buf, (const uint8_t*)u8 + l, size - l); + } + + r->used += size; + + return 0; +} + +/* + * Remove @len bytes from the start of the ring-buffer. Note that we protect + * against overflows so removing more bytes than available is safe. + */ +void ring_pull(struct ring *r, size_t size) { + assert(r); + + if (size > r->used) + size = r->used; + + r->start = RING_MASK(r, r->start + size); + r->used -= size; +} diff --git a/src/shared/ring.h b/src/shared/ring.h new file mode 100644 index 000000000..6b12530e3 --- /dev/null +++ b/src/shared/ring.h @@ -0,0 +1,59 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +#pragma once + +/*** + This file is part of systemd. + + Copyright 2014 David Herrmann + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include +#include +#include +#include +#include + +struct ring { + uint8_t *buf; /* buffer or NULL */ + size_t size; /* actual size of @buf */ + size_t start; /* start position of ring */ + size_t used; /* number of actually used bytes */ +}; + +/* flush buffer so it is empty again */ +void ring_flush(struct ring *r); + +/* flush buffer, free allocated data and reset to initial state */ +void ring_clear(struct ring *r); + +/* get pointers to buffer data and their length */ +size_t ring_peek(struct ring *r, struct iovec *vec); + +/* copy data into external linear buffer */ +size_t ring_copy(struct ring *r, void *buf, size_t size); + +/* push data to the end of the buffer */ +int ring_push(struct ring *r, const void *u8, size_t size); + +/* pull data from the front of the buffer */ +void ring_pull(struct ring *r, size_t size); + +/* return size of occupied buffer in bytes */ +static inline size_t ring_get_size(struct ring *r) +{ + return r->used; +} diff --git a/src/test/test-ring.c b/src/test/test-ring.c new file mode 100644 index 000000000..880815811 --- /dev/null +++ b/src/test/test-ring.c @@ -0,0 +1,135 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +/*** + This file is part of systemd. + + Copyright 2014 David Herrmann + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd 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 + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include +#include +#include +#include +#include + +#include "def.h" +#include "ring.h" +#include "util.h" + +static void test_ring(void) { + static const char buf[8192]; + struct ring r; + size_t l; + struct iovec vec[2]; + int s; + + memset(&r, 0, sizeof(r)); + + l = ring_peek(&r, vec); + assert_se(l == 0); + + s = ring_push(&r, buf, 2048); + assert_se(!s); + assert_se(ring_get_size(&r) == 2048); + + l = ring_peek(&r, vec); + assert_se(l == 1); + assert_se(vec[0].iov_len == 2048); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(ring_get_size(&r) == 2048); + + ring_pull(&r, 2048); + assert_se(ring_get_size(&r) == 0); + + l = ring_peek(&r, vec); + assert_se(l == 0); + assert_se(ring_get_size(&r) == 0); + + s = ring_push(&r, buf, 2048); + assert_se(!s); + assert_se(ring_get_size(&r) == 2048); + + l = ring_peek(&r, vec); + assert_se(l == 1); + assert_se(vec[0].iov_len == 2048); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(ring_get_size(&r) == 2048); + + s = ring_push(&r, buf, 1); + assert_se(!s); + assert_se(ring_get_size(&r) == 2049); + + l = ring_peek(&r, vec); + assert_se(l == 2); + assert_se(vec[0].iov_len == 2048); + assert_se(vec[1].iov_len == 1); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(!memcmp(vec[1].iov_base, buf, vec[1].iov_len)); + assert_se(ring_get_size(&r) == 2049); + + ring_pull(&r, 2048); + assert_se(ring_get_size(&r) == 1); + + l = ring_peek(&r, vec); + assert_se(l == 1); + assert_se(vec[0].iov_len == 1); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(ring_get_size(&r) == 1); + + ring_pull(&r, 1); + assert_se(ring_get_size(&r) == 0); + + s = ring_push(&r, buf, 2048); + assert_se(!s); + assert_se(ring_get_size(&r) == 2048); + + s = ring_push(&r, buf, 2049); + assert_se(!s); + assert_se(ring_get_size(&r) == 4097); + + l = ring_peek(&r, vec); + assert_se(l == 1); + assert_se(vec[0].iov_len == 4097); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(ring_get_size(&r) == 4097); + + ring_pull(&r, 1); + assert_se(ring_get_size(&r) == 4096); + + s = ring_push(&r, buf, 4096); + assert_se(!s); + assert_se(ring_get_size(&r) == 8192); + + l = ring_peek(&r, vec); + assert_se(l == 2); + assert_se(vec[0].iov_len == 8191); + assert_se(vec[1].iov_len == 1); + assert_se(!memcmp(vec[0].iov_base, buf, vec[0].iov_len)); + assert_se(!memcmp(vec[1].iov_base, buf, vec[1].iov_len)); + assert_se(ring_get_size(&r) == 8192); + + ring_clear(&r); + assert_se(ring_get_size(&r) == 0); +} + +int main(int argc, char *argv[]) { + log_parse_environment(); + log_open(); + + test_ring(); + + return 0; +} -- 2.30.2