Summary: To estimate length of a number's base-10 length in digits, use insn `bsrq` (Bit Scan Reverse) to count significant bits.  From that, approximate base-10 length.  Tries to avoid branchiness, expensive math, and loops.

Test Plan:
1) Tested correctness by comparing results with `snprintf` and ensuring same string lengths.  Tested at each boundary condition (2^k)-1, 2^k, (2^k+1); and similar for base 10.
2) Benchmarked with gcc 4.9 and clang 3.5.

Before/after values are millions operations / sec
GCC 4.9                             Clang 3.5
1       111.09  111.7   1.005       1       115.36  393.81  3.414
2       115.36  111.7   0.968       2       115.36  393.89  3.414
3       114.91  111.34  0.969       3       111.09  393.56  3.543
4       114.91  111.34  0.969       4       111.09  393.86  3.545
5       115.36  111.36  0.965       5       111.09  392.18  3.530
6        99.99  104.32  1.043       6       103.43  393.74  3.807
7        83.31   84.71  1.017       7        81.06  268.39  3.311
8        76.9    78.23  1.017       8        76.91  268.26  3.488
9        62.48   68.26  1.093       9        65.56  190     2.898
10        59.98   63.65  1.061      10        61.17  190.54  3.115
11        50.6    55.87  1.104      11        54.54  148.03  2.714
12        47.19   51.7   1.096      12        50.84  148.57  2.922
13        40.53   46.99  1.159      13        43.33  115.91  2.675
14        40.48   43.42  1.073      14        41.5   115.97  2.794
15        34.92   40.21  1.151      15        37.27   94.89  2.546
16        33.49   37.51  1.120      16        35.77   94.88  2.653
17        29.89   35.02  1.172      17        31.7    80.67  2.545
18        29.11   32.98  1.133      18        30.76   80.63  2.621
19        26.58   31.05  1.168      19        28.22   70.15  2.486
20        25.64   29.38  1.146      20        27.96   70.16  2.509

Reviewed By: ldbrandy@fb.com

Subscribers: dancol, trunkagent, marcelo, chalfant, maoy, folly-diffs@, yzhan, yfeldblum

FB internal diff: D1934777

Signature: t1:1934777:1433523486:3acbe7ed9c9560c44194f854754529041eaa289d

Summary:
This always bothered me. Now:

1) Separate tests for each feature
2) `XTest.cpp` contains `TEST(X, lowerCaseCamelCase)`

Also cleaned up some header files and using statements.

Shamelessly trying to increase the number of lines that blame to me.

Test Plan:
Run all the tests.

`git grep 'TEST' -- 'folly/futures/test/*Test.cpp' | cut -d ',' -f 1 | cut -d '/' -f 4 | sort -u`

`diff <(git ls-files -- 'folly/futures/test/*Test.cpp' | cut -d '/' -f 4 | sort) <(git grep 'Test.cpp' -- folly/futures/TARGETS | cut -d '/' -f 4 | cut -d "'" -f 1 | sort)`

Reviewed By: jsedgwick@fb.com

Subscribers: trunkagent, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2127359

Tasks: 6019442

Signature: t1:2127359:1433459532:54a91ae83d7fb2d0b3f3769f673fefea20f35435

Summary:
This diff strengthens the preconditions for attempting to use
optimize by madvising away idle stacks, because it seemed to be causing
problems on OS X (https://github.com/facebook/proxygen/issues/3).

Test Plan: unit tests

Reviewed By: ldbrandy@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2129100

Signature: t1:2129100:1433458268:0b6b3696dde6c2bd13b89bc7ec58f0b1898be458

Summary:
`std::runtime_error` is defined in this header. Most build
systems seem to end up including it transitively anyways, but one version
of Clang on my Mac does not.

Test Plan:
`fbconfig -r folly && fbmake dbg` still works. Builds on my
Mac with MacPorts clang 3.6.

Reviewed By: ldbrandy@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2127268

Signature: t1:2127268:1433437985:546d0de71d8973d10f8ae3fdb6c61efae59444b9

Summary:
This is still manual as in the previous DEX.md revision, but I incorporated README.md into dex and redid the manual export.

Test Plan: reading_intensifies

Reviewed By: yfeldblum@fb.com

Subscribers: exa, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2124555

Tasks: 6047407

Signature: t1:2124555:1433370669:91f8bb55c1e6de4dbeccbb85556f54ae49464c7a

Summary:
`EliasFanoReader` has a copy of `EliasFanoCompressedList` as member, but it only needs few of its members. With this diff, it only copies the members it needs.
Also, `progress_` is a duplicate of `upper_.position()`, so it was removed.
Microbenchmarks do not indicate any significant change in performance.

Test Plan: unit tests

Reviewed By: philipp@fb.com

Subscribers: chaoyc, search-fbcode-diffs@, unicorn-diffs@, folly-diffs@, yfeldblum, tudort, chalfant

FB internal diff: D2125956

Signature: t1:2125956:1433381848:2a333ce7a741bec5d059e9e771309463d6018ea2

Summary:
``` lang=cpp
folly::IOBuf buf(folly::IOBuf::CLONE, other);
```

is more convenient (and expression-friendly) than

``` lang=cpp
folly::IOBuf buf;
other.cloneInto(buf);
```

Test Plan: used it

Reviewed By: davejwatson@fb.com

Subscribers: net-systems@, folly-diffs@, yfeldblum, chalfant

FB internal diff: D2124605

Signature: t1:2124605:1433372767:c167a36ffdc6d20c740aa57895532e9445766fce

Summary:
I'm pretty sure this doesn't do anything.

Based on a cursory review, I also don't think this is a bug (ie, it should have been assigned to something else).

Test Plan: fbconfig -r folly && fbmake runtests

Reviewed By: tudorb@fb.com

Subscribers: net-systems@, enis, folly-diffs@, yfeldblum, darshan, chalfant

FB internal diff: D2124497

Tasks: 7306976

Signature: t1:2124497:1433368083:1097dc22734dacad59b30d4b721be111d021bb43

Summary:

Test Plan: I copied this to a test github project and see that it renders well enough.

Reviewed By: jsedgwick@fb.com

Subscribers: exa, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2120950

Tasks: 7295194

Signature: t1:2120950:1433289846:8fbf5123e71d5594742305009fadb516206e2ba6

Summary:
Implement constructors for EliasFanoCompressedList to read a list from a contiguous byte range given either size and upper bound, or size, lower bits width, and upper bits size.

Refactor the rest accordingly.

Test Plan: unit tests

Reviewed By: philipp@fb.com

Subscribers: trunkagent, chaoyc, search-fbcode-diffs@, unicorn-diffs@, folly-diffs@, yfeldblum, tudort, chalfant

FB internal diff: D2105658

Tasks: 5474196

Signature: t1:2105658:1433270469:9948b159504e08c1b00eeb4cbe327752364ec300

Summary:
- use folly::ThreadLocal to work around GCC bug 57914 (with the benefit of accessAllThreads)
- clean up corresponding thread-local and global cache entries before eventbase gets destructed since there was a possible memory leak for short-term living eventbase.

Test Plan:
tests

Reviewed By: andrii@fb.com

Subscribers: smarlow, rushix, ilyam, trunkagent, folly-diffs@, yfeldblum, chalfant, jinfu

FB internal diff: D2116216

Tasks: 7291028, 7279391

Signature: t1:2116216:1433212893:e57a7df90b15b89ccd9471469e669c6e7dc477bf

Blame Revision: D1941662

Summary:
Seems like an unnecessary indirection that might make it harder to for
the compiler to inline everything (if that's even possible with
`std::bind`)?

Test Plan: Run all the tests.

Reviewed By: hans@fb.com

Subscribers: folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2115032

Signature: t1:2115032:1433182233:3938d0498cad50df32c8b6ee4536de14ae5fd006

Summary:
`LockFreeRingBuffer` was using `std::unique_ptr` but not importing `memory`.
Also, Android NDK's libstdc++ doesn't provide `std::llround`, use straight
`llround`, we don't need the constexpr-ness anyway.

Test Plan: `fbmake runtests`

Reviewed By: jmkaldor@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2116923

Signature: t1:2116923:1433210832:9ec0ed7f558c271a51d528b8f88fbce9b466ba3a

Summary: User reports of intermittent failures at 5.  Setting up a server is expensive.  Binding to a socket is pretty cheap.  Why not 25 tries?  Why not 100?

Test Plan: hope

Reviewed By: alandau@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2116187

Signature: t1:2116187:1433199889:09d6916eddf8521f120894ce361c3e1a96905c90

Summary:
folly: adding folly::trimWhitespace

extending the idea of folly::skipWhitespace.
the reason for adding it, we want to be able to do:

auto s = skipWhitespace(trimWhitespace(" aaaa "))

very similar to python's strip()

Test Plan:
adding unit tests:

# make ; _bin/folly/test/string_test --gtest_filter="String.whitespace"
# fbmake --ccache off --distcc off dbg -j 16
fbmake dbg -j 16
Fbmake run id: G62i4cDP42U
Note: Google Test filter = String.whitespace
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from String
[ RUN      ] String.whitespace
[       OK ] String.whitespace (0 ms)
[----------] 1 test from String (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (0 ms total)
[  PASSED  ] 1 test.

Reviewed By: ldbrandy@fb.com

Subscribers: ldbrandy, folly-diffs@, yfeldblum, chalfant, azhavnerchik

FB internal diff: D2109364

Signature: t1:2109364:1433192444:862e237bba1928fcb94be1f95c57a68d457939e9

Summary:
estimating tcp retransmission rate of the socket

Test Plan: unit tests

Reviewed By: afrind@fb.com

Subscribers: folly-diffs@, njormrod, bmatheny, trunkagent, chalfant, yfeldblum, jsedgwick

FB internal diff: D2097198

Tasks: 4888253

Signature: t1:2097198:1433196365:16db26dfd721514481497eddfc7820a453618d33

Summary:
http://libcxxabi.llvm.org/spec.html

void* __cxa_begin_catch(void* exceptionObject) throw();

```
folly/experimental/exception_tracer/ExceptionTracerLib.cpp:145:7: error: '__cxa_begin_catch' is missing exception specification 'throw()' [-Werror]
void* __cxa_begin_catch(void *excObj) {
^
throw()
folly/experimental/exception_tracer/ExceptionTracerLib.cpp:35:7: note: previous declaration is here
void* __cxa_begin_catch(void* excObj);
^
1 error generated.
11.44s error: folly/experimental/exception_tracer/ExceptionTracerLib.cpp
fbmake: *** [_build/opt/folly/experimental/exception_tracer/b187621/ExceptionTracerLib.o] Error 1
```

Test Plan: fbmake

Reviewed By: philipp@fb.com

Subscribers: folly-diffs@, yfeldblum, tudort, chalfant

FB internal diff: D2115305

Tasks: 5908365

Signature: t1:2115305:1433186210:3652d81ab10effe1be6da86705322ce090fb6cd4

Blame Revision: https://phabricator.fb.com/D2114085

Test Plan: runtests

Reviewed By: philipp@fb.com

Subscribers: folly-diffs@, jsedgwick, yfeldblum, tudort, chalfant

FB internal diff: D2114063

Signature: t1:2114063:1433111051:6686508d78de39ea4ea5dc283189c472e23f8f42

Summary:
Instead of comparing tlsExthostname_ with NULL, we are comparing it
against tlsExthostname_.

Test Plan: Automated tests

Reviewed By: afrind@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant, moa

FB internal diff: D2106257

Tasks: 4751985

Signature: t1:2106257:1432932687:78c6244392d7842e844a3c1e654ffc4dc0e760a2

Summary:
https://github.com/facebook/wangle/pull/1

Test Plan: reads better

Reviewed By: jsedgwick@fb.com

Subscribers: fugalh, exa, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2111498

Signature: t1:2111498:1432927058:1f14b38faa324d0bdef9421ae5592244a6b78928

Summary: We need to prevent the socket from being deleted while in the loopCallback.

Test Plan: --  fbconfig '--sanitize' 'address' 'folly/io/async/test' && fbmake runtests

Reviewed By: davejwatson@fb.com

Subscribers: trunkagent, folly-diffs@, yfeldblum, chalfant

FB internal diff: D2109031

Tasks: 7250307

Signature: t1:2109031:1432918801:77f0352254925d3f33f1e004c8bba89cde63e2cf

Blame Revision: D2102601

Summary: within, onTimeout, etc use the executor of the future if it is set.

Test Plan: added unittest

Reviewed By: hans@fb.com

Subscribers: doug, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2104770

Tasks: 6958727

Signature: t1:2104770:1432773599:a71c00827071bef46e5700de04c7125142e4eb17

Summary:
`TurnSequencer` uses inline assembly, which obviously won't work on ARM.
Guard said assembly to x86{,_64} targets.

Test Plan:
Added an always-false `static_assert` to the `ifdef` block, confirmed it gets
triggered (i.e., we're not removing the `pause` on x86_64).

Reviewed By: ngbronson@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2069320

Signature: t1:2069320:1431663264:3b3fb4282cf2b755f9b26c76b608b91ff665e226

Summary:
The headers that the Android NDK exports are all sorts of screwed up.
In particular, they expose a subset of the `futex.h`, so, even though the
kernel supports newer options, we can't reference them from the NDK headers.

This diff ensures Futex.cpp redefines all the things it uses, if the headers
are lacking.

It also transitions away from `SYS_` to `__NR_` which is apparently the newer
convention.

Lastly, the duration usage is made explicitly `time_t`-safe for use on 32-bit
platforms where `time_t` is `long int` but `std::chrono:seconds` is stored as
`long long int`.

Test Plan:
Existing tests, sample app compiled and ran cleanly on Android as well
(tests not verified on Android due to folly largely being unported to Android yet).

Reviewed By: ngbronson@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2069306

Signature: t1:2069306:1431721711:36c77b1afe8dd9259c1050f11a87511dcf7dd25f

Summary:
This introduces a lock-free ring buffer with the following expected semantics:

1. Writers can't block on readers
2. Writers are mostly lock-free
3. Readers can detect if they're being too slow
4. Be usable on Android (TBD but should work as-is with the armeabi-v7a ABI; armeabi (ARMv5) support is explicitly a non-goal)

Non-goals:
1. Match MPMCQueue in level of optimization. There's no need for that yet.

Test Plan: iloveunittests

Reviewed By: ngbronson@fb.com

Subscribers: trunkagent, folly-diffs@, yfeldblum, chalfant

FB internal diff: D2037718

Signature: t1:2037718:1432850250:c57963510d8cda58edc006f4c3260f5ac34d4996

Summary:
A completely mechanical transformation that moves TurnSequencer into its own
header, to be used by other collections.

Test Plan: Existing tests.

Reviewed By: jmkaldor@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2065108

Signature: t1:2065108:1431474613:a3a9d063ebd2bedb31abb37be5fd33f0fb3eca6a

Summary: Uri("foo:bar").str() would incorrectly return "foo://bar"

Test Plan: test added

Reviewed By: savasp@fb.com, markisaa@fb.com

Subscribers: folly-diffs@, yfeldblum, chalfant

FB internal diff: D2107530

Tasks: 7248055

Signature: t1:2107530:1432837143:c100f148c07b5b141cc036b1b39e6c8317e9bbd6

Summary: Chain interrupt handlers in then().  User can always choose to set a new one later.

Test Plan: added unittest

Reviewed By: hans@fb.com

Subscribers: doug, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2091569

Signature: t1:2091569:1432760579:ea7afa9b4e62e4b04b4d5f17950b9b7356a57f09

Summary:
If openssl has buffered data read from the socket, we might not get a
read event on the socket. So, we must schedule a readCallback to ensure
before exiting from AsyncSocket::handleRead if we have exhausted the
maxReadsPerEvent_ limit.

Test Plan: -- modifying existing test to test this corner case.

Reviewed By: davejwatson@fb.com

Subscribers: net-systems@, trunkagent, folly-diffs@, yfeldblum, chalfant

FB internal diff: D2102601

Tasks: 7168699

Signature: t1:2102601:1432837605:82e72a2a1875c08c9c1e8e831796c9c90df927fa

Test Plan: n/a

Reviewed By: ott@fb.com

Subscribers: ott, folly-diffs@, yfeldblum, tudort, chalfant

FB internal diff: D2100535

Tasks: 4421175

Signature: t1:2100535:1432674713:6f5f40a8462851b2b8972c68d34ae23aaf1e9340

Summary: Cleanup. Drop support for V0 in favor of V1.

Test Plan: unit tests

Reviewed By: lucian@fb.com

Subscribers: fbcode-common-diffs@, chaoyc, search-fbcode-diffs@, unicorn-diffs@, folly-diffs@, yfeldblum, tudort, chalfant

FB internal diff: D2105967

Signature: t1:2105967:1432781247:e420d8b4b8c69d28dfc229e8a2af6df8a580f979

Summary: This is actually a bug, future.cancel() doesn't work with the current THreadWheelTimekeeper, because cancel() only works from the eventBase thread.

Test Plan: added unittest.  Crashes before, passes now

Reviewed By: hans@fb.com

Subscribers: doug, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2091531

Signature: t1:2091531:1432224024:4aa5dd71de15b1344034a414d47c97ffaba68949

Summary:
I'm not sure about the name Lift now. We are lifting, yes, but are we lifting into Unit, or into "can't be void because void is unit"? But LiftIntoNonVoid is a bit verbose. I'm totally open to other names or arrangements. We could also rename `is_void_or_unit`, but to what?

I reimplemented `is_void_or_unit` in terms of `Unit::Lift` because it's kinda cool but also to provide a little motivational example to the reader for why Lift exists in the first place.

Test Plan: Still builds and passes tests. Nothing significant depends on this yet.

Reviewed By: hannesr@fb.com

Subscribers: exa, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2102147

Tasks: 6847876

Signature: t1:2102147:1432742966:a03973a45882d3e9f6fa7158ef393b148cbe16fc

Summary:
Add the option to instrument every EventHandler that runs in a
EventBase.

Test Plan:
Unit tests

Reviewed By: davejwatson@fb.com

Subscribers: alikhtarov, folly-diffs@, yfeldblum, chalfant

FB internal diff: D2044546

Tasks: 6958000

Signature: t1:2044546:1432221358:6500d6c1a6631d7a06a18e874d051f2ff3108e10

Summary: See task

Test Plan: runtests

Reviewed By: jsedgwick@fb.com

Subscribers: exa, folly-diffs@, jsedgwick, yfeldblum, chalfant

FB internal diff: D2101549

Tasks: 7225286

Signature: t1:2101549:1432688294:5fb9d7370c38c1392429a09ba48b131cac16647d

Summary: copy everything but example/

Test Plan: fbconfig -r folly/wangle && fbmake runtests

Reviewed By: hans@fb.com

Subscribers: fugalh, ps, bmatheny, folly-diffs@, jsedgwick, yfeldblum, markdrayton, chalfant

FB internal diff: D2100811

Tasks: 5802833

Signature: t1:2100811:1432678173:6c336fe53aa223993f6f82de4ac91b3c19beacf1

Summary: this preserves history and will be followed by a copy diff

Test Plan: next diff will compile

Reviewed By: hans@fb.com

Subscribers: fugalh, ps, bmatheny, folly-diffs@, jsedgwick, yfeldblum, markdrayton, chalfant

FB internal diff: D2100784

Tasks: 5802833

Signature: t1:2100784:1432677219:838a336d84918145d19c6cfa4290dd58374821fd