From b1fe65ff984c0bee2ea0dcdb4aded475b5463315 Mon Sep 17 00:00:00 2001 From: Yedidya Feldblum Date: Thu, 11 Jan 2018 13:26:45 -0800 Subject: [PATCH] MemoryIdler::futexWaitUntil Summary: [Folly] `MemoryIdler::futexWaitUntil`. Adds `MemoryIdler::futexWaitUntil` that works like `Futex::futexWaitUntil`, in a similar way that `MemoryIdler::futexWait` works like `Futex::futexWait`. Removes the ability to customize the idle-timeout clock for `MemoryIdler::futexWait` as a side-effect; the idle-timeout is now a pure duration. Now, the clock used with the idle-timeout is the same as the normal deadline clock, so the idle-timeout clock can be set for `MemoryIdler::futexWaitUntil` by providing a deadline with that clock type. This normally would not matter, but it affects the unit-tests. Reviewed By: djwatson Differential Revision: D6681679 fbshipit-source-id: e3cf6e71d7530c5877a834b318b423eb91f71eb9 --- folly/detail/MemoryIdler.h | 153 ++++++++++++++++++++++++--------- folly/test/MemoryIdlerTest.cpp | 40 ++++----- 2 files changed, 131 insertions(+), 62 deletions(-) diff --git a/folly/detail/MemoryIdler.h b/folly/detail/MemoryIdler.h index caac253e..14018f6e 100644 --- a/folly/detail/MemoryIdler.h +++ b/folly/detail/MemoryIdler.h @@ -67,74 +67,143 @@ struct MemoryIdler { /// Selects a timeout pseudo-randomly chosen to be between /// idleTimeout and idleTimeout * (1 + timeoutVariationFraction), to /// smooth out the behavior in a bursty system - template - static typename Clock::duration getVariationTimeout( - typename Clock::duration idleTimeout - = defaultIdleTimeout.load(std::memory_order_acquire), + template + static IdleTime getVariationTimeout( + IdleTime const& idleTimeout = + defaultIdleTimeout.load(std::memory_order_acquire), float timeoutVariationFrac = 0.5) { - if (idleTimeout.count() > 0 && timeoutVariationFrac > 0) { - // hash the pthread_t and the time to get the adjustment. - // Standard hash func isn't very good, so bit mix the result - auto pr = std::make_pair(getCurrentThreadID(), - Clock::now().time_since_epoch().count()); - std::hash hash_fn; - uint64_t h = folly::hash::twang_mix64(hash_fn(pr)); - - // multiplying the duration by a floating point doesn't work, grr.. - auto extraFrac = - timeoutVariationFrac / std::numeric_limits::max() * h; - auto tics = uint64_t(idleTimeout.count() * (1 + extraFrac)); - idleTimeout = typename Clock::duration(tics); + if (idleTimeout <= IdleTime::zero() || timeoutVariationFrac <= 0) { + return idleTimeout; } - return idleTimeout; + // hash the pthread_t and the time to get the adjustment + // Standard hash func isn't very good, so bit mix the result + uint64_t h = folly::hash::twang_mix64(folly::hash::hash_combine( + getCurrentThreadID(), + std::chrono::system_clock::now().time_since_epoch().count())); + + // multiplying the duration by a floating point doesn't work, grr + auto extraFrac = + timeoutVariationFrac / std::numeric_limits::max() * h; + auto tics = uint64_t(idleTimeout.count() * (1 + extraFrac)); + return IdleTime(tics); } /// Equivalent to fut.futexWait(expected, waitMask), but calls /// flushLocalMallocCaches() and unmapUnusedStack(stackToRetain) - /// after idleTimeout has passed (if it has passed). Internally uses - /// fut.futexWait and fut.futexWaitUntil. Like futexWait, returns - /// false if interrupted with a signal. The actual timeout will be + /// after idleTimeout has passed (if it has passed). Internally uses + /// fut.futexWait and fut.futexWaitUntil. The actual timeout will be /// pseudo-randomly chosen to be between idleTimeout and idleTimeout * /// (1 + timeoutVariationFraction), to smooth out the behavior in a - /// system with bursty requests. The default is to wait up to 50% - /// extra, so on average 25% extra + /// system with bursty requests. The default is to wait up to 50% + /// extra, so on average 25% extra. template < template class Atom, - typename Clock = std::chrono::steady_clock> + typename IdleTime = std::chrono::steady_clock::duration> static FutexResult futexWait( Futex& fut, uint32_t expected, uint32_t waitMask = -1, - typename Clock::duration idleTimeout = + IdleTime const& idleTimeout = + defaultIdleTimeout.load(std::memory_order_acquire), + size_t stackToRetain = kDefaultStackToRetain, + float timeoutVariationFrac = 0.5) { + FutexResult pre; + if (futexWaitPreIdle( + pre, + fut, + expected, + std::chrono::steady_clock::time_point::max(), + waitMask, + idleTimeout, + stackToRetain, + timeoutVariationFrac)) { + return pre; + } + return fut.futexWait(expected, waitMask); + } + + /// Equivalent to fut.futexWaitUntil(expected, deadline, waitMask), but + /// calls flushLocalMallocCaches() and unmapUnusedStack(stackToRetain) + /// after idleTimeout has passed (if it has passed). Internally uses + /// fut.futexWaitUntil. The actual timeout will be pseudo-randomly + /// chosen to be between idleTimeout and idleTimeout * + /// (1 + timeoutVariationFraction), to smooth out the behavior in a + /// system with bursty requests. The default is to wait up to 50% + /// extra, so on average 25% extra. + template < + template class Atom, + typename Deadline, + typename IdleTime = std::chrono::steady_clock::duration> + static FutexResult futexWaitUntil( + Futex& fut, + uint32_t expected, + Deadline const& deadline, + uint32_t waitMask = -1, + IdleTime const& idleTimeout = defaultIdleTimeout.load(std::memory_order_acquire), size_t stackToRetain = kDefaultStackToRetain, float timeoutVariationFrac = 0.5) { - if (idleTimeout == Clock::duration::max()) { - // no need to use futexWaitUntil if no timeout is possible - return fut.futexWait(expected, waitMask); + FutexResult pre; + if (futexWaitPreIdle( + pre, + fut, + expected, + deadline, + waitMask, + idleTimeout, + stackToRetain, + timeoutVariationFrac)) { + return pre; } + return fut.futexWaitUntil(expected, deadline, waitMask); + } - idleTimeout = getVariationTimeout(idleTimeout, timeoutVariationFrac); - if (idleTimeout.count() > 0) { - while (true) { - auto rv = fut.futexWaitUntil( - expected, Clock::now() + idleTimeout, waitMask); - if (rv == FutexResult::TIMEDOUT) { - // timeout is over - break; + private: + template < + template class Atom, + typename Deadline, + typename IdleTime> + static bool futexWaitPreIdle( + FutexResult& _ret, + Futex& fut, + uint32_t expected, + Deadline const& deadline, + uint32_t waitMask, + IdleTime idleTimeout, + size_t stackToRetain, + float timeoutVariationFrac) { + // idleTimeout < 0 means no flush behavior + if (idleTimeout < IdleTime::zero()) { + return false; + } + + // idleTimeout == 0 means flush immediately, without variation + // idleTimeout > 0 means flush after delay, with variation + if (idleTimeout > IdleTime::zero()) { + idleTimeout = std::max( + IdleTime::zero(), + getVariationTimeout(idleTimeout, timeoutVariationFrac)); + } + if (idleTimeout > IdleTime::zero()) { + auto idleDeadline = Deadline::clock::now() + idleTimeout; + if (idleDeadline < deadline) { + while (true) { + auto rv = fut.futexWaitUntil(expected, idleDeadline, waitMask); + if (rv == FutexResult::TIMEDOUT) { + break; + } + // finished before timeout hit, no flush + _ret = rv; + return true; } - // finished before timeout hit, no flush - assert(rv == FutexResult::VALUE_CHANGED || rv == FutexResult::AWOKEN || - rv == FutexResult::INTERRUPTED); - return rv; } } - // flush, then wait with no timeout + // flush, then wait flushLocalMallocCaches(); unmapUnusedStack(stackToRetain); - return fut.futexWait(expected, waitMask); + return false; } }; diff --git a/folly/test/MemoryIdlerTest.cpp b/folly/test/MemoryIdlerTest.cpp index 6945f22e..d23be515 100644 --- a/folly/test/MemoryIdlerTest.cpp +++ b/folly/test/MemoryIdlerTest.cpp @@ -64,10 +64,10 @@ struct MockAtom : public std::atomic { /// extending its scope beyond that of the test. I generally avoid /// shared_ptr, but a weak_ptr is just the ticket here struct MockClock { - typedef std::chrono::steady_clock::duration duration; - typedef std::chrono::steady_clock::time_point time_point; + using duration = std::chrono::steady_clock::duration; + using time_point = std::chrono::time_point; - MOCK_METHOD0(nowImpl, time_point(void)); + MOCK_METHOD0(nowImpl, time_point()); /// Hold on to the returned shared_ptr until the end of the test static std::shared_ptr> setup() { @@ -103,6 +103,8 @@ struct Futex { } // namespace detail } // namespace folly +static auto const forever = MockClock::time_point::max(); + TEST(MemoryIdler, futexWaitValueChangedEarly) { StrictMock> fut; auto clock = MockClock::setup(); @@ -115,8 +117,7 @@ TEST(MemoryIdler, futexWaitValueChangedEarly) { Lt(begin + 2 * idleTimeout)), -1)) .WillOnce(Return(FutexResult::VALUE_CHANGED)); EXPECT_EQ( - FutexResult::VALUE_CHANGED, - (MemoryIdler::futexWait(fut, 1))); + FutexResult::VALUE_CHANGED, MemoryIdler::futexWaitUntil(fut, 1, forever)); } TEST(MemoryIdler, futexWaitValueChangedLate) { @@ -130,11 +131,10 @@ TEST(MemoryIdler, futexWaitValueChangedLate) { EXPECT_CALL(fut, futexWaitUntil(1, AllOf(Ge(begin + idleTimeout), Lt(begin + 2 * idleTimeout)), -1)) .WillOnce(Return(FutexResult::TIMEDOUT)); - EXPECT_CALL(fut, futexWait(1, -1)) + EXPECT_CALL(fut, futexWaitUntil(1, forever, -1)) .WillOnce(Return(FutexResult::VALUE_CHANGED)); EXPECT_EQ( - FutexResult::VALUE_CHANGED, - (MemoryIdler::futexWait(fut, 1))); + FutexResult::VALUE_CHANGED, MemoryIdler::futexWaitUntil(fut, 1, forever)); } TEST(MemoryIdler, futexWaitAwokenEarly) { @@ -147,9 +147,7 @@ TEST(MemoryIdler, futexWaitAwokenEarly) { .WillOnce(Return(begin)); EXPECT_CALL(fut, futexWaitUntil(1, Ge(begin + idleTimeout), -1)) .WillOnce(Return(FutexResult::AWOKEN)); - EXPECT_EQ( - FutexResult::AWOKEN, - (MemoryIdler::futexWait(fut, 1))); + EXPECT_EQ(FutexResult::AWOKEN, MemoryIdler::futexWaitUntil(fut, 1, forever)); } TEST(MemoryIdler, futexWaitAwokenLate) { @@ -162,31 +160,33 @@ TEST(MemoryIdler, futexWaitAwokenLate) { .WillOnce(Return(begin)); EXPECT_CALL(fut, futexWaitUntil(1, begin + idleTimeout, -1)) .WillOnce(Return(FutexResult::TIMEDOUT)); - EXPECT_CALL(fut, futexWait(1, -1)).WillOnce(Return(FutexResult::AWOKEN)); + EXPECT_CALL(fut, futexWaitUntil(1, forever, -1)) + .WillOnce(Return(FutexResult::AWOKEN)); EXPECT_EQ( FutexResult::AWOKEN, - (MemoryIdler::futexWait( - fut, 1, -1, idleTimeout, 100, 0.0f))); + MemoryIdler::futexWaitUntil(fut, 1, forever, -1, idleTimeout, 100, 0.0f)); } TEST(MemoryIdler, futexWaitImmediateFlush) { StrictMock> fut; auto clock = MockClock::setup(); - EXPECT_CALL(fut, futexWait(2, 0xff)).WillOnce(Return(FutexResult::AWOKEN)); + EXPECT_CALL(fut, futexWaitUntil(2, forever, 0xff)) + .WillOnce(Return(FutexResult::AWOKEN)); EXPECT_EQ( FutexResult::AWOKEN, - (MemoryIdler::futexWait( - fut, 2, 0xff, std::chrono::seconds(0)))); + MemoryIdler::futexWaitUntil( + fut, 2, forever, 0xff, std::chrono::seconds(0))); } TEST(MemoryIdler, futexWaitNeverFlush) { StrictMock> fut; auto clock = MockClock::setup(); - EXPECT_CALL(fut, futexWait(1, -1)).WillOnce(Return(FutexResult::AWOKEN)); + EXPECT_CALL(fut, futexWaitUntil(1, forever, -1)) + .WillOnce(Return(FutexResult::AWOKEN)); EXPECT_EQ( FutexResult::AWOKEN, - (MemoryIdler::futexWait( - fut, 1, -1, MockClock::duration::max()))); + MemoryIdler::futexWaitUntil( + fut, 1, forever, -1, std::chrono::seconds(-7))); } -- 2.34.1