From bec08358369930d4631f472fce94f8adb31cdc6b Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Mon, 30 Jun 2008 02:42:40 +0000 Subject: Add a generic ring buffer implementation This piece of code is from the JACK Audio Connection Kit (trimmed down a bit for better readability). The vector functions now reuse the common iovec struct used by writev/readv instead of reinventing an identical but differently-named struct. From the comments: > ISO/POSIX C version of Paul Davis's lock free ringbuffer C++ code. > This is safe for the case of one read thread and one write thread. License is LGPL 2.1 or later git-svn-id: https://svn.musicpd.org/mpd/trunk@7386 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/Makefile.am | 2 + src/ringbuf.c | 296 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/ringbuf.h | 205 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 503 insertions(+) create mode 100644 src/ringbuf.c create mode 100644 src/ringbuf.h diff --git a/src/Makefile.am b/src/Makefile.am index 6d709c38a..9e053ef3e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -66,6 +66,7 @@ mpd_headers = \ playerData.h \ playlist.h \ replayGain.h \ + ringbuf.h \ signal_check.h \ sig_handlers.h \ sllist.h \ @@ -122,6 +123,7 @@ mpd_SOURCES = \ playerData.c \ playlist.c \ replayGain.c \ + ringbuf.c \ sig_handlers.c \ signal_check.c \ sllist.c \ diff --git a/src/ringbuf.c b/src/ringbuf.c new file mode 100644 index 000000000..517a4c216 --- /dev/null +++ b/src/ringbuf.c @@ -0,0 +1,296 @@ +/* + * This file is originally from JACK Audio Connection Kit + * + * Copyright (C) 2000 Paul Davis + * Copyright (C) 2003 Rohan Drape + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * ISO/POSIX C version of Paul Davis's lock free ringbuffer C++ code. + * This is safe for the case of one read thread and one write thread. + */ + +#include "ringbuf.h" +#include "utils.h" + +#define advance_ptr(ptr,cnt,mask) ptr = (ptr + cnt) & mask + +/* + * Create a new ringbuffer to hold at least `sz' bytes of data. The + * actual buffer size is rounded up to the next power of two. + */ +struct ringbuf *ringbuf_create(size_t sz) +{ + struct ringbuf *rb = xmalloc(sizeof(struct ringbuf)); + size_t power_of_two; + + for (power_of_two = 1; 1 << power_of_two < sz; power_of_two++) + /* next power_of_two... */; + + rb->size = 1 << power_of_two; + rb->size_mask = rb->size; + rb->size_mask -= 1; + rb->buf = xmalloc(rb->size); + ringbuf_reset(rb); + + return rb; +} + +/* Free all data associated with the ringbuffer `rb'. */ +void ringbuf_free(struct ringbuf * rb) +{ + free(rb->buf); + free(rb); +} + +/* Reset the read and write pointers to zero. This is not thread safe. */ +void ringbuf_reset(struct ringbuf * rb) +{ + rb->read_ptr = 0; + rb->write_ptr = 0; +} + +/* + * Return the number of bytes available for reading. This is the + * number of bytes in front of the read pointer and behind the write + * pointer. + */ +size_t ringbuf_read_space(const struct ringbuf * rb) +{ + size_t w = rb->write_ptr; + size_t r = rb->read_ptr; + + if (w > r) + return w - r; + else + return (w - r + rb->size) & rb->size_mask; +} + +/* + * Return the number of bytes available for writing. This is the + * number of bytes in front of the write pointer and behind the read + * pointer. + */ +size_t ringbuf_write_space(const struct ringbuf * rb) +{ + size_t w = rb->write_ptr; + size_t r = rb->read_ptr; + + if (w > r) + return ((r - w + rb->size) & rb->size_mask) - 1; + else if (w < r) + return (r - w) - 1; + else + return rb->size - 1; +} + +/* + * The copying data reader. Copy at most `cnt' bytes from `rb' to + * `dest'. Returns the actual number of bytes copied. + */ +size_t ringbuf_read(struct ringbuf * rb, void *dest, size_t cnt) +{ + size_t free_cnt; + size_t cnt2; + size_t to_read; + size_t n1, n2; + + if ((free_cnt = ringbuf_read_space(rb)) == 0) + return 0; + + to_read = cnt > free_cnt ? free_cnt : cnt; + cnt2 = rb->read_ptr + to_read; + + if (cnt2 > rb->size) { + n1 = rb->size - rb->read_ptr; + n2 = cnt2 & rb->size_mask; + } else { + n1 = to_read; + n2 = 0; + } + + memcpy(dest, rb->buf + rb->read_ptr, n1); + ringbuf_read_advance(rb, n1); + + if (n2) { + memcpy(dest + n1, rb->buf + rb->read_ptr, n2); + ringbuf_read_advance(rb, n2); + } + + return to_read; +} + +/* + * The copying data reader w/o read pointer advance. Copy at most + * `cnt' bytes from `rb' to `dest'. Returns the actual number of bytes + * copied. + */ +size_t ringbuf_peek(struct ringbuf * rb, void *dest, size_t cnt) +{ + size_t free_cnt; + size_t cnt2; + size_t to_read; + size_t n1, n2; + size_t tmp_read_ptr = rb->read_ptr; + + if ((free_cnt = ringbuf_read_space(rb)) == 0) + return 0; + + to_read = cnt > free_cnt ? free_cnt : cnt; + cnt2 = tmp_read_ptr + to_read; + + if (cnt2 > rb->size) { + n1 = rb->size - tmp_read_ptr; + n2 = cnt2 & rb->size_mask; + } else { + n1 = to_read; + n2 = 0; + } + + memcpy(dest, rb->buf + tmp_read_ptr, n1); + advance_ptr(tmp_read_ptr, n1, rb->size_mask); + + if (n2) { + memcpy(dest + n1, rb->buf + tmp_read_ptr, n2); + advance_ptr(tmp_read_ptr, n2, rb->size_mask); + } + + return to_read; +} + +/* + * The copying data writer. Copy at most `cnt' bytes to `rb' from + * `src'. Returns the actual number of bytes copied. + */ +size_t ringbuf_write(struct ringbuf * rb, const void *src, size_t cnt) +{ + size_t free_cnt; + size_t cnt2; + size_t to_write; + size_t n1, n2; + + if ((free_cnt = ringbuf_write_space(rb)) == 0) + return 0; + + to_write = cnt > free_cnt ? free_cnt : cnt; + cnt2 = rb->write_ptr + to_write; + + if (cnt2 > rb->size) { + n1 = rb->size - rb->write_ptr; + n2 = cnt2 & rb->size_mask; + } else { + n1 = to_write; + n2 = 0; + } + + memcpy(rb->buf + rb->write_ptr, src, n1); + ringbuf_write_advance(rb, n1); + + if (n2) { + memcpy(rb->buf + rb->write_ptr, src + n1, n2); + ringbuf_write_advance(rb, n2); + } + + return to_write; +} + +/* Advance the read pointer `cnt' places. */ +void ringbuf_read_advance(struct ringbuf * rb, size_t cnt) +{ + advance_ptr(rb->read_ptr, cnt, rb->size_mask); +} + +/* Advance the write pointer `cnt' places. */ +void ringbuf_write_advance(struct ringbuf * rb, size_t cnt) +{ + advance_ptr(rb->write_ptr, cnt, rb->size_mask); +} + +/* + * The non-copying data reader. `vec' is an array of two places. Set + * the values at `vec' to hold the current readable data at `rb'. If + * the readable data is in one segment the second segment has zero + * length. + */ +void ringbuf_get_read_vector(const struct ringbuf * rb, struct iovec * vec) +{ + size_t free_cnt; + size_t cnt2; + size_t w = rb->write_ptr; + size_t r = rb->read_ptr; + + if (w > r) + free_cnt = w - r; + else + free_cnt = (w - r + rb->size) & rb->size_mask; + + cnt2 = r + free_cnt; + + if (cnt2 > rb->size) { + /* + * Two part vector: the rest of the buffer after the current + * write ptr, plus some from the start of the buffer. + */ + vec[0].iov_base = rb->buf + r; + vec[0].iov_len = rb->size - r; + vec[1].iov_base = rb->buf; + vec[1].iov_len = cnt2 & rb->size_mask; + + } else { + /* Single part vector: just the rest of the buffer */ + vec[0].iov_base = rb->buf + r; + vec[0].iov_len = free_cnt; + vec[1].iov_len = 0; + } +} + +/* + * The non-copying data writer. `vec' is an array of two places. Set + * the values at `vec' to hold the current writeable data at `rb'. If + * the writeable data is in one segment the second segment has zero + * length. + */ +void ringbuf_get_write_vector(const struct ringbuf * rb, struct iovec * vec) +{ + size_t free_cnt; + size_t cnt2; + size_t w = rb->write_ptr; + size_t r = rb->read_ptr; + + if (w > r) + free_cnt = ((r - w + rb->size) & rb->size_mask) - 1; + else if (w < r) + free_cnt = (r - w) - 1; + else + free_cnt = rb->size - 1; + + cnt2 = w + free_cnt; + + if (cnt2 > rb->size) { + /* + * Two part vector: the rest of the buffer after the current + * write ptr, plus some from the start of the buffer. + */ + vec[0].iov_base = rb->buf + w; + vec[0].iov_len = rb->size - w; + vec[1].iov_base = rb->buf; + vec[1].iov_len = cnt2 & rb->size_mask; + } else { + vec[0].iov_base = rb->buf + w; + vec[0].iov_len = free_cnt; + vec[1].iov_len = 0; + } +} + diff --git a/src/ringbuf.h b/src/ringbuf.h new file mode 100644 index 000000000..dc3509363 --- /dev/null +++ b/src/ringbuf.h @@ -0,0 +1,205 @@ +/* + * This file is originally from JACK Audio Connection Kit + * + * Copyright (C) 2000 Paul Davis + * Copyright (C) 2003 Rohan Drape + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +#ifndef RINGBUF_H +#define RINGBUF_H + +#include "os_compat.h" + +/** @file ringbuf.h + * + * A set of library functions to make lock-free ringbuffers available + * to JACK clients. The `capture_client.c' (in the example_clients + * directory) is a fully functioning user of this API. + * + * The key attribute of a ringbuffer is that it can be safely accessed + * by two threads simultaneously -- one reading from the buffer and + * the other writing to it -- without using any synchronization or + * mutual exclusion primitives. For this to work correctly, there can + * only be a single reader and a single writer thread. Their + * identities cannot be interchanged. + */ + +struct ringbuf { + void *buf; + size_t write_ptr; + size_t read_ptr; + size_t size; + size_t size_mask; +}; + +/** + * Allocates a ringbuffer data structure of a specified size. The + * caller must arrange for a call to ringbuf_free() to release + * the memory associated with the ringbuffer. + * + * @param sz the ringbuffer size in bytes. + * + * @return a pointer to a new struct ringbuf, if successful; NULL + * otherwise. + */ +struct ringbuf *ringbuf_create(size_t sz); + +/** + * Frees the ringbuffer data structure allocated by an earlier call to + * ringbuf_create(). + * + * @param rb a pointer to the ringbuffer structure. + */ +void ringbuf_free(struct ringbuf * rb); + +/** + * Fill a data structure with a description of the current readable + * data held in the ringbuffer. This description is returned in a two + * element array of struct iovec. Two elements are needed + * because the data to be read may be split across the end of the + * ringbuffer. + * + * The first element will always contain a valid @a len field, which + * may be zero or greater. If the @a len field is non-zero, then data + * can be read in a contiguous fashion using the address given in the + * corresponding @a buf field. + * + * If the second element has a non-zero @a len field, then a second + * contiguous stretch of data can be read from the address given in + * its corresponding @a buf field. + * + * @param rb a pointer to the ringbuffer structure. + * @param vec a pointer to a 2 element array of struct iovec. + * + */ +void ringbuf_get_read_vector(const struct ringbuf * rb, struct iovec * vec); + +/** + * Fill a data structure with a description of the current writable + * space in the ringbuffer. The description is returned in a two + * element array of struct iovec. Two elements are needed + * because the space available for writing may be split across the end + * of the ringbuffer. + * + * The first element will always contain a valid @a len field, which + * may be zero or greater. If the @a len field is non-zero, then data + * can be written in a contiguous fashion using the address given in + * the corresponding @a buf field. + * + * If the second element has a non-zero @a len field, then a second + * contiguous stretch of data can be written to the address given in + * the corresponding @a buf field. + * + * @param rb a pointer to the ringbuffer structure. + * @param vec a pointer to a 2 element array of struct iovec. + */ +void ringbuf_get_write_vector(const struct ringbuf * rb, struct iovec * vec); + +/** + * Read data from the ringbuffer. + * + * @param rb a pointer to the ringbuffer structure. + * @param dest a pointer to a buffer where data read from the + * ringbuffer will go. + * @param cnt the number of bytes to read. + * + * @return the number of bytes read, which may range from 0 to cnt. + */ +size_t ringbuf_read(struct ringbuf * rb, void *dest, size_t cnt); + +/** + * Read data from the ringbuffer. Opposed to ringbuf_read() + * this function does not move the read pointer. Thus it's + * a convenient way to inspect data in the ringbuffer in a + * continous fashion. The price is that the data is copied + * into a user provided buffer. For "raw" non-copy inspection + * of the data in the ringbuffer use ringbuf_get_read_vector(). + * + * @param rb a pointer to the ringbuffer structure. + * @param dest a pointer to a buffer where data read from the + * ringbuffer will go. + * @param cnt the number of bytes to read. + * + * @return the number of bytes read, which may range from 0 to cnt. + */ +size_t ringbuf_peek(struct ringbuf * rb, void *dest, size_t cnt); + +/** + * Advance the read pointer. + * + * After data have been read from the ringbuffer using the pointers + * returned by ringbuf_get_read_vector(), use this function to + * advance the buffer pointers, making that space available for future + * write operations. + * + * @param rb a pointer to the ringbuffer structure. + * @param cnt the number of bytes read. + */ +void ringbuf_read_advance(struct ringbuf * rb, size_t cnt); + +/** + * Return the number of bytes available for reading. + * + * @param rb a pointer to the ringbuffer structure. + * + * @return the number of bytes available to read. + */ +size_t ringbuf_read_space(const struct ringbuf * rb); + +/** + * Reset the read and write pointers, making an empty buffer. + * + * This is not thread safe. + * + * @param rb a pointer to the ringbuffer structure. + */ +void ringbuf_reset(struct ringbuf * rb); + +/** + * Write data into the ringbuffer. + * + * @param rb a pointer to the ringbuffer structure. + * @param src a pointer to the data to be written to the ringbuffer. + * @param cnt the number of bytes to write. + * + * @return the number of bytes write, which may range from 0 to cnt + */ +size_t ringbuf_write(struct ringbuf * rb, const void *src, size_t cnt); + +/** + * Advance the write pointer. + * + * After data have been written the ringbuffer using the pointers + * returned by ringbuf_get_write_vector(), use this function + * to advance the buffer pointer, making the data available for future + * read operations. + * + * @param rb a pointer to the ringbuffer structure. + * @param cnt the number of bytes written. + */ +void ringbuf_write_advance(struct ringbuf * rb, size_t cnt); + +/** + * Return the number of bytes available for writing. + * + * @param rb a pointer to the ringbuffer structure. + * + * @return the amount of free space (in bytes) available for writing. + */ +size_t ringbuf_write_space(const struct ringbuf * rb); + +#endif /* RINGBUF_H */ -- cgit v1.2.3