Whoops, missed a spot:
When you've processed the stuff reported in this thread before now,
recall that line about the lock only having to surround the sort() to
make the stuff threadsafe... ASSUMING a repeatable sort. (As in
parallel access fringe cases the 'sorted' flag can be read and found
to be false a few few times too many: 'repeatable' here means that an
already sorted stack will not change upon repeating the sort()
operation -- which WILL happen in this fringe case. (I remembered why
my kneejerk 'not threadsafe' wasn't all that dumb after all.)
Anyway, it so happens that sk_sort() employs qsort(), which, assuming
a quicksort implementation, is NOT repeatable. At least not for
collections, where multiple elements compare as 'equal' on the sort
key (qsort will arbitrarily re-order equal-key elements, depending on
where the splits occur this time around). And we have sk_find() and
sk_find_ex() with, tada! 'OBJ_BSEARCH_FIRST_VALUE_ON_MATCH' and
'OBJ_BSEARCH_VALUE_ON_NOMATCH' driving constants respectively,
instructing bsearch to find the 'first element with matching key K'
and 'any element with matching key K is fine' so the code is at least
expecting this case of multiple elements with same key in some
situations.
This means just critical-sectioning the sort() call is NOT enough - at
least for those stacks, where multiple elements with the very same key
are acceptable.
The trick here is to make sure that the is_sorted() operation (i.e.
checking the 'sorted' flag) PLUS the sort() TOGETHER are guaranteed
atomic: right now, any is_sorted() check while [q]sort() is running in
another thread, will ensure that the second thread, who did the
checking, will (correctly) see 'false', take the 'gotta sort' branch
in the code, run up to the lock and wait to do some repeated sort()ing
of its own once thread 1 is done - which will corrupt the find()
thread safety as qsort() is not guaranteed to be repeatable: as the
array is completely sorted on input to qsort() the second time around
(a condition not applying to the first round of [q]sort()), the splits
in qsort() will happen at different locations, resulting in equal-key
elements to be reshuffled in the second qsort().
Meanwhile, thread 1, now done sort()ing, does a bsearch() in that same
space. Of course, it doesn't really matter which element is found by
bsearch, but having its contents changed as it is swapped for another
equal-key element in the second thread's sort, means thread 1 will
access inconsistent data for the element found: this is not thread
safe.
Hence, x_crl.c is not how it should be done to be safe. Instead the
code flow should be this:
lock(l);
if ( ! is_locked())
{
sort();
sorted=1;
}
unlock(l);
bsearch();
inside internal_find().
That means each find() will lock and unlock, but in case of a fully
sorted stack, only very shortly: to check the 'locked' flag. This
approach should have an extremely minimal effect on performance:
multiple find(): bsearch()es can still run in parallel, and that where
the brunt of the find work is anyway.
--
Met vriendelijke groeten / Best regards,
Ger Hobbelt
--------------------------------------------------
web: http://www.hobbelt.com/
http://www.hebbut.net/
mail: [EMAIL PROTECTED]
mobile: +31-6-11 120 978
--------------------------------------------------
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [EMAIL PROTECTED]
