Can msieve handle c197's with SNFS? - Page 2

jasonp · 2012-07-24, 01:35

Are you running the binary directly or using one of the scripts? What command line and .fb file is involved?

debrouxl · 2012-07-24, 11:36

The most recent entries of your backtrace seem to indicate that msieve is somehow using sprintf on a too small string, and overflowing as a result.

david314 · 2012-07-24, 14:32

Batalov: good thought, however I've tried rebuilding the binary and all dependencies (first libgmp, then libecm, then msieve) on the same machine, and keep observing the same crash and stack trace.

jasonp: I've tried running msieve both directly and via the factmsieve.py script. Here's an example command:

Code:

/msieve -nc -v -s ./input.dat -l ./input.log -i ./input.ini -nf ./input.fb -t 8

Anyway: via trial and error, I've found that if I manually cut input.dat down to 24M input lines (from about 30M, or 49M as I tried earlier in response to another suggestion) it works!

Code:

Msieve v. 1.51 (SVN 722)
Mon Jul 23 23:56:12 2012
random seeds: 3fe35917 a88d007f
factoring 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439 (197 digits)
searching for 15-digit factors
commencing number field sieve (197-digit input)
R0: -3990838394187339929534246675572349035227
R1: 1
A0: -54
A1: 0
A2: 0
A3: 0
A4: 0
A5: 1
skew 2.00, size 1.836e-13, alpha 0.134, combined = 2.763e-11 rroots = 1

commencing relation filtering
estimated available RAM is 12040.1 MB
commencing duplicate removal, pass 1
read 10M relations
read 20M relations
found 2078146 hash collisions in 23999999 relations
added 726541 free relations
commencing duplicate removal, pass 2
found 1291513 duplicates and 23435027 unique relations
memory use: 98.6 MB
reading ideals above 720000
commencing singleton removal, initial pass
memory use: 689.0 MB
reading all ideals from disk
memory use: 791.0 MB
keeping 23999135 ideals with weight <= 200, target excess is 139104
commencing in-memory singleton removal
begin with 23435027 relations and 23999135 unique ideals
reduce to 12487018 relations and 11182174 ideals in 16 passes
max relations containing the same ideal: 135
removing 2282578 relations and 1882578 ideals in 400000 cliques
commencing in-memory singleton removal
begin with 10204440 relations and 11182174 unique ideals
reduce to 9942302 relations and 9026818 ideals in 9 passes
max relations containing the same ideal: 115
removing 1686020 relations and 1286020 ideals in 400000 cliques
commencing in-memory singleton removal
begin with 8256282 relations and 9026818 unique ideals
reduce to 8076784 relations and 7554338 ideals in 8 passes
max relations containing the same ideal: 99
removing 1370818 relations and 1009733 ideals in 361085 cliques
commencing in-memory singleton removal
begin with 6705966 relations and 7554338 unique ideals
reduce to 6556505 relations and 6389005 ideals in 8 passes
max relations containing the same ideal: 86
relations with 0 large ideals: 2828
relations with 1 large ideals: 650
relations with 2 large ideals: 13030
relations with 3 large ideals: 104858
relations with 4 large ideals: 448147
relations with 5 large ideals: 1128260
relations with 6 large ideals: 1816078
relations with 7+ large ideals: 3042654
commencing 2-way merge
reduce to 4402803 relation sets and 4235303 unique ideals
commencing full merge
memory use: 530.3 MB
found 2306660 cycles, need 2279503
weight of 2279503 cycles is about 159850036 (70.12/cycle)
distribution of cycle lengths:
1 relations: 216521
2 relations: 267899
3 relations: 290599
4 relations: 274236
5 relations: 248802
6 relations: 213914
7 relations: 180399
8 relations: 146592
9 relations: 116725
10+ relations: 323816
heaviest cycle: 20 relations
commencing cycle optimization
start with 12650080 relations
pruned 391426 relations
memory use: 400.6 MB
distribution of cycle lengths:
1 relations: 216521
2 relations: 274871
3 relations: 303599
4 relations: 282905
5 relations: 256928
6 relations: 217945
7 relations: 182178
8 relations: 145178
9 relations: 113798
10+ relations: 285580
heaviest cycle: 20 relations
RelProcTime: 957

commencing linear algebra
read 2279503 cycles
cycles contain 6421939 unique relations
read 6421939 relations
using 20 quadratic characters above 268434282
building initial matrix
memory use: 831.2 MB
read 2279503 cycles
matrix is 2279322 x 2279503 (680.4 MB) with weight 203588565 (89.31/col)
sparse part has weight 153290252 (67.25/col)
filtering completed in 2 passes
matrix is 2278602 x 2278783 (680.3 MB) with weight 203562419 (89.33/col)
sparse part has weight 153280386 (67.26/col)
matrix starts at (0, 0)
matrix is 2278602 x 2278783 (680.3 MB) with weight 203562419 (89.33/col)
sparse part has weight 153280386 (67.26/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 2278554 x 2278783 (647.5 MB) with weight 160281204 (70.34/col)
sparse part has weight 146951378 (64.49/col)
using block size 65536 for processor cache size 12288 kB
commencing Lanczos iteration (12 threads)
memory use: 711.5 MB
linear algebra at 0.1%, ETA 7h30m2278783 dimensions (0.1%, ETA 7h30m)    
checkpointing every 300000 dimensions783 dimensions (0.1%, ETA 7h49m)    
linear algebra completed 2238333 of 2278783 dimensions (98.2%, ETA 0h 7m)

Still waiting for the square root steps and the factors, but it's almost there.

I don't know if this makes any sense -- that if I use 30M or 49M relations, msieve crashes with:

Code:

read 10M relations
read 20M relations
read 30M relations
read 40M relations
*** buffer overflow detected ***: ./msieve terminated
======= Backtrace: =========
/lib/libc.so.6(__fortify_fail+0x37)[0x7f74ffa1d7e7]
/lib/libc.so.6(+0xfe6a0)[0x7f74ffa1c6a0]
/lib/libc.so.6(+0xfdb09)[0x7f74ffa1bb09]
/lib/libc.so.6(_IO_default_xsputn+0xcc)[0x7f74ff993f6c]
/lib/libc.so.6(_IO_vfprintf+0x395e)[0x7f74ff966cfe]
/lib/libc.so.6(__vsprintf_chk+0x99)[0x7f74ffa1bba9]
/lib/libc.so.6(__sprintf_chk+0x7f)[0x7f74ffa1baef]
./msieve[0x439565]
./msieve[0x4233f3]
./msieve[0x41639e]
./msieve[0x40588a]
./msieve[0x40397f]
./msieve[0x4042fd]

but if I use only 24M, trimming input.dat manually, it chugs along happily? I can try to upload the .dat somewhere in case anyone wants to try reproducing this...

jasonp · 2012-07-24, 14:52

Well, it's been a while since the parsing of relation lines has caused a crash, but it would be interesting to find what line out of the savefile caused the error. Long lines shouldn't be a problem, they get read in pieces and are silently thrown away.

Any way you can check that? As a start, try building with 'make x86_64 OPT_FLAGS=-g' then running 'gdb ./msieve' and 'run <your_command_line>'. If it crashes, try pasting the output of 'bt full' here.

Batalov · 2012-07-24, 23:34

Ah, must be something in the relations, indeed!
You could try some sanity checks on the .dat file (if it is gzipped, also try gzip -tvv test.dat ):

Code:

grep -v ",0:" test.dat | awk -F: 'NF!=3' > weird1
awk -F: '{print length($0}' test.dat | sort -nr |head
awk -F: '{print length($1}' test.dat | sort -nr |head
awk -F: '{print length($2}' test.dat | sort -nr |head
awk -F: '{print length($3}' test.dat | sort -nr |head

david314 · 2012-07-26, 05:53

hmm, I found a bunch of lines at the end of input.dat like:

Code:

268427021,0:
268427381,0:
268427461,0:
268428071,0:
268428211,0:
268428431,0:
268428631,0:
268429211,0:
268429241,0:
268431461,0:
268431811,0:
268432481,0:
268432631,0:
268432691,0:
268433171,0:
268433531,0:
268434181,0:
268434581,0:
268434731,0:

Are these valid relations? If so, maybe factmsieve/ggnfs is producing garbage input somehow?

(i haven't been able to repro this with msieve compiled with jasonp's flags... but trimming those lines from the file seems to make things work...)

axn · 2012-07-26, 06:05

Quote:

Originally Posted by david314

hmm, I found a bunch of lines at the end of input.dat like:

Are these valid relations? If so, maybe factmsieve/ggnfs is producing garbage input somehow?

(i haven't been able to repro this with msieve compiled with jasonp's flags... but trimming those lines from the file seems to make things work...)

These are the "free relations" added by msieve to the dat file as part of filtering step. They're legit -- don't worry about them.

jasonp · 2012-07-26, 11:10

Correct; even if they were left over from a previous filtering run, free relations are only added once. Having free relations in the data file should definitely *not* cause a crash.

david314 · 2012-07-29, 06:27

k, I'm still hitting this, and I can't figure out what to do. Here's another run with another number (c203), same symptoms though. I'm running in "-v" mode to get a little more verbose details about what's going on. Again, this happens on several different machines, using either the v1.50 or v1.51 code, and whether run standalone or as part of factmsieve.

Code:

Msieve v. 1.51 (SVN 727)
Sun Jul 29 08:06:46 2012
random seeds: 771379d9 bff460a2
factoring 62581158555697378800237649586956931509990963254594555943052827811286155461879998356516108862048309388429051085220676261763779646463087983694925501968657751229016303039311964494627784592260935059912419751 (203 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (203-digit input)
R0: -323257909929174534292273980721360271853387
R1: 1
A0: -54
A1: 0
A2: 0
A3: 0
A4: 0
A5: 1
skew 2.00, size 4.244e-14, alpha 0.134, combined = 1.098e-11 rroots = 1

commencing relation filtering
estimated available RAM is 5958.0 MB
commencing duplicate removal, pass 1
read 10M relations
read 20M relations
read 30M relations
skipped 4 relations with b > 2^32
found 3288532 hash collisions in 39942757 relations
added 662 free relations
commencing duplicate removal, pass 2
found 2210628 duplicates and 37732791 unique relations
memory use: 130.6 MB
reading ideals above 56164352
commencing singleton removal, initial pass
memory use: 753.0 MB
reading all ideals from disk
*** buffer overflow detected ***: ./msieve terminated
======= Backtrace: =========
/lib/libc.so.6(__fortify_fail+0x37)[0x7f2d76b537e7]
/lib/libc.so.6(+0xfe6a0)[0x7f2d76b526a0]
/lib/libc.so.6(+0xfdb09)[0x7f2d76b51b09]
/lib/libc.so.6(_IO_default_xsputn+0xcc)[0x7f2d76ac9f6c]
/lib/libc.so.6(_IO_vfprintf+0x395e)[0x7f2d76a9ccfe]
/lib/libc.so.6(__vsprintf_chk+0x99)[0x7f2d76b51ba9]
/lib/libc.so.6(__sprintf_chk+0x7f)[0x7f2d76b51aef]
./msieve[0x438c85]
./msieve[0x42286d]
./msieve[0x415e6e]
./msieve[0x40535a]
./msieve[0x40371a]
./msieve[0x403fb6]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7f2d76a72c4d]
./msieve[0x4030d9]

I still can't reproduce this with msieve built with "make x86_64 OPT_FLAGS=-g" and run with gdb, but I'm still trying.

(P.S. what is "__fortify_fail"? Is this some weird library I happen to have on my system?)

debrouxl · 2012-07-29, 08:55

Quote:

(P.S. what is "__fortify_fail"? Is this some weird library I happen to have on my system?)

That's an internal symbol for a length-checking version of some function of the printf family, which aborts the program by printing an error message because a buffer overflow has occurred

But despite "-g", your msieve still doesn't seem to be built with enough debugging information, otherwise we'd get at least a function name for the caller of __sprintf_chk.
Try modifying the Makefile itself, rather than passing OPT_FLAGS=-g when invoking make.

For a completely different way to try and find the problem, building msieve with "clang -faddress-sanitizer", instead of "gcc", may do the job. It generates an instrumented binary that can be executed much faster natively than a non-instrumented binary can be executed through Valgrind.

chris2be8 · 2012-07-29, 15:21

Quote:

Originally Posted by david314

Using SNFS with the polynomial:

Code:

n: 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439
m: 3990838394187339929534246675572349035227
deg: 5
skew: 2.0
type: snfs
c5: 1
c0: -54

I would have used:

Code:

n: 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439
type: snfs
m: 3^82 (calculated out of course)
c5: 9
c1: -2

and left the script to calculate the skew. But that would just make sieving a bit faster. You could try letting the script calculate the skew but that's clutching at straws.

Chris

2012-07-24, 23:34	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9494₁₀ Posts	Ah, must be something in the relations, indeed! You could try some sanity checks on the .dat file (if it is gzipped, also try gzip -tvv test.dat ): Code: grep -v ",0:" test.dat \| awk -F: 'NF!=3' > weird1 awk -F: '{print length($0}' test.dat \| sort -nr \|head awk -F: '{print length($1}' test.dat \| sort -nr \|head awk -F: '{print length($2}' test.dat \| sort -nr \|head awk -F: '{print length($3}' test.dat \| sort -nr \|head Last fiddled with by Batalov on 2012-07-24 at 23:35 Reason: .dat file is a :-separated file of ,-separated thingies

2012-07-26, 05:53	#17
david314 Jul 2012 13 Posts	hmm, I found a bunch of lines at the end of input.dat like: Code: 268427021,0: 268427381,0: 268427461,0: 268428071,0: 268428211,0: 268428431,0: 268428631,0: 268429211,0: 268429241,0: 268431461,0: 268431811,0: 268432481,0: 268432631,0: 268432691,0: 268433171,0: 268433531,0: 268434181,0: 268434581,0: 268434731,0: Are these valid relations? If so, maybe factmsieve/ggnfs is producing garbage input somehow? (i haven't been able to repro this with msieve compiled with jasonp's flags... but trimming those lines from the file seems to make things work...)

2012-07-26, 11:10	#19
jasonp Tribal Bullet Oct 2004 6727₈ Posts	Correct; even if they were left over from a previous filtering run, free relations are only added once. Having free relations in the data file should definitely not cause a crash. Last fiddled with by jasonp on 2012-07-26 at 11:12

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Where can I find a arbitrary precision Calculator online that can handle this #	ONeil	Information & Answers	9	2018-04-17 18:18
How to handle ECM results?	dbaugh	PrimeNet	6	2012-11-09 19:27
Tweaking polynomial search for C197	fivemack	Msieve	38	2011-07-08 08:12
222-digit SNFS completed with msieve	frmky	Factoring	2	2007-10-01 18:23
New PC can handle two instances of Prime 95	Bundu	Software	9	2004-08-21 02:29

2012-07-24, 01:35	#12
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	Are you running the binary directly or using one of the scripts? What command line and .fb file is involved?

2012-07-24, 11:36	#13
debrouxl Sep 2009 977 Posts	The most recent entries of your backtrace seem to indicate that msieve is somehow using sprintf on a too small string, and overflowing as a result.

2012-07-24, 14:52	#15
jasonp Tribal Bullet Oct 2004 DD7₁₆ Posts	Well, it's been a while since the parsing of relation lines has caused a crash, but it would be interesting to find what line out of the savefile caused the error. Long lines shouldn't be a problem, they get read in pieces and are silently thrown away. Any way you can check that? As a start, try building with 'make x86_64 OPT_FLAGS=-g' then running 'gdb ./msieve' and 'run <your_command_line>'. If it crashes, try pasting the output of 'bt full' here.