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

[David Herrmann]

Hi

On Thu, Nov 28, 2013 at 1:27 AM, Lucas De Marchi
<lucas.de.marchi at gmail.com> wrote:
> 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.

Yepp, that one looks good. Didn't know there was a builtin to count
leading zeros.

Thanks
David