1#pragma once
2#include <compiler.h>
3#include <log.h>
4#include <stdatomic.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 32
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 struct cpu_mask idle_cpus; /* CPUs RCU sees are idle, i.e. quiescent */
56 uint32_t blocked_count; /* registered readers counted against gp_seq */
57 struct list_head blocked; /* threads preempted in a read section */
58};
59
60/* Per-CPU RCU data, so rcu_defer() doesn't have global contention
61 * and reported_seq lets interrupt exit skip leaf lock */
62struct rcu_cpu {
63 struct spinlock lock;
64 struct list_head list;
65 _Atomic uint64_t reported_seq;
66} __cache_aligned;
67
68struct rcu_state {
69 bool ready;
70
71 _Atomic uint64_t gp_seq; /* last GP started */
72 _Atomic uint64_t gp_completed; /* last GP completed */
73 _Atomic uint64_t gp_requests; /* pending rcu_synchronize() requests */
74
75 struct semaphore sem; /* wake the GP worker */
76
77 struct rcu_node *nodes; /* root first */
78 size_t node_count;
79 struct rcu_node *root;
80 struct rcu_node *leaves;
81 size_t leaf_count;
82
83 struct rcu_cpu *cpus; /* one per CPU */
84 struct thread *worker;
85};
86
87struct rcu_stall_blocker {
88 thread_id_t id;
89 const char *name;
90 int state;
91 uint64_t read_seq;
92};
93
94LOG_SITE_EXTERN(rcu);
95LOG_HANDLE_EXTERN(rcu);
96
97#define rcu_log(lvl, fmt, ...) \
98 log(LOG_SITE(rcu), LOG_HANDLE(rcu), lvl, fmt, ##__VA_ARGS__)
99
100#define rcu_err(fmt, ...) rcu_log(LOG_ERROR, fmt, ##__VA_ARGS__)
101#define rcu_warn(fmt, ...) rcu_log(LOG_WARN, fmt, ##__VA_ARGS__)
102#define rcu_info(fmt, ...) rcu_log(LOG_INFO, fmt, ##__VA_ARGS__)
103#define rcu_debug(fmt, ...) rcu_log(LOG_DEBUG, fmt, ##__VA_ARGS__)
104#define rcu_trace(fmt, ...) rcu_log(LOG_TRACE, fmt, ##__VA_ARGS__)
105