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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
/* This software was written by Dirk Engling <erdgeist@erdgeist.org>
It is considered beerware. Prost. Skol. Cheers or whatever.
$id$ */
/* System */
#include <pthread.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
/* Opentracker */
#include "ot_fdstate.h"
#include "test.h"
/* ------------------------------------------------------- one thread first */
static void case_open_claim_release(void) {
char cookie[4];
uint32_t generation;
test_case("a descriptor taken into the table can be claimed and gives back its cookie");
generation = fdstate_open(7, cookie, 0);
CHECK_INT(fdstate_claim(7, generation), 1);
CHECK_PTR(fdstate_cookie(7), cookie);
fdstate_release(7);
test_case("and can be claimed again once released");
CHECK_INT(fdstate_claim(7, generation), 1);
fdstate_release(7);
fdstate_close(7);
}
static void case_one_holder_at_a_time(void) {
uint32_t generation = fdstate_open(8, NULL, 0);
test_case("a descriptor somebody holds cannot be claimed again");
CHECK_INT(fdstate_claim(8, generation), 1);
CHECK_INT(fdstate_claim(8, generation), 0);
fdstate_release(8);
CHECK_INT(fdstate_claim(8, generation), 1);
fdstate_release(8);
fdstate_close(8);
}
static void case_stale_generation_is_refused(void) {
char first[4], second[4];
uint32_t old, new;
test_case("a caller quoting the generation of a closed descriptor is turned away");
old = fdstate_open(9, first, 0);
fdstate_close(9);
new = fdstate_open(9, second, 0);
CHECK(old != new);
CHECK_INT(fdstate_claim(9, old), 0);
test_case("while the one quoting the new generation gets the new cookie");
CHECK_INT(fdstate_claim(9, new), 1);
CHECK_PTR(fdstate_cookie(9), second);
fdstate_release(9);
fdstate_close(9);
}
static void case_expiry(void) {
uint32_t generation = fdstate_open(10, NULL, 100);
test_case("a descriptor past its expiry is collected");
CHECK_INT(fdstate_claim_expired(10, 99), 0);
CHECK_INT(fdstate_claim_expired(10, 100), 1);
fdstate_close(10);
test_case("one that never expires is never collected");
generation = fdstate_open(10, NULL, 0);
CHECK_INT(fdstate_claim_expired(10, 1 << 30), 0);
test_case("and one somebody is working on is left alone");
fdstate_set_expiry(10, 1);
CHECK_INT(fdstate_claim(10, generation), 1);
CHECK_INT(fdstate_claim_expired(10, 1 << 30), 0);
fdstate_release(10);
CHECK_INT(fdstate_claim_expired(10, 1 << 30), 1);
fdstate_close(10);
}
static void case_out_of_range(void) {
test_case("a descriptor outside the table is refused rather than trusted");
CHECK_INT(fdstate_claim(-1, 0), 0);
CHECK_INT(fdstate_claim((int)fdstate_slots(), 0), 0);
CHECK_INT(fdstate_claim_expired(-1, 0), 0);
CHECK_PTR(fdstate_cookie(-1), NULL);
}
/* --------------------------------------------------------- then in anger */
/* The race this is about only exists while a descriptor is being recycled,
so recycling is driven by work done rather than by a clock: every slot is
given up after RECYCLE_AFTER claims, whatever the machine's speed. */
#define STRESS_SLOTS 64
#define RECYCLE_AFTER 32
#define STRESS_CLAIMS 200000
#define STRESS_GIVEUP (STRESS_CLAIMS * 100)
static _Atomic long stress_claims, stress_recycles, stress_violations, stress_attempts;
static _Atomic int stress_lives[STRESS_SLOTS];
static _Atomic int stress_live[STRESS_SLOTS];
/* Generation and cookie are published in one word so a worker can never read
a cookie that belongs to a different generation than the one it claimed
with. Each connection gets a cookie nobody else ever gets. */
static _Atomic uint64_t stress_conn[STRESS_SLOTS];
static _Atomic uint64_t stress_next_cookie;
#define STRESS_CONN(cookie, gen) (((uint64_t)(cookie) << 32) | (uint32_t)(gen))
#define STRESS_CONN_COOKIE(w) ((void *)(uintptr_t)((w) >> 32))
#define STRESS_CONN_GEN(w) ((uint32_t)(w))
static int stress_running(void) {
return atomic_load(&stress_claims) < STRESS_CLAIMS && atomic_load(&stress_attempts) < STRESS_GIVEUP;
}
static void *stress_worker(void *arg) {
unsigned seed = (unsigned)(uintptr_t)arg;
while (stress_running()) {
int fd = (int)(rand_r(&seed) % STRESS_SLOTS);
uint64_t conn = atomic_load(&stress_conn[fd]);
atomic_fetch_add(&stress_attempts, 1);
if (!fdstate_claim(fd, STRESS_CONN_GEN(conn)))
continue;
if (fdstate_cookie(fd) != STRESS_CONN_COOKIE(conn))
atomic_fetch_add(&stress_violations, 1);
if (atomic_fetch_sub(&stress_lives[fd], 1) <= 1)
fdstate_set_expiry(fd, 1); /* retired by its holder, as a handler would */
if (fdstate_cookie(fd) != STRESS_CONN_COOKIE(conn))
atomic_fetch_add(&stress_violations, 1);
fdstate_release(fd);
atomic_fetch_add(&stress_claims, 1);
}
return NULL;
}
static void *stress_keeper(void *arg) {
(void)arg;
while (stress_running()) {
int fd;
for (fd = 0; fd < STRESS_SLOTS; ++fd) {
if (atomic_load(&stress_live[fd])) {
if (!fdstate_claim_expired(fd, 1))
continue; /* a worker has it, come back */
fdstate_close(fd);
atomic_store(&stress_live[fd], 0);
atomic_fetch_add(&stress_recycles, 1);
}
{
void *cookie = (void *)(uintptr_t)(atomic_fetch_add(&stress_next_cookie, 1) + 1);
uint32_t gen = fdstate_open(fd, cookie, 0);
atomic_store(&stress_lives[fd], RECYCLE_AFTER);
atomic_store(&stress_conn[fd], STRESS_CONN((uintptr_t)cookie, gen));
atomic_store(&stress_live[fd], 1);
}
}
}
return NULL;
}
static void case_recycling_under_load(void) {
pthread_t worker[4], keeper;
size_t i;
test_case("no worker is ever handed a connection from another generation");
atomic_store(&stress_claims, 0);
atomic_store(&stress_recycles, 0);
atomic_store(&stress_violations, 0);
atomic_store(&stress_attempts, 0);
atomic_store(&stress_next_cookie, 0);
/* Every slot is opened and published before any worker runs: a worker only
ever learns of a descriptor from whoever registered it, and never
invents a generation of its own. */
for (i = 0; i < STRESS_SLOTS; ++i) {
void *cookie = (void *)(uintptr_t)(atomic_fetch_add(&stress_next_cookie, 1) + 1);
uint32_t gen = fdstate_open((int)i, cookie, 0);
atomic_store(&stress_lives[i], RECYCLE_AFTER);
atomic_store(&stress_conn[i], STRESS_CONN((uintptr_t)cookie, gen));
atomic_store(&stress_live[i], 1);
}
pthread_create(&keeper, NULL, stress_keeper, NULL);
for (i = 0; i < sizeof(worker) / sizeof(worker[0]); ++i)
pthread_create(&worker[i], NULL, stress_worker, (void *)(uintptr_t)(i + 1));
for (i = 0; i < sizeof(worker) / sizeof(worker[0]); ++i)
pthread_join(worker[i], NULL);
pthread_join(keeper, NULL);
CHECK_INT(atomic_load(&stress_violations), 0);
test_case("and the run actually recycled descriptors, or it proved nothing");
CHECK(atomic_load(&stress_claims) >= STRESS_CLAIMS);
CHECK(atomic_load(&stress_recycles) > STRESS_CLAIMS / (RECYCLE_AFTER * 4));
for (i = 0; i < STRESS_SLOTS; ++i)
fdstate_close((int)i);
}
void test_fdstate(void) {
CHECK_INT(fdstate_init(), 0);
CHECK(fdstate_slots() > STRESS_SLOTS);
case_open_claim_release();
case_one_holder_at_a_time();
case_stale_generation_is_refused();
case_expiry();
case_out_of_range();
case_recycling_under_load();
fdstate_deinit();
}
|
