1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #define NONE 0
#define READER 1
#define WRITER 2
typedef struct _qnode{
int type;
union {
volatile int state; //(1)
struct {
volatile short waiting;
volatile short successor_type;
};
};
_qnode *volatile next;
} __cacheline_aligned_in_smp qnode;
typedef struct {
qnode *volatile tail;
qnode *volatile next_writer;
atomic_t nr_readers;
} rwlock_t
void init_lock(rwlock_t *lock)
{
lock->tail = NULL;
lock->next_writer = NULL;
lock->nr_readers = ATOMIC_INIT(0);
}
void reader_lock(rwlock_t *lock)
{
qnode *me = get_myself(); //(2)
qnode *pred = me;
me->type = READER;
me->next = NULL;
me->state = 1;// successor_type == NONE && waiting == 1
xchg(&lock->tail, pred);
if (pred == NULL) {
atomic_inc(&lock->nr_readers);
me->waiting = 0;
} else {
If ((pred->type == WRITER)
|| (cmpxchg(&pred->state, 1, 0x00010001) == 1)} { //(3)
pred->next = me;
while (me->waiting)
cpu_relax();
} else {
atomic_inc(&lock->nr_readers);
pred->next = me;
me->waiting = 0;
}
}
if (me->successor_type == READER) {
while (me->next == NULL)
cpu_relax();
atomic_inc(&lock->nr_readers);
me->next->waiting = 0;
}
}
void reader_unlock(rwlock_t *lock)
{
qnode *w;
qnode *me = get_myself();
if ((me->next != NULL)
|| (cmpxchg(&lock->tail, me, NULL) != me)) {
while (me->next == NULL)
cpu_relax();
if (me->successor_type == WRITER)
lock->next_writer = me->next;
}
if ((atomic_dec_return(&lock->nr_readers) == 1)
&& ((w = lock->next_writer) != NULL)
&& (atomic_read(lock->nr_readers) == 0)
&& (cmpxchg(&lock->next_writer, w, NULL) == w))
w->waiting = 0;
}
void writer_lock(rwlock_t *lock)
{
qnode *me = get_myself();
qnode *pred = me;
me->type = WRITER;
me->next = NULL;
me->state = 1;
xchg(&lock->tail, pred);
if (pred == NULL) {
lock->next_writer = me;
if ((atomic_read(lock->nr_readers) == 0)
&& (cmpxchg(&lock->next_writer, me, NULL) == me))
me->waiting = 0;
} else {
pred->successor_type = WRITER;
smp_wmb(); //(4)
pred->next = me;
}
while (me->waiting)
cpu_relax();
}
void writer_unlock(rwlock_t *lock)
{
qnode *me = get_myself();
if ((me->next != NULL)
|| (cmpxchg(&lock->tail, me, NULL) != me)) {
while (me->next == NULL)
cpu_relax();
if (me->next->type == READER)
atomic_inc(&lock->nr_readers);
me->next->waiting = 0;
}
}
|
