sage crashes on some degenerate flint xgcd's #11771
Comments
|
Replying to @lftabera:
I'm not sure. While FLINT 1.5.2 fixes #7518, it doesn't change the behaviour of this one. Even if I remove the "offending" It seems some weird heap corruption happens there (and apparently earlier in (With some variations on the example code, not changing the polynomials themselves, slightly different things happen.) It's not totally clear to me how the allocation of |
|
Changed keywords from flint, crash, xgcd to flint, crash, xgcd fmpq_poly |
|
comment:3
P.S.: FWIW, I've compiled FLINT without |
|
comment:4
Replying to @nexttime:
Aha, with that, now even doctests fail: |
|
comment:5
With non-verbose debugging memory allocator: |
|
comment:6
Replying to @nexttime:
Hahaha, but despite the above doctest failing, the example Apparently really "random" errors, depending on what gets allocated when and where. |
|
Luis' example, augmented with print statements and some tests |
|
Attachment: trac_11771-boom.sage.gz Attachment: trac_11771-boom.sage.log Output of the above |
|
comment:7
Luis, could you check whether it works outside Sage, i.e. from a C program linked with It's odd that the coefficients are that large... ;-) |
|
test case outside sage |
|
comment:8
Attachment: fmpq_poly-example-2.c.gz I can confirm that the crash occur with flint 1.5.2 and fmpq 0.1.9 vanilla sources. I attach the c file I have used. I have been unable to build flint 1.6 without mpir. |
|
comment:9
Truncated (the polynomials) output of fmpq_poly_example-2 |
|
comment:10
Replying to @lftabera:
Where did you get fmpq_poly 0.1.9 from? (The version in Sage is 0.1.8.)
Just change I guess you already managed, but to build the FLINT library outside of Sage from the vanilla sources, you can use e.g. (on non-Darwin / non-Cygwin systems): make PREFIX=/usr/local FLINT_GMP_LIB_DIR=/usr/lib FLINT_LIB=libflint.so library
# optionally:
make PREFIX=/usr/local FLINT_GMP_LIB_DIR=/usr/lib FLINT_LIB=libflint.so checkwhich produces the library in FLINT's top-level directory. |
|
comment:11
P.S.: To further narrow the origin of the bug, you could scale your polynomials and use |
|
comment:12
FWIW, the example crashes in Going to recompile FLINT without |
|
comment:13
With FLINT 1.6 (compiled with GMP 5.0.1 and MPFR 3.0.0-p3), fmpq_poly 0.1.8 I get: (The output with FLINT 1.5.2 looks similar.) |
|
comment:14
P.S.: Valgrind / Memcheck doesn't report any errors before |
|
comment:15
It seems the memory allocated for /* Now the following equation holds: */
/* rop->den rop->num == */
/* (s->num a->den / s->den) a + (t->num b->den / t->den) b. */
limbs = FLINT_MAX(s->num->limbs, t->num->limbs);
limbs = FLINT_MAX(limbs, fmpz_size(s->den));
limbs = FLINT_MAX(limbs, fmpz_size(t->den) + fmpz_size(rop->den) + fmpz_size(lead));
temp = fmpz_init(limbs);
s->den = fmpz_realloc(s->den, fmpz_size(s->den) + fmpz_size(rop->den)
+ fmpz_size(lead));
if (!fmpz_is_one(a->den))
fmpz_poly_scalar_mul_fmpz(s->num, s->num, a->den);
fmpz_mul(temp, s->den, rop->den); // this is line 2372, invalid write
fmpz_mul(s->den, temp, lead); // this is line 2373, invalid read
Which would mean the bug is in (To verify this, you could rescale your polynomials to integer ones and use only FLINT's |
|
comment:16
Replying to @nexttime:
Yep, increasing I don't know what the correct size for At least it's good to know that the memory corruption doesn't happen elsewhere in Sage, and also isn't caused by (upstream) FLINT. |
|
comment:17
P.S.: Apparently FLINT 2.2 (which includes Guess there's a reason for that... ;-) |
|
comment:18
Apparently a proper fix to the insufficient size of diff --git a/sage/libs/flint/fmpq_poly.c b/sage/libs/flint/fmpq_poly.c
--- a/sage/libs/flint/fmpq_poly.c
+++ b/sage/libs/flint/fmpq_poly.c
@@ -2360,15 +2360,14 @@
/* rop->den rop->num == */
/* (s->num a->den / s->den) a + (t->num b->den / t->den) b. */
- limbs = FLINT_MAX(s->num->limbs, t->num->limbs);
- limbs = FLINT_MAX(limbs, fmpz_size(s->den));
- limbs = FLINT_MAX(limbs, fmpz_size(t->den) + fmpz_size(rop->den) + fmpz_size(lead));
- temp = fmpz_init(limbs);
-
s->den = fmpz_realloc(s->den, fmpz_size(s->den) + fmpz_size(rop->den)
+ fmpz_size(lead));
if (!fmpz_is_one(a->den))
fmpz_poly_scalar_mul_fmpz(s->num, s->num, a->den);
+
+ limbs = fmpz_size(s->den) + fmpz_size(rop->den);
+ temp = fmpz_init(limbs);
+
fmpz_mul(temp, s->den, rop->den);
fmpz_mul(s->den, temp, lead);
@@ -2376,6 +2375,10 @@
+ fmpz_size(lead));
if (!fmpz_is_one(b->den))
fmpz_poly_scalar_mul_fmpz(t->num, t->num, b->den);
+
+ limbs = fmpz_size(t->den) + fmpz_size(rop->den);
+ temp = fmpz_realloc(temp, limbs);
+
fmpz_mul(temp, t->den, rop->den);
fmpz_mul(t->den, temp, lead);
But someone more knowledgeable than me should IMHO (re-)review the whole function w.r.t. the sizes used in memory (re)allocations. Reluctantly I dispense with cc-ing all the reviewers of #4000... ;-) |
|
Attachment: trac_11771-fix_size_of_temporary_in_fmpq_poly_xgcd.sagelib.patch.gz Sage library patch. Fixes amount of memory allocated for |
|
Author: Leif Leonhardy |
|
Changed keywords from flint, crash, xgcd fmpq_poly to flint, crash, xgcd fmpq_poly rational polynomials |
|
comment:19
Attached a patch to |
|
comment:34
Just noticed that Sebastian's patch is referenced in the description. |
|
Reviewer: Luis Felipe Tabera Alonso, Leif Leonhardy |
|
comment:35
Attachment: trac-11771-test.2.patch.gz Fixed, I hate when I forget to mark the "replace patch" box. |
This comment has been minimized.
This comment has been minimized.
|
comment:36
just some quick comments to keep this ticket alive:
Paul |
|
Changed keywords from flint, crash, xgcd fmpq_poly rational polynomials to flint, crash, xgcd fmpq_poly rational polynomials, sd35.5 |
|
comment:37
Apply trac-11771-fmpq_poly.patch, trac-11771-test.2.patch (for the patchbot, which is trying to install the wrong patches) |
|
comment:39
still there in 5.5. Which info is needed? Paul |
|
comment:40
Replying to @zimmermann6:
How to proceed I guess. (I'd prefer only fixing the bug here, rather than upgrading other parts as well.) Probably merging FLINT 2.3 into Sage will supersede this ticket... ;-) |
|
comment:41
You could also add an updated / reviewer patch with your suggestions... (and set the ticket to "positive review", or "needs review") |
|
comment:42
This ought to work now. |
|
comment:43
Replying to @fredrik-johansson:
Yes, with the meanwhile merged FLINT 2.3 at least the example (attachment: trac_11771-boom.sage) works... :-) |
|
comment:45
Probably Luis Felipe should confirm it now works for all of his examples... (although I'm pretty sure it will) |
|
comment:46
Indeed, it works on my battery of examples. But I am not sure if the ticket should just be closed or we should add a doctest... |
|
comment:47
I think we can just add trac-11771-test.2.patch . Apply trac-11771-test.2.patch . |
|
Changed reviewer from Luis Felipe Tabera Alonso, Leif Leonhardy to Luis Felipe Tabera Alonso, Leif Leonhardy, Mike Hansen |
This comment has been minimized.
This comment has been minimized.
|
Merged: sage-5.12.beta2 |
It is a quite special case of a crash confirmed on my personal build of sage-4.7.1 over debian 64 bits and on the sage 4.6.2 live-cd.
A smaller example:
Apply
to the Sage library.
CC: @nexttime @sagetrac-spancratz
Component: basic arithmetic
Keywords: flint, crash, xgcd fmpq_poly rational polynomials, sd35.5
Author: Sebastian Pancratz, Luis Felipe Tabera Alonso
Reviewer: Luis Felipe Tabera Alonso, Leif Leonhardy, Mike Hansen
Merged: sage-5.12.beta2
Issue created by migration from https://trac.sagemath.org/ticket/11771
The text was updated successfully, but these errors were encountered: