1#pragma once
2#include <atomic.h>
3#include <compiler/core.h>
4#include <log.h>
5#include <stdbool.h>
6#include <stddef.h>
7#include <stdint.h>
8#include <structures/cpu_mask.h>
9#include <structures/list.h>
10#include <sync/rcu.h>
11#include <sync/semaphore.h>
12#include <sync/spinlock.h>
13#include <types/types.h>
14
15/* TODO: Here, we have 32 bit masks per node, with 4 levels, since right now
16 * CPU_MASK has a maximum of 128 CPUs, however, in the future, we might
17 * want to come up with something smarter + maybe introduce NR_CPUS */
18#define RCU_FANOUT 32UL
19#define RCU_MAX_LEVELS 4
20
21/* Frequency for workers to poke CPUs that are not quiesced */
22#define RCU_KICK_INTERVAL_MS 5
23
24/* TODO: Tune this */
25#define RCU_STALL_MS 1000
26
27/* TODO: Tune this ? */
28#define RCU_STALL_MAX_REPORTED 8
29
30/* Tree node, everything except parent, child_index, and full_ is
31 * protected by lock, always irq disabled on acquire, since IRQ
32 * exit takes that lock,
33 *
34 * ordering leaf -> parent -> ... -> root, and node locks
35 * get dropped before parent locks are taken
36 *
37 * TODO: We need to make this topology aware in the future, but for
38 * this naive tree impl. we can cheese it with what we're doing here */
39struct rcu_node {
40 struct spinlock lock;
41
42 struct rcu_node *parent;
43 size_t child_index; /* our bit in parent->qs_children */
44
45 uint64_t gp_seq; /* GP this node is tracking */
46 uint64_t completed_seq; /* last GP we propagated upward */
47
48 bitmap_word_t full_children; /* every child we own */
49 bitmap_word_t qs_children; /* children that still owe a QS */
50
51 bool is_leaf;
52 cpu_id_t cpu_base;
53 struct cpu_mask full_cpus; /* every CPU we own */
54 struct cpu_mask qs_cpus; /* CPUs that still owe a QS */
55 uint32_t blocked_count; /* registered readers counted against gp_seq */
56 struct list_head blocked; /* threads preempted in a read section */
57};
58
59struct rcu_cpu {
60 struct spinlock lock;
61 struct list_head list;
62 atomic_uint64_t reported_seq;
63 atomic_bool idle;
64} cc_cache_aligned;
65
66struct rcu_globals {
67 bool ready;
68
69 atomic_uint64_t gp_seq; /* last GP started */
70 atomic_uint64_t gp_completed; /* last GP completed */
71 atomic_uint64_t gp_requests; /* pending rcu_synchronize() requests */
72
73 struct semaphore sem; /* wake the GP worker */
74
75 struct rcu_node *nodes cc_counted_by(node_count); /* root first */
76 size_t node_count;
77 struct rcu_node *root;
78 struct rcu_node *leaves;
79 size_t leaf_count;
80
81 struct rcu_cpu *cpus; /* one per CPU */
82 struct thread *worker;
83};
84
85struct rcu_stall_blocker {
86 thread_id_t id;
87 const char *name;
88 int state;
89 uint64_t read_seq;
90};
91
92LOG_SITE_EXTERN(rcu);
93LOG_HANDLE_EXTERN(rcu);
94
95#define rcu_log(lvl, fmt, ...) \
96 log(LOG_SITE(rcu), LOG_HANDLE(rcu), lvl, fmt, ##__VA_ARGS__)
97
98#define rcu_err(fmt, ...) rcu_log(LOG_ERROR, fmt, ##__VA_ARGS__)
99#define rcu_warn(fmt, ...) rcu_log(LOG_WARN, fmt, ##__VA_ARGS__)
100#define rcu_info(fmt, ...) rcu_log(LOG_INFO, fmt, ##__VA_ARGS__)
101#define rcu_debug(fmt, ...) rcu_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
102#define rcu_trace(fmt, ...) rcu_log(LOG_TRACE, fmt, ##__VA_ARGS__)
103