source: doc/theses/thierry_delisle_PhD/code/processor_list_good.cpp @ c921712

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since c921712 was b2a37b0, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Initial drafts in C++ of the CFA scheduler

  • Property mode set to 100644
File size: 5.4 KB
Line 
1#include "processor_list.hpp"
2
3#include <iostream>
4#include <string>
5#include <thread>
6
7unsigned num() {
8        return 0x1000000;
9}
10
11// Barrier from
12class barrier_t {
13public:
14        barrier_t(size_t total)
15                : waiting(0)
16                , total(total)
17        {}
18
19        void wait(unsigned) {
20                size_t target = waiting++;
21                target = (target - (target % total)) + total;
22                while(waiting < target)
23                        asm volatile("pause");
24
25                assert(waiting < (1ul << 60));
26        }
27
28private:
29        std::atomic<size_t> waiting;
30        size_t total;
31};
32
33class Random {
34private:
35        unsigned int seed;
36public:
37        Random(int seed) {
38                this->seed = seed;
39        }
40
41        /** returns pseudorandom x satisfying 0 <= x < n. **/
42        unsigned int next() {
43                seed ^= seed << 6;
44                seed ^= seed >> 21;
45                seed ^= seed << 7;
46                return seed;
47        }
48};
49
50//-------------------
51
52struct processor {
53        unsigned id;
54};
55
56// Stage 1
57// Make sure that the early registration works correctly
58// Registration uses a different process if the act of
59// registering the processor makes it the highest processor count
60// seen yet.
61void stage1(unsigned nthread, unsigned repeats) {
62        const int n = repeats;
63        const int nproc = 10;
64
65        // List being tested
66        processor_list list;
67
68        // Barrier for synchronization
69        barrier_t barrier(nthread + 1);
70
71        // Seen values to detect duplicattion
72        std::atomic<processor *> ids[nthread * nproc];
73        for(auto & i : ids) {
74                i = nullptr;
75        }
76
77        // Can't pass VLA to lambda
78        std::atomic<processor *> * idsp = ids;
79
80        // Threads which will run the code
81        std::thread * threads[nthread];
82        unsigned i = 1;
83        for(auto & t : threads) {
84                // Each thread will try to register a processor then add it to the
85                // list of registerd processor
86                t = new std::thread([&list, &barrier, idsp, n](unsigned tid){
87                        processor proc[nproc];
88                        for(int i = 0; i < n; i++) {
89                                for(auto & p : proc) {
90                                        // Register the thread
91                                        p.id = list.doregister(&p);
92                                }
93
94                                for(auto & p : proc) {
95                                        // Make sure no one got this id before
96                                        processor * prev = idsp[p.id].exchange(&p);
97                                        assert(nullptr == prev);
98
99                                        // Make sure id is still consistend
100                                        assert(&p == list.get(p.id));
101                                }
102
103                                // wait for round to finish
104                                barrier.wait(tid);
105
106                                // wait for reset
107                                barrier.wait(tid);
108                        }
109                }, i++);
110        }
111
112        for(int i = 0; i < n; i++) {
113                //Wait for round to finish
114                barrier.wait(0);
115
116                // Reset list
117                list.reset();
118
119                std::cout << i << "\r";
120
121                // Reset seen values
122                for(auto & i : ids) {
123                        i = nullptr;
124                }
125
126                // Start next round
127                barrier.wait(0);
128        }
129
130        for(auto t : threads) {
131                t->join();
132                delete t;
133        }
134}
135
136// Stage 2
137// Check that once churning starts, registration is still consistent.
138void stage2(unsigned nthread, unsigned repeats) {
139        // List being tested
140        processor_list list;
141
142        // Threads which will run the code
143        std::thread * threads[nthread];
144        unsigned i = 1;
145        for(auto & t : threads) {
146                // Each thread will try to register a few processors and
147                // unregister them, making sure that the registration is
148                // consistent
149                t = new std::thread([&list, repeats](unsigned tid){
150                        processor procs[10];
151                        for(unsigned i = 0; i < repeats; i++) {
152                                // register the procs and note the id
153                                for(auto & p : procs) {
154                                        p.id = list.doregister(&p);
155                                }
156
157                                if(1 == tid) std::cout << i << "\r";
158
159                                // check the id is still consistent
160                                for(const auto & p : procs) {
161                                        assert(&p == list.get(p.id));
162                                }
163
164                                // unregister and check the id is consistent
165                                for(const auto & p : procs) {
166                                        assert(&p == list.unregister(p.id));
167                                }
168                        }
169                }, i++);
170        }
171
172        for(auto t : threads) {
173                t->join();
174                delete t;
175        }
176}
177
178bool is_writer();
179
180// Stage 3
181// Check that the reader writer lock works.
182void stage3(unsigned nthread, unsigned repeats) {
183        // List being tested
184        processor_list list;
185
186        size_t before = 0;
187
188        std::unique_ptr<size_t> after( new size_t(0) );
189
190        std::atomic<bool> done ( false );
191
192        // Threads which will run the code
193        std::thread * threads[nthread];
194        unsigned i = 1;
195        for(auto & t : threads) {
196                // Each thread will try to register a few processors and
197                // unregister them, making sure that the registration is
198                // consistent
199                t = new std::thread([&list, repeats, &before, &after, &done](unsigned tid){
200                        Random rng(tid);
201                        processor proc;
202                        proc.id = list.doregister(&proc);
203                        while(!done) {
204
205                                if( (rng.next() % 100) == 0 ) {
206                                        auto r = list.write_lock();
207
208                                        auto b = before++;
209
210                                        std::cout << b << "\r";
211
212                                        (*after)++;
213
214                                        if(b >= repeats) done = true;
215
216                                        list.write_unlock(r);
217                                }
218                                else {
219                                        list.read_lock(proc.id);
220                                        assert(before == *after);
221                                        list.read_unlock(proc.id);
222                                }
223
224                        }
225
226                        list.unregister(proc.id);
227                }, i++);
228        }
229
230        for(auto t : threads) {
231                t->join();
232                delete t;
233        }
234}
235
236int main(int argc, char * argv[]) {
237
238        unsigned nthreads = 1;
239        if( argc >= 3 ) {
240                size_t idx;
241                nthreads = std::stoul(argv[2], &idx);
242                assert('\0' == argv[2][idx]);
243        }
244
245        unsigned repeats = 100;
246        if( argc >= 2 ) {
247                size_t idx;
248                repeats = std::stoul(argv[1], &idx);
249                assert('\0' == argv[1][idx]);
250        }
251
252        processor_list::check_cache_line_size();
253
254        std::cout << "Running " << repeats << " repetitions on " << nthreads << " threads" << std::endl;
255        std::cout << "Checking registration - early" << std::endl;
256        stage1(nthreads, repeats);
257        std::cout << "Done                         " << std::endl;
258
259        std::cout << "Checking registration - churn" << std::endl;
260        stage2(nthreads, repeats);
261        std::cout << "Done                         " << std::endl;
262
263        std::cout << "Checking RW lock             " << std::endl;
264        stage3(nthreads, repeats);
265        std::cout << "Done                         " << std::endl;
266
267
268        return 0;
269}
Note: See TracBrowser for help on using the repository browser.