basho/eleveldb — pull request #58 by nicad (2013-04-12 22:25:25+00:00)
Title: Fix race condition with thread direct work

I can see in production a case where threads get stuck doing eleveldb operations, they just never get a response from their async get or put.

You find a test program below to reproduce the problem (does it on a production server but not on my dev laptop).
Production:
* eleveldb: master from March 5th 2013
* OS: FreeBSD 9.1-PRERELEASE
* HW: amd64 32 CPUs,
* Erlang: r16 running with -zdbbl 16384 -swt medium -sbt tnnps -sbwt none -A 128

I tracked down the problem to a wrong assumption (or oversight) that if a thread is blocked in pthread_cond_wait and one thread does broadcast/unlock the next thread to get the lock is the one blocked, that's not a correct assumption.

The problem can happen with 3 threads:

thread A:
FindWaitingThread
sees worker thread B available, mark it as busy
doesn't lock mutex yet

thread B takes its lock
make itself as available
wait on cond var

thread C
FindWaitingThread
marks thread B as busy
takes mutex
set work
flag cond var

thread A can now take the lock
overwrite DirectWork
flag cond var

thread worker X gets out of cond_wait
marks itself not available
get the work of thread A, work of thread C will never be processed/replied to

Here is a test program that could reproduce the problem and confirmed the fix:

```erlang
-define(READ_OPTIONS, [{verify_checksums, false}, {fill_cache, true}]).
-define(WRITE_OPTIONS, [{sync, false}]).

-record( wstate, {
id,
controller_pid,
max_loops,
loops = 0,
ref
}).

stuck_worker(#wstate{loops = N, max_loops = N, controller_pid = CPID} = S) ->
CPID ! {done, S};
stuck_worker(#wstate{id = Id, loops = L, ref = Ref} = S) ->
Key = to_binary( pid_to_list(self()) ),
Value = to_binary(L),
WRatio = 100,
case L > 0 of
true ->
RV = to_binary( (L-1) - ( (L-1) rem WRatio) ),
{ok, RV} = eleveldb:get(Ref, Key, ?READ_OPTIONS);
_ ->
ok
end,
case (L rem WRatio) == 0 of
true ->
ok = eleveldb:put(Ref, Key, Value, ?WRITE_OPTIONS);
_ ->
ok
end,
case (L rem 100000) == 0 of
true ->
io:format("~p ~p done ~p iterations~n", [Id, self(), L]);
_ -> ok
end,
stuck_worker(S#wstate{loops = L + 1}).

stuck_test() ->
stuck_test(10, 10).

stuck_test(NProcs, Rounds) ->
os:cmd("rm -rf /tmp/eleveldb_stuck_test"),
{ok, Ref} = eleveldb:open("/tmp/eleveldb_stuck_test", [{create_if_missing, true}]),
ok = eleveldb:put(Ref, <<"abc">>, <<"123">>, []),
{ok, <<"123">>} = eleveldb:get(Ref, <<"abc">>, []),
not_found = eleveldb:get(Ref, <<"def">>, []),

WorkerState = #wstate{
controller_pid = self(),
max_loops = Rounds,
loops = 0,
ref = Ref
},
io:format("Spawn all: ~p~n", [NProcs]),
Workers = [ {N, spawn_link( ?MODULE, stuck_worker, [WorkerState#wstate{id = N}] )}
|| N <- lists:seq(1, NProcs)
],
io:format("All workers started, wait~n", []),
[
begin
io:format("wait for ~p pid=~p~n", [N, Pid]),
receive
{done, #wstate{id = N} = Info} ->
io:format("worker done: ~p~n", [Info])
%%Other ->
%%io:format("invalid response from worker: ~p~n", [Other])
end
end
|| {N, Pid} <- Workers
],
ok.

%% I could create the problem with just 100 processes and 5000 updates per thread
stuck_test(100, 1000*5).
```

While I completed agree with the need to avoid blocking the Erlang VM the current implementation is too complex, I'm pretty sure there are other bugs with this mix of locks and atomic variables:
* why not make eleveldb a driver ? it pretty much works like one, it would remove one layer to optimize from erlang app/erlang VM/eleveldb custom thread pool/leveldb threads/OS.
* should not have m_Available and m_DirectWork, just doing CAS on m_DirectWork is logically enough (setting it to NULL to indicate that the thread is available), I didn't get it to work due to my unfamiliarity with the ref counting scheme used (and didn't invest enough time)
* are the compare and swap/atomic variables really worth it ? or is it just that less code is executed than with the dequeue ? i.e. if an application gets into contention issues is it really benefiting from leveldb in the first place or should it just use an in-memory database ?

Hope I don't sound like complaining, I appreciate being able to use eleveldb, thanks for making it available. I just want it to be as good as possible.