tools/ninja/patches/100-make_jobserver_support.patch

   1 From c1a081c00f803fc28e51f155f25abe8346ce5f13 Mon Sep 17 00:00:00 2001
   2 From: Stefan Becker <stefanb@gpartner-nvidia.com>
   3 Date: Tue, 22 Mar 2016 13:48:07 +0200
   4 Subject: [PATCH] Add GNU make jobserver client support
   5
   6 - add new TokenPool interface
   7 - GNU make implementation for TokenPool parses and verifies the magic
   8   information from the MAKEFLAGS environment variable
   9 - RealCommandRunner tries to acquire TokenPool
  10   * if no token pool is available then there is no change in behaviour
  11 - When a token pool is available then RealCommandRunner behaviour
  12   changes as follows
  13   * CanRunMore() only returns true if TokenPool::Acquire() returns true
  14   * StartCommand() calls TokenPool::Reserve()
  15   * WaitForCommand() calls TokenPool::Release()
  16
  17 Documentation for GNU make jobserver
  18
  19   http://make.mad-scientist.net/papers/jobserver-implementation/
  20
  21 Fixes https://github.com/ninja-build/ninja/issues/1139
  22
  23 Add TokenPool monitoring to SubprocessSet::DoWork()
  24
  25 Improve on the original jobserver client implementation. This makes
  26 ninja a more aggressive GNU make jobserver client.
  27
  28 - add monitor interface to TokenPool
  29 - TokenPool is passed down when main loop indicates that more work is
  30   ready and would be allowed to start if a token becomes available
  31 - posix: update DoWork() to monitor TokenPool read file descriptor
  32 - WaitForCommand() exits when DoWork() sets token flag
  33 - Main loop starts over when WaitForCommand() sets token exit status
  34
  35 Ignore jobserver when -jN is forced on command line
  36
  37 This emulates the behaviour of GNU make.
  38
  39 - add parallelism_from_cmdline flag to build configuration
  40 - set the flag when -jN is given on command line
  41 - pass the flag to TokenPool::Get()
  42 - GNUmakeTokenPool::Setup()
  43   * prints a warning when the flag is true and jobserver was detected
  44   * returns false, i.e. jobserver will be ignored
  45 - ignore config.parallelism in CanRunMore() when we have a valid
  46   TokenPool, because it gets always initialized to a default when not
  47   given on the command line
  48
  49 Honor -lN from MAKEFLAGS
  50
  51 This emulates the behaviour of GNU make.
  52
  53 - build: make a copy of max_load_average and pass it to TokenPool.
  54 - GNUmakeTokenPool: if we detect a jobserver and a valid -lN argument in
  55   MAKEFLAGS then set max_load_average to N.
  56
  57 Use LinePrinter for TokenPool messages
  58
  59 - replace printf() with calls to LinePrinter
  60 - print GNU make jobserver message only when verbose build is requested
  61
  62 Prepare PR for merging
  63
  64 - fix Windows build error in no-op TokenPool implementation
  65 - improve Acquire() to block for a maximum of 100ms
  66 - address review comments
  67
  68 Add tests for TokenPool
  69
  70 - TokenPool setup
  71 - GetMonitorFd() API
  72 - implicit token and tokens in jobserver pipe
  73 - Acquire() / Reserve() / Release() protocol
  74 - Clear() API
  75
  76 Add tests for subprocess module
  77
  78 - add TokenPoolTest stub to provide TokenPool::GetMonitorFd()
  79 - add two tests
  80   * both tests set up a dummy GNUmake jobserver pipe
  81   * both tests call DoWork() with TokenPoolTest
  82   * test 1: verify that DoWork() detects when a token is available
  83   * test 2: verify that DoWork() works as before without a token
  84 - the tests are not compiled in under Windows
  85
  86 Add tests for build module
  87
  88 Add tests that verify the token functionality of the builder main loop.
  89 We replace the default fake command runner with a special version where
  90 the tests can control each call to AcquireToken(), CanRunMore() and
  91 WaitForCommand().
  92
  93 Add Win32 implementation for GNUmakeTokenPool
  94
  95 GNU make uses a semaphore as jobserver protocol on Win32. See also
  96
  97    https://www.gnu.org/software/make/manual/html_node/Windows-Jobserver.html
  98
  99 Usage is pretty simple and straightforward, i.e. WaitForSingleObject()
 100 to obtain a token and ReleaseSemaphore() to return it.
 101
 102 Unfortunately subprocess-win32.cc uses an I/O completion port (IOCP).
 103 IOCPs aren't waitable objects, i.e. we can't use WaitForMultipleObjects()
 104 to wait on the IOCP and the token semaphore at the same time.
 105
 106 Therefore GNUmakeTokenPoolWin32 creates a child thread that waits on the
 107 token semaphore and posts a dummy I/O completion status on the IOCP when
 108 it was able to obtain a token. That unblocks SubprocessSet::DoWork() and
 109 it can then check if a token became available or not.
 110
 111 - split existing GNUmakeTokenPool into common and platform bits
 112 - add GNUmakeTokenPool interface
 113 - move the Posix bits to GNUmakeTokenPoolPosix
 114 - add the Win32 bits as GNUmakeTokenPoolWin32
 115 - move Setup() method up to TokenPool interface
 116 - update Subprocess & TokenPool tests accordingly
 117
 118 Prepare PR for merging - part II
 119
 120 - remove unnecessary "struct" from TokenPool
 121 - add PAPCFUNC cast to QueryUserAPC()
 122 - remove hard-coded MAKEFLAGS string from win32
 123 - remove useless build test CompleteNoWork
 124 - rename TokenPoolTest to TestTokenPool
 125 - add tokenpool modules to CMake build
 126 - remove unused no-op TokenPool implementation
 127 - address review comments from
 128
 129 https://github.com/ninja-build/ninja/pull/1140#pullrequestreview-195195803
 130 https://github.com/ninja-build/ninja/pull/1140#pullrequestreview-185089255
 131 https://github.com/ninja-build/ninja/pull/1140#issuecomment-473898963
 132 https://github.com/ninja-build/ninja/pull/1140#issuecomment-596624610
 133 ---
 134  CMakeLists.txt                  |   8 +-
 135  configure.py                    |   7 +-
 136  src/build.cc                    | 127 ++++++++---
 137  src/build.h                     |  12 +-
 138  src/build_test.cc               | 363 +++++++++++++++++++++++++++++++-
 139  src/exit_status.h               |   3 +-
 140  src/ninja.cc                    |   1 +
 141  src/subprocess-posix.cc         |  33 ++-
 142  src/subprocess-win32.cc         |  11 +-
 143  src/subprocess.h                |   8 +-
 144  src/subprocess_test.cc          | 149 +++++++++++--
 145  src/tokenpool-gnu-make-posix.cc | 202 ++++++++++++++++++
 146  src/tokenpool-gnu-make-win32.cc | 239 +++++++++++++++++++++
 147  src/tokenpool-gnu-make.cc       | 108 ++++++++++
 148  src/tokenpool-gnu-make.h        |  40 ++++
 149  src/tokenpool.h                 |  42 ++++
 150  src/tokenpool_test.cc           | 269 +++++++++++++++++++++++
 151  17 files changed, 1562 insertions(+), 60 deletions(-)
 152  create mode 100644 src/tokenpool-gnu-make-posix.cc
 153  create mode 100644 src/tokenpool-gnu-make-win32.cc
 154  create mode 100644 src/tokenpool-gnu-make.cc
 155  create mode 100644 src/tokenpool-gnu-make.h
 156  create mode 100644 src/tokenpool.h
 157  create mode 100644 src/tokenpool_test.cc
 158
 159 --- a/CMakeLists.txt
 160 +++ b/CMakeLists.txt
 161 @@ -94,6 +94,7 @@ add_library(libninja OBJECT
 162         src/parser.cc
 163         src/state.cc
 164         src/string_piece_util.cc
 165 +       src/tokenpool-gnu-make.cc
 166         src/util.cc
 167         src/version.cc
 168  )
 169 @@ -104,12 +105,16 @@ if(WIN32)
 170                 src/msvc_helper-win32.cc
 171                 src/msvc_helper_main-win32.cc
 172                 src/getopt.c
 173 +               src/tokenpool-gnu-make-win32.cc
 174         )
 175         if(MSVC)
 176                 target_sources(libninja PRIVATE src/minidump-win32.cc)
 177         endif()
 178  else()
 179 -       target_sources(libninja PRIVATE src/subprocess-posix.cc)
 180 +       target_sources(libninja PRIVATE
 181 +               src/subprocess-posix.cc
 182 +               src/tokenpool-gnu-make-posix.cc
 183 +       )
 184         if(CMAKE_SYSTEM_NAME STREQUAL "OS400" OR CMAKE_SYSTEM_NAME STREQUAL "AIX")
 185                 target_sources(libninja PRIVATE src/getopt.c)
 186         endif()
 187 @@ -182,6 +187,7 @@ if(BUILD_TESTING)
 188      src/string_piece_util_test.cc
 189      src/subprocess_test.cc
 190      src/test.cc
 191 +    src/tokenpool_test.cc
 192      src/util_test.cc
 193    )
 194    if(WIN32)
 195 --- a/configure.py
 196 +++ b/configure.py
 197 @@ -514,11 +514,13 @@ for name in ['build',
 198               'parser',
 199               'state',
 200               'string_piece_util',
 201 +             'tokenpool-gnu-make',
 202               'util',
 203               'version']:
 204      objs += cxx(name, variables=cxxvariables)
 205  if platform.is_windows():
 206      for name in ['subprocess-win32',
 207 +                 'tokenpool-gnu-make-win32',
 208                   'includes_normalize-win32',
 209                   'msvc_helper-win32',
 210                   'msvc_helper_main-win32']:
 211 @@ -527,7 +529,9 @@ if platform.is_windows():
 212          objs += cxx('minidump-win32', variables=cxxvariables)
 213      objs += cc('getopt')
 214  else:
 215 -    objs += cxx('subprocess-posix')
 216 +    for name in ['subprocess-posix',
 217 +                 'tokenpool-gnu-make-posix']:
 218 +        objs += cxx(name)
 219  if platform.is_aix():
 220      objs += cc('getopt')
 221  if platform.is_msvc():
 222 @@ -582,6 +586,7 @@ for name in ['build_log_test',
 223               'string_piece_util_test',
 224               'subprocess_test',
 225               'test',
 226 +             'tokenpool_test',
 227               'util_test']:
 228      objs += cxx(name, variables=cxxvariables)
 229  if platform.is_windows():
 230 --- a/src/build.cc
 231 +++ b/src/build.cc
 232 @@ -38,6 +38,7 @@
 233  #include "graph.h"
 234  #include "state.h"
 235  #include "subprocess.h"
 236 +#include "tokenpool.h"
 237  #include "util.h"
 238
 239  using namespace std;
 240 @@ -50,8 +51,9 @@ struct DryRunCommandRunner : public Comm
 241
 242    // Overridden from CommandRunner:
 243    virtual bool CanRunMore() const;
 244 +  virtual bool AcquireToken();
 245    virtual bool StartCommand(Edge* edge);
 246 -  virtual bool WaitForCommand(Result* result);
 247 +  virtual bool WaitForCommand(Result* result, bool more_ready);
 248
 249   private:
 250    queue<Edge*> finished_;
 251 @@ -61,12 +63,16 @@ bool DryRunCommandRunner::CanRunMore() c
 252    return true;
 253  }
 254
 255 +bool DryRunCommandRunner::AcquireToken() {
 256 +  return true;
 257 +}
 258 +
 259  bool DryRunCommandRunner::StartCommand(Edge* edge) {
 260    finished_.push(edge);
 261    return true;
 262  }
 263
 264 -bool DryRunCommandRunner::WaitForCommand(Result* result) {
 265 +bool DryRunCommandRunner::WaitForCommand(Result* result, bool more_ready) {
 266     if (finished_.empty())
 267       return false;
 268
 269 @@ -379,7 +385,7 @@ void Plan::EdgeWanted(const Edge* edge)
 270  }
 271
 272  Edge* Plan::FindWork() {
 273 -  if (ready_.empty())
 274 +  if (!more_ready())
 275      return NULL;
 276    set<Edge*>::iterator e = ready_.begin();
 277    Edge* edge = *e;
 278 @@ -665,19 +671,39 @@ void Plan::Dump() const {
 279  }
 280
 281  struct RealCommandRunner : public CommandRunner {
 282 -  explicit RealCommandRunner(const BuildConfig& config) : config_(config) {}
 283 -  virtual ~RealCommandRunner() {}
 284 +  explicit RealCommandRunner(const BuildConfig& config);
 285 +  virtual ~RealCommandRunner();
 286    virtual bool CanRunMore() const;
 287 +  virtual bool AcquireToken();
 288    virtual bool StartCommand(Edge* edge);
 289 -  virtual bool WaitForCommand(Result* result);
 290 +  virtual bool WaitForCommand(Result* result, bool more_ready);
 291    virtual vector<Edge*> GetActiveEdges();
 292    virtual void Abort();
 293
 294    const BuildConfig& config_;
 295 +  // copy of config_.max_load_average; can be modified by TokenPool setup
 296 +  double max_load_average_;
 297    SubprocessSet subprocs_;
 298 +  TokenPool* tokens_;
 299    map<const Subprocess*, Edge*> subproc_to_edge_;
 300  };
 301
 302 +RealCommandRunner::RealCommandRunner(const BuildConfig& config) : config_(config) {
 303 +  max_load_average_ = config.max_load_average;
 304 +  if ((tokens_ = TokenPool::Get()) != NULL) {
 305 +    if (!tokens_->Setup(config_.parallelism_from_cmdline,
 306 +                        config_.verbosity == BuildConfig::VERBOSE,
 307 +                        max_load_average_)) {
 308 +      delete tokens_;
 309 +      tokens_ = NULL;
 310 +    }
 311 +  }
 312 +}
 313 +
 314 +RealCommandRunner::~RealCommandRunner() {
 315 +  delete tokens_;
 316 +}
 317 +
 318  vector<Edge*> RealCommandRunner::GetActiveEdges() {
 319    vector<Edge*> edges;
 320    for (map<const Subprocess*, Edge*>::iterator e = subproc_to_edge_.begin();
 321 @@ -688,14 +714,23 @@ vector<Edge*> RealCommandRunner::GetActi
 322
 323  void RealCommandRunner::Abort() {
 324    subprocs_.Clear();
 325 +  if (tokens_)
 326 +    tokens_->Clear();
 327  }
 328
 329  bool RealCommandRunner::CanRunMore() const {
 330 -  size_t subproc_number =
 331 -      subprocs_.running_.size() + subprocs_.finished_.size();
 332 -  return (int)subproc_number < config_.parallelism
 333 -    && ((subprocs_.running_.empty() || config_.max_load_average <= 0.0f)
 334 -        || GetLoadAverage() < config_.max_load_average);
 335 +  bool parallelism_limit_not_reached =
 336 +    tokens_ || // ignore config_.parallelism
 337 +    ((int) (subprocs_.running_.size() +
 338 +            subprocs_.finished_.size()) < config_.parallelism);
 339 +  return parallelism_limit_not_reached
 340 +    && (subprocs_.running_.empty() ||
 341 +        (max_load_average_ <= 0.0f ||
 342 +         GetLoadAverage() < max_load_average_));
 343 +}
 344 +
 345 +bool RealCommandRunner::AcquireToken() {
 346 +  return (!tokens_ || tokens_->Acquire());
 347  }
 348
 349  bool RealCommandRunner::StartCommand(Edge* edge) {
 350 @@ -703,19 +738,33 @@ bool RealCommandRunner::StartCommand(Edg
 351    Subprocess* subproc = subprocs_.Add(command, edge->use_console());
 352    if (!subproc)
 353      return false;
 354 +  if (tokens_)
 355 +    tokens_->Reserve();
 356    subproc_to_edge_.insert(make_pair(subproc, edge));
 357
 358    return true;
 359  }
 360
 361 -bool RealCommandRunner::WaitForCommand(Result* result) {
 362 +bool RealCommandRunner::WaitForCommand(Result* result, bool more_ready) {
 363    Subprocess* subproc;
 364 -  while ((subproc = subprocs_.NextFinished()) == NULL) {
 365 -    bool interrupted = subprocs_.DoWork();
 366 +  subprocs_.ResetTokenAvailable();
 367 +  while (((subproc = subprocs_.NextFinished()) == NULL) &&
 368 +         !subprocs_.IsTokenAvailable()) {
 369 +    bool interrupted = subprocs_.DoWork(more_ready ? tokens_ : NULL);
 370      if (interrupted)
 371        return false;
 372    }
 373
 374 +  // token became available
 375 +  if (subproc == NULL) {
 376 +    result->status = ExitTokenAvailable;
 377 +    return true;
 378 +  }
 379 +
 380 +  // command completed
 381 +  if (tokens_)
 382 +    tokens_->Release();
 383 +
 384    result->status = subproc->Finish();
 385    result->output = subproc->GetOutput();
 386
 387 @@ -825,38 +874,42 @@ bool Builder::Build(string* err) {
 388    // command runner.
 389    // Second, we attempt to wait for / reap the next finished command.
 390    while (plan_.more_to_do()) {
 391 -    // See if we can start any more commands.
 392 -    if (failures_allowed && command_runner_->CanRunMore()) {
 393 -      if (Edge* edge = plan_.FindWork()) {
 394 -        if (edge->GetBindingBool("generator")) {
 395 -          scan_.build_log()->Close();
 396 -        }
 397 +    // See if we can start any more commands...
 398 +    bool can_run_more =
 399 +        failures_allowed   &&
 400 +        plan_.more_ready() &&
 401 +        command_runner_->CanRunMore();
 402 +
 403 +    // ... but we also need a token to do that.
 404 +    if (can_run_more && command_runner_->AcquireToken()) {
 405 +      Edge* edge = plan_.FindWork();
 406 +      if (edge->GetBindingBool("generator")) {
 407 +        scan_.build_log()->Close();
 408 +      }
 409 +      if (!StartEdge(edge, err)) {
 410 +        Cleanup();
 411 +        status_->BuildFinished();
 412 +        return false;
 413 +      }
 414
 415 -        if (!StartEdge(edge, err)) {
 416 +      if (edge->is_phony()) {
 417 +        if (!plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, err)) {
 418            Cleanup();
 419            status_->BuildFinished();
 420            return false;
 421          }
 422 -
 423 -        if (edge->is_phony()) {
 424 -          if (!plan_.EdgeFinished(edge, Plan::kEdgeSucceeded, err)) {
 425 -            Cleanup();
 426 -            status_->BuildFinished();
 427 -            return false;
 428 -          }
 429 -        } else {
 430 -          ++pending_commands;
 431 -        }
 432 -
 433 -        // We made some progress; go back to the main loop.
 434 -        continue;
 435 +      } else {
 436 +        ++pending_commands;
 437        }
 438 +
 439 +      // We made some progress; go back to the main loop.
 440 +      continue;
 441      }
 442
 443      // See if we can reap any finished commands.
 444      if (pending_commands) {
 445        CommandRunner::Result result;
 446 -      if (!command_runner_->WaitForCommand(&result) ||
 447 +      if (!command_runner_->WaitForCommand(&result, can_run_more) ||
 448            result.status == ExitInterrupted) {
 449          Cleanup();
 450          status_->BuildFinished();
 451 @@ -864,6 +917,10 @@ bool Builder::Build(string* err) {
 452          return false;
 453        }
 454
 455 +      // We might be able to start another command; start the main loop over.
 456 +      if (result.status == ExitTokenAvailable)
 457 +        continue;
 458 +
 459        --pending_commands;
 460        if (!FinishCommand(&result, err)) {
 461          Cleanup();
 462 --- a/src/build.h
 463 +++ b/src/build.h
 464 @@ -55,6 +55,9 @@ struct Plan {
 465    /// Returns true if there's more work to be done.
 466    bool more_to_do() const { return wanted_edges_ > 0 && command_edges_ > 0; }
 467
 468 +  /// Returns true if there's more edges ready to start
 469 +  bool more_ready() const { return !ready_.empty(); }
 470 +
 471    /// Dumps the current state of the plan.
 472    void Dump() const;
 473
 474 @@ -139,6 +142,7 @@ private:
 475  struct CommandRunner {
 476    virtual ~CommandRunner() {}
 477    virtual bool CanRunMore() const = 0;
 478 +  virtual bool AcquireToken() = 0;
 479    virtual bool StartCommand(Edge* edge) = 0;
 480
 481    /// The result of waiting for a command.
 482 @@ -150,7 +154,9 @@ struct CommandRunner {
 483      bool success() const { return status == ExitSuccess; }
 484    };
 485    /// Wait for a command to complete, or return false if interrupted.
 486 -  virtual bool WaitForCommand(Result* result) = 0;
 487 +  /// If more_ready is true then the optional TokenPool is monitored too
 488 +  /// and we return when a token becomes available.
 489 +  virtual bool WaitForCommand(Result* result, bool more_ready) = 0;
 490
 491    virtual std::vector<Edge*> GetActiveEdges() { return std::vector<Edge*>(); }
 492    virtual void Abort() {}
 493 @@ -158,7 +164,8 @@ struct CommandRunner {
 494
 495  /// Options (e.g. verbosity, parallelism) passed to a build.
 496  struct BuildConfig {
 497 -  BuildConfig() : verbosity(NORMAL), dry_run(false), parallelism(1),
 498 +  BuildConfig() : verbosity(NORMAL), dry_run(false),
 499 +                  parallelism(1), parallelism_from_cmdline(false),
 500                    failures_allowed(1), max_load_average(-0.0f) {}
 501
 502    enum Verbosity {
 503 @@ -169,6 +176,7 @@ struct BuildConfig {
 504    Verbosity verbosity;
 505    bool dry_run;
 506    int parallelism;
 507 +  bool parallelism_from_cmdline;
 508    int failures_allowed;
 509    /// The maximum load average we must not exceed. A negative value
 510    /// means that we do not have any limit.
 511 --- a/src/build_test.cc
 512 +++ b/src/build_test.cc
 513 @@ -15,6 +15,7 @@
 514  #include "build.h"
 515
 516  #include <assert.h>
 517 +#include <stdarg.h>
 518
 519  #include "build_log.h"
 520  #include "deps_log.h"
 521 @@ -473,8 +474,9 @@ struct FakeCommandRunner : public Comman
 522
 523    // CommandRunner impl
 524    virtual bool CanRunMore() const;
 525 +  virtual bool AcquireToken();
 526    virtual bool StartCommand(Edge* edge);
 527 -  virtual bool WaitForCommand(Result* result);
 528 +  virtual bool WaitForCommand(Result* result, bool more_ready);
 529    virtual vector<Edge*> GetActiveEdges();
 530    virtual void Abort();
 531
 532 @@ -580,6 +582,10 @@ bool FakeCommandRunner::CanRunMore() con
 533    return active_edges_.size() < max_active_edges_;
 534  }
 535
 536 +bool FakeCommandRunner::AcquireToken() {
 537 +  return true;
 538 +}
 539 +
 540  bool FakeCommandRunner::StartCommand(Edge* edge) {
 541    assert(active_edges_.size() < max_active_edges_);
 542    assert(find(active_edges_.begin(), active_edges_.end(), edge)
 543 @@ -625,7 +631,7 @@ bool FakeCommandRunner::StartCommand(Edg
 544    return true;
 545  }
 546
 547 -bool FakeCommandRunner::WaitForCommand(Result* result) {
 548 +bool FakeCommandRunner::WaitForCommand(Result* result, bool more_ready) {
 549    if (active_edges_.empty())
 550      return false;
 551
 552 @@ -3302,3 +3308,356 @@ TEST_F(BuildTest, DyndepTwoLevelDiscover
 553    EXPECT_EQ("touch tmp", command_runner_.commands_ran_[3]);
 554    EXPECT_EQ("touch out", command_runner_.commands_ran_[4]);
 555  }
 556 +
 557 +/// The token tests are concerned with the main loop functionality when
 558 +// the CommandRunner has an active TokenPool. It is therefore intentional
 559 +// that the plan doesn't complete and that builder_.Build() returns false!
 560 +
 561 +/// Fake implementation of CommandRunner that simulates a TokenPool
 562 +struct FakeTokenCommandRunner : public CommandRunner {
 563 +  explicit FakeTokenCommandRunner() {}
 564 +
 565 +  // CommandRunner impl
 566 +  virtual bool CanRunMore() const;
 567 +  virtual bool AcquireToken();
 568 +  virtual bool StartCommand(Edge* edge);
 569 +  virtual bool WaitForCommand(Result* result, bool more_ready);
 570 +  virtual vector<Edge*> GetActiveEdges();
 571 +  virtual void Abort();
 572 +
 573 +  vector<string> commands_ran_;
 574 +  vector<Edge *> edges_;
 575 +
 576 +  vector<bool> acquire_token_;
 577 +  vector<bool> can_run_more_;
 578 +  vector<bool> wait_for_command_;
 579 +};
 580 +
 581 +bool FakeTokenCommandRunner::CanRunMore() const {
 582 +  if (can_run_more_.size() == 0) {
 583 +    EXPECT_FALSE("unexpected call to CommandRunner::CanRunMore()");
 584 +    return false;
 585 +  }
 586 +
 587 +  bool result = can_run_more_[0];
 588 +
 589 +  // Unfortunately CanRunMore() isn't "const" for tests
 590 +  const_cast<FakeTokenCommandRunner*>(this)->can_run_more_.erase(
 591 +    const_cast<FakeTokenCommandRunner*>(this)->can_run_more_.begin()
 592 +  );
 593 +
 594 +  return result;
 595 +}
 596 +
 597 +bool FakeTokenCommandRunner::AcquireToken() {
 598 +  if (acquire_token_.size() == 0) {
 599 +    EXPECT_FALSE("unexpected call to CommandRunner::AcquireToken()");
 600 +    return false;
 601 +  }
 602 +
 603 +  bool result = acquire_token_[0];
 604 +  acquire_token_.erase(acquire_token_.begin());
 605 +  return result;
 606 +}
 607 +
 608 +bool FakeTokenCommandRunner::StartCommand(Edge* edge) {
 609 +  commands_ran_.push_back(edge->EvaluateCommand());
 610 +  edges_.push_back(edge);
 611 +  return true;
 612 +}
 613 +
 614 +bool FakeTokenCommandRunner::WaitForCommand(Result* result, bool more_ready) {
 615 +  if (wait_for_command_.size() == 0) {
 616 +    EXPECT_FALSE("unexpected call to CommandRunner::WaitForCommand()");
 617 +    return false;
 618 +  }
 619 +
 620 +  bool expected = wait_for_command_[0];
 621 +  if (expected != more_ready) {
 622 +    EXPECT_EQ(expected, more_ready);
 623 +    return false;
 624 +  }
 625 +  wait_for_command_.erase(wait_for_command_.begin());
 626 +
 627 +  if (edges_.size() == 0)
 628 +    return false;
 629 +
 630 +  Edge* edge = edges_[0];
 631 +  result->edge = edge;
 632 +
 633 +  if (more_ready &&
 634 +      (edge->rule().name() == "token-available")) {
 635 +    result->status = ExitTokenAvailable;
 636 +  } else {
 637 +    edges_.erase(edges_.begin());
 638 +    result->status = ExitSuccess;
 639 +  }
 640 +
 641 +  return true;
 642 +}
 643 +
 644 +vector<Edge*> FakeTokenCommandRunner::GetActiveEdges() {
 645 +  return edges_;
 646 +}
 647 +
 648 +void FakeTokenCommandRunner::Abort() {
 649 +  edges_.clear();
 650 +}
 651 +
 652 +struct BuildTokenTest : public BuildTest {
 653 +  virtual void SetUp();
 654 +  virtual void TearDown();
 655 +
 656 +  FakeTokenCommandRunner token_command_runner_;
 657 +
 658 +  void ExpectAcquireToken(int count, ...);
 659 +  void ExpectCanRunMore(int count, ...);
 660 +  void ExpectWaitForCommand(int count, ...);
 661 +
 662 +private:
 663 +  void EnqueueBooleans(vector<bool>& booleans, int count, va_list ao);
 664 +};
 665 +
 666 +void BuildTokenTest::SetUp() {
 667 +  BuildTest::SetUp();
 668 +
 669 +  // replace FakeCommandRunner with FakeTokenCommandRunner
 670 +  builder_.command_runner_.release();
 671 +  builder_.command_runner_.reset(&token_command_runner_);
 672 +}
 673 +void BuildTokenTest::TearDown() {
 674 +  EXPECT_EQ(0u, token_command_runner_.acquire_token_.size());
 675 +  EXPECT_EQ(0u, token_command_runner_.can_run_more_.size());
 676 +  EXPECT_EQ(0u, token_command_runner_.wait_for_command_.size());
 677 +
 678 +  BuildTest::TearDown();
 679 +}
 680 +
 681 +void BuildTokenTest::ExpectAcquireToken(int count, ...) {
 682 +  va_list ap;
 683 +  va_start(ap, count);
 684 +  EnqueueBooleans(token_command_runner_.acquire_token_, count, ap);
 685 +  va_end(ap);
 686 +}
 687 +
 688 +void BuildTokenTest::ExpectCanRunMore(int count, ...) {
 689 +  va_list ap;
 690 +  va_start(ap, count);
 691 +  EnqueueBooleans(token_command_runner_.can_run_more_, count, ap);
 692 +  va_end(ap);
 693 +}
 694 +
 695 +void BuildTokenTest::ExpectWaitForCommand(int count, ...) {
 696 +  va_list ap;
 697 +  va_start(ap, count);
 698 +  EnqueueBooleans(token_command_runner_.wait_for_command_, count, ap);
 699 +  va_end(ap);
 700 +}
 701 +
 702 +void BuildTokenTest::EnqueueBooleans(vector<bool>& booleans, int count, va_list ap) {
 703 +  while (count--) {
 704 +    int value = va_arg(ap, int);
 705 +    booleans.push_back(!!value); // force bool
 706 +  }
 707 +}
 708 +
 709 +TEST_F(BuildTokenTest, DoNotAquireToken) {
 710 +  // plan should execute one command
 711 +  string err;
 712 +  EXPECT_TRUE(builder_.AddTarget("cat1", &err));
 713 +  ASSERT_EQ("", err);
 714 +
 715 +  // pretend we can't run anything
 716 +  ExpectCanRunMore(1, false);
 717 +
 718 +  EXPECT_FALSE(builder_.Build(&err));
 719 +  EXPECT_EQ("stuck [this is a bug]", err);
 720 +
 721 +  EXPECT_EQ(0u, token_command_runner_.commands_ran_.size());
 722 +}
 723 +
 724 +TEST_F(BuildTokenTest, DoNotStartWithoutToken) {
 725 +  // plan should execute one command
 726 +  string err;
 727 +  EXPECT_TRUE(builder_.AddTarget("cat1", &err));
 728 +  ASSERT_EQ("", err);
 729 +
 730 +  // we could run a command but do not have a token for it
 731 +  ExpectCanRunMore(1,   true);
 732 +  ExpectAcquireToken(1, false);
 733 +
 734 +  EXPECT_FALSE(builder_.Build(&err));
 735 +  EXPECT_EQ("stuck [this is a bug]", err);
 736 +
 737 +  EXPECT_EQ(0u, token_command_runner_.commands_ran_.size());
 738 +}
 739 +
 740 +TEST_F(BuildTokenTest, CompleteOneStep) {
 741 +  // plan should execute one command
 742 +  string err;
 743 +  EXPECT_TRUE(builder_.AddTarget("cat1", &err));
 744 +  ASSERT_EQ("", err);
 745 +
 746 +  // allow running of one command
 747 +  ExpectCanRunMore(1,   true);
 748 +  ExpectAcquireToken(1, true);
 749 +  // block and wait for command to finalize
 750 +  ExpectWaitForCommand(1, false);
 751 +
 752 +  EXPECT_TRUE(builder_.Build(&err));
 753 +  EXPECT_EQ("", err);
 754 +
 755 +  EXPECT_EQ(1u, token_command_runner_.commands_ran_.size());
 756 +  EXPECT_TRUE(token_command_runner_.commands_ran_[0] == "cat in1 > cat1");
 757 +}
 758 +
 759 +TEST_F(BuildTokenTest, AcquireOneToken) {
 760 +  // plan should execute more than one command
 761 +  string err;
 762 +  EXPECT_TRUE(builder_.AddTarget("cat12", &err));
 763 +  ASSERT_EQ("", err);
 764 +
 765 +  // allow running of one command
 766 +  ExpectCanRunMore(3,     true, false, false);
 767 +  ExpectAcquireToken(1,   true);
 768 +  // block and wait for command to finalize
 769 +  ExpectWaitForCommand(1, false);
 770 +
 771 +  EXPECT_FALSE(builder_.Build(&err));
 772 +  EXPECT_EQ("stuck [this is a bug]", err);
 773 +
 774 +  EXPECT_EQ(1u, token_command_runner_.commands_ran_.size());
 775 +  // any of the two dependencies could have been executed
 776 +  EXPECT_TRUE(token_command_runner_.commands_ran_[0] == "cat in1 > cat1" ||
 777 +              token_command_runner_.commands_ran_[0] == "cat in1 in2 > cat2");
 778 +}
 779 +
 780 +TEST_F(BuildTokenTest, WantTwoTokens) {
 781 +  // plan should execute more than one command
 782 +  string err;
 783 +  EXPECT_TRUE(builder_.AddTarget("cat12", &err));
 784 +  ASSERT_EQ("", err);
 785 +
 786 +  // allow running of one command
 787 +  ExpectCanRunMore(3,     true, true, false);
 788 +  ExpectAcquireToken(2,   true, false);
 789 +  // wait for command to finalize or token to become available
 790 +  ExpectWaitForCommand(1, true);
 791 +
 792 +  EXPECT_FALSE(builder_.Build(&err));
 793 +  EXPECT_EQ("stuck [this is a bug]", err);
 794 +
 795 +  EXPECT_EQ(1u, token_command_runner_.commands_ran_.size());
 796 +  // any of the two dependencies could have been executed
 797 +  EXPECT_TRUE(token_command_runner_.commands_ran_[0] == "cat in1 > cat1" ||
 798 +              token_command_runner_.commands_ran_[0] == "cat in1 in2 > cat2");
 799 +}
 800 +
 801 +TEST_F(BuildTokenTest, CompleteTwoSteps) {
 802 +  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 803 +"build out1: cat in1\n"
 804 +"build out2: cat out1\n"));
 805 +
 806 +  // plan should execute more than one command
 807 +  string err;
 808 +  EXPECT_TRUE(builder_.AddTarget("out2", &err));
 809 +  ASSERT_EQ("", err);
 810 +
 811 +  // allow running of two commands
 812 +  ExpectCanRunMore(2,     true, true);
 813 +  ExpectAcquireToken(2,   true, true);
 814 +  // wait for commands to finalize
 815 +  ExpectWaitForCommand(2, false, false);
 816 +
 817 +  EXPECT_TRUE(builder_.Build(&err));
 818 +  EXPECT_EQ("", err);
 819 +
 820 +  EXPECT_EQ(2u, token_command_runner_.commands_ran_.size());
 821 +  EXPECT_TRUE(token_command_runner_.commands_ran_[0] == "cat in1 > out1");
 822 +  EXPECT_TRUE(token_command_runner_.commands_ran_[1] == "cat out1 > out2");
 823 +}
 824 +
 825 +TEST_F(BuildTokenTest, TwoCommandsInParallel) {
 826 +  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 827 +"rule token-available\n"
 828 +"  command = cat $in > $out\n"
 829 +"build out1: token-available in1\n"
 830 +"build out2: token-available in2\n"
 831 +"build out12: cat out1 out2\n"));
 832 +
 833 +  // plan should execute more than one command
 834 +  string err;
 835 +  EXPECT_TRUE(builder_.AddTarget("out12", &err));
 836 +  ASSERT_EQ("", err);
 837 +
 838 +  // 1st command: token available -> allow running
 839 +  // 2nd command: no token available but becomes available later
 840 +  ExpectCanRunMore(4,     true, true,  true,  false);
 841 +  ExpectAcquireToken(3,   true, false, true);
 842 +  // 1st call waits for command to finalize or token to become available
 843 +  // 2nd call waits for command to finalize
 844 +  // 3rd call waits for command to finalize
 845 +  ExpectWaitForCommand(3, true, false, false);
 846 +
 847 +  EXPECT_FALSE(builder_.Build(&err));
 848 +  EXPECT_EQ("stuck [this is a bug]", err);
 849 +
 850 +  EXPECT_EQ(2u, token_command_runner_.commands_ran_.size());
 851 +  EXPECT_TRUE((token_command_runner_.commands_ran_[0] == "cat in1 > out1" &&
 852 +               token_command_runner_.commands_ran_[1] == "cat in2 > out2") ||
 853 +              (token_command_runner_.commands_ran_[0] == "cat in2 > out2" &&
 854 +               token_command_runner_.commands_ran_[1] == "cat in1 > out1"));
 855 +}
 856 +
 857 +TEST_F(BuildTokenTest, CompleteThreeStepsSerial) {
 858 +  // plan should execute more than one command
 859 +  string err;
 860 +  EXPECT_TRUE(builder_.AddTarget("cat12", &err));
 861 +  ASSERT_EQ("", err);
 862 +
 863 +  // allow running of all commands
 864 +  ExpectCanRunMore(4,     true, true,  true,  true);
 865 +  ExpectAcquireToken(4,   true, false, true,  true);
 866 +  // wait for commands to finalize
 867 +  ExpectWaitForCommand(3, true, false, false);
 868 +
 869 +  EXPECT_TRUE(builder_.Build(&err));
 870 +  EXPECT_EQ("", err);
 871 +
 872 +  EXPECT_EQ(3u, token_command_runner_.commands_ran_.size());
 873 +  EXPECT_TRUE((token_command_runner_.commands_ran_[0] == "cat in1 > cat1"     &&
 874 +               token_command_runner_.commands_ran_[1] == "cat in1 in2 > cat2") ||
 875 +              (token_command_runner_.commands_ran_[0] == "cat in1 in2 > cat2" &&
 876 +               token_command_runner_.commands_ran_[1] == "cat in1 > cat1"    ));
 877 +  EXPECT_TRUE(token_command_runner_.commands_ran_[2] == "cat cat1 cat2 > cat12");
 878 +}
 879 +
 880 +TEST_F(BuildTokenTest, CompleteThreeStepsParallel) {
 881 +  ASSERT_NO_FATAL_FAILURE(AssertParse(&state_,
 882 +"rule token-available\n"
 883 +"  command = cat $in > $out\n"
 884 +"build out1: token-available in1\n"
 885 +"build out2: token-available in2\n"
 886 +"build out12: cat out1 out2\n"));
 887 +
 888 +  // plan should execute more than one command
 889 +  string err;
 890 +  EXPECT_TRUE(builder_.AddTarget("out12", &err));
 891 +  ASSERT_EQ("", err);
 892 +
 893 +  // allow running of all commands
 894 +  ExpectCanRunMore(4,     true, true,  true,  true);
 895 +  ExpectAcquireToken(4,   true, false, true,  true);
 896 +  // wait for commands to finalize
 897 +  ExpectWaitForCommand(4, true, false, false, false);
 898 +
 899 +  EXPECT_TRUE(builder_.Build(&err));
 900 +  EXPECT_EQ("", err);
 901 +
 902 +  EXPECT_EQ(3u, token_command_runner_.commands_ran_.size());
 903 +  EXPECT_TRUE((token_command_runner_.commands_ran_[0] == "cat in1 > out1" &&
 904 +               token_command_runner_.commands_ran_[1] == "cat in2 > out2") ||
 905 +              (token_command_runner_.commands_ran_[0] == "cat in2 > out2" &&
 906 +               token_command_runner_.commands_ran_[1] == "cat in1 > out1"));
 907 +  EXPECT_TRUE(token_command_runner_.commands_ran_[2] == "cat out1 out2 > out12");
 908 +}
 909 --- a/src/exit_status.h
 910 +++ b/src/exit_status.h
 911 @@ -18,7 +18,8 @@
 912  enum ExitStatus {
 913    ExitSuccess,
 914    ExitFailure,
 915 -  ExitInterrupted
 916 +  ExitTokenAvailable,
 917 +  ExitInterrupted,
 918  };
 919
 920  #endif  // NINJA_EXIT_STATUS_H_
 921 --- a/src/ninja.cc
 922 +++ b/src/ninja.cc
 923 @@ -1289,6 +1289,7 @@ int ReadFlags(int* argc, char*** argv,
 924          // We want to run N jobs in parallel. For N = 0, INT_MAX
 925          // is close enough to infinite for most sane builds.
 926          config->parallelism = value > 0 ? value : INT_MAX;
 927 +        config->parallelism_from_cmdline = true;
 928          break;
 929        }
 930        case 'k': {
 931 --- a/src/subprocess-posix.cc
 932 +++ b/src/subprocess-posix.cc
 933 @@ -13,6 +13,7 @@
 934  // limitations under the License.
 935
 936  #include "subprocess.h"
 937 +#include "tokenpool.h"
 938
 939  #include <sys/select.h>
 940  #include <assert.h>
 941 @@ -249,7 +250,7 @@ Subprocess *SubprocessSet::Add(const str
 942  }
 943
 944  #ifdef USE_PPOLL
 945 -bool SubprocessSet::DoWork() {
 946 +bool SubprocessSet::DoWork(TokenPool* tokens) {
 947    vector<pollfd> fds;
 948    nfds_t nfds = 0;
 949
 950 @@ -263,6 +264,12 @@ bool SubprocessSet::DoWork() {
 951      ++nfds;
 952    }
 953
 954 +  if (tokens) {
 955 +    pollfd pfd = { tokens->GetMonitorFd(), POLLIN | POLLPRI, 0 };
 956 +    fds.push_back(pfd);
 957 +    ++nfds;
 958 +  }
 959 +
 960    interrupted_ = 0;
 961    int ret = ppoll(&fds.front(), nfds, NULL, &old_mask_);
 962    if (ret == -1) {
 963 @@ -295,11 +302,20 @@ bool SubprocessSet::DoWork() {
 964      ++i;
 965    }
 966
 967 +  if (tokens) {
 968 +    pollfd *pfd = &fds[nfds - 1];
 969 +    if (pfd->fd >= 0) {
 970 +      assert(pfd->fd == tokens->GetMonitorFd());
 971 +      if (pfd->revents != 0)
 972 +        token_available_ = true;
 973 +    }
 974 +  }
 975 +
 976    return IsInterrupted();
 977  }
 978
 979  #else  // !defined(USE_PPOLL)
 980 -bool SubprocessSet::DoWork() {
 981 +bool SubprocessSet::DoWork(TokenPool* tokens) {
 982    fd_set set;
 983    int nfds = 0;
 984    FD_ZERO(&set);
 985 @@ -314,6 +330,13 @@ bool SubprocessSet::DoWork() {
 986      }
 987    }
 988
 989 +  if (tokens) {
 990 +    int fd = tokens->GetMonitorFd();
 991 +    FD_SET(fd, &set);
 992 +    if (nfds < fd+1)
 993 +      nfds = fd+1;
 994 +  }
 995 +
 996    interrupted_ = 0;
 997    int ret = pselect(nfds, &set, 0, 0, 0, &old_mask_);
 998    if (ret == -1) {
 999 @@ -342,6 +365,12 @@ bool SubprocessSet::DoWork() {
1000      ++i;
1001    }
1002
1003 +  if (tokens) {
1004 +    int fd = tokens->GetMonitorFd();
1005 +    if ((fd >= 0) && FD_ISSET(fd, &set))
1006 +    token_available_ = true;
1007 +  }
1008 +
1009    return IsInterrupted();
1010  }
1011  #endif  // !defined(USE_PPOLL)
1012 --- a/src/subprocess-win32.cc
1013 +++ b/src/subprocess-win32.cc
1014 @@ -13,6 +13,7 @@
1015  // limitations under the License.
1016
1017  #include "subprocess.h"
1018 +#include "tokenpool.h"
1019
1020  #include <assert.h>
1021  #include <stdio.h>
1022 @@ -251,11 +252,14 @@ Subprocess *SubprocessSet::Add(const str
1023    return subprocess;
1024  }
1025
1026 -bool SubprocessSet::DoWork() {
1027 +bool SubprocessSet::DoWork(TokenPool* tokens) {
1028    DWORD bytes_read;
1029    Subprocess* subproc;
1030    OVERLAPPED* overlapped;
1031
1032 +  if (tokens)
1033 +    tokens->WaitForTokenAvailability(ioport_);
1034 +
1035    if (!GetQueuedCompletionStatus(ioport_, &bytes_read, (PULONG_PTR)&subproc,
1036                                   &overlapped, INFINITE)) {
1037      if (GetLastError() != ERROR_BROKEN_PIPE)
1038 @@ -266,6 +270,11 @@ bool SubprocessSet::DoWork() {
1039                  // delivered by NotifyInterrupted above.
1040      return true;
1041
1042 +  if (tokens && tokens->TokenIsAvailable((ULONG_PTR)subproc)) {
1043 +    token_available_ = true;
1044 +    return false;
1045 +  }
1046 +
1047    subproc->OnPipeReady();
1048
1049    if (subproc->Done()) {
1050 --- a/src/subprocess.h
1051 +++ b/src/subprocess.h
1052 @@ -76,6 +76,8 @@ struct Subprocess {
1053    friend struct SubprocessSet;
1054  };
1055
1056 +struct TokenPool;
1057 +
1058  /// SubprocessSet runs a ppoll/pselect() loop around a set of Subprocesses.
1059  /// DoWork() waits for any state change in subprocesses; finished_
1060  /// is a queue of subprocesses as they finish.
1061 @@ -84,13 +86,17 @@ struct SubprocessSet {
1062    ~SubprocessSet();
1063
1064    Subprocess* Add(const std::string& command, bool use_console = false);
1065 -  bool DoWork();
1066 +  bool DoWork(struct TokenPool* tokens);
1067    Subprocess* NextFinished();
1068    void Clear();
1069
1070    std::vector<Subprocess*> running_;
1071    std::queue<Subprocess*> finished_;
1072
1073 +  bool token_available_;
1074 +  bool IsTokenAvailable() { return token_available_; }
1075 +  void ResetTokenAvailable() { token_available_ = false; }
1076 +
1077  #ifdef _WIN32
1078    static BOOL WINAPI NotifyInterrupted(DWORD dwCtrlType);
1079    static HANDLE ioport_;
1080 --- a/src/subprocess_test.cc
1081 +++ b/src/subprocess_test.cc
1082 @@ -13,6 +13,7 @@
1083  // limitations under the License.
1084
1085  #include "subprocess.h"
1086 +#include "tokenpool.h"
1087
1088  #include "test.h"
1089
1090 @@ -34,8 +35,30 @@ const char* kSimpleCommand = "cmd /c dir
1091  const char* kSimpleCommand = "ls /";
1092  #endif
1093
1094 +struct TestTokenPool : public TokenPool {
1095 +  bool Acquire()     { return false; }
1096 +  void Reserve()     {}
1097 +  void Release()     {}
1098 +  void Clear()       {}
1099 +  bool Setup(bool ignore_unused, bool verbose, double& max_load_average) { return false; }
1100 +
1101 +#ifdef _WIN32
1102 +  bool _token_available;
1103 +  void WaitForTokenAvailability(HANDLE ioport) {
1104 +    if (_token_available)
1105 +      // unblock GetQueuedCompletionStatus()
1106 +      PostQueuedCompletionStatus(ioport, 0, (ULONG_PTR) this, NULL);
1107 +  }
1108 +  bool TokenIsAvailable(ULONG_PTR key) { return key == (ULONG_PTR) this; }
1109 +#else
1110 +  int _fd;
1111 +  int GetMonitorFd() { return _fd; }
1112 +#endif
1113 +};
1114 +
1115  struct SubprocessTest : public testing::Test {
1116    SubprocessSet subprocs_;
1117 +  TestTokenPool tokens_;
1118  };
1119
1120  }  // anonymous namespace
1121 @@ -45,10 +68,12 @@ TEST_F(SubprocessTest, BadCommandStderr)
1122    Subprocess* subproc = subprocs_.Add("cmd /c ninja_no_such_command");
1123    ASSERT_NE((Subprocess *) 0, subproc);
1124
1125 +  subprocs_.ResetTokenAvailable();
1126    while (!subproc->Done()) {
1127      // Pretend we discovered that stderr was ready for writing.
1128 -    subprocs_.DoWork();
1129 +    subprocs_.DoWork(NULL);
1130    }
1131 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1132
1133    EXPECT_EQ(ExitFailure, subproc->Finish());
1134    EXPECT_NE("", subproc->GetOutput());
1135 @@ -59,10 +84,12 @@ TEST_F(SubprocessTest, NoSuchCommand) {
1136    Subprocess* subproc = subprocs_.Add("ninja_no_such_command");
1137    ASSERT_NE((Subprocess *) 0, subproc);
1138
1139 +  subprocs_.ResetTokenAvailable();
1140    while (!subproc->Done()) {
1141      // Pretend we discovered that stderr was ready for writing.
1142 -    subprocs_.DoWork();
1143 +    subprocs_.DoWork(NULL);
1144    }
1145 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1146
1147    EXPECT_EQ(ExitFailure, subproc->Finish());
1148    EXPECT_NE("", subproc->GetOutput());
1149 @@ -78,9 +105,11 @@ TEST_F(SubprocessTest, InterruptChild) {
1150    Subprocess* subproc = subprocs_.Add("kill -INT $$");
1151    ASSERT_NE((Subprocess *) 0, subproc);
1152
1153 +  subprocs_.ResetTokenAvailable();
1154    while (!subproc->Done()) {
1155 -    subprocs_.DoWork();
1156 +    subprocs_.DoWork(NULL);
1157    }
1158 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1159
1160    EXPECT_EQ(ExitInterrupted, subproc->Finish());
1161  }
1162 @@ -90,7 +119,7 @@ TEST_F(SubprocessTest, InterruptParent)
1163    ASSERT_NE((Subprocess *) 0, subproc);
1164
1165    while (!subproc->Done()) {
1166 -    bool interrupted = subprocs_.DoWork();
1167 +    bool interrupted = subprocs_.DoWork(NULL);
1168      if (interrupted)
1169        return;
1170    }
1171 @@ -102,9 +131,11 @@ TEST_F(SubprocessTest, InterruptChildWit
1172    Subprocess* subproc = subprocs_.Add("kill -TERM $$");
1173    ASSERT_NE((Subprocess *) 0, subproc);
1174
1175 +  subprocs_.ResetTokenAvailable();
1176    while (!subproc->Done()) {
1177 -    subprocs_.DoWork();
1178 +    subprocs_.DoWork(NULL);
1179    }
1180 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1181
1182    EXPECT_EQ(ExitInterrupted, subproc->Finish());
1183  }
1184 @@ -114,7 +145,7 @@ TEST_F(SubprocessTest, InterruptParentWi
1185    ASSERT_NE((Subprocess *) 0, subproc);
1186
1187    while (!subproc->Done()) {
1188 -    bool interrupted = subprocs_.DoWork();
1189 +    bool interrupted = subprocs_.DoWork(NULL);
1190      if (interrupted)
1191        return;
1192    }
1193 @@ -126,9 +157,11 @@ TEST_F(SubprocessTest, InterruptChildWit
1194    Subprocess* subproc = subprocs_.Add("kill -HUP $$");
1195    ASSERT_NE((Subprocess *) 0, subproc);
1196
1197 +  subprocs_.ResetTokenAvailable();
1198    while (!subproc->Done()) {
1199 -    subprocs_.DoWork();
1200 +    subprocs_.DoWork(NULL);
1201    }
1202 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1203
1204    EXPECT_EQ(ExitInterrupted, subproc->Finish());
1205  }
1206 @@ -138,7 +171,7 @@ TEST_F(SubprocessTest, InterruptParentWi
1207    ASSERT_NE((Subprocess *) 0, subproc);
1208
1209    while (!subproc->Done()) {
1210 -    bool interrupted = subprocs_.DoWork();
1211 +    bool interrupted = subprocs_.DoWork(NULL);
1212      if (interrupted)
1213        return;
1214    }
1215 @@ -153,9 +186,11 @@ TEST_F(SubprocessTest, Console) {
1216          subprocs_.Add("test -t 0 -a -t 1 -a -t 2", /*use_console=*/true);
1217      ASSERT_NE((Subprocess*)0, subproc);
1218
1219 +    subprocs_.ResetTokenAvailable();
1220      while (!subproc->Done()) {
1221 -      subprocs_.DoWork();
1222 +      subprocs_.DoWork(NULL);
1223      }
1224 +    ASSERT_FALSE(subprocs_.IsTokenAvailable());
1225
1226      EXPECT_EQ(ExitSuccess, subproc->Finish());
1227    }
1228 @@ -167,9 +202,11 @@ TEST_F(SubprocessTest, SetWithSingle) {
1229    Subprocess* subproc = subprocs_.Add(kSimpleCommand);
1230    ASSERT_NE((Subprocess *) 0, subproc);
1231
1232 +  subprocs_.ResetTokenAvailable();
1233    while (!subproc->Done()) {
1234 -    subprocs_.DoWork();
1235 +    subprocs_.DoWork(NULL);
1236    }
1237 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1238    ASSERT_EQ(ExitSuccess, subproc->Finish());
1239    ASSERT_NE("", subproc->GetOutput());
1240
1241 @@ -200,12 +237,13 @@ TEST_F(SubprocessTest, SetWithMulti) {
1242      ASSERT_EQ("", processes[i]->GetOutput());
1243    }
1244
1245 +  subprocs_.ResetTokenAvailable();
1246    while (!processes[0]->Done() || !processes[1]->Done() ||
1247           !processes[2]->Done()) {
1248      ASSERT_GT(subprocs_.running_.size(), 0u);
1249 -    subprocs_.DoWork();
1250 +    subprocs_.DoWork(NULL);
1251    }
1252 -
1253 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1254    ASSERT_EQ(0u, subprocs_.running_.size());
1255    ASSERT_EQ(3u, subprocs_.finished_.size());
1256
1257 @@ -237,8 +275,10 @@ TEST_F(SubprocessTest, SetWithLots) {
1258      ASSERT_NE((Subprocess *) 0, subproc);
1259      procs.push_back(subproc);
1260    }
1261 +  subprocs_.ResetTokenAvailable();
1262    while (!subprocs_.running_.empty())
1263 -    subprocs_.DoWork();
1264 +    subprocs_.DoWork(NULL);
1265 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1266    for (size_t i = 0; i < procs.size(); ++i) {
1267      ASSERT_EQ(ExitSuccess, procs[i]->Finish());
1268      ASSERT_NE("", procs[i]->GetOutput());
1269 @@ -254,10 +294,91 @@ TEST_F(SubprocessTest, SetWithLots) {
1270  // that stdin is closed.
1271  TEST_F(SubprocessTest, ReadStdin) {
1272    Subprocess* subproc = subprocs_.Add("cat -");
1273 +  subprocs_.ResetTokenAvailable();
1274    while (!subproc->Done()) {
1275 -    subprocs_.DoWork();
1276 +    subprocs_.DoWork(NULL);
1277    }
1278 +  ASSERT_FALSE(subprocs_.IsTokenAvailable());
1279    ASSERT_EQ(ExitSuccess, subproc->Finish());
1280    ASSERT_EQ(1u, subprocs_.finished_.size());
1281  }
1282  #endif  // _WIN32
1283 +
1284 +TEST_F(SubprocessTest, TokenAvailable) {
1285 +  Subprocess* subproc = subprocs_.Add(kSimpleCommand);
1286 +  ASSERT_NE((Subprocess *) 0, subproc);
1287 +
1288 +  // simulate GNUmake jobserver pipe with 1 token
1289 +#ifdef _WIN32
1290 +  tokens_._token_available = true;
1291 +#else
1292 +  int fds[2];
1293 +  ASSERT_EQ(0u, pipe(fds));
1294 +  tokens_._fd = fds[0];
1295 +  ASSERT_EQ(1u, write(fds[1], "T", 1));
1296 +#endif
1297 +
1298 +  subprocs_.ResetTokenAvailable();
1299 +  subprocs_.DoWork(&tokens_);
1300 +#ifdef _WIN32
1301 +  tokens_._token_available = false;
1302 +  // we need to loop here as we have no conrol where the token
1303 +  // I/O completion post ends up in the queue
1304 +  while (!subproc->Done() && !subprocs_.IsTokenAvailable()) {
1305 +    subprocs_.DoWork(&tokens_);
1306 +  }
1307 +#endif
1308 +
1309 +  EXPECT_TRUE(subprocs_.IsTokenAvailable());
1310 +  EXPECT_EQ(0u, subprocs_.finished_.size());
1311 +
1312 +  // remove token to let DoWork() wait for command again
1313 +#ifndef _WIN32
1314 +  char token;
1315 +  ASSERT_EQ(1u, read(fds[0], &token, 1));
1316 +#endif
1317 +
1318 +  while (!subproc->Done()) {
1319 +    subprocs_.DoWork(&tokens_);
1320 +  }
1321 +
1322 +#ifndef _WIN32
1323 +  close(fds[1]);
1324 +  close(fds[0]);
1325 +#endif
1326 +
1327 +  EXPECT_EQ(ExitSuccess, subproc->Finish());
1328 +  EXPECT_NE("", subproc->GetOutput());
1329 +
1330 +  EXPECT_EQ(1u, subprocs_.finished_.size());
1331 +}
1332 +
1333 +TEST_F(SubprocessTest, TokenNotAvailable) {
1334 +  Subprocess* subproc = subprocs_.Add(kSimpleCommand);
1335 +  ASSERT_NE((Subprocess *) 0, subproc);
1336 +
1337 +  // simulate GNUmake jobserver pipe with 0 tokens
1338 +#ifdef _WIN32
1339 +  tokens_._token_available = false;
1340 +#else
1341 +  int fds[2];
1342 +  ASSERT_EQ(0u, pipe(fds));
1343 +  tokens_._fd = fds[0];
1344 +#endif
1345 +
1346 +  subprocs_.ResetTokenAvailable();
1347 +  while (!subproc->Done()) {
1348 +    subprocs_.DoWork(&tokens_);
1349 +  }
1350 +
1351 +#ifndef _WIN32
1352 +  close(fds[1]);
1353 +  close(fds[0]);
1354 +#endif
1355 +
1356 +  EXPECT_FALSE(subprocs_.IsTokenAvailable());
1357 +  EXPECT_EQ(ExitSuccess, subproc->Finish());
1358 +  EXPECT_NE("", subproc->GetOutput());
1359 +
1360 +  EXPECT_EQ(1u, subprocs_.finished_.size());
1361 +}
1362 --- /dev/null
1363 +++ b/src/tokenpool-gnu-make-posix.cc
1364 @@ -0,0 +1,202 @@
1365 +// Copyright 2016-2018 Google Inc. All Rights Reserved.
1366 +//
1367 +// Licensed under the Apache License, Version 2.0 (the "License");
1368 +// you may not use this file except in compliance with the License.
1369 +// You may obtain a copy of the License at
1370 +//
1371 +//     http://www.apache.org/licenses/LICENSE-2.0
1372 +//
1373 +// Unless required by applicable law or agreed to in writing, software
1374 +// distributed under the License is distributed on an "AS IS" BASIS,
1375 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1376 +// See the License for the specific language governing permissions and
1377 +// limitations under the License.
1378 +
1379 +#include "tokenpool-gnu-make.h"
1380 +
1381 +#include <errno.h>
1382 +#include <fcntl.h>
1383 +#include <poll.h>
1384 +#include <unistd.h>
1385 +#include <signal.h>
1386 +#include <sys/time.h>
1387 +#include <stdio.h>
1388 +#include <string.h>
1389 +#include <stdlib.h>
1390 +
1391 +// TokenPool implementation for GNU make jobserver - POSIX implementation
1392 +// (http://make.mad-scientist.net/papers/jobserver-implementation/)
1393 +struct GNUmakeTokenPoolPosix : public GNUmakeTokenPool {
1394 +  GNUmakeTokenPoolPosix();
1395 +  virtual ~GNUmakeTokenPoolPosix();
1396 +
1397 +  virtual int GetMonitorFd();
1398 +
1399 +  virtual const char* GetEnv(const char* name) { return getenv(name); };
1400 +  virtual bool ParseAuth(const char* jobserver);
1401 +  virtual bool AcquireToken();
1402 +  virtual bool ReturnToken();
1403 +
1404 + private:
1405 +  int rfd_;
1406 +  int wfd_;
1407 +
1408 +  struct sigaction old_act_;
1409 +  bool restore_;
1410 +
1411 +  static int dup_rfd_;
1412 +  static void CloseDupRfd(int signum);
1413 +
1414 +  bool CheckFd(int fd);
1415 +  bool SetAlarmHandler();
1416 +};
1417 +
1418 +GNUmakeTokenPoolPosix::GNUmakeTokenPoolPosix() : rfd_(-1), wfd_(-1), restore_(false) {
1419 +}
1420 +
1421 +GNUmakeTokenPoolPosix::~GNUmakeTokenPoolPosix() {
1422 +  Clear();
1423 +  if (restore_)
1424 +    sigaction(SIGALRM, &old_act_, NULL);
1425 +}
1426 +
1427 +bool GNUmakeTokenPoolPosix::CheckFd(int fd) {
1428 +  if (fd < 0)
1429 +    return false;
1430 +  int ret = fcntl(fd, F_GETFD);
1431 +  if (ret < 0)
1432 +    return false;
1433 +  return true;
1434 +}
1435 +
1436 +int GNUmakeTokenPoolPosix::dup_rfd_ = -1;
1437 +
1438 +void GNUmakeTokenPoolPosix::CloseDupRfd(int signum) {
1439 +  close(dup_rfd_);
1440 +  dup_rfd_ = -1;
1441 +}
1442 +
1443 +bool GNUmakeTokenPoolPosix::SetAlarmHandler() {
1444 +  struct sigaction act;
1445 +  memset(&act, 0, sizeof(act));
1446 +  act.sa_handler = CloseDupRfd;
1447 +  if (sigaction(SIGALRM, &act, &old_act_) < 0) {
1448 +    perror("sigaction:");
1449 +    return false;
1450 +  }
1451 +  restore_ = true;
1452 +  return true;
1453 +}
1454 +
1455 +bool GNUmakeTokenPoolPosix::ParseAuth(const char* jobserver) {
1456 +  int rfd = -1;
1457 +  int wfd = -1;
1458 +  if ((sscanf(jobserver, "%*[^=]=%d,%d", &rfd, &wfd) == 2) &&
1459 +      CheckFd(rfd) &&
1460 +      CheckFd(wfd) &&
1461 +      SetAlarmHandler()) {
1462 +    rfd_ = rfd;
1463 +    wfd_ = wfd;
1464 +    return true;
1465 +  }
1466 +
1467 +  return false;
1468 +}
1469 +
1470 +bool GNUmakeTokenPoolPosix::AcquireToken() {
1471 +  // Please read
1472 +  //
1473 +  //   http://make.mad-scientist.net/papers/jobserver-implementation/
1474 +  //
1475 +  // for the reasoning behind the following code.
1476 +  //
1477 +  // Try to read one character from the pipe. Returns true on success.
1478 +  //
1479 +  // First check if read() would succeed without blocking.
1480 +#ifdef USE_PPOLL
1481 +  pollfd pollfds[] = {{rfd_, POLLIN, 0}};
1482 +  int ret = poll(pollfds, 1, 0);
1483 +#else
1484 +  fd_set set;
1485 +  struct timeval timeout = { 0, 0 };
1486 +  FD_ZERO(&set);
1487 +  FD_SET(rfd_, &set);
1488 +  int ret = select(rfd_ + 1, &set, NULL, NULL, &timeout);
1489 +#endif
1490 +  if (ret > 0) {
1491 +    // Handle potential race condition:
1492 +    //  - the above check succeeded, i.e. read() should not block
1493 +    //  - the character disappears before we call read()
1494 +    //
1495 +    // Create a duplicate of rfd_. The duplicate file descriptor dup_rfd_
1496 +    // can safely be closed by signal handlers without affecting rfd_.
1497 +    dup_rfd_ = dup(rfd_);
1498 +
1499 +    if (dup_rfd_ != -1) {
1500 +      struct sigaction act, old_act;
1501 +      int ret = 0;
1502 +
1503 +      // Temporarily replace SIGCHLD handler with our own
1504 +      memset(&act, 0, sizeof(act));
1505 +      act.sa_handler = CloseDupRfd;
1506 +      if (sigaction(SIGCHLD, &act, &old_act) == 0) {
1507 +        struct itimerval timeout;
1508 +
1509 +        // install a 100ms timeout that generates SIGALARM on expiration
1510 +        memset(&timeout, 0, sizeof(timeout));
1511 +        timeout.it_value.tv_usec = 100 * 1000; // [ms] -> [usec]
1512 +        if (setitimer(ITIMER_REAL, &timeout, NULL) == 0) {
1513 +          char buf;
1514 +
1515 +          // Now try to read() from dup_rfd_. Return values from read():
1516 +          //
1517 +          // 1. token read                               ->  1
1518 +          // 2. pipe closed                              ->  0
1519 +          // 3. alarm expires                            -> -1 (EINTR)
1520 +          // 4. child exits                              -> -1 (EINTR)
1521 +          // 5. alarm expired before entering read()     -> -1 (EBADF)
1522 +          // 6. child exited before entering read()      -> -1 (EBADF)
1523 +          // 7. child exited before handler is installed -> go to 1 - 3
1524 +          ret = read(dup_rfd_, &buf, 1);
1525 +
1526 +          // disarm timer
1527 +          memset(&timeout, 0, sizeof(timeout));
1528 +          setitimer(ITIMER_REAL, &timeout, NULL);
1529 +        }
1530 +
1531 +        sigaction(SIGCHLD, &old_act, NULL);
1532 +      }
1533 +
1534 +      CloseDupRfd(0);
1535 +
1536 +      // Case 1 from above list
1537 +      if (ret > 0)
1538 +        return true;
1539 +    }
1540 +  }
1541 +
1542 +  // read() would block, i.e. no token available,
1543 +  // cases 2-6 from above list or
1544 +  // select() / poll() / dup() / sigaction() / setitimer() failed
1545 +  return false;
1546 +}
1547 +
1548 +bool GNUmakeTokenPoolPosix::ReturnToken() {
1549 +  const char buf = '+';
1550 +  while (1) {
1551 +    int ret = write(wfd_, &buf, 1);
1552 +    if (ret > 0)
1553 +      return true;
1554 +    if ((ret != -1) || (errno != EINTR))
1555 +      return false;
1556 +    // write got interrupted - retry
1557 +  }
1558 +}
1559 +
1560 +int GNUmakeTokenPoolPosix::GetMonitorFd() {
1561 +  return rfd_;
1562 +}
1563 +
1564 +TokenPool* TokenPool::Get() {
1565 +  return new GNUmakeTokenPoolPosix;
1566 +}
1567 --- /dev/null
1568 +++ b/src/tokenpool-gnu-make-win32.cc
1569 @@ -0,0 +1,239 @@
1570 +// Copyright 2018 Google Inc. All Rights Reserved.
1571 +//
1572 +// Licensed under the Apache License, Version 2.0 (the "License");
1573 +// you may not use this file except in compliance with the License.
1574 +// You may obtain a copy of the License at
1575 +//
1576 +//     http://www.apache.org/licenses/LICENSE-2.0
1577 +//
1578 +// Unless required by applicable law or agreed to in writing, software
1579 +// distributed under the License is distributed on an "AS IS" BASIS,
1580 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1581 +// See the License for the specific language governing permissions and
1582 +// limitations under the License.
1583 +
1584 +#include "tokenpool-gnu-make.h"
1585 +
1586 +// Always include this first.
1587 +// Otherwise the other system headers don't work correctly under Win32
1588 +#include <windows.h>
1589 +
1590 +#include <ctype.h>
1591 +#include <stdlib.h>
1592 +#include <string.h>
1593 +
1594 +#include "util.h"
1595 +
1596 +// TokenPool implementation for GNU make jobserver - Win32 implementation
1597 +// (https://www.gnu.org/software/make/manual/html_node/Windows-Jobserver.html)
1598 +struct GNUmakeTokenPoolWin32 : public GNUmakeTokenPool {
1599 +  GNUmakeTokenPoolWin32();
1600 +  virtual ~GNUmakeTokenPoolWin32();
1601 +
1602 +  virtual void WaitForTokenAvailability(HANDLE ioport);
1603 +  virtual bool TokenIsAvailable(ULONG_PTR key);
1604 +
1605 +  virtual const char* GetEnv(const char* name);
1606 +  virtual bool ParseAuth(const char* jobserver);
1607 +  virtual bool AcquireToken();
1608 +  virtual bool ReturnToken();
1609 +
1610 + private:
1611 +  // Semaphore for GNU make jobserver protocol
1612 +  HANDLE semaphore_jobserver_;
1613 +  // Semaphore Child -> Parent
1614 +  // - child releases it before entering wait on jobserver semaphore
1615 +  // - parent blocks on it to know when child enters wait
1616 +  HANDLE semaphore_enter_wait_;
1617 +  // Semaphore Parent -> Child
1618 +  // - parent releases it to allow child to restart loop
1619 +  // - child blocks on it to know when to restart loop
1620 +  HANDLE semaphore_restart_;
1621 +  // set to false if child should exit loop and terminate thread
1622 +  bool running_;
1623 +  // child thread
1624 +  HANDLE child_;
1625 +  // I/O completion port from SubprocessSet
1626 +  HANDLE ioport_;
1627 +
1628 +
1629 +  DWORD SemaphoreThread();
1630 +  void ReleaseSemaphore(HANDLE semaphore);
1631 +  void WaitForObject(HANDLE object);
1632 +  static DWORD WINAPI SemaphoreThreadWrapper(LPVOID param);
1633 +  static void NoopAPCFunc(ULONG_PTR param);
1634 +};
1635 +
1636 +GNUmakeTokenPoolWin32::GNUmakeTokenPoolWin32() : semaphore_jobserver_(NULL),
1637 +                                                 semaphore_enter_wait_(NULL),
1638 +                                                 semaphore_restart_(NULL),
1639 +                                                 running_(false),
1640 +                                                 child_(NULL),
1641 +                                                 ioport_(NULL) {
1642 +}
1643 +
1644 +GNUmakeTokenPoolWin32::~GNUmakeTokenPoolWin32() {
1645 +  Clear();
1646 +  CloseHandle(semaphore_jobserver_);
1647 +  semaphore_jobserver_ = NULL;
1648 +
1649 +  if (child_) {
1650 +    // tell child thread to exit
1651 +    running_ = false;
1652 +    ReleaseSemaphore(semaphore_restart_);
1653 +
1654 +    // wait for child thread to exit
1655 +    WaitForObject(child_);
1656 +    CloseHandle(child_);
1657 +    child_ = NULL;
1658 +  }
1659 +
1660 +  if (semaphore_restart_) {
1661 +    CloseHandle(semaphore_restart_);
1662 +    semaphore_restart_ = NULL;
1663 +  }
1664 +
1665 +  if (semaphore_enter_wait_) {
1666 +    CloseHandle(semaphore_enter_wait_);
1667 +    semaphore_enter_wait_ = NULL;
1668 +  }
1669 +}
1670 +
1671 +const char* GNUmakeTokenPoolWin32::GetEnv(const char* name) {
1672 +  // getenv() does not work correctly together with tokenpool_tests.cc
1673 +  static char buffer[MAX_PATH + 1];
1674 +  if (GetEnvironmentVariable(name, buffer, sizeof(buffer)) == 0)
1675 +    return NULL;
1676 +  return buffer;
1677 +}
1678 +
1679 +bool GNUmakeTokenPoolWin32::ParseAuth(const char* jobserver) {
1680 +  // match "--jobserver-auth=gmake_semaphore_<INTEGER>..."
1681 +  const char* start = strchr(jobserver, '=');
1682 +  if (start) {
1683 +    const char* end = start;
1684 +    unsigned int len;
1685 +    char c, *auth;
1686 +
1687 +    while ((c = *++end) != '\0')
1688 +      if (!(isalnum(c) || (c == '_')))
1689 +        break;
1690 +    len = end - start; // includes string terminator in count
1691 +
1692 +    if ((len > 1) && ((auth = (char*)malloc(len)) != NULL)) {
1693 +      strncpy(auth, start + 1, len - 1);
1694 +      auth[len - 1] = '\0';
1695 +
1696 +      if ((semaphore_jobserver_ =
1697 +           OpenSemaphore(SEMAPHORE_ALL_ACCESS, /* Semaphore access setting */
1698 +                         FALSE,                /* Child processes DON'T inherit */
1699 +                         auth                  /* Semaphore name */
1700 +                        )) != NULL) {
1701 +        free(auth);
1702 +        return true;
1703 +      }
1704 +
1705 +      free(auth);
1706 +    }
1707 +  }
1708 +
1709 +  return false;
1710 +}
1711 +
1712 +bool GNUmakeTokenPoolWin32::AcquireToken() {
1713 +  return WaitForSingleObject(semaphore_jobserver_, 0) == WAIT_OBJECT_0;
1714 +}
1715 +
1716 +bool GNUmakeTokenPoolWin32::ReturnToken() {
1717 +  ReleaseSemaphore(semaphore_jobserver_);
1718 +  return true;
1719 +}
1720 +
1721 +DWORD GNUmakeTokenPoolWin32::SemaphoreThread() {
1722 +  while (running_) {
1723 +    // indicate to parent that we are entering wait
1724 +    ReleaseSemaphore(semaphore_enter_wait_);
1725 +
1726 +    // alertable wait forever on token semaphore
1727 +    if (WaitForSingleObjectEx(semaphore_jobserver_, INFINITE, TRUE) == WAIT_OBJECT_0) {
1728 +      // release token again for AcquireToken()
1729 +      ReleaseSemaphore(semaphore_jobserver_);
1730 +
1731 +      // indicate to parent on ioport that a token might be available
1732 +      if (!PostQueuedCompletionStatus(ioport_, 0, (ULONG_PTR) this, NULL))
1733 +        Win32Fatal("PostQueuedCompletionStatus");
1734 +    }
1735 +
1736 +    // wait for parent to allow loop restart
1737 +    WaitForObject(semaphore_restart_);
1738 +    // semaphore is now in nonsignaled state again for next run...
1739 +  }
1740 +
1741 +  return 0;
1742 +}
1743 +
1744 +DWORD WINAPI GNUmakeTokenPoolWin32::SemaphoreThreadWrapper(LPVOID param) {
1745 +  GNUmakeTokenPoolWin32* This = (GNUmakeTokenPoolWin32*) param;
1746 +  return This->SemaphoreThread();
1747 +}
1748 +
1749 +void GNUmakeTokenPoolWin32::NoopAPCFunc(ULONG_PTR param) {
1750 +}
1751 +
1752 +void GNUmakeTokenPoolWin32::WaitForTokenAvailability(HANDLE ioport) {
1753 +  if (child_ == NULL) {
1754 +    // first invocation
1755 +    //
1756 +    // subprocess-win32.cc uses I/O completion port (IOCP) which can't be
1757 +    // used as a waitable object. Therefore we can't use WaitMultipleObjects()
1758 +    // to wait on the IOCP and the token semaphore at the same time. Create
1759 +    // a child thread that waits on the semaphore and posts an I/O completion
1760 +    ioport_ = ioport;
1761 +
1762 +    // create both semaphores in nonsignaled state
1763 +    if ((semaphore_enter_wait_ = CreateSemaphore(NULL, 0, 1, NULL))
1764 +        == NULL)
1765 +      Win32Fatal("CreateSemaphore/enter_wait");
1766 +    if ((semaphore_restart_ = CreateSemaphore(NULL, 0, 1, NULL))
1767 +        == NULL)
1768 +      Win32Fatal("CreateSemaphore/restart");
1769 +
1770 +    // start child thread
1771 +    running_ = true;
1772 +    if ((child_ = CreateThread(NULL, 0, &SemaphoreThreadWrapper, this, 0, NULL))
1773 +        == NULL)
1774 +      Win32Fatal("CreateThread");
1775 +
1776 +  } else {
1777 +    // all further invocations - allow child thread to loop
1778 +    ReleaseSemaphore(semaphore_restart_);
1779 +  }
1780 +
1781 +  // wait for child thread to enter wait
1782 +  WaitForObject(semaphore_enter_wait_);
1783 +  // semaphore is now in nonsignaled state again for next run...
1784 +
1785 +  // now SubprocessSet::DoWork() can enter GetQueuedCompletionStatus()...
1786 +}
1787 +
1788 +bool GNUmakeTokenPoolWin32::TokenIsAvailable(ULONG_PTR key) {
1789 +  // alert child thread to break wait on token semaphore
1790 +  QueueUserAPC((PAPCFUNC)&NoopAPCFunc, child_, (ULONG_PTR)NULL);
1791 +
1792 +  // return true when GetQueuedCompletionStatus() returned our key
1793 +  return key == (ULONG_PTR) this;
1794 +}
1795 +
1796 +void GNUmakeTokenPoolWin32::ReleaseSemaphore(HANDLE semaphore) {
1797 +  if (!::ReleaseSemaphore(semaphore, 1, NULL))
1798 +    Win32Fatal("ReleaseSemaphore");
1799 +}
1800 +
1801 +void GNUmakeTokenPoolWin32::WaitForObject(HANDLE object) {
1802 +  if (WaitForSingleObject(object, INFINITE) != WAIT_OBJECT_0)
1803 +    Win32Fatal("WaitForSingleObject");
1804 +}
1805 +
1806 +TokenPool* TokenPool::Get() {
1807 +  return new GNUmakeTokenPoolWin32;
1808 +}
1809 --- /dev/null
1810 +++ b/src/tokenpool-gnu-make.cc
1811 @@ -0,0 +1,108 @@
1812 +// Copyright 2016-2018 Google Inc. All Rights Reserved.
1813 +//
1814 +// Licensed under the Apache License, Version 2.0 (the "License");
1815 +// you may not use this file except in compliance with the License.
1816 +// You may obtain a copy of the License at
1817 +//
1818 +//     http://www.apache.org/licenses/LICENSE-2.0
1819 +//
1820 +// Unless required by applicable law or agreed to in writing, software
1821 +// distributed under the License is distributed on an "AS IS" BASIS,
1822 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1823 +// See the License for the specific language governing permissions and
1824 +// limitations under the License.
1825 +
1826 +#include "tokenpool-gnu-make.h"
1827 +
1828 +#include <stdlib.h>
1829 +#include <stdio.h>
1830 +#include <string.h>
1831 +
1832 +#include "line_printer.h"
1833 +
1834 +// TokenPool implementation for GNU make jobserver - common bits
1835 +// every instance owns an implicit token -> available_ == 1
1836 +GNUmakeTokenPool::GNUmakeTokenPool() : available_(1), used_(0) {
1837 +}
1838 +
1839 +GNUmakeTokenPool::~GNUmakeTokenPool() {
1840 +}
1841 +
1842 +bool GNUmakeTokenPool::Setup(bool ignore,
1843 +                             bool verbose,
1844 +                             double& max_load_average) {
1845 +  const char* value = GetEnv("MAKEFLAGS");
1846 +  if (!value)
1847 +    return false;
1848 +
1849 +  // GNU make <= 4.1
1850 +  const char* jobserver = strstr(value, "--jobserver-fds=");
1851 +  if (!jobserver)
1852 +    // GNU make => 4.2
1853 +    jobserver = strstr(value, "--jobserver-auth=");
1854 +  if (jobserver) {
1855 +    LinePrinter printer;
1856 +
1857 +    if (ignore) {
1858 +      printer.PrintOnNewLine("ninja: warning: -jN forced on command line; ignoring GNU make jobserver.\n");
1859 +    } else {
1860 +      if (ParseAuth(jobserver)) {
1861 +        const char* l_arg = strstr(value, " -l");
1862 +        int load_limit = -1;
1863 +
1864 +        if (verbose) {
1865 +          printer.PrintOnNewLine("ninja: using GNU make jobserver.\n");
1866 +        }
1867 +
1868 +        // translate GNU make -lN to ninja -lN
1869 +        if (l_arg &&
1870 +            (sscanf(l_arg + 3, "%d ", &load_limit) == 1) &&
1871 +            (load_limit > 0)) {
1872 +          max_load_average = load_limit;
1873 +        }
1874 +
1875 +        return true;
1876 +      }
1877 +    }
1878 +  }
1879 +
1880 +  return false;
1881 +}
1882 +
1883 +bool GNUmakeTokenPool::Acquire() {
1884 +  if (available_ > 0)
1885 +    return true;
1886 +
1887 +  if (AcquireToken()) {
1888 +    // token acquired
1889 +    available_++;
1890 +    return true;
1891 +  }
1892 +
1893 +  // no token available
1894 +  return false;
1895 +}
1896 +
1897 +void GNUmakeTokenPool::Reserve() {
1898 +  available_--;
1899 +  used_++;
1900 +}
1901 +
1902 +void GNUmakeTokenPool::Return() {
1903 +  if (ReturnToken())
1904 +    available_--;
1905 +}
1906 +
1907 +void GNUmakeTokenPool::Release() {
1908 +  available_++;
1909 +  used_--;
1910 +  if (available_ > 1)
1911 +    Return();
1912 +}
1913 +
1914 +void GNUmakeTokenPool::Clear() {
1915 +  while (used_ > 0)
1916 +    Release();
1917 +  while (available_ > 1)
1918 +    Return();
1919 +}
1920 --- /dev/null
1921 +++ b/src/tokenpool-gnu-make.h
1922 @@ -0,0 +1,40 @@
1923 +// Copyright 2016-2018 Google Inc. All Rights Reserved.
1924 +//
1925 +// Licensed under the Apache License, Version 2.0 (the "License");
1926 +// you may not use this file except in compliance with the License.
1927 +// You may obtain a copy of the License at
1928 +//
1929 +//     http://www.apache.org/licenses/LICENSE-2.0
1930 +//
1931 +// Unless required by applicable law or agreed to in writing, software
1932 +// distributed under the License is distributed on an "AS IS" BASIS,
1933 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1934 +// See the License for the specific language governing permissions and
1935 +// limitations under the License.
1936 +
1937 +#include "tokenpool.h"
1938 +
1939 +// interface to GNU make token pool
1940 +struct GNUmakeTokenPool : public TokenPool {
1941 +  GNUmakeTokenPool();
1942 +  ~GNUmakeTokenPool();
1943 +
1944 +  // token pool implementation
1945 +  virtual bool Acquire();
1946 +  virtual void Reserve();
1947 +  virtual void Release();
1948 +  virtual void Clear();
1949 +  virtual bool Setup(bool ignore, bool verbose, double& max_load_average);
1950 +
1951 +  // platform specific implementation
1952 +  virtual const char* GetEnv(const char* name) = 0;
1953 +  virtual bool ParseAuth(const char* jobserver) = 0;
1954 +  virtual bool AcquireToken() = 0;
1955 +  virtual bool ReturnToken() = 0;
1956 +
1957 + private:
1958 +  int available_;
1959 +  int used_;
1960 +
1961 +  void Return();
1962 +};
1963 --- /dev/null
1964 +++ b/src/tokenpool.h
1965 @@ -0,0 +1,42 @@
1966 +// Copyright 2016-2018 Google Inc. All Rights Reserved.
1967 +//
1968 +// Licensed under the Apache License, Version 2.0 (the "License");
1969 +// you may not use this file except in compliance with the License.
1970 +// You may obtain a copy of the License at
1971 +//
1972 +//     http://www.apache.org/licenses/LICENSE-2.0
1973 +//
1974 +// Unless required by applicable law or agreed to in writing, software
1975 +// distributed under the License is distributed on an "AS IS" BASIS,
1976 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1977 +// See the License for the specific language governing permissions and
1978 +// limitations under the License.
1979 +
1980 +#ifdef _WIN32
1981 +#include <windows.h>
1982 +#endif
1983 +
1984 +// interface to token pool
1985 +struct TokenPool {
1986 +  virtual ~TokenPool() {}
1987 +
1988 +  virtual bool Acquire() = 0;
1989 +  virtual void Reserve() = 0;
1990 +  virtual void Release() = 0;
1991 +  virtual void Clear() = 0;
1992 +
1993 +  // returns false if token pool setup failed
1994 +  virtual bool Setup(bool ignore, bool verbose, double& max_load_average) = 0;
1995 +
1996 +#ifdef _WIN32
1997 +  virtual void WaitForTokenAvailability(HANDLE ioport) = 0;
1998 +  // returns true if a token has become available
1999 +  // key is result from GetQueuedCompletionStatus()
2000 +  virtual bool TokenIsAvailable(ULONG_PTR key) = 0;
2001 +#else
2002 +  virtual int GetMonitorFd() = 0;
2003 +#endif
2004 +
2005 +  // returns NULL if token pool is not available
2006 +  static TokenPool* Get();
2007 +};
2008 --- /dev/null
2009 +++ b/src/tokenpool_test.cc
2010 @@ -0,0 +1,269 @@
2011 +// Copyright 2018 Google Inc. All Rights Reserved.
2012 +//
2013 +// Licensed under the Apache License, Version 2.0 (the "License");
2014 +// you may not use this file except in compliance with the License.
2015 +// You may obtain a copy of the License at
2016 +//
2017 +//     http://www.apache.org/licenses/LICENSE-2.0
2018 +//
2019 +// Unless required by applicable law or agreed to in writing, software
2020 +// distributed under the License is distributed on an "AS IS" BASIS,
2021 +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2022 +// See the License for the specific language governing permissions and
2023 +// limitations under the License.
2024 +
2025 +#include "tokenpool.h"
2026 +
2027 +#include "test.h"
2028 +
2029 +#ifdef _WIN32
2030 +#include <windows.h>
2031 +#else
2032 +#include <unistd.h>
2033 +#endif
2034 +
2035 +#include <stdio.h>
2036 +#include <stdlib.h>
2037 +
2038 +#ifdef _WIN32
2039 +// should contain all valid characters
2040 +#define SEMAPHORE_NAME      "abcdefghijklmnopqrstwxyz01234567890_"
2041 +#define AUTH_FORMAT(tmpl)   "foo " tmpl "=%s bar"
2042 +#define ENVIRONMENT_CLEAR() SetEnvironmentVariable("MAKEFLAGS", NULL)
2043 +#define ENVIRONMENT_INIT(v) SetEnvironmentVariable("MAKEFLAGS", v)
2044 +#else
2045 +#define AUTH_FORMAT(tmpl)   "foo " tmpl "=%d,%d bar"
2046 +#define ENVIRONMENT_CLEAR() unsetenv("MAKEFLAGS")
2047 +#define ENVIRONMENT_INIT(v) setenv("MAKEFLAGS", v, true)
2048 +#endif
2049 +
2050 +namespace {
2051 +
2052 +const double kLoadAverageDefault = -1.23456789;
2053 +
2054 +struct TokenPoolTest : public testing::Test {
2055 +  double load_avg_;
2056 +  TokenPool* tokens_;
2057 +  char buf_[1024];
2058 +#ifdef _WIN32
2059 +  const char* semaphore_name_;
2060 +  HANDLE semaphore_;
2061 +#else
2062 +  int fds_[2];
2063 +#endif
2064 +
2065 +  virtual void SetUp() {
2066 +    load_avg_ = kLoadAverageDefault;
2067 +    tokens_ = NULL;
2068 +    ENVIRONMENT_CLEAR();
2069 +#ifdef _WIN32
2070 +    semaphore_name_ = SEMAPHORE_NAME;
2071 +    if ((semaphore_ = CreateSemaphore(0, 0, 2, SEMAPHORE_NAME)) == NULL)
2072 +#else
2073 +    if (pipe(fds_) < 0)
2074 +#endif
2075 +      ASSERT_TRUE(false);
2076 +  }
2077 +
2078 +  void CreatePool(const char* format, bool ignore_jobserver = false) {
2079 +    if (format) {
2080 +      sprintf(buf_, format,
2081 +#ifdef _WIN32
2082 +              semaphore_name_
2083 +#else
2084 +              fds_[0], fds_[1]
2085 +#endif
2086 +      );
2087 +      ENVIRONMENT_INIT(buf_);
2088 +    }
2089 +    if ((tokens_ = TokenPool::Get()) != NULL) {
2090 +      if (!tokens_->Setup(ignore_jobserver, false, load_avg_)) {
2091 +        delete tokens_;
2092 +        tokens_ = NULL;
2093 +      }
2094 +    }
2095 +  }
2096 +
2097 +  void CreateDefaultPool() {
2098 +    CreatePool(AUTH_FORMAT("--jobserver-auth"));
2099 +  }
2100 +
2101 +  virtual void TearDown() {
2102 +    if (tokens_)
2103 +      delete tokens_;
2104 +#ifdef _WIN32
2105 +    CloseHandle(semaphore_);
2106 +#else
2107 +    close(fds_[0]);
2108 +    close(fds_[1]);
2109 +#endif
2110 +    ENVIRONMENT_CLEAR();
2111 +  }
2112 +};
2113 +
2114 +} // anonymous namespace
2115 +
2116 +// verifies none implementation
2117 +TEST_F(TokenPoolTest, NoTokenPool) {
2118 +  CreatePool(NULL, false);
2119 +
2120 +  EXPECT_EQ(NULL, tokens_);
2121 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2122 +}
2123 +
2124 +TEST_F(TokenPoolTest, SuccessfulOldSetup) {
2125 +  // GNUmake <= 4.1
2126 +  CreatePool(AUTH_FORMAT("--jobserver-fds"));
2127 +
2128 +  EXPECT_NE(NULL, tokens_);
2129 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2130 +}
2131 +
2132 +TEST_F(TokenPoolTest, SuccessfulNewSetup) {
2133 +  // GNUmake => 4.2
2134 +  CreateDefaultPool();
2135 +
2136 +  EXPECT_NE(NULL, tokens_);
2137 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2138 +}
2139 +
2140 +TEST_F(TokenPoolTest, IgnoreWithJN) {
2141 +  CreatePool(AUTH_FORMAT("--jobserver-auth"), true);
2142 +
2143 +  EXPECT_EQ(NULL, tokens_);
2144 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2145 +}
2146 +
2147 +TEST_F(TokenPoolTest, HonorLN) {
2148 +  CreatePool(AUTH_FORMAT("-l9 --jobserver-auth"));
2149 +
2150 +  EXPECT_NE(NULL, tokens_);
2151 +  EXPECT_EQ(9.0, load_avg_);
2152 +}
2153 +
2154 +#ifdef _WIN32
2155 +TEST_F(TokenPoolTest, SemaphoreNotFound) {
2156 +  semaphore_name_ = SEMAPHORE_NAME "_foobar";
2157 +  CreateDefaultPool();
2158 +
2159 +  EXPECT_EQ(NULL, tokens_);
2160 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2161 +}
2162 +
2163 +TEST_F(TokenPoolTest, TokenIsAvailable) {
2164 +  CreateDefaultPool();
2165 +
2166 +  ASSERT_NE(NULL, tokens_);
2167 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2168 +
2169 +  EXPECT_TRUE(tokens_->TokenIsAvailable((ULONG_PTR)tokens_));
2170 +}
2171 +#else
2172 +TEST_F(TokenPoolTest, MonitorFD) {
2173 +  CreateDefaultPool();
2174 +
2175 +  ASSERT_NE(NULL, tokens_);
2176 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2177 +
2178 +  EXPECT_EQ(fds_[0], tokens_->GetMonitorFd());
2179 +}
2180 +#endif
2181 +
2182 +TEST_F(TokenPoolTest, ImplicitToken) {
2183 +  CreateDefaultPool();
2184 +
2185 +  ASSERT_NE(NULL, tokens_);
2186 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2187 +
2188 +  EXPECT_TRUE(tokens_->Acquire());
2189 +  tokens_->Reserve();
2190 +  EXPECT_FALSE(tokens_->Acquire());
2191 +  tokens_->Release();
2192 +  EXPECT_TRUE(tokens_->Acquire());
2193 +}
2194 +
2195 +TEST_F(TokenPoolTest, TwoTokens) {
2196 +  CreateDefaultPool();
2197 +
2198 +  ASSERT_NE(NULL, tokens_);
2199 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2200 +
2201 +  // implicit token
2202 +  EXPECT_TRUE(tokens_->Acquire());
2203 +  tokens_->Reserve();
2204 +  EXPECT_FALSE(tokens_->Acquire());
2205 +
2206 +  // jobserver offers 2nd token
2207 +#ifdef _WIN32
2208 +  LONG previous;
2209 +  ASSERT_TRUE(ReleaseSemaphore(semaphore_, 1, &previous));
2210 +  ASSERT_EQ(0, previous);
2211 +#else
2212 +  ASSERT_EQ(1u, write(fds_[1], "T", 1));
2213 +#endif
2214 +  EXPECT_TRUE(tokens_->Acquire());
2215 +  tokens_->Reserve();
2216 +  EXPECT_FALSE(tokens_->Acquire());
2217 +
2218 +  // release 2nd token
2219 +  tokens_->Release();
2220 +  EXPECT_TRUE(tokens_->Acquire());
2221 +
2222 +  // release implict token - must return 2nd token back to jobserver
2223 +  tokens_->Release();
2224 +  EXPECT_TRUE(tokens_->Acquire());
2225 +
2226 +  // there must be one token available
2227 +#ifdef _WIN32
2228 +  EXPECT_EQ(WAIT_OBJECT_0, WaitForSingleObject(semaphore_, 0));
2229 +  EXPECT_TRUE(ReleaseSemaphore(semaphore_, 1, &previous));
2230 +  EXPECT_EQ(0, previous);
2231 +#else
2232 +  EXPECT_EQ(1u, read(fds_[0], buf_, sizeof(buf_)));
2233 +#endif
2234 +
2235 +  // implicit token
2236 +  EXPECT_TRUE(tokens_->Acquire());
2237 +}
2238 +
2239 +TEST_F(TokenPoolTest, Clear) {
2240 +  CreateDefaultPool();
2241 +
2242 +  ASSERT_NE(NULL, tokens_);
2243 +  EXPECT_EQ(kLoadAverageDefault, load_avg_);
2244 +
2245 +  // implicit token
2246 +  EXPECT_TRUE(tokens_->Acquire());
2247 +  tokens_->Reserve();
2248 +  EXPECT_FALSE(tokens_->Acquire());
2249 +
2250 +  // jobserver offers 2nd & 3rd token
2251 +#ifdef _WIN32
2252 +  LONG previous;
2253 +  ASSERT_TRUE(ReleaseSemaphore(semaphore_, 2, &previous));
2254 +  ASSERT_EQ(0, previous);
2255 +#else
2256 +  ASSERT_EQ(2u, write(fds_[1], "TT", 2));
2257 +#endif
2258 +  EXPECT_TRUE(tokens_->Acquire());
2259 +  tokens_->Reserve();
2260 +  EXPECT_TRUE(tokens_->Acquire());
2261 +  tokens_->Reserve();
2262 +  EXPECT_FALSE(tokens_->Acquire());
2263 +
2264 +  tokens_->Clear();
2265 +  EXPECT_TRUE(tokens_->Acquire());
2266 +
2267 +  // there must be two tokens available
2268 +#ifdef _WIN32
2269 +  EXPECT_EQ(WAIT_OBJECT_0, WaitForSingleObject(semaphore_, 0));
2270 +  EXPECT_EQ(WAIT_OBJECT_0, WaitForSingleObject(semaphore_, 0));
2271 +  EXPECT_TRUE(ReleaseSemaphore(semaphore_, 2, &previous));
2272 +  EXPECT_EQ(0, previous);
2273 +#else
2274 +  EXPECT_EQ(2u, read(fds_[0], buf_, sizeof(buf_)));
2275 +#endif
2276 +
2277 +  // implicit token
2278 +  EXPECT_TRUE(tokens_->Acquire());
2279 +}