Summary:
Benchmark each type with its native key type and with its non-native key type.
This allows you to make a more-informed decision about which to use based on
the types you have available at insertion/lookup time.

Reviewed By: yfeldblum

Differential Revision: D4826527

fbshipit-source-id: ee4ef5255d2bdd955e9deb30dc4c28be183cee07

IndexedMemPool: Fix race condition on size_ that can cause the destructor to access nonexistent slots

Summary:
Contention on allocation when there is exactly one slot remaining can cause size_ to exceed actualCapacity_.
Without taking the min of size_ and actualCapacity_ the destructor may try to destroy out-of-bound slots.

Added a test to test/IndexedMemPoolTest.cpp that failed before the fix and passes after the fix.

Reviewed By: nbronson

Differential Revision: D4837251

fbshipit-source-id: a887487727f17eaf2ba66345f40fc91d2fe3bc00

Summary: There's a comment in that code that states that it *it* noexcept, and that is common for most folly async io callbacks.

Reviewed By: yfeldblum

Differential Revision: D4831800

fbshipit-source-id: 78894ad72504b9dfe540c14b8d7bbb29247aaf87

Summary:
Add trimAtMost start and trimAtMost end.
These are useful functions to have if you
don't care about trimming an exact amount.

Reviewed By: yfeldblum

Differential Revision: D4658087

fbshipit-source-id: f7dd62c0f4837503e59cdec75fdad433be20306c

Summary:
Implementing `clearenv()` correctly on multiple OS's without relying on underlying implementation details is significantly more complicated, and this is preventing being able to build on OSX.
This function isn't actually used anywhere currently.

Reviewed By: yfeldblum

Differential Revision: D4832473

fbshipit-source-id: a80aabb5a223264746ab45e3138d065bce5fe99c

Summary: fixing D4825412

Reviewed By: lbrandy

Differential Revision: D4826815

fbshipit-source-id: 94691ff293dad53b16e7a2f139c1df490a61e565

Summary: GMock can't mock class methods that are not virtual. This way classes relying on the non-virtual methods of AsyncSocket can't be efficiently tested using gtest/gmock.

Reviewed By: yfeldblum

Differential Revision: D4806838

fbshipit-source-id: fde852b75f7ac1d468c177e317c516cb0dc333b5

Summary:
We recently removed declarations of Function constructors and
assignment operators that took non-const Function references. They
were necessary at the time to make sure that the templated
constructor that can take any invokable object did not get
selected for copying Functions from non-const lvalues. This,
however, is now provided by some std::enable_if construct.

Reviewed By: ericniebler

Differential Revision: D4818736

fbshipit-source-id: 08197721beef009f6ae482b576df78ec6999d132

Summary:
More work to get wangle compiling. wangle/facebook/http pulls in
proxygen libs and that's another pain altogether, so this only makes the rest of
wangle build with 1.1.0 and BoringSSL

Depends on D4406876

Reviewed By: ngoyal

Differential Revision: D4767060

fbshipit-source-id: bd6bc6959d04028c84360e434f6bbdb2cde2faac

Summary: Add more layers to support compiling with OpenSSL 1.1.0

Reviewed By: yfeldblum

Differential Revision: D4406876

fbshipit-source-id: 8eff7e4f8e096605fc9e1093ef533b5afe0ee539

Summary: This is same as D4249032, but for now this is only enabled in dbg and dev builds. I'm planning to bump this to FATAL later, once we fix know problematic main()s.

Reviewed By: lbrandy, yfeldblum

Differential Revision: D4821763

fbshipit-source-id: 5f7930f8cbcb10275d23a89848f1ec8ee34a8020

Summary:
The use of generic lambdas caused compiler errors with gcc 4.8.2.
Fixes https://github.com/facebook/folly/issues/569.

Reviewed By: Orvid, yfeldblum

Differential Revision: D4821115

fbshipit-source-id: 8372ee7695a3d0a1df0d033623618a923c261737

Summary:
The priority queue in the manual executor implementation is backwards. This means that scheduled things run in reverse order, and a later thing will block an earlier thing if you advance to a timestamp in between the two.

This diff fixes the problem and adds tests to confirm the fix. These tests fail on the old implementation.

Reviewed By: yfeldblum

Differential Revision: D4739101

fbshipit-source-id: 6e429828460df5b3c656580568a9ae1eb4009527

Summary: Macros are not the best solution anymore.

Reviewed By: yfeldblum

Differential Revision: D4270626

fbshipit-source-id: 8acbd5b778d4effcfb587655b4397737bef0d379

Remove/make private the default ***Holder constructor to allow compile time detection of ***Holder(mutexPtr_) constructs

Summary: Avoid unintended C++ stuff - this is not the same as the "fleeting rvalue" - this change might break the build but I will fix it

Reviewed By: yfeldblum

Differential Revision: D4814104

fbshipit-source-id: 058a0eac44893c573062fcf5665d4fd022ee64a0

Summary:
A (almost) lock-free atomic_shared_ptr, matching the proposed concurrency TS interface.

See notes at top of file

Reviewed By: davidtgoldblatt

Differential Revision: D4716098

fbshipit-source-id: b9ca2443ba9e227ebb6f40807128073c6e14222a

Summary:
`escapeString` is very slow even when there's very little to nothing to escape. This diff adds a fast path to copy sequences of bytes that don't need escaping.
It also optimizes appending escape sequences: `string::push_back` is slow because it has to do a capacity check for every character.

Before:
```
  ============================================================================
  folly/test/JsonOtherTest.cpp                    relative  time/iter  iters/s
  ============================================================================
  jsonSerialize                                              818.55ns    1.22M
  jsonSerializeWithNonAsciiEncoding                            1.35us  738.06K
  jsonSerializeWithUtf8Validation                              1.42us  705.60K
  jsonSerializeAsciiWithUtf8Validation                         3.27us  306.06K
  parseSmallStringWithUtf                                      1.91us  522.38K
  parseNormalString                                            1.51us  660.27K
  parseBigString                                             384.44ns    2.60M
  toJson                                                     480.54ns    2.08M
  ============================================================================
```

After:
```
  ============================================================================
  folly/test/JsonOtherTest.cpp                    relative  time/iter  iters/s
  ============================================================================
  jsonSerialize                                              781.69ns    1.28M
  jsonSerializeWithNonAsciiEncoding                          847.68ns    1.18M
  jsonSerializeWithUtf8Validation                            928.68ns    1.08M
  jsonSerializeAsciiWithUtf8Validation                       199.85ns    5.00M
  parseSmallStringWithUtf                                      1.93us  518.39K
  parseNormalString                                            1.45us  689.11K
  parseBigString                                             378.66ns    2.64M
  toJson                                                     446.38ns    2.24M
  ============================================================================
```

All string escaping benchmarks are slightly faster, and ASCII-only with no escapes is 8x faster.

Reviewed By: luciang, evilmucedin, yfeldblum

Differential Revision: D4793233

fbshipit-source-id: c40d07708bd787799c8c00f9f23a417b862ee9ae

Summary: Infinite retries is something that is often needed for read-modify-write like workflows. The current implementation was creating a nested chain of implicit promises. This manifests as a memory leak after some time. Worse yet, even if it succeeds, it will take a long time to churn thru the chain of promises.

Reviewed By: yfeldblum

Differential Revision: D4770335

fbshipit-source-id: 44b8d6df1084de4514b66919a9838cf2322d6dce

Summary:
ubsan flags this problem:

```
buck-out/opt-ubsan/gen/folly/__default_headers__#header-mode-symlink-tree-with-header-map,headers/folly/experimental/StringKeyedCommon.h:31:18: runtime error: null pointer passed as argument 2, which is declared to never be null
third-party-buck/gcc-4.9-glibc-2.20-fb/build/glibc/include/string.h:47:28: note: nonnull attribute specified here
    #0 0x5cb88f in std::pair<std::__detail::_Node_iterator<std::pair<folly::Range<char const*> const, facebook::eden::GitIgnore>, false, true>, bool> folly::StringKeyedUnorderedMap<facebook::eden::GitIgnore, folly::Hash, std::equal_to<folly::Range<char const*> >, std::allocator<std::pair<folly::Range<char const*> const, facebook::eden::GitIgnore> > >::emplace<facebook::eden::GitIgnore>(folly::Range<char const*>, facebook::eden::GitIgnore&&) buck-out/opt-ubsan/gen/folly/__default_headers__#header-mode-symlink-tree-with-header-map,headers/folly/experimental/StringKeyedCommon.h:31
    #1 0x5c6652 in facebook::eden::(anonymous namespace)::IgnoreChecker::isIgnored(facebook::eden::detail::RelativePathBase<folly::Range<char const*> >) eden/fs/inodes/Dirstate.cpp:226
    #2 0x5c6037 in facebook::eden::(anonymous namespace)::IgnoreChecker::isIgnored(facebook::eden::detail::RelativePathBase<folly::Range<char const*> >) eden/fs/inodes/Dirstate.cpp:180
    #3 0x5c5173 in facebook::eden::Dirstate::getStatusForExistingDirectory(facebook::eden::detail::RelativePathBase<folly::Range<char const*> >) const eden/fs/inodes/Dirstate.cpp:372
    #4 0x5c4509 in facebook::eden::Dirstate::getStatus() const eden/fs/inodes/Dirstate.cpp:272
    #5 0x50a448 in verifyExpectedDirstate(facebook::eden::Dirstate const*, std::unordered_map<std::basic_fbstring<char, std::char_traits<char>, std::allocator<char>, std::fbstring_core<char> >, facebook::eden::StatusCode, std::hash<std::basic_fbstring<char, std::char_traits<char>, std::allocator<char>, std::fbstring_core<char> > >, std::equal_to<std::basic_fbstring<char, std::char_traits<char>, std::allocator<char>, std::fbstring_core<char> > >, std::allocator<std::pair<std::basic_fbstring<char, std::char_traits<char>, std::allocator<char>, std::fbstring_core<char> > const, facebook::eden::StatusCode> > >&&) eden/fs/inodes/test/DirstateTest.cpp:48
    #6 0x50c70c in Dirstate_addDirectoriesWithMixOfFiles_Test::TestBody() eden/fs/inodes/test/DirstateTest.cpp:220
    #7 0xb45857 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:2364
    #8 0xb36784 in testing::Test::Run() /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:2437
    #9 0xb36957 in testing::TestInfo::Run() [clone .part.558] /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:2612
    #10 0xb36b74 in testing::TestCase::Run() [clone .part.559] /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:2587
    #11 0xb3806e in testing::internal::UnitTestImpl::RunAllTests() [clone .part.561] /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:4571
    #12 0xb382d9 in testing::UnitTest::Run() /home/engshare/third-party2/gtest/1.7.0/src/gtest-1.7.0/./src/gtest.cc:4519
    #13 0x861ca7 in main third-party-buck/gcc-4.9-glibc-2.20-fb/build/gtest/include/gtest/gtest.h:2326
    #14 0x7f20be0740f5 in __libc_start_main /home/engshare/third-party2/glibc/2.20/src/glibc-2.20/csu/libc-start.c:289
    #15 0x4a552c in _start /home/engshare/third-party2/glibc/2.20/src/glibc-2.20/csu/../sysdeps/x86_64/start.S:122

UndefinedBehaviorSanitizer: undefined-behavior buck-out/opt-ubsan/gen/folly/__default_headers__#header-mode-symlink-tree-with-header-map,headers/folly/experimental/StringKeyedCommon.h:31:18
```

The issue is that `StringPiece` default constructs to `{nullptr, nullptr}` as a valid representation of an empty string.
This is tripping up UBSAN in this case.

The fix is a trivial nullptr check

Reviewed By: igorsugak

Differential Revision: D4791015

fbshipit-source-id: dec7484b29ecb29c17b8dd6a9b0e8093f07d63cb

Summary:
[Folly] Some constexpr symbols for whether sanitizers are enabled.

Useful where we need to do or not do some particular thing when sanitizers are enabled or disabled. Such cases do happen. It is better to use a C++ `constexpr` symbol rather than a preprocessor symbol in such cases, where possible.

Reviewed By: meyering

Differential Revision: D4805110

fbshipit-source-id: ca9ce074edef73dce3a04693dda102698c9cd29f

Summary:
[Folly] Fix double-`delete` in `Singleton::make_mock`.

In that function, we unconditionally destroy any existing singleton instance of the same singleton. Actually, we must conditionally destroy it - conditionally on one having been created and not yet destroyed.

This problem only rarely appears because it is masked by `delete static_cast<T*>(nullptr)` being a no-op. For example, if we call `make_mock` before actually instantiating the singleton, we call that no-op. The way to make it appear is to instantiate the singleton, and then to call `make_mock` twice in a row. The first call to `make_mock` unconditionally destroys the existing instance (it still should have checked) and the second call does it again, but because the existing instance is not `nullptr`, the second call is a double-delete of a non-`nullptr` instance and crashes. In the simple case, as reproduced in an attached test, the failure is observable with ASAN. In other cases, the double-`free` is tolerated, but the failure may only be observable depending on the singleton object's state - if running the dtor twice fails.

Reviewed By: ivmaykov

Differential Revision: D4798163

fbshipit-source-id: e7b65d030d89225dfdc2fad4c778d3653460806e

Summary: Self-moves are exceedingly rare and need not preserve the state of the object. They must only leave the object in a valid but unspecified state. By removing the branch, we make the common case (non-self move) faster.

Reviewed By: spacedentist, ot

Differential Revision: D4803486

fbshipit-source-id: 3ef2e1e13cd08d9221ecb154bfb3338b16487717

Properly constrain folly::Function's generic conversion constructor and fix its noexcept specification

Summary:
The generic conversion constructor for `folly::Function` was not checking that the source object could successfully be copy/move constructed, leading to some `is_constructible` false positives.

Also, the `noexcept` specification on the `Function` constructor wasn't taking into account that the source object might be copied into the Function, instead of moved. The copy could throw.

Reviewed By: yfeldblum

Differential Revision: D4775037

fbshipit-source-id: f337b41bf9ac431baa9457a501e63c18ca099e57

Summary: Useful for the same reason as the `get_ptr()` path function, but when you want to use a default value.

Reviewed By: luciang, yfeldblum

Differential Revision: D4785728

fbshipit-source-id: 70fd56f9ffa7a9edd6740f6dd712d3a251bf9fb0

Summary:
https://our.intern.facebook.com/intern/sevmanager/view/s/145809/?hc_location=ufi

```
hg backout d4e3fdfd57750c8dcabdb4c01ab3b528c4818624
```

Reviewed By: lbrandy

Differential Revision: D4799568

fbshipit-source-id: 76366040702e68becc7e245d7ce15832f933e10e

Summary: Extending ApplyTuple to support this common functional construct, with good forwarding semantics.

Reviewed By: yfeldblum

Differential Revision: D4787560

fbshipit-source-id: 2c740e448e0cb916abe948b79709d5ecd8ba54bb

Summary:
[Folly] Cut extraneous typename in `StringKeyedCommon.h`.

In this case, `typename` is optional, and, to avoid confusion, should be removed.

"In this case" means in a template definition, with a qualified non-dependent name.

Reviewed By: ericniebler

Differential Revision: D4792087

fbshipit-source-id: dbb9d2c747432a1f9bc8823e72a7668e78a2fbaa

Summary:
This diff adds two tests to futures/test/ViaTest.cpp:
viaDummyExecutorFutureSetValueFirst and
viaDummyExecutorFutureSetCallbackFirst. The latter resulted in a
dead-lock before the fix contained in this diff.

It is important that the callback function is destroyed after
it is executed, since it may capture objects (like a Promise)
that should be destroyed (so that e.g. a corresponding Future
throws BrokenPromise). When the callback is executed via an
executor, it is possible that the executor doesn't get around to
executing the task. We shouldn't rely on the task being executed
to do necessary clean-up. That clean-up should (also) happen
when the task (with its captured data) is destroyed (in the
spirit of RIAA).

Reviewed By: djwatson

Differential Revision: D4779215

fbshipit-source-id: d029cf8b8f7b55e1b03357749c5fb62d95986ca7

Summary:
Add codec that does automatic format detection for decompression.
The codec returned by `getCodec(CodecType::AUTOMATIC)` can decompress codecs `LZ4_FRAME`, `ZSTD`, `ZLIB`, `GZIP`, and `LZMA2`.
Additionally, the function `getAutomaticCodec()` allows users to pass their own custom codecs, but the 5 default codecs must also be supported.
We force the default codecs on users because having a common subset of formats is in general useful, and because we want to be able to add codecs to this set.

When compiled in debug mode, on construction it checks that the codecs are compatible.
This helps make sure that users don't accidentally add ambiguous codecs, and if we add a new default codec in the future, tests will fail on ambiguity.

Reviewed By: yfeldblum

Differential Revision: D4760065

fbshipit-source-id: 9e65844aba9f1ae3d5c7b86643931782c06ab3eb

Summary:
If the compiler doesn't see thru the call to tryRead which always initializes the val variable, it will emit the following error.
I was getting error when compiling my android project:
error: 'val' may be used uninitialized in this function [-Werror=maybe-uninitialized]
This should not have a negative perf impact as smart compilers which inline call to tryRead can elliminate the initialization.

Reviewed By: djwatson

Differential Revision: D4790864

fbshipit-source-id: f353cfe54ca4d056b6ddfc075d00580c9f2d391e

Summary:
`ZlibCodec::doUncompress()` always allocates at least 4 MiB when the uncompressed size is unkown.
We can get a 10-20% speed boost for small inputs (as well as significant memory savings) if we dynamically choose the buffer size.

Benchmarks before the change:
  ============================================================================
  experimental/terrelln/CompressionBenchmark.cpp  relative  time/iter  iters/s
  ============================================================================
  uncompress(ZLIB_100)                                         2.96us  338.19K
  uncompress(ZLIB_1000)                                        7.22us  138.44K
  uncompress(ZLIB_10000)                                      36.86us   27.13K
  uncompress(ZLIB_100000)                                    299.70us    3.34K
  uncompress(ZLIB_1000000)                                     2.74ms   365.32
  uncompress(ZLIB_10000000)                                   26.91ms    37.16
  uncompress(ZLIB_100000000)                                 273.92ms     3.65
  ============================================================================
After:
  ============================================================================
  experimental/terrelln/CompressionBenchmark.cpp  relative  time/iter  iters/s
  ============================================================================
  uncompress(ZLIB_100)                                         2.34us  426.68K
  uncompress(ZLIB_1000)                                        6.24us  160.38K
  uncompress(ZLIB_10000)                                      35.52us   28.16K
  uncompress(ZLIB_100000)                                    296.30us    3.37K
  uncompress(ZLIB_1000000)                                     2.74ms   365.25
  uncompress(ZLIB_10000000)                                   27.16ms    36.82
  uncompress(ZLIB_100000000)                                 273.72ms     3.65
  ============================================================================

Reviewed By: yfeldblum

Differential Revision: D4783871

fbshipit-source-id: 0fcce191ea520fd2117551db679c86f5ff734893

Summary: It's needed downstream in HHVM.

Reviewed By: yfeldblum

Differential Revision: D4785204

fbshipit-source-id: fe81ed8e23497fffeb44b2a366c457b788bcaada

Reviewed By: yfeldblum

Differential Revision: D4782707

fbshipit-source-id: 535b42b4f2558cadc78037268d6de81a8bb49840

Summary: In some situations it is useful to be able to sort the JSON keys according to some different scheme for readability, so allow the sorting function to be changed by the serializer_opts

Reviewed By: yfeldblum

Differential Revision: D4782077

fbshipit-source-id: 032fa60a38804452bd1c22c67ba897521cb2cd1d

Summary:
D4715918 broke open source builds on Ubuntu 14.04, since it has lz4-r114, but the lz4 frame API was introduced in [r123](https://github.com/lz4/lz4/blob/r123/lz4frame.h).
Put the `LZ4FrameCodec` behind a lz4 version check.
Fixes https://github.com/facebook/fbthrift/issues/209.

Reviewed By: yfeldblum

Differential Revision: D4780830

fbshipit-source-id: 19492a7e6bdd128e610c36b5778274e19eff9548

Summary: Passing a temporary default value to `get_ref_default()` returns a dangling reference when it is used.

Reviewed By: lbrandy, yfeldblum

Differential Revision: D4768769

fbshipit-source-id: 4c58a17dc7662ad553cf88a8544dae20016d2f6f

Summary:
Fix a correctness bug in "SWMRList.h".

Thanks to Maged for the tip! The old code omitted setting a removed node's
"next" pointer to `nullptr`, which meant that if the writer removed node
A and then node B = A->next while the reader was looking at B, then the reader
might happily keep chasing pointers B->next, B->next->next,... without ever
noticing that it was now on a "dead branch" of the linked list.

(And then there's a bit of a trick: you really do have to remove the node
first and *then* set its "next" pointer to null, because if you do the null
assignment first, you'll truncate the list, which means that some readers
will see a truncated list and return the wrong answer. I've added comments
to try to explain this to future-me.)

Style nit: Avoid doing multiple atomic operations on the same line of code.

----

Modernize the parameter-passing conventions in SWMRList.h.

Pass `T`s by const reference, except in `add` where we're likely to want to
make a copy of the `T` anyway. In that case it would be more "STL-correct"
to supply two different overloads `add(T&&)` and `add(const T&)`, but this
is just an example so it makes sense to keep things simple.

----

Fix an undefined behavior in SWMRList example.

Searching an empty SWMRList<int> always invokes undefined behavior by
comparing an uninitialized `T elem` against `val` on the final line of
the `contains` function. Besides, this patch allows SWMRList to work
with `T`s that aren't default-constructible or even copy-constructible.

----

Closes https://github.com/facebook/folly/pull/566

Reviewed By: djwatson

Differential Revision: D4772359

Pulled By: yfeldblum

fbshipit-source-id: 8f96573530800675cb56006aa91e7a5c5c1fb85d

Summary:
Two changes:
- Add a lock holder interface to enable users to move exclusive access and implicitly release the held lock.
- Change an assert to a static_assert to check at compile time if a provided function fits in the Function structure without dynamic allocation.

Reviewed By: djwatson

Differential Revision: D4770229

fbshipit-source-id: 89408164c08d7660231a6ca4e37637dd688356cd

Summary:
Add a `tryRead()`, and endian variants, which try to read into an arithmetic type, and if there isn't enough data they return false.
One use case is to quickly check if an IOBuf starts with a certain prefix, benchmarks show that using `tryReadLE()` is 6x faster than using `pullAtMost()` and `memcmp()`.

Reviewed By: yfeldblum

Differential Revision: D4767855

fbshipit-source-id: feb8c61092772933d4b8496b27d464559ff8b827

Summary: `get_ref_default()` won't accept temporary default values after D4768769.

Reviewed By: yfeldblum

Differential Revision: D4769043

fbshipit-source-id: 46b039e13b80721922f69036c6cc02f5642a26f9