Reworks MCS-PDR locks to avoid preempt storms
[akaros.git] / user / parlib / include / mcs.h
1 #ifndef _MCS_H
2 #define _MCS_H
3
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7
8 #include <vcore.h>
9 #include <arch/arch.h>
10
11 #define MCS_LOCK_INIT {0}
12 #define MCS_QNODE_INIT {0, 0}
13
14 typedef struct mcs_lock_qnode
15 {
16         struct mcs_lock_qnode *next;
17         int locked;
18 }__attribute__((aligned(ARCH_CL_SIZE))) mcs_lock_qnode_t;
19
20 typedef struct mcs_lock
21 {
22         mcs_lock_qnode_t* lock;
23 } mcs_lock_t;
24
25 typedef struct
26 {
27         volatile int myflags[2][LOG2_MAX_VCORES];
28         volatile int* partnerflags[2][LOG2_MAX_VCORES];
29         int parity;
30         int sense;
31         char pad[ARCH_CL_SIZE];
32 } mcs_dissem_flags_t;
33
34 typedef struct
35 {
36         size_t nprocs;
37         mcs_dissem_flags_t* allnodes;
38         size_t logp;
39 } mcs_barrier_t;
40
41 int mcs_barrier_init(mcs_barrier_t* b, size_t nprocs);
42 void mcs_barrier_wait(mcs_barrier_t* b, size_t vcoreid);
43
44 void mcs_lock_init(struct mcs_lock *lock);
45 /* Caller needs to alloc (and zero) their own qnode to spin on.  The memory
46  * should be on a cacheline that is 'per-thread'.  This could be on the stack,
47  * in a thread control block, etc. */
48 void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
49 void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
50 void mcs_lock_unlock_cas(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
51 /* If you lock the lock from vcore context, you must use these. */
52 void mcs_lock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
53 void mcs_unlock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode);
54
55 /* Preemption detection and recovering MCS locks.
56  *
57  * The basic idea is that when spinning, vcores make sure someone else is
58  * making progress that will lead to them not spinning.  Usually, it'll be to
59  * make sure the lock holder (if known) is running.  If we don't know the lock
60  * holder, we ensure the end of whatever chain we can see is running, which
61  * will make sure its predecessor runs, which will eventually unjam the system.
62  * */
63
64 /* Old style.  Has trouble getting out of 'preempt/change-to storms' under
65  * heavy contention and with preemption. */
66 struct mcs_pdro_qnode
67 {
68         struct mcs_pdro_qnode *next;
69         int locked;
70         uint32_t vcoreid;
71 }__attribute__((aligned(ARCH_CL_SIZE)));
72
73 struct mcs_pdro_lock
74 {
75         struct mcs_pdro_qnode *lock;
76 };
77
78 #define MCSPDRO_LOCK_INIT {0}
79 #define MCSPDRO_QNODE_INIT {0, 0, 0}
80
81 void mcs_pdro_init(struct mcs_pdro_lock *lock);
82 void mcs_pdro_fini(struct mcs_pdro_lock *lock);
83 void mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
84 void mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
85
86 /* Only call these if you have notifs disabled and know your vcore's qnode.
87  * Mostly used for debugging, benchmarks, or critical code. */
88 void __mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
89 void __mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode);
90 void __mcs_pdro_unlock_no_cas(struct mcs_pdro_lock *lock,
91                              struct mcs_pdro_qnode *qnode);
92
93 /* New style: under heavy contention with preemption, they won't enter the
94  * 'preempt/change_to storm' that can happen to PDRs, at the cost of some
95  * performance.  This is the default. */
96 struct mcs_pdr_qnode
97 {
98         struct mcs_pdr_qnode *next;
99         int locked;
100 }__attribute__((aligned(ARCH_CL_SIZE)));
101
102 struct mcs_pdr_lock
103 {
104         struct mcs_pdr_qnode *lock __attribute__((aligned(ARCH_CL_SIZE)));
105         uint32_t lockholder_vcoreid __attribute__((aligned(ARCH_CL_SIZE)));
106         struct mcs_pdr_qnode *qnodes __attribute__((aligned(ARCH_CL_SIZE)));
107 };
108
109 #define MCSPDR_NO_LOCKHOLDER ((uint32_t)-1)
110
111 void mcs_pdr_init(struct mcs_pdr_lock *lock);
112 void mcs_pdr_fini(struct mcs_pdr_lock *lock);
113 void mcs_pdr_lock(struct mcs_pdr_lock *lock);
114 void mcs_pdr_unlock(struct mcs_pdr_lock *lock);
115
116 #ifdef __cplusplus
117 }
118 #endif
119
120 #endif