| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1275552062-8153-2-git-send-email-rydberg@euromail.se>
Date: Thu, 3 Jun 2010 10:00:59 +0200
From: "Henrik Rydberg" <rydberg@...omail.se>
To: Dmitry Torokhov <dmitry.torokhov@...il.com>
Cc: linux-input@...r.kernel.org, linux-kernel@...r.kernel.org,
Jiri Kosina <jkosina@...e.cz>,
Mika Kuoppala <mika.kuoppala@...ia.com>,
Benjamin Tissoires <tissoire@...a.fr>,
Rafi Rubin <rafi@...s.upenn.edu>,
Henrik Rydberg <rydberg@...omail.se>
Subject: [PATCH 1/4] input: Introduce buflock, a one-to-many circular buffer mechanism
In spite of the many lock patterns and fifo helpers in the kernel, the
case of a single writer feeding many readers via a circular buffer
seems to be uncovered. This patch adds the buflock, a minimalistic
interface implementing SMP-safe locking for such a buffer. Under
normal operation, given adequate buffer size, the operation is
lock-less. The template is given the name buflock to emphasize that
the locking depends on the buffer read/write clashes.
Signed-off-by: Henrik Rydberg <rydberg@...omail.se>
---
drivers/input/buflock.h | 133 +++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 133 insertions(+), 0 deletions(-)
create mode 100644 drivers/input/buflock.h
diff --git a/drivers/input/buflock.h b/drivers/input/buflock.h
new file mode 100644
index 0000000..3a4322c
--- /dev/null
+++ b/drivers/input/buflock.h
@@ -0,0 +1,133 @@
+#ifndef _BUFLOCK_H
+#define _BUFLOCK_H
+/*
+ * Circular buffer lock for single writer, multiple readers
+ *
+ * Copyright (c) 2010 Henrik Rydberg
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ */
+
+/*
+ * Mechanism for circular buffer locking:
+ *
+ * Single writer does not block.
+ *
+ * Readers block on buffer wrap-around only.
+ *
+ * These locks are particularly suitable when a single writer must not
+ * be starved, and when there are several threads reading the same buffer.
+ *
+ * The structure is similar to seqlocks, with the main difference being
+ * that readers retry only when the writer simultaneously overwrites the
+ * data currently being read.
+ *
+ * In practise, given enough buffer size, the mechanism is lock-less.
+ *
+ * Like seqlocks, buflocks are not very cache friendly, and require the
+ * buffer to be valid in all threads.
+ *
+ * Multiple writers or re-entrant readers require additional locking.
+ *
+ */
+
+#include <linux/spinlock.h>
+
+struct buflock_writer {
+ unsigned int head;
+ unsigned int next_head;
+};
+
+struct buflock_reader {
+ unsigned int head;
+ unsigned int tail;
+};
+
+/*
+ * Write to buffer without locking
+ *
+ * bw - the buflock_writer keeping track of the write position
+ * buf - the buffer to write to (array of item type)
+ * size - the size of the circular buffer (must be a power of two)
+ * item - the item to write
+ *
+ * There is no locking involved during write, so this method is
+ * suitable to use in interrupt context.
+ */
+#define buflock_write(bw, buf, size, item) \
+ do { \
+ bw.next_head = (bw.head + 1) & ((size) - 1); \
+ smp_wmb(); \
+ buf[bw.head] = item; \
+ smp_wmb(); \
+ bw.head = bw.next_head; \
+ smp_wmb(); \
+ } while (0)
+
+
+/*
+ * Syncronize reader with current writer
+ *
+ * br - the buflock_reader keeping track of the read position
+ * bw - the buflock_writer keeping track of the write position
+ *
+ * Synchronize the reader head with the writer head, effectively
+ * telling the reader thread that there is new data to read.
+ *
+ * The reader head will always follow the writer head. As a
+ * consequence, the number of items stored in the read buffer might
+ * decrease during sync, as an effect of wrap-around. To avoid
+ * non-deterministic behavior during polls, the read buffer is
+ * guaranteed to be non-empty after synchronization.
+ *
+ */
+#define buflock_sync_reader(br, bw) \
+ do { \
+ if (br.tail != bw.head) \
+ br.head = bw.head; \
+ } while (0)
+
+/*
+ * True if reader is empty
+ *
+ * br - the buflock_reader keeping track of the read position
+ *
+ */
+#define buflock_reader_empty(br) (br.head == br.tail)
+
+/*
+ * Read from buffer, retry during wrap-around
+ *
+ * br - the buflock_reader keeping track of the read position
+ * bw - the buflock_writer keeping track of the write position
+ * buf - the buffer to read from (array of item type)
+ * size - the size of the circular buffer (must be a power of two)
+ * item - the item to read to
+ *
+ * Read the oldest item available in the buffer.
+ *
+ * During normal operation, with adequate buffer size, this method will not
+ * block, regardless of the number of concurrent readers. The method will
+ * only block momentarily during a write to the same position being read
+ * from, which happens when the buffer gets full. In such cases, the value
+ * eventually read will be the new value written to the buffer.
+ *
+ */
+#define buflock_read(br, bw, buf, size, item) \
+ do { \
+ unsigned int _h, _nh; \
+ do { \
+ _h = bw.head; \
+ smp_rmb(); \
+ item = buf[br.tail]; \
+ smp_rmb(); \
+ _nh = bw.next_head; \
+ smp_rmb(); \
+ } while (unlikely(br.tail - _h < _nh - _h)); \
+ br.tail = (br.tail + 1) & ((size) - 1); \
+ } while (0)
+
+
+#endif /* _BUFLOCK_H */
--
1.6.3.3
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists