Integer underflow and buffer overrun in detail::count_rows on disconnected distance matrices

Open Beginner friendly
  • Is something wrong?
#3,192 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 3 days

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
72/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp, postgresql
Domain
backend

Research direction

Start in src/cpp_common/to_postgres.cpp at detail::count_rows, then read matrix_to_tuple and the pgr_alloc(tupcount, tuples) call that sizes the buffer. Replace the size subtraction with an explicit count of off-diagonal finite cells, as the issue proposes. Done when a unit test with a disconnected matrix (including an unreachable diagonal) gets the correct row count and no buffer overrun.

Written by the indexing model from the issue text.

Description

Integer underflow and buffer overrun in detail::count_rows on disconnected or sparse distance matrices

Description

In src/cpp_common/to_postgres.cpp, detail::count_rows calculates the number of valid off-diagonal entries in an all-pairs distance matrix (pgr_johnson, pgr_floydWarshall):

size_t
count_rows(const std::vector<std::vector<double>> &matrix) {
    int64_t count = 0;
    for (size_t i = 0; i < matrix.size(); i++) {
        count += std::count_if(
                matrix[i].begin(), matrix[i].end(),
                [](double value) {
                return value != (std::numeric_limits<double>::max)();
                });
    }
    return static_cast<size_t>(count) - matrix.size();
}

This implementation assumes that every diagonal entry matrix[i][i] is non-infinity (!= max()) and is counted in count. However, on disconnected graphs, sparse inputs, or subgraphs with unreachable self-distances:

  1. Underallocation & Buffer Overrun: If any diagonal entry equals max(), count did not include that cell, yet matrix.size() is still subtracted. As a result, count_rows returns fewer rows than the actual number of valid off-diagonal pairs. matrix_to_tuple then iterates over all valid off-diagonal entries and writes past the end of the tuples buffer allocated by pgr_alloc(tupcount, tuples), resulting in memory corruption.

  2. Unsigned Integer Underflow: If count < matrix.size() (for example, on an empty or largely unreachable graph where fewer than N cells are finite), static_cast<size_t>(count) - matrix.size() underflows unsigned subtraction to a huge value (~1.84e19). pgr_alloc then attempts to allocate an astronomical amount of memory, terminating the PostgreSQL backend process with an out-of-memory error.

Expected Behavior

count_rows should count exactly the valid off-diagonal cells (i != j && matrix[i][j] != max()) without underflowing or underallocating.

Proposed Solution

Replace the subtraction assumption with an explicit off-diagonal count:

size_t
count_rows(const std::vector<std::vector<double>> &matrix) {
    size_t count = 0;
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {
            if (i != j && matrix[i][j] != (std::numeric_limits<double>::max)()) {
                ++count;
            }
        }
    }
    return count;
}

I can open a PR with this fix and a unit test covering disconnected matrices.

Dominant language
C++
Stars
1.4k
Forks
397
Avg merge
2d 16h
Merged PRs (30d)
8

Getting set up

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 pgRouting/pgrouting

All issues in pgRouting/pgrouting

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.