Opened 8 years ago

Closed 6 years ago

#11771 closed defect (fixed)

sage crashes on some degenerate flint xgcd's

Reported by: lftabera Owned by: AlexGhitza
Priority: minor Milestone: sage-5.12
Component: basic arithmetic Keywords: flint, crash, xgcd fmpq_poly rational polynomials, sd35.5
Cc: leif, spancratz Merged in: sage-5.12.beta2
Authors: Sebastian Pancratz, Luis Felipe Tabera Alonso Reviewers: Luis Felipe Tabera Alonso, Leif Leonhardy, Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mhansen)

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.

sage: K.<t> = QQ[]
sage: f = 1191473873476953285460227947527304741094529005781035717529284834642240745265086239433225233076380605624702266276885804709520281440988182053809930373012295427761599173283075394027446821241892392804713752542041540414303545583709080606441854656664598446661127728326564842323560052105463862185938911893961846570332829347182333704456070837343428230983843530274245217749818452153963934998122234661271161569262586325411921064111934381922037945270623943491947875/174871690725031062857895617270118958943875455402498164912193640599242093454750654780085420853488176444988327239631035217531243625721319710975536503495407145388346890918173115305552220286954950702835407245264267388461374170898342445030455218024182130357203694248197982274053168818543555835515884596734129707663700160914563749534599365348467621157940711549705946958811234911744609308389669378785394624299045157307052537461489976306157712499268558208*t^2 + 5957369375137745766183044465877722046314306073183566047662176066376092822960216106589074191713407928403006693599830465933201735913930024018536420188572573727786004174018936541086056419278615451779011404807616761860595584128639414642858019879851937134914457225162263601277479470481610775838350438889994627122281434924162712202260797778449612640435669592035220516200416587508637711781532078536756632435733417252181811941101332377039987959982663304126874375/699486762900124251431582469080475835775501821609992659648774562396968373819002619120341683413952705779953308958524140870124974502885278843902146013981628581553387563672692461222208881147819802811341628981057069553845496683593369780121820872096728521428814776992791929096212675274174223342063538386936518830654800643658254998138397461393870484631762846198823787835244939646978437233558677515141578497196180629228210149845959905224630849997074232832*t + 595736938787822009331990421961260248362332039245863629830822372455192136576779705935162047105729215117952692017561893764228666459028138729266510727391875394724342702142392944610048092837133895505126656842160002614286655228073218094975822828090436855755172392470009650873209905710177629566178254191440085731926712596202595947686810438960749730919092209485990076735620893188477276276323303747694695509334321377061733279957672914270197272127541816272056125/174871690725031062857895617270118958943875455402498164912193640599242093454750654780085420853488176444988327239631035217531243625721319710975536503495407145388346890918173115305552220286954950702835407245264267388461374170898342445030455218024182130357203694248197982274053168818543555835515884596734129707663700160914563749534599365348467621157940711549705946958811234911744609308389669378785394624299045157307052537461489976306157712499268558208
sage: g = 7925514953439579217949411496070912283478756109542146778302736430907864339692157890889177607003850592550664633799500428198493004015260056890058768264544347643931941923348352003774969492496740120316730457336026114447919653038820695052079984552717333048168876470640134695132125004739250250335197986836852600631182406711728391491853158562797699369204277005299010981337229996326844358132661064724072391106497919430501388151144632847309459048255619440076828071778798946142720000*t^45 + 293918791735480187577516941922733339937352807492841059118385933713283748539804779598827534478091602814003325445243382063224479399718045693658301080762463524046243363063916545047844750387215544788284927537953987285544630566149438287142367528767727980654042920664036206810459153927037523164720164761138218983102711056490362217363277405537096087836114521783454293906133185934584337779537607245876838439405747698796418648433570169192974538900486764773328257871805216316101120000*t^44 + 5058044922569190077396724941164677520085481670106248685911864235740946801026987029117321650107013512436092366949300075069290665996401186739662934911788711343592999481217405623453178126021128397426295357197196460668417362332865447139408950326853588609524618735771926784908539435208354146402007017240653850509854643423004019209503548291682701753204354835806410957416430193017771366830735558144633575952567366598242644959867584304192999520949046953957287435927760351691612654592*t^43 + 54694849336338045833196438539312842280539310213616574853920662032930034365977405106809106935195387675024326548871547468517032727833977513266054462393556813498574344707769305602332489254981329059675876167472860588231715013102018073265202456236085176045504848348705979465130426930205907924724013784863969063360253359489925535762884329455665859013929198494760643835634782798402879965906486564928851921325634019050906087746076965043556286091899796610509937049781963748750859254784*t^42 + 421699361379403421927899085135161755299555767411337866977865778493376007237300023161182987072258309302850137118151960357388606569278273465474395618920242931384017029701996942217038242402694557600928709998824326923455010165560839170156900871767094770732933837469169350292826850777032352906260377542855705628909042897309335030259615222631926105615612994898757637232330315292186344302495295509082542975157721318285008930334275498140777527773837345204734923496752054480072350336768*t^41 + 2485471180921170180607487275048773208518394460583694079509045568317632688737198424067265257527867517793151316977650485529586251838580079895022127039471687019113613172118865405146609447207318120265759639488442383722133279326662700576733389743893160823509646564702044962581518617642509050986818943929029387972887811527720497045443156272736524708800344882974541859663477943872044376006963377805774615921049946808404940634710642903775036096700801717224590724670725219584628943554048*t^40 + 11702378297468092749338378099214444222368765770816490714907329235706807184009354699943824805760512336243783912186297243552005418130718361111985339119609056250692893485448677102001611042393950441338930850603214615872821215966972121594867139857842213985124897237202754537980110286449222571966646098603372943387688932003778781645868983730827578716908282739295978752028540662513070685571058895344336399030077210838607103255178310257903019435702993291293447777974394203651555510402688*t^39 + 45362608030363136983761025968625775573374925940317388209913546851288099896642451818517887036310825019112231824348237451781148889932768526881830630212197032202388230334104401636913181857080758121707993940119507385058600903763265096557369885301489985186177849373073225800198133826995533491758473417655750983222833567200113682054724362172575209804038397427264061796643094475089574554995291272299124661987948290864363370884192707990532587355664736646537065381463763137557096381829504*t^38 + 147965890938599589757330010425310111051260874059570344878889758962164965472254145408316670017020710033693604947168767422990988024997940157312220092212716715448475832439504425498058516260807960514052625712698891974219508630496098590248872494328304864851680476142137598768436390325126452874499966738926030670860118673432811493358550010256440448423980641986304554336308635220027870988252373907228112821838730509231333943573216437875869737577406424765998992668610873464787760105267184*t^37 + 412854050610727648913144179286213988165102990084805131216351904196579648643020811472044176027506718745756031427507192390745146505459535312783780659680100208237312732111308864004353533251568679529354532012814448168551555072542785816924044258457770660764268565568835913972977574995625860425980583139193447726220461195958238938354984629898917253646529411365038734000396561116321935183778850534277244118752421455062274868907741199640604154477528940169647302694075547996396454663456080*t^36 + 997973095185670625342370012469193970072389349234039878960553396297231223850670551360280149898813930061089384702788964426010766318658006295791076198317931702254350596268494110689335004627369696534313393233533793059042895246030064749549144858437845777909867391912833168688310347575974286923470058609001230574861208881801687078070994081568485741432202615128809330327295433600567937229541718419320874514736401051249778187402772501230797574461072433345946754218272275390828609771128028*t^35 + 2110971448933982524270043074289041291948850888916022538871279405036127894935809303880054368383060194664879573001798307389813109430943567418440464670579721076015381103131439464445871365824921081152395014313443335004407093777729315321032362362665019604464442089860196445899707831913065091756228821154878219661390976361499300164048804555656549257391147099986057127409119173362059606509455507824055265076272913740563410477900218869017568335862947706849711982733524319104967312757621100*t^34 + 3938885011139390642689248899047135951625893233815279706609229027016277354215915265277536272967330277440679523435204392263874560538379975241192537501760945071902026114404299873621572987453111739188285635750659528523753618044607778963952789214572609165961705511007095276637444349704203809176774642808993482441123358390263424923237415389263737538016980028990649268719720355983776805736249058208290276899970063276998182485280176565942360784595059838544067051327159256328182679067087425*t^33 + 6525421391013158287374331859667706862622395406857629685576298935370455818921680560188357241485402426889475634793749083217763488048399226120794213545599529842906755304384555504715022996032523078558736166814277649036134922690130477889703580177476622398225490952424241174726573520765022987236742936620584956995142951378174313302142748058429850501535610984950254690159075714173349693558435876552839898853760900861233075399962019657298006619149445198792686650582799567219703558116753688*t^32 + 9648801282294413240161523587424028799474272425190062586162358477659819408179981983268045602187864919296081105306888791383622497929357821256907058519748651340418123952836827613631937758260039260109488362021820930920652881855336971170398212707146489726591703547998345460435470704986784048986381294667829639859422935802115321763721715233560384707943499143721866744933538010860236653435152228417811812570479854509838459533925634420312773859096650361368525070915843660608513545449628965*t^31 + 12788467727774863982860932695554531415431010038222657224597409376738309895255496598699085564562611914543872174948728417217861116590582218873594992794647290550587069394424888291792728073869775911559563548869037244496013093484035449180322054195136227715331656047831641660194463981256812058982845477890235707953147984444495791817913458270321409853350983938909616786485620868826055262888744900416864639739642240645321991793381338117747160795616177381276528086788883290362073364517310110*t^30 + 15245084675733140263510462479971519024464935284011264360732722516372209503564972564242783264973941129294373208527063336224511241111787257558828526897684433254770390766688701125094537565404661815222608274121611907636528026244472744578082024023284457504496262004174592670562135169552014194946781533106661151841808755115752690244382533005603893072375934580549851198518327099303857929709676825950111718340319550932902855393030382909942160634286908383042983407969571191558978997162971776*t^29 + 16389951846896937229684045335945407785840086947555325034979775336777455628122125638613099035723610729504225486244003183126673774336767238358935322612435153467454802372562897670561798021260928795669492574588127327057926632309295733178832770597400730454496823661641229484065558774191955359265052164066901003335254512458375327233888471980656041727845585880437760736721784430221168946602813450436934855428800736608888630402338731188537699091277296228247128288562867864067508966725404752*t^28 + 15923973789374768314546269572985607273749036550180317305240513246207729744120863777209917797722876735784975653007774911161404509133686488858610418292062539401050613438570289158808567185961127993832278231066843611896605279605480919443620945739621341052011584412147624443100375541102245899360700454373716960111379959263682525737333535136945861314971037426513726517069175843040738462580847660739402516209160379545099559065703017830300590723044243924141014988739640512398577454796664476*t^27 + 14001764394118664221365206554061743531919131389416723428850796309445899180279854787473844143324506601237284093381014172518532461861580157150183045101088822073504564582435586045945864096435832224990725152648055544530233866937231681699766545657677557399795731199700050280252278936158980797345993442097940252054209910054854241690800395931427478486967307500263537574465159547017734598880583993054365523971510552159114864414391932706811393890082594668348159436779018718323413449796325904*t^26 + 11152161888522339297047382181389984496470642736735513884256930857175834666740949086753134099736943340304561928965074116948212273744710030661552874274273046970113512832800667317284701785355036689358051685238495272142984093593859477999840388790510757550037927344563490784242536726856421183289066567690610353457240120882891159249567030203154125624915221253038814995370885289883505147497042896257983613864919367006061695750766398976658871799390578324185904458271442438766162123372463230*t^25 + 8048767426777293986280101456360410318074316903960649425762014786693258249580484709366956726437551573519850944154140151991337562394501837144303175973954574168220453234351591478712918456619580092223150835056045596683747783894992197977014074148479416703012501517673714119710712920691272989716895307008262298947501703127842691991089971239006010429505720910153802720743412967809829162569092795605684221989967029689769857864765539496427612981800788644513328127425845054164509454678849760*t^24 + 5262629840754091621498163090386478520959348881638641852457969492933171333770256000739085142273276157414972528992818884448674820920428182057346608285967687794943569455502202311215176576359583926697977293833618300618058369623330182711765003464697208548935973536988475267319987325748996314305664613322390546343892430347729948383335605168387765087758863985064215694995846725974771800071361536680579393805669372930131017183020805629262193824532507665897277119555401627902151392926466886*t^23 + 3114872049902244131198004454354240480861453040251809454516259996348746639356801379009427430803791009609999333881668300012557163502674103336510572301255506183265693623891565114440784962586589854053100030598628556249879285924408182431347846097272341983659709282453355734645414966005528671173141037080863122995123105138579163336937462639492023651833224234008386356220637039060693991805367808585100580042562435067309704774953003285221727483544116830611805267517300271782766763574712996*t^22 + 1666627226706498959557569817871044264469975437540138603547861660424437753187968734534269154979245874083777852839681106901618513988387556354135476267209998115236437653432075331629750632662495842321072485397276767146656045937766487705986571895670316666819198728237342392263488456815656063467424237187409163420343607734844711341149766902013302158748182880854692946455365378394748860711744495257629861061790331563768858195817759951127316780041858861340702710950272840344251229121976316*t^21 + 804464834486138544348798891433796454231646886206326824306727373298236559907169642412283642932504399480419824409057860790751821911252896045259918870858582914050428404596574128510689623562665524085613489955256202965010536601953931632614496294081729283601815297769394328375659692985967483973949962395772855218330007785637876876883977949541805398229657071342421906491883790305712298361083859591974949228704766502689594346827377699106721539643982509108668637670395687194854009853559296*t^20 + 349329055372500354547538290873283032799895433524662339350400896711791239467505083751247234655256780794749126974043725172371330117187543276954967491124908086523104594082490844511359123292898812951874034570389136432669436648578362219274505429022668426105897746929630484094178581602834154449012297935131832055010426700124727186638514023026346095650596927031721573003182422440273685274234152126898260802074169572786521571071016770318423808972800483083075951988223594743727756435669504*t^19 + 135970178440190733686976648333288719209399226795745431128424124413323459178258812383609911825411458342695253443602900735461842828734073894634467815295101591994921267094517811731331788386355113200620792535367328387170628641472662219124648693969171576846446777832125509823449953865555125490264321192383500916108943970763885127898840749587660831597585290822779628679161972491770359270881598753566146318815667305460083658210276919309522087588038185694806776407712756275668571297933556*t^18 + 47220119878855114578841099437857621050003005505338000961291979917933062561619465788218527999275811747395589277891453164092312531838385038609342512458386864008476413080478040723881311242494744412610030464575315516179948065454446646709274787440911877994073341943953530226325202781169005471561389176519070560246381804817378674434166769605954883972733489647995020964516504286765945289519242194014728034933289939619898697460168046082410104243080646437921598662277302797579766361092457*t^17 + 14546627014189438964512706854650793214817304563955069878503854818479294289754639965492451614697560641693214826940062953511978649923303687706880263748727749447781576849419244116658425201644564502294011017732202607235682773633225298829846293741435525891552913383547550531097802489199814218768739219984777033729204507515003390344548396054912879261653728951720511374739308709852401505328620130972266281409612843573623348202425270806909994641433149760293353106403204256445542222522248*t^16 + 3946287357118856747646743142580593180939325050223992458622609211743180087022180772833114442329622430374316780587467023040090435505459976913463073861531260027990924025389557149025676931945354656607866432107770707789011877744999824844566442180758643359451895760661308697273167127817164540336480827202068678749542720002600015385213437650698615470916610783893524115942220101563867434589406278990407634797628726058198006074102013910015548155953201783697557528543838750959394053556061*t^15 + 934181590724770156915121004042777606161562949855773977707196319851682764084778164345009830448714185683203091887847113021315864358945158757002057378238681910795856882103918960498973246285660595756600854496832492409948244818119142214008502127887890664086339947877591954627544721639128225366634705684047851450258435126430535496332219271174934110382633876512397804132233468015623531700341451035637648183418605632726936720033403670460130341182357816091351707013610759108358043925070*t^14 + 190738265078847725464059099686973360226079226125591419597419273307843571919221993624609004807094949542537850299255591462226477704236366433678716480097986435248818265963227494210179712983351105189386123039415065129332466606464332943124257613667592173523881935826488171910076088988681568884136734413633892669060662429803501783978516416390099896013889822236834115043995324359124391333714059990367900026352780161633494701458720094409430117592018921442373009969179443638870062346988*t^13 + 33088049551037012798857177042722000193629544928008635389450319418211587965335619342118248562537077096642309649281561022671014835030321694154797484807481552597966588490657356662848904239835719942440454608148536064974653088471095766092954698432637899189563137460275353284987446905248285182967446248234843454909116257520524169201918559007250649957354907022508216119298434903744970302555249924206012507530243948655460549138602168471705376479061075435247210004317368478922250617504*t^12 + 4780187861721097103421561504473720080097879838434489981410900988923806826767038474149118065492431720003008010074490959041516205300270412600732006878130282527359815583167841562703978176562571470273327439400220606911238069883104078808401835243758082134119690372361919556246090973649393219281872499556319943605369431098587333613949137129901200152676301909312138551001257884772289368549889782023312965046345828969092261644048750545132819747315414260973934103740635207103079351040*t^11 + 559456649409886517645554677325434685404247415709075724496655340573007665156097888221466733090215909892776141041270636001048895662846873433472179876903609388072089924715739721327595617305966251009918502571196130241803928478317145667346711840073166257174045705379704025968568225447113909317485425485479748356181065107172686885985956704504868081475311032360176200232811872041489907430881442837189728503567315354892167205681887760346135640102753024288097919601200561864927528960*t^10 + 50948447320385157792093530249246838208031268919466441287872892089466939406750271520044586955455469631770452191371795427682228376861523785135751860465732772770514295524246348236755132306410324289872598037031652344909505466010244708482699970488591391158927745679388227707618184734312276209378143976203607433911954759308136519704111075049513573207271119863538527240044888047459536934880621838240381356255608370390128674722386723352260558307928475089179132001780766848571444352*t^9 + 3386383999415701694153144567404545114197212924565506475658615899907383110858925294348764492602287569714233807066332712270209826285433705988336069535913396240007407262079890674092810430206696339495806933712600233830106996236755749182709289489991676755574269775048935064447699877505894788426520663565697439483811584523304369689029519204164313704270043719071837613020018670205825837832956321719482167916544739603691526977940054824033147634694036228966374823157449193066433344*t^8 + 146129819533605282881369878670528470174682582412263676202436838024776579204937296748229742107782448036399991778261509236976766661608498459029942418603165693474827891939437652249157107703838182010618001835953553609568030251493145121213363732254240565443863856611828927934993270952161362827640471915769158980284414045744730042169203279944903177115422708184079408527852076598648336108329072616511297356464038589229877488600106455364053377578706638349219218400048080717568832*t^7 + 3078008404143493325413396687603783048676684531507315217124643655099648945604285571597962778361644756677217839388352364597631894566526667909215536689081642597871533196748743113012102495156839081957060918357959037763612336384960332383390307267489046640355974229033444297439381102120575735152282466099915115765069224178495809715479854152461837912208100621532997693246250331161420250695120941793376823326789008211563539255738001764942691529982240678219816015055537668266880*t^6 + 749748266535448482980000523900796337014242550617334827635636271746870485465093441313047420670806434022189643465167292453851477259379861096245984247914017889271447123532861287448471402369899354001146099867801514522003520187909165283161941015281752676289626464039751194288937136954552645140845144982368850097887709675809538065905149537050270180310827327235552300073985756330885804520707969356508120353152276058005042033621190388641966298893439264882274400080138078464*t^5 + 22763021001212288525649219968240291795076682753281626473681762600836656962585296182347503578671254114661839316796047947827363307641155102385375948302008994251312450927706934275869317866448368974931310767329411101190226875471975465789589406436141329920570157654491441039511574791429872260010053983457052134350770020681152207688178102926181096881988395383061276940165294920112663731913982666150498311432405537959954661232773771461891712577468241898048368054186979840*t^4 + 760732209322956364230918251465211804255898726453501652201559924531687159934218116267300005988973501819064052076963672731344826951331488544717567082215953893286027963750212303463945592667622105759098569422663953220699523340224299677842522347708908264142117729514148011758810169174673273142042930237593812742842033904048542885118122073981169544281742573178479542614718551213601389649603467359720415591501513267189141401706542384007133438447938695504788377845760*t^3 + 41544813352135040976950738897887893114387003240423790799951649970908436827293276688809866886969098156185071386944798195405430774778955507150491060619751798064808932393088305841792374978427887767434322831927102150959987052094792515451797115686345263540045464322800865086061669021994451484819098927834799228368418293630987202178683439976104931312600439164262249011017202677016929889120382632621091757957638702011602473100289484910127266680720568281114356303872*t^2 + 223835764128039760458106390105752267448160582915197651087607859967029879622080838118509338692464865849585058866727725078439991840923289230048686724474121146097084020375261587591106841967302336899629321273938262257230558938749878329638982679070953126857220728637693417310788056087735751469460332283819686025809536205970641599404287187646038555082164110783623612107278380687033099914738776804845305119102777801353027247950707169671881871999063754506240*t - 55958941032009940114526597526438066862040145728799412771901964991757469905520209529627334673116216462396264716681931269609997960230822307512171681118530286524271005093815396897776710491825584224907330318484565564307639734687469582409745669767738281714305182159423354327697014021933937867365083070954921506452384051492660399851071796911509638770541027695905903026819595171758274978684694201211326279775694450338256811987676792417970467999765938626560
sage: f.xgcd(g)
...
CRASH!

A smaller example:

sage: R.<t> = QQ[]
sage: f = 10**383 * (t+1)
sage: g = 10**445 * t^2 + 1
sage: r = f.xgcd(g)

Apply

  1. trac-11771-test.2.patch

to the Sage library.

Attachments (7)

trac_11771-boom.sage (25.1 KB) - added by leif 8 years ago.
Luis' example, augmented with print statements and some tests
trac_11771-boom.sage.log (165.4 KB) - added by leif 8 years ago.
Output of the above
fmpq_poly-example-2.c (26.4 KB) - added by lftabera 8 years ago.
test case outside sage
trac_11771-fix_size_of_temporary_in_fmpq_poly_xgcd.sagelib.patch (1.6 KB) - added by leif 8 years ago.
Sage library patch. Fixes amount of memory allocated for temp in fmpq_poly_xgcd(). Based on Sage 4.7.2.alpha2.
trac-11771-fmpq_poly.patch (12.5 KB) - added by spancratz 8 years ago.
Removes second parameter from fmpq_poly_canonicalize()
trac-11771-test.patch (1.0 KB) - added by lftabera 8 years ago.
doctest
trac-11771-test.2.patch (1.0 KB) - added by lftabera 8 years ago.

Download all attachments as: .zip

Change History (58)

comment:1 Changed 8 years ago by leif

  • Cc leif added

comment:2 in reply to: ↑ description Changed 8 years ago by leif

  • Cc spancratz added

Replying to lftabera:

The bug might be related to #7518.

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" fmpz_clear(), Sage segfaults afterwards.

It seems some weird heap corruption happens there (and apparently earlier in fmpq_poly_xgcd()):

...
type(t):  <type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>
type(f):  <type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>
type(g):  <type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>
Calling f.xgcd(g)...
limbs=797 -> temp=fmpz_init(797)
 -> temp==0x5EE2120
    fmpz_size(temp)==140175663150488
Before fmpz_mul(temp,s->den,rop->den):
    fmpz_size(s->den)  ==7
    fmpz_size(rop->den)==795
    fmpz_size(temp)    ==140175663150488
After fmpz_mul(temp,s->den,rop->den):
    fmpz_size(temp)    ==802
Before fmpz_mul(temp,t->den,rop->den):
    fmpz_size(t->den)  ==1
    fmpz_size(rop->den)==795
    fmpz_size(temp)    ==802
After fmpz_mul(temp,t->den,rop->den):
    fmpz_size(temp)    ==795
([fmpz_clear(temp) disabled.] Leaving fmpq_poly_xgcd()...)
*** glibc detected *** python: corrupted double-linked list: 0x0000000005e81860 ***
======= Backtrace: =========
/lib/libc.so.6(+0x775b6)[0x7f7d306b35b6]
/lib/libc.so.6(+0x7a9d3)[0x7f7d306b69d3]
/lib/libc.so.6(cfree+0x73)[0x7f7d306b9e83]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_rational_flint.so(+0x92d8)[0x7f7d1ada92d8]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(+0x9ceab)[0x7f7d31302eab]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0xd1e)[0x7f7d31349d6e]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x888)[0x7f7d3134f948]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f7d3134fa22]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_FileExFlags+0xb0)[0x7f7d313715a0]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_SimpleFileExFlags+0x1ff)[0x7f7d3137204f]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(Py_Main+0xb2c)[0x7f7d31380d3c]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7f7d3065ac4d]
python[0x400619]
======= Memory map: ========
...
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0x7f7d2e4f2817]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7f7d2e4f2849]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x1d5)[0x7f7d2e4f243b]
/lib/libpthread.so.0(+0xf8f0)[0x7f7d310588f0]
/lib/libc.so.6(gsignal+0x35)[0x7f7d3066fa75]
/lib/libc.so.6(abort+0x180)[0x7f7d306735c0]
/lib/libc.so.6(+0x6d4fb)[0x7f7d306a94fb]
/lib/libc.so.6(+0x775b6)[0x7f7d306b35b6]
/lib/libc.so.6(+0x7a9d3)[0x7f7d306b69d3]
/lib/libc.so.6(cfree+0x73)[0x7f7d306b9e83]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_rational_flint.so(+0x92d8)[0x7f7d1ada92d8]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(+0x9ceab)[0x7f7d31302eab]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0xd1e)[0x7f7d31349d6e]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x888)[0x7f7d3134f948]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f7d3134fa22]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_FileExFlags+0xb0)[0x7f7d313715a0]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_SimpleFileExFlags+0x1ff)[0x7f7d3137204f]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(Py_Main+0xb2c)[0x7f7d31380d3c]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7f7d3065ac4d]
python[0x400619]

------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------

(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 fmpz_ts is supposed to work.

comment:3 follow-up: Changed 8 years ago by leif

  • Keywords fmpq_poly added

P.S.: FWIW, I've compiled FLINT without -DNDEBUG, i.e., with assertion checking enabled. Will retry with FLINT's debugging memory allocator enabled.

comment:4 in reply to: ↑ 3 Changed 8 years ago by leif

Replying to leif:

Will retry with FLINT's debugging memory allocator enabled.

Aha, with that, now even doctests fail:

...
Reallocing from 1 to 2 limbs on heap
Reallocing from 1 to 2 limbs on heap
Reallocing from 1 to 2 limbs on heap
Releasing 2 limbs from heap
Releasing 1 limbs from heap
Releasing 1 limbs from heap
Releasing 1 limbs from heap
Releasing 1 limbs from heap
*** glibc detected *** python: munmap_chunk(): invalid pointer: 0x0000000007b474d8 ***
======= Backtrace: =========
/lib/libc.so.6(+0x775b6)[0x7ff35856b5b6]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_clear+0x3b)[0x7ff34b82cdab]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xb6a)[0x7ff34b83360a]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xaf4)[0x7ff34b833594]
======= Memory map: ========
...
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0x7ff3563aa817]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7ff3563aa849]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x1d5)[0x7ff3563aa43b]
/lib/libpthread.so.0(+0xf8f0)[0x7ff358f108f0]
/lib/libc.so.6(gsignal+0x35)[0x7ff358527a75]
/lib/libc.so.6(abort+0x180)[0x7ff35852b5c0]
/lib/libc.so.6(+0x6d4fb)[0x7ff3585614fb]
/lib/libc.so.6(+0x775b6)[0x7ff35856b5b6]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_clear+0x3b)[0x7ff34b82cdab]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xb6a)[0x7ff34b83360a]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xaf4)[0x7ff34b833594]

------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
Aborted
	 [3.8 s]
 
----------------------------------------------------------------------
The following tests failed:


	sage -t -long -verbose "devel/sage/sage/libs/flint/zmod_poly_linkage.pxi"
Total time for all tests: 3.8 seconds

comment:5 follow-up: Changed 8 years ago by leif

With non-verbose debugging memory allocator:

...
Trying:
    P = GF(Integer(1009))['x']; (x,) = P._first_ngens(1)###line 621:_sage_    >>> P.<x> = GF(1009)[]
Expecting nothing
ok
Trying:
    (prod(P.random_element() for i in range(Integer(5)))).factor()###line 622:_sage_    >>> (prod(P.random_element() for i in range(5))).factor()
Expecting:
    (920) * (x + 96) * (x + 288) * (x + 362) * (x + 432) * (x + 603) * (x + 709) * (x^2 + x + 585) * (x^2 + 40*x + 888)
*** glibc detected *** python: munmap_chunk(): invalid pointer: 0x00000000072d7de8 ***
======= Backtrace: =========
/lib/libc.so.6(+0x775b6)[0x7f90f075b5b6]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_clear+0x3b)[0x7f90e3a1ccdb]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xb6a)[0x7f90e3a2353a]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libflint.so(zmod_poly_factor_berlekamp+0xaf4)[0x7f90e3a234c4]

comment:6 in reply to: ↑ 5 Changed 8 years ago by leif

Replying to leif:

With non-verbose debugging memory allocator ...

Hahaha, but despite the above doctest failing, the example f.xgcd(g) now works! XD

Apparently really "random" errors, depending on what gets allocated when and where.

Changed 8 years ago by leif

Luis' example, augmented with print statements and some tests

Changed 8 years ago by leif

Output of the above

comment:7 Changed 8 years ago by leif

Luis, could you check whether it works outside Sage, i.e. from a C program linked with fmpq_poly.o and a FLINT library (not necessarily Sage's, but some 1.5.x one, perhaps also 1.6.x)?

It's odd that the coefficients are that large... ;-)

Changed 8 years ago by lftabera

test case outside sage

comment:8 follow-up: Changed 8 years ago by lftabera

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 Changed 8 years ago by lftabera

Truncated (the polynomials) output of fmpq_poly_example-2

f     = 7925514953439579217949411496070912283478756109542146778302736430907864339692157890889177607003850592550664633799500428198493004015260056890058768264544347643931941923348352003774969492496740120316730457336026114447919653038820695052079984552717333048168876470640134695132125004739250250335197986836852600631182406711728391491853158562797699369204277005299010981337229996326844358132661064724072391106497919430501388151144632847309459048255619440076828071778798946142720000*t^45 + ...
g     = 1191473873476953285460227947527304741094529005781035717529284834642240745265086239433225233076380605624702266276885804709520281440988182053809930373012295427761599173283075394027446821241892392804713752542041540414303545583709080606441854656664598446661127728326564842323560052105463862185938911893961846570332829347182333704456070837343428230983843530274245217749818452153963934998122234661271161569262586325411921064111934381922037945270623943491947875/174871690725031062857895617270118958943875455402498164912193640599242093454750654780085420853488176444988327239631035217531243625721319710975536503495407145388346890918173115305552220286954950702835407245264267388461374170898342445030455218024182130357203694248197982274053168818543555835515884596734129707663700160914563749534599365348467621157940711549705946958811234911744609308389669378785394624299045157307052537461489976306157712499268558208*t^2 + ...
f * g = 1101101212788499360810129345899195039702949194476063939955641278765375111724305434546660894662338059538430086096903872314683727366315834245042992834176660316433190688307506096472980279025068957644841073120248908438919056225183447086679153691142213161790082995561613533450526850071597905824622408147163104174783054666538502291981096470240689258957915215906666572910940190140719966752789417415927640263436980073090431283879530089120368898239703777446992846956750190327352413696126193074904067897336709516511845348078572276607349027967595186321707443665173889805099691108502481995770785355116721759382487110422696562193804194888362863419159995682445665932110720140344917107432313752626523472232209771387528380088885036702942166646596523728163690220769690451069629199345704608176695680369879384555989342582460821203101399777620592399030848522166525619661759709299396458159774539961683256200076002596808159015291365684532500000/20390822146109032516079246416758274130582492467642043483231534584799684404705067021931602245042931022036885172531603919954669266058922540925319088560565198855917314705943693482457115238684112721879128643337717745856037100151392542564185543146476461095756027780806667709194632558132410894999520125552020721509293395629030287958791903608729899855170325507195189710682280190268727764504392418235237246303526720768079820133102842386445628789560233*t^47 + ...
*** glibc detected *** ./fmpq_poly-example-2: free(): invalid next size (normal): 0x000000000212fc00 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x72606)[0x7f54fa586606]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x6c)[0x7f54fa58b33c]
./fmpq_poly-example-2[0x402563]
./fmpq_poly-example-2[0x409cef]
./fmpq_poly-example-2[0x40cb5b]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xfd)[0x7f54fa532ead]
./fmpq_poly-example-2[0x402449]
======= Memory map: ========
00400000-00415000 r-xp 00000000 08:02 5744657                            /home/luisfe/sage-bug/fmpq/fmpq_poly-example-2
00614000-00615000 rw-p 00014000 08:02 5744657                            /home/luisfe/sage-bug/fmpq/fmpq_poly-example-2
0212a000-02195000 rw-p 00000000 00:00 0                                  [heap]
7f54f4000000-7f54f4021000 rw-p 00000000 00:00 0 
7f54f4021000-7f54f8000000 ---p 00000000 00:00 0 
7f54f9e60000-7f54f9e75000 r-xp 00000000 08:02 2875502                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f54f9e75000-7f54fa075000 ---p 00015000 08:02 2875502                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f54fa075000-7f54fa076000 rw-p 00015000 08:02 2875502                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f54fa076000-7f54fa0f7000 r-xp 00000000 08:02 2875463                    /lib/x86_64-linux-gnu/libm-2.13.so
7f54fa0f7000-7f54fa2f6000 ---p 00081000 08:02 2875463                    /lib/x86_64-linux-gnu/libm-2.13.so
7f54fa2f6000-7f54fa2f7000 r--p 00080000 08:02 2875463                    /lib/x86_64-linux-gnu/libm-2.13.so
7f54fa2f7000-7f54fa2f8000 rw-p 00081000 08:02 2875463                    /lib/x86_64-linux-gnu/libm-2.13.so
7f54fa2f8000-7f54fa30f000 r-xp 00000000 08:02 2875457                    /lib/x86_64-linux-gnu/libpthread-2.13.so
7f54fa30f000-7f54fa50e000 ---p 00017000 08:02 2875457                    /lib/x86_64-linux-gnu/libpthread-2.13.so
7f54fa50e000-7f54fa50f000 r--p 00016000 08:02 2875457                    /lib/x86_64-linux-gnu/libpthread-2.13.so
7f54fa50f000-7f54fa510000 rw-p 00017000 08:02 2875457                    /lib/x86_64-linux-gnu/libpthread-2.13.so
7f54fa510000-7f54fa514000 rw-p 00000000 00:00 0 
7f54fa514000-7f54fa68e000 r-xp 00000000 08:02 2875461                    /lib/x86_64-linux-gnu/libc-2.13.so
7f54fa68e000-7f54fa88e000 ---p 0017a000 08:02 2875461                    /lib/x86_64-linux-gnu/libc-2.13.so
7f54fa88e000-7f54fa892000 r--p 0017a000 08:02 2875461                    /lib/x86_64-linux-gnu/libc-2.13.so
7f54fa892000-7f54fa893000 rw-p 0017e000 08:02 2875461                    /lib/x86_64-linux-gnu/libc-2.13.so
7f54fa893000-7f54fa898000 rw-p 00000000 00:00 0 
7f54fa898000-7f54fa904000 r-xp 00000000 08:02 4629972                    /usr/lib/libgmp.so.10.0.1
7f54fa904000-7f54fab04000 ---p 0006c000 08:02 4629972                    /usr/lib/libgmp.so.10.0.1
7f54fab04000-7f54fab0c000 rw-p 0006c000 08:02 4629972                    /usr/lib/libgmp.so.10.0.1
7f54fab0c000-7f54fabfd000 r-xp 00000000 08:02 5744440                    /home/luisfe/sage-bug/flint-1.5.2/libflint.so
7f54fabfd000-7f54fadfd000 ---p 000f1000 08:02 5744440                    /home/luisfe/sage-bug/flint-1.5.2/libflint.so
7f54fadfd000-7f54fae01000 rw-p 000f1000 08:02 5744440                    /home/luisfe/sage-bug/flint-1.5.2/libflint.so
7f54fae01000-7f54fae9a000 rw-p 00000000 00:00 0 
7f54fae9a000-7f54faeb9000 r-xp 00000000 08:02 2875462                    /lib/x86_64-linux-gnu/ld-2.13.so
7f54fb055000-7f54fb0a0000 rw-p 00000000 00:00 0 
7f54fb0b6000-7f54fb0b9000 rw-p 00000000 00:00 0 
7f54fb0b9000-7f54fb0ba000 r--p 0001f000 08:02 2875462                    /lib/x86_64-linux-gnu/ld-2.13.so
7f54fb0ba000-7f54fb0bb000 rw-p 00020000 08:02 2875462                    /lib/x86_64-linux-gnu/ld-2.13.so
7f54fb0bb000-7f54fb0bc000 rw-p 00000000 00:00 0 
7fff9b5cc000-7fff9b5ed000 rw-p 00000000 00:00 0                          [stack]
7fff9b5ff000-7fff9b600000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

comment:10 in reply to: ↑ 8 Changed 8 years ago by leif

Replying to lftabera:

I can confirm that the crash occur with flint 1.5.2 and fmpq 0.1.9 vanilla sources.

Where did you get fmpq_poly 0.1.9 from? (The version in Sage is 0.1.8.)


I have been unable to build flint 1.6 without mpir.

Just change -lmpir to -lgmp in the makefile (at the top; one occurrence).

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 check

which produces the library in FLINT's top-level directory.

comment:11 Changed 8 years ago by leif

P.S.:

To further narrow the origin of the bug, you could scale your polynomials and use fmpz_poly instead (leading to even larger coefficients of course).

comment:12 Changed 8 years ago by leif

FWIW, the example crashes in fmpq_poly_xgcd() with FLINT 1.6 in exactly the same way, as expected.

Going to recompile FLINT without -DNDEBUG and with -g...

comment:13 Changed 8 years ago by leif

With FLINT 1.6 (compiled with GMP 5.0.1 and MPFR 3.0.0-p3), fmpq_poly 0.1.8 I get:

...
Now trying xgcd()...
==6335== Invalid write of size 8
==6335==    at 0x4E69CDF: fmpz_mul (mpn_extras.h:100)
==6335==    by 0x409DAA: fmpq_poly_xgcd (fmpq_poly.c:2372)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335==  Address 0x6479440 is not stack'd, malloc'd or (recently) free'd
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x4E69A87: fmpz_mul (fmpz.c:442)
==6335==    by 0x409DC8: fmpq_poly_xgcd (fmpq_poly.c:2373)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335==  Address 0x6479440 is not stack'd, malloc'd or (recently) free'd
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x5553CD6: __gmpn_mul_basecase (tmp-mul_basecase.s:186)
==6335==    by 0x6477B37: ???
==6335==    by 0x321: ???
==6335==    by 0x664F607: ???
==6335==  Address 0x6479420 is 0 bytes after a block of size 6,384 alloc'd
==6335==    at 0x4C26F60: malloc (vg_replace_malloc.c:236)
==6335==    by 0x4E6191C: flint_heap_alloc (memory-manager.c:529)
==6335==    by 0x4029F7: fmpz_init (fmpz.h:80)
==6335==    by 0x409CE9: fmpq_poly_xgcd (fmpq_poly.c:2366)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x5553C98: __gmpn_mul_basecase (tmp-mul_basecase.s:165)
==6335==    by 0x6477B37: ???
==6335==    by 0x321: ???
==6335==    by 0x664F607: ???
==6335==  Address 0x6479428 is 8 bytes after a block of size 6,384 alloc'd
==6335==    at 0x4C26F60: malloc (vg_replace_malloc.c:236)
==6335==    by 0x4E6191C: flint_heap_alloc (memory-manager.c:529)
==6335==    by 0x4029F7: fmpz_init (fmpz.h:80)
==6335==    by 0x409CE9: fmpq_poly_xgcd (fmpq_poly.c:2366)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x5553CAF: __gmpn_mul_basecase (tmp-mul_basecase.s:174)
==6335==    by 0x6477B37: ???
==6335==    by 0x321: ???
==6335==    by 0x664F607: ???
==6335==  Address 0x6479430 is not stack'd, malloc'd or (recently) free'd
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x5553CC1: __gmpn_mul_basecase (tmp-mul_basecase.s:180)
==6335==    by 0x6477B37: ???
==6335==    by 0x321: ???
==6335==    by 0x664F607: ???
==6335==  Address 0x6479438 is not stack'd, malloc'd or (recently) free'd
==6335== 

valgrind: m_mallocfree.c:248 (get_bszB_as_is): Assertion 'bszB_lo == bszB_hi' failed.
valgrind: Heap block lo/hi size mismatch: lo = 29, hi = 7715086580855095582.
This is probably caused by your program erroneously writing past the
end of a heap block and corrupting heap metadata.  If you fix any
invalid writes reported by Memcheck, this assertion failure will
probably go away.  Please try that before reporting this as a bug.

...

(The output with FLINT 1.5.2 looks similar.)

comment:14 Changed 8 years ago by leif

P.S.:

Valgrind / Memcheck doesn't report any errors before fmpq_poly_xgcd() is called.

comment:15 follow-up: Changed 8 years ago by leif

==6335== Invalid write of size 8
==6335==    at 0x4E69CDF: fmpz_mul (mpn_extras.h:100)
==6335==    by 0x409DAA: fmpq_poly_xgcd (fmpq_poly.c:2372)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335==  Address 0x6479440 is not stack'd, malloc'd or (recently) free'd
==6335== 
==6335== Invalid read of size 8
==6335==    at 0x4E69A87: fmpz_mul (fmpz.c:442)
==6335==    by 0x409DC8: fmpq_poly_xgcd (fmpq_poly.c:2373)
==6335==    by 0x4028AF: main (fmpq_poly-example-2.c:56)
==6335==  Address 0x6479440 is not stack'd, malloc'd or (recently) free'd
==6335== 

It seems the memory allocated for temp is insufficient:

    /* 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 fmpq_poly, not FLINT.

(To verify this, you could rescale your polynomials to integer ones and use only FLINT's fmpz_poly functions instead, as mentioned earlier.)

comment:16 in reply to: ↑ 15 Changed 8 years ago by leif

Replying to leif:

It seems the memory allocated for temp is insufficient [...]

Which would mean the bug is in fmpq_poly, not FLINT.

Yep, increasing limbs by five the example runs without errors, though I get:

...
==6537== HEAP SUMMARY:
==6537==     in use at exit: 160,209 bytes in 7 blocks
==6537==   total heap usage: 143,815 allocs, 143,808 frees, 261,851,498 bytes allocated
==6537== 
==6537== LEAK SUMMARY:
==6537==    definitely lost: 72,129 bytes in 3 blocks
==6537==    indirectly lost: 0 bytes in 0 blocks
==6537==      possibly lost: 80,000 bytes in 1 blocks
==6537==    still reachable: 8,080 bytes in 3 blocks
==6537==         suppressed: 0 bytes in 0 blocks
==6537== Rerun with --leak-check=full to see details of leaked memory
==6537== 
==6537== For counts of detected and suppressed errors, rerun with: -v
==6537== Use --track-origins=yes to see where uninitialised values come from
==6537== ERROR SUMMARY: 6 errors from 2 contexts (suppressed: 2 from 2)

I don't know what the correct size for temp should be in general though; perhaps you (Luis) know better, or Sebastian can fix this.

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 Changed 8 years ago by leif

P.S.:

Apparently FLINT 2.2 (which includes fmpq_poly) doesn't [yet] have xgcd() for fmpq_poly_ts.

Guess there's a reason for that... ;-)

comment:18 Changed 8 years ago by leif

Apparently a proper fix to the insufficient size of temp is:

  • sage/libs/flint/fmpq_poly.c

    diff --git a/sage/libs/flint/fmpq_poly.c b/sage/libs/flint/fmpq_poly.c
    a b  
    23602360    /*   rop->den rop->num ==                                                */
    23612361    /*             (s->num a->den / s->den) a +  (t->num b->den / t->den) b. */
    23622362   
    2363     limbs = FLINT_MAX(s->num->limbs, t->num->limbs);
    2364     limbs = FLINT_MAX(limbs, fmpz_size(s->den));
    2365     limbs = FLINT_MAX(limbs, fmpz_size(t->den) + fmpz_size(rop->den) + fmpz_size(lead));
    2366     temp = fmpz_init(limbs);
    2367    
    23682363    s->den = fmpz_realloc(s->den, fmpz_size(s->den) + fmpz_size(rop->den)
    23692364                                                    + fmpz_size(lead));
    23702365    if (!fmpz_is_one(a->den))
    23712366        fmpz_poly_scalar_mul_fmpz(s->num, s->num, a->den);
     2367
     2368    limbs = fmpz_size(s->den) + fmpz_size(rop->den);
     2369    temp = fmpz_init(limbs);
     2370
    23722371    fmpz_mul(temp, s->den, rop->den);
    23732372    fmpz_mul(s->den, temp, lead);
    23742373   
     
    23762375                                                    + fmpz_size(lead));
    23772376    if (!fmpz_is_one(b->den))
    23782377        fmpz_poly_scalar_mul_fmpz(t->num, t->num, b->den);
     2378
     2379    limbs = fmpz_size(t->den) + fmpz_size(rop->den);
     2380    temp = fmpz_realloc(temp, limbs);
     2381
    23792382    fmpz_mul(temp, t->den, rop->den);
    23802383    fmpz_mul(t->den, temp, lead);
    23812384   

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... ;-)

Changed 8 years ago by leif

Sage library patch. Fixes amount of memory allocated for temp in fmpq_poly_xgcd(). Based on Sage 4.7.2.alpha2.

comment:19 Changed 8 years ago by leif

  • Authors set to Leif Leonhardy
  • Keywords rational polynomials added
  • Status changed from new to needs_review

Attached a patch to fmpq_poly.c, fixing (only) the size of temp.

comment:20 follow-up: Changed 8 years ago by spancratz

I can confirm that the patch suggested by leif does the right thing. It does have one extra re-allocation, though, which isn't necessary. I suggest the following,

    limbs = FLINT_MAX(fmpz_size(s->den), fmpz_size(t->den)) + fmpz_size(rop->den);
    temp  = fmpz_init(limbs);

which might perhaps also be easier to read as it's two lines shorter?

Also, the two subsequent calls to fmpq_poly_canonicalize() should be replaced by

    fmpq_poly_canonicalize(s, NULL);
    fmpq_poly_canonicalize(t, NULL);

If you look at the code for fmpq_poly_canonicalize() you'll see that this is in fact not necessary at all since the function doesn't ever actually use the temporary space passed in anyway. --- I realise this looks rather bad. If you think this should be cleaned up on the occasion of this ticket, let me know. ---

In any case, the above bit of code fixes this issue.

By the way, the tight re-use of fmpz variables in flint1 together with the manual memory management is one of the biggest pains when working with flint1. This is all much, much easier in flint2.

comment:21 follow-up: Changed 8 years ago by spancratz

On second thought, the code in fmpq_poly_canonicalize() is too embarrassing. I have deleted the bits of code that were commented out, removed the temporary parameter, which wasn't used anyway, and adjusted the remaining part of the code in fmpq_poly.c accordingly. This also made the memory allocations in two or three other places a little cleaner.

What's the best way to proceed?

On my laptop here at home I only have a version of Sage 4.6 and downloading the latest version of Sage, plus installing it from source etc might take a little while.

I could either send you the updated versions of fmpq_poly.c and fmpq_poly.h and then let you make a patch from it etc. The only other change necessary should be a one-line change in line 26 of fmpq_poly.pxd.

Alternatively, I can attach a patch for those three files based on Sage 4.6. I assume they haven't changed since then?

Best wishes,

Sebastian

comment:22 in reply to: ↑ 20 Changed 8 years ago by leif

Replying to spancratz:

I can confirm that the patch suggested by leif does the right thing. It does have one extra re-allocation, though, which isn't necessary. I suggest the following,

    limbs = FLINT_MAX(fmpz_size(s->den), fmpz_size(t->den)) + fmpz_size(rop->den);
    temp  = fmpz_init(limbs);

Well, I think something like that led to the problem we had, as the sizes can change inbetween. The reallocation should be a nop in at least half of the cases, and I think doesn't have a major impact on the overall performance of the function. It is safe(r) at any rate.


Also, the two subsequent calls to fmpq_poly_canonicalize() should be replaced by

    fmpq_poly_canonicalize(s, NULL);
    fmpq_poly_canonicalize(t, NULL);

If you look at the code for fmpq_poly_canonicalize() you'll see that this is in fact not necessary at all since the function doesn't ever actually use the temporary space passed in anyway. --- I realise this looks rather bad. If you think this should be cleaned up on the occasion of this ticket, let me know. ---

I'd prefer making such changes on another ticket.


In any case, the above bit of code fixes this issue.

I haven't really checked the sizes of other variables...


By the way, the tight re-use of fmpz variables in flint1 together with the manual memory management is one of the biggest pains when working with flint1. This is all much, much easier in flint2.

I know. I was first confused by the fact that foo=fmpz_init(n) gives random values for fmpz_size(foo), so one really has to keep track of the "real" sizes (the amount of memory allocated) separately, or perhaps just on the semantic level, not actually available to the code, at least not directly through the fmpz interface.

Doing so is error-prone, but in general more efficient though, as the functions you use can omit frequent checks, relying on that you know what you're doing...

comment:23 in reply to: ↑ 21 Changed 8 years ago by leif

Replying to spancratz:

On my laptop here at home I only have a version of Sage 4.6 and downloading the latest version of Sage, plus installing it from source etc might take a little while.

I could either send you the updated versions of fmpq_poly.c and fmpq_poly.h and then let you make a patch from it etc. The only other change necessary should be a one-line change in line 26 of fmpq_poly.pxd.

Alternatively, I can attach a patch for those three files based on Sage 4.6. I assume they haven't changed since then?

fmpq_poly.{c,h,pxd} haven't changed since #4000 got merged.

You could upload updated files onto sage.math, or attach them to another ticket.

comment:24 follow-up: Changed 8 years ago by spancratz

Hi Leif,

Thank you for the quick reply.

Actually, the changes are really tiny and it only fixes the issue pertinent to this ticket. Perhaps I can upload the patches (once they are done) and you can review it here?

Sebastian

comment:25 in reply to: ↑ 24 Changed 8 years ago by leif

Replying to spancratz:

Actually, the changes are really tiny and it only fixes the issue pertinent to this ticket. Perhaps I can upload the patches (once they are done) and you can review it here?

We can give it a try...

comment:26 Changed 8 years ago by leif

P.S.: I guess Luis has more code and data to stress-test an updated fmpq_poly version.

comment:27 Changed 8 years ago by spancratz

Excellent.

I am currently at home so until 25 September I will have a little more time than usual. I will try to reply to emails and posts as quick as I can.

Best wishes,

Sebastian

Changed 8 years ago by spancratz

Removes second parameter from fmpq_poly_canonicalize()

comment:28 Changed 8 years ago by spancratz

Hi Leif,

I've now attached a patch. It is based on Sage 4.6, but according what you say it should apply to 4.7 just fine.

Best wishes, Sebastian

comment:29 Changed 8 years ago by lftabera

I can confirm that the patch applies to 4.7.1 and solves the problem in my example. All doctest passes.

However, I have not carefully checked the code. Leif do you give a positive review to Sebastian's patch?

I will also look for a nicer doctest.

Changed 8 years ago by lftabera

doctest

comment:30 Changed 8 years ago by lftabera

  • Description modified (diff)

I have added a doctest to the Sage library with a much nicer example.

Laif. Could you review Sebastian's patch. It looks correct to me, but I am by no means a C authority.

comment:31 Changed 8 years ago by leif

Yes, I should have returned to this ticket earlier, but was quite busy and forgot.

Sebastian, please separate the bug fix patch from changes to the interface (also with meaningful commit messages; a changelog entry is missing, too).

I think we should merge the former into 4.7.2 (since it could be considered a blocker); for the interface change, I'd suggest the following:

  • Create an fmpq_poly 0.1.10 package (of course based on the 0.1.9) with both the bug fix and the interface change.
  • Upgrade Sage's version to that on another ticket.

comment:32 Changed 8 years ago by leif

Luis, your patch looks fine except that it should be TESTS: (with only a single colon), and I'd put the ticket reference into parentheses:

        The following example used to crash (cf. #11771)::

(Or you could change it to "Make sure that #11771 is fixed::".)

comment:33 Changed 8 years ago by leif

  • Authors changed from Leif Leonhardy to Leif Leonhardy, Luis Felipe Tabera
  • Description modified (diff)

comment:34 Changed 8 years ago by leif

  • Authors changed from Leif Leonhardy, Luis Felipe Tabera to Sebastian Pancratz, Luis Felipe Tabera Alonso
  • Reviewers set to Luis Felipe Tabera Alonso, Leif Leonhardy

Just noticed that Sebastian's patch is referenced in the description.

Changed 8 years ago by lftabera

comment:35 Changed 8 years ago by lftabera

  • Description modified (diff)

Fixed,

I hate when I forget to mark the "replace patch" box.

comment:36 Changed 8 years ago by zimmerma

  • Keywords sd35.5 added

just some quick comments to keep this ticket alive:

  • in line 171 of the patched fmpq_poly.c I don't understand why the size of the denominator is used since temp only depends on the numerator
  • further below tempgcd can be allocated to the size of the denominator only, since by definition the gcd is bounded by den.
  • and tempgcd can be used instead of temp to divide den by tempgcd, or better fmpz_tdiv(f->den, f->den, tempgcd)?

Paul

comment:37 Changed 8 years ago by davidloeffler

Apply trac-11771-fmpq_poly.patch, trac-11771-test.2.patch

(for the patchbot, which is trying to install the wrong patches)

comment:38 Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_info

comment:39 follow-up: Changed 7 years ago by zimmerma

still there in 5.5. Which info is needed?

Paul

comment:40 in reply to: ↑ 39 Changed 7 years ago by leif

Replying to zimmerma:

still there in 5.5. Which info is needed?

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 Changed 7 years ago by leif

You could also add an updated / reviewer patch with your suggestions... (and set the ticket to "positive review", or "needs review")

comment:42 follow-up: Changed 7 years ago by fredrik.johansson

This ought to work now.

comment:43 in reply to: ↑ 42 Changed 7 years ago by leif

Replying to fredrik.johansson:

This ought to work now.

Yes, with the meanwhile merged FLINT 2.3 at least the example (trac_11771-boom.sage) works... :-)

comment:44 Changed 7 years ago by leif

  • Milestone changed from sage-5.11 to sage-duplicate/invalid/wontfix
  • Status changed from needs_info to needs_review

comment:45 Changed 7 years ago by leif

Probably Luis Felipe should confirm it now works for all of his examples... (although I'm pretty sure it will)

comment:46 Changed 7 years ago by lftabera

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 Changed 7 years ago by mhansen

  • Reviewers changed from Luis Felipe Tabera Alonso, Leif Leonhardy to Luis Felipe Tabera Alonso, Leif Leonhardy, Mike Hansen
  • Status changed from needs_review to positive_review

I think we can just add trac-11771-test.2.patch​ .

Apply trac-11771-test.2.patch​ .

comment:48 Changed 7 years ago by mhansen

  • Description modified (diff)

comment:49 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-5.12

comment:50 Changed 6 years ago by jdemeyer

  • Priority changed from critical to minor

comment:51 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.12.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.