This is an automated email from the ASF dual-hosted git repository. asekretenko pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/mesos.git
The following commit(s) were added to refs/heads/master by this push: new 50b7299 Fixed a LevelDBStorage bug where positions would overflow. 50b7299 is described below commit 50b729904e4b4ed7964cd5f2ac8177bca5a5a72c Author: Charles-Francois Natali <cf.nat...@gmail.com> AuthorDate: Sun May 16 00:07:09 2021 +0100 Fixed a LevelDBStorage bug where positions would overflow. Positions were encoded with a width of 10, which limited the maximum position to 9'999'999'999. And actually the code suffered from overflow above INT32_MAX. In order to be backward compatible, we still encode positions up to 9'999'999'999 using a width of 10, however for positions above that, we switch to a width of 20 with the twist that we prepend 'A' in order to preserve lexicographic ordering. Here's what it looks like: 0000000000 ....... 9999999998 9999999999 A00000000010000000000 A00000000010000000001 The reason this works is because the only property which is required by the encoding function is that it is strictly monotonically increasing, i.e. if i < j, then encode(i) < encode(j) in lexicographic order. Closes #10216. --- src/log/leveldb.cpp | 39 ++++++++++++- src/tests/log_tests.cpp | 148 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 185 insertions(+), 2 deletions(-) diff --git a/src/log/leveldb.cpp b/src/log/leveldb.cpp index 72eeffb..7cb84bc 100644 --- a/src/log/leveldb.cpp +++ b/src/log/leveldb.cpp @@ -88,7 +88,10 @@ public: static string encode(uint64_t position, bool adjust = true) { // Adjusted stringified represenation is plus 1 of actual position. - position = adjust ? position + 1 : position; + if (adjust) { + CHECK_LT(position, UINT64_MAX); + position += 1; + } // TODO(benh): Use varint encoding for VarInt64Comparator! // string s; @@ -98,7 +101,31 @@ static string encode(uint64_t position, bool adjust = true) // stream.WriteVarint64(position); // return s; - Try<string> s = strings::format("%.*d", 10, position); + // Historically, positions were encoded with a width of 10, which limited the + // maximum position to 9'999'999'999. And actually the code suffered from + // overflow above INT32_MAX, see MESOS-10186. + // In order to be backward compatible, we still encode positions up to + // 9'999'999'999 using a width of 10, however for positions above that, we + // switch to a width of 20 with the twist that we prepend 'A' in order to + // preserve lexicographic ordering. Here's what it looks like: + // + // 0000000000 + // ....... + // 9999999998 + // 9999999999 + // A00000000010000000000 + // A00000000010000000001 + // + // The reason this works is because the only property which is required + // by the encoding function is that it is strictly monotonically increasing, + // i.e. if i < j, then encode(i) < encode(j) in lexicographic order. + Try<string> s = ""; + if (position <= 9999999999ull) { + s = strings::format("%.*llu", 10, position); + } else { + s = strings::format("A%.*llu", 20, position); + } + CHECK_SOME(s); return s.get(); } @@ -160,6 +187,14 @@ Try<Storage::State> LevelDBStorage::restore(const string& path) CHECK(leveldb::BytewiseComparator()->Compare(one, ten) < 0); CHECK(leveldb::BytewiseComparator()->Compare(ten, two) > 0); CHECK(leveldb::BytewiseComparator()->Compare(ten, ten) == 0); + CHECK(leveldb::BytewiseComparator()->Compare( + encode(9999999998), encode(9999999999)) < 0); + CHECK(leveldb::BytewiseComparator()->Compare( + encode(9999999999), encode(10000000000)) < 0); + CHECK(leveldb::BytewiseComparator()->Compare( + encode(10000000000), encode(UINT64_MAX - 2)) < 0); + CHECK(leveldb::BytewiseComparator()->Compare( + encode(UINT64_MAX - 2), encode(UINT64_MAX - 1)) < 0); Stopwatch stopwatch; stopwatch.start(); diff --git a/src/tests/log_tests.cpp b/src/tests/log_tests.cpp index a8980e3..94fca13 100644 --- a/src/tests/log_tests.cpp +++ b/src/tests/log_tests.cpp @@ -321,6 +321,154 @@ TYPED_TEST(LogStorageTest, TruncateWithManyHoles) } +TYPED_TEST(LogStorageTest, Overflow) +{ + // This test checks that the log storage correctly handles positions + // up to UINT64_MAX, see MESOS-10216. + // Specifically we check some values which would overflow when `encode` + // formatted them as signed integer, and collide with each other. + TypeParam storage; + + Try<Storage::State> state = storage.restore(os::getcwd() + "/.log"); + ASSERT_SOME(state); + + EXPECT_EQ(Metadata::EMPTY, state->metadata.status()); + EXPECT_EQ(0u, state->metadata.promised()); + EXPECT_EQ(0u, state->begin); + EXPECT_EQ(0u, state->end); + + // Note that position 0 is reserved so internally the positions below + // have 1 added to them before being encoded, see `encode`. + std::vector<uint64_t> positions{ + // The positions below are encoded using legacy + // 10-width format. + 0, + INT32_MAX - 1, + INT32_MAX, // Would overflow to INT32_MIN. + 2ull * INT32_MAX + 1, // Would overflow to 0. + 4ull * INT32_MAX + 3, // Would overflow to 0 as well. + UINT32_MAX - 1, + UINT32_MAX, + 9999999998, // 1 below legacy 10-width limit. + + // The positions below are encoded with new A+20-width + // format. + 9999999999, + 10000000000, + 9999999999 + 2 * (INT32_MAX + 1ull), + 10000000000 + 2 * (INT32_MAX + 1ull), + UINT64_MAX - 1 - 2 * (INT32_MAX + 1ull), + UINT64_MAX - 1, + }; + + foreach(uint64_t i, positions) { + Action action; + action.set_position(i); + action.set_promised(1); + action.set_performed(1); + action.set_learned(true); + action.set_type(Action::APPEND); + action.mutable_append()->set_bytes(stringify(i)); + + ASSERT_SOME(storage.persist(action)); + } + + foreach(uint64_t i, positions) { + Try<Action> action = storage.read(i); + ASSERT_SOME(action); + + EXPECT_EQ(i, action->position()); + EXPECT_EQ(1u, action->promised()); + EXPECT_EQ(1u, action->performed()); + EXPECT_TRUE(action->learned()); + EXPECT_EQ(Action::APPEND, action->type()); + ASSERT_TRUE(action->has_append()); + EXPECT_EQ(stringify(i), action->append().bytes()); + } +} + + +TYPED_TEST(LogStorageTest, OverflowTruncate) +{ + // Similar to test `Overflow` above, but here we test `truncate` + // which checks that the encoded positions are strictly monotonically + // increasing. + // The reason we check this in a separate test is that `truncate` + // requires iterating over positions from the first known position + // in the log, so the `Overflow` test above would take too long + // since it starts from 0. + TypeParam storage; + + Try<Storage::State> state = storage.restore(os::getcwd() + "/.log"); + ASSERT_SOME(state); + + EXPECT_EQ(Metadata::EMPTY, state->metadata.status()); + EXPECT_EQ(0u, state->metadata.promised()); + EXPECT_EQ(0u, state->begin); + EXPECT_EQ(0u, state->end); + + // Test positions around the legacy 10-width limit. + std::vector<uint64_t> positions{ + 9999999997, + 9999999998, + 9999999999, + 10000000000, + 10000000042, + }; + + foreach(uint64_t i, positions) { + Action action; + action.set_position(i); + action.set_promised(1); + action.set_performed(1); + action.set_learned(true); + action.set_type(Action::APPEND); + action.mutable_append()->set_bytes(stringify(i)); + + ASSERT_SOME(storage.persist(action)); + } + + // Truncate to position 9'999'999'999 (at position 10'000'000'000). + Action truncate; + truncate.set_position(10000000000ull); + truncate.set_promised(1); + truncate.set_performed(1); + truncate.set_learned(true); + truncate.set_type(Action::TRUNCATE); + truncate.mutable_truncate()->set_to(9999999999ull); + + ASSERT_SOME(storage.persist(truncate)); + + foreach(uint64_t i, positions) { + Try<Action> action = storage.read(i); + + if (i < 9999999999ull) { + // Position below 9'999'999'999 have been truncated. + EXPECT_ERROR(action); + } else if (i == 10000000000ull) { + // Position 10'000'000'000 is a truncate (to position + // 9'999'999'999). + EXPECT_EQ(i, action->position()); + EXPECT_EQ(1u, action->promised()); + EXPECT_EQ(1u, action->performed()); + EXPECT_TRUE(action->learned()); + EXPECT_EQ(Action::TRUNCATE, action->type()); + ASSERT_TRUE(action->has_truncate()); + EXPECT_EQ(9999999999ull, action->truncate().to()); + } else { + // Remaining positions have been preserved. + ASSERT_SOME(action); + EXPECT_EQ(i, action->position()); + EXPECT_EQ(1u, action->promised()); + EXPECT_EQ(1u, action->performed()); + EXPECT_TRUE(action->learned()); + EXPECT_EQ(Action::APPEND, action->type()); + ASSERT_TRUE(action->has_append()); + EXPECT_EQ(stringify(i), action->append().bytes()); + } + } +} + class ReplicaTest : public TemporaryDirectoryTest { protected: