Re: [systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
On Thu, 28.11.13 09:19, David Herrmann (dh.herrm...@gmail.com) wrote:
Hmm, so if end and start match the buffer is empty? So you can never
fill it entirely? Or am I missing something?
I'd always maintain start index + fill level instead of a start
index + end index, to avoid the confusion regarding the fill-level...
Well, start+end is how ring-buffers were implemented historically. I
think the reason is that wrapping over is easier to calculate for
indices than for lengths (you cannot do: r-len = (r-len + 1)
RING_MASK). Even all examples on wikipedia use two indices
(http://en.wikipedia.org/wiki/Circular_buffer). And all kernel
ring-buffers use start/end..
Well, you only need the wrapping over for the reading side, the writing
side never needs that.
int append(..., length, ...) {
...
if (current_length + length MAX_LENGTH)
return -ENOBUFS;
...
current_length += length;
...
}
int remove(..., length, ...) {
...
if (length current_length)
return -EAGAIN;
...
rindex = (rindex + length) RING_MASK;
current_length -= length;
...
}
Lennart
--
Lennart Poettering, Red Hat
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
Re: [systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
Hi
On Wed, Nov 27, 2013 at 10:53 PM, Lennart Poettering
lenn...@poettering.net wrote:
On Wed, 27.11.13 19:48, David Herrmann (dh.herrm...@gmail.com) wrote:
+void ring_flush(Ring *r) {
+r-start = 0;
+r-end = 0;
+}
+
+void ring_clear(Ring *r) {
+free(r-buf);
+memset(r, 0, sizeof(*r));
zero(*r) is a tiny bit nicer.
+}
+
+/*
+ * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise
+ * ring operations will behave incorrectly.
+ */
+static int ring_resize(Ring *r, size_t nsize) {
+char *buf;
Hmm, char suggests a bit that this is about text. But it's mostly raw
bytes, right? So I'd always use uint8_t for these things, it feels so
much rawer... Not that it would matter much...
Yepp, uint8_t it is.
+
+buf = malloc(nsize);
+if (!buf)
+return -ENOMEM;
+
+if (r-end == r-start) {
+r-end = 0;
+r-start = 0;
Hmm, so if end and start match the buffer is empty? So you can never
fill it entirely? Or am I missing something?
I'd always maintain start index + fill level instead of a start
index + end index, to avoid the confusion regarding the fill-level...
Well, start+end is how ring-buffers were implemented historically. I
think the reason is that wrapping over is easier to calculate for
indices than for lengths (you cannot do: r-len = (r-len + 1)
RING_MASK). Even all examples on wikipedia use two indices
(http://en.wikipedia.org/wiki/Circular_buffer). And all kernel
ring-buffers use start/end..
Also note that the one special byte is not unused. It cannot be
filled, in case the buffer is full, that's right. But it's used during
normal buffer-operation if the occupied space moves along the
buffer.
If you can find me circular/ring-buffers that use start+len, I can fix
that up. Otherwise, I'd rather keep this close to existing
implementations. Besides, a lot of wrapping calculations get easier
if start/end are restricted by RING_MASK, which wouldn't be the case
for len.
+ * 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(Ring *r, const char *u8, size_t len) {
So, here you call the parameter u8 suggesting unsigned bytes, but you
use char, which indicates a text string, and is
signed... Confusing. I'd recommend using const void * here by default,
since all types implicitly downgrade to const void* without casting...
I usually use u8 for utf8.. no idea where that came from. But yes,
void* makes sense for input/output and uint8_t* for internal
operations.
Thanks
David
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
Re: [systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
Hi
On Thu, Nov 28, 2013 at 1:27 AM, Lucas De Marchi
lucas.de.mar...@gmail.com wrote:
On Wed, Nov 27, 2013 at 4:48 PM, David Herrmann dh.herrm...@gmail.com wrote:
This adds a very straightforward ring-buffer implementation to
libsystemd-shared. Ring-buffers allow pushing data to, and pulling data
from, both ends of a buffer without modifying existing/remaining buffer
content. This is very useful for network buffers and asynchronous writes.
This implementation only contains the most basic functions to push data
onto the end of the buffer and pull data from the front. More helpers may
be added once needed.
---
Makefile.am | 2 +
src/shared/ring.c | 213
++
src/shared/ring.h | 54 ++
3 files changed, 269 insertions(+)
create mode 100644 src/shared/ring.c
create mode 100644 src/shared/ring.h
diff --git a/Makefile.am b/Makefile.am
index 0119751..4aa2bdf 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -768,6 +768,8 @@ libsystemd_shared_la_SOURCES = \
src/shared/net-util.h \
src/shared/errno-list.c \
src/shared/errno-list.h \
+ src/shared/ring.h \
+ src/shared/ring.c \
src/shared/syscall-list.c \
src/shared/syscall-list.h
diff --git a/src/shared/ring.c b/src/shared/ring.c
new file mode 100644
index 000..f60f098
--- /dev/null
+++ b/src/shared/ring.c
@@ -0,0 +1,213 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2013 David Herrmann dh.herrm...@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 stdlib.h
+#include string.h
+#include sys/uio.h
+
+#include ring.h
+#include util.h
+
+#define RING_MASK(_r, _v) ((_v) ((_r)-size - 1))
+
+void ring_flush(Ring *r) {
+r-start = 0;
+r-end = 0;
+}
+
+void ring_clear(Ring *r) {
+free(r-buf);
+memset(r, 0, sizeof(*r));
+}
+
+/*
+ * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise
+ * ring operations will behave incorrectly.
+ */
+static int ring_resize(Ring *r, size_t nsize) {
+char *buf;
+
+buf = malloc(nsize);
+if (!buf)
+return -ENOMEM;
+
+if (r-end == r-start) {
+r-end = 0;
+r-start = 0;
+} else if (r-end r-start) {
+memcpy(buf, r-buf[r-start], r-end - r-start);
+
+r-end -= r-start;
+r-start = 0;
+} else {
+memcpy(buf, r-buf[r-start], r-size - r-start);
+memcpy(buf[r-size - r-start], r-buf, r-end);
+
+r-end += r-size - r-start;
+r-start = 0;
+}
+
+free(r-buf);
+r-buf = buf;
+r-size = nsize;
+
+return 0;
+}
+
+/* Compute next higher power-of-2 of @v. Returns 4096 in case v is 0. */
+static size_t ring_pow2(size_t v) {
+size_t i;
+
+if (!v)
+return 4096;
+
+--v;
+
+for (i = 1; i 8 * sizeof(size_t); i *= 2)
+v |= v i;
+
+return ++v;
If you are interested, take a look in
https://git.kernel.org/cgit/utils/kernel/kmod/kmod.git/commit/?id=3ba7f59e84857eb4dbe56a68fc7a3ffe8a650393
for a shorter and faster version of this.
Yepp, that one looks good. Didn't know there was a builtin to count
leading zeros.
Thanks
David
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
[systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
This adds a very straightforward ring-buffer implementation to
libsystemd-shared. Ring-buffers allow pushing data to, and pulling data
from, both ends of a buffer without modifying existing/remaining buffer
content. This is very useful for network buffers and asynchronous writes.
This implementation only contains the most basic functions to push data
onto the end of the buffer and pull data from the front. More helpers may
be added once needed.
---
Makefile.am | 2 +
src/shared/ring.c | 213 ++
src/shared/ring.h | 54 ++
3 files changed, 269 insertions(+)
create mode 100644 src/shared/ring.c
create mode 100644 src/shared/ring.h
diff --git a/Makefile.am b/Makefile.am
index 0119751..4aa2bdf 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -768,6 +768,8 @@ libsystemd_shared_la_SOURCES = \
src/shared/net-util.h \
src/shared/errno-list.c \
src/shared/errno-list.h \
+ src/shared/ring.h \
+ src/shared/ring.c \
src/shared/syscall-list.c \
src/shared/syscall-list.h
diff --git a/src/shared/ring.c b/src/shared/ring.c
new file mode 100644
index 000..f60f098
--- /dev/null
+++ b/src/shared/ring.c
@@ -0,0 +1,213 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2013 David Herrmann dh.herrm...@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 stdlib.h
+#include string.h
+#include sys/uio.h
+
+#include ring.h
+#include util.h
+
+#define RING_MASK(_r, _v) ((_v) ((_r)-size - 1))
+
+void ring_flush(Ring *r) {
+r-start = 0;
+r-end = 0;
+}
+
+void ring_clear(Ring *r) {
+free(r-buf);
+memset(r, 0, sizeof(*r));
+}
+
+/*
+ * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise
+ * ring operations will behave incorrectly.
+ */
+static int ring_resize(Ring *r, size_t nsize) {
+char *buf;
+
+buf = malloc(nsize);
+if (!buf)
+return -ENOMEM;
+
+if (r-end == r-start) {
+r-end = 0;
+r-start = 0;
+} else if (r-end r-start) {
+memcpy(buf, r-buf[r-start], r-end - r-start);
+
+r-end -= r-start;
+r-start = 0;
+} else {
+memcpy(buf, r-buf[r-start], r-size - r-start);
+memcpy(buf[r-size - r-start], r-buf, r-end);
+
+r-end += r-size - r-start;
+r-start = 0;
+}
+
+free(r-buf);
+r-buf = buf;
+r-size = nsize;
+
+return 0;
+}
+
+/* Compute next higher power-of-2 of @v. Returns 4096 in case v is 0. */
+static size_t ring_pow2(size_t v) {
+size_t i;
+
+if (!v)
+return 4096;
+
+--v;
+
+for (i = 1; i 8 * sizeof(size_t); i *= 2)
+v |= v i;
+
+return ++v;
+}
+
+/*
+ * 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(Ring *r, size_t add) {
+size_t len;
+
+/*
+ * Note that end == start means empty buffer. Hence, we can never
+ * fill the last byte of a buffer. That means, we must account for an
+ * additional byte here (end == start-byte).
+ */
+
+if (r-end r-start)
+len = r-start - r-end;
+else
+len = r-start + r-size - r-end;
+
+/* don't use = as end == start would be ambigious */
+if (len add)
+return 0;
+
+/* +1 for additional end == start byte */
+len = r-size + add - len + 1;
+len = ring_pow2(len);
+
+if (len = r-size)
+return -ENOMEM;
+
+return ring_resize(r, len);
+}
+
+/*
+ * 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(Ring *r, const char *u8, size_t len) {
+int err;
+size_t l;
+
+err = ring_grow(r, len);
+if (err 0)
+return err;
+
+if (r-start = r-end) {
+l = r-size - r-end;
+if (l len)
+l = len;
+
Re: [systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
On Wed, 27.11.13 19:48, David Herrmann (dh.herrm...@gmail.com) wrote:
+void ring_flush(Ring *r) {
+r-start = 0;
+r-end = 0;
+}
+
+void ring_clear(Ring *r) {
+free(r-buf);
+memset(r, 0, sizeof(*r));
zero(*r) is a tiny bit nicer.
+}
+
+/*
+ * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise
+ * ring operations will behave incorrectly.
+ */
+static int ring_resize(Ring *r, size_t nsize) {
+char *buf;
Hmm, char suggests a bit that this is about text. But it's mostly raw
bytes, right? So I'd always use uint8_t for these things, it feels so
much rawer... Not that it would matter much...
+
+buf = malloc(nsize);
+if (!buf)
+return -ENOMEM;
+
+if (r-end == r-start) {
+r-end = 0;
+r-start = 0;
Hmm, so if end and start match the buffer is empty? So you can never
fill it entirely? Or am I missing something?
I'd always maintain start index + fill level instead of a start
index + end index, to avoid the confusion regarding the fill-level...
+ * 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(Ring *r, const char *u8, size_t len) {
So, here you call the parameter u8 suggesting unsigned bytes, but you
use char, which indicates a text string, and is
signed... Confusing. I'd recommend using const void * here by default,
since all types implicitly downgrade to const void* without casting...
Lennart
--
Lennart Poettering, Red Hat
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
Re: [systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper
On Wed, Nov 27, 2013 at 4:48 PM, David Herrmann dh.herrm...@gmail.com wrote:
This adds a very straightforward ring-buffer implementation to
libsystemd-shared. Ring-buffers allow pushing data to, and pulling data
from, both ends of a buffer without modifying existing/remaining buffer
content. This is very useful for network buffers and asynchronous writes.
This implementation only contains the most basic functions to push data
onto the end of the buffer and pull data from the front. More helpers may
be added once needed.
---
Makefile.am | 2 +
src/shared/ring.c | 213
++
src/shared/ring.h | 54 ++
3 files changed, 269 insertions(+)
create mode 100644 src/shared/ring.c
create mode 100644 src/shared/ring.h
diff --git a/Makefile.am b/Makefile.am
index 0119751..4aa2bdf 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -768,6 +768,8 @@ libsystemd_shared_la_SOURCES = \
src/shared/net-util.h \
src/shared/errno-list.c \
src/shared/errno-list.h \
+ src/shared/ring.h \
+ src/shared/ring.c \
src/shared/syscall-list.c \
src/shared/syscall-list.h
diff --git a/src/shared/ring.c b/src/shared/ring.c
new file mode 100644
index 000..f60f098
--- /dev/null
+++ b/src/shared/ring.c
@@ -0,0 +1,213 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2013 David Herrmann dh.herrm...@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 stdlib.h
+#include string.h
+#include sys/uio.h
+
+#include ring.h
+#include util.h
+
+#define RING_MASK(_r, _v) ((_v) ((_r)-size - 1))
+
+void ring_flush(Ring *r) {
+r-start = 0;
+r-end = 0;
+}
+
+void ring_clear(Ring *r) {
+free(r-buf);
+memset(r, 0, sizeof(*r));
+}
+
+/*
+ * Resize ring-buffer to size @nsize. @nsize must be a power-of-2, otherwise
+ * ring operations will behave incorrectly.
+ */
+static int ring_resize(Ring *r, size_t nsize) {
+char *buf;
+
+buf = malloc(nsize);
+if (!buf)
+return -ENOMEM;
+
+if (r-end == r-start) {
+r-end = 0;
+r-start = 0;
+} else if (r-end r-start) {
+memcpy(buf, r-buf[r-start], r-end - r-start);
+
+r-end -= r-start;
+r-start = 0;
+} else {
+memcpy(buf, r-buf[r-start], r-size - r-start);
+memcpy(buf[r-size - r-start], r-buf, r-end);
+
+r-end += r-size - r-start;
+r-start = 0;
+}
+
+free(r-buf);
+r-buf = buf;
+r-size = nsize;
+
+return 0;
+}
+
+/* Compute next higher power-of-2 of @v. Returns 4096 in case v is 0. */
+static size_t ring_pow2(size_t v) {
+size_t i;
+
+if (!v)
+return 4096;
+
+--v;
+
+for (i = 1; i 8 * sizeof(size_t); i *= 2)
+v |= v i;
+
+return ++v;
If you are interested, take a look in
https://git.kernel.org/cgit/utils/kernel/kmod/kmod.git/commit/?id=3ba7f59e84857eb4dbe56a68fc7a3ffe8a650393
for a shorter and faster version of this.
Lucas De Marchi
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
