Στοίβα κλήσεων

Στην επιστήμη της πληροφορικής, η στοίβα κλήσεων (call stack) είναι μια δομή δεδομένων στοίβας που κρατά πληροφορίες σχετικά με τις ενεργές υπορουτίνες ενός προγράμματος. Αυτός ο τύπος στοίβας είναι γνωστός και σαν στοίβα εκτέλεσης (execution stack), στοίβα ελέγχου (control stack), στοίβα συναρτήσεων (function stack), ή στοίβα χρόνου εκτέλεσης (run-time stack), και συχνά αναφέρεται απλά σαν «η στοίβα». Αν και η συντήρηση της στοίβας κλήσεων είναι σημαντική για τη σωστή λειτουργία των πιο πολλών προγραμμάτων, οι λεπτομέρειες συνήθως είναι αόρατες στις γλώσσες υψηλού επιπέδου.
Μια στοίβα κλήσεων χρησιμοποιείται για πολλούς σχετικούς μεταξύ τους σκοπούς, αλλά ο κύριος λόγος που υπάρχει είναι για να παρακολουθείται το σημείο στο οποίο κάθε ενεργή υπορουτίνα θα επιστρέψει τον έλεγχο όταν τελειώσει η εκτέλεσή της (ενεργές υπορουτίνες είναι αυτές που έχουν κληθεί αλλά ακόμα δεν έχει τελειώσει η εκτέλεσή τους, επιστρέφοντας). Αν, για παράδειγμα μια υπορουτίνα DrawSquare καλεί μια υπορουτίνα DrawLine από τέσσερα διαφορετικά σημεία, ο κώδικας της DrawLine πρέπει με κάποιον τρόπο να γνωρίζει πού να επιστρέψει. Αυτό συνήθως γίνεται με κώδικα για κάθε κλήση μέσα στην DrawSquare που τοποθετεί τη διεύθυνση στη μνήμη (της "διεύθυνσης επιστροφής") μιας εντολής στη στοίβα κλήσεων μετά την εντολή της κλήσης.

Περιγραφή

Επειδή η στοίβα κλήσεων έχει την οργάνωση στοίβας, ο κώδικας που κάνει την κλήση σπρώχνει(pushes) τη διεύθυνση επιστροφής στη στοίβα, και η καλούμενη υπορουτίνα, όταν τελειώσει, επαναφέρει(pops) τη διεύθυνση επιστροφής από την κορυφή της στοίβας κλήσεων και μεταφέρει τον έλεγχο σε αυτήν τη διεύθυνση. Αν μια καλούμενη υπορουτίνα καλέσει μια άλλη υπορουτίνα, θα σπρώξει άλλη μια διεύθυνση επιστροφής στη στοίβα κλήσεων, και με αυτόν τον τρόπο το πρόγραμμα, η πληροφορία μπαίνει και βγαίνει από την κορυφή της στοίβας, κατά τις εντολές του προγράμματος. Αν η εισαγωγή νέων διευθύνσεων κάποια στιγμή καταναλώσει όλο το διαθέσιμο χώρο που έχει δεσμευτεί για τη στοίβα κλήσεων, προκύπτει ένα σφάλμα που ονομάζεται "υπερχείλιση στοίβας" ("stack overflow"), με αποτέλεσμα συνήθως το πρόγραμμα να τερματίζεται εσφαλμένα. Κάποιες φορές η προσθήκη στη στοίβα μιας εγγραφής για μια υπορουτίνα ονομάζεται τύλιγμα (winding), αντίστοιχα η αφαίρεσή της ονομάζεται ξετύλιγμα (unwinding).
Συνήθως υπάρχει μια λίστα σχετική με ένα πρόγραμμα που εκτελείται (ή, πιο σωστά, με κάθε εργασία ή νήμα μιας διεργασίας), αν και επιπλέον στοίβες μπορούν να δημιουργηθούν από το χειρισμό σημάτων ή τη συνεργατική πολυδιεργασία (όπως με τη setcontext). Από τη στιγμή που υπάρχει μόνο ένα σημαντικό περιβάλλον, αυτό ονομάζεται η στοίβα (εννοώντας "της εργασίας").
Στις γλώσσες υψηλού επιπέδου, οι λεπτομέρειες της στοίβας κλήσεων είναι κρυμμένες από τον προγραμματιστή. Υπάρχει μόνο πρόσβαση στη λίστα των συναρτήσεων και όχι στη μνήμη της ίδιας της στοίβας. Οι περισσότερες συμβολικές γλώσσες, όμως, απαιτούν από τον προγραμματιστή να συμμετέχει στο χειρισμό της στοίβας. Οι πραγματικές λεπτομέρειες της στοίβας σε μια γλώσσα προγραμματισμού εξαρτώνται από το μεταγλωττιστή, το λειτουργικό σύστημα και το διαθέσιμο σύνολο εντολών.

Επεξεργασία θέσης κλήσης (call site processing)

Συνήθως δε χρειάζεται κάποιος ιδιαίτερος χειρισμός της στοίβας κλήσεων στη θέση που καλείται μια υπορουτίνα (κάτι το οποίο είναι καλό - υπάρχουν πολλές θέσεις στις οποίες καλείται κάθε υπορουτίνα). Οι τιμές των πραγματικών ορισμάτων αποτιμώνται στη θέση κλήσης, μιας και αφορούν τη συγκεκριμένη κλήση, και είτε σπρώχνονται στη στοίβα, είτε τοποθετούνται σε καταχωρητές, ανάλογα με τη σύμβαση κλήσης που χρησιμοποιείται. Η πραγματική εντολή της κλήσης, π.χ. η "Branch and Link", εκτελείται στη συνέχεια για να μεταφέρει τον έλεγχο στην υπορουτίνα που κλήθηκε.

Επεξεργασία καλούμενου (callee processing)

Στην υπορουτίνα που κλήθηκε, ο πρώτος κώδικας που καλείται λέγεται συνήθως ο πρόλογος υπορουτίνας, επειδή κάνει όλες τις απαραίτητες πράξεις πριν αρχίσει η εκτέλεση του κώδικα των εντολών της υπορουτίνας.
Ο πρόλογος συνήθως αποθηκεύει τη διεύθυνση επιστροφής που είχε μείνει στον καταχωρητή από την εντολή κλήσης, σπρώχνοντας την τιμή της στη στοίβα. Όμοια, ο τρέχων δείκτης στοίβας και/ή ο δείκτης πλαισίου μπορεί να αποθηκευτούν στη στοίβα. Εναλλακτικά, κάποιες αρχιτεκτονικές παρέχουν αυτόματα τέτοιες λειτουργίες σαν μέρος της ίδιας της εντολής κλήσης, και σε αυτές τις περιπτώσεις ο πρόλογος δε χρειάζεται να κάνει αυτές τις ενέργειες.
Αν χρησιμοποιούνται δείκτες πλαισίων, ο πρόλογος συνήθως θα θέσει τη νέα τιμή του δείκτη πλαισίου από το δείκτη στοίβας. Μπορεί τότε να δεσμευτεί χώρος στη στοίβα για τις τοπικές μεταβλητές αυξάνοντας το δείκτη στοίβας. 
Η γλώσσα προγραμματισμού Forth επιτρέπει το ρητό ξετύλιγμα της στοίβας κλήσεων (που καλείται εκεί "στοίβα επιστροφής"). Η γλώσσα προγραμματισμού Scheme επιτρέπει το τύλιγμα ειδικών πλαισίων μέσα από ένα "δυναμικό τύλιγμα".

Επεξεργασία επιστροφής (return processing)

Όταν μια υπορουτίνα είναι έτοιμη να επιστρέψει, εκτελεί έναν επίλογο που αναιρεί τις ενέργειες του προλόγου. Συνήθως επαναφέρει αποθηκευμένες τιμές των καταχωρητών (όπως η τιμή του δείκτη πλαισίου) από το πλαίσιο στοίβας, θα αφαιρέσει όλο το πλαίσιο στοίβας από τη στοίβα αλλάζοντας την τιμή του του δείκτη στοίβας και στο τέλος θα κάνει άλμα στην εντολή στη διεύθυνση επιστροφής. Κάτω από πολλές συμβάσεις κλήσης αυτά που αφαιρούνται από την κορυφή της στοίβας περιλαμβάνουν τις αρχικές τιμές των ορισμάτων, επομένως δε χρειάζεται να γίνουν άλλες ενέργειες στη στοίβα από τον κώδικα που έκανε την κλήση. Σε κάποιες συμβάσεις κλήσης όμως, είναι υποχρέωση του κώδικα που καλεί να αφαιρέσει τα ορίσματα από τη στοίβα πριν την επιστροφή.

Ξετύλιγμα

Η επιστροφή από τη συνάρτηση που κλήθηκε θα αφαιρέσει το πλαίσιο στην κορυφή της στοίβας, ίσως αφήνοντας κάποια τιμή επιστροφής.
Κάποιες γλώσσες όπως η Pascal επιτρέπουν μια καθολική εντολή goto που να μεταφέρει τον έλεγχο έξω από μια φωλιασμένη συνάρτηση σε μια εξωτερική συνάρτηση που είχε ήδη κληθεί στο παρελθόν. Αυτή η λειτουργία απαιτεί να ξετυλιχτεί η στοίβα, αφαιρώντας όσα πλαίσια στοίβας χρειάζονται ώστε να γίνει η επαναφορά του κατάλληλου περιβάλλοντος για τη μεταφορά του ελέγχου στην κατάλληλη εντολή στην περιβάλλουσα συνάρτηση. Τέτοιες μεταφορές ελέγχου συνήθως συμβαίνουν στη διαχείριση σφαλμάτων.
Κάποιες άλλες γλώσσες (όπως η Object Pascal) παρέχουν διαχείριση εξαιρέσεων, η οποία επίσης χρειάζεται ξετύλιγμα της στοίβας. Το πλαίσιο στοίβας μιας συνάρτησης περιέχει μια ή περισσότερες εγγραφές που ορίζουν κάποιους χειριστές εξαιρέσεων. Όταν εμφανίζεται μια εξαίρεση, η στοίβα ξετυλίγεται μέχρι να βρεθεί ένας χειριστής εξαιρέσεων που να μπορεί να χειριστεί (πιάσει) την εξαίρεση. Η Common Lisp επιτρέπει τον έλεγχο των ενεργειών που γίνονται όταν η στοίβα ξετυλίγεται χρησιμοποιώντας τον ειδικό τελεστή unwind-protect.
Όταν εφαρμόζεται μια συνέχεια, η στοίβα ξετυλίγεται και ξανατυλίγεται με τη στοίβα της συνέχειας. Αυτός δεν είναι ο μοναδικός τρόπος να υλοποιήσουμε τις συνέχειες: με τη χρήση, για παράδειγμα, πολλαπλών στοιβών, μια συνέχεια μπορεί να ενεργοποιήσει απλά τη στοίβα της και να τυλίξει μια τιμή που θέλει να περαστεί.

Στοίβες κλήσεων και δοκιμή λογισμικού

Μια πρόσφατα δημοσιευμένη τεχνική  χρησιμοποιεί τις στοίβες κλήσεων με έναν αρκετά διαφορετικό τρόπο από αυτούς που προαναφέρθηκαν. Χρησιμοποιεί τις στοίβες κλήσεων για αναγωγή δοκιμών (test suite reduction). Εν συντομία, η αναγωγή δοκιμών προσπαθεί να μειώσει τον αριθμό των δοκιμαστικών περιπτώσεων σε μια δοκιμαστική σουίτα διατηρώντας ένα υψηλό ποσοστό της επιτυχίας σήμανσης λαθών της αρχικής σουίτας. Δυο δοκιμαστικές περιπτώσεις θεωρούνται ισοδύναμες αν δημιουργούν το ίδιο σύνολο στοιβών κλήσεων κατά τη διάρκεια της εκτέλεσης. Δείτε το  για περισσότερες λεπτομέρειες.

Ανάλυση της απόδοσης

Η λήψη τυχαίων δειγμάτων από τη στοίβα κλήσεων μπορεί να είναι πολύ χρήσιμη στη βελτιστοποίηση της απόδοσης των προγραμμάτων. Αυτό συμβαίνει γιατί αν μια εντολή κλήσης μιας υπορουτίνας εμφανίζεται στη στοίβα κλήσεων για σημαντικό μέρος του χρόνου εκτέλεσης, η πιθανή αφαίρεσή της θα εξοικονομούσε αρκετό χρόνο. Δείτε Ανάλυση απόδοσης και Deep sampling.

Ασφάλεια

Η ανάμειξη δεδομένων της ροής ελέγχου που επηρεάζουν την εκτέλεση κώδικα (διευθύνσεις επιστροφής, αποθηκευμένοι δείκτες σε πλαίσια) και απλών δεδομένων του προγράμματος (παράμετροι, τιμές επιστροφής) στη στοίβα κλήσεων αποτελεί κενό ασφάλειας που μπορεί κάποιες φορές να γίνει εκμετάλλευσή του με την τεχνική της υπερχείλισης ενταμιευτή (buffer overflow).