Summary:
Using the alignment bits to store the index for a packed
iterator is one of the steps toward better support of 32-bit platforms
(and pointer authentication in future platforms, such as ARMv8.3-A).
Previously this was complicated by a desire to make construction of
a packed ItemIter as cheap as possible.  The ItemPtr has a variable
number of bits available due to alignment, which may not be sufficient
to encode the index.  This diff observes that we can piggyback on the
chunk alignment to efficiently deduce the remaining bits of the index.
If sizeof(Item) gives us only 2 bits of alignment, for example, then we
can deduce 2 bits of the index from the Item*.

Differential Revision: D8452991

fbshipit-source-id: 40dfd9957da3733090bb947646c553620cc7d33d

Summary: Cleanup checks if the current thread has retired objects during bulk reclaim. It does so by flushing the thread local set of retired objects and checking if domain's list of retired objects.

Reviewed By: djwatson

Differential Revision: D8503159

fbshipit-source-id: 59ddd29d8ae1429b62b5bc9511b84e4c9e7128f2

Summary: Add shutdown indicator to domain to be checked in retire to avoid accessing thread local private list of objects at shutdown time when the thread local structure may be already destroyed.

Reviewed By: djwatson

Differential Revision: D8501530

fbshipit-source-id: 16adef34f2fd265f35851c792bd9e62a2f19b81a

Summary: As title

Reviewed By: yfeldblum

Differential Revision: D8517773

fbshipit-source-id: 971178184e446c9de476cf43f65e04f49f05e0ad

Summary: facepaw

Reviewed By: yfeldblum

Differential Revision: D8465375

fbshipit-source-id: 9cbd00286963366e8e987b7fe865ec5d334e65b3

Reviewed By: shixiao

Differential Revision: D8516223

fbshipit-source-id: 0e259ce65183d779f066869091cdea837b7bd237

Summary:
Sometimes unit tests compare the JSON output of a
component. We want a simple way to compare them semantically and also
to ignore numerical errors for double values.

Reviewed By: yfeldblum

Differential Revision: D8505209

fbshipit-source-id: 04da89889f08a595e8296716f71b9a22156e3506

Summary: [Folly] Let `window` work with functions returning `SemiFuture`.

Reviewed By: LeeHowes

Differential Revision: D8505836

fbshipit-source-id: 51c14b131760528eb6c367298cb23c4deec30ab3

Summary: [Folly] Let `makeSemiFutureWith` accept functions returning `Future`, joining what would otherwise be the resulting `SemiFuture<Future<...>>` into `SemiFuture<...>`.

Reviewed By: LeeHowes

Differential Revision: D8505834

fbshipit-source-id: 10b626fae00b5002877295b59716066f089cb6a8

Summary:
rehash's max_size check was previously relying on the optimizer
to inline and then remove a loop whose value could be determined at
compile time.  It failed to do this even in some trivial cases, wasting
about 10 nanoseconds per rehash.  This code moves the max_size check lower
(more than 6 entries) and removes the loop entirely.

Reviewed By: ot

Differential Revision: D8499582

fbshipit-source-id: 8f5c288d3922b094da81ee9261254c729e8cb1b9

Summary: exception_wrapper requires the actual exception object to be passed in for any std::exception.

Reviewed By: memorybank

Differential Revision: D8501214

fbshipit-source-id: 034a4c7df9979711dcb3740ca5c4313944f29cb6

Summary:
The `glog/logging.h` header is a bit expensive here considering its size, and how frequently `Range.h` is used.

Replace the `DCHECK_${comparison}` macro usage with macros defined in this file.

Reviewed By: yfeldblum

Differential Revision: D8473303

fbshipit-source-id: cc2a7e9eabab2c1f83a377de5191f708f1c9f317

Summary: Adjust the growth factor based on the StaticMetaBase::head_::elementsCapacity

Reviewed By: yfeldblum

Differential Revision: D8409650

fbshipit-source-id: 189b839e19a1d3f2f1ac8e4b35a2f11a4d319ad7

Summary:
- Use the hazard pointer library under folly/synchronization.
  - NodeT derived from hazptr_obj_base_linked.
  - Bucket heads are hazptr_root-s with dtor that automatically unlinks nodes
  - Provides support for uncertain removal of NodeT-s both from NodeT and Buckets
  - As intended, hazptr_cleanup reclaims all unprotected removed objects even if they have not been determined to be retirable at the start of cleanup.

Fixes the following:
- The pattern of calling h.get_protected(node->next_), when hazptr_holder h is protecting node is unsafe because try_protect (inside get_protected) may fail and we end protecting neither node nor next. This diff uses a different hazptr_holder to protect the next node. A correct pattern is to call h2.get_protected(node->next_) then h.swap(h2); h2.reset();
- The pattern of calling h2.reset(node) then h1.reset() to continue protecting a node already protected by h1 is unsafe because h2's protection may be too late after node was retired. A correct pattern is h2.swap(h1).

Reviewed By: djwatson

Differential Revision: D7708325

fbshipit-source-id: 617dcfe19410071888abafa32f0e1ada9d123983

Summary: [Folly] `bool_constant` (C++17 backport) and `index_constant`.

Reviewed By: aary

Differential Revision: D8440131

fbshipit-source-id: 2bc4fae1e2d1f404d4060c209ee325beebe2a415

Summary:
A comment to `FutureAlreadyContinued` to explain to readers in what circumstance it is thrown.

(Note: this ignores all push blocking failures!)

Reviewed By: yfeldblum

Differential Revision: D8460097

fbshipit-source-id: 49657e030efe72c026c1c3eea3612952746bb0e1

Summary: Add `explicit` to `MoveCtorOnly::MoveCtorOnly(int)` in FutureTest.cpp

Reviewed By: yfeldblum

Differential Revision: D8439496

fbshipit-source-id: 51217f186aa9b79d342a7be7f460d0a9c3f070c1

Summary:
When passing elements of a set or map through a bulk API that understands
arrays, it is a useful optimization to be able to iterator or visit
contiguous ranges rather than individual elements.  This diff adds
visitContiguousRanges to F14 maps and sets, which repeatedly passes a
contiguous range to the visitor.  The range is identified with a begin
and end value_type const*.  Each value_type of the table will be included
in exactly one of the passed ranges, and the number of ranges will be
minimized whenever possible.

Reviewed By: yfeldblum

Differential Revision: D8332897

fbshipit-source-id: a7cd5d670b14faeeef97497cccd4cb0a3b07dd50

Summary:
vshrn_n_u16 can be used to efficiently get a bit of information
from every byte in a 16-byte vector into an 8-byte vector, which is better
than the previous NEON sequence used during tag matching.  The resulting
code is faster and smaller on aarch64.  x86_64 code is refactored but
should compile to the same assembly.

Reviewed By: shixiao

Differential Revision: D8420917

fbshipit-source-id: 21a9f920f55ffc479b20fee6882a5987b626c89a

Summary: Add rvalue-qualified overloads of Future::get() and get(dur) which invalidate their this-object.

Reviewed By: yfeldblum

Differential Revision: D8242442

fbshipit-source-id: 4dea8a41878d59f6088504df2b8b3e686d581c89

Summary:
Codemod non-pointer expressions:
   - expr.get() ==> std::move(expr).get()
   - expr.get(dur) ==> std::move(expr).get(dur)
when expr is not already an xvalue.

Reviewed By: yfeldblum

Differential Revision: D8430137

fbshipit-source-id: 20da463f9cceb5cb1e71a7226f3b11d1e8007011

Summary: When hazptr_priv dtor pushes objects to the domain and that happens to trigger (either due to timed cleanup or reaching the bulk reclaim threshold) bulk reclamation that retires objects. These newly retired objects should be pushed to the domain and not into the hazptr_priv.

Reviewed By: djwatson

Differential Revision: D8410795

fbshipit-source-id: c7af01cc41a1d82896bd3700fa072f698c0aa77b

Summary: Currently the implementation just relies on futures::sleep. Ideally it should be able to use Executor's timer if available.

Reviewed By: yfeldblum

Differential Revision: D8404592

fbshipit-source-id: e952a0cc3d99bc528ea14ff5c68835d63a71e685

Summary:
[Folly] Optimize Futures Core state-dependent fields, controlling when they are constructed and destructed.

* Reduces layout size by removing the `Optional` wrapper for the result.
* Reduces code size by removing checks and destructions in assignment operators which are not in constructors for `Optional`, `Try`, `Function`, and `shared_ptr`.

Reviewed By: andriigrynenko

Differential Revision: D8346365

fbshipit-source-id: 83ac164dc36934065f2fcfb112440869d023b674

Reviewed By: aary

Differential Revision: D8393345

fbshipit-source-id: 5fc9bbfb3fa1dc63077cd406f4335c2a7967a53d

Summary:
This diff extends heterogeneous key handling (when the hasher and
key equality functor are transparent) to mutating operations.  If a key
of type K was previously eligible for heterogeneous find and key_type can
be constructed from the key, then that construction can be deferred until
after it is verified that the key is not previously in the table when
using any of the operations that may insert a new element.  If the key was
already present then this avoids the construction of key_type entirely.
Heterogeneous erase is also added in the obvious fashion.

Construction of key_type from K can be accomplished without key_type's
cooperation by the use of an explicit conversion operator, such as the
explicit operator std::string recently added to StringPiece.  That means
that a F14 map or set with std::string key and transparent StringPiece
hash and equality can now use StringPiece natively as a key.

Destructuring is applied whenever possible, so the heterogeneous key
type K may be found as the first element of a pair (for map insert or
emplace) or even inside the first tuple when using map emplace with
std::piecewise_construct.

This diff adds heterogeneous key support to

    Map::insert
    Map::insert_or_assign
    Map::emplace
    Map::try_emplace
    Map::operator[]
    Set::insert
    Set::emplace

Reviewed By: yfeldblum

Differential Revision: D8301887

fbshipit-source-id: 1a45e13739c550f094afe09123839a3c9cd892ff

Summary:
[Folly] In Futures Core, destroy context when destroying callback since they basically go together.

Also removes expectations in an Eden FS test case which affirm the old behavior, along with a TODO to remove the expectations once the affirmed behavior is fixed.

Reviewed By: marshallcline

Differential Revision: D8347040

fbshipit-source-id: ed9fec932ad1e0aa1e40675cf70081d19bbe4325

Summary:
[Folly] Use a simpler atomic state in Futures `Core` v.s. `FSM` which abstracts an atomic state plus a spin-lock.

The `FSM` abstraction can be useful in more complex cases, but is not needed in the current case. All that is needed is a single barrier state, which is `Done` - setting callback and result happen before state transitions to `Done`, while invoking callback with result happens after state transitions to `Done`.

Reviewed By: marshallcline

Differential Revision: D8083703

fbshipit-source-id: 42d96b41cbdac5e7c42f3f8a661d5db3113655db

Summary:
[Folly] Use `terminate_with` in Futures `Core` invalid transitions.

Both `Promise` and `Future` check state validity before calling the `Core` transition methods and throws in invalid state. So `Core` no longer needs to throw and may terminate instead.

Reviewed By: marshallcline

Differential Revision: D8346113

fbshipit-source-id: 9ff158673149096789b29544453262797b06d441

Summary: [Folly] `folly::terminate_with`, to terminate as if by forwarding to `folly::throw_exception` but in a `noexcept` context.

Reviewed By: marshallcline

Differential Revision: D8345962

fbshipit-source-id: bc5cf5d3a3e1f085dd2989c940a6ea753a520cbf

Summary:
[Folly] Let Future check before adding a continuation whether a continuation has already been added.

Requires making wait behave more like timed-wait; alternatively, it would be possible to add a reverse state transition, but there seems not to be a need.

Reviewed By: marshallcline

Differential Revision: D8344923

fbshipit-source-id: f077fb4b83b92c96af9a83e1b1479c4cb41b048a

Summary:
[Folly] `Range` explicit conversion to any target type, with overloads enabled only for target types which are explicitly constructible from two iterators.

Also changes `Range::to` to do similar, but permits additional arguments to be forwarded as trailing arguments to the target type constructor.

For example, this makes `std::string`, `folly::fbstring`, `std::vector<char>`, and all variants with default-constructible custom allocators, to be constructible from (but not convertible from) `folly::StringPiece`.

Reviewed By: nbronson

Differential Revision: D8386240

fbshipit-source-id: 2426191d1c8ac71cd5832f784e83bbe09b8716e7

Summary:
There were two TODOs that I knew of in fbcode about this, so I decided to file
a task so we can track it.

Reviewed By: simpkins

Differential Revision: D8176921

fbshipit-source-id: 0ca45620050639659ac038dbed43acf4634f7a1d

Summary:
Added `FutureBase::delayedImplementation`. Kept the existing semantics of
`Future::delayed` and `Future::delayedUnsafe`. `SemiFuture::delayed` uses
the inline executor which means we could execute our trivial lambda on
the `Timekeeper` thread. However we ultimately return a `SemiFuture`,
so we're not necessarily on the hook to execute an arbitrarily complex
continuation.

NOTE: This is still possible if the user explicitly specifies
`.via(inline_executor)`. Perhaps we should consider disallowing, or maybe linting for this.

Reviewed By: yfeldblum

Differential Revision: D8372515

fbshipit-source-id: e660dbf2a2bb084e11c5e57d1badacf09425f939

Summary:
To implement tdigest aggregation in scuba, we need to be able to deserialize and serialize the digests.
I added a getter for the centroids so that we can serialize the tdigest, and added a constructor to create one from the list of centroids.

Last diff was reverted because of a build error :(
We were seeing an error only in opt mode because it's an error in gcc but not in clang.

Differential Revision: D8381617

fbshipit-source-id: 768a12795aeb02737eb9b060f80d01608685c91d

Summary: title

Reviewed By: yfeldblum, andriigrynenko

Differential Revision: D8386575

fbshipit-source-id: c900c8692b10004f2d9fbd95fa8ca96b3b8517d2

Summary:
[Folly] Skip trivial-copyability `Expected` expectations under gcc49.

The focus is on gcc5+; all that is needed for now is to keep code compiling with gcc49, but not necessarily to ensure optimal trivial-copyability behavior.

Reviewed By: Orvid

Differential Revision: D8364392

fbshipit-source-id: b0062193c844509b6bf26ed632dd8e5d4bdf77d2

Summary: Assume, when UBSAN is used, it is always used on top of ASAN.

Reviewed By: luciang

Differential Revision: D8360231

fbshipit-source-id: 3106cfa53567b18f199e9303ea4c14a464ff03cc

Summary: Makes a spec for libsodium.

Reviewed By: knekritz

Differential Revision: D8228801

fbshipit-source-id: 18f623bce0bbc07f711129b15b78d56b6c852bf7

Summary: [Folly] A cache for `InlineExecutor` singleton, which can be inlined into callers with little extra code compared to calling the backing function directly.

Reviewed By: marshallcline

Differential Revision: D8339793

fbshipit-source-id: d2be0128e617cfefe66809eb44ce40e1a8ae2dfb