tools/ninja/patches/100-make_jobserver_support.patch

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