如何发生"堆栈溢出",如何防止它？

Question

如何发生堆栈溢出以及确保它不会发生的最佳方法是什么,或者是哪种方法可以防止,特别是在Web服务器上,但其他示例也会很有趣？

Answer 1

堆

在此上下文中,堆栈是在程序运行时放置数据的最后进先出缓冲区.最后一次出来(LIFO)意味着你输入的最后一件事总是你要退回的第一件事 - 如果你在堆叠上推2个项目,'A'然后'B',那么你首先要弹出的东西在堆栈中将是'B',接下来是'A'.

当您在代码中调用函数时,函数调用之后的下一条指令将存储在堆栈中,以及可能被函数调用覆盖的任何存储空间.您调用的函数可能会为其自己的局部变量使用更多堆栈.完成后,它释放它使用的局部变量堆栈空间,然后返回到上一个函数.

堆栈溢出

堆栈溢出是指您为堆栈耗尽的内存超出了程序应该使用的内存.在嵌入式系统中,堆栈可能只有256个字节,如果每个函数占用32个字节,那么你只能有函数调用8深 - 函数1调用函数2调用函数3调用函数4 ....函数8调用函数9,但函数9覆盖堆栈外的内存.这可能会覆盖内存,代码等.

许多程序员通过调用函数A然后调用函数B来犯这个错误,然后调用函数C然后调用函数A.它可能在大多数情况下工作,但只是一次错误的输入将导致它永远进入该循环直到计算机识别出堆栈被夸大了.

递归函数也是导致这种情况的原因,但是如果你正在递归编写(即,你的函数自己调用),那么你需要注意这一点并使用静态/全局变量来防止无限递归.

通常,您正在使用的操作系统和编程语言管理堆栈,而且它不在您的手中.您应该查看您的调用图(从您的主要显示每个函数调用的树结构),以查看函数调用的深度,以及检测非预期的循环和递归.如果他们互相称呼过多次,则需要人为地检查故意循环和递归以防错误.

除了良好的编程实践,静态和动态测试之外,您无法在这些高级系统上做太多事情.

嵌入式系统

在嵌入式领域,特别是在高可靠性代码(汽车,飞机,太空)中,您可以进行大量的代码审查和检查,但您还要执行以下操作:

• 禁止递归和循环 - 由策略和测试强制执行
• 保持代码和堆栈相隔很远(代码在flash中,堆栈在RAM中,而且twain不会满足)
• 将保护带放置在堆栈周围 - 空白的内存区域,您填充了一个幻数(通常是软件中断指令,但这里有很多选项),每秒数百或数千次看保护带以确保他们没有被覆盖.
• 使用内存保护(即,堆栈上没有执行,堆栈外没有读取或写入)
• 中断不会调用辅助函数 - 它们设置标志,复制数据,并让应用程序负责处理它(否则你可能会在函数调用树中深入8,有一个中断,然后在内部运行另外几个函数)中断,引起井喷).你有几个调用树 - 一个用于主进程,一个用于每个中断.如果你的中断可以互相打断......好吧,有龙......

高级语言和系统

但是在操作系统上运行的高级语言:

• 减少局部变量存储(局部变量存储在堆栈中 - 尽管编译器非常聪明,如果调用树很浅,有时会将大型本地变量放在堆上)
• 避免或严格限制递归
• 不要将程序分解成越来越小的函数 - 即使不计算局部变量,每个函数调用在堆栈上消耗多达64个字节(32位处理器,节省一半CPU寄存器,标志等)
• 保持呼叫树浅(类似于上面的陈述)

Web服务器

它取决于您拥有的"沙盒",无论您是否可以控制甚至看到堆栈.很有可能你可以像处理任何其他高级语言和操作系统一样对待Web服务器 - 它很大程度上取决于你的手,但检查你正在使用的语言和服务器堆栈.这是可能的吹堆栈SQL服务器上,比如.

-亚当

Answer 2

实际代码中的堆栈溢出很少发生.它发生的大多数情况是递归,其中忘记了终止.然而,它可能很少出现在高度嵌套的结构中,例如特别大的XML文档.这里唯一真正的帮助是重构代码以使用显式堆栈对象而不是调用堆栈.

Answer 3

大多数人会告诉你,没有退出路径的递归会发生堆栈溢出 - 而大多数情况下,如果使用足够大的数据结构,即使正确的递归退出路径也无法帮助你.

在这种情况下的一些选项:

• 广度优先搜索
• 尾递归,特定于.Net的博客文章(对不起,32位.Net)

Answer 4

除了从直接递归中获得的堆栈溢出形式（例如Fibonacci(1000000)）之外，我多次经历过的一种更微妙的形式是间接递归，其中一个函数调用另一个函数，该函数调用另一个函数，然后其中一个函数这些函数再次调用第一个函数。

这通常发生在为响应事件而调用的函数中，但它们本身可能会生成新事件，例如：

void WindowSizeChanged(Size& newsize) {
  // override window size to constrain width
    newSize.width=200;
    ResizeWindow(newSize);
}

在这种情况下，调用ResizeWindow可能会导致WindowSizeChanged()再次触发回调，从而ResizeWindow再次调用，直到耗尽堆栈。在这样的情况下，您通常需要推迟响应事件，直到堆栈帧返回，例如通过发布消息。

Answer 5

无限递归是获得堆栈溢出错误的常见方法.要防止 - 始终确保有一个将被击中的退出路径.:-)

另一种获得堆栈溢出的方法(至少在C/C++中)是在堆栈上声明一些巨大的变量.

char hugeArray[100000000];

那就行了.

Answer 6

当Jeff和Joel想要给世界一个更好的地方来获得技术问题的答案时,会发生堆栈溢出.防止这种堆栈溢出为时已晚.那个"其他网站"本可以通过不被嘲弄来阻止它.;)

Answer 7

通常，堆栈溢出是无限递归调用的结果（考虑到当今标准计算机中通常的内存量）。

当您以“标准”方式调用方法、函数或过程或进行调用时：

1. 将调用的返回方向压入堆栈（即调用后的下一句话）
2. 通常返回值的空间被保留到堆栈中
3. 将每个参数压入堆栈（顺序有所不同，取决于每个编译器，有时也将其中一些参数存储在 CPU 寄存器中以提高性能）
4. 进行实际通话。

因此，通常这需要几个字节，具体取决于参数的数量和类型以及机器架构。

然后您将看到，如果开始进行递归调用，堆栈将开始增长。现在，堆栈通常以与堆相反的方向增长的方式保留在内存中，因此，如果没有“返回”大量调用，堆栈就会开始变满。

现在，在过去，堆栈溢出可能仅仅因为耗尽了所有可用内存而发生，就像那样。对于超出范围的虚拟内存模型（X86 系统上最多 4GB），如果出现堆栈溢出错误，通常会查找无限递归调用。

Answer 8

我在获取最常见的斐波那契数（即 1, 1, 2, 3, 5.....）时重新创建了堆栈溢出问题，因此计算 fib(1) = 1 或 fib(3) = 2.. fib(n ) = ??.

对于 n，假设我们感兴趣 - 如果 n = 100,000 那么相应的斐波那契数是什么？

单循环方法如下 -

package com.company.dynamicProgramming;

import java.math.BigInteger;

public class FibonacciByBigDecimal {

    public static void main(String ...args) {

        int n = 100000;
        BigInteger[] fibOfnS = new BigInteger[n + 1];

        System.out.println("fibonacci of "+ n + " is : " + fibByLoop(n));
    }


    static BigInteger fibByLoop(int n){

        if(n==1 || n==2 ){
            return BigInteger.ONE;
        }

        BigInteger fib = BigInteger.ONE;
        BigInteger fip = BigInteger.ONE;


        for (int i = 3; i <= n; i++){

            BigInteger p = fib;
            fib = fib.add(fip);
            fip = p;
        }

        return fib;
    }

}

这非常简单，结果是 -

fibonacci of 100000 is : 25974069347221724166155034021275915414880485386517696584724770703952534543511273686265556772836716744754637587223074432111638399473875091030965697382188304493052287638531334921353026792789567010512765782716356080730505322002432331143839865161378272381247774537783372999162146340500546698603908627509966393664092118901252719601721050603003505868940285581036751176582513683774386849364134573388343651587754253719124105003321959913300622043630352137565254218239986908485563740801792517616293917549634585586163007628199160811098365263529954406942842065710460449038056471363460330005208522777075544467947237090309790190148604328468198579610159510018506082649192345873133991501339199323631023018641725364771362664750801339824312317034314529641817900511879573167668349799016820118499077566864568450662873924856039140476051995500662888263458771894106803700918793650017330117100283104739474562560914449328213748555738640805798130282666402703542944121049199958031318768058991865134251759599115205631553377039969410355182752749199598022575079020377981030899229849963044962558140455170002502997643221934621653662108418767454282982613982344783665815880408190033073829395000821320093747154851310272208173054322648669496309879147143629255542526240439996153269798768075106468190687921182991679644091782718685617029181022126792674013626504997849688436809752547001310045741864064482994858725517447466956518791269169932445648176733222571493149677633458466238303338202397024368594782876418757885729107101337003000942293335972927791914092128049015459762627910570552481588840517794181929052167695766087488155678601288183543542923073978101547857013284386127286201766539534449930019800629538936985500723286651317181135886613537472684585432548981137176605194616937916884425342594781263103889520479565943807153019112539648471126389007133628569101551453423329441284357220996286746119420951661002309740709965531900508158669911445442647882872642845017253320486483194578920399848938236367456182203750973485668474338872490493370316338265717607297788917989136673251906232471180372801739215723908227692280772924566627505383375006926077210593619421268920302567443565378008318306375933345023502569729065152853271943677560156660399164048825639676930792905029514886934137991251748566670747175149389790386533381395346848378086126737554383821108448976538368483182588363399173104558509056638462025014631311831087429077292622159430204291594740306101839816855066950261973761508571761199475875722129872053120607918649803615960923395941041186351688548839119185179061511562752936158490008721501922265117853150892510275280451512386037921846921215338292871369243215273327141574788295902601571954853164447945467502858402360002383447905203451080332820138038807089807348326201227952633606773669875783326254859449060219173688677862411205621098369850197290177157801120404586491539351157834995461006366357454485082418882790675313599505192062229760153765297973085881648731173082370598284894044874039320535929359764541655607954724778620299692329561389719894679422187273605123365595211331087787582288795975803204596084790245063851941743126163775104599211024868794963417068620929088930685252348056925998333775103901013166178123051145719327066291671254465121517468025481903583516889717075706778656188008220346836321018130262329960275994035799977740462449521145315883703579044832931500072461734173558055678321534543411700202585608091662941986374015145695722728369219632295111877625307534025947814482046574602884855000628069348113982760168555840795421620575435572915106415375929390228843561207926437055600623679865443824643739469724719459965557955058380348255978396827760847315302517889517186307227611036305093600742622617173630586132915440246954329046162586917746305785076749374879923291817501634840688134655343709975893536074051729094126976575932951568186247471276364688365517570183534172746626073065104511957628663499228486787805910851189856535554349587616640164475880286336297040462890970677362565843002353147494612339120686321466370878446992104275415694109122465685712047172411333784898167640969249816334211768571503116710400681753031921154156119580425706586931272762137106974722260296555246110537155545324997508432752001992143019105053629960070429632978051030666506387862681576587726837451289768507963663710593809112254288358391941211547737599813019216509521401333060709873137329265181692268450634439540567298120315463923249817937804691037934221694952291007930299492375072993250630509428139027930841344730614116433556147640931044259184813639305423693789765205264563476483182726333715121120306292338892864879492097378478618848682608046473195392008403983080088038690495574197562192939221108257663976813610444900247209483403267967688376213967440757138872928630798218493143438797780887379588968409461434159271317578365114578289355818599029235343888888465874521308381377794436361197628390368945957601203165022798579015453447473527069728514545998614229027372911314637820455162254475353567736227936485450357102086445412089842350389087702230398493802147348096874333362254491501174117515707045610508952740002063804979679604026178186644812485472696308234733772455433905198413087697812765659167642290229481817630757102557933650081522863836344931380899717850870708636322058690189383777660630060667577324272729292474212952650007066467227300099561241914091389846752249557907293984956087504566942177715511073466304566039441362358884436762152739285970722879373559667239246138274687032178584599482575147454064364609970593161205968415604732343966524572316503177928338605903883604176914287327357039868033426046700717173635730911229813069032861371225979370966057751729645282637574340757922821807443529086696068540217185978911663338638585897362091142484321786450394791954242081916260885710691104339948014730131008698488664307212167624731196181907378207665829682807960794822595490363282665780069948568253005364366748225346037051345036031521542969439918662368576380623512098844487411386001711736476321260299614085619255997075668278667787323774194444622753999092910446977164761511186723272386792081333673061819448493966071233452718565202536436219641987827529788130600803131418170693144682211892757849782810943677515407101063505537980038422190455084822393869932969266592211127426981330623000734656284980936366930494468016285537126334126203784919194986000972008367278766507868863069334189952257683143908324848863403189401941610369798438333466086767094316436535384309121578155435128520777208580989020995864496024794919706872307656871092343807195098248144731578137800806393584187566550985013218828528401849814076907385073695353777118803885289353476009303385986916082893354211477229365619072762646037260272393209911878204070674122722581207667290400719242379303309721323641840939561029959712917998282900095391473824378027790511120309545825328887211461701334403859396540478061993332245473178034073409025121302172795957538631581488103929524754109438805550983826276331276067181261710220113561818007754002275167341441692164249731756213631285882819780057888324545345815224349372681334339977105125320814783450671398350383329013139459864818202723220433419309290119078328965692228783374973543015617228291156273294688148532819221007523736268276431526857354932230280181014496490090155292486383388856648930022509743436012008143651536253691994467097111269519667257800618912154402224875646015546328120919458246535574320476442126507906552082083379760714651275083204871652715774723258872757611283575921325539344462894332581050286335836692918285668947362235082502949640657986308096143416968304675951743553132243626642071976084590242630174733922252912483663164280065528709750519975049130098594680710136023364401644001791886108532307649917143720544678235972117604651532001630853363193515896458906817223728123103202718979179512727996560536940321112428465909945563802154613161062675216338056643943188812681994940055370686976218552318589211009634410129335357339184596681975398342846968228894600763520316889220020219313183697575569620611157743058263055358620156378912460312206729339926173783796251509999354036487314232088739779689089083699962929953919772177965334212492919783837514600620549673416628334873410110977705358980664981360113955715843283087139405825352740560810115039079416880791972129331483030726386786314110384431282159949368243429981887197686376044963425975242568861886889789808883158650762626048564650043228968561492550639688114044004295038942458723822335431010786915173283336047792627277656860761777056168740502577437499837758301438561354272738385897741335269491654839297215195547935789238667625027453701046609093824496266269353213037445388924792161611888897020779104485631995148266308028795495464535838663073444237533197122791588617072896520901498483054359832007713266534072906620167757064096901837712013068232453334779666605253254908736019614803782415660712716503835822572892157082093695109958901328594907243061833257552012080900071750220229497428018234454137119162984499147222541965946822214682606449618392542496709031040075814888579716722463228870164384039084638567311643081695373267903031145836805750211196399056151691547085104597005420985717973180155647414061723341458471112685479298924430013914682891036791792169786165824890073220335913767065276765213071439853027609884780562169946596554613791749856597392273794167264953778019920983554278661791231266993747307777305693244301668393330115545155426568649374921286870491217542459678311329692484924667442619990339728256748734602011504422287804661243201830161082321839086547710423982285313165596856880052265714744288233175394565438819286244326625033453881995900851052113831244918618026244321955404339857228413412544094117717221568670862917421240531106205228429861992736294062088347548536451281232796090972139537753600230767656942082199430346487833485444927135394502245913343746649377016556057633846970629187257454265058794146301766397604574743110815567470916527087481252671599137932405273046136939611698925898083119063225107779285620719994594877006118010022961323045882945584409524966111583428049086438608807964405577636918577437540258968559272525145634043852178258905995539546274513854544529167610429692679708935800562345019185714890304184957674008193599732187119574963570959678251710962647520688908064076514458931328707674541696071079316927042851680934133110463535062422098103632167719104207861621842137639381946256972867814136363896201239769104654189568061973231484142245500716172158513213020306841760872158927020988791089380810459033972765473264169168454456276007595613671035845756490944306924525320850030910687831575615198475675691912847846546925586651115579134612724253360836351313421839051771545112284644551360160135132289485432715047608393075561009087860966638706122786902748318193316067014849571630047052622282384062668184487883745481319943803876138301288598852642019922861882084995886408885213525014576153964826474510259025307431729568996364996157075518558371659353671254485150893629045677366300355624573747791009879924991469672240414816012895309440154889426137831400878043114317418580718261851490511387448313584390672289494082582860216502889272283874264327861686903819605301558944594518087351972460082215293439808282541261282571572093509853828007385604729109411840060844852353778335033068619777245018863640703449733664731006020181287928869918618244184539689947772594821691371336474704531729798092458443611296189975956962409718455640205114325895918447249209429303016514887130798021023790655365251547802980594075294405131458075515377948616358799011581920198088796949671874482241568364635343261602426329347616344581638901638051238941845239734218414968892623984896486420934098166814947711551770095626690298501015135375998012725012419711198715265937474847789354887778151929311714311674447738829410646150287513277094745047639228748906629898415402593508340351420351361688192482389980277066669163421334243120545073593886166876911881857761181357713324839652098820859823912986063868228047543624089565229214108598520373305446259532613402348646892750605268937551484032985420869912210525970056285767077025676953009789700464089200098521069802954196998021380532957981594782899344432454915653278452238405512404452082264354206563133107029407223715527705042634820739844548895892488613976570791454144276535845729513297190919476944119109667974742626755909538320391696734942613600322630774286841050400613510521944137781580950057145268460098103521092490400279580507364369610212411377397171648695254931148050401265683512688295984139832226763778045006265072417317573952197968907548251993292596498016270686656580301788774056151671597319273204793762473755058550528396602945669925221736008740812120142090710419375985717214313380174251415824918247109050847159772494170493202541652393232332588515888933370971363108925715314177619783260337501090262840664158013713593565292780884563059517700814439941146742918503607488523666547448699280832305168157116029118363741479584921008605289814695477508123388969431528610212027367470499039304170351713421269234867005666275062290586369118822289031705103054068820969708755453293694340639812976964780318254516421783473477164710584232385945801830527562139101869976043058440686657123468696794560441557421000391797583489799358827518815246759308789281592434921975453876683056846684207754098217812470533545231947973989533201759886402810588255576980043971205383124594289573776960018574973352499650135093689259580218638117259065064368821271568157510217129007659927503702282839639629159732511734185867210234973177659694542836255193715560091436803293119628425466284031424443706484323903749064108113007928489557672434812000903098884572709077508736388732996425550504738125289759629348228789176199207251383093882882925104168376227582040819189336036538752841167857037209897188329869219278166296758445801749118091196630481874341550677908639488314892415043004767045279712834822115222028370628573142441078237925136450866775666228049772113971406216641163247567842166129614771090188260946773776864061767214842938949766713801227889413090265535110961183470125651975408070953840609168639369066737866272094294342642604029021583173450037274625889926220498771211784055633484924903260035085690993823927772974984135656148307882623633223683807098223460122742413790364734517359252157547571609342709351929017239549214264906911152715233381091240428121028937384881673589539345089306977155229891996989038858832754090443003219868340034702712200201596993716906503305475770953987485806700244910455048900617271891680313945280361656339415713346372225504775474607560550241087643821216888489169403712589019484906853797222445620094838194915327245022762185891695074057949837598210066044819965193601102615769471762025717020486849146168940684041408335875621183192108380056321445620189415059457800253187474719116048406779977654148306221790693308538751292989830095802775541454350587689849441791365358916200987252220490551835546037065331831767161107380097866252474886914760776644701471930744763024116603356717655648744405779905319962716329720091094492492164560306188277729477507647774464525863289191591074442523200829182095180210837003538813309832158946086801279542247520719241346483349639150948130975414332442092999307514810779190023461281223301617994299306188005334145506339321393396468616164169552202164479954172431711657444713641977332048993650747678441499295480730258564429423817876415064928783617679786771585107842357026402133880188756019892340568684232155856285086455252583770106205322242449879906252634840107743224881725586022333020763999338541520153438477254429178951306370503204449177977523708719582779767996861136265322911186296311646851599346606934605575459560631558300336976340002766851512938436388860908283761411577320035275651587459065670254394379311048385713132944906049265823631089495350900826731544972263966480886180415739778884728921746189741897217007700098624496537590127270152276345108749069480122106849520630025190116559635805524291802055869042596852610474128345184667369385800277002529653563667216198836724282269339503259303909945831686655422346548570208755046175205218537215672826799034181355206029998953664701065579005321295413369244724922124363245230428951884617791223380696742339806948872705875033892283950951352091231092581590069603951563677360671090505662996035718764232479207528361608055976977787564767672105212223271848214844466312614875842260926088757643317310232637688648225946912110323677375581221334705568059580083101274816739620195835980239674144898672768458698193767837571679367232130815861910459950589709910646869194634480385741438296295471313721736698361845581445057486761243224515199433621829161914680260911217930018647880500613516031443500761892134416024880917410512322903571792054979279709245024799408426961588184426161637800447594782122408732041244211691998055726491182436619218357147628914258057718717436880003241130087048193739622950171430900984769272374988759386399425305953316078916188108635059824445789427993465149159528848697574880258233535716778648268280511408854297327881977657369660057277001625924043016886599468629837172705958098087309018201209310034300587965526947880498092054843054676110346547480672906743997636125924346377199958438628123919854702024148800768808188480878923915913694632931132768493297772016466417275872591223547844808134333280500877588552646861195769621722393086937957571658218524162043419723839899327348034292623407223381551022091012629492497424232716988420232973032601617905756731112354658902982983131151236076067739689981538122869996420146098525797936912460163460887623212862056342159014791886321946596374834825642916162785329482393132294402310432772887681395502133482663886874532592815878545038909915619496324788550350902893909737189880039990261320158726786378730956781096253110080544894188579835659020636806996431650339120299443277267708693052407184165920700961392864019667257500870122181497331336958096003697517649513500402859262492033981110149532275336218445007443315624345324842179861083462613458975912348399707518542232816771872159568272432459108290198863903697845426225669125427470560975679848571366236790238784781612014779829390805131502581745237735295101652969345627861222411507835877553733483727644398380820006672147400344663227769189369676128789834889420946881023084270364528545049667596973188360444967028531906373969163579809288657199353977234954867871804164014152814894437850362910715178052858575839877111454742401564164771941163913549354667555935926088492005463846854030280809364172505836533680934072253108208447235702268098269514261624512040407115014487478561999228146645658939384880286438223138498523284523606670458051136796637510392481633361732745472757756368109773445392758275605974251607054686896577945305216023159398657809748015154149870977780787053570580084723768924221897503127585271401731176212798987449584061998439133656802977212087519349885044997139142851580323248230213406303125860726245416377652345055220510863182853596585207081733927095664450114040551065790550374177803933516583609045430477214222818168325396136349825252152322576909202542164096574526180660517779015929028842405999988827536919575401169546961522704012808575797661547221929256559639918209488946426575122887663303021337463674492174493516371047257329808328