สแต็คการโทร

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา

ในวิทยาการคอมพิวเตอร์ call stackเป็นโครงสร้างข้อมูลstack ที่เก็บข้อมูลเกี่ยวกับsubroutines ที่ใช้งาน อยู่ของโปรแกรมคอมพิวเตอร์ สแต็กประเภทนี้เรียกอีกอย่างว่าExecute stack , program stack , control stack , run-time stackหรือmachine stackและมักจะย่อให้เหลือเพียงแค่ " the stack " แม้ว่าการบำรุงรักษา call stack จะมีความสำคัญต่อการทำงานที่เหมาะสมของซอฟต์แวร์ ส่วนใหญ่ แต่โดยปกติรายละเอียดจะถูกซ่อนไว้และเป็นไปโดยอัตโนมัติในภาษาโปรแกรมระดับสูง คอมพิวเตอร์จำนวนมากชุดคำสั่งจัดเตรียมคำสั่งพิเศษสำหรับจัดการสแต็ค

สแต็กการโทรถูกใช้เพื่อวัตถุประสงค์ที่เกี่ยวข้องหลายประการ แต่เหตุผลหลักในการมีอยู่คือการติดตามจุดที่รูทีนย่อยที่ใช้งานอยู่แต่ละรายการควรส่งคืนการควบคุมเมื่อดำเนินการเสร็จสิ้น รูทีนย่อยที่แอ็คทีฟคือรูทีนที่เรียกใช้แล้ว แต่ยังดำเนินการไม่เสร็จสิ้น หลังจากนั้นควรส่งการควบคุมกลับไปยังจุดที่โทร การเปิดใช้งานรูทีนย่อยดังกล่าวอาจซ้อนกันในระดับใดก็ได้ (เรียกซ้ำเป็นกรณีพิเศษ) ดังนั้นโครงสร้างสแต็ก ตัวอย่างเช่น หากรูทีนย่อยDrawSquareเรียกรูทีนย่อยDrawLineจากที่ต่างกันสี่แห่งDrawLineต้องรู้ว่าจะส่งคืนที่ใดเมื่อการดำเนินการเสร็จสิ้น เพื่อให้บรรลุสิ่งนี้ที่อยู่ตามคำสั่งที่ข้ามไปที่DrawLine, ที่อยู่ผู้ส่ง, ถูกผลักไปที่ด้านบนสุดของสแต็กการโทรด้วยการโทรแต่ละครั้ง

คำอธิบาย

เนื่องจาก call stack ถูกจัดระเบียบเป็นstackผู้โทรจึงพุชที่อยู่ผู้ส่งกลับไปยังสแต็ก และรูทีนย่อยที่ถูกเรียก เมื่อเสร็จสิ้นดึงหรือแสดงที่อยู่ผู้ส่งกลับจาก call stack และโอนการควบคุมไปยังที่อยู่นั้น หากรูทีนย่อยที่เรียกเรียกเรียกใช้รูทีนย่อยอื่น รูทีนย่อยอื่นจะพุชที่อยู่ผู้ส่งอื่นไปยังคอลสแต็ก และอื่นๆ โดยที่ข้อมูลจะซ้อนขึ้นและคลายสแต็กตามที่โปรแกรมกำหนด หากการพุชใช้พื้นที่ทั้งหมดที่จัดสรรไว้สำหรับ call stack จะเกิดข้อผิดพลาดที่เรียกว่าstack overflowซึ่งโดยทั่วไปจะทำให้โปรแกรมหยุดทำงาน การเพิ่มรายการของรูทีนย่อยไปยัง call stack บางครั้งเรียกว่า "winding"; ในทางกลับกัน การลบรายการคือ "การคลี่คลาย"

โดยปกติจะมี call stack ที่เกี่ยวข้องกับโปรแกรมที่กำลังรันอยู่ (หรือแม่นยำกว่านั้น กับแต่ละงานหรือthreadของprocess ) แม้ว่าอาจมีการสร้าง stack เพิ่มเติมสำหรับ การ จัดการสัญญาณ หรือการ ทำงานหลายอย่างพร้อมกัน (เช่นเดียวกับsetcontext ) เนื่องจากมีเพียงหนึ่งในบริบทที่สำคัญนี้ จึงสามารถเรียกว่าแต็ก (โดยปริยาย "ของงาน"); อย่างไรก็ตาม ใน ภาษา การเขียนโปรแกรม Forth สแต็กข้อมูลหรือพารามิเตอร์สแต็กสามารถเข้าถึงได้อย่างชัดเจนมากกว่าคอลสแต็ก และโดยทั่วไปจะเรียกว่าแต็ก (ดูด้านล่าง)

ในภาษาโปรแกรมระดับสูงข้อมูลเฉพาะของ call stack มักจะถูกซ่อนจากโปรแกรมเมอร์ พวกเขาจะได้รับการเข้าถึงเฉพาะชุดของฟังก์ชันเท่านั้น ไม่ใช่หน่วยความจำบนสแต็กเอง นี่คือตัวอย่างของนามธรรม ในทางกลับกัน ภาษาแอสเซมบลีส่วนใหญ่ต้องการให้โปรแกรมเมอร์เกี่ยวข้องกับการจัดการสแต็ก รายละเอียดที่แท้จริงของสแต็กในภาษาการเขียนโปรแกรมขึ้นอยู่กับคอมไพเลอร์ระบบปฏิบัติการและชุดคำสั่ง ที่มี อยู่

หน้าที่ของ call stack

ดังที่กล่าวไว้ข้างต้น วัตถุประสงค์หลักของ call stack คือการจัดเก็บที่อยู่ผู้ส่งกลับ เมื่อมีการเรียกรูทีนย่อย ตำแหน่ง (ที่อยู่) ของคำสั่งที่รูทีนการเรียกสามารถกลับมาทำงานต่อได้ในภายหลังจะต้องถูกบันทึกไว้ที่ใดที่หนึ่ง การใช้สแต็กเพื่อบันทึกที่อยู่ผู้ส่งมีข้อได้เปรียบที่สำคัญเหนือแบบแผนการเรียก ทางเลือกบางอย่าง เช่น การบันทึกที่อยู่ผู้ส่งก่อนเริ่มต้นรูทีนย่อยที่เรียกหรือในตำแหน่งคงที่อื่นๆ หนึ่งคืองานแต่ละงานสามารถมีสแต็กของตัวเองได้ ดังนั้นรูทีนย่อยจึงสามารถเป็นthread-safeได้ กล่าวคือ สามารถแอ็คทีฟพร้อมกันสำหรับงานต่างๆ ที่ทำสิ่งต่าง ๆ ได้ ประโยชน์อีกประการหนึ่งคือการให้reentrancy , recursionได้รับการสนับสนุนโดยอัตโนมัติ เมื่อฟังก์ชันเรียกตัวเองแบบเรียกซ้ำ จะต้องจัดเก็บที่อยู่ผู้ส่งสำหรับการเปิดใช้งานฟังก์ชันแต่ละครั้ง เพื่อให้สามารถใช้เพื่อย้อนกลับจากการเปิดใช้งานฟังก์ชันได้ในภายหลัง โครงสร้างสแต็กให้ความสามารถนี้โดยอัตโนมัติ

สแต็กการโทรอาจให้บริการเพื่อวัตถุประสงค์เพิ่มเติม ทั้งนี้ขึ้นอยู่กับภาษา ระบบปฏิบัติการ และสภาพแวดล้อมของเครื่อง ซึ่งรวมถึง:

การจัดเก็บข้อมูลในเครื่อง
รูทีนย่อยมักต้องการพื้นที่หน่วยความจำสำหรับจัดเก็บค่าของตัวแปรโลคัล ตัวแปรที่ทราบเฉพาะภายในรูทีนย่อยที่แอ็คทีฟเท่านั้น และไม่เก็บค่าหลังจากส่งคืน มักจะสะดวกในการจัดสรรพื้นที่สำหรับการใช้งานนี้โดยเพียงแค่ย้ายส่วนบนของสแต็กให้เพียงพอเพื่อให้มีที่ว่าง ซึ่งเร็วมากเมื่อเทียบกับการจัดสรรหน่วยความจำแบบไดนามิกซึ่งใช้พื้นที่ฮีโปรดทราบว่าแต่ละการเปิดใช้งานรูทีนย่อยแยกกันจะมีพื้นที่แยกต่างหากในสแต็กสำหรับโลคัล
ผ่านพารามิเตอร์
รูทีนย่อยมักจะต้องการให้ค่าสำหรับพารามิเตอร์ถูกระบุโดยโค้ดที่เรียกใช้ และไม่ใช่เรื่องแปลกที่พื้นที่สำหรับพารามิเตอร์เหล่านี้อาจถูกจัดวางใน call stack โดยทั่วไป หากมีพารามิเตอร์ขนาดเล็กเพียงไม่กี่ ตัว การ ลงทะเบียนโปรเซสเซอร์จะถูกใช้เพื่อส่งผ่านค่า แต่ถ้ามีพารามิเตอร์มากกว่าที่จะจัดการได้ด้วยวิธีนี้ จะต้องใช้พื้นที่หน่วยความจำ call stack ทำงานได้ดีเป็นที่สำหรับพารามิเตอร์เหล่านี้ โดยเฉพาะอย่างยิ่งเนื่องจากการเรียกไปยังรูทีนย่อยแต่ละครั้ง ซึ่งจะมีค่าพารามิเตอร์ที่แตกต่างกัน จะได้รับพื้นที่แยกต่างหากบน call stack สำหรับค่าเหล่านั้น
กองการประเมิน
ตัวถูกดำเนินการสำหรับการดำเนินการทางคณิตศาสตร์หรือเชิงตรรกะมักถูกวางไว้ในรีจิสเตอร์และดำเนินการที่นั่น อย่างไรก็ตาม ในบางสถานการณ์ ตัวถูกดำเนินการอาจซ้อนกันได้ถึงความลึกตามอำเภอใจ ซึ่งหมายความว่าต้องใช้บางอย่างมากกว่าการลงทะเบียน (นี่คือกรณีของregister scattering ) สแต็กของตัวถูกดำเนินการดังกล่าว ค่อนข้างเหมือนกับในเครื่องคิดเลข RPNเรียกว่า สแต็กการประเมิน และอาจใช้พื้นที่ในคอลสแต็ก
ตัวชี้ไปยังอินสแตนซ์ปัจจุบัน
ภาษาเชิงวัตถุบาง ภาษา (เช่นC++ ) เก็บตัวชี้นี้พร้อมกับอาร์กิวเมนต์ของฟังก์ชันใน call stack เมื่อเรียกใช้เมธอด ตัว ชี้ นี้ชี้ไปที่อินสแตนซ์อ็อบเจ็กต์ ที่เกี่ยวข้องกับเมธอดที่จะเรียกใช้
การปิดบริบทรูทีนย่อย
ภาษาโปรแกรมบางภาษา (เช่นPascalและAda ) รองรับการประกาศรูทีนย่อยที่ซ้อนกันซึ่งได้รับอนุญาตให้เข้าถึงบริบทของรูทีนที่ล้อมรอบอยู่ กล่าวคือ พารามิเตอร์และตัวแปรท้องถิ่นภายในขอบเขตของรูทีนภายนอก การซ้อนสแตติกดังกล่าวสามารถทำซ้ำได้ (ฟังก์ชันที่ประกาศภายในฟังก์ชันที่ประกาศภายในฟังก์ชัน...) การใช้งานต้องจัดเตรียมวิธีการที่ฟังก์ชันที่เรียกในระดับการซ้อนสแตติกที่ระบุสามารถอ้างอิงเฟรมที่ล้อมรอบในแต่ละระดับการซ้อนที่ล้อมรอบ โดยทั่วไปแล้ว การอ้างอิงนี้จะดำเนินการโดยตัวชี้ไปยังเฟรมของอินสแตนซ์ที่เปิดใช้งานล่าสุดของฟังก์ชันการปิดล้อม ที่เรียกว่า "ลิงก์ดาวน์สแต็ก" หรือ "ลิงก์แบบคงที่" เพื่อแยกความแตกต่างจาก "ลิงก์แบบไดนามิก" ที่อ้างอิงถึงผู้เรียกทันที ( ซึ่งไม่จำเป็นต้องเป็นฟังก์ชันพาเรนต์แบบคงที่)

แทนที่จะเป็นลิงก์แบบสแตติก การอ้างอิงไปยังเฟรมสแตติกที่ปิดอยู่อาจถูกรวบรวมไว้ในอาร์เรย์ของพอยน์เตอร์ที่เรียกว่าจอแสดงผลซึ่งจัดทำดัชนีเพื่อระบุตำแหน่งเฟรมที่ต้องการ ความลึกของการซ้อนคำศัพท์ของรูทีนเป็นค่าคงที่ที่ทราบ ดังนั้นขนาดของการแสดงรูทีนจึงคงที่ นอกจากนี้ยังทราบจำนวนของขอบเขตที่มีการสำรวจ ดัชนีในการแสดงผลก็คงที่เช่นกัน โดยปกติ การแสดงผลของกิจวัตรจะอยู่ในสแต็กเฟรมของตัวเอง แต่Burroughs B6500ใช้จอแสดงผลดังกล่าวในฮาร์ดแวร์ซึ่งรองรับการซ้อนสแตติกได้ถึง 32 ระดับ
รายการแสดงผลที่แสดงถึงขอบเขตนั้นได้มาจากคำนำหน้าที่เหมาะสมของการแสดงผลของผู้โทร รูทีนภายในซึ่งเรียกซ้ำจะสร้างเฟรมการโทรแยกต่างหากสำหรับการเรียกใช้แต่ละครั้ง ในกรณีนี้ ลิงก์สแตติกของรูทีนภายในทั้งหมดชี้ไปที่บริบทรูทีนภายนอกเดียวกัน
สถานะการส่งคืนอื่น ๆ
ข้างที่อยู่ผู้ส่ง ในบางสภาพแวดล้อมอาจมีสถานะเครื่องหรือซอฟต์แวร์อื่นที่ต้องกู้คืนเมื่อรูทีนย่อยกลับมา ซึ่งอาจรวมถึงสิ่งต่างๆ เช่น ระดับสิทธิ์ ข้อมูลการจัดการข้อยกเว้น โหมดเลขคณิต และอื่นๆ หากจำเป็น ค่านี้อาจถูกเก็บไว้ใน call stack เช่นเดียวกับที่อยู่ผู้ส่ง

สแต็กการโทรทั่วไปใช้สำหรับที่อยู่ผู้ส่ง โลคัล และพารามิเตอร์ (เรียกว่าcall frame ) ในบางสภาพแวดล้อม อาจมีฟังก์ชันที่กำหนดให้กับ call stack มากหรือน้อย ในภาษาโปรแกรม Forthตัวอย่างเช่น โดยปกติเฉพาะที่อยู่ที่ส่งคืน พารามิเตอร์ลูปที่นับและดัชนี และตัวแปรโลคัลอาจถูกเก็บไว้ใน call stack (ซึ่งในสภาพแวดล้อมนั้นมีชื่อว่าreturn stack ) แม้ว่าข้อมูลใด ๆ จะถูกวางชั่วคราว ที่นั่นโดยใช้รหัสการจัดการการส่งคืนแบบพิเศษ ตราบใดที่ยังคำนึงถึงความต้องการของการโทรและการส่งคืน โดยปกติพารามิเตอร์จะถูกเก็บไว้ใน สแต็ก ข้อมูล แยกต่างหาก หรือ ส แต็คพารามิเตอร์โดยทั่วไปเรียกว่าstack ในคำศัพท์ Forth แม้ว่าจะมี call stack เนื่องจากมักจะเข้าถึงได้ชัดเจนกว่า Forths บางตัวยังมีสแต็คที่สามสำหรับพารามิเตอร์ ทศนิยม

โครงสร้าง

เค้าโครง Call stack สำหรับ stack ที่เพิ่มขึ้นหลังจากDrawSquareรูทีนย่อย (แสดงเป็นblue ) ที่เรียกว่าDrawLine(แสดงเป็นgreen ) ซึ่งเป็นรูทีนที่ดำเนินการอยู่ในปัจจุบัน

สแต็ กการโทรประกอบด้วยสแต็กเฟรม (เรียกอีกอย่างว่าบันทึกการเปิด ใช้งาน หรือเฟรมการเปิดใช้งาน ) โครงสร้าง เหล่านี้ขึ้นอยู่กับเครื่องและ โครงสร้างข้อมูลที่ขึ้นกับ ABIที่มีข้อมูลสถานะรูทีนย่อย แต่ละสแต็กเฟรมสอดคล้องกับการเรียกรูทีนย่อยที่ยังไม่สิ้นสุดด้วยการส่งคืน ตัวอย่างเช่น หากรูทีนย่อยที่ชื่อDrawLineกำลังทำงานอยู่ โดยถูกเรียกโดยรูทีนย่อยDrawSquareส่วนบนของสแต็กการโทรอาจถูกจัดวางเหมือนในรูปภาพที่อยู่ติดกัน

ไดอะแกรมแบบนี้สามารถวาดได้ทั้งสองทิศทางตราบเท่าที่ตำแหน่งของด้านบน และทิศทางของการเติบโตของกอง เป็นที่เข้าใจ นอกจากนี้ โดยไม่ขึ้นกับสิ่งนี้ สถาปัตยกรรมแตกต่างกันว่า call stack เติบโตขึ้นตามที่อยู่ที่สูงขึ้นหรือไปยังที่อยู่ที่ต่ำกว่า ตรรกะของไดอะแกรมไม่ขึ้นอยู่กับตัวเลือกที่อยู่

สแต็กเฟรมที่ด้านบนสุดของสแต็กมีไว้สำหรับรูทีนที่กำลังดำเนินการอยู่ ซึ่งสามารถเข้าถึงข้อมูลภายในเฟรม (เช่น พารามิเตอร์หรือตัวแปรในเครื่อง) ในลำดับใดก็ได้ [1]สแต็กเฟรมมักจะมีรายการต่อไปนี้เป็นอย่างน้อย (ตามลำดับการพุช):

  • อาร์กิวเมนต์ (ค่าพารามิเตอร์) ที่ส่งผ่านไปยังรูทีน (ถ้ามี)
  • ที่อยู่ผู้ส่งกลับไปยังผู้เรียกของรูทีน (เช่นในDrawLineสแต็กเฟรม, ที่อยู่ในDrawSquareโค้ดของ); และ
  • พื้นที่สำหรับตัวแปรโลคัลของรูทีน (ถ้ามี)

ตัวชี้สแต็คและเฟรม

เมื่อขนาดเฟรมสแต็กอาจแตกต่างกัน เช่น ระหว่างฟังก์ชันต่างๆ หรือระหว่างการเรียกใช้ฟังก์ชันเฉพาะ การดึงเฟรมออกจากสแต็กไม่ถือเป็นการลดค่าคงที่ของตัวชี้สแต็เมื่อฟังก์ชันส่งคืน ตัวชี้สแต็กจะถูกคืนค่าไปที่ตัวชี้เฟรมแทน ค่าของตัวชี้สแต็กก่อนเรียกใช้ฟังก์ชัน แต่ละสแต็กเฟรมมีตัวชี้สแต็กไปที่ด้านบนของเฟรมด้านล่างทันที ตัวชี้สแต็กเป็นรีจิสเตอร์ที่ไม่แน่นอนที่ใช้ร่วมกันระหว่างการเรียกใช้ทั้งหมด ตัวชี้เฟรมของการเรียกใช้ฟังก์ชันที่กำหนดคือสำเนาของตัวชี้สแต็กเหมือนที่เคยเป็นก่อนเรียกใช้ฟังก์ชัน [2]

ตำแหน่งของฟิลด์อื่นๆ ทั้งหมดในเฟรมสามารถกำหนดได้โดยสัมพันธ์กับด้านบนของเฟรม เป็นค่าลบของตัวชี้สแต็ก หรือสัมพันธ์กับด้านบนของเฟรมด้านล่าง เป็นค่าบวกของตัวชี้เฟรม ตำแหน่งของตัวชี้เฟรมเองต้องถูกกำหนดโดยเนื้อแท้เป็นออฟเซ็ตเชิงลบของตัวชี้สแต็ก

การจัดเก็บที่อยู่ในกรอบของผู้โทร

ในระบบส่วนใหญ่ สแต็กเฟรมมีฟิลด์สำหรับเก็บค่าก่อนหน้าของการลงทะเบียนตัวชี้เฟรม ค่าที่มีอยู่ในขณะที่ผู้เรียกดำเนินการ ตัวอย่างเช่น สแต็กเฟรมของDrawLineจะมีตำแหน่งหน่วยความจำที่เก็บค่าตัวชี้เฟรมที่DrawSquareใช้ (ไม่แสดงในไดอะแกรมด้านบน) ค่าจะถูกบันทึกเมื่อเข้าสู่รูทีนย่อยและกู้คืนเมื่อส่งคืน การมีฟิลด์ดังกล่าวในตำแหน่งที่รู้จักในสแต็กเฟรมช่วยให้โค้ดเข้าถึงแต่ละเฟรมอย่างต่อเนื่องภายใต้เฟรมของรูทีนที่กำลังดำเนินการอยู่ และยังช่วยให้รูทีนสามารถคืนค่าตัวชี้เฟรมไปยัง เฟรม ของผู้ เรียกได้อย่างง่ายดาย ก่อนที่มันจะกลับมา

รูทีนซ้อนคำศัพท์

ภาษาโปรแกรมที่สนับสนุนรูทีนย่อยที่ซ้อนกันยังมีฟิลด์ในเฟรมการเรียกที่ชี้ไปที่สแต็กเฟรมของการ เปิดใช้งานโพรซีเดอร์ ล่าสุดที่ห่อหุ้ม callee อย่างใกล้ชิด กล่าวคือขอบเขตของ callee ในทันที นี่เรียกว่าลิงก์เข้าใช้หรือลิงก์แบบคงที่(เนื่องจากจะติดตามการซ้อนสแตติกระหว่างการโทรแบบไดนามิกและแบบเรียกซ้ำ) และให้รูทีน (รวมถึงรูทีนอื่นๆ ที่อาจเรียกใช้) เข้าถึงข้อมูลในเครื่องของรูทีนการห่อหุ้มในทุกระดับการซ้อน สถาปัตยกรรม คอมไพเลอร์ หรือกรณีการปรับให้เหมาะสมบางตัวเก็บหนึ่งลิงก์สำหรับแต่ละระดับการปิดล้อม (ไม่ใช่แค่การปิดล้อมทันที) ดังนั้นรูทีนที่ซ้อนกันอย่างลึกล้ำซึ่งเข้าถึงข้อมูลตื้นไม่จำเป็นต้องข้ามหลายลิงก์ กลยุทธ์นี้มักเรียกว่า "การแสดงผล" [3]

ลิงก์การเข้าถึงสามารถเพิ่มประสิทธิภาพได้เมื่อฟังก์ชันภายในไม่เข้าถึงข้อมูลภายในเครื่อง (ไม่คงที่) ในการห่อหุ้ม เช่นเดียวกับกรณีที่ฟังก์ชันบริสุทธิ์สื่อสารผ่านอาร์กิวเมนต์และค่าที่ส่งกลับเท่านั้น คอมพิวเตอร์ในอดีตบางเครื่อง เช่นระบบขนาดใหญ่ของ Burroughsมี "รีจิสเตอร์การแสดงผล" พิเศษเพื่อรองรับฟังก์ชันที่ซ้อนกัน ในขณะที่คอมไพเลอร์สำหรับเครื่องที่ทันสมัยส่วนใหญ่ (เช่น x86 ที่แพร่หลาย) เพียงแค่สำรองคำสองสามคำบนสแต็กสำหรับพอยน์เตอร์ ตามความจำเป็น

ทับซ้อนกัน

สำหรับวัตถุประสงค์บางอย่าง สแต็กเฟรมของรูทีนย่อยและรูทีนของรูทีนสามารถพิจารณาว่าคาบเกี่ยวกันได้ การคาบเกี่ยวกันประกอบด้วยพื้นที่ที่พารามิเตอร์ถูกส่งผ่านจากผู้เรียกไปยังผู้รับแคลลี ในบางสภาพแวดล้อม ผู้เรียกจะพุชอาร์กิวเมนต์แต่ละรายการไปยังสแต็ก ดังนั้นจะขยายสแต็กเฟรม จากนั้นเรียกใช้ callee ในสภาพแวดล้อมอื่น ผู้เรียกจะมีพื้นที่ที่จัดสรรล่วงหน้าไว้ที่ด้านบนสุดของสแต็กเฟรมเพื่อเก็บอาร์กิวเมนต์ที่ส่งไปยังรูทีนย่อยอื่นๆ ที่เรียกใช้ พื้นที่นี้บางครั้งเรียกว่าพื้นที่อาร์กิวเมนต์ขาออกหรือ พื้นที่ คำบรรยาย ภายใต้แนวทางนี้ ขนาดของพื้นที่จะถูกคำนวณโดยคอมไพเลอร์เพื่อให้เป็นรูทีนย่อยที่เรียกว่าใหญ่ที่สุดที่จำเป็น

ใช้

การประมวลผลไซต์การโทร

โดยปกติการจัดการ call stack ที่จำเป็นที่ไซต์ของการเรียกไปยังรูทีนย่อยจะน้อยที่สุด (ซึ่งเป็นสิ่งที่ดีเนื่องจากสามารถมีไซต์การโทรจำนวนมากสำหรับรูทีนย่อยแต่ละรูทีนที่จะเรียก) ค่าสำหรับอาร์กิวเมนต์ที่เกิดขึ้นจริงจะถูกประเมินที่ไซต์การโทร เนื่องจากเป็นค่าเฉพาะสำหรับการเรียกนั้น ๆ และอาจพุชไปยังสแต็กหรือวางไว้ในรีจิสเตอร์ ตามที่กำหนดโดยแบบแผนการเรียกที่ ใช้ คำสั่งการโทรจริง เช่น "สาขาและลิงก์" จะดำเนินการตามปกติเพื่อถ่ายโอนการควบคุมไปยังรหัสของรูทีนย่อยเป้าหมาย

การประมวลผลรายการย่อย

ในรูทีนย่อยที่เรียก รหัสแรกที่ดำเนินการมักจะถูกเรียกว่าบทนำของรูทีนเนื่องจากมันทำหน้าที่ดูแลทำความสะอาดที่จำเป็น ก่อนที่โค้ดสำหรับคำสั่งของรูทีนจะเริ่มขึ้น

สำหรับสถาปัตยกรรมชุดคำสั่งซึ่งคำสั่งที่ใช้ในการเรียกรูทีนย่อยใส่ที่อยู่ผู้ส่งกลับลงในรีจิสเตอร์ แทนที่จะผลักมันลงบนสแต็ก อารัมภบทมักจะบันทึกที่อยู่ผู้ส่งกลับโดยการผลักค่าไปยังสแต็กการเรียก แม้ว่าการเรียก รูทีนย่อยไม่เรียกรูทีนอื่นใด ซึ่งอาจทิ้งค่าไว้ในรีจิสเตอร์ ในทำนองเดียวกัน ค่าตัวชี้สแต็กปัจจุบันและ/หรือตัวชี้เฟรมอาจถูกผลัก

หากมีการใช้ตัวชี้เฟรม บทนำมักจะตั้งค่าใหม่ของการลงทะเบียนตัวชี้เฟรมจากตัวชี้สแต็ก พื้นที่บนสแต็กสำหรับตัวแปรโลคัลสามารถจัดสรรได้โดยการเปลี่ยนตัวชี้สแต็กแบบค่อยเป็นค่อยไป

ภาษา การเขียนโปรแกรม Forthอนุญาตให้มีการม้วน call stack อย่างชัดเจน (เรียกว่า "return stack")

ส่งคืนการประมวลผล

เมื่อรูทีนย่อยพร้อมที่จะส่งคืน รันบทส่งท้ายที่จะยกเลิกขั้นตอนของอารัมภบท โดยทั่วไปจะคืนค่ารีจิสเตอร์ที่บันทึกไว้ (เช่น ค่าตัวชี้เฟรม) จากสแต็กเฟรม ดึงสแต็กเฟรมทั้งหมดออกจากสแต็กโดยเปลี่ยนค่าตัวชี้สแต็ก และสุดท้ายแยกย่อยไปยังคำสั่งที่อยู่ที่ส่งคืน ภายใต้ข้อตกลงการเรียกหลายรายการ รายการที่โผล่ออกมาจากสแต็กโดยบทส่งท้ายรวมถึงค่าอาร์กิวเมนต์ดั้งเดิม ซึ่งในกรณีนี้มักจะไม่มีการจัดการสแต็กเพิ่มเติมที่ผู้เรียกต้องทำ อย่างไรก็ตาม ด้วยข้อตกลงการเรียกบางอย่าง มันเป็นความรับผิดชอบของผู้เรียกที่จะลบอาร์กิวเมนต์ออกจากสแต็กหลังจากการส่งคืน

คลายเครียด

การกลับมาจากฟังก์ชันที่เรียกจะทำให้เฟรมบนสุดหลุดออกจากสแต็ก อาจทำให้เหลือค่าที่ส่งคืน การกระทำทั่วๆ ไปของการแตกเฟรมตั้งแต่หนึ่งเฟรมขึ้นไปออกจากสแต็กเพื่อดำเนินการต่อในที่อื่นในโปรแกรมเรียกว่าการคลายสแต็ ก และต้องดำเนินการเมื่อใช้โครงสร้างการควบคุมที่ไม่ใช่โลคัล เช่น โครงสร้างที่ใช้สำหรับ การจัดการ ข้อยกเว้น ในกรณีนี้ สแต็กเฟรมของฟังก์ชันประกอบด้วยหนึ่งรายการขึ้นไปที่ระบุตัวจัดการข้อยกเว้น เมื่อมีการส่งข้อยกเว้น สแต็กจะคลายออกจนกว่าจะพบตัวจัดการที่เตรียมที่จะจัดการ (จับ) ประเภทของข้อยกเว้นที่ส่งออกมา

บางภาษามีโครงสร้างการควบคุมอื่นๆ ที่ต้องการการคลายตัวโดยทั่วไป Pascal อนุญาตให้คำสั่ง gotoส่วนกลางถ่ายโอนการควบคุมจากฟังก์ชันที่ซ้อนกันและไปยังฟังก์ชันภายนอกที่เรียกใช้ก่อนหน้านี้ การดำเนินการนี้ต้องการให้คลายสแตก ลบสแต็กเฟรมให้มากเท่าที่จำเป็นเพื่อกู้คืนบริบทที่เหมาะสมเพื่อถ่ายโอนการควบคุมไปยังคำสั่งเป้าหมายภายในฟังก์ชันภายนอกที่ล้อมรอบ ในทำนองเดียวกัน C มีsetjmpandlongjmpฟังก์ชั่นที่ทำหน้าที่เป็น gotos ที่ไม่ใช่ในเครื่อง Common Lispอนุญาตให้ควบคุมสิ่งที่จะเกิดขึ้นเมื่อมีการคลายสแต็กโดยใช้ตัวunwind-protectดำเนินการพิเศษ

เมื่อใช้ความต่อเนื่องสแต็กจะคลาย (ตามหลักเหตุผล) แล้วจึงกรอกลับด้วยสแต็กของความต่อเนื่อง นี่ไม่ใช่วิธีเดียวที่จะใช้ความต่อเนื่อง ตัวอย่างเช่น การใช้สแต็กที่ชัดเจนหลายอัน แอปพลิเคชันของความต่อเนื่องสามารถเปิดใช้งานสแต็กของมันและกรอกค่าที่จะส่งผ่าน ภาษา การเขียนโปรแกรม Schemeอนุญาตให้ ดำเนินการ thunk โดยพล การในจุดที่ระบุใน "การคลาย" หรือ "การกรอกลับ" ของสแต็กควบคุมเมื่อมีการเรียกใช้ความต่อเนื่อง

การตรวจสอบ

บางครั้ง call stack สามารถตรวจสอบได้ในขณะที่โปรแกรมกำลังทำงานอยู่ ข้อมูลในสแต็กสามารถใช้เพื่อกำหนดค่ากลางและการติดตามการเรียกใช้ฟังก์ชันได้ ทั้งนี้ขึ้นอยู่กับวิธีการเขียนและคอมไพล์โปรแกรม สิ่งนี้ถูกใช้เพื่อสร้างการทดสอบอัตโนมัติแบบละเอียด[4]และในกรณีเช่น Ruby และ Smalltalk เพื่อใช้ความต่อเนื่องระดับเฟิร์สคลาส ตัวอย่างเช่นGNU Debugger (GDB) ใช้การตรวจสอบเชิงโต้ตอบของ call stack ของโปรแกรม C ที่รันอยู่ แต่หยุดชั่วคราว [5]

การสุ่มตัวอย่าง call stack ตามเวลาปกติอาจมีประโยชน์ในการสร้างโปรไฟล์ประสิทธิภาพของโปรแกรม เพราะหากตัวชี้ของรูทีนย่อยปรากฏขึ้นบนข้อมูลสุ่มตัวอย่าง call stack หลายครั้ง อาจเป็นปัญหาคอขวดของโค้ดและควรตรวจสอบปัญหาด้านประสิทธิภาพ

ความปลอดภัย

ในภาษาที่มีพอยน์เตอร์อิสระหรือการเขียนอาร์เรย์ที่ไม่ได้ตรวจสอบ (เช่นในภาษา C) การผสมข้อมูลโฟลว์การควบคุมที่ส่งผลต่อการทำงานของโค้ด (ที่อยู่ส่งคืนหรือพอยน์เตอร์เฟรมที่บันทึกไว้) และข้อมูลโปรแกรมอย่างง่าย (พารามิเตอร์หรือค่าที่ส่งคืน ) ใน call stack มีความเสี่ยงด้านความปลอดภัย ซึ่งอาจใช้ประโยชน์ ได้ ผ่านstack buffer overflowเนื่องจากเป็นประเภทbuffer overflow ที่พบบ่อย ที่สุด

หนึ่งในการโจมตีดังกล่าวเกี่ยวข้องกับการเติมบัฟเฟอร์หนึ่งอันด้วยโค้ดสั่งการได้ตามอำเภอใจ จากนั้นจึงโอเวอร์โฟลว์บัฟเฟอร์เดียวกันหรือบางบัฟเฟอร์เพื่อเขียนทับที่อยู่ส่งคืนด้วยค่าที่ชี้ไปยังโค้ดสั่งการโดยตรง เป็นผลให้เมื่อฟังก์ชันส่งคืน คอมพิวเตอร์รันโค้ดนั้น การโจมตีประเภทนี้สามารถบล็อกได้อย่างง่ายดายด้วยW ^X [ ต้องการอ้างอิง ]การโจมตีที่คล้ายกันสามารถทำได้สำเร็จแม้จะเปิดใช้งานการป้องกัน W^X รวมถึงการโจมตีแบบ return-to-libcหรือการโจมตีที่มาจากการเขียนโปรแกรมเชิงส่งคืน มีการเสนอการบรรเทาปัญหาต่างๆ เช่น การจัดเก็บอาร์เรย์ในตำแหน่งที่แยกจากกันโดยสิ้นเชิงจากสแต็กส่งคืน เช่นเดียวกับกรณีในภาษาการเขียนโปรแกรม Forth [6]

ดูเพิ่มเติม

อ้างอิง

  1. ↑ Krzyzanowski , Paul (16 กุมภาพันธ์ 2018). "สแต็คเฟรม" . มหาวิทยาลัยรัตเกอร์ส . เก็บถาวรจากต้นฉบับเมื่อ2021-08-28 สืบค้นเมื่อ19 ธันวาคม 2021 .
  2. ^ "ทำความเข้าใจกับกอง" . cs.umd.edu _ 2546-06-22. เก็บถาวรจากต้นฉบับเมื่อ 2013-02-25 . สืบค้นเมื่อ2014-05-21 .
  3. ^ การออกแบบไมโครโปรเซสเซอร์ทางเลือก
  4. ^ McMaster, S.; เมมอน, เอ. (2549). Call Stack Coverage สำหรับ GUI Test-Suite Reduction (PDF ) การประชุมวิชาการระดับนานาชาติครั้งที่ 17 ด้านวิศวกรรมความน่าเชื่อถือของซอฟต์แวร์ ( ISSRE '06) น. 33–44. CiteSeerX 10.1.1.88.873 . ดอย : 10.1109/ISSRE.2006.19 . ISBN   0-7695-2684-5.
  5. ^ "การดีบักด้วย GDB: การตรวจสอบสแต็ก " chemie.fu-berlin.de _ 1997-10-17 . สืบค้นเมื่อ2014-12-16 .
  6. ดั๊ก ฮอยต์. "The Forth Programming Language - ทำไมคุณควรเรียนรู้มัน" .

อ่านเพิ่มเติม

ลิงค์ภายนอก