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

Subversion Repositories open8_urisc

[/] [open8_urisc/] [trunk/] [gnu/] [binutils/] [gold/] [workqueue.cc] - Blame information for rev 27

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

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

powered by: WebSVN 2.1.0

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