• R/O
  • HTTP
  • SSH
  • HTTPS

immortalwrt: Commit

Mirror only - Please move to https://github.com/immortalwrt/immortalwrt


Commit MetaInfo

Revisionf1ede256882b80cb997f499de61906d46b00e83b (tree)
Zeit2022-05-18 13:09:29
AutorFelix Fietkau <nbd@nbd....>
CommiterTianling Shen

Log Message

build: add ninja build tool and make it available for cmake

ninja is faster at building cmake packages than make, and according to reports
also more reliable at handling parallel builds
This commit includes a patch that adds GNU make jobserver support, in order to
allow more precise control over the number of parallel tasks

Enable parallel build by default for packages using ninja

Signed-off-by: Felix Fietkau <nbd@nbd.name>
Signed-off-by: Rosen Penev <rosenp@gmail.com>
(cherry picked from commit 97258f53634d7237a2962aec3387f011047ce83b)

Ändern Zusammenfassung

Diff

--- a/include/cmake.mk
+++ b/include/cmake.mk
@@ -1,5 +1,11 @@
11 cmake_bool = $(patsubst %,-D%:BOOL=$(if $($(1)),ON,OFF),$(2))
22
3+ifeq ($(PKG_USE_NINJA),1)
4+ PKG_BUILD_PARALLEL ?= 1
5+endif
6+ifeq ($(HOST_USE_NINJA),1)
7+ HOST_BUILD_PARALLEL ?= 1
8+endif
39 PKG_INSTALL:=1
410
511 ifneq ($(findstring c,$(OPENWRT_VERBOSE)),)
@@ -44,6 +50,34 @@ CMAKE_FIND_ROOT_PATH:=$(STAGING_DIR)/usr;$(TOOLCHAIN_DIR)$(if $(CONFIG_EXTERNAL_
4450 CMAKE_HOST_FIND_ROOT_PATH:=$(STAGING_DIR)/host;$(STAGING_DIR_HOSTPKG);$(STAGING_DIR_HOST)
4551 CMAKE_SHARED_LDFLAGS:=-Wl,-Bsymbolic-functions
4652
53+ifeq ($(HOST_USE_NINJA),1)
54+ CMAKE_HOST_OPTIONS += -DCMAKE_GENERATOR="Ninja"
55+
56+ define Host/Compile/Default
57+ +$(NINJA) -C $(HOST_BUILD_DIR) $(1)
58+ endef
59+
60+ define Host/Install/Default
61+ +DESTDIR="$(HOST_INSTALL_DIR)" $(NINJA) -C $(HOST_BUILD_DIR) install
62+ endef
63+
64+ define Host/Uninstall/Default
65+ +DESTDIR="$(HOST_INSTALL_DIR)" $(NINJA) -C $(HOST_BUILD_DIR) uninstall
66+ endef
67+endif
68+
69+ifeq ($(PKG_USE_NINJA),1)
70+ CMAKE_OPTIONS += -DCMAKE_GENERATOR="Ninja"
71+
72+ define Build/Compile/Default
73+ +$(NINJA) -C $(CMAKE_BINARY_DIR) $(1)
74+ endef
75+
76+ define Build/Install/Default
77+ +DESTDIR="$(PKG_INSTALL_DIR)" $(NINJA) -C $(CMAKE_BINARY_DIR) install
78+ endef
79+endif
80+
4781 define Build/Configure/Default
4882 mkdir -p $(CMAKE_BINARY_DIR)
4983 (cd $(CMAKE_BINARY_DIR); \
--- a/rules.mk
+++ b/rules.mk
@@ -339,6 +339,12 @@ else
339339 $(SCRIPT_DIR)/rstrip.sh
340340 endif
341341
342+NINJA = \
343+ MAKEFLAGS="$(MAKE_JOBSERVER)" \
344+ $(STAGING_DIR_HOST)/bin/ninja \
345+ $(if $(findstring c,$(OPENWRT_VERBOSE)),-v) \
346+ $(if $(MAKE_JOBSERVER),,-j1)
347+
342348 ifeq ($(CONFIG_IPV6),y)
343349 DISABLE_IPV6:=
344350 else
--- a/tools/Makefile
+++ b/tools/Makefile
@@ -24,7 +24,7 @@ endif
2424 tools-y += autoconf autoconf-archive automake bc bison cmake dosfstools
2525 tools-y += e2fsprogs fakeroot findutils firmware-utils flex gengetopt
2626 tools-y += libressl libtool lzma m4 make-ext4fs missing-macros mkimage
27-tools-y += mklibs mm-macros mtd-utils mtools padjffs2 patch-image
27+tools-y += mklibs mm-macros mtd-utils mtools ninja padjffs2 patch-image
2828 tools-y += patchelf pkgconf quilt squashfskit4 sstrip xxd zip zlib zstd
2929 tools-$(BUILD_B43_TOOLS) += b43-tools
3030 tools-$(BUILD_ISL) += isl
--- /dev/null
+++ b/tools/ninja/Makefile
@@ -0,0 +1,39 @@
1+include $(TOPDIR)/rules.mk
2+
3+PKG_NAME:=ninja
4+PKG_VERSION:=1.10.2
5+PKG_RELEASE:=1
6+
7+PKG_SOURCE:=$(PKG_NAME)-$(PKG_VERSION).tar.gz
8+PKG_SOURCE_URL:=https://codeload.github.com/ninja-build/ninja/tar.gz/v$(PKG_VERSION)?
9+PKG_HASH:=ce35865411f0490368a8fc383f29071de6690cbadc27704734978221f25e2bed
10+
11+include $(INCLUDE_DIR)/host-build.mk
12+
13+CONFIGURE_ARGS:=
14+ifneq ($(findstring c,$(OPENWRT_VERBOSE)),)
15+ CONFIGURE_ARGS+=--verbose
16+endif
17+
18+define Host/Configure
19+endef
20+
21+define Host/Compile
22+ cd $(HOST_BUILD_DIR) && \
23+ CXX="$(HOSTCXX)" \
24+ CXXFLAGS="$(HOST_CXXFLAGS) $(HOST_CPPFLAGS)" \
25+ LDFLAGS="$(HOST_LDFLAGS)" \
26+ $(STAGING_DIR_HOST)/bin/$(PYTHON) configure.py --bootstrap $(CONFIGURE_ARGS)
27+endef
28+
29+define Host/Install
30+ $(INSTALL_DIR) $(STAGING_DIR_HOST)/bin
31+ $(INSTALL_BIN) $(HOST_BUILD_DIR)/ninja $(STAGING_DIR_HOST)/bin/
32+endef
33+
34+define Host/Clean
35+ $(call Host/Clean/Default)
36+ rm -f $(STAGING_DIR_HOST)/bin/ninja
37+endef
38+
39+$(eval $(call HostBuild))
--- /dev/null
+++ b/tools/ninja/patches/100-make_jobserver_support.patch
@@ -0,0 +1,2279 @@
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++}
Show on old repository browser