Çağrı yığını - Call stack

Olarak bilgisayar biliminin , bir çağrı yığını a, yığın veri yapısı aktif olduğunu bilgileri depolar bu alt yordamlar a bilgisayar programı . Bu tür yığın, yürütme yığını , program yığını , kontrol yığını , çalışma zamanı yığını veya makine yığını olarak da bilinir ve genellikle sadece " yığın " olarak kısaltılır . Çağrı yığınının bakımı çoğu yazılımın düzgün çalışması için önemli olsa da , ayrıntılar üst düzey programlama dillerinde normalde gizli ve otomatiktir . Birçok bilgisayar talimat seti , yığınları işlemek için özel talimatlar sağlar.

Bir çağrı yığını, birkaç ilgili amaç için kullanılır, ancak bir çağrı yığınına sahip olmanın ana nedeni, her aktif alt rutinin yürütmeyi bitirdiğinde kontrolü döndürmesi gereken noktayı takip etmektir. Etkin bir alt program, çağrılan ancak henüz yürütmeyi tamamlamamış olan ve ardından kontrolün çağrı noktasına geri verilmesi gereken bir alt programdır. Alt programların bu tür aktivasyonları, herhangi bir seviyeye yuvalanabilir (özel bir durum olarak özyinelemeli), dolayısıyla yığın yapısı. Örneğin, bir altyordam dört farklı yerden bir altyordamı DrawSquareçağırırsa , yürütme tamamlandığında nereye döneceğini bilmelidir. Bunu başarmak için, adres aşağıdaki talimat atlar , iade adresi , her çağrı ile çağrı yığının üstüne itilir. DrawLineDrawLineDrawLine

Açıklama

Çağrı yığını bir yığın olarak düzenlendiğinden , arayan kişi geri dönüş adresini yığına iter ve çağrılan alt program bittiğinde, geri dönüş adresini çağrı yığınından çeker veya çıkarır ve kontrolü bu adrese aktarır. Çağrılan bir alt rutin başka bir alt rutini çağırırsa, çağrı yığınına başka bir geri dönüş adresi gönderir ve bu, programın belirttiği gibi bilgi yığını ve yığınını kaldırma ile devam eder. İtme, çağrı yığını için ayrılan tüm alanı tüketirse, yığın taşması adı verilen ve genellikle programın çökmesine neden olan bir hata oluşur . Çağrı yığınına bir alt program girişi eklemek bazen "sargı" olarak adlandırılır; tersine, girişleri kaldırmak "gevşemektir".

Genellikle çalışan bir programla (veya daha doğrusu, bir sürecin her görevi veya iş parçacığıyla ) ilişkili tam olarak bir çağrı yığını vardır , ancak sinyal işleme veya ortak çoklu görev için ek yığınlar oluşturulabilir ( setcontext ile olduğu gibi ). Bu önemli bağlamda yalnızca bir tane olduğundan , yığın (dolaylı olarak "görev"); Bununla birlikte, içinde Dördüncü programlama dilinde veri kümesi ya da parametre yığın çağrı yığını daha açık bir şekilde erişilir ve yaygın olarak ifade edilir istifin (aşağıya bakınız).

Gelen yüksek seviyeli programlama dilleri , çağrı yığını özelliklerini genellikle programcı gizlenir. Yığının kendisindeki belleğe değil, yalnızca bir dizi işleve erişim izni verilir. Bu bir soyutlama örneğidir . Öte yandan çoğu montaj dili , programcıların yığını değiştirmeye dahil olmasını gerektirir. Bir yığının fiili ayrıntıları programlama dili bağlıdır derleyici , işletim sistemi ve kullanılabilir komut kümesi .

Çağrı yığınının işlevleri

Yukarıda belirtildiği gibi, bir çağrı yığınının birincil amacı , dönüş adreslerini depolamaktır . Bir alt program çağrıldığında, çağırma rutininin daha sonra devam edebileceği talimatın konumu (adresi) bir yere kaydedilmelidir. Dönüş adresini kaydetmek için bir yığın kullanmanın alternatif arama kurallarına göre önemli avantajları vardır . Birincisi, her görevin kendi yığını olabilir ve bu nedenle alt program iş parçacığı için güvenli olabilir , yani farklı şeyler yapan farklı görevler için aynı anda etkin olabilir. Başka bir yararı sağlayarak olmasıdır evresel , tekrarlama otomatik desteklenmektedir. Bir fonksiyon kendini yinelemeli olarak çağırdığında, daha sonra fonksiyon aktivasyonundan geri dönmek için kullanılabilmesi için fonksiyonun her aktivasyonu için bir dönüş adresinin saklanması gerekir. Yığın yapıları bu yeteneği otomatik olarak sağlar.

Dile, işletim sistemine ve makine ortamına bağlı olarak, bir çağrı yığını aşağıdakiler dahil olmak üzere ek amaçlara hizmet edebilir:

Yerel veri depolama
Bir alt yordam , yalnızca etkin alt yordam içinde bilinen ve döndükten sonra değerleri tutmayan değişkenler olan yerel değişkenlerin değerlerini depolamak için sıklıkla bellek alanına ihtiyaç duyar . Bu kullanım için, yığının üst kısmını alan sağlamaya yetecek kadar hareket ettirerek alan ayırmak genellikle uygundur. Yığın alanını kullanan dinamik bellek ayırma ile karşılaştırıldığında bu çok hızlıdır . Bir alt rutinin her ayrı aktivasyonunun, yereller için yığında kendi ayrı alanını aldığını unutmayın.
parametre geçişi
Altyordamlar genellikle parametre değerlerinin kendilerini çağıran kod tarafından kendilerine sağlanmasını gerektirir ve bu parametreler için yerin çağrı yığınında düzenlenmesi nadir değildir. Genellikle sadece birkaç küçük parametre varsa, değerleri iletmek için işlemci kayıtları kullanılacaktır, ancak bu şekilde ele alınabilecek olandan daha fazla parametre varsa, bellek alanına ihtiyaç duyulacaktır. Çağrı yığını, özellikle parametreler için farklı değerlere sahip olacak bir alt programa yapılan her çağrıya, çağrı yığınında bu değerler için ayrı bir alan verileceğinden, bu parametreler için bir yer olarak iyi çalışır.
Değerlendirme yığını
Aritmetik veya mantıksal işlemler için işlenenler çoğunlukla kayıtlara yerleştirilir ve orada çalıştırılır. Bununla birlikte, bazı durumlarda işlenenler keyfi bir derinliğe kadar istiflenebilir, bu da yazmaçlardan daha fazlasının kullanılması gerektiği anlamına gelir (bu, yazmaç dökülmesi durumudur ). Bu tür işlenenlerin yığını, daha çok bir RPN hesap makinesindeki gibi , değerlendirme yığını olarak adlandırılır ve çağrı yığınında yer kaplayabilir.
Geçerli örneğe işaretçi
Bazı nesne yönelimli diller (örneğin, C++ ), yöntemleri çağırırken bu işaretçiyi işlev argümanlarıyla birlikte çağrı yığınında saklar . Bu işaretçi noktası nesnesi örneği yöntemiyle ilişkili çağırılacak.
Alt yordam bağlamını kapsayan
Bazı programlama dilleri (örneğin, Pascal ve Ada ) , çevreleyen rutinlerin bağlamına, yani dış rutinlerin kapsamındaki parametreler ve yerel değişkenlere erişmesine izin verilen iç içe alt rutinlerin bildirimini destekler . Bu tür statik iç içe yerleştirme yinelenebilir - bir işlev içinde bildirilen bir işlev içinde bildirilen bir işlev... Uygulama, verilen herhangi bir statik iç içe yerleştirme düzeyinde çağrılan bir işlevin, her bir çevreleyen iç içe yerleştirme düzeyinde çevreleyen çerçeveye başvurabilmesi için bir araç sağlamalıdır. Genellikle bu referans, onu hemen arayana atıfta bulunan "dinamik bağlantı"dan ayırt etmek için, "downstack link" veya "static link" olarak adlandırılan, çevreleyen işlevin en son etkinleştirilen örneğinin çerçevesine bir işaretçi tarafından uygulanır ( statik ana işlev olması gerekmez).

Statik bir bağlantı yerine, çevreleyen statik çerçevelere yapılan referanslar, istenen bir çerçeveyi konumlandırmak için indekslenen bir gösterge olarak bilinen bir dizi işaretçide toplanabilir . Bir rutinin sözcük yerleştirme derinliği bilinen bir sabittir, bu nedenle bir rutinin görüntüsünün boyutu sabittir. Ayrıca, geçilecek kapsamların sayısı da bilinir, ekrandaki dizin de sabitlenir. Genellikle bir rutinin ekranı kendi yığın çerçevesinde bulunur, ancak Burroughs B6500 , 32 seviyeye kadar statik yerleştirmeyi destekleyen donanımda böyle bir ekran uyguladı.
Kapsamları içeren ekran girişleri, arayanın ekranının uygun ön ekinden elde edilir. Yinelenen bir iç rutin, her çağrı için ayrı çağrı çerçeveleri oluşturur. Bu durumda, iç rutinin tüm statik bağlantıları aynı dış rutin bağlamına işaret eder.
Diğer iade durumu
Dönüş adresinin yanı sıra, bazı ortamlarda bir alt program döndüğünde geri yüklenmesi gereken başka makine veya yazılım durumları olabilir. Bu, ayrıcalık düzeyi, özel durum işleme bilgileri, aritmetik modlar vb. gibi şeyleri içerebilir. Gerekirse, bu, dönüş adresi olduğu gibi çağrı yığınında saklanabilir.

Tipik çağrı yığını, dönüş adresi, yereller ve parametreler ( çağrı çerçevesi olarak bilinir ) için kullanılır. Bazı ortamlarda çağrı yığınına daha fazla veya daha az işlev atanmış olabilir. Gelen Forth programlama dili , örneğin, normalde sadece dönüş adresi, sayılan döngü parametreleri ve endeksler ve muhtemelen yerel değişkenler (bu ortamda adlı çağrı yığını saklanan dönüş yığını herhangi bir veri geçici olarak yerleştirilebilir rağmen,) arama ve iade ihtiyaçlarına saygı duyulduğu sürece özel geri dönüş yığını işleme kodu kullanarak; parametreleri genellikle ayrı saklanan veri kümesi ya da parametre yığın tipik olarak adlandırılan, genellikle daha açık bir şekilde erişilebilir olduğu için, bir çağrı yığını olsa bile Dördüncü terminolojisinde yığını. Bazı Forth'larda ayrıca kayan nokta parametreleri için üçüncü bir yığın bulunur .

yapı

Yukarı doğru büyüyen yığınlar için çağrı yığını düzeni

Bir çağrı yığını oluşan yığın çerçeveleri (ayrıca aktivasyon kayıtlarını veya aktivasyon kare ). Bunlar, alt rutin durum bilgilerini içeren makineye bağlı ve ABI'ye bağlı veri yapılarıdır. Her yığın çerçevesi, henüz bir dönüşle sonlandırılmamış bir alt programa yapılan bir çağrıya karşılık gelir. Örneğin, bir altyordam DrawLinetarafından çağrılmış olarak adlandırılmış bir altyordam şu anda çalışıyorsa, DrawSquareçağrı yığınının üst kısmı yandaki resimdeki gibi düzenlenebilir.

Bunun gibi bir diyagram, tepenin yerleşimi ve dolayısıyla yığın büyümesinin yönü anlaşıldığı sürece her iki yönde de çizilebilir. Ayrıca, bundan bağımsız olarak mimariler, çağrı yığınlarının daha yüksek adreslere mi yoksa daha düşük adreslere doğru mu büyüdüğüne göre farklılık gösterir. Diyagramın mantığı, adresleme seçiminden bağımsızdır.

Yığının üstündeki yığın çerçevesi, o anda yürütülen rutin içindir. Yığın çerçevesi genellikle en azından aşağıdaki öğeleri içerir (itme sırasına göre):

  • yordama iletilen bağımsız değişkenler (parametre değerleri) (varsa);
  • rutinin arayana geri dönüş adresi (örneğin DrawLineyığın çerçevesinde, DrawSquare' koduna bir adres ); ve
  • rutinin yerel değişkenleri için alan (varsa).

Yığın ve çerçeve işaretçileri

Yığın çerçeve boyutları, farklı işlevler arasında veya belirli bir işlevin çağrıları arasında farklılık gösterebildiğinde, yığından bir çerçeve çıkarmak yığın işaretçisinde sabit bir azalma oluşturmaz . İşlev dönüşünde, yığın işaretçisi bunun yerine , işlev çağrılmadan hemen önceki yığın işaretçisinin değeri olan çerçeve işaretçisine geri yüklenir . Her yığın çerçevesi, hemen altındaki çerçevenin üstüne bir yığın işaretçisi içerir. Yığın işaretçisi, tüm çağrılar arasında paylaşılan değişken bir kayıttır. Belirli bir işlevin çağrılmasının çerçeve işaretçisi, işlev çağrılmadan önceki haliyle yığın işaretçisinin bir kopyasıdır.

Çerçevedeki diğer tüm alanların konumları, ya çerçevenin tepesine göre yığın işaretçisinin negatif ötelemeleri olarak ya da aşağıdaki çerçevenin üstüne göre, çerçeve işaretçisinin pozitif ötelemeleri olarak tanımlanabilir. Çerçeve işaretçisinin konumu, doğal olarak yığın işaretçisinin bir negatif uzaklığı olarak tanımlanmalıdır.

Adresi arayanın çerçevesine kaydetme

Çoğu sistemde, bir yığın çerçevesi, çerçeve işaretçi kaydının önceki değerini, çağıran yürütülürken sahip olduğu değeri içeren bir alana sahiptir. Örneğin, yığın çerçevesi, DrawLinekullanılan çerçeve işaretçi değerini tutan bir bellek konumuna sahip olacaktır DrawSquare(yukarıdaki şemada gösterilmemiştir). Değer, alt programa girildiğinde kaydedilir ve geri döndüğünde geri yüklenir. Yığın çerçevesinde bilinen bir konumda böyle bir alana sahip olmak, kodun, o anda yürütülen rutinin çerçevesinin altındaki her bir çerçeveye art arda erişmesini sağlar ve ayrıca rutinin, çerçeve işaretçisini , geri dönmeden hemen önce , çerçeve işaretçisini arayanın çerçevesine kolayca geri yüklemesine izin verir .

Sözlüksel olarak iç içe rutinler

İç içe alt rutinleri destekleyen programlama dilleri , çağrı çerçevesinde , çağrılıyı en yakın şekilde içine alan prosedürün en son aktivasyonunun yığın çerçevesine , yani arananın doğrudan kapsamına işaret eden bir alana da sahiptir. Buna erişim bağlantısı veya statik bağlantı denir (dinamik ve özyinelemeli çağrılar sırasında statik yuvalamayı takip ettiği için) ve rutinin (ve çağırabileceği diğer rutinlerin yanı sıra) her yuvalamada kapsülleme rutinlerinin yerel verilerine erişim sağlar. seviye. Bazı mimariler, derleyiciler veya optimizasyon durumları, her bir çevreleyen düzey için (yalnızca hemen çevreleyen değil) bir bağlantı depolar, böylece sığ verilere erişen derinlemesine iç içe geçmiş rutinlerin birkaç bağlantıyı geçmesi gerekmez; bu stratejiye genellikle "görüntüleme" denir.

Örneğin, yalnızca bağımsız değişkenler ve dönüş değerleri aracılığıyla iletişim kuran salt işlevlerde olduğu gibi, bir iç işlev kapsüllemedeki herhangi bir (sabit olmayan) yerel veriye erişmediğinde erişim bağlantıları optimize edilebilir. Burroughs büyük sistemleri gibi bazı tarihi bilgisayarlar, iç içe işlevleri desteklemek için özel "görüntüleme kayıtlarına" sahipken, çoğu modern makine için derleyiciler (her yerde bulunan x86 gibi), gerektiğinde işaretçiler için yığında birkaç kelime ayırır.

Üst üste gelmek

Bazı amaçlar için, bir alt rutinin yığın çerçevesi ve onu çağıranınkinin örtüştüğü düşünülebilir, örtüşme, parametrelerin arayandan aranana iletildiği alandan oluşur. Bazı ortamlarda, arayan kişi her argümanı yığına iter, böylece yığın çerçevesini genişletir ve ardından arananı çağırır. Diğer ortamlarda, arayan, çağırdığı diğer alt yordamlara sağladığı argümanları tutmak için yığın çerçevesinin üstünde önceden tahsis edilmiş bir alana sahiptir. Bu alan bazen giden bağımsız değişkenler alanı veya belirtme çizgisi alanı olarak adlandırılır . Bu yaklaşım altında, alanın boyutu derleyici tarafından herhangi bir alt program tarafından ihtiyaç duyulan en büyük olacak şekilde hesaplanır.

kullanın

Çağrı sitesi işleme

Genellikle, bir alt programa yapılan bir çağrının yerinde ihtiyaç duyulan çağrı yığını manipülasyonu minimumdur (bu, çağrılacak her bir alt program için birçok çağrı sitesi olabileceğinden iyidir). Gerçek argümanların değerleri, belirli çağrıya özel olduklarından ve kullanılan çağrı kuralı tarafından belirlendiği gibi, ya yığına itilir ya da kayıtlara yerleştirilir, çağrı sitesinde değerlendirilir . "Şube ve bağlantı" gibi gerçek çağrı talimatı daha sonra kontrolü hedef alt rutinin koduna aktarmak için tipik olarak yürütülür.

Alt program girişi işleme

Çağrılan alt yordamda, yürütülen ilk kod genellikle alt yordam prologu olarak adlandırılır , çünkü yordamın ifadeleri için kod başlamadan önce gerekli düzenlemeyi yapar.

Bir alt rutini çağırmak için kullanılan talimatın dönüş adresini yığına itmek yerine bir kayıt defterine koyduğu komut kümesi mimarileri için, önsöz genellikle çağrı yığınına değeri iterek dönüş adresini kaydeder. altyordam diğer rutinleri çağırmaz, değeri kayıtta bırakabilir. Benzer şekilde, geçerli yığın işaretçisi ve/veya çerçeve işaretçisi değerleri itilebilir.

Çerçeve işaretçileri kullanılıyorsa, önsöz tipik olarak yığın işaretçisinden kare işaretçi kaydının yeni değerini ayarlar. Yerel değişkenler için yığın üzerindeki alan, yığın işaretçisini aşamalı olarak değiştirerek tahsis edilebilir.

Forth programlama dili ( "geri dönüş küme" Orada da adlandırılır) çağrı yığını sarma açık verir.

İade işleme

Bir altyordam geri dönmeye hazır olduğunda, girişin adımlarını geri alan bir sonsöz yürütür. Bu, tipik olarak, yığın çerçevesinden kaydedilen kayıt değerlerini (çerçeve işaretçi değeri gibi) geri yükleyecek, yığın işaretçi değerini değiştirerek yığın çerçevesinin tamamını yığından çıkaracak ve son olarak dönüş adresindeki talimata dallanacaktır. Birçok çağrı kuralı altında, epilog tarafından yığından çıkarılan öğeler orijinal argüman değerlerini içerir, bu durumda genellikle arayan tarafından yapılması gereken başka yığın manipülasyonları yoktur. Ancak bazı arama kurallarında, dönüşten sonra argümanları yığından çıkarmak arayan kişinin sorumluluğundadır.

gevşemek

Çağrılan işlevden geri dönmek, belki de bir dönüş değeri bırakarak üst çerçeveyi yığından çıkarır. Programın başka bir yerinde yürütmeye devam etmek için bir veya daha fazla çerçeveyi yığından çıkarmanın daha genel eylemine yığın çözme denir ve istisna işleme için kullanılanlar gibi yerel olmayan kontrol yapıları kullanıldığında gerçekleştirilmelidir . Bu durumda, bir işlevin yığın çerçevesi, istisna işleyicilerini belirten bir veya daha fazla giriş içerir. Bir istisna atıldığında, atılan istisnanın türünü işlemeye (yakalamaya) hazırlanan bir işleyici bulunana kadar yığın çözülür.

Bazı diller, genel çözülmeyi gerektiren başka kontrol yapılarına sahiptir. Pascal , global bir goto ifadesinin, kontrolü iç içe geçmiş bir işlevden daha önce çağrılan bir dış işleve aktarmasına izin verir . Bu işlem, kontrolü çevreleyen dış işlev içindeki hedef ifadeye aktarmak için uygun bağlamı geri yüklemek için gerektiği kadar yığın çerçevesini kaldırarak yığının çözülmesini gerektirir. Benzer şekilde, C, yerel olmayan gotos olarak hareket eden setjmpvelongjmp işlevlerine sahiptir. Common Lisp , unwind-protectözel operatör kullanılarak yığın açıldığında ne olacağının kontrol edilmesini sağlar .

Devam uygularken , yığın (mantıksal olarak) çözülür ve ardından devam yığını ile geri sarılır. Devamlılıkları uygulamanın tek yolu bu değildir; örneğin, çoklu, açık yığınlar kullanarak, bir devam uygulaması basitçe yığınını etkinleştirebilir ve iletilecek bir değeri sarabilir. Şema programlama dili keyfi sağlar thunks "dinlenmek" ya da bir devamı çağrıldığında kontrol yığının "sarma" belirtilen noktalarında yürütülecek.

muayene

Çağrı yığını bazen program çalışırken incelenebilir. Programın nasıl yazıldığına ve derlendiğine bağlı olarak, yığındaki bilgiler ara değerleri ve işlev çağrısı izlerini belirlemek için kullanılabilir. Bu, ince taneli otomatik testler oluşturmak ve Ruby ve Smalltalk gibi durumlarda birinci sınıf devamlılıkları uygulamak için kullanılmıştır. Örnek olarak, GNU Hata Ayıklayıcı (GDB), çalışan ancak duraklatılmış bir C programının çağrı yığınının etkileşimli incelemesini uygular.

Çağrı yığınının normal zamanlı örneklerinin alınması, programların performansının profilinin çıkarılmasında yararlı olabilir, çünkü bir altyordamın işaretçisi çağrı yığını örnekleme verilerinde birçok kez görünüyorsa, bu muhtemelen bir kod darboğazı olabilir ve performans sorunları için denetlenmelidir.

Güvenlik

Serbest işaretçilerin veya kontrol edilmeyen dizi yazmalarının (C'de olduğu gibi) olduğu bir dilde, kodun yürütülmesini etkileyen kontrol akış verilerinin (dönüş adresleri veya kaydedilen çerçeve işaretçileri) ve basit program verilerinin (parametreler veya dönüş değerleri) karıştırılması ) bir çağrı yığınında bir güvenlik riskidir ve muhtemelen en yaygın arabellek taşmaları türü olarak yığın arabellek taşmaları yoluyla istismar edilebilir .

Bu tür saldırılardan biri, bir arabelleği rastgele yürütülebilir kodla doldurmayı ve ardından doğrudan yürütülebilir koda işaret eden bir değerle bazı dönüş adreslerinin üzerine yazmak için aynı ya da başka bir arabelleğin taşmasını içerir. Sonuç olarak, işlev döndüğünde bilgisayar bu kodu yürütür. Bu tür bir saldırı W^X ile kolayca engellenebilir . Benzer saldırılar, libc'ye dönüş saldırısı veya geri dönüş odaklı programlamadan gelen saldırılar da dahil olmak üzere, W^X koruması etkinleştirildiğinde bile başarılı olabilir . Forth programlama dilinde olduğu gibi, dizileri dönüş yığınından tamamen ayrı bir yerde depolamak gibi çeşitli azaltmalar önerilmiştir.

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar