Traceback allocation: 32-bit index guard validates the per-block size, one line before the total is formed

[sumitak12]

Traceback allocation: the 32-bit index guard validates the per-block size, one line before the total is formed

Summary

With -x (traceback/CIGAR output), wfa.affine.gpu fails with

Error cudaErrorIllegalAddress: an illegal memory access was encountered
  at lib/sequence_alignment.cu:353

on configurations whose per-block allocation is small but whose total allocation exceeds the
32-bit index range. allocate_offloaded_bt_d() contains a check for exactly this condition, but it
tests the per-block figure and then multiplies by num_blocks on the following line. Because
num_blocks scales with the device's SM count, wider devices cross the limit while the only
quantity actually validated stays small.

This is distinct from a genuine allocation failure, which this code reports correctly as
cudaErrorMemoryAllocation at lib/sequence_alignment.cu:56 and only at much larger ceilings.

The code

lib/wfa_types.h:

#define wfa_backtrace_bits 32
typedef uint32_t bt_prev_t;                       // the backtrace INDEX type
#define BT_OFFLOADED_ELEMENTS(s) (((s)*2+1) * ((s)*2 / (wfa_backtrace_bits/2)))

so the per-block backtrace store is quadratic in the declared ceiling, roughly s^2/4 elements.

lib/sequence_alignment.cu, allocate_offloaded_bt_d():

size_t bt_offloaded_size = BT_OFFLOADED_ELEMENTS(max_steps);
size_t max_addressable_elements = 1L << (sizeof(bt_prev_t) * 8);
if (bt_offloaded_size >= max_addressable_elements) {   // <-- checks PER-BLOCK
    LOG_ERROR(...);
    exit(-1);
}
bt_offloaded_size *= num_blocks;                        // <-- total formed AFTER the check

The intent of the guard is clear and correct; it simply runs against the wrong value.

Model, and how well it holds

Taking the total as

total_elements = BT_OFFLOADED_ELEMENTS(s) * num_blocks + RESULT_ELEMENTS(s) * n

and predicting failure once total_elements exceeds 2^31 (the effective limit under signed index
arithmetic) reproduces every observation we have, 11 of 11 cells:

device	blocks	ceiling	total / 2^31	predicted	observed
RTX PRO 6000 (188 SM)	376	1,174	0.08x	OK	OK
RTX PRO 6000	376	4,396	0.92x	OK	OK
RTX PRO 6000	376	4,918	1.12x	FAIL	illegal address
RTX PRO 6000	376	6,000	1.67x	FAIL	illegal address
RTX PRO 6000	376	8,908	3.53x	FAIL	illegal address
MIG 1g.24gb (46 SM)	92	4,396	0.27x	OK	OK
MIG 1g.24gb	92	4,918	0.29x	OK	OK
MIG 1g.24gb	92	6,000	0.47x	OK	OK
MIG 1g.24gb	92	8,908	0.87x	OK	OK
MIG 1g.24gb	92	15,154	2.48x	FAIL	illegal address
MIG 1g.24gb	92	19,372	4.14x	FAIL	illegal address

Note rows 2 and 3: the same device succeeds at 0.92x and fails at 1.12x.

It also explains the otherwise puzzling behaviour of -t. Raising threads-per-worker grows the
per-block allocation toward the real memory limit, while lowering it multiplies the block count
toward the index limit, so a working window can sit between two different ceilings. On GB10 at
ceiling 15,157, -t 1024 fails, -t 512 works, and -t 256 fails, with total threads constant
(workers x t = 49,152) across all three.

Practical consequence

Both parameters default silently: the ceiling from the first pair of the input file, and -t to
1024. On a real read set with a difficulty tail, the derived ceiling can be below the maximum score
in the file, and the default (ceiling, -t) pair is not guaranteed to lie in a working region. On
a 6,000-pair PacBio set at 13-15% divergence we found exactly one of twelve (ceiling, -t)
combinations both covered every pair and completed: -e 11000 -t 1024.

Reproduction

Two devices, two CUDA toolkits (12.x), same source line:

• NVIDIA RTX PRO 6000 Blackwell Server Edition, 188 SM, 97 GB
• NVIDIA GB10, 48 SM, unified memory

bin/wfa.affine.gpu -i <6000 pairs, max exact score 10036> -g 4,6,2 -b 10000 -e 12000 -t 1024 -x

Pair count is not a factor: 9,000 / 20,000 / 50,000 / 105,000 fail identically at fixed
(ceiling, -t). Batch size is not a factor where the combination works: 10,000 / 4,000 / 1,000 /
250 all succeed.

Suggested fix

Form the total first, then validate it:

size_t bt_offloaded_size = BT_OFFLOADED_ELEMENTS(max_steps) * num_blocks;
size_t max_addressable_elements = 1L << (sizeof(bt_prev_t) * 8);
if (bt_offloaded_size >= max_addressable_elements) { LOG_ERROR(...); exit(-1); }

Since indices appear to be used as signed in places, 2^31 may be the safer bound than 2^32. A
wider bt_prev_t would raise the ceiling but not remove the need for the check.

Every failure we observed was reported by CUDA rather than silent, so we are not claiming
incorrect output. But an out-of-bounds access in a traceback kernel is the class of defect that can
also read without faulting, so the check seems worth getting right.

Happy to test a patch on either device.