[systemd-devel] [RFC 02/12] ring: add basic ring-buffer helper

[Lucas De Marchi]

On Wed, Nov 27, 2013 at 4:48 PM, David Herrmann <dh.herrmann at 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 0000000..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.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 <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