`PrimeSieveBig()` can access past the final bucket at segment boundaries

Closed
  • Is something wrong?
#83 0 comments 0 reactions 1 assignee View on GitHub

@jwood000 is already working on this.

Since Oct 31, 2026.

Assessment

This issue has not been assessed yet.

Description

PrimeSieveBig() can schedule a composite beyond the requested upper bound into a bucket that does not exist, causing undefined behavior.

In

https://github.com/jwood000/RcppAlgos/blob/41d76201d4bd349c9287a81df1c9d2b2df9fa0f3/src/Eratosthenes.cpp#L447-L488

myRange includes the final requested position:

const int myRange = (maxNum - lowerBnd) + 1;

However, scheduling permits idx <= myRange + 1. The final valid requested offset is myRange - 1. Near a segment boundary, those extra positions can produce divTest == numCacheSegs, followed by an invalid access:

myBuckets[divTest].push_back(idx);

Reproduction

The following standalone program reproduces the problem using fixed thread/cache parameters:

#include "src/Eratosthenes.cpp"

int main() {
    std::vector<std::vector<double>> chunks(1);
    std::vector<double> output;
    bool parallel = false;

    PrimeSieve::PrimeSieveMain(
        chunks, output,
        1037517761278999LL, 1037517761279999LL,
        parallel, 1, 10, 1
    );
}

Save as /tmp/sieve-bucket-repro.cpp, then compile and run from the repository root:

clang++ -std=c++11 -O1 -g \
  -fsanitize=address,undefined -fno-omit-frame-pointer \
  -I. -Iinst/include /tmp/sieve-bucket-repro.cpp \
  -o /tmp/sieve-bucket-repro

/tmp/sieve-bucket-repro

Apple Clang 17 with AddressSanitizer confirmed a container-overflow in this native path.

Why this input triggers it

  • The segment size is 19,219,200, and one bucket is allocated.
  • The requested maximum has segment-relative offset segSize - 1.
  • The sieving prime 10,000,019 schedules the multiple
    10000019 × 103751579 = 1037517761280001.
  • That multiple has offset segSize + 1, which the current limit admits.
  • The resulting access is myBuckets[1], although only bucket 0 exists.

Public R dispatch depends on detected core/thread settings, so the native reproduction fixes those parameters explicitly.

Expected behavior and follow-up

  • Restrict scheduling to the inclusive requested interval and allocated buckets.
  • Add regression coverage around aligned final-segment boundaries.
  • Verify expected output and run the regression under sanitizers.
  • Keep this correctness fix separate from sieve performance changes.
Dominant language
C++
Stars
51
Forks
5
Avg merge
5h 49m
Merged PRs (30d)
7

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from jwood000/RcppAlgos

All issues in jwood000/RcppAlgos

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.