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
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <fe1183a4cf91d8888411725eb84695e8d7daf234.1483138400.git.tst@schoebel-theuer.de>
Date:   Fri, 30 Dec 2016 23:57:34 +0100
From:   Thomas Schoebel-Theuer <tst@...oebel-theuer.de>
To:     linux-kernel@...r.kernel.org, tst@...oebel-theuer.de
Subject: [RFC 08/32] mars: add new module lib_queue

Signed-off-by: Thomas Schoebel-Theuer <tst@...oebel-theuer.de>
---
 include/linux/brick/lib_queue.h | 165 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)
 create mode 100644 include/linux/brick/lib_queue.h

diff --git a/include/linux/brick/lib_queue.h b/include/linux/brick/lib_queue.h
new file mode 100644
index 000000000000..72cd0a2710c2
--- /dev/null
+++ b/include/linux/brick/lib_queue.h
@@ -0,0 +1,165 @@
+/*
+ * MARS Long Distance Replication Software
+ *
+ * Copyright (C) 2010-2014 Thomas Schoebel-Theuer
+ * Copyright (C) 2011-2014 1&1 Internet AG
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 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 General Public License for more details.
+ */
+
+#ifndef LIB_QUEUE_H
+#define LIB_QUEUE_H
+
+#define QUEUE_ANCHOR(PREFIX, KEYTYPE, HEAPTYPE)				\
+	/* parameters */						\
+	/* readonly from outside */					\
+	atomic_t q_queued;						\
+	atomic_t q_flying;						\
+	atomic_t q_total;						\
+	/* tunables */							\
+	int q_batchlen;							\
+	int q_io_prio;							\
+	bool q_ordering;						\
+	/* private */							\
+	wait_queue_head_t *q_event;					\
+	spinlock_t q_lock;						\
+	struct list_head q_anchor;					\
+	struct pairing_heap_##HEAPTYPE *heap_high;			\
+	struct pairing_heap_##HEAPTYPE *heap_low;			\
+	long long q_last_insert; /* jiffies */				\
+	KEYTYPE heap_margin;						\
+	KEYTYPE last_pos
+
+#define QUEUE_FUNCTIONS(PREFIX, ELEM_TYPE, HEAD, KEYFN, KEYCMP, HEAPTYPE)\
+									\
+static inline								\
+void q_##PREFIX##_trigger(struct PREFIX##_queue *q)			\
+{									\
+	if (q->q_event) {						\
+		wake_up_interruptible(q->q_event);			\
+	}								\
+}									\
+									\
+static inline								\
+void q_##PREFIX##_init(struct PREFIX##_queue *q)			\
+{									\
+	INIT_LIST_HEAD(&q->q_anchor);					\
+	q->heap_low = NULL;						\
+	q->heap_high = NULL;						\
+	spin_lock_init(&q->q_lock);					\
+	atomic_set(&q->q_queued, 0);					\
+	atomic_set(&q->q_flying, 0);					\
+}									\
+									\
+static inline								\
+void q_##PREFIX##_insert(struct PREFIX##_queue *q, ELEM_TYPE * elem)	\
+{									\
+	unsigned long flags;						\
+									\
+	spin_lock_irqsave(&q->q_lock, flags);				\
+									\
+	if (q->q_ordering) {						\
+		struct pairing_heap_##HEAPTYPE **use = &q->heap_high;	\
+		if (KEYCMP(KEYFN(elem), &q->heap_margin) <= 0) {	\
+			use = &q->heap_low;				\
+		}							\
+		ph_insert_##HEAPTYPE(use, &elem->ph);			\
+	} else {							\
+		list_add_tail(&elem->HEAD, &q->q_anchor);		\
+	}								\
+	atomic_inc(&q->q_queued);					\
+	atomic_inc(&q->q_total);					\
+	q->q_last_insert = jiffies;					\
+									\
+	spin_unlock_irqrestore(&q->q_lock, flags);			\
+									\
+	q_##PREFIX##_trigger(q);					\
+}									\
+									\
+static inline								\
+void q_##PREFIX##_pushback(struct PREFIX##_queue *q, ELEM_TYPE * elem)	\
+{									\
+	unsigned long flags;						\
+									\
+	if (q->q_ordering) {						\
+		atomic_dec(&q->q_total);				\
+		q_##PREFIX##_insert(q, elem);				\
+		return;							\
+	}								\
+									\
+	spin_lock_irqsave(&q->q_lock, flags);				\
+									\
+	list_add(&elem->HEAD, &q->q_anchor);				\
+	atomic_inc(&q->q_queued);					\
+									\
+	spin_unlock_irqrestore(&q->q_lock, flags);			\
+}									\
+									\
+static inline								\
+ELEM_TYPE *q_##PREFIX##_fetch(struct PREFIX##_queue *q)			\
+{									\
+	ELEM_TYPE *elem = NULL;						\
+	unsigned long flags;						\
+									\
+	spin_lock_irqsave(&q->q_lock, flags);				\
+									\
+	if (q->q_ordering) {						\
+		if (!q->heap_high) {					\
+			q->heap_high = q->heap_low;			\
+			q->heap_low = NULL;				\
+			q->heap_margin = 0;				\
+			q->last_pos = 0;				\
+		}							\
+		if (q->heap_high) {					\
+			elem = container_of(q->heap_high, ELEM_TYPE, ph);\
+									\
+			if (unlikely(KEYCMP(KEYFN(elem), &q->last_pos) < 0)) {\
+				printk(KERN_ERR				\
+				"backskip pos %lld -> %lld\n", (long long)q->last_pos, (long long)KEYFN(elem));\
+			}						\
+			memcpy(&q->last_pos, KEYFN(elem), sizeof(q->last_pos));\
+									\
+			if (KEYCMP(KEYFN(elem), &q->heap_margin) > 0) { \
+				memcpy(&q->heap_margin, KEYFN(elem), sizeof(q->heap_margin));\
+			}						\
+			ph_delete_min_##HEAPTYPE(&q->heap_high);	\
+			atomic_dec(&q->q_queued);			\
+		}							\
+	} else if (!list_empty(&q->q_anchor)) {				\
+		struct list_head *next = q->q_anchor.next;		\
+		list_del_init(next);					\
+		atomic_dec(&q->q_queued);				\
+		elem = container_of(next, ELEM_TYPE, HEAD);		\
+	}								\
+									\
+	spin_unlock_irqrestore(&q->q_lock, flags);			\
+									\
+	q_##PREFIX##_trigger(q);					\
+									\
+	return elem;							\
+}									\
+									\
+static inline								\
+void q_##PREFIX##_inc_flying(struct PREFIX##_queue *q)			\
+{									\
+	atomic_inc(&q->q_flying);					\
+	q_##PREFIX##_trigger(q);					\
+}									\
+									\
+static inline								\
+void q_##PREFIX##_dec_flying(struct PREFIX##_queue *q)			\
+{									\
+	atomic_dec(&q->q_flying);					\
+	q_##PREFIX##_trigger(q);					\
+}									\
+									\
+
+#endif
-- 
2.11.0

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ