Harden failure signal handler in the face of memory corruptions

Summary:
@mhorowitz got

*** Aborted at 1393267847 (Unix time, try 'date -d @1393267847') ***
*** Signal 11 (SIGSEGV) (0x0) received by PID 12652 (TID 0x7f59cbfff700), stack trace: ***
pure virtual method called
terminate called without an active exception
Entered fatal signal handler recursively. We're in trouble.

in a test, and no stack trace.

The first time we enter recursively (ie. the second time overall), try to dump
without symbolization. The next time, give up.

Test Plan: folly/experimental/symbolizer/test, ran crash with a modified dumpStackTrace to force it to enter recursively

Reviewed By: lucian@fb.com

FB internal diff: D1187942

Random number generator utilities for folly

Summary:
In looking at how people were using common/base/Random, I noticed
a number of issues with our current usage of random number generators

1) People would simply declare a RandomInt32 without seeding it. This
results in a predictable seed
2) We initialize a Mersenne Twister RNG from a single int32. This
causes us to have a more predictable starting sequence of numbers
3) People aren't consistently using thread-local RNGs
4) Many of the APIs lack consistency. For example random32 takes a
max parameter that is exclusive while uniformRandom32 uses inclusive
boundries

I'm hoping a better API can fix this. thread_prng implements the Generator
concept with result_type = int32. It isn't actually a random number generator,
but it uses a thread local to point to a real generator. An advantage
of this is that it can be used in existing APIs but that it doesn't expose
the implementation of the RNG via the header file. One thing that's a bit
weird about it is that if you copy the object across threads it could
cause an error.

The Random class provides utilities that take any type of random number
generator. This has the advantage of allowing the user to pass a RNG
meant for testing or a secure RNG based on /dev/random. Another advnatage
is if you're woried about the performance of TLS lookups, you can
cache a local thread_prng which memoizes the TLS lookup.

If available, we use a SIMD optimized MT API

Some open questions:

1) What functions should be in random
2) Should the default RNG be a 64 or 32 bit based RNG

Test Plan: Benchmark runs

Reviewed By: simpkins@fb.com

FB internal diff: D1181864

Fix clang folly::to failure

Summary:
Converting an enum class to a string fails with clang.
Adfinder clang build failure is http://ci-fbcode.fb.com:8080/builders/project/builds/146520/steps/build/logs/stdio
Our version of clang supports std::underlying_type so use that implementation instead.

Test Plan:
fbconfig -r folly && fbmake runtests (only failure is folly/experimental/symbolizer/test:symbolizer_test which failed before this diff)
fbconfig --clang folly/test:conv_test && fbmake runtests (fbconfig -r --clang folly fails and fbconfig --clang folly/test && fbmake has some unrelated compile errors)
Build adfinder with clang

Reviewed By: delong.j@fb.com

FB internal diff: D1178770

Fix FBString's new includes

Summary:
The headers <ext/hash*> were being included but not used when
_LIBSTDCXX_FBSTRING is defined. They have been relocated to within the
appropiate header block.

Test Plan:
fbconfig -r folly && fbmake runtests_opt

copy FBString and Malloc into libgcc, then
tp2_build libgcc/4.8.1/gcc-4.8.1-glibc-2.17-fb

Reviewed By: pgriess@fb.com

FB internal diff: D1187345

Remove disallowed &* of FwdIterator

Summary:
Iterators are not required to dereference into lvalues, so
taking the address of the dereferenced value of a general iterator
may cause a compile-time error.

This bug was observed when compiling clang-3.4. Clang uses a custom
iterator type when calling fbstring::replace, whose dereference operator
returns a char (instead of the 'expected' const char&).

FBString takes the address of the dereference in order to test if the
iterator is actually an iterator referencing its own data. This protects
the string from data trampling in certain cases. See the added test case
for an example.

For sequence containers, the standard specifies that supplying interal
iterators for such operations is forbidden. The standard also states
that the iterators passed into containers will be dereferenced at each
location exactly once. The standard (from by too-brief inspection) does
not specify either of these restrictions for strings, which I find odd.

As a compromise between safety and strict compliance, the offending code
is now only run when the iterator type is either fbstring::iterator or
fbstring::const_iterator. In these cases, we know that it is safe to
both dereference the iterator multiple times and to take its
dereference's address.

While fixing this error, I noticed that fbstring::replaceImpl was
public. It is now private.

Test Plan:
Added a new test case to FBStringTest.cpp.

fbconfig -r folly && fbmake opt && fbmake runtests_opt

Reviewed By: delong.j@fb.com

FB internal diff: D1185655

Try again to fix hash<fbstring> namespacing

Summary:
- Unfortunately when D1152140 broke the Android build, which uses the
Bionic C++ standard library, and which Boost doesn't auto-detect. Deal
with this by manually picking namespaces for template specialization
based on #defines.

Test Plan:
- fbconfig -r folly/ unicorn/utils/ && fbmake runtests
- Build Liger on iOS and Android

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1154569

Blame Revision: D1152140

Part 2: Crontab selector

Summary: See docblock in CrontabSelector.h.

Test Plan: unit test

Reviewed By: agoder@fb.com

FB internal diff: D1181803

Better support for folly::Range with non-const iterators underneath

Summary:
Implicitly construct Range<To> from Range<From> if From is implicitly
convertible to To.

Explicitly construct Range<To> from Range<From> if To is (explicitly)
constructible from From.

Add special-cases for Range<char*>, Range<unsigned char*> similar to the
ones for Range<const char*>, Range<const unsigned char*>.

Test Plan: test added

Reviewed By: philipp@fb.com

FB internal diff: D1182999

Part 1: Local time label <=> UTC timestamp conversion

Summary: See the block comment in date_time_utils.h -- the actual Cron code comes in later diffs.

Test Plan: unit tests

Reviewed By: agoder@fb.com

FB internal diff: D1181554

allow folly Cursor to read and write floats

Summary: and doubles!

Test Plan: none really, will test later for now it compiles

Reviewed By: tudorb@fb.com

FB internal diff: D1175021

Make IOBuf support 64-bit length and capacity

Summary:
Remove type_ (unused), pack flags in least significant bits of sharedInfo_.
sizeof(IOBuf) remains 56 bytes.

Test Plan: folly/io/test with -opt and -dbg; iobuf*_test with asan as well.

Reviewed By: simpkins@fb.com

FB internal diff: D1179993

add clone() of stack allocated memory for folly::Cursor and folly::IOBuf

Summary: as title

Test Plan: fbconfig folly/io/test/ && fbmake runtests

Reviewed By: simpkins@fb.com

FB internal diff: D1176922

Use standard variadic macros instead of gcc-specific ones

Summary: We've intentionally eliminated support for gcc's old variadic macro syntax so as to bring our close in line with compatbile standards. This diff enables folly to build using warp.

Test Plan: built folly

Reviewed By: delong.j@fb.com

FB internal diff: D1176956

Use #if rather than #ifdef for FOLLY_HAVE_WEAK_SYMBOLS

Summary:
- We need to be able to disable FOLLY_HAVE_WEAK_SYMBOLS via
-DFOLLY_HAVE_WEAK_SYMBOLS=0. Switch the #ifdef checks to #if.

Test Plan:
- fbconfig -r folly && fbmake runtests
- Build in fbobjc

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1150036

folly: avoid false-positive ASAN-abort from SignalHandlerTest

Summary:
Without this change, the sig-handling test's deliberate
invalid access would trigger an ASAN-abort, which differed
from the expected SEGV.  Skip this test when ASAN is enabled.
* folly/experimental/symbolizer/test/SignalHandlerTest.cpp: Include
CPortability.h for definion of FOLLY_SANITIZE_ADDRESS.
(SignalHandler) [FOLLY_SANITIZE_ADDRESS]: Provide a different
regexp to match the first line of output from an ASAN-enabled binary.

Test Plan:
fbconfig --sanitize=address --platform-all=gcc-4.8.1-glibc-2.17 \
folly/experimental/symbolizer/test:signal_handler_test \
&& fbmake --fast runtests \
&& fbmake --fast runtests_opt

Sample output, before this change: https://phabricator.fb.com/P5428975
(search down to first AddressSanitizer abort.
With this change, expect that test to pass.

Reviewed By: lucian@fb.com

FB internal diff: D1164768

Removing redirects

Test Plan: contbuild

Reviewed By: philipp@fb.com

FB internal diff: D1164211

<Thrift perftest> folly: modify Histogram const, add substract

Summary:
This diff is a split from D1157286 for folly part;
adds a substract function which substracts a histogram data from another;
modifies some of the const specifiers in the Histogram class.

Test Plan: tested on the thrift perftest by adding x-th percentile latency stats

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1158270

Fix OS X compilation

Summary: Fix OS X compilation

Test Plan: compiled on OS X

Reviewed By: delong.j@fb.com

FB internal diff: D1163199

folly: ASAN-exempt scanHaystackBlock, to avoid an FP buffer overrun

Summary:
scanHaystackBlock may read-overrun the needle.data() buffer by
up to 15 bytes, but that overrun will never cross a page boundary.
The fix is to turn off ASAN-checking for this function, but since
that attribute is accompanied by a "noinline" one (which conflicts
with the function's own "inline"), I have also removed the "inline"
attribute on both decl and defn.  That is a good thing, regardless:
these days, there are very few cases in which we should be trying to
tell the compiler to inline.

Test Plan:
Before, this would elicit an ASAN abort.  Now it passes 100%:

fbconfig --platform-all=gcc-4.8.1-glibc-2.17 --sanitize=address \
folly/test:range_test && fbmake runtests

Reviewed By: philipp@fb.com

FB internal diff: D1162982

Cache open ELF files in Symbolizer

Summary:
Rather than opening and closing Elf files every time we symbolize them, we open
the first time and cache.

We're using two caches: one for the signal handler (fixed size, slow, but
async-signal-safe) and one for exception tracing and general use.

Also, unrelated, removed two useless frames from the stack trace dump in the
signal handler.

Test Plan: tests added

Reviewed By: lucian@fb.com

FB internal diff: D1161444

fix missing change from D1156950

Test Plan: fbconfig -r folly/experimental/test:eliasfano_test && fbmake runtests_opt

Reviewed By: lucian@fb.com

FB internal diff: D1161670

Codemod following promotion

Summary:
Changing all the include paths following D1151911.
Depends on D1151911

Test Plan: contbuild

Reviewed By: ldbrandy@fb.com

FB internal diff: D1159003

Facebook:
Contbuild is mostly passed, remaining failures are unrelated. I'm confident other failures are unrelated.
@override-unit-failures

Promoting out of experimental

Summary:
At long last, promoting this out of experimental. Also, while I'm at
it, I've separated the tests and benchmarks into their corresponding parts.

Redirect headers provided.

Test Plan: Unit tests, contbuild.

Reviewed By: marcelo.juchem@fb.com

FB internal diff: D1151911

raise error when parsing object with NaN or INF to JSON

Summary:
NaN or INF is not allowed according to JSON specification.
This will cause problems when other places try to encode the output
of toJson with NaN or INF.
raise error when parsing object with NaN or INF to JSON.

Test Plan: manually test, raise error for object w/ NaN

Reviewed By: delong.j@fb.com

FB internal diff: D1143853

Replace CHECK_GT with DCHECK_GT in folly::Range::operator[]

Summary: Since I don't want to pay the cost when we access array elements. If I did, I would just use Java.

Test Plan: fbconfig folly/test/ && fbmake runtests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1158505

Fix rare corruption in StaticMeta::head_ list around fork

Summary:
In a rare case, the current thread's would be inserted in the StaticMeta linked
list twice, causing the list to be corrupted, leading to code spinning forever.

After a fork, in the child, only the current thread survives, so all other threads
must be forcefully removed from StaticMeta. We do that by clearing the list
and re-adding the current thread, but we didn't check whether the current thread
was already there. It is possible for the current thread to not be in the list
if it never used any ThreadLocalPtr objects with the same tag.

Now, when the thread in the child tries to use a ThreadLocalPtr with the same
tag, it adds itself to the list (##if (prevCapacity == 0)
meta.push_back(threadEntry)##), but it had already been added by the post-fork
handler, boom.

Fix by adding the necessary check in onForkChild.

Test Plan: @durham's test case, also added new test for this

Reviewed By: delong.j@fb.com

FB internal diff: D1158672

@override-unit-failures

Baton - flushing of thread-local memory during a long wait

Summary:
This diff causes Baton to reduce a thread's memory footprint when it
blocks for an extended period (by default 5 to 7.5 seconds).  Reductions
are achieved by flushing the thread-local jemalloc caches (if jemalloc
is in use) and by calling madvise(MADV_DONTNEED) on the portion of the
thread's stack that isn't active.  Once the thread resumes execution
both of these resources will be reallocated.  Configuration is via
system-wide default.

Test Plan:
1. new unit tests
2. manual execution of existing unit tests with very low idleTimeout
3. peek and poke with gdb to observe madvise discarding the page

Reviewed By: davejwatson@fb.com

FB internal diff: D1146966

FB_LOG_EVERY_MS should use wall time instead of cpu time

Summary:
FB_LOG_EVERY_MS was using clock() as its source of time, which
measures the elapsed CPU time of the process.  The name and the docs
suggest that wall time was intended, so that's what this diff does.

Test Plan: new unit test

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1157926

tune EF coding

Summary:
Change the way forward / skip pointers are encoded, so we can
expect that `uint32_t` will be enough to address ~4B elements instead
of ~2B as it is now.

Test Plan:
Ran benchmarks for both versions, saw no significant
difference.

Added tests.

Reviewed By: lucian@fb.com

FB internal diff: D1156950

Specialize hash<basic_fbstring> in correct namespaces

Summary:
- Use the BOOST_STD_EXTENSION_NAMESPACE macro to pick the namespace to
use for hash specializations

Test Plan:
- fbconfig -r unicorn/utils/ && fbmake opt
- fbconfig -r folly && fbmake runtests
- Build in fbobjc with libc++
@override-unit-failures

Reviewed By: rajatr@fb.com

FB internal diff: D1153422

Blame Revision: D1152140

add additional formatChecked() and vformatChecked() wrappers

Summary:
Add wrapper functions for directly appending to a string, similar to the
existing format() and vformat() wrappers.

Test Plan:
Converted some existing code using these format() and vformat() wrappers
to use formatChecked() and vformatChecked().

Reviewed By: jon.coens@fb.com

FB internal diff: D1151496

@override-unit-failures

Use C++11 unordered collections instead of libstdc++ extensions

Summary:
- The fbobjc builds complain about use of deprecated <ext/hash_set> and
friends, and then fail because of -Werror. Just use the C++ standard
collections.

Test Plan:
- fbconfig -r folly && fbmake runtests
- Build for iOS and Android
@override-unit-failures

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1152140

Update folly-config.h for iOS/Apple

Summary: - Update the pre-computed folly-config.h file for Apple builds

Test Plan:
- fbconfig -r folly && fbmake runtests
- Build in fbobjc

Reviewed By: delong.j@fb.com

FB internal diff: D1150188

Copyright 2013 -> 2014

Summary: ...and stop lint complaining at everyone.

@override-unit-failures

Test Plan: Inspection. Build folly.

Reviewed By: delong.j@fb.com

FB internal diff: D1151216

Use libc++ equivalent of std::__ostream_insert()

Summary:
- In libstdc++, existing code uses the internal std::__ostream_insert()
method to write a formatted string that can include '\0' characters.
This internal method doesn't exist in libc++. Instead, use the
relevant internal bits.

Test Plan:
- fbconfig -r folly && fbmake runtests
- ./configure && make check on Mac OS X

Reviewed By: njormrod@fb.com

FB internal diff: D1108540

Change paramter name to FB_STRINGIZE

Summary:
- The fbobjc codebase defines this macro as well, and to the same thing.
However, Clang complains on macro redefinitions if paramater names are
different, even if the macros expand to the same thing. Normalize the
Folly version to 'x', which is what fbobjc uses.

Test Plan:
- fbconfig -r folly && fbmake runtests
- Builds in fbobjc

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1149985

split_step - tokenization make simple in folly::Range

Summary: this is a simple method that allows a folly::Range `[b, e)` to be split on a character at position `i` (where b <= i < e) in an incremental manner.
@override-unit-failures

Test Plan: unit tests added

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1145631

Handle platforms where off_t is not convertible to size_t

Summary:
- On iOS, off_t is an int64_t, and as such std::min() doesn't compile
since the types don't match. Normalize to size_t and fail with an
error if this conversion can't be made

Test Plan:
- fbconfig -r folly && fbmake runtests
- Built on iOS

Reviewed By: tudorb@fb.com

FB internal diff: D1142795

folly: File explicit ctor

Summary: explicit ctor

Test Plan: contbuild

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1134033

Blame Revision: D1133938

add formatChecked(), which does not crash on bad format strings

Summary:
This restore's format()'s behavior of crashing on invalid format
strings, and adds an alternative formatChecked() function to throw
instead of crashing.

Format strings are commonly programmer defined, and fixed at compile
time.  Bad format strings are usually programmer errors, and crashing is
desirable to help catch these bugs early.

However, it is also useful to support dynamic format strings which are
not guaranteed to be well formed at compile time.  formatChecked() makes
it safe to use dynamic format strings, as a bad format strings will not
crash the program.

This does change the throwing/crashing behavior slightly: the old
format() code also used to crash if the format string referred to a
non-existent key in one of the argument containers.  I removed this,
since it seems like the argument containers are likely to be dynamic.

I also changed the code to crash on std::range_errors as well.  Various
problems in format string arguments are caught in the Conv.h code, which
throws range_errors.  The old crashing code did not crash on these
errors, but it seems useful to do so.  The only minor concern here is
that this may also crash unintentionally if the Output callback throws a
range_error.  This seems low-risk, but we can remove this behavior if
needed.

Test Plan:
Updated the BogusFormatString test to check both format() and
formatChecked().

Reviewed By: tudorb@fb.com

FB internal diff: D1144301

revert format()'s behavior of crashing on error

Summary:
This reverts 61e20daa, which changed the format code to abort on error.

I do plan to restore the crashing behavior, but I plan to make it
optional.  I will add a formatSafe() function that throws on error,
while format() catches these exceptions and crashes.

This diff is an intermediate diff to make it easier to review the
changes.  This is close to a straight revert of 61e20daa and 61a41c9b.
However, I did leave the new test case, as well as the
FormatArg::errorStr() method added by those diffs.

Test Plan:
Verified that the existing format tests pass.

Also added a handful of new tests for bad format strings.  This did
catch one bug in the code where it wasn't correctly checking for a null
return value from memchr().

Reviewed By: delong.j@fb.com

FB internal diff: D1144298

bug fix when rallocm fails

Summary:
rallocm sets the value of the second argument even if it has failed to allocate the requested size:
https://github.com/jemalloc/jemalloc/blob/898960247a8b2e6534738b7a3a244855f379faf9/src/jemalloc.c#L1903-L1906

As a result newAllocatedCapacity was being set to a value less than the original value and the logic was broken.

Test Plan: unit tests pass and my code which was crashing before now works!

Reviewed By: soren@fb.com

FB internal diff: D1144314

CHECK EliasFanoCompressedList::encode input is sorted

Test Plan: fbconfig -r folly/experimental/test && fbmake runtests_opt

Reviewed By: chaoyc@fb.com

FB internal diff: D1141124

Add benchmark functions to the checksum unit tests

Summary:
* Added benchmark functions to the checksum unit tests
* While in the code, fixed the order of the arguments to
the EXPECT_EQ statements so the tests will report the
actual and expected values properly upon error

Test Plan:
fbconfig -r folly && fbmake opt
_build/opt/folly/test/checksum_test --benchmark

Reviewed By: rajat@fb.com

FB internal diff: D1134930

Removed duplicate #includes

Summary:
Removed duplicate #includes.

Facebook: The removals were examined by hand: several duplicate includes
were not removed because they were/seemed to
be in different preprocessor branches of the source.

@override-unit-failures

Test Plan: arc unit

Reviewed By: robbert@fb.com

FB internal diff: D1136491

Enable the __builtin_ia32_crc* acceleration functions for gcc-4.7

Summary:
Adjusted the ifdefs to allow the use of the hardware CRC instructions
when compiling with gcc-4.7.x

Test Plan:
Built with gcc-4.7.1, ran the unit tests, verified that they ran the
hardware-accelerated code path

Reviewed By: saramg@fb.com

FB internal diff: D1134567

Remove byLine(const char*) method

Summary:
Many callers of byLine method use it by providing arguments for File
explicit constructors. Added function breaks byLine(file desciptor)
use case. Commenting it out until File constructors are made exlicit to
fix failing tests.

Test Plan: unittest

Reviewed By: lucian@fb.com

FB internal diff: D1133938

Blame Revision: D1129497

support stack-allocated IOBufs

Summary:
Previously, all IOBuf APIs required that IOBufs always be allocated on
the heap.  The only methods provided to create IOBufs returned
unique_ptr<IOBuf>.

This adds new methods to support creating IOBufs on the stack.  This is
useful in cases where the IOBuf will be short-lived, and the overhead of
the heap allocation is undesirable.  (One use case is to wrap an
existing buffer in a short-lived IOBuf so that it can be used with the
Cursor API.)

I have currently made IOBufs movable but not copyable.  (Move operations
clearly should move only a single IOBuf, but it is not clear if the copy
operators should copy only a single IOBuf or the entire chain.)

Test Plan:
Updated the unit tests to test the new CREATE, WRAP_BUFFER,
TAKE_OWNERSHIP, and COPY_BUFFER constructors, as well as the move
constructor and assignment operator.

Reviewed By: davejwatson@fb.com

FB internal diff: D1067341

Baton - minimalist inter-thread notification

Summary:
A Baton allows a thread to block once and be awoken: it captures
a single handoff.  During its lifecycle (from construction/reset to
destruction/reset) a baton must either be post()ed and wait()ed exactly
once each, or not at all.  Batons may be reused after a call to
recycle().

Baton includes no internal padding, and is only 4 bytes in size.
Any alignment or padding to avoid false sharing is up to the user.

This is basically a stripped-down semaphore that supports only a single
call to sem_post.  The current posix semaphore sem_t isn't too bad, but
this provides more a bit more speed, checking, inlining, smaller size,
a guarantee that the implementation won't change, and compatibility
with DeterministicSchedule.  Baton is directly implemented on top of
futex, and takes care to avoid system calls.

Test Plan:
1. new unit tests
2. this code has already been in production use in TAO for many months

Reviewed By: davejwatson@fb.com

FB internal diff: D1130407

folly json bug fix: overflow for -1LL<<63

Summary: -1LL<<63 was passed to folly::to() without '-' so it overflowed. Fixed that

Test Plan:
tried this:

int main() {
stringstream s;
s << "{\"int\":" << -1LL<<63 << "}";
string str = s.str();
cout << "string to parse: " << endl << str << endl;

int64_t sample = folly::parseJson(str.c_str())["int"].asInt();
LOG(INFO) << "test result = " << sample;

return 0;
}

it returns right value.

Also tried it with "-Infinity" and double type for sample. In works fine as well.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1130155

readFile reads an entire file into a string, vector<char>, or similar

Test Plan: unittest

Reviewed By: lucian@fb.com

FB internal diff: D1129497

move folly::detail::IsSomeString outside of folly::detail

Summary:
It is useful when writing additional specializations of of
toAppend() and related functions to use IsSomeString, the same way the
ones in Conv.h do.  Move IsSomeString out of detail, so outside code
doesn't access a detail namespace inappropriately.

Test Plan: fbmake runtests; arc lint

Reviewed By: tudorb@fb.com

FB internal diff: D1130910

Remove some files that should have been deleted in earlier commits

Summary: Our script wasn't picking up removed files.

stack_trace_test was broken in debug mode

Summary: A function was getting inlined in opt mode but not in debug mode.

Test Plan: ran test

Reviewed By: philipp@fb.com

FB internal diff: D1130949

@override-unit-failures
test fix only

include guard name cleanup for IndexedMemPool

Summary: Include guard had FOLLY_DETAIL_.. even though code is in folly

Test Plan: unit tests

Reviewed By: davejwatson@fb.com

FB internal diff: D1130269

@override-unit-failures

IndexedMemPool - pool allocator tailored for lock-free data structures

Summary:
Instances of IndexedMemPool dynamically allocate and then pool
their element type (T), returning 4-byte integer indices that can be
passed to the pool's operator[] method to access or obtain pointers to
the actual elements.  Once they are constructed, elements are never
destroyed.  These two features are useful for lock-free algorithms.
The indexing behavior makes it easy to build tagged pointer-like-things,
since a large number of elements can be managed using fewer bits than a
full pointer.  The pooling behavior makes it safe to read from T-s even
after they have been recycled

Test Plan:
1. unit tests
2. unit tests using DeterministicSchedule
3. this code is moved from tao/queues where it is in production use

Reviewed By: davejwatson@fb.com

FB internal diff: D1089053

folly: symbolizer: small terse write fix + colorize signal handler output if printing to TTY

Summary:
Detailed output is a bit hard to parse visually. Add some colors for
clarity (clownyness?). Enabled only when printing stack traces from a
signal-handler to TTY.

Also:
- terse output printed empty lines if it could not find a symbol for an address; fixed by printing "(unknown)".
- added a dummy ##Crash## program to test colorization easily

Test Plan: n/a

Reviewed By: tudorb@fb.com

FB internal diff: D1128303

fix AtomicHashMap race condition

Summary: AHM::find checks that the returned SimpleRetT index is >= numMapsAllocated_ but that value may have changed and find pick the first element in the next sub map. Use success instead.

@override-unit-failures

Test Plan: unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D1126684

add FB_SINGLE_ARG macro

Test Plan: eyeballed it

@override-unit-failures

Reviewed By: soren@fb.com

FB internal diff: D1125180

Some fixes for folly-oss repo.

Summary:
The __builtin_ia32_crc[qd]i() functions are GCC >= 4.8 specific
folly-config.h includes must be wrapped in a FOLLY_NO_CONFIG guard
FOLLY_HAVE_WEAK_SYMBOLS needs to apply to the cpp file as well as the header

Closes #44
Closes #42

Test Plan: HHVM builds with recent folly

Reviewed By: seanc@fb.com

FB internal diff: D1117181

Fix cursor insert inconsistency

Summary:
The invariant after Cursor::insert is that the cursor points to the buffer
after the insert. That invariant was not followed in the branch where the
new buffer was just prepended. This change fixes the bug.

Test Plan:
Unit test modified, all tests run with
fbconfig -r folly && fbmake runtests_opt

Reviewed By: davejwatson@fb.com

FB internal diff: D1114749

work around broken try_lock_for in gcc

Summary:
timed_mutex::try_lock_for is broken in gcc 4.8 (see
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54562), so this diff adds
a workaround using try_lock_until.  The internal implementation of
try_lock_for converts to try_lock_until, but it uses the steady_clock
instead of the system_clock as its time base.  In some gcc versions
these are the same clock so it works okay, but not in all.

Test Plan: unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D1108584

Remove FOLLY_NORETURN from definition.

Summary:
- Remove FOLLY_NORETURN from function definitions, which was causing
compilation errors on some platforms.

Test Plan: - Compile on Mac OS X with Clang

Reviewed By: tudorb@fb.com

FB internal diff: D1111416

Add new CRC-32C checksum functions to folly

Summary:
* Added a new crc32c() function, with a portable implementation
and an optimized version for x86 with SSE4.2

Test Plan: New unit test included

Reviewed By: tudorb@fb.com

FB internal diff: D1111515

folly: avoid ASAN-detected new[] vs "delete" mismatch

Summary:
* folly/test/PackedSyncPtrTest.cpp: Avoid an operator new [] vs
operator delete mismatch.

Test Plan:
fbconfig --platform-all=gcc-4.8.1-glibc-2.17 --sanitize=address \
folly/test:packed_sync_ptr_test && fbmake runtests

Reviewed By: tudorb@fb.com

FB internal diff: D1111227

Detect availability of cplus_demangle_v3_callback()

Summary:
- Add autoconf check for cplus_demangle_v3_callback() in libiberty and
avoid is usage when not available. Clang/libc++ on Mac OS X doesn't
support this.

Test Plan:
- fbconfig -r folly && fbmake runtests
- ./configure && make check on Mac OS X

Reviewed By: tudorb@fb.com

FB internal diff: D1108543

Revert "[Folly] Helper method to get exception type"

Summary: This reverts commit 2c4f8da739ba0294f2c947753a0e30fee291feb5.

Test Plan: Compiles

Reviewed By: tudorb@fb.com

FB internal diff: D1108840

Helper method to get exception type

Test Plan: Tested with subsequent thrift diff

Reviewed By: davejwatson@fb.com

FB internal diff: D1108428

Handle lack of <bits/c++config.h> and <bits/functexcept.h>

Summary:
- Clang's libc++ doesn't provide these header files. Detect libc++ via
the _LIBCPP_VERSION symbol (pulling it in by sourcing some header files
earlier if necessary) and avoid using these files.
- This is another attempt at D1074481.

Test Plan: .

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1074723

Define weak r?allocm symbols in Malloc.h

Summary:
- This fixes a bug introduced in D1002959 that broke -fb platform
compilation: there was noone to forward-declare these symbols.

Test Plan:
- Built the gcc-4.8.1-glibc-2.17-fb platform
- fbconfig -r folly && fbmake runtests
- configure/make check on Mac OS X

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1074720

Blame Revision: D1002959

Fix name handling when baseDir and subDir are both empty, simplify paths

Test Plan: fbconfig -r folly/experimental/symbolizer folly/experimental/exception_tracer && fbmake runtests_opt

Reviewed By: wez@fb.com

FB internal diff: D1104426

Add startsWith, endsWith, removePrefix, removeSuffix to folly::Range

Summary:
Yes, I know about boost::starts_with, but I think the convenience is worth it.
Also, I've written then equivalent of removePrefix / removeSuffix way too
many times.

Test Plan: test added

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1106425

unw_backtrace is not async-signal-safe

Summary:
Even though it should be according to the docs; tdep_trace allocates memory on
first use from each thread.

Wrote a slow loop that we can use from the signal handler. The exception tracer
still uses the fast version.

Test Plan: fbconfig -r folly/experimental/symbolizer folly/experimental/exception_tracer && fbmake runtests_opt

Reviewed By: philipp@fb.com

FB internal diff: D1101095

Add futexTimedWait

Summary:
Add futexTimedWait to Futex which allows callers to wait on the futex
for a specified max duration.

Test Plan: -- Ran all unitests

Reviewed By: ngbronson@fb.com

FB internal diff: D1090115

AtomicStruct<T> provides atomic ops on small trivial classes

Summary:
AtomicStruct<T> acts like std::atomic<T>, but it supports any
trivial or trivially-copyable type up to 8 bytes in size.  I'm not sure
why these types weren't included in the original std::atomic standard,
since this construct removes a lot of boilerplate for some uses of
std::atomic.

Test Plan:
1. unit tests
2. this code is adapted from production use in tao/queues/LifoSem

Reviewed By: davejwatson@fb.com

FB internal diff: D1085106

folly::json: allow skipping invalid UTF8

Summary:
folly::json::serialize by default doesn't check for valid UTF8, and as a result can generate invalid JSON.  There is an option to check for valid UTF8, which throws on an error.

This diff introduces a new option, `skip_invalid`, which replaces invalid chars with U+FFFD. http://en.wikipedia.org/wiki/Specials_(Unicode_block) seems to suggest that this is the correct replacement.

@override-unit-failures

Test Plan: g-unittest

Reviewed By: delong.j@fb.com

FB internal diff: D1102923

folly/io:compression: add LZMA2 support

Summary:
Adds LZMA2 and LZMA2_VARINT_SIZE compression support for
folly::io::Compression.  This format shows some big wins for
compressing ELF object files and is useful in our modified
ccache client.

Test Plan:
Compression unittests.  Also, tested compressing object files built
in fbcode.  On average, the compression percentage improved from
~16.5% to ~12%.  But we save a lot more as object files get bigger,
which can help make bigger object files fit over fewer memcache
keys.

Reviewed By: njormrod@fb.com

FB internal diff: D1092576

Fix test, also do not read from stack of another thread

Summary:
... even though Google's signal handler does it
(https://code.google.com/p/google-glog/source/browse/trunk/src/signalhandler.cc?r=16#235)

Assuming the existence of an invalid pthread_t is a lesser evil than reading
from another thread's stack, IMO.

Test Plan: folly/experimental/symbolizer/test

Reviewed By: simpkins@fb.com

FB internal diff: D1096620

Don't forward declare ObjectMaker twice in dynamic

Summary: Makes clang nervous

@override-unit-failures

Test Plan: fbconfig -r folly && fbmake dbg succeeds

Reviewed By: delong.j@fb.com

FB internal diff: D1094209

fix callPreviousSignalHandler()

Summary:
If a previous handler was found, the code was missing the step of
actually re-raising the handler after restoring the old handler.

Test Plan: Verified that our service actually exits after receiving SIGTERM.

Reviewed By: tudorb@fb.com

FB internal diff: D1096360

Separate installFatalSignalCallbacks

Summary:
We want to install the signal handler first and then give users an opportunity
to add their callbacks.

Test Plan: built

Reviewed By: lucian@fb.com

FB internal diff: D1092083

@override-unit-failures

Switch to folly symbolizer

Summary:
(not committing yet, but I want to trigger unittests)

The glog symbolizer that we use has a few bugs (abort()s on certain small
shared libraries) and doesn't allow us to distinguish between template
specializations and function overloads (which, given that our code is more
template-heavy than Google's, has in fact been an issue).

Luckily, we have our own in folly, which doesn't have these problems and also
supports mappings from address to file and line number.

Switch translateFrames (aka the fb303 call that cpprof uses) to our symbolizer.
Also, removed a lot of dead code in common/process.

Test Plan: common/process, tested cpprof by hand

Reviewed By: lucian@fb.com

FB internal diff: D1090907

@override-unit-failures

SCOPE_SUCCESS should be able to throw, the others shouldn't

Summary: SCOPE_SUCCESS may legitimately throw, so changed the `noexcept` attribute to a conditional one. Also added the noexcept promise to the lambdas in the hope the compiler will check code during compilation appropriately. (It currently doesn't.)

Test Plan: Added a unittest that failed, not passes.

Reviewed By: simpkins@fb.com

FB internal diff: D1093328

@override-unit-failures

centralize cache-line alignment goo into CacheLocality

Summary:
The alignment requirements and details required to avoid false
sharing belong in CacheLocality, so this diff moves them there.

@override-unit-failures

Test Plan: fbmake runtests

Reviewed By: davejwatson@fb.com

FB internal diff: D1086090

FBString iomanip fix.

Summary:
D1090936 noticed some problems with fbstring iomanip behavior.
The root cause is that os.write(ostream, char*, size_t) is an
UnformattedOutputFunction, so disregards setw(), setfill(), and
left/right alignment.

The use of os.write instead of os << str.data() is intentional:
D367009 switched from the latter to the former so that strings
containing a '\0' are printed properly.

There does not seem to be a public function to write with formatting.
Where needed in libgcc, the function __ostream_insert is used. Since
FBString already uses such 'private' functions, __ostream_insert is an
appropriate solution.

@override-unit-failures

Test Plan:
Added test cases to FBStringTest.cpp to cover iomanip.
fbconfig -r folly && fbmake opt && fbmake runtests_opt

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D1091474

Use fixed size stack traces; unify getStackTrace

Summary:
Also, switch to the simpler unw_backtrace(), which has the nice advantage of
actually doing IP adjustment (-1 in certain frames) correctly, unlike me :)

This is in preparation for the faster backtrace in libunwind 1.1.

Test Plan: folly/experimental/exception_tracer, folly/experimental/symbolizer, admarket/lib/util:memory_tracker_test

Reviewed By: lucian@fb.com

FB internal diff: D1088357

detail/CacheLocality.h - utilities for dynamic cache optimizations

Summary:
CacheLocality reads cache sharing information from sysfs to
determine how CPUs should be grouped to minimize contention, Getcpu
provides fast access to the current CPU via __vdso_getcpu, and
AccessSpreader uses these two to optimally spread accesses among a
predetermined number of stripes.

AccessSpreader<>::current(n) microbenchmarks at 22 nanos, which is
substantially less than the cost of a cache miss.  This means that we
can effectively use it to reduce cache line ping-pong on striped data
structures such as IndexedMemPool or statistics counters.

Because CacheLocality looks at all of the cache levels, it can be used for
different levels of optimization.  AccessSpreader<>::stripeByChip.current()
uses as few stripes as possible to avoid off-chip communication,
AccessSpreader<>::stripeByCore.current() uses as many stripes as necessary
to get the optimal speedup, but no more.

@override-unit-failures

Test Plan: new unit tests

Reviewed By: davejwatson@fb.com

FB internal diff: D1076718

Revert "Change exception tracer to use per-thread caching in libunwind"

Summary:
Per-thread caching calls malloc, which means it doesn't work for malloc's
profiling (and also it isn't async-signal-safe, despite the documentation).

Test Plan: compiled

Reviewed By: philipp@fb.com

FB internal diff: D1085368

@override-unit-failures

Print (2 more) if stack trace truncated

Summary:
Also, C++ify the interface and switch to per-thread caching in libunwind as per
D1081259

Test Plan: folly/experimental/symbolizer/test

Reviewed By: lucian@fb.com

FB internal diff: D1081272

Fix asm constraints in folly::MicroSpinLock::cas

Summary:
If the compare part of cmpxchg fails, it writes the unexpected value
to %rax. At certain optimization levels this was causing me to hit an
incorrectly failed assertion in some thrift code. I also cleaned up the asm
statement to use named operands.

Test Plan: Added new test that fails before this diff.

Reviewed By: delong.j@fb.com

FB internal diff: D1083222
@override-unit-failures

make IOBuf::gather() safe

Summary:
Update IOBuf::gather() and RWCursor::gather() to check their arguments
more carefully, and throw std::overflow_errors if the caller attempts to
gather more data than is available.

The comments for IOBuf::gather() claimed that it ensured that maxLength
bytes would always be available when it returned.  However, if the total
chain length was less than maxLength, it would simply coalesce the full
chain and return successfully, even though fewer than maxLength bytes
were available.  This fixes the code to throw a std::overflow_error
rather than coalescing the chain.

Additional, this updates RWCursor::gather() to ensure that it does not
attempt to gather past the end of the IOBuf chain.  Previously it could
gather past the end of the chain, coalescing the head of the chain into
the tail.  This would free the IOBuf head, which was owned by an
external caller.

A new RWCursor::gatherAtMost() API is provided for callers that wish to
gather as much as requested if possible, but still succeed if less than
this is available.

Test Plan:
Updated the unit tests to test calling gather() with more bytes than
actually available.

Reviewed By: davejwatson@fb.com

FB internal diff: D1081995

fix issues when compiling with clang

Summary:
My previous change to re-implement IOBuf's internal storage mechanism
introduced a build failure when compiling with clang.

This fixes the new compilation error in IOBuf.cpp, as well as two
existing build failures in some of the unit tests.

Test Plan: Built the folly/io code with clang.

Reviewed By: andrewjcg@fb.com

FB internal diff: D1082086

change the mechanism for "internal" buffer storage

Summary:
This removes kFlagExt, and instead implements the internal buffer
optimization using operator new and delete.

IOBuf::createCombined() will allocate a single buffer for the IOBuf,
SharedInfo, and the actual data itself.  Each heap allocated IOBuf now
contains a set of flags indicating if the memory segment indicating when
it can actually be deleted.  The delete operator won't actually free the
storage until both the IOBuf and the data buffer are unused (the
SharedInfo object always becomes unused at the same time as the data
buffer).

This has a couple advantages over the old mechanism:

- Other IOBufs can continue to use and share the data storage space even
after the original IOBuf associated with it is deleted.  With the old
internal buffer mechanism, internal buffers could never be shared.

- This simplifies several parts of the code, since kFlagExt no longer
exists.  Code that previously required special handling for internal
buffers no longer needs to be aware of them.

One downside is that this can result in wasted space in some cases if
the original IOBuf is changed to point at a different buffer, since the
space for the data buffer cannot be freed until the IOBuf itself is also
destroyed.  The old internal buffer mechanism also had this problem,
which we mitigated simply by disallowing internal buffers for larger
than ~200 bytes.  With the new mechanism we currently allocate an
internal buffer for up to 1024 bytes by default, but we also allow
callers to explicitly decide if they want an internal buffer or not.

Test Plan:
Added some new unit tests for the combined buffer behavior.  Also ran
all of the existing IOBuf unit tests, with and without ASAN.  (ASAN
performs additional memory checking, but also changes IOBuf's behavior
slightly as usingJEMalloc() is false with ASAN.)

Reviewed By: davejwatson@fb.com

FB internal diff: D1072336

@override-unit-failures

Change exception tracer to use per-thread caching in libunwind

Summary: Because the global cache is slow and contends on locks.

Test Plan: testinproduction

Reviewed By: philipp@fb.com

FB internal diff: D1081259

Made File::release() return the released file descriptor.

Summary: It's convenient to get back the fd, similar to unique_ptr::release().

Test Plan: unittest

Reviewed By: tudorb@fb.com

FB internal diff: D1080426

Async-signal-safe symbolizer, fatal signal handler

Test Plan: test added

Reviewed By: lucian@fb.com

FB internal diff: D1076170

@override-unit-failures

Add async-signal-safe flavor of demangle

Summary: To be used in the new fatal signal handler.

Test Plan: test added

Reviewed By: lucian@fb.com

FB internal diff: D1076169

@override-unit-failures

SafeAssert: async-signal-safe CHECK, DCHECK

Summary: To be used from the (new) fatal signal handler.

Test Plan: test added

Reviewed By: lucian@fb.com

FB internal diff: D1076168

@override-unit-failures

update moveToFbString()'s handling of flags_

Summary:
Improve moveToFbString()'s code which determines if we actually have a
buffer that was allocated with malloc().

The old code simply checked if flags_ == kFlagExt.  This check is rather
fragile, and relies on very specific behavior from the existing
construction methods.  It also unnecessarily forced reallocation in some
cases.

This updates the code to have more specific checks for the flags and
fields that actually matter.  In particular, even if we have an external
buffer, if sharedInfo->freeFn is set then it is not managed by malloc().
The old check happened to work because takeOwnership() was the only
function that set set freeFn, and it also set kFlagFreeSharedInfo.

This also improves the code so that it won't unnecessarily reallocate
the buffer if kFlagMaybeShared is set but the buffer isn't really
shared.  The code will also no longer unnecessarily reallocates the
buffer just because kFlagFreeSharedInfo is set.

Test Plan:
Updated the moveToFbString() test to also test with buffers created
using takeOwnership() and wrapBuffer().

Reviewed By: davejwatson@fb.com

FB internal diff: D1072304

@override-unit-failures

fix IOBuf::reserve() when operating on a user-supplied buffer

Summary:
The IOBuf::reserveSlow() code assumed that external buffers were always
allocated with malloc.  This would cause problems when if reserve() was
ever used on a buffer created with IOBuf::takeOwnership().

This changes the code to now check if a user-specified free function has
been supplied.  If so, then it does not try to use realloc()/rallocm(),
and it now frees the old buffer using the specified free function rather
than free().

User-supplied buffers also have a separately allocated SharedInfo
object, which must be freed when we no longer need it.

Test Plan:
Added additional unit tests to check calling reserve() on IOBufs created
with IOBuf::takeOwnership().

Reviewed By: davejwatson@fb.com

FB internal diff: D1072292