Issue 44 in leveldb: reappearing "ghost" key after 17 steps
lev...@googlecode.com
Owner: ----
Labels: Type-Defect Priority-Medium
New issue 44 by nor...@alum.mit.edu: reappearing "ghost" key after 17 steps
http://code.google.com/p/leveldb/issues/detail?id=44
I'm testing an Erlang-based API for leveldb via an Erlang NIF written in
C++. The test model is written in Erlang with the help of the test tool
QuickCheck. The test model and test tool have found a failing minimal test
case of 17 steps that appears (but not proven yet) to be an issue with
leveldb.
I tried to manually create a minimal failing example that in pure C++.
Unfortunately, I am unable to reproduce the issue with a pure C++ test case.
I attached the failing counterexample case and leveldb data directory after
closing of the database. I'm hoping the leveldb authors might be able to
pinpoint the issue or provide some instructions on how to troubleshoot this
issue.
What steps will reproduce the problem?
1. open new database
2. put key1 and val1
3. close database
4. open database
5. delete key2
6. delete key1
7. close database
8. open database
9. delete key2
10. close database
11. open database
12. put key3 and val1
13. close database
14. open database
15. close database
16. open database
17. seek first
What is the expected output? key3 at step 17
What do you see instead? key1 at step 17
> foobar:test().
<<10,0,0,0,12>>/'$end_of_table': [{obj,6,0}]
'$end_of_table'/'$end_of_table': []
'$end_of_table'/'$end_of_table': []
<<18,193,216,96,0,8>>/'$end_of_table': [{obj,6,0}]
<<18,193,216,96,0,8>>/'$end_of_table': [{obj,6,0}]
<<10,0,0,0,12>>/<<18,193,216,96,0,8>>: [{obj,6,0},{obj,6,0}]
ok
What version of the product are you using? On what operating system?
commit 26db4d971a15d2a7d45bef73f69ef527d164b340
Author: Hans Wennborg <ha...@chromium.org>
Date: Mon Sep 26 17:37:09 2011 +0100
The issue repeats on MacOS X Lion and Fedora 15.
Please provide any additional information below.
The following shutdown sequence is performed at the time of closing the
database:
leveldb::WriteOptions db_write_options;
leveldb::WriteBatch batch;
leveldb::Status status;
db_write_options.sync = true;
status = h->db->Write(db_write_options, &batch);
if (!status.ok()) {
return MAKEBADARG(env, status);
}
delete h->db;
h->db = NULL;
Attachments:
lets.tgz 3.2 KB
lev...@googlecode.com
Comment #1 on issue 44 by sanjay.g...@gmail.com: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
Do you have a C++ program that demonstrates the bug?
PS. Your erlang test ends with:
Key1 = lets_nif:impl_first(Tab6),
That seems to be checking that the result of step 17 is key1.
I presume you used to check
Key3 = ...
and this change to Key1 is just to make the test pass in the
presence of a bug in leveldb or your erlang wrapper? Or did
you just have a typo in the test and everything is actually
working correctly.
I tried emulating your program as a new test case in
leveldb/db/db_test.cc, and that test passed:
TEST(DBTest, ReopenMultipleTimes) {
std::string key1("\x0a\x00\x00\x00\x0c", 5);
std::string key2 = std::string("\x0a\x00\x00\x00\x01\x80", 6)
+ std::string(152, '2');
std::string key3("\x12\xc1\xd8\x60\x00\x08", 6);
std::string val = std::string("\x10\x00\x00\x00", 4) +
std::string(17, '1');
ASSERT_OK(Put(key1, val));
Reopen();
ASSERT_OK(Delete(key2));
ASSERT_OK(Delete(key1));
Reopen();
ASSERT_OK(Delete(key2));
Reopen();
ASSERT_OK(Put(key3, val));
Reopen();
Reopen();
Iterator* iter = db_->NewIterator(ReadOptions());
iter->SeekToFirst();
ASSERT_EQ(key3, iter->key().ToString());
ASSERT_EQ(val, iter->value().ToString());
delete iter;
}
lev...@googlecode.com
Comment #2 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
Yes, I used key1 to make the test pass.
I created a C++ program by hand to repeat the issue but unfortunately I was
unable to repeat the problem.
I need to spend more time to see how I can repeat the issue using only the
c and/or c++ leveldb API.
Is there any debug or verbose mode that I can enable to trace the low level
behavior of leveldb?
Sanjay Ghemawat
While making an unrelated change, I found and fixed a bug that could
explain the behavior you are seeing. The release for that should be out in
a few days. You might want to not waste too much time trying to reproduce
the failure until that release is out.
I don't have a simple patch since there are a series of changes that
all touch the affected part of the code base.
Joseph Norton
Ok, thanks for the head up.
In the meantime, I'll spend my time to build a new test model for leveldb's C api. This will make it easy to repeat test cases and issues with only leveldb's C api.
Joseph Norton
nor...@alum.mit.edu
Joseph Norton
Sanjay -
I created a new test model specifically for leveldb's C api. This test model can reproduce this issue just like the other model but after 16 steps. It takes a few minutes for QuickCheck to identify the failing test case and then shrink the failing test case to this minimal test case. Please see the attached log for details.
regards,
- Joe N.
[{init,{state,qc_statemc_lets,{state,false,false,undefined,[]}}},
{set,{var,1},{call,qc_leveldb,open,[]}},
{set,{var,2},{call,qc_leveldb,put,[{var,1},{obj,<<"{">>,<<>>}]}},
{set,{var,5},{call,qc_leveldb,close,[{var,1}]}},
{set,{var,6},{call,qc_leveldb,reopen,[]}},
{set,{var,10},{call,qc_leveldb,delete,[{var,6},<<18>>]}},
{set,{var,20},{call,qc_leveldb,close,[{var,6}]}},
{set,{var,21},{call,qc_leveldb,reopen,[]}},
{set,{var,25},{call,qc_leveldb,put,[{var,21},{obj,<<"0%E0<!">>,<<>>}]}},
{set,{var,27},{call,qc_leveldb,delete,[{var,21},<<17,11,41>>]}},
{set,{var,29},{call,qc_leveldb,close,[{var,21}]}},
{set,{var,30},{call,qc_leveldb,reopen,[]}},
{set,{var,35},{call,qc_leveldb,delete,[{var,30},<<"{">>]}},
{set,{var,39},{call,qc_leveldb,delete,[{var,30},<<"0%E0<!">>]}},
{set,{var,40},{call,qc_leveldb,close,[{var,30}]}},
{set,{var,41},{call,qc_leveldb,reopen,[]}},
{set,{var,42},{call,qc_leveldb,next,[{var,41},<<>>]}}]
Sanjay Ghemawat
> Status: New
> Owner: ----
> Labels: Type-Defect Priority-Medium
>
> New issue 44 by nor...@alum.mit.edu: reappearing "ghost" key after 17 steps
> http://code.google.com/p/leveldb/issues/detail?id=44
>
> I'm testing an Erlang-based API for leveldb via an Erlang NIF written in
> C++. The test model is written in Erlang with the help of the test tool
> QuickCheck. The test model and test tool have found a failing minimal test
> case of 17 steps that appears (but not proven yet) to be an issue with
> leveldb.
Change 299ccedfeca1 on oct 15 should have fixed this bug.
lev...@googlecode.com
Comment #3 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
As a follow-up, the test used to find this bug has been uploaded to GitHub.
There is also a simpler version that can repeat the behavior using
leveldb's c bindings.
https://github.com/norton/lets/blob/master/test/qc/qc_statem_lets.erl
https://github.com/norton/lets/blob/leveldb-issue44/test/qc/qc_statemc_lets.erl
Sanjay Ghemawat
Did change 299ccedfeca1 on oct 15 not fix this bug?
lev...@googlecode.com
Comment #4 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
The problem hasn't been fixed. I'm testing against the following version
of leveldb. It is dated Oct 5 and not Oct 15. I was (mistakenly) waiting
for the next release.
https://github.com/norton/leveldb/commits/master
commit 299ccedfeca1fb3497978c288e76008a5c08e899
Author: Gabor Cselle <ga...@google.com>
Date: Wed Oct 5 16:30:28 2011 -0700
Sanjay Ghemawat
I was confused about the date for some reason. That release is the one.
Are you saying that that release does not work? It contains the following test
which used to fail before the release and works afterwards.
db/db_test.cc:
...
TEST(DBTest, OverlapInLevel0) {
...
Joseph Norton
On Oct 27, 2011, at 1:00 AM, Sanjay Ghemawat wrote:
> I was confused about the date for some reason. That release is the one.
> Are you saying that that release does not work?
Yes, I'm still seeing the same behavior as a previous release.
> It contains the following test
> which used to fail before the release and works afterwards.
>
> db/db_test.cc:
> ...
> TEST(DBTest, OverlapInLevel0) {
> ...
Yes, it contains this test.
https://github.com/norton/leveldb/blob/master/db/db_test.cc#L1012
Do you have any suggestions?
thanks,
Joseph Norton
nor...@alum.mit.edu
Sanjay Ghemawat
I couldn't find any C program in that repository that I could use to
reconstruct the
problem, just some erlang code. I can't help any more until there is
a way for me to
reproduce the problem with a short C or C++ program that runs against
the supplied
leveldb code.
lev...@googlecode.com
Comment #5 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
Sanjay -
I constructed a failing C test case to mimic the original QuickCheck Erlang
counterexample. Please see the Makefile for details on how to build and to
run.
https://github.com/norton/lets/blob/leveldb-issue44/priv/test/qc_leveldb_issue44.c
[(leveldb-issue44)]$ pwd
<working-directory>/lets/priv/test
[(leveldb-issue44)]$ make clean all; ./qc_leveldb_issue44
rm -rf *.o qc_leveldb
gcc -c -Wall -I ../../c_src/leveldb/include qc_statemc_lets.c -o
qc_statemc_lets.o
gcc -c -Wall -I ../../c_src/leveldb/include qc_leveldb_issue44.c -o
qc_leveldb_issue44.o
gcc qc_statemc_lets.o
qc_leveldb_issue44.o ../../c_src/leveldb/lib/libleveldb.a ../../c_src/snappy/lib/libsnappy.a
-lstdc++ -lpthread -o qc_leveldb_issue44
!!! NO - reappearing ghost key 'g' !!!
KEY POINT => sleep for background compaction to finish it's work
!!! YES - reappearing ghost key 'g' !!!
qc_leveldb_issue44: qc_leveldb_issue44.c:115: main: Assertion `buglen ==
nillen' failed.
Aborted
Sanjay Ghemawat
> counterexample. Please see the Makefile for details on how to build and to
> run.
Thanks. That was very helpful. I have a fix that will hopefully get submitted
in a few days. If you want to try it out, try applying the following change to
version_set.cc:
diff --git a/db/version_set.cc b/db/version_set.cc
index 8b96af0..63f4cd4 100644
--- a/db/version_set.cc
+++ b/db/version_set.cc
@@ -1179,13 +1179,19 @@ Compaction* VersionSet::PickCompaction() {
// Files in level 0 may overlap each other, so pick up all overlapping ones
if (level == 0) {
- InternalKey smallest, largest;
- GetRange(c->inputs_[0], &smallest, &largest);
- // Note that the next call will discard the file we placed in
- // c->inputs_[0] earlier and replace it with an overlapping set
- // which will include the picked file.
- current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
- assert(!c->inputs_[0].empty());
+ // Loop until we stop picking up new files since adding new files may
+ // change the range we are compacting.
+ int old_size = 1;
+ do {
+ old_size = c->inputs_[0].size();
+ InternalKey smallest, largest;
+ GetRange(c->inputs_[0], &smallest, &largest);
+ // Note that the next call will discard the file we placed in
+ // c->inputs_[0] earlier and replace it with an overlapping set
+ // which will include the picked file.
+ current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
+ assert(!c->inputs_[0].empty());
+ } while (c->inputs_[0].size() > old_size);
}
SetupOtherInputs(c);
Joseph Norton
I tried the patch but I didn't see any change in behavior.
Joseph Norton
Sorry, I was mistaken. The patch seems to work well.
https://github.com/norton/lets/commit/23698aa66f578ddba1cf907bf6a423293f3bdf5c
thanks,
Joseph Norton
nor...@alum.mit.edu
lev...@googlecode.com
Comment #6 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
Sanjay -
The previous patch did fix the previous issue. However, a new
counterexample in 31 steps was found (and is repeatable). The failing post
condition is same as previous issue - a reappearing ghost key.
[{init,{state,qc_statemc_lets,{state,false,false,undefined,[]}}},
{set,{var,1},{call,qc_leveldb,open,[]}},
{set,{var,3},{call,qc_leveldb,close,[{var,1}]}},
{set,{var,4},{call,qc_leveldb,reopen,[]}},
{set,{var,5},{call,qc_leveldb,put,[{var,4},{obj,<<>>,<<>>}]}},
{set,{var,7},{call,qc_leveldb,close,[{var,4}]}},
{set,{var,11},{call,qc_leveldb,reopen,[]}},
{set,{var,16},{call,qc_leveldb,delete,[{var,11},<<"~88I.1">>]}},
{set,{var,19},{call,qc_leveldb,put,[{var,11},{obj,<<>>,<<>>}]}},
{set,{var,25},{call,qc_leveldb,close,[{var,11}]}},
{set,{var,29},{call,qc_leveldb,reopen,[]}},
{set,{var,30},
{call,qc_leveldb,put,
[{var,29},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,127>>,
<<95,78,70,31,26>>}]}},
{set,{var,33},{call,qc_leveldb,close,[{var,29}]}},
{set,{var,34},{call,qc_leveldb,reopen,[]}},
{set,{var,35},{call,qc_leveldb,put,[{var,34},{obj,<<>>,<<>>}]}},
{set,{var,46},{call,qc_leveldb,close,[{var,34}]}},
{set,{var,47},{call,qc_leveldb,reopen,[]}},
{set,{var,49},{call,qc_leveldb,put,[{var,47},{obj,<<>>,<<>>}]}},
{set,{var,50},{call,qc_leveldb,close,[{var,47}]}},
{set,{var,51},{call,qc_leveldb,reopen,[]}},
{set,{var,52},{call,qc_leveldb,put,[{var,51},{obj,<<"l\r%`}Yc">>,<<>>}]}},
{set,{var,53},{call,qc_leveldb,close,[{var,51}]}},
{set,{var,54},{call,qc_leveldb,reopen,[]}},
{set,{var,56},{call,qc_leveldb,put,[{var,54},{obj,<<>>,<<>>}]}},
{set,{var,60},{call,qc_leveldb,close,[{var,54}]}},
{set,{var,61},{call,qc_leveldb,reopen,[]}},
{set,{var,62},{call,qc_leveldb,delete,[{var,61},<<"l\r%`}Yc">>]}},
{set,{var,64},
{call,qc_leveldb,delete,[{var,61},<<77,99,17,98,63,58,96,106,22,21>>]}},
{set,{var,65},{call,qc_leveldb,close,[{var,61}]}},
{set,{var,66},{call,qc_leveldb,reopen,[]}},
{set,{var,69},{call,qc_leveldb,delete,[{var,66},<<2,74,62,26>>]}},
{set,{var,72},{call,qc_leveldb,last,[{var,66}]}}]
COMMANDS:
"qc_statem-20111030-212350.erl"
HISTORY:
#1:
Cmd: {set,{var,1},{call,qc_leveldb,open,[]}}
Reply: {ptr,{struct,leveldb_t},34376672}
State: {state,qc_statemc_lets,{state,false,false,undefined,[]}}
#2:
Cmd: {set,{var,3},{call,qc_leveldb,close,[{var,1}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,{ptr,{struct,leveldb_t},34376672},[]}}
#3:
Cmd: {set,{var,4},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34376784}
State: {state,qc_statemc_lets,{state,false,true,undefined,[]}}
#4:
Cmd: {set,{var,5},{call,qc_leveldb,put,[{var,4},{obj,<<>>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,{ptr,{struct,leveldb_t},34376784},[]}}
#5:
Cmd: {set,{var,7},{call,qc_leveldb,close,[{var,4}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34376784},
[{obj,<<>>,<<>>}]}}
#6:
Cmd: {set,{var,11},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34374432}
State: {state,qc_statemc_lets,
{state,false,true,undefined,[{obj,<<>>,<<>>}]}}
#7:
Cmd: {set,{var,16},{call,qc_leveldb,delete,[{var,11},<<"~88I.1">>]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374432},
[{obj,<<>>,<<>>}]}}
#8:
Cmd: {set,{var,19},{call,qc_leveldb,put,[{var,11},{obj,<<>>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374432},
[{obj,<<>>,<<>>}]}}
#9:
Cmd: {set,{var,25},{call,qc_leveldb,close,[{var,11}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374432},
[{obj,<<>>,<<>>}]}}
#10:
Cmd: {set,{var,29},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34375728}
State: {state,qc_statemc_lets,
{state,false,true,undefined,[{obj,<<>>,<<>>}]}}
#11:
Cmd: {set,{var,30},
{call,qc_leveldb,put,
[{var,29},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,127>>,
<<95,78,70,31,26>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34375728},
[{obj,<<>>,<<>>}]}}
#12:
Cmd: {set,{var,33},{call,qc_leveldb,close,[{var,29}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34375728},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#13:
Cmd: {set,{var,34},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34413600}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#14:
Cmd: {set,{var,35},{call,qc_leveldb,put,[{var,34},{obj,<<>>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34413600},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#15:
Cmd: {set,{var,46},{call,qc_leveldb,close,[{var,34}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34413600},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#16:
Cmd: {set,{var,47},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34376640}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#17:
Cmd: {set,{var,49},{call,qc_leveldb,put,[{var,47},{obj,<<>>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34376640},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#18:
Cmd: {set,{var,50},{call,qc_leveldb,close,[{var,47}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34376640},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#19:
Cmd: {set,{var,51},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34370688}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#20:
Cmd: {set,{var,52},
{call,qc_leveldb,put,[{var,51},{obj,<<"l\r%`}Yc">>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34370688},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#21:
Cmd: {set,{var,53},{call,qc_leveldb,close,[{var,51}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34370688},
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#22:
Cmd: {set,{var,54},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34370656}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#23:
Cmd: {set,{var,56},{call,qc_leveldb,put,[{var,54},{obj,<<>>,<<>>}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34370656},
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#24:
Cmd: {set,{var,60},{call,qc_leveldb,close,[{var,54}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34370656},
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#25:
Cmd: {set,{var,61},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34415328}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#26:
Cmd:
{set,{var,62},{call,qc_leveldb,delete,[{var,61},<<"l\r%`}Yc">>]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34415328},
[{obj,<<"l\r%`}Yc">>,<<>>},
{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#27:
Cmd: {set,{var,64},
{call,qc_leveldb,delete,
[{var,61},<<77,99,17,98,63,58,96,106,22,21>>]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34415328},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#28:
Cmd: {set,{var,65},{call,qc_leveldb,close,[{var,61}]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34415328},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#29:
Cmd: {set,{var,66},{call,qc_leveldb,reopen,[]}}
Reply: {ptr,{struct,leveldb_t},34374880}
State: {state,qc_statemc_lets,
{state,false,true,undefined,
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#30:
Cmd:
{set,{var,69},{call,qc_leveldb,delete,[{var,66},<<2,74,62,26>>]}}
Reply: true
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374880},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
#31:
Cmd: {set,{var,72},{call,qc_leveldb,last,[{var,66}]}}
Reply: <<"l\r%`}Yc">>
State: {state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374880},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,
127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
RESULT:
{postcondition,false}
STATE:
{state,qc_statemc_lets,
{state,false,true,
{ptr,{struct,leveldb_t},34374880},
[{obj,<<98,66,22,50,78,96,90,21,61,48,126,34,1,65,127>>,
<<95,78,70,31,26>>},
{obj,<<>>,<<>>}]}}
STATE IS SANE:
true
false
Sanjay Ghemawat
>
> Comment #6 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key after
> 17 steps
> http://code.google.com/p/leveldb/issues/detail?id=44
>
> Sanjay -
>
> The previous patch did fix the previous issue. However, a new
> counterexample in 31 steps was found (and is repeatable). The failing post
> condition is same as previous issue - a reappearing ghost key.
Thanks for trying out the fix. That fix was in the wrong place. It only
covered one out of three compaction paths. Can you try the following
change (and remove the previous fix I sent)?
Replace the definition of Version::GetOverlappingFiles in version_set.cc with:
// Store in "*inputs" all files in "level" that overlap [begin,end]
void Version::GetOverlappingInputs(
int level,
const InternalKey* begin,
const InternalKey* end,
std::vector<FileMetaData*>* inputs) {
inputs->clear();
Slice user_begin, user_end;
if (begin != NULL) {
user_begin = begin->user_key();
}
if (end != NULL) {
user_end = end->user_key();
}
const Comparator* user_cmp = vset_->icmp_.user_comparator();
for (size_t i = 0; i < files_[level].size(); ) {
FileMetaData* f = files_[level][i++];
const Slice file_start = f->smallest.user_key();
const Slice file_limit = f->largest.user_key();
if (begin != NULL && user_cmp->Compare(file_limit, user_begin) < 0) {
// "f" is completely before specified range; skip it
} else if (end != NULL && user_cmp->Compare(file_start, user_end) > 0) {
// "f" is completely after specified range; skip it
} else {
inputs->push_back(f);
if (level == 0) {
// Level-0 files may overlap each other. So check if the newly
// added file has expanded the range. If so, restart search.
if (begin != NULL && user_cmp->Compare(file_start, user_begin) < 0) {
user_begin = file_start;
inputs->clear();
i = 0;
} else if (end != NULL && user_cmp->Compare(file_limit, user_end) > 0) {
user_end = file_limit;
inputs->clear();
i = 0;
}
}
}
}
}
Joseph Wayne Norton
The 2nd patch works well so far.
https://github.com/norton/lets/commit/83a898b97c134441fab4732772e342c003108ca5
If you are interested in running these tests on your own, see https://github.com/norton/lets for instructions. See https://github.com/norton/qc for links to QuickCheck and PropEr testing tools. It is also worth mentioning that the total number of lines codes for these two tests is ~500 lines.
$ cloc-1.55.pl test/qc/qc_statem_lets.erl
1 text file.
1 unique file.
0 files ignored.
http://cloc.sourceforge.net v 1.55 T=0.5 s (2.0 files/s, 896.0 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
Erlang 1 63 46 339
-------------------------------------------------------------------------------
$ cloc-1.55.pl test/qc/qc_statemc_lets.erl
1 text file.
1 unique file.
0 files ignored.
http://cloc.sourceforge.net v 1.55 T=0.5 s (2.0 files/s, 474.0 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
Erlang 1 41 33 163
-------------------------------------------------------------------------------
Joseph Wayne Norton
nor...@alum.mit.edu
Sanjay Ghemawat
git commit 36a5f8ed7f9f / SVN r54
I will keep quickcheck in mind when I get some spare time to think
about more thorough testing.
lev...@googlecode.com
Comment #7 on issue 44 by nor...@alum.mit.edu: reappearing "ghost" key
http://code.google.com/p/leveldb/issues/detail?id=44
Please close this issue - thanks!
lev...@googlecode.com
Status: Done
Comment #8 on issue 44 by dgr...@chromium.org: reappearing "ghost" key
after 17 steps
http://code.google.com/p/leveldb/issues/detail?id=44
(No comment was entered for this change.)