lkml.org 
[lkml]   [2018]   [Jan]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH RFC 01/16] prcu: Add PRCU implementation
Date
From: Heng Zhang <heng.z@huawei.com>

This RCU implementation (PRCU) is based on a fast consensus protocol
published in the following paper:

Fast Consensus Using Bounded Staleness for Scalable Read-mostly Synchronization.
Haibo Chen, Heng Zhang, Ran Liu, Binyu Zang, and Haibing Guan.
IEEE Transactions on Parallel and Distributed Systems (TPDS), 2016.
https://dl.acm.org/citation.cfm?id=3024114.3024143

Signed-off-by: Heng Zhang <heng.z@huawei.com>
Signed-off-by: Lihao Liang <lianglihao@huawei.com>
---
include/linux/prcu.h | 37 +++++++++++++++
kernel/rcu/Makefile | 2 +-
kernel/rcu/prcu.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++
kernel/sched/core.c | 2 +
4 files changed, 165 insertions(+), 1 deletion(-)
create mode 100644 include/linux/prcu.h
create mode 100644 kernel/rcu/prcu.c

diff --git a/include/linux/prcu.h b/include/linux/prcu.h
new file mode 100644
index 00000000..653b4633
--- /dev/null
+++ b/include/linux/prcu.h
@@ -0,0 +1,37 @@
+#ifndef __LINUX_PRCU_H
+#define __LINUX_PRCU_H
+
+#include <linux/atomic.h>
+#include <linux/mutex.h>
+#include <linux/wait.h>
+
+#define CONFIG_PRCU
+
+struct prcu_local_struct {
+ unsigned int locked;
+ unsigned int online;
+ unsigned long long version;
+};
+
+struct prcu_struct {
+ atomic64_t global_version;
+ atomic_t active_ctr;
+ struct mutex mtx;
+ wait_queue_head_t wait_q;
+};
+
+#ifdef CONFIG_PRCU
+void prcu_read_lock(void);
+void prcu_read_unlock(void);
+void synchronize_prcu(void);
+void prcu_note_context_switch(void);
+
+#else /* #ifdef CONFIG_PRCU */
+
+#define prcu_read_lock() do {} while (0)
+#define prcu_read_unlock() do {} while (0)
+#define synchronize_prcu() do {} while (0)
+#define prcu_note_context_switch() do {} while (0)
+
+#endif /* #ifdef CONFIG_PRCU */
+#endif /* __LINUX_PRCU_H */
diff --git a/kernel/rcu/Makefile b/kernel/rcu/Makefile
index 23803c7d..8791419c 100644
--- a/kernel/rcu/Makefile
+++ b/kernel/rcu/Makefile
@@ -2,7 +2,7 @@
# and is generally not a function of system call inputs.
KCOV_INSTRUMENT := n

-obj-y += update.o sync.o
+obj-y += update.o sync.o prcu.o
obj-$(CONFIG_CLASSIC_SRCU) += srcu.o
obj-$(CONFIG_TREE_SRCU) += srcutree.o
obj-$(CONFIG_TINY_SRCU) += srcutiny.o
diff --git a/kernel/rcu/prcu.c b/kernel/rcu/prcu.c
new file mode 100644
index 00000000..a00b9420
--- /dev/null
+++ b/kernel/rcu/prcu.c
@@ -0,0 +1,125 @@
+#include <linux/smp.h>
+#include <linux/prcu.h>
+#include <linux/percpu.h>
+#include <linux/compiler.h>
+#include <linux/sched.h>
+
+#include <asm/barrier.h>
+
+DEFINE_PER_CPU_SHARED_ALIGNED(struct prcu_local_struct, prcu_local);
+
+struct prcu_struct global_prcu = {
+ .global_version = ATOMIC64_INIT(0),
+ .active_ctr = ATOMIC_INIT(0),
+ .mtx = __MUTEX_INITIALIZER(global_prcu.mtx),
+ .wait_q = __WAIT_QUEUE_HEAD_INITIALIZER(global_prcu.wait_q)
+};
+struct prcu_struct *prcu = &global_prcu;
+
+static inline void prcu_report(struct prcu_local_struct *local)
+{
+ unsigned long long global_version;
+ unsigned long long local_version;
+
+ global_version = atomic64_read(&prcu->global_version);
+ local_version = local->version;
+ if (global_version > local_version)
+ cmpxchg(&local->version, local_version, global_version);
+}
+
+void prcu_read_lock(void)
+{
+ struct prcu_local_struct *local;
+
+ local = get_cpu_ptr(&prcu_local);
+ if (!local->online) {
+ WRITE_ONCE(local->online, 1);
+ smp_mb();
+ }
+
+ local->locked++;
+ put_cpu_ptr(&prcu_local);
+}
+EXPORT_SYMBOL(prcu_read_lock);
+
+void prcu_read_unlock(void)
+{
+ int locked;
+ struct prcu_local_struct *local;
+
+ barrier();
+ local = get_cpu_ptr(&prcu_local);
+ locked = local->locked;
+ if (locked) {
+ local->locked--;
+ if (locked == 1)
+ prcu_report(local);
+ put_cpu_ptr(&prcu_local);
+ } else {
+ put_cpu_ptr(&prcu_local);
+ if (!atomic_dec_return(&prcu->active_ctr))
+ wake_up(&prcu->wait_q);
+ }
+}
+EXPORT_SYMBOL(prcu_read_unlock);
+
+static void prcu_handler(void *info)
+{
+ struct prcu_local_struct *local;
+
+ local = this_cpu_ptr(&prcu_local);
+ if (!local->locked)
+ WRITE_ONCE(local->version, atomic64_read(&prcu->global_version));
+}
+
+void synchronize_prcu(void)
+{
+ int cpu;
+ cpumask_t cpus;
+ unsigned long long version;
+ struct prcu_local_struct *local;
+
+ version = atomic64_add_return(1, &prcu->global_version);
+ mutex_lock(&prcu->mtx);
+
+ local = get_cpu_ptr(&prcu_local);
+ local->version = version;
+ put_cpu_ptr(&prcu_local);
+
+ cpumask_clear(&cpus);
+ for_each_possible_cpu(cpu) {
+ local = per_cpu_ptr(&prcu_local, cpu);
+ if (!READ_ONCE(local->online))
+ continue;
+ if (READ_ONCE(local->version) < version) {
+ smp_call_function_single(cpu, prcu_handler, NULL, 0);
+ cpumask_set_cpu(cpu, &cpus);
+ }
+ }
+
+ for_each_cpu(cpu, &cpus) {
+ local = per_cpu_ptr(&prcu_local, cpu);
+ while (READ_ONCE(local->version) < version)
+ cpu_relax();
+ }
+
+ if (atomic_read(&prcu->active_ctr))
+ wait_event(prcu->wait_q, !atomic_read(&prcu->active_ctr));
+
+ mutex_unlock(&prcu->mtx);
+}
+EXPORT_SYMBOL(synchronize_prcu);
+
+void prcu_note_context_switch(void)
+{
+ struct prcu_local_struct *local;
+
+ local = get_cpu_ptr(&prcu_local);
+ if (local->locked) {
+ atomic_add(local->locked, &prcu->active_ctr);
+ local->locked = 0;
+ }
+ local->online = 0;
+ prcu_report(local);
+ put_cpu_ptr(&prcu_local);
+}
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 326d4f88..a308581b 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -15,6 +15,7 @@
#include <linux/init_task.h>
#include <linux/context_tracking.h>
#include <linux/rcupdate_wait.h>
+#include <linux/prcu.h>

#include <linux/blkdev.h>
#include <linux/kprobes.h>
@@ -3383,6 +3384,7 @@ static void __sched notrace __schedule(bool preempt)

local_irq_disable();
rcu_note_context_switch(preempt);
+ prcu_note_context_switch();

/*
* Make sure that signal_pending_state()->signal_pending() below
--
2.14.1.729.g59c0ea183
\
 
 \ /
  Last update: 2018-01-23 09:12    [W:0.259 / U:0.216 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site