OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [binutils-2.20.1/] [gold/] [workqueue.cc] - Blame information for rev 280

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 205 julius
// workqueue.cc -- the workqueue for gold
2
 
3
// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
4
// Written by Ian Lance Taylor <iant@google.com>.
5
 
6
// This file is part of gold.
7
 
8
// This program is free software; you can redistribute it and/or modify
9
// it under the terms of the GNU General Public License as published by
10
// the Free Software Foundation; either version 3 of the License, or
11
// (at your option) any later version.
12
 
13
// This program is distributed in the hope that it will be useful,
14
// but WITHOUT ANY WARRANTY; without even the implied warranty of
15
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
// GNU General Public License for more details.
17
 
18
// You should have received a copy of the GNU General Public License
19
// along with this program; if not, write to the Free Software
20
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21
// MA 02110-1301, USA.
22
 
23
#include "gold.h"
24
 
25
#include "debug.h"
26
#include "options.h"
27
#include "workqueue.h"
28
#include "workqueue-internal.h"
29
 
30
namespace gold
31
{
32
 
33
// Class Task_list.
34
 
35
// Add T to the end of the list.
36
 
37
inline void
38
Task_list::push_back(Task* t)
39
{
40
  gold_assert(t->list_next() == NULL);
41
  if (this->head_ == NULL)
42
    {
43
      this->head_ = t;
44
      this->tail_ = t;
45
    }
46
  else
47
    {
48
      this->tail_->set_list_next(t);
49
      this->tail_ = t;
50
    }
51
}
52
 
53
// Add T to the front of the list.
54
 
55
inline void
56
Task_list::push_front(Task* t)
57
{
58
  gold_assert(t->list_next() == NULL);
59
  if (this->head_ == NULL)
60
    {
61
      this->head_ = t;
62
      this->tail_ = t;
63
    }
64
  else
65
    {
66
      t->set_list_next(this->head_);
67
      this->head_ = t;
68
    }
69
}
70
 
71
// Remove and return the first Task waiting for this lock to be
72
// released.
73
 
74
inline Task*
75
Task_list::pop_front()
76
{
77
  Task* ret = this->head_;
78
  if (ret != NULL)
79
    {
80
      if (ret == this->tail_)
81
        {
82
          gold_assert(ret->list_next() == NULL);
83
          this->head_ = NULL;
84
          this->tail_ = NULL;
85
        }
86
      else
87
        {
88
          this->head_ = ret->list_next();
89
          gold_assert(this->head_ != NULL);
90
          ret->clear_list_next();
91
        }
92
    }
93
  return ret;
94
}
95
 
96
// The simple single-threaded implementation of Workqueue_threader.
97
 
98
class Workqueue_threader_single : public Workqueue_threader
99
{
100
 public:
101
  Workqueue_threader_single(Workqueue* workqueue)
102
    : Workqueue_threader(workqueue)
103
  { }
104
  ~Workqueue_threader_single()
105
  { }
106
 
107
  void
108
  set_thread_count(int thread_count)
109
  { gold_assert(thread_count > 0); }
110
 
111
  bool
112
  should_cancel_thread()
113
  { return false; }
114
};
115
 
116
// Workqueue methods.
117
 
118
Workqueue::Workqueue(const General_options& options)
119
  : lock_(),
120
    first_tasks_(),
121
    tasks_(),
122
    running_(0),
123
    waiting_(0),
124
    condvar_(this->lock_),
125
    threader_(NULL)
126
{
127
  bool threads = options.threads();
128
#ifndef ENABLE_THREADS
129
  threads = false;
130
#endif
131
  if (!threads)
132
    this->threader_ = new Workqueue_threader_single(this);
133
  else
134
    {
135
#ifdef ENABLE_THREADS
136
      this->threader_ = new Workqueue_threader_threadpool(this);
137
#else
138
      gold_unreachable();
139
#endif
140
    }
141
}
142
 
143
Workqueue::~Workqueue()
144
{
145
}
146
 
147
// Add a task to the end of a specific queue, or put it on the list
148
// waiting for a Token.
149
 
150
void
151
Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)
152
{
153
  Hold_lock hl(this->lock_);
154
 
155
  Task_token* token = t->is_runnable();
156
  if (token != NULL)
157
    {
158
      if (front)
159
        token->add_waiting_front(t);
160
      else
161
        token->add_waiting(t);
162
      ++this->waiting_;
163
    }
164
  else
165
    {
166
      if (front)
167
        queue->push_front(t);
168
      else
169
        queue->push_back(t);
170
      // Tell any waiting thread that there is work to do.
171
      this->condvar_.signal();
172
    }
173
}
174
 
175
// Add a task to the queue.
176
 
177
void
178
Workqueue::queue(Task* t)
179
{
180
  this->add_to_queue(&this->tasks_, t, false);
181
}
182
 
183
// Queue a task which should run soon.
184
 
185
void
186
Workqueue::queue_soon(Task* t)
187
{
188
  t->set_should_run_soon();
189
  this->add_to_queue(&this->first_tasks_, t, false);
190
}
191
 
192
// Queue a task which should run next.
193
 
194
void
195
Workqueue::queue_next(Task* t)
196
{
197
  t->set_should_run_soon();
198
  this->add_to_queue(&this->first_tasks_, t, true);
199
}
200
 
201
// Return whether to cancel the current thread.
202
 
203
inline bool
204
Workqueue::should_cancel_thread()
205
{
206
  return this->threader_->should_cancel_thread();
207
}
208
 
209
// Find a runnable task in TASKS.  Return NULL if none could be found.
210
// If we find a Task waiting for a Token, add it to the list for that
211
// Token.  The workqueue lock must be held when this is called.
212
 
213
Task*
214
Workqueue::find_runnable_in_list(Task_list* tasks)
215
{
216
  Task* t;
217
  while ((t = tasks->pop_front()) != NULL)
218
    {
219
      Task_token* token = t->is_runnable();
220
 
221
      if (token == NULL)
222
        return t;
223
 
224
      token->add_waiting(t);
225
      ++this->waiting_;
226
    }
227
 
228
  // We couldn't find any runnable task.
229
  return NULL;
230
}
231
 
232
// Find a runnable task.  Return NULL if none could be found.  The
233
// workqueue lock must be held when this is called.
234
 
235
Task*
236
Workqueue::find_runnable()
237
{
238
  Task* t = this->find_runnable_in_list(&this->first_tasks_);
239
  if (t == NULL)
240
    t = this->find_runnable_in_list(&this->tasks_);
241
  return t;
242
}
243
 
244
// Find a runnable a task, and wait until we find one.  Return NULL if
245
// we should exit.  The workqueue lock must be held when this is
246
// called.
247
 
248
Task*
249
Workqueue::find_runnable_or_wait(int thread_number)
250
{
251
  Task* t = this->find_runnable();
252
 
253
  while (t == NULL)
254
    {
255
      if (this->running_ == 0
256
          && this->first_tasks_.empty()
257
          && this->tasks_.empty())
258
        {
259
          // Kick all the threads to make them exit.
260
          this->condvar_.broadcast();
261
 
262
          gold_assert(this->waiting_ == 0);
263
          return NULL;
264
        }
265
 
266
      if (this->should_cancel_thread())
267
        return NULL;
268
 
269
      gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
270
 
271
      this->condvar_.wait();
272
 
273
      gold_debug(DEBUG_TASK, "%3d awake", thread_number);
274
 
275
      t = this->find_runnable();
276
    }
277
 
278
  return t;
279
}
280
 
281
// Find and run tasks.  If we can't find a runnable task, wait for one
282
// to become available.  If we run a task, and it frees up another
283
// runnable task, then run that one too.  This returns true if we
284
// should look for another task, false if we are cancelling this
285
// thread.
286
 
287
bool
288
Workqueue::find_and_run_task(int thread_number)
289
{
290
  Task* t;
291
  Task_locker tl;
292
 
293
  {
294
    Hold_lock hl(this->lock_);
295
 
296
    // Find a runnable task.
297
    t = this->find_runnable_or_wait(thread_number);
298
 
299
    if (t == NULL)
300
      return false;
301
 
302
    // Get the locks for the task.  This must be called while we are
303
    // still holding the Workqueue lock.
304
    t->locks(&tl);
305
 
306
    ++this->running_;
307
  }
308
 
309
  while (t != NULL)
310
    {
311
      gold_debug(DEBUG_TASK, "%3d running   task %s", thread_number,
312
                 t->name().c_str());
313
 
314
      t->run(this);
315
 
316
      gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number,
317
                 t->name().c_str());
318
 
319
      Task* next;
320
      {
321
        Hold_lock hl(this->lock_);
322
 
323
        --this->running_;
324
 
325
        // Release the locks for the task.  This must be done with the
326
        // workqueue lock held.  Get the next Task to run if any.
327
        next = this->release_locks(t, &tl);
328
 
329
        if (next == NULL)
330
          next = this->find_runnable();
331
 
332
        // If we have another Task to run, get the Locks.  This must
333
        // be called while we are still holding the Workqueue lock.
334
        if (next != NULL)
335
          {
336
            tl.clear();
337
            next->locks(&tl);
338
 
339
            ++this->running_;
340
          }
341
      }
342
 
343
      // We are done with this task.
344
      delete t;
345
 
346
      t = next;
347
    }
348
 
349
  return true;
350
}
351
 
352
// Handle the return value of release_locks, and get tasks ready to
353
// run.
354
 
355
// 1) If T is not runnable, queue it on the appropriate token.
356
 
357
// 2) Otherwise, T is runnable.  If *PRET is not NULL, then we have
358
// already decided which Task to run next.  Add T to the list of
359
// runnable tasks, and signal another thread.
360
 
361
// 3) Otherwise, *PRET is NULL.  If IS_BLOCKER is false, then T was
362
// waiting on a write lock.  We can grab that lock now, so we run T
363
// now.
364
 
365
// 4) Otherwise, IS_BLOCKER is true.  If we should run T soon, then
366
// run it now.
367
 
368
// 5) Otherwise, check whether there are other tasks to run.  If there
369
// are, then we generally get a better ordering if we run those tasks
370
// now, before T.  A typical example is tasks waiting on the Dirsearch
371
// blocker.  We don't want to run those tasks right away just because
372
// the Dirsearch was unblocked.
373
 
374
// 6) Otherwise, there are no other tasks to run, so we might as well
375
// run this one now.
376
 
377
// This function must be called with the Workqueue lock held.
378
 
379
// Return true if we set *PRET to T, false otherwise.
380
 
381
bool
382
Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
383
{
384
  Task_token* token = t->is_runnable();
385
 
386
  if (token != NULL)
387
    {
388
      token->add_waiting(t);
389
      ++this->waiting_;
390
      return false;
391
    }
392
 
393
  bool should_queue = false;
394
  bool should_return = false;
395
 
396
  if (*pret != NULL)
397
    should_queue = true;
398
  else if (!is_blocker)
399
    should_return = true;
400
  else if (t->should_run_soon())
401
    should_return = true;
402
  else if (!this->first_tasks_.empty() || !this->tasks_.empty())
403
    should_queue = true;
404
  else
405
    should_return = true;
406
 
407
  if (should_return)
408
    {
409
      gold_assert(*pret == NULL);
410
      *pret = t;
411
      return true;
412
    }
413
  else if (should_queue)
414
    {
415
      if (t->should_run_soon())
416
        this->first_tasks_.push_back(t);
417
      else
418
        this->tasks_.push_back(t);
419
      this->condvar_.signal();
420
      return false;
421
    }
422
 
423
  gold_unreachable();
424
}
425
 
426
// Release the locks associated with a Task.  Return the first
427
// runnable Task that we find.  If we find more runnable tasks, add
428
// them to the run queue and signal any other threads.  This must be
429
// called with the Workqueue lock held.
430
 
431
Task*
432
Workqueue::release_locks(Task* t, Task_locker* tl)
433
{
434
  Task* ret = NULL;
435
  for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
436
    {
437
      Task_token* token = *p;
438
      if (token->is_blocker())
439
        {
440
          if (token->remove_blocker())
441
            {
442
              // The token has been unblocked.  Every waiting Task may
443
              // now be runnable.
444
              Task* t;
445
              while ((t = token->remove_first_waiting()) != NULL)
446
                {
447
                  --this->waiting_;
448
                  this->return_or_queue(t, true, &ret);
449
                }
450
            }
451
        }
452
      else
453
        {
454
          token->remove_writer(t);
455
 
456
          // One more waiting Task may now be runnable.  If we are
457
          // going to run it next, we can stop.  Otherwise we need to
458
          // move all the Tasks to the runnable queue, to avoid a
459
          // potential deadlock if the locking status changes before
460
          // we run the next thread.
461
          Task* t;
462
          while ((t = token->remove_first_waiting()) != NULL)
463
            {
464
              --this->waiting_;
465
              if (this->return_or_queue(t, false, &ret))
466
                break;
467
            }
468
        }
469
    }
470
  return ret;
471
}
472
 
473
// Process all the tasks on the workqueue.  Keep going until the
474
// workqueue is empty, or until we have been told to exit.  This
475
// function is called by all threads.
476
 
477
void
478
Workqueue::process(int thread_number)
479
{
480
  while (this->find_and_run_task(thread_number))
481
    ;
482
}
483
 
484
// Set the number of threads to use for the workqueue, if we are using
485
// threads.
486
 
487
void
488
Workqueue::set_thread_count(int threads)
489
{
490
  Hold_lock hl(this->lock_);
491
 
492
  this->threader_->set_thread_count(threads);
493
  // Wake up all the threads, since something has changed.
494
  this->condvar_.broadcast();
495
}
496
 
497
// Add a new blocker to an existing Task_token.
498
 
499
void
500
Workqueue::add_blocker(Task_token* token)
501
{
502
  Hold_lock hl(this->lock_);
503
  token->add_blocker();
504
}
505
 
506
} // End namespace gold.

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.