Fix int32 overflow in ltree_compare()
The expression (len_diff * 10 * (an + 1)) used as the return value of
ltree_compare() is computed at int32 width. With LTREE_MAX_LEVELS =
65535, the product can exceed INT32_MAX once an ltree has more than
~14,653 levels, which causes the result to wrap and invert its sign.
That corrupts btree ordering as well as the "magnitude" consumed by
ltree_penalty() for GiST page splits.
To fix, split ltree_compare() into two functions. The new
ltree_compare_distance() function returns a float, which won't
overflow. It's used by the ltree_penalty() caller. All the other
callers only care about the sign of the return value, i.e. which of
the arguments is greater, so change ltree_compare() to not multiply
the result with (10 * (an + 1)), which avoids the overflow for those
callers.
Existing btree or GiST indexes on ltree columns containing values with
more than ~14,653 levels may be corrupt and should be REINDEXed.
Add a regression test based on the reporter's PoC.
Author: Ayush Tiwari <ayushtiwari.slg01@gmail.com>
Reported-by: 王跃林 <violin0613@tju.edu.cn>
Discussion:
https://www.postgresql.org/message-id/AI6AnABgKW93Qbx1jVzi84r9.8.1781322625756.Hmail.3020001251%40tju.edu.cn
Backpatch-through: 14
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/3f32804918383e48e9ce1d0f1b396775ab312d52
Modified Files
--------------
contrib/ltree/expected/ltree.out | 10 ++++++++
contrib/ltree/ltree.h | 1 +
contrib/ltree/ltree_gist.c | 6 ++---
contrib/ltree/ltree_op.c | 49 +++++++++++++++++++++++++++++++++++-----
contrib/ltree/sql/ltree.sql | 6 +++++
5 files changed, 63 insertions(+), 9 deletions(-)
