[systemd-commits] 2 commits - .gitignore Makefile.am src/shared src/test
David Herrmann
dvdhrm at kemper.freedesktop.org
Tue May 13 13:09:17 PDT 2014
.gitignore | 1
Makefile.am | 9 ++
src/shared/macro.h | 13 +++
src/shared/ring.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++++++
src/shared/ring.h | 59 ++++++++++++++
src/test/test-ring.c | 135 +++++++++++++++++++++++++++++++++
src/test/test-util.c | 31 +++++++
7 files changed, 456 insertions(+)
New commits:
commit e0dd92729e68e0005866a890d8209ddcf3568805
Author: David Herrmann <dh.herrmann at gmail.com>
Date: Tue May 13 20:08:18 2014 +0200
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.
diff --git a/.gitignore b/.gitignore
index 03f1b72..83fbe74 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 c54d357..653fcfc 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 0000000..8ae6123
--- /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 <dh.herrmann at gmail.com>
+
+ 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 <http://www.gnu.org/licenses/>.
+***/
+
+#include <errno.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/uio.h>
+#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 <sys/uio.h> 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 0000000..6b12530
--- /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 <dh.herrmann at gmail.com>
+
+ 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 <http://www.gnu.org/licenses/>.
+***/
+
+#include <errno.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/uio.h>
+
+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 0000000..8808158
--- /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 <dh.herrmann at gmail.com>
+
+ 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 <http://www.gnu.org/licenses/>.
+***/
+
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <locale.h>
+#include <errno.h>
+
+#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;
+}
commit 625e870b4fb7ff4caf4d8a4614e9bda7c174b291
Author: David Herrmann <dh.herrmann at gmail.com>
Date: Tue May 13 19:47:58 2014 +0200
shared: add ALIGN_POWER2 macro
Sounds easy, turns out to be horrible to implement: ALIGN_POWER2 returns
the next higher power of 2. clz(0) is undefined, same is true for
left-shift-overflows, yey, C rocks!
diff --git a/src/shared/macro.h b/src/shared/macro.h
index d53b07f..53bd578 100644
--- a/src/shared/macro.h
+++ b/src/shared/macro.h
@@ -100,6 +100,19 @@ static inline size_t ALIGN_TO(size_t l, size_t ali) {
#define ALIGN_TO_PTR(p, ali) ((void*) ALIGN_TO((unsigned long) p, ali))
+/* align to next higher power-of-2 (except for: 0 => 0, overflow => 0) */
+static inline unsigned long ALIGN_POWER2(unsigned long u) {
+ /* clz(0) is undefined */
+ if (u == 1)
+ return 1;
+
+ /* left-shift overflow is undefined */
+ if (__builtin_clzl(u - 1UL) < 1)
+ return 0;
+
+ return 1UL << (sizeof(u) * 8 - __builtin_clzl(u - 1UL));
+}
+
#define ELEMENTSOF(x) (sizeof(x)/sizeof((x)[0]))
/*
diff --git a/src/test/test-util.c b/src/test/test-util.c
index 93929cd..caf8d2b 100644
--- a/src/test/test-util.c
+++ b/src/test/test-util.c
@@ -37,6 +37,36 @@ static void test_streq_ptr(void) {
assert_se(!streq_ptr("abc", "cdef"));
}
+static void test_align_power2(void) {
+ unsigned long i, p2;
+
+ assert_se(ALIGN_POWER2(0) == 0);
+ assert_se(ALIGN_POWER2(1) == 1);
+ assert_se(ALIGN_POWER2(2) == 2);
+ assert_se(ALIGN_POWER2(3) == 4);
+ assert_se(ALIGN_POWER2(12) == 16);
+
+ assert_se(ALIGN_POWER2(ULONG_MAX) == 0);
+ assert_se(ALIGN_POWER2(ULONG_MAX - 1) == 0);
+ assert_se(ALIGN_POWER2(ULONG_MAX - 1024) == 0);
+ assert_se(ALIGN_POWER2(ULONG_MAX / 2) == ULONG_MAX / 2 + 1);
+ assert_se(ALIGN_POWER2(ULONG_MAX + 1) == 0);
+
+ for (i = 1; i < 131071; ++i) {
+ for (p2 = 1; p2 < i; p2 <<= 1)
+ /* empty */ ;
+
+ assert_se(ALIGN_POWER2(i) == p2);
+ }
+
+ for (i = ULONG_MAX - 1024; i < ULONG_MAX; ++i) {
+ for (p2 = 1; p2 && p2 < i; p2 <<= 1)
+ /* empty */ ;
+
+ assert_se(ALIGN_POWER2(i) == p2);
+ }
+}
+
static void test_first_word(void) {
assert_se(first_word("Hello", ""));
assert_se(first_word("Hello", "Hello"));
@@ -680,6 +710,7 @@ int main(int argc, char *argv[]) {
log_open();
test_streq_ptr();
+ test_align_power2();
test_first_word();
test_close_many();
test_parse_boolean();
More information about the systemd-commits
mailing list