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

未关闭 适合新手
  • 哪里不对？
#3,192 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 3 天内回复

还没有人认领这个 Issue。

评估

难度
2/5
预计耗时
1-3 小时
新手友好度
72/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
cpp, postgresql
领域
backend

调研方向

从 src/cpp_common/to_postgres.cpp 中的 detail::count_rows 开始，然后阅读 matrix_to_tuple 以及确定缓冲区大小的 pgr_alloc(tupcount, tuples) 调用。按照 issue 的建议，将大小计算中的减法替换为显式统计非对角线上的有限单元格。当包含不可达对角线的非连通矩阵单元测试得到正确的行数且没有缓冲区溢出时，即视为完成。

由索引模型根据 Issue 内容生成。

描述

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.

主要语言
C++
星标
1.4k
派生
397
平均合并
2 天 16 小时
30 天内合并 PR
8

环境准备

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

pgRouting/pgrouting 的其他 Issue

查看 pgRouting/pgrouting 的全部 Issue

相似的 Issue

更多 C++ Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。