Rekurzia v Bashi. Alebo: Koľko je to "no limit"?

11.11.2008 23:10 | Přečteno: 1399× | Skripty | | poslední úprava: 11.11.2008 23:10

Funkcie v bashi sa môžu volať rekurzívne. Manuál tvrdí: "No limit is imposed on the number of recursive calls." V reále to nie je až tak neobmedzené, ale na druhej strane je to celkom postačujúce. Zaujímavé je, že bashovská rekurzia nie je obmedzená veľkosťou dostupnej pamäte, ale pravdepodobne chybou v bashi.

Spustite si skriptíček

#!/bin/bash

recurent() {
        [[ "$1" -eq 10000 ]] &&
                return
        echo "$1"
        recurent "$(($1+1))"
}

a napíšte do diskusie pri akom čísle vám to spadlo. U mňa to končí nie úplne deterministicky na číslach 8176 až 8182 s chybou "Segmentation fault". Kde asi tvorca bashu urobil chybu?

Nemusíte sa báť to spustiť. Na mojom Athlone64 3200+ (@2.2GHz) trvá skript 20s a hodnota VIRT v top-e ukazuje maximálne cca 24000 (znamená to pre program bez veľkého objemu zdieľaných knižníc veľkost alokovanej pamäte v kB?). Aký je vzťah medzi touto hodnotou a skutočne obsadenou pamaťou si už ani zďaleka nepamätám, ale rozhodne vám to nedostaví počítač divokým swapovaním. Na grafe spotreby pamäte som to ani nezaregistroval.

Zároveň si môžete vyskúšať aké spomalenie znamenajú niektoré drobné úpravy v kóde. Napríklad pridanie alokácie (pridať local i pred echo) jednej premennej predĺži čas behu na trojnásobok. Pričom vidno, že s rastúcimi číslami sa beh spomaľuje a spomaľuje. Pravdepodobne prehľadáva niečo ako lineárny zásobník stále od jeho začiatku.

Pre info, testujem to na bashi:

$ echo $BASH_VERSION
3.2.33(1)-release

       

Komentáře

[qiRzT]

Nesouvisí tohle spíš s počtem spuštěných procesů?

[isimluk]

Nemyslím, žr jde až o takovou chybu bashe, ale spíš programátora toho skriptu...

[Käyttäjä 11133]

9515
Neoprávněný přístup do paměti (SIGSEGV)

marek@mantisha:~> echo $BASH_VERSION
3.2.39(1)-release
marek@mantisha:~>

[spang]

Hmm, segfault na 7813 (64-bit bash 3.2.39(1) z testing Debianu). Jinak v tom skriptíku chybí ještě první zavolání té funkce (a recurrent se píše se dvěma 'r' ).

[isimluk]

Zastavilo se to na 9999, a nepokraču je to dál, pak chvíli nic a legální konec. Žádnej SIGSEGV u mě...

3.2.39(1)-release

bte, nechybí něco v tom skriptíku? Já jsem si ho musel upravit, aby to vůbec něco dělalo...

[ondrej]

Zvys si limit, mne to spadlo na 12464 a 12463.

[PY.gn.EI]

Taktéž 9999, pak chvilku nic a konec. 3.2.39(1)-release

[PY.gn.EI]

Po zvýšení 12465 a 12466

[Václav HFechs Švirga]

9027
Neoprávněný přístup do paměti (SIGSEGV)
$ echo $BASH_VERSION
3.2.17(1)-release
$ uname -a
Linux HF 2.6.22-gentoo-r8 #14 Mon Mar 17 21:43:08 CET 2008 i686 Intel(R) Celeron(R) CPU 2.60GHz GenuineIntel GNU/Linux

[pc2005]

V konsole se uzavře tab, takže z textové konzole to dělá 5755. Bash verze: 3.1.17(2) .

[progdan]

11381
Segmentation fault
[progdan@notas ~]$ echo $BASH_VERSION
3.2.39(1)-release
[progdan@notas ~]$ uname -a
Linux notas 2.6.27-ARCH #1 SMP PREEMPT Sat Nov 8 09:52:52 UTC 2008 x86_64 Intel(R) Core(TM)2 Duo CPU T5250 @1.50GHz GenuineIntel GNU/Linux


PS: Do toho skriptu by to chtelo pridat volani te samotne funkce

[Käyttäjä 11133]

PS: Do toho skriptu by to chtelo pridat volani te samotne funkce

To je jen maličká zkouška pozornosti

[YYY]

LOL. Koukam, ze cim nizsi verze bashe, tim mene prubehu rekurzi - bash mam 3.1.17 a zastavilo se to na cisle 5754. Jinak mam Amd Sempron 2500+(s754). Na pameti to ale fakt nebylo prakticky znat.

[Andrej Herceg]

To nie je celkom pravda. Ja mám 3.00.16 a skončilo to niekde pri 9678. :)

Inak skôr by som tipoval (pokiaľ teda nejde o chybu v bash), že to má nejaký súvis s fragmentáciou pamäte.

[dfsfsfs]

Zajímavé. Pro 3.2.33(1)-release pod

Linux f 2.6.25-gentoo-r7 #1 SMP Sun Aug 10 09:24:29 
CEST 2008 x86_64 Intel(R) Core(TM)2 CPU 6400 @
 2.13GHz GenuineIntel GNU/Linux

to dává segmentation fault pro 8441 rekusí za asi 20 sec.

Kdežto pro starý sh ve versi pro

FreeBSD xxx.xxx.xxx.xxx 7.1-PRERELEASE 
FreeBSD 7.1-PRERELEASE #0: Sun Sep  7 17:10:51 CEST 2008
 xxx@xxx.xxx.xxx.xxx:/usr/obj/usr/src/sys/XXX i386

to je plný počet rekursí během 1.2 (!!) sec. (Přitom jsem nahradil podminku [[ ... ]] za: test ...). Sneslo to i omezení na sto tisíc vnoření, víc jsem nezkoušel.

(V obou případech to bylo zdržované vypisem na terminal.)

[Let_Me_Be]

No nevim, ale mam pocit ze chybu neudelal tvurce bashe, ale ty To ze to sleti je celkem normalni a pada to protoze dojde stack.

[alblaho]

Přesně. Neřídí se to velikostí dostupné paměti, ale velikostí zásobníku. A když dojde, je z toho segfault.

[zero]

a ten zvedneme ulimit -s unlimited, pak už jen tak nespadne;)

[Let_Me_Be]

Eh? To tezko. Pomoci ulimit se nastavuje maximalni objem core dumpu.

[Jan Kundrát (jkt)]

man bash, vyhledat ulimit (jelikoz je to shell builtin). Dozvite se, ze:

-s The maximum stack size

[petr_p]

Rychlejší než hledat v několikatisíciřádkovém manuálu je použít vestavěnou nápovědu: help ulimit

[Let_Me_Be]

ROFL, tak se ocividne bavime o dvou ruznych ulimitech. Jeden je internim prikazem bashe (ktery nepouzivam) a druhy dela presne to co jsem napsal nahore.

[razor]

IMHO jakýkoliv segfault je chyba.

[Let_Me_Be]

A jak chces osetrit to, ze ti dojde stack? Nevis jak velky stack mas (coz by mozna slo zjistit) a nevis kolik pameti se ti pri volani na stacku alokuje (to pujde zjistit dost tezko).

[Kvakor]

Osetrovat vycerpani zasobniku z vysokourovnoveho jazyka je velmi, velmi obtizne, protoze v okaziku, kdy dojde, nemuzete skoro nic delat, ponevac skoro kazda akce potrebuje zasobnik. Napr. kdyz vam dojde zasobnik v C a chcete zavolat longjmp() (coz by za normalnich okolnosti fungovalo), tak nemuzete, protoze musite na zasobnik ulozit navratovou adresu, aktualni adresu zasobniku a jeste parametry.

Mozne reseni je budto pouzit docasne jiny zasobnik (coz chce minimalne kousek kodu v assembleru), nebo hlidat jeho velikost dopredu (coz vetsinou take potrebuje trochu kodu v assembleru) a skoncit jeste drive, nez se zcela vycerpa, pripadne - jedine ciste vysokourovnover reseni - programove omezit hloubku rekurze.

[default]

No tak vošukáš Stack Pointer registr a jedeme dál, ne? (Stačí jen párkrát zavolat POP (E)AX.)

[razor]

Možná že by to šlo takto.

[petr_p]

Assembler jsem opustil někdy v dobách i486, ale není ten zásadní problém, že zatímco na data segment si nikdo nedovolí zapsat bez předchozí alokace, tak na stack segment se vesele zapisuje a optimisticky se očekává, že tam pořád nějaké místo bude.

Má vůbec na x86 smysl omezovat zásobník, ale neomezovat haldu? Vždyť oba jsou ve stejném virtuálním prostoru a operační systém má docela dobrou představu, které stránky jsou alokovány a které vyvolají výjimku.

[Let_Me_Be]

Rekl bych ze zasadni problem je v tom ze stack je proste pevna pamet (souvisly blok pameti do ktereho nemuze nikdo jiny sahat), nevim zda system vubec poskytuje nejakou moznost jak stack bez restartu programu zvetsit.

[petr_p]

Jak říkám, neznám detaily dnešní x86 architektury, ale podle manuálu sigaltstack(2) si mohu požádat operační systém o vytvoření náhradního zásobníku o velikosti, jakou si sám zvolím.

Někde jsem četl pěknou ukázku, jak tuhle službu používat. Zcela normálně se tam ta paměť nejprve malloc()ovala a pak se přes sigaltstack() zaregistrovala. Takže bych řekl, že fyzicky spojitý adresní prostor není třeba.

Podle mě to funguje tak, že ve virtuálním prostoru procesu máte zespoda rostoucí haldu a ze shora o dost pomaleji rostoucí zásobník (i když ten z dlouhodobého hlediska neroste, protože tak fungují dnešní programy). Pokud se procesor pokusí přistoupit za konec alokovaného zásobníku, tak se vyvolá přerušení, operační systém zjistí, že zasažená stránka sousedí se zásobníkem (tzn. zásobník je plný), a tak přialokuje další kus paměti k zásobníku (technicky vzato pouze nastaví atributy stránky), vrátí se do kontextu procesu a procesor restartuje vykonávání instrukce procesu. (Stejný mechanismus jako je obsluha výpadku stránky haldy/textu.)

Avšak pouze ve dvou případech operační systém odmítne prodloužit zásobník: buď se zásobník potkal s haldou (prostě došla paměť), nebo velikost zásobníku dosáhla run-time limit pro velikost zásobníku, který se nastavuje přes ulimit(1)/setrlimit(2). V takovém případě pošle procesu SIGSEGV a pokud proces nemá předchystán náhradní zásobník (siglatstack(2)) nebo neobsluhuje SIGSEGV, tak končí.

K tomu mě vede vzpomínka na manuál k céčkové funkci/makru, která alokuje virtuálně souvislý blok na vrcholu zásobníku, kde je poznámka cosi o dynamicky rostoucím zásobníku, který může potkat haldu. Taktéž existují podivné služby, kterými se mohu dotázat na libovolnou virtuální adresu, mohu nastavovat na daných regionech příznaky (jen pro čtení, nespustitelný) ad.. Takže docela odmítám věřit, že by správa zásobníku zhlediska operačního systému byla tak předpotopně žádná.

[petr_p]

a tak přialokuje další kus paměti k zásobníku (technicky vzato pouze nastaví atributy stránky)

Zapomněl jsem dodat, že také nastaví záznamy v TLB, aby k virtuální stránce existovala fyzická.

[Deleted [8409]]

Pokud jakýkoliv program skončí na SEGFAULT, tak je chyba vždycky na straně programátora. Je to staré známé "nevěřte uživatelům".

[Robo]

GNU bash, version 3.2.39(1)-release (i486-pc-linux-gnu) Copyright (C) 2007 Free Software Foundation, Inc.

8308 Segmentation fault

[Miloš Kozák]

12468
Segmentation fault
milos@raketa:/tmp$ echo $BASH_VERSION
3.2.39(1)-release

[Tomáš]

V cygwinu to skončí po 2807 bez chybové hlášky, bash version 3.2.39(19)-release.

[Shadow]

12464
Neoprávněný přístup do paměti (SIGSEGV)
[user@host ]$ echo $BASH_VERSION
3.2.39(1)-release

[Aleš Kapica]

Mi to žádnou chybu neháže.

[Käyttäjä 11133]

Musíš přidat volání te funkce...

[boriz]

ubuntu 8.04 projde bez jakekoliv chyby... cim to bude? zkousel jsem jak v tty tak v emulatoru terminalu

[boriz]

mimochodem 3.2.39(1)-release asi uz to soudruzi opravili

[Semo]

Ide skutocne o velkost zasobnika. Vyssie uvedena rada s ulimit -s unlimited zaberie. Mozno je v Ubuntu nastaveny defaultne inak. Limit je dostatocne velky, ale aj tak by som uvital nejake ine riesenie, nez spadnut na SEGFAULT.

[default]

by som uvital nejake ine riesenie

Převést na cyklus?

[boriz]

nepomohlo.... nepomohlo