Package: src:jellyfish
Version: 2.3.1-6
User: [email protected]
Usertags: python3.15-default
Tags: patch, ftbfs, forky, sid
Severity: important
Hi!
While rebuilding the python related packages against the Python 3.15rc2
as the default version we found that jellyfish fails to build from
source [1].
This is the error:
AIL: test_add (__main__.TestHashCounter.test_add)
Traceback (most recent call last):
File
"/build/reproducible-path/jellyfish-2.3.1/swig/python/test_hash_counter.py",
line 43, in test_add
self.assertTrue(good)
AssertionError: False is not true
This failure is only present in arm64, and it happens when adding a
value that is an exact multiple of 2^val_len (where lower bits are 0),
an overflow on the large-value carry produced carry_shift == v. This
caused hash_counter::add to incorrectly assume the key was never
claimed, resulting in false duplicate detection (is_new = false) and
duplicate additions after size doubling.
I've created a patch that explicitly tracks whether the key was
claimed/found in large_hash_array instead of guessing via carry_shift ==
v. And I've also added a regression test. I've sent this patch upstream
as PR#214
I've applied this fix in the sandbox [3] to verify that it builds
successfully, please consider applying the patch to support the upcoming
3.15 version.
Setting the severity to important for now. Once Python 3.15 becomes the
default Python version this bug will become release critical.
Happy hacking,
[1]: https://debusine.debian.net/debian/r-python-python3.15/artifact/4704166/
[2]: https://github.com/gmarcais/Jellyfish/pull/214
[3]: https://debusine.debian.net/debian/r-python-python3.15/
--
"Can you imagine what I would do if I could do all I can?" -- Sun Tzu
Saludos /\/\ /\ >< `/
Description: Fix key claim tracking during hash resizing on carry overflow
When a value is a multiple of 2^val_len and overflows to carry during insertion,
carry_shift equals the original value even though the key was claimed and its
lower bits stored. Track key claim status explicitly to prevent duplicate adds
and incorrect is_new return values after table resizing.
Author: Maximiliano Curia <[email protected]>
Forwarded: no
Index: jellyfish/include/jellyfish/hash_counter.hpp
===================================================================
--- jellyfish.orig/include/jellyfish/hash_counter.hpp
+++ jellyfish/include/jellyfish/hash_counter.hpp
@@ -97,16 +97,17 @@ public:
// while(!ary_->add(k, v, &carry_shift, is_new_ptr, id_ptr)) {
while(true) {
- if(ary_->add(k, v, &carry_shift, is_new_ptr, id_ptr)) break;
+ bool key_claimed = false;
+ if(ary_->add(k, v, &carry_shift, is_new_ptr, id_ptr, &key_claimed)) break;
handle_full_ary();
- // If carry_shift == v, failed to allocate the first field for
+ // If !key_claimed, failed to allocate the first field for
// key, hence status of is_new and value for id are not
- // determined yet. On the other hand, if carry_shift < v, we
+ // determined yet. On the other hand, if key_claimed is true, we
// failed while adding extra field for large key, so the status
// of is_new and value of id are known. We do not update them in future
// calls.
- if(carry_shift != v) {
+ if(key_claimed) {
is_new_ptr = &is_new_void;
id_ptr = &id_void;
v = carry_shift;
@@ -156,9 +157,10 @@ public:
uint64_t carry_shift = 0;
while(true) {
- if(ary_->update_add(k, v, &carry_shift, tmp_key))
+ bool key_found = false;
+ if(ary_->update_add(k, v, &carry_shift, tmp_key, &key_found))
return true;
- if(carry_shift == v)
+ if(!key_found)
return false;
handle_full_ary();
v = carry_shift;
Index: jellyfish/include/jellyfish/large_hash_array.hpp
===================================================================
--- jellyfish.orig/include/jellyfish/large_hash_array.hpp
+++ jellyfish/include/jellyfish/large_hash_array.hpp
@@ -288,10 +288,11 @@ public:
* proper size doubling is perform, one need to call add again with
* val set to carry_shift.
*/
- inline bool add(const key_type& key, mapped_type val, word* carry_shift, bool* is_new, size_t* id) {
+ inline bool add(const key_type& key, mapped_type val, word* carry_shift, bool* is_new, size_t* id, bool* key_claimed = 0) {
uint64_t hash = hash_matrix_.times(key);
*carry_shift = 0;
- return add_rec(hash & size_mask_, key, val, false, is_new, id, carry_shift);
+ if(key_claimed) *key_claimed = false;
+ return add_rec(hash & size_mask_, key, val, false, is_new, id, carry_shift, key_claimed);
}
inline bool add(const key_type& key, mapped_type val, word* carry_shift) {
@@ -332,12 +333,14 @@ public:
// Optimization. Use tmp_key as buffer. Avoids allocation if update_add is called repeatedly.
- bool update_add(const key_type& key, mapped_type val, word* carry_shift, key_type& tmp_key) {
+ bool update_add(const key_type& key, mapped_type val, word* carry_shift, key_type& tmp_key, bool* key_found = 0) {
size_t id;
word* w;
const offset_t* o;
+ if(key_found) *key_found = false;
if(get_key_id(key, &id, tmp_key, (const word**)&w, &o)) {
+ if(key_found) *key_found = true;
*carry_shift = 0;
return add_rec_at(id, key, val, o, w, carry_shift);
} else {
@@ -654,24 +657,27 @@ public:
// carry_shift is properly set to the value of the carry shifted by
// the right number of bits so a further call to add with
// carry_shift as val finishes the operation.
- bool add_rec(size_t id, const key_type& key, word val, bool large, bool* is_new, size_t* eid, word* carry_shift) {
+ bool add_rec(size_t id, const key_type& key, word val, bool large, bool* is_new, size_t* eid, word* carry_shift, bool* key_claimed = 0) {
const offset_t *ao = 0;
word *w = 0;
bool claimed = false;
if(large)
claimed = claim_large_key(&id, &ao, &w);
- else
+ else {
claimed = claim_key(key, is_new, &id, &ao, &w);
+ if(claimed && key_claimed)
+ *key_claimed = true;
+ }
if(!claimed) {
*carry_shift = val << (*carry_shift);
return false;
}
*eid = id;
- return add_rec_at(id, key, val, ao, w, carry_shift);
+ return add_rec_at(id, key, val, ao, w, carry_shift, key_claimed);
}
- bool add_rec_at(size_t id, const key_type& key, word val, const offset_t* ao, word* w, word* carry_shift) {
+ bool add_rec_at(size_t id, const key_type& key, word val, const offset_t* ao, word* w, word* carry_shift, bool* key_claimed = 0) {
// Increment value
word *vw = w + ao->val.woff;
word cary = add_val(vw, val, ao->val.boff, ao->val.mask1);
@@ -690,7 +696,7 @@ public:
id = (id + reprobes_[0]) & size_mask_;
size_t ignore_eid;
bool ignore_is_new;
- return add_rec(id, key, cary, true, &ignore_is_new, &ignore_eid, carry_shift);
+ return add_rec(id, key, cary, true, &ignore_is_new, &ignore_eid, carry_shift, key_claimed);
// // Adding failed, table is full. Need to back-track and
// // substract val.
