Increase leveldb version to 1.20.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148937577

Separate Env tests from PosixEnv tests.

env_test.cc defines EnvPosixTest which tests the Env implementation returned by Env::Default(). The naming is a bit unfortunate, as the tests in env_test.cc a

Separate Env tests from PosixEnv tests.

env_test.cc defines EnvPosixTest which tests the Env implementation returned by Env::Default(). The naming is a bit unfortunate, as the tests in env_test.cc are written against the Env contract, and therefore are applicable to any Env implementation. An instance of the confusion caused by the naming is [] which added a dependency from env_test.cc to EnvPosixTestHelper, which is closely coupled to EnvPosix.

This change disentangles EnvPosix-specific test code into a env_posix_test.cc file. The code there uses EnvPosixTestHelper and specifically targets the EnvPosix implementation. env_test.cc now implements EnvTest, and contains tests that are also applicable to other ports, which may define their own Env implementation.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148914642

show more ...

leveldb: Fix compilation warnings in port_posix_sse.cc on x86 (32-bit).

LE_LOAD64 is only used when _mm_crc32_u64 is available, on 64-bit x86 processors.

-------------
Created by MOE: https://githu

leveldb: Fix compilation warnings in port_posix_sse.cc on x86 (32-bit).

LE_LOAD64 is only used when _mm_crc32_u64 is available, on 64-bit x86 processors.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148906169

show more ...

Fixed path to doc file: index.md.

Prior index.html was using rawgit.com which doesn't process
Markdown and therefore only serves the markdown source.

-------------
Created by MOE: https://github.co

Fixed path to doc file: index.md.

Prior index.html was using rawgit.com which doesn't process
Markdown and therefore only serves the markdown source.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148902180

show more ...

Convert documentation to markdown.

Markdown is more readable in a text editor and when hosted
on GitHub is more readable than HTML.

-------------
Created by MOE: https://github.com/google/moe
MOE_M

Convert documentation to markdown.

Markdown is more readable in a text editor and when hosted
on GitHub is more readable than HTML.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148830423

show more ...

Implement support for Intel crc32 instruction (SSE 4.2)

This change authored by vadimskipin and submitted via:

https://github.com/google/leveldb/pull/309

Changes made to support iOS builds and

Implement support for Intel crc32 instruction (SSE 4.2)

This change authored by vadimskipin and submitted via:

https://github.com/google/leveldb/pull/309

Changes made to support iOS builds and other architectures
without support for SSE 4.2.

db_bench reports original crc32 speed at:

crc32c : 3.610 micros/op; 1082.0 MB/s (4K per op)

with this change performance has increased to:

crc32c : 0.843 micros/op; 4633.6 MB/s (4K per op)

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=148694935

show more ...

Including <limits> for std::numeric_limits.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=146841327

Limit the number of read-only files the POSIX Env will have open.

Background compaction can create an unbounded number of
leveldb::RandomAccessFile instances. On 64-bit systems mmap is used and
file

Limit the number of read-only files the POSIX Env will have open.

Background compaction can create an unbounded number of
leveldb::RandomAccessFile instances. On 64-bit systems mmap is used and
file descriptors are only used beyond a certain number of mmap's.
32-bit systems to not use mmap at all. leveldb::RandomAccessFile does not
observe Options.max_open_files so compaction could exhaust the file
descriptor limit.

This change uses getrlimit to determine the maximum number of open
files and limits RandomAccessFile to approximately 20% of that value.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=143505556

show more ...

Add option for max file size. The currend hard-coded value of 2M is inefficient in colossus.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=134391640

Increase leveldb version to 1.19.

-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=129930720

A zippy change broke test assumptions about the size of compressed output.
Fix the tests by allowing more slop in zippy's behavior.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIG

A zippy change broke test assumptions about the size of compressed output.
Fix the tests by allowing more slop in zippy's behavior.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=123432472

show more ...

fix problems in LevelDB's caching code

Background:

LevelDB uses a cache (util/cache.h, util/cache.cc) of (key,value)
pairs for two purposes:
- a cache of (table, file handle) pairs
- a cache of blo

fix problems in LevelDB's caching code

Background:

LevelDB uses a cache (util/cache.h, util/cache.cc) of (key,value)
pairs for two purposes:
- a cache of (table, file handle) pairs
- a cache of blocks

The cache places the (key,value) pairs in a reference-counted
wrapper. When it returns a value, it returns a reference to this
wrapper. When the client has finished using the reference and
its enclosed (key,value), it calls Release() to decrement the
reference count.

Each (key,value) pair has an associated resource usage. The
cache maintains the sum of the usages of the elements it holds,
and removes values as needed to keep the sum below a capacity
threshold. It maintains an LRU list so that it will remove the
least-recently used elements first.

The max_open_files option to LevelDB sets the size of the cache
of (table, file handle) pairs. The option is not used in any
other way.

The observed behaviour:

If LevelDB at any time used more file handles concurrently than
the cache size set via max_open_files, it attempted to reduce the
number by evicting entries from the table cache. This could
happen most easily during compaction, and if max_open_files was
low. Because the handles were in use, their reference count did
not drop to zero, and so the usage sum in the cache was not
modified by the evictions. Subsequent Insert() calls returned
valid handles, but their entries were immediately evicted from
the cache, which though empty still acted as though full. As a
result, there was effectively no caching, and the number of open
file handles rose []ly until it hit system-imposed limits and
the process died.

If one set max_open_files lower, the cache was more likely to
exhibit this beahviour, and cause the process to run out of file
descriptors. That is, max_open_files acted in almost exactly the
opposite manner from what was intended.

The problems:

1. The cache kept all elements on its LRU list eligible for capacity
eviction---even those with outstanding references from clients. This was
ineffective in reducing resource consumption because there was an
outstanding reference, guaranteeing that the items remained. A secondary
issue was that there is no guarantee that these in-use items will be the
last things reached in the LRU chain, which actually recorded
"least-recently requested" rather than "least-recently used".

2. The sum of usages was decremented not when a (key,value) was evicted from
the cache, but when its reference count went to zero. Thus, when things
were removed from the cache, either by garbage collection or via Erase(),
the usage sum was not necessarily decreased. This allowed the cache to act
as though full when it was in fact not, reducing caching effectiveness, and
leading to more resources being consumed---the opposite of what the
evictions were intended to achieve.

3. (minor) The cache's clients insert items into it by first looking up the
key, and inserting only if no value is found. Although the cache has an
internal lock, the clients use no locking to ensure atomicity of the
Lookup/Insert pair. (see table/table.cc: block_cache->Insert() and
db/table_cache.cc: cache_->Insert()). Thus, if two threads Insert() at
about the same time, they can both Lookup(), find nothing, and both
Insert(). The second Insert() would evict the first value, leaving each
thread with a handle on its own version of the data, and with the second
version in the cache. It would be better if both threads ended up with a
handle on the same (key,value) pair, which implies it must be the first item
inserted. This suggests that Insert() should not replace an existing value.

This can be made safe with current usage inside LeveDB itself, but this is
not easy to change first because Cache is a public interface, so to change
the semantics of an existing call might break things, second because Cache
is an abstract virtual class, so adding a new abstract virtual method may
break other implementations, and third, the new method "insert without
replacing" cannot be implemented in terms of the existing methods, so cannot
be implemented with a non-abstract default. But fortunately, the effects
of this issue are minor, so this issue is not fixed by this change.

The changes:

The assumption in the fixes is that it is always better to cache
entries unless removal from the cache would lead to deallocation.

Cache entries now have an "in_cache" boolean indicating whether
the cache has a reference on the entry. The only ways that this can
become false without the entry being passed to its "deleter" are via
Erase(), via Insert() when an element with a duplicate key is inserted,
or on destruction of the cache.

The cache now keeps two linked lists instead of one. All items
in the cache are in one list or the other, and never both. Items
still referenced by clients but erased from the cache are in
neither list. The lists are:
- in-use: contains the items currently referenced by clients, in no particular
order. (This list is used for invariant checking. If we removed the check,
elements that would otherwise be on this list could be left as disconnected
singleton lists.)
- LRU: contains the items not currently referenced by clients, in LRU order

A new internal Ref() method increments the reference count. If
incrementing from 1 to 2 for an item in the cache, it is moved
from the LRU list to the in-use list.

The Unref() call now moves things from the in-use list to the LRU
list if the reference count falls to 1, and the item is in the
cache. It no longer adjusts the usage sum. The usage sum now
reflects only what is in the cache, rather than including
still-referenced items that have been evicted.

The LRU_Append() now takes a "list" parameter so that it can be
used to append either to the LRU list or the in-use list.

Lookup() is modified to use the new Ref() call, rather than
adjusting the reference count and LRU chain directly.

Insert() eviction code is also modified to adjust the usage sum and the
in_cache boolean of the evicted elements. Some LevelDB tests assume that there
will be no caching whatsoever if the cache size is set to zero, so this is
handled as a special case.

A new private method FinishErase() is factored out
with the common code from where items are removed from the cache.

Erase() is modified to adjust the usage sum and the in_cache
boolean of the erased elements, and to use FinishErase().

Prune() is modified to use FinishErase() also, and to make use of the fact that
the lru_ list now contains only items with reference count 1.

- EvictionPolicy is modified to test that an entry with an
outstanding handle is not evicted. This test fails with the old cache.cc.

- A new test case UseExceedsCacheSize verifies that even when the
cache is overfull of entries with outstanding handles, none are
evicted. This test fails with the old cache.cc, and is the key
issue that causes file descriptors to run out when the cache
size is set too small.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=123247237

show more ...

Fix LevelDB build when asserts are enabled in release builds. (#367)

* Fix LevelDB build when asserts are enabled in release builds.

BUG=https://bugs.chromium.org/p/chromium/issues/detail?id=6031

Fix LevelDB build when asserts are enabled in release builds. (#367)

* Fix LevelDB build when asserts are enabled in release builds.

BUG=https://bugs.chromium.org/p/chromium/issues/detail?id=603166

* fix

* Add comment

show more ...

Change std::uint64_t to uint64_t (#354)

-This fixes compile errors with default setup on RHEL 6 systems.

This CL fixes a bug encountered when reading records from leveldb files that have been split, as in a [] input task split.

Detailed description:

Suppose an input split is generated between two leve

This CL fixes a bug encountered when reading records from leveldb files that have been split, as in a [] input task split.

Detailed description:

Suppose an input split is generated between two leveldb record blocks and the preceding block ends with null padding.

A reader that previously read at least 1 record within the first block (before encountering the padding) upon trying to read the next record, will successfully and correctly read the next logical record from the subsequent block, but will return a last record offset pointing to the padding in the first block.

When this happened in a [], it resulted in duplicate records being handled at what appeared to be different offsets that were separated by only a few bytes.

This behavior is only observed when at least 1 record was read from the first block before encountering the padding. If the initial offset for a reader was within the padding, the correct record offset would be reported, namely the offset within the second block.

The tests failed to catch this scenario/bug, because each read test only read a single record with an initial offset. This CL adds an explicit test case for this scenario, and modifies the test structure to read all remaining records in the test case after an initial offset is specified. Thus an initial offset that jumps to record #3, with 5 total records in the test file, will result in reading 2 records, and validating the offset of each of them in order to pass successfully.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=115338487

show more ...

Deleted redundant null ptr check prior to delete.

Fixes issue #338.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=113439460

Fix signed/unsigned mismatch on VC++ builds

Putting build artifacts in subdirectory.

1. Object files, libraries, and compiled executables are put
into subdirectories.
2. The shared library is linked from individual object files.
This pr

Putting build artifacts in subdirectory.

1. Object files, libraries, and compiled executables are put
into subdirectories.
2. The shared library is linked from individual object files.
This provides for greater parallelism on large desktops
while at the same time making for easier builds on small
(i.e. embedded) systems. Fixes issue #279.
3. One program, db_bench, is compiled using the shared library.
4. The source file for "leveldbutil" was renamed from
leveldb_main.cc to leveldbutil.cc. This provides for simpler
makefile rules.
5. Because all targets placed the library (libleveldb.a) at the top
level, the last platform built (desktop/device) always overwrote
any prior artifact.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=113407013

show more ...

add travis build badge

Added a Travis CI build file.

This allows for continuous integration builds by travis-ci.org.
More information at https://docs.travis-ci.com/user/languages/cpp

Added a contributors section to README.md

In preparation for accepting GitHub pull requests this new README
section outlines the general criteria that the leveldb project owners
will use when accept

Added a contributors section to README.md

In preparation for accepting GitHub pull requests this new README
section outlines the general criteria that the leveldb project owners
will use when accepting external (and internal) project contributions.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=111349899

show more ...

Resolve race when getting approximate-memory-usage property

The write operations in the table happens without holding the mutex
lock, but concurrent writes are avoided using "writers_" queue.
The Ar

Resolve race when getting approximate-memory-usage property

The write operations in the table happens without holding the mutex
lock, but concurrent writes are avoided using "writers_" queue.
The Arena::MemoryUsage could access the blocks when write happens.
So, the memory usage is cached in atomic word and can be loaded
from any thread safely.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=107573379

show more ...

Only compiling TrimSpace on linux.

Incorporated change by zmodem at https://github.com/google/leveldb/pull/310
to fix issue #310.

This change will only build TrimSace on linux to avoid unused funct

Only compiling TrimSpace on linux.

Incorporated change by zmodem at https://github.com/google/leveldb/pull/310
to fix issue #310.

This change will only build TrimSace on linux to avoid unused function
warning/error.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=105323419

show more ...

Including atomic_pointer.h in port_posix

A recent CL (104348226) created the port_posix library, but omitted: port/atomic_pointer.h.

And when:

[] test third_party/leveldb:all

was run this err

Including atomic_pointer.h in port_posix

A recent CL (104348226) created the port_posix library, but omitted: port/atomic_pointer.h.

And when:

[] test third_party/leveldb:all

was run this error was reported:

//third_party/leveldb:port_posix does not depend on a
module exporting 'third_party/leveldb/port/atomic_pointer.h'
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=105243399

show more ...

Let LevelDB use xcrun to determine Xcode.app path instead of using a hardcoded path.

This allows build agents to select from multiple Xcode installations.
-------------
Created by MOE: https://githu

Let LevelDB use xcrun to determine Xcode.app path instead of using a hardcoded path.

This allows build agents to select from multiple Xcode installations.
-------------
Created by MOE: https://github.com/google/moe
MOE_MIGRATED_REVID=104859097

show more ...