Allow capacity and length to be different for user buffers

Summary:
Currently, takeOwnership lets a user pass in a data buffer and wraps it in an
IOBuffer. However, the capacity and length of the user buffer are required to
be same.

Added a new API to allow buffers where the capacity and length can be different.

Users of existing API should not be affected.

Test Plan:
1) Added new test case to IOBufTest that checks buffers with length
different from capacity
2) Run existing IOBuf test cases to verify no regressions

Reviewed By: brianp@fb.com

FB internal diff: D536575

Make AtomicHashMap support move constructible types

Summary: modified AtomicHashArray and AtomicHashMap to support move constructible types

Test Plan: tested with fbcode/folly/test/AtomicHashArrayTest.cpp and fbcode/folly/test/AtomicHashMapTest.cpp

Reviewed By: philipp@fb.com

FB internal diff: D527270

Moving some more benchmarks to fbcode benchmark system

Summary: The format benchmark that was ported some time back has few data points to show - http://fburl.com/3545876

Test Plan: fbmake --log-to-rfe runbenchmarks_opt

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D524306

Add IEC binary unit prefixes

Summary: KiB, MiB, GiB, TiB, etc

Test Plan: by hand in a program using them

Reviewed By: philipp@fb.com

FB internal diff: D527001

add sched_yield in RWTicketSpinLock

Summary:
This diff makes RWTicketSpinLock eventually start calling
sched_yield() during shared and aggressive exclusive lock access, to
avoid pathologies that can arise when the number of threads far
exceeds the number of actual cores.

Test Plan:
1. unit tests
2. benchmark w/o + w/ diff

Reviewed By: nathan@fb.com

FB internal diff: D524897

Add folly::applyTuple utility

Summary: Applies a function to a std::tuple of arguments.

Test Plan: Unit test.

Reviewed By: tjackson@fb.com

FB internal diff: D520190

Fix an issue in IOBufQueue::move

Summary: That's all.

Test Plan: .

Reviewed By: philipp@fb.com

FB internal diff: D520116

Add wrapper macros for "final" and "override"

Summary:
... which are supported in gcc 4.7, but not 4.6, and they enable useful
optimizations.  As long as we're planning to support both 4.6 and 4.7 in
our code base, we should write code using these macros.

Test Plan:
test added, compiled with both 4.6 and 4.7, verified the
assertion in the test comment by looking at dissassembly output in the
4.7 version

Reviewed By: delong.j@fb.com

FB internal diff: D520343

Add missing include

Test Plan: yes

Reviewed By: delong.j@fb.com

FB internal diff: D519897

rallocm(ALLOCM_ZERO) only zeroes *new* memory

Summary:
If you allocate N bytes and then try to grow that in place using rallocm
(ALLOCM_ZERO | ALLOCM_NO_MOVE) to M > N, our code assumed that all
memory from N to M would be zeroed.  In fact, rallocm only zeroes *new*
memory, so if jemalloc actually allocated N1 > N bytes initially,
rallocm will only zero memory from N1 to M.

Fixed by using calloc.

Test Plan: thread_local_test, tested in production

Reviewed By: delong.j@fb.com

FB internal diff: D519781

A sample diff thats ports FormatTests to benchmarks

Summary:
Is there any better solution? Maybe a generic flag in Benchmarks to say
please don't run benchmarks?

Test Plan: (not in folly)

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D503619

Unbreak build.

Summary: I could have sworn I undid that un-templatification of the constructor.

Test Plan: build folly/test

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D518981

Range<const char*> -> Range<const unsigned char*> implicit conversion

Summary: As they can both be used to represent ranges of bytes.

Test Plan: test added

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D518666

(minor changes, part of unrelated diff)

Test Plan: No

Reviewed By: lucian@fb.com

FB internal diff: D515713

Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)

Test Plan: all folly tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D517118

folly/Malloc.h: use libstdc++-safe exception wrappers

Summary:
gcc errors out when code that throws is compiled with
'-fno-exceptions'.  Since we add Malloc.h into our custom libstdc++
use the exception wrappers from functexcept.h so that they can build
with third-party projects that use '-fno-exceptions'.

Test Plan:
Built llvm in the gcc-4.7.1-glibc-2.14.1-fb platform with these
changes.

Reviewed By: tudorb@fb.com

FB internal diff: D516577

fix memory order in AtomicHashMap<>::findInternal()

Summary:
Looks like a typo, it should obviously be std::memory_order_relaxed (all
necessary synchronization is done on numMapsAllocated_).

Test Plan: compiled it, ran tests

Reviewed By: sahrens@fb.com

FB internal diff: D515322

folly: fix build on ubuntu and fedora platforms

Summary:
A boost regex dependency wasn't added to the Makefile.am file.  Also
the it appears that boost thread lib dependencies had a typo in the
makefile variable name.

Test Plan: ran builds on ubunutu and fedora VMs

Reviewed By: tudorb@fb.com

FB internal diff: D514039

(minor changes, part of unrelated diff)

Test Plan: no

Reviewed By: philipp@fb.com

FB internal diff: D512868

Add IOBufQueue::prepend, fix bug in IOBuf::prepend.

Summary:
IOBuf::prepend needs to increment length_.

Added IOBufQueue::prepend, which uses the headroom in the first buffer
instead of growing the queue at the head.

Test Plan: tests added

Reviewed By: simpkins@fb.com

FB internal diff: D513676

Improve digits_to() performance

Summary:
This optimization eliminates about 75% of the multiplications and bounds
checking in the original code by using constant lookup tables to convert
from decical digit to (shifted) binary number, instead of arithmetic.
The total cost of the lookup tables is 2KB of static memory, but the
average throughput gain across the range from 1 to 19 characters is 27%.
The throughput distributes as follows: (in million iters/sec)
Bytes   Orig    New     Speedup
1       101.31  110.12  109%
2       97.42   110.12  113%
3       97.42   105.53  108%
4       79.13   101.31  128%
5       74.48   97.42   131%
6       74.48   93.81   126%
7       70.35   93.81   133%
8       61.77   79.14   128%
9       58.9    72.35   123%
10      58.9    74.48   126%
11      56.28   74.48   132%
12      50.22   64.93   129%
13      48.52   60.3    124%
14      47.74   61.77   129%
15      46.88   61.77   132%
16      42.54   55.06   129%
17      41.51   51.69   125%
18      40.97   52.76   129%
19      39.57   52.76   133%

Test Plan: Passes all unit tests

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D493245

Add multi-bit operations to folly/experimental/Bits.h

Summary: Add ability to set and get N consecutive bits from the bit sequence.

Test Plan: test added

Reviewed By: lucian@fb.com

FB internal diff: D511438

adding StringPiece constructor that takes a piece of another StringPiece

Summary:
adding what seems to be a missing constructor to StringPiece --
I need to be able to take a piece of another StringPiece. (It's possible
to do that with all sorts of strings already, except StringPiece...)

Test Plan: na -- tested as part of other (dependent) diffs

Reviewed By: delong.j@fb.com

FB internal diff: D508545

Remove unnecessary member variable.

Test Plan: No

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D509324

add bm_max/min_iters and bm_regex

Summary: These were handy in the old framework and easy enough to add.

Test Plan:
ran ThreadCachedIntTest - got better (but not perfect due to
subtraction of single-threaded baseline from multi-threaded results).

Reviewed By: sherman.ye@fb.com

FB internal diff: D490324

folly: get building with gcc-4.7.1

Summary:
A lot of libstdc++-4.7 headers dropped includes of unistdc.h, so
we'll probably see more of these.

Test Plan: built folly

Reviewed By: simpkins@fb.com

FB internal diff: D508871

Minor changes to folly/experimental/io

Reviewed By: philipp@fb.com

FB internal diff: D491952

Adding support to output benchmarks result in JSON

Summary: The main reason being so that they can be fed to some automated systems, if required.

Test Plan: Just ran few benchmarks locally

Reviewed By: andrewjcg@fb.com

FB internal diff: D501025

Add TypedIOBuf.

Summary: Simple class to handle IOBuf as an array of objects of fixed size.

Test Plan: test added

Reviewed By: brianp@fb.com

FB internal diff: D497287

Add sizeGuess() member to ProducerConsumerQueue

Summary:
This is part 1 of a change to add hysteretic behavior to a blocking queue based on ProducerConsumerQueue.

Knowing the size is useful for monitoring and possibly for objects that contain a ProducerConsumerQueue.

Test Plan:
Added tiny test-case.

Tests pass

Reviewed By: delong.j@fb.com

FB internal diff: D496787

Add an allocate() member function on IOBufQueue

Summary: Function is documented in the header.

Reviewed By: soren@fb.com

FB internal diff: D494315

Fix a typo in benchmark comments

Summary: As title

Test Plan: Deployed to wormhole_apps.dragon.dev

Reviewed By: asharma@fb.com

FB internal diff: D493253

Unbreak Ubuntu build.

Summary: follybenchmark and follyfingerprint need folly to work.

Test Plan: built on ubuntu

Reviewed By: andrewjcg@fb.com

FB internal diff: D494955

Fix clang narrowing error in GroupVarintTables

Summary:
The __m128i type is a pair of 64-bit signed ints and the values
generated in generate_varint_tables.py overflow this range, which
causes clang to complain.

Test Plan:
Built and ran unittests.  Also verified that the GroupVarintTable.o
data section was identical with and w/o this change.

Reviewed By: tudorb@fb.com

FB internal diff: D494645

Clarify split / splitTo comments.

Test Plan: No

Reviewed By: delong.j@fb.com

FB internal diff: D494525

Move and refactor code

Summary:

Moves some string manipulation code like humanify into folly

Moves hash-related functions into folly and removes some old includes
to clean up some code

Adds generic hashing for tuples, similar to pairs

Updates all of the build breakages from the above

Test Plan: run unit tests

Reviewed By: delong.j@fb.com

FB internal diff: D490478

Fix narrowing warning (if enabled).

Summary: They're (signed) long long.

Test Plan: built, folly/test

Reviewed By: andrewjcg@fb.com

FB internal diff: D493270

Fix intermittent failure in concurrent_skip_list_test

Summary: It creates too many threads, stop when we run out of resources.

Test Plan: by hand, in a loop, in a memory-constrained environment

Reviewed By: delong.j@fb.com

FB internal diff: D493239

Fix build and test.

Summary:
Fix bug in FBStringTest (don't reuse the same file name)

Don't use VLOG, as that requires that glog is compiled with gflags
support, which it isn't always.

Add other targets and tests, make all tests pass.

Test Plan: tests

Reviewed By: delong.j@fb.com

FB internal diff: D493018

Fix build and test.

Summary:
Fix bug in FBStringTest (don't reuse the same file name)

Don't use VLOG, as that requires that glog is compiled with gflags
support, which it isn't always.

Add other targets and tests, make all tests pass.

Test Plan: tests

Reviewed By: delong.j@fb.com

FB internal diff: D493018

Move Rabin fingerprinting code to folly.

Summary:
Also generate fingerprint tables every time, so the code doesn't rot.

TODO(tudorb): move benchmark to folly
TODO(tudorb): Include the program used to generate the polynomials
(can't build as it requires NTL from http://www.shoup.net/ntl/)

Test Plan: folly/test

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D492455

InternalBuf doesn't need capacity

Summary: as it's always kMaxInternalDataSize.

Test Plan: all tests in folly/experimental/io/test, both opt and dbg

Reviewed By: brianp@fb.com

FB internal diff: D492008

Properly align internal buffer in IOBuf.

Summary:
Yes, it's gcc specific, because alignas and max_align_t aren't in gcc
4.6.2.

Test Plan: iobuf_test, test added

Reviewed By: brianp@fb.com

FB internal diff: D491939

Add IOBuf::takeOwnership(unique_ptr<T>&&).

Summary:
Useful for in-place serialization.  Dangerous, obviously, but anything
involving IOBuf usually is.

Test Plan: test added

Reviewed By: brianp@fb.com

FB internal diff: D491663

Typos.

Test Plan: No

Reviewed By: delong.j@fb.com

FB internal diff: D491038

D'oh: fix size computation in ThreadLocalDetail.h

Test Plan: thread_local_test

Reviewed By: ldemailly@fb.com

FB internal diff: D490912

folly::detail::futex should be inline

Summary: It breaks build.

Test Plan: will check *_try builds

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D489935

Add IOBufQueue::wrapBuffer, which handles buffers > 4GB.

Test Plan: test added

Reviewed By: brianp@fb.com

FB internal diff: D489158

Add links to README.

Test Plan: No

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D489199

Deuglify unaligned accesses in GroupVarint.

Test Plan: folly/test

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D488631

EventCount: "condition variable" for lock-free algorithms

Summary:
This allows you to convert non-blocking lock-free algorithms into
blocking versions.

See
http://www.1024cores.net/home/lock-free-algorithms/eventcounts,
http://software.intel.com/en-us/forums/showthread.php?t=62364,
http://www.akkadia.org/drepper/futex.pdf

Test Plan: new test

Reviewed By: delong.j@fb.com

FB internal diff: D474570

fbstring: remove reference to /home/engshare/ paths

Summary: Reported by https://github.com/facebook/folly/issues/8

Test Plan: no

Reviewed By: tudorb@fb.com

FB internal diff: D487572

Fix some memory_order parameters in AtomicHashMap

Summary: Herb Sutter noticed an error in the AHM find pseudo-code at
the C++ conference, and the error is in the real implementation too.
We should be using memory_order_acquire, because we need the load of
the key to happen before any subsequent loads of the value itself.
Our implementation is conservative for a memory_order_relaxed load
(we generate the same code as if it were memory_order_acquire---i.e. a
compiler barrier but no memory barriers), so this should not change the
generated code.  Correctness is a good idea, though (when we upgrade
to gcc 4.7's atomics it might not be as conservative).  Also, erase was
doing three loads when one is enough.  ... also fixes an exception safety
bug in insert.  (Phew.)

Test Plan: Ran the AHM unit tests, debug and opt.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D485744

Some typos corrects, and collapsed the two descriptions of Bits.h into one.

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

Test Plan: N/A.

Reviewed By: andrewjcg@fb.com

FB internal diff: D485738

Add #include <new> to folly/Malloc.h.

Test Plan: folly tests

Reviewed By: philipp@fb.com, andrei.alexandrescu@fb.com

FB internal diff: D486884, D487376

Check the return value from malloc / realloc.

Summary:
https://github.com/facebook/folly/issues/7

Wrappers: checkedMalloc / checkedRealloc / checkedCalloc

Test Plan: all folly tests

FB internal diff: D486841

Fix error in ProducerQueue::isEmpty

Summary:
Oops.

Also: documented the slightly confusing behavior w.r.t. 'size'.

Test Plan: Added a unit test.

Reviewers: tjackson, jdelong

Reviewed By: jdelong

CC: folly@lists, lr, bagashe
Differential Revision: https://phabricator.fb.com/D486832

Typos.

Summary:
As pointed out by orbitcowboy at
https://github.com/facebook/folly/issues/6

Test Plan: No

Reviewers: jdelong, aalexandre

Reviewed By: jdelong

CC: folly@lists, bagashe
Differential Revision: https://phabricator.fb.com/D486754

Move LICENCE and README to top level directory

Summary: For the public version of the repo.

Test Plan: N/A.

add a .gitignore and remove folly-config.h (generated file) from the repo

Adding support for in-place use of ProducerConsumerQueue.

Summary: As it is, ProducerConsumerQueue requires that values are moved or copied on the way out of the queue. It would be nice if it was possible to get a reference to the front of the queue, use it in place, then destruct it.

Test Plan: Unit tests

FB internal diff: D484538

Add a LICENSE file for folly

Summary: Adds a copy of the apache license 2.0.

Test Plan: None.

Update the folly/README

Summary: Now that we have an Overview.md.

Test Plan: None.

Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6

initial