// workqueue.h -- the work queue for gold   -*- C++ -*-

// Copyright 2006, 2007 Free Software Foundation, Inc.
// Written by Ian Lance Taylor <iant@google.com>.

// This file is part of gold.

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
// MA 02110-1301, USA.

// After processing the command line, everything the linker does is
// driven from a work queue.  This permits us to parallelize the
// linker where possible.

// Task_token
//   A simple locking implementation to ensure proper task ordering.
// Task_read_token, Task_write_token
//   Lock a Task_token for read or write.
// Task_locker
//   Task locking using RAII.
// Task
//   An abstract class for jobs to run.

#ifndef GOLD_WORKQUEUE_H
#define GOLD_WORKQUEUE_H

#include "gold-threads.h"
#include "fileread.h"

namespace gold
{

class General_options;
class Task;
class Workqueue;

// Some tasks require access to shared data structures, such as the
// symbol table.  Some tasks must be executed in a particular error,
// such as reading input file symbol tables--if we see foo.o -llib, we
// have to read the symbols for foo.o before we read the ones for
// -llib.  To implement this safely and efficiently, we use tokens.
// Task_tokens support shared read/exclusive write access to some
// resource.  Alternatively, they support blockers: blockers implement
// the requirement that some set of tasks must complete before another
// set of tasks can start.  In such a case we increment the block
// count when we create the task, and decrement it when the task
// completes.  Task_tokens are only manipulated by the main thread, so
// they do not themselves require any locking.

class Task_token
{
 public:
  Task_token();

  ~Task_token();

  // A read/write token uses these methods.

  bool
  is_readable() const;

  void
  add_reader();

  void
  remove_reader();

  bool
  is_writable() const;

  void
  add_writer(const Task*);

  void
  remove_writer(const Task*);

  bool
  has_write_lock(const Task*);

  // A blocker token uses these methods.

  void
  add_blocker();

  // Returns true if block count drops to zero.
  bool
  remove_blocker();

  bool
  is_blocked() const;

 private:
  // It makes no sense to copy these.
  Task_token(const Task_token&);
  Task_token& operator=(const Task_token&);

  bool is_blocker_;
  int readers_;
  const Task* writer_;
};

// In order to support tokens more reliably, we provide objects which
// handle them using RAII.

class Task_read_token
{
 public:
  Task_read_token(Task_token& token)
    : token_(token)
  { this->token_.add_reader(); }

  ~Task_read_token()
  { this->token_.remove_reader(); }

 private:
  Task_read_token(const Task_read_token&);
  Task_read_token& operator=(const Task_read_token&);

  Task_token& token_;
};

class Task_write_token
{
 public:
  Task_write_token(Task_token& token, const Task* task)
    : token_(token), task_(task)
  { this->token_.add_writer(this->task_); }

  ~Task_write_token()
  { this->token_.remove_writer(this->task_); }

 private:
  Task_write_token(const Task_write_token&);
  Task_write_token& operator=(const Task_write_token&);

  Task_token& token_;
  const Task* task_;
};

class Task_block_token
{
 public:
  // The blocker count must be incremented when the task is created.
  // This object is created when the task is run.  When we unblock the
  // last task, we notify the workqueue.
  Task_block_token(Task_token& token, Workqueue* workqueue);
  ~Task_block_token();

 private:
  Task_block_token(const Task_block_token&);
  Task_block_token& operator=(const Task_block_token&);

  Task_token& token_;
  Workqueue* workqueue_;
};

// An object which implements an RAII lock for any object which
// supports lock and unlock methods.

template<typename Obj>
class Task_lock_obj
{
 public:
  Task_lock_obj(Obj& obj)
    : obj_(obj)
  { this->obj_.lock(); }

  ~Task_lock_obj()
  { this->obj_.unlock(); }

 private:
  Task_lock_obj(const Task_lock_obj&);
  Task_lock_obj& operator=(const Task_lock_obj&);

  Obj& obj_;
};

// An abstract class used to lock Task_tokens using RAII.  A typical
// implementation would simply have a set of members of type
// Task_read_token, Task_write_token, and Task_block_token.

class Task_locker
{
 public:
  Task_locker()
  { }

  virtual ~Task_locker()
  { }
};

// A version of Task_locker which may be used for a single read lock.

class Task_locker_read : public Task_locker
{
 public:
  Task_locker_read(Task_token& token)
    : read_token_(token)
  { }

 private:
  Task_locker_read(const Task_locker_read&);
  Task_locker_read& operator=(const Task_locker_read&);

  Task_read_token read_token_;
};

// A version of Task_locker which may be used for a single write lock.

class Task_locker_write : public Task_locker
{
 public:
  Task_locker_write(Task_token& token, const Task* task)
    : write_token_(token, task)
  { }

 private:
  Task_locker_write(const Task_locker_write&);
  Task_locker_write& operator=(const Task_locker_write&);

  Task_write_token write_token_;
};

// A version of Task_locker which may be used for a single blocker
// lock.

class Task_locker_block : public Task_locker
{
 public:
  Task_locker_block(Task_token& token, Workqueue* workqueue)
    : block_token_(token, workqueue)
  { }

 private:
  Task_locker_block(const Task_locker_block&);
  Task_locker_block& operator=(const Task_locker_block&);

  Task_block_token block_token_;
};

// A version of Task_locker which may be used to hold a lock on any
// object which supports lock() and unlock() methods.

template<typename Obj>
class Task_locker_obj : public Task_locker
{
 public:
  Task_locker_obj(Obj& obj)
    : obj_lock_(obj)
  { }

 private:
  Task_locker_obj(const Task_locker_obj&);
  Task_locker_obj& operator=(const Task_locker_obj&);

  Task_lock_obj<Obj> obj_lock_;
};

// The superclass for tasks to be placed on the workqueue.  Each
// specific task class will inherit from this one.

class Task
{
 public:
  Task()
  { }
  virtual ~Task()
  { }

  // Type returned by Is_runnable.
  enum Is_runnable_type
  {
    // Task is runnable.
    IS_RUNNABLE,
    // Task is waiting for a block to clear.
    IS_BLOCKED,
    // Task is not waiting for a block, but is not runnable--i.e., is
    // waiting for a lock.
    IS_LOCKED
  };

  // Return whether the task can be run now.  This method is only
  // called from the main thread.
  virtual Is_runnable_type
  is_runnable(Workqueue*) = 0;

  // Return a pointer to a Task_locker which locks all the resources
  // required by the task.  We delete the pointer when the task is
  // complete.  This method can return NULL if no locks are required.
  // This method is only called from the main thread.
  virtual Task_locker*
  locks(Workqueue*) = 0;

  // Run the task.
  virtual void
  run(Workqueue*) = 0;

 private:
  Task(const Task&);
  Task& operator=(const Task&);
};

// A simple task which waits for a blocker and then runs a function.

class Task_function_runner
{
 public:
  virtual ~Task_function_runner()
  { }

  virtual void
  run(Workqueue*) = 0;
};

class Task_function : public Task
{
 public:
  // Both points should be allocated using new, and will be deleted
  // after the task runs.
  Task_function(Task_function_runner* runner, Task_token* blocker)
    : runner_(runner), blocker_(blocker)
  { }

  ~Task_function()
  {
    delete this->runner_;
    delete this->blocker_;
  }

  // The standard task methods.

  // Wait until the task is unblocked.
  Is_runnable_type
  is_runnable(Workqueue*)
  { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; }

  // This type of task does not normally hold any locks.
  virtual Task_locker*
  locks(Workqueue*)
  { return NULL; }

  // Run the action.
  void
  run(Workqueue* workqueue)
  { this->runner_->run(workqueue); }

 private:
  Task_function(const Task_function&);
  Task_function& operator=(const Task_function&);

  Task_function_runner* runner_;
  Task_token* blocker_;
};

// The workqueue

class Workqueue_runner;

class Workqueue
{
 public:
  Workqueue(const General_options&);
  ~Workqueue();

  // Add a new task to the work queue.
  void
  queue(Task*);

  // Add a new task to the front of the work queue.  It will be the
  // next task to run if it is ready.
  void
  queue_front(Task*);

  // Process all the tasks on the work queue.
  void
  process();

  // A complete set of blocking tasks has completed.
  void
  cleared_blocker();

 private:
  // This class can not be copied.
  Workqueue(const Workqueue&);
  Workqueue& operator=(const Workqueue&);

  typedef std::list<Task*> Task_list;

  // Run a task.
  void run(Task*);

  friend class Workqueue_runner;

  // Find a runnable task.
  Task* find_runnable(Task_list&, bool*);

  // Add a lock to the completed queue.
  void completed(Task*, Task_locker*);

  // Clear the completed queue.
  bool clear_completed();

  // How to run a task.  Only accessed from main thread.
  Workqueue_runner* runner_;

  // Lock for access to tasks_ members.
  Lock tasks_lock_;
  // List of tasks to execute at each link level.
  Task_list tasks_;

  // Lock for access to completed_ and running_ members.
  Lock completed_lock_;
  // List of Task_locker objects for main thread to free.
  std::list<Task_locker*> completed_;
  // Number of tasks currently running.
  int running_;
  // Condition variable signalled when a new entry is added to completed_.
  Condvar completed_condvar_;

  // Number of blocker tokens which were fully cleared.  Only accessed
  // from main thread.
  int cleared_blockers_;
};

} // End namespace gold.

#endif // !defined(GOLD_WORKQUEUE_H)