MINOR: ring: add a new mechanism for retrieving/storing ring data in buffers
Our circular buffers are well suited for being used as ring buffers for
not-so-structured data. The machanism here consists in making room in a
buffer before inserting a new record which is prefixed by its size, and
looking up next record based on the previous one's offset and size. We
can have up to 255 consumers watching for data (dump in progress, tail)
which guarantee that entrees are not recycled while they're being dumped.
The complete representation is described in the header file. For now only
ring_new(), ring_resize() and ring_free() are created.
diff --git a/Makefile b/Makefile
index ddddb44..5536d54 100644
--- a/Makefile
+++ b/Makefile
@@ -774,7 +774,7 @@
src/http_htx.o src/buffer.o src/hpack-tbl.o src/shctx.o src/sha1.o \
src/http.o src/hpack-dec.o src/action.o src/proto_udp.o src/http_acl.o \
src/xxhash.o src/hpack-enc.o src/h2.o src/freq_ctr.o src/lru.o \
- src/protocol.o src/arg.o src/hpack-huff.o src/base64.o \
+ src/protocol.o src/arg.o src/hpack-huff.o src/base64.o src/ring.o \
src/hash.o src/mailers.o src/activity.o src/version.o src/trace.o \
src/mworker.o src/mworker-prog.o src/debug.o src/wdt.o src/dict.o \
src/xprt_handshake.o
diff --git a/include/proto/ring.h b/include/proto/ring.h
new file mode 100644
index 0000000..6c08353
--- /dev/null
+++ b/include/proto/ring.h
@@ -0,0 +1,38 @@
+/*
+ * include/proto/ring.h
+ * This file provides definitions for ring buffers used for disposable data.
+ *
+ * Copyright (C) 2000-2019 Willy Tarreau - w@1wt.eu
+ *
+ * This library 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, version 2.1
+ * exclusively.
+ *
+ * This library 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 library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _PROTO_RING_H
+#define _PROTO_RING_H
+
+#include <types/ring.h>
+
+struct ring *ring_new(size_t size);
+struct ring *ring_resize(struct ring *ring, size_t size);
+void ring_free(struct ring *ring);
+
+#endif /* _PROTO_RING_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */
diff --git a/include/types/ring.h b/include/types/ring.h
new file mode 100644
index 0000000..3d69b22
--- /dev/null
+++ b/include/types/ring.h
@@ -0,0 +1,110 @@
+/*
+ * include/types/ring.h
+ * This file provides definitions for ring buffers used for disposable data.
+ *
+ * Copyright (C) 2000-2019 Willy Tarreau - w@1wt.eu
+ *
+ * This library 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, version 2.1
+ * exclusively.
+ *
+ * This library 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 library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _TYPES_RING_H
+#define _TYPES_RING_H
+
+#include <common/buffer.h>
+#include <common/compat.h>
+#include <common/config.h>
+#include <common/ist.h>
+
+/* The code below handles circular buffers with single-producer and multiple
+ * readers (up to 255). The buffer storage area must remain always allocated.
+ * It's made of series of payload blocks followed by a readers count (RC).
+ * There is always a readers count at the beginning of the buffer as well. Each
+ * payload block is composed of a varint-encoded size (VI) followed by the
+ * actual payload (PL).
+ *
+ * The readers count is encoded on a single byte. It indicates how many readers
+ * are still waiting at this position. The writer writes after the buffer's
+ * tail, which initially starts just past the first readers count. Then it
+ * knows by reading this count that it must wake up the readers to indicate
+ * data availability. When a reader reads the payload block, it increments the
+ * next readers count and decrements the current one. The area between the
+ * initial readers count and the next one is protected from overwriting for as
+ * long as the initial count is non-null. As such these readers count are
+ * effective barriers against data recycling.
+ *
+ * Only the writer is allowed to update the buffer's tail/head. This ensures
+ * that events can remain as long as possible so that late readers can get the
+ * maximum history available. It also helps dealing with multi-thread accesses
+ * using a simple RW lock during the buffer head's manipulation. The writer
+ * will have to delete some old records starting at the head until the new
+ * message can fit or a non-null readers count is encountered. If a message
+ * cannot fit due to insufficient room, the message is lost and the drop
+ * counted must be incremented.
+ *
+ * Like any buffer, this buffer naturally wraps at the end and continues at the
+ * beginning. The creation process consists in immediately adding a null
+ * readers count byte into the buffer. The write process consists in always
+ * writing a payload block followed by a new readers count. The delete process
+ * consists in removing a null readers count and payload block. As such, there
+ * is always at least one readers count byte in the buffer available at the
+ * head for new readers to attach to, and one before the tail, both of which
+ * may be the same when the buffer doesn't contain any event. It is thus safe
+ * for any reader to simply keep the absolute offset of the last visited
+ * position and to restart from there. The write will update the buffer's
+ * absolute offset when deleting entries. All this also has the benefit of
+ * allowing a buffer to be hot-resized without losing its contents.
+ *
+ * Thus we have this :
+ * - init of empty buffer:
+ * head-, ,-tail
+ * [ RC | xxxxxxxxxxxxxxxxxxxxxxxxxx ]
+ *
+ * - reader attached:
+ * head-, ,-tail
+ * [ RC | xxxxxxxxxxxxxxxxxxxxxxxxxx ]
+ * ^- +1
+ *
+ * - append of one event:
+ * appended
+ * head-, <----------> ,-tail
+ * [ RC | VI | PL | RC | xxxxxxxxxxx ]
+ *
+ * - reader advancing:
+ * head-, ,-tail
+ * [ RC | VI | PL | RC | xxxxxxxxxxx ]
+ * ^- -1 ^- +1
+ *
+ * - writer removing older message:
+ * head-, ,-tail
+ * [ xxxxxxxxxxxx | RC | xxxxxxxxxxx ]
+ * <---------->
+ * removed
+ */
+
+struct ring {
+ struct buffer buf; // storage area
+ size_t ofs; // absolute offset in history of the buffer's head
+ __decl_hathreads(HA_RWLOCK_T lock);
+ int readers_count;
+};
+
+#endif /* _TYPES_RING_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */
diff --git a/src/ring.c b/src/ring.c
new file mode 100644
index 0000000..a1f77da
--- /dev/null
+++ b/src/ring.c
@@ -0,0 +1,108 @@
+/*
+ * Ring buffer management
+ *
+ * Copyright (C) 2000-2019 Willy Tarreau - w@1wt.eu
+ *
+ * This library 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, version 2.1
+ * exclusively.
+ *
+ * This library 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 library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stdlib.h>
+#include <common/buf.h>
+#include <common/compat.h>
+#include <common/config.h>
+#include <common/hathreads.h>
+#include <proto/ring.h>
+
+/* Creates and returns a ring buffer of size <size> bytes. Returns NULL on
+ * allocation failure.
+ */
+struct ring *ring_new(size_t size)
+{
+ struct ring *ring = NULL;
+ void *area = NULL;
+
+ if (size < 2)
+ goto fail;
+
+ ring = malloc(sizeof(*ring));
+ if (!ring)
+ goto fail;
+
+ area = malloc(size);
+ if (!area)
+ goto fail;
+
+ HA_RWLOCK_INIT(&ring->lock);
+ ring->readers_count = 0;
+ ring->ofs = 0;
+ ring->buf = b_make(area, size, 0, 0);
+ /* write the initial RC byte */
+ b_putchr(&ring->buf, 0);
+ return ring;
+ fail:
+ free(area);
+ free(ring);
+ return NULL;
+}
+
+/* Resizes existing ring <ring> to <size> which must be larger, without losing
+ * its contents. The new size must be at least as large as the previous one or
+ * no change will be performed. The pointer to the ring is returned on success,
+ * or NULL on allocation failure. This will lock the ring for writes.
+ */
+struct ring *ring_resize(struct ring *ring, size_t size)
+{
+ void *area;
+
+ if (b_size(&ring->buf) >= size)
+ return ring;
+
+ area = malloc(size);
+ if (!area)
+ return NULL;
+
+ HA_RWLOCK_WRLOCK(LOGSRV_LOCK, &ring->lock);
+
+ /* recheck the buffer's size, it may have changed during the malloc */
+ if (b_size(&ring->buf) < size) {
+ /* copy old contents */
+ b_getblk(&ring->buf, area, ring->buf.data, 0);
+ area = HA_ATOMIC_XCHG(&ring->buf.area, area);
+ ring->buf.size = size;
+ ring->buf.head = 0;
+ }
+
+ HA_RWLOCK_WRUNLOCK(LOGSRV_LOCK, &ring->lock);
+
+ free(area);
+ return ring;
+}
+
+/* destroys and frees ring <ring> */
+void ring_free(struct ring *ring)
+{
+ if (!ring)
+ return;
+ free(ring->buf.area);
+ free(ring);
+}
+
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */