Fix a race at thread creation
[stockfish] / src / thread.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <algorithm> // For std::count
21 #include <cassert>
22
23 #include "movegen.h"
24 #include "search.h"
25 #include "thread.h"
26 #include "ucioption.h"
27
28 using namespace Search;
29
30 ThreadPool Threads; // Global object
31
32 namespace {
33
34  // start_routine() is the C function which is called when a new thread
35  // is launched. It is a wrapper to the virtual function idle_loop().
36
37  extern "C" { long start_routine(Thread* th) { th->idle_loop(); return 0; } }
38
39
40  // Helpers to launch a thread after creation and joining before delete. Must be
41  // outside Thread c'tor and d'tor because object shall be fully initialized
42  // when start_routine (and hence virtual idle_loop) is called and when joining.
43
44  template<typename T> T* new_thread() {
45    T* th = new T();
46    thread_create(th->handle, start_routine, th);
47    return th;
48  }
49
50  void delete_thread(Thread* th) {
51    th->exit = true; // Search must be already finished
52    th->notify_one();
53    thread_join(th->handle); // Wait for thread termination
54    delete th;
55  }
56
57 }
58
59
60 // Thread c'tor starts a newly-created thread of execution that will call
61 // the the virtual function idle_loop(), going immediately to sleep.
62
63 Thread::Thread() /* : splitPoints() */ { // Value-initialization bug in MSVC
64
65   searching = exit = false;
66   maxPly = splitPointsSize = 0;
67   activeSplitPoint = NULL;
68   activePosition = NULL;
69   idx = Threads.size();
70 }
71
72
73 // TimerThread::idle_loop() is where the timer thread waits msec milliseconds
74 // and then calls check_time(). If msec is 0 thread sleeps until is woken up.
75 extern void check_time();
76
77 void TimerThread::idle_loop() {
78
79   while (!exit)
80   {
81       mutex.lock();
82
83       if (!exit)
84           sleepCondition.wait_for(mutex, msec ? msec : INT_MAX);
85
86       mutex.unlock();
87
88       if (msec)
89           check_time();
90   }
91 }
92
93
94 // MainThread::idle_loop() is where the main thread is parked waiting to be started
95 // when there is a new search. Main thread will launch all the slave threads.
96
97 void MainThread::idle_loop() {
98
99   while (true)
100   {
101       mutex.lock();
102
103       thinking = false;
104
105       while (!thinking && !exit)
106       {
107           Threads.sleepCondition.notify_one(); // Wake up UI thread if needed
108           sleepCondition.wait(mutex);
109       }
110
111       mutex.unlock();
112
113       if (exit)
114           return;
115
116       searching = true;
117
118       Search::think();
119
120       assert(searching);
121
122       searching = false;
123   }
124 }
125
126
127 // Thread::notify_one() wakes up the thread when there is some search to do
128
129 void Thread::notify_one() {
130
131   mutex.lock();
132   sleepCondition.notify_one();
133   mutex.unlock();
134 }
135
136
137 // Thread::wait_for() set the thread to sleep until condition 'b' turns true
138
139 void Thread::wait_for(volatile const bool& b) {
140
141   mutex.lock();
142   while (!b) sleepCondition.wait(mutex);
143   mutex.unlock();
144 }
145
146
147 // Thread::cutoff_occurred() checks whether a beta cutoff has occurred in the
148 // current active split point, or in some ancestor of the split point.
149
150 bool Thread::cutoff_occurred() const {
151
152   for (SplitPoint* sp = activeSplitPoint; sp; sp = sp->parentSplitPoint)
153       if (sp->cutoff)
154           return true;
155
156   return false;
157 }
158
159
160 // Thread::is_available_to() checks whether the thread is available to help the
161 // thread 'master' at a split point. An obvious requirement is that thread must
162 // be idle. With more than two threads, this is not sufficient: If the thread is
163 // the master of some split point, it is only available as a slave to the slaves
164 // which are busy searching the split point at the top of slaves split point
165 // stack (the "helpful master concept" in YBWC terminology).
166
167 bool Thread::is_available_to(Thread* master) const {
168
169   if (searching)
170       return false;
171
172   // Make a local copy to be sure doesn't become zero under our feet while
173   // testing next condition and so leading to an out of bound access.
174   int size = splitPointsSize;
175
176   // No split points means that the thread is available as a slave for any
177   // other thread otherwise apply the "helpful master" concept if possible.
178   return !size || (splitPoints[size - 1].slavesMask & (1ULL << master->idx));
179 }
180
181
182 // init() is called at startup to create and launch requested threads, that will
183 // go immediately to sleep due to 'sleepWhileIdle' set to true. We cannot use
184 // a c'tor becuase Threads is a static object and we need a fully initialized
185 // engine at this point due to allocation of Endgames in Thread c'tor.
186
187 void ThreadPool::init() {
188
189   sleepWhileIdle = true;
190   timer = new_thread<TimerThread>();
191   push_back(new_thread<MainThread>());
192   read_uci_options();
193 }
194
195
196 // exit() cleanly terminates the threads before the program exits
197
198 void ThreadPool::exit() {
199
200   delete_thread(timer); // As first because check_time() accesses threads data
201
202   for (iterator it = begin(); it != end(); ++it)
203       delete_thread(*it);
204 }
205
206
207 // read_uci_options() updates internal threads parameters from the corresponding
208 // UCI options and creates/destroys threads to match the requested number. Thread
209 // objects are dynamically allocated to avoid creating in advance all possible
210 // threads, with included pawns and material tables, if only few are used.
211
212 void ThreadPool::read_uci_options() {
213
214   maxThreadsPerSplitPoint = Options["Max Threads per Split Point"];
215   minimumSplitDepth       = Options["Min Split Depth"] * ONE_PLY;
216   size_t requested        = Options["Threads"];
217
218   assert(requested > 0);
219
220   while (size() < requested)
221       push_back(new_thread<Thread>());
222
223   while (size() > requested)
224   {
225       delete_thread(back());
226       pop_back();
227   }
228 }
229
230
231 // slave_available() tries to find an idle thread which is available as a slave
232 // for the thread 'master'.
233
234 Thread* ThreadPool::available_slave(Thread* master) const {
235
236   for (const_iterator it = begin(); it != end(); ++it)
237       if ((*it)->is_available_to(master))
238           return *it;
239
240   return NULL;
241 }
242
243
244 // split() does the actual work of distributing the work at a node between
245 // several available threads. If it does not succeed in splitting the node
246 // (because no idle threads are available), the function immediately returns.
247 // If splitting is possible, a SplitPoint object is initialized with all the
248 // data that must be copied to the helper threads and then helper threads are
249 // told that they have been assigned work. This will cause them to instantly
250 // leave their idle loops and call search(). When all threads have returned from
251 // search() then split() returns.
252
253 template <bool Fake>
254 void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue,
255                    Move* bestMove, Depth depth, Move threatMove, int moveCount,
256                    MovePicker* movePicker, int nodeType, bool cutNode) {
257
258   assert(pos.pos_is_ok());
259   assert(*bestValue <= alpha && alpha < beta && beta <= VALUE_INFINITE);
260   assert(*bestValue > -VALUE_INFINITE);
261   assert(depth >= Threads.minimumSplitDepth);
262   assert(searching);
263   assert(splitPointsSize < MAX_SPLITPOINTS_PER_THREAD);
264
265   // Pick the next available split point from the split point stack
266   SplitPoint& sp = splitPoints[splitPointsSize];
267
268   sp.masterThread = this;
269   sp.parentSplitPoint = activeSplitPoint;
270   sp.slavesMask = 1ULL << idx;
271   sp.depth = depth;
272   sp.bestValue = *bestValue;
273   sp.bestMove = *bestMove;
274   sp.threatMove = threatMove;
275   sp.alpha = alpha;
276   sp.beta = beta;
277   sp.nodeType = nodeType;
278   sp.cutNode = cutNode;
279   sp.movePicker = movePicker;
280   sp.moveCount = moveCount;
281   sp.pos = &pos;
282   sp.nodes = 0;
283   sp.cutoff = false;
284   sp.ss = ss;
285
286   // Try to allocate available threads and ask them to start searching setting
287   // 'searching' flag. This must be done under lock protection to avoid concurrent
288   // allocation of the same slave by another master.
289   Threads.mutex.lock();
290   sp.mutex.lock();
291
292   splitPointsSize++;
293   activeSplitPoint = &sp;
294   activePosition = NULL;
295
296   size_t slavesCnt = 1; // This thread is always included
297   Thread* slave;
298
299   while (    (slave = Threads.available_slave(this)) != NULL
300          && ++slavesCnt <= Threads.maxThreadsPerSplitPoint && !Fake)
301   {
302       sp.slavesMask |= 1ULL << slave->idx;
303       slave->activeSplitPoint = &sp;
304       slave->searching = true; // Slave leaves idle_loop()
305       slave->notify_one(); // Could be sleeping
306   }
307
308   // Everything is set up. The master thread enters the idle loop, from which
309   // it will instantly launch a search, because its 'searching' flag is set.
310   // The thread will return from the idle loop when all slaves have finished
311   // their work at this split point.
312   if (slavesCnt > 1 || Fake)
313   {
314       sp.mutex.unlock();
315       Threads.mutex.unlock();
316
317       Thread::idle_loop(); // Force a call to base class idle_loop()
318
319       // In helpful master concept a master can help only a sub-tree of its split
320       // point, and because here is all finished is not possible master is booked.
321       assert(!searching);
322       assert(!activePosition);
323
324       // We have returned from the idle loop, which means that all threads are
325       // finished. Note that setting 'searching' and decreasing splitPointsSize is
326       // done under lock protection to avoid a race with Thread::is_available_to().
327       Threads.mutex.lock();
328       sp.mutex.lock();
329   }
330
331   searching = true;
332   splitPointsSize--;
333   activeSplitPoint = sp.parentSplitPoint;
334   activePosition = &pos;
335   pos.set_nodes_searched(pos.nodes_searched() + sp.nodes);
336   *bestMove = sp.bestMove;
337   *bestValue = sp.bestValue;
338
339   sp.mutex.unlock();
340   Threads.mutex.unlock();
341 }
342
343 // Explicit template instantiations
344 template void Thread::split<false>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool);
345 template void Thread::split< true>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool);
346
347
348 // wait_for_think_finished() waits for main thread to go to sleep then returns
349
350 void ThreadPool::wait_for_think_finished() {
351
352   MainThread* t = main_thread();
353   t->mutex.lock();
354   while (t->thinking) sleepCondition.wait(t->mutex);
355   t->mutex.unlock();
356 }
357
358
359 // start_thinking() wakes up the main thread sleeping in MainThread::idle_loop()
360 // so to start a new search, then returns immediately.
361
362 void ThreadPool::start_thinking(const Position& pos, const LimitsType& limits,
363                                 const std::vector<Move>& searchMoves, StateStackPtr& states) {
364   wait_for_think_finished();
365
366   SearchTime = Time::now(); // As early as possible
367
368   Signals.stopOnPonderhit = Signals.firstRootMove = false;
369   Signals.stop = Signals.failedLowAtRoot = false;
370
371   RootMoves.clear();
372   RootPos = pos;
373   Limits = limits;
374   if (states.get()) // If we don't set a new position, preserve current state
375   {
376       SetupStates = states; // Ownership transfer here
377       assert(!states.get());
378   }
379
380   for (MoveList<LEGAL> it(pos); *it; ++it)
381       if (   searchMoves.empty()
382           || std::count(searchMoves.begin(), searchMoves.end(), *it))
383           RootMoves.push_back(RootMove(*it));
384
385   main_thread()->thinking = true;
386   main_thread()->notify_one(); // Starts main thread
387 }