heap_allocator
1.0.0
นี่คือตัวจัดสรรฮีปอย่างง่ายที่ฉันเขียนสำหรับระบบปฏิบัติการงานอดิเรกที่ฉันกำลังทำอยู่ ฉันเขียนตัวจัดสรรนี้โดยอาศัยการวิจัยเพียงเล็กน้อย และออกแบบให้เข้าใจง่ายที่สุดเท่าที่จะเป็นไปได้ ฉันคิดว่าพื้นที่เก็บข้อมูลนี้จะมีประโยชน์สำหรับผู้ที่ยังใหม่ต่อการพัฒนาระบบปฏิบัติการ (เช่นตัวฉันเอง) หรือสนใจที่จะเห็นฟังก์ชันเวอร์ชันที่เรียบง่ายเช่น malloc และฟรี
มีไฟล์ส่วนหัวสองไฟล์ที่กำหนดฮีปและรายการที่เชื่อมโยง เพื่อรวบรวมที่เก็บนี้:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
นี่จะเป็นการสาธิตตัวจัดสรรและพิมพ์ข้อมูลบางส่วน
ในการเริ่มต้นฮีปนี้ จะต้องจัดเตรียมส่วนของหน่วยความจำไว้ ในที่เก็บนี้ หน่วยความจำนั้นจัดทำโดย malloc (ใช่ การจัดสรรฮีปผ่านฮีป) ในการตั้งค่าระบบปฏิบัติการ บางหน้าจะต้องได้รับการแมปและจัดหาให้กับฮีป (หนึ่งสถานการณ์) โปรดทราบว่าถังขยะในโครงสร้าง heap_t จำเป็นต้องจัดสรรหน่วยความจำด้วย
เมื่อฟังก์ชัน init_heap ถูกเรียกว่า จะต้องระบุที่อยู่ของโครงสร้างฮีปว่าง (พร้อมตัวชี้ช่องเก็บที่จัดสรรไว้) จากนั้นฟังก์ชัน init_heap จะสร้างชิ้นส่วนขนาดใหญ่หนึ่งอันที่มีส่วนหัว ( node_t struct) และส่วนท้าย ( footer_t struct) ในการกำหนดขนาดของส่วนนี้ ฟังก์ชันจะใช้ค่าคงที่ HEAP_INIT_SIZE มันจะเพิ่มสิ่งนี้ลงในอาร์กิวเมนต์ start เพื่อกำหนดว่าฮีปจะสิ้นสุดที่ใด
แต่ละส่วนของหน่วยความจำมีโครงสร้างโหนดที่จุดเริ่มต้นและโครงสร้างส่วนท้ายที่ส่วนท้าย โหนดเก็บขนาด ไม่ว่าชิ้นส่วนจะว่างหรือไม่ก็ตาม และพอยน์เตอร์สองตัวที่ใช้ในรายการที่เชื่อมโยงแบบทวีคูณ (ถัดไปและก่อนหน้า) โครงสร้างส่วนท้ายเพียงแค่จับตัวชี้ไปที่ส่วนหัว (ใช้ในขณะที่ปล่อยชิ้นส่วนที่อยู่ติดกัน) ก้อนที่อยู่ปลายกองเรียกว่าก้อน "ถิ่นทุรกันดาร" เป็นชิ้นที่ใหญ่ที่สุดและขนาดต่ำสุดและสูงสุดถูกกำหนดไว้ใน heap.h การหดตัวและขยายฮีปนั้นง่ายเหมือนกับการปรับขนาดก้อนพื้นที่รกร้างนี้ หน่วยความจำว่างจะถูกจัดเก็บไว้ใน "ถังขยะ" แต่ละถังขยะจริงๆ แล้วเป็นเพียงรายการโหนดที่มีขนาดใกล้เคียงกันที่เชื่อมโยงสองเท่า โครงสร้างฮีปเก็บจำนวนถังขยะที่กำหนดไว้ ( BIN_COUNT ใน heap.h) เพื่อกำหนดถังขยะที่จะวางชิ้น ขนาดของชิ้นจะถูกแมปกับดัชนีถังขยะโดยฟังก์ชัน get_bin_index ฟังก์ชัน Binning ที่สอดคล้องกันนี้จะช่วยให้แน่ใจว่าชิ้นส่วนต่างๆ สามารถเข้าถึงและจัดเก็บตามรูปแบบที่กำหนดได้ ชิ้นต่างๆ จะถูกจัดเรียงในขณะที่ใส่ลงในถังขยะ ดังนั้นการใส่ชิ้นอาหารจึงไม่ใช่ O(1) แต่จะทำให้การค้นหาชิ้นส่วนที่มีขนาดพอดีที่สุดได้ง่ายขึ้นมาก โปรดทราบว่าสามารถกำหนดฟังก์ชัน binning ได้ แต่ผู้ใช้ฮีปนี้รู้สึกว่าเหมาะสม อาจเป็นประโยชน์ในการพิจารณาฟังก์ชันการจัดวางที่ซับซ้อนมากขึ้น เพื่อช่วยดึงชิ้นส่วนออกมาอย่างรวดเร็ว
ฟังก์ชัน heap_alloc ใช้ที่อยู่ของโครงสร้างฮีปเพื่อจัดสรรและขนาด ฟังก์ชันใช้ get_bin_index เพื่อกำหนดว่าชิ้นของขนาดนี้ควรอยู่ที่ใด แน่นอนว่าอาจไม่มีชิ้นของขนาดนี้ หากไม่พบชิ้นส่วนในถังขยะที่เกี่ยวข้อง ถังขยะถัดไปจะถูกตรวจสอบ สิ่งนี้จะดำเนินต่อไปจนกว่าจะพบชิ้นส่วนหรือถึงถังขยะสุดท้าย ซึ่งในกรณีนี้ความทรงจำชิ้นหนึ่งจะถูกพรากไปจากชิ้นส่วนในป่า ถ้าก้อนที่พบมีขนาดใหญ่พอก็จะถูกแบ่งออก เพื่อพิจารณาว่าควรแบ่งชิ้นส่วนหรือไม่ จำนวนเมตาดาต้า (ค่าใช้จ่าย) จะถูกหักออกจากสิ่งที่การจัดสรรปัจจุบันของเราไม่ได้ใช้ หากสิ่งที่เหลืออยู่มากกว่าหรือเท่ากับ MIN_ALLOC_SZ นั่นหมายความว่าเราควรแยกชิ้นส่วนนี้และนำสิ่งของที่เหลือไปใส่ในถังขยะที่ถูกต้อง เมื่อเราพร้อมที่จะคืนชิ้นส่วนที่เราพบแล้ว เราก็นำที่อยู่ของช่อง next แล้วส่งคืน สิ่งนี้เกิดขึ้นเนื่องจากไม่ได้ใช้ฟิลด์ next และ prev ในขณะที่มีการจัดสรรก้อน ดังนั้นผู้ใช้ของก้อนจึงสามารถเขียนข้อมูลลงในฟิลด์เหล่านี้ได้โดยไม่ส่งผลกระทบต่อการทำงานภายในของฮีป
ฟังก์ชัน heap_free รับตัวชี้ที่ส่งคืนโดย heap_alloc มันจะลบออฟเซ็ตที่ถูกต้องเพื่อให้ได้ที่อยู่ของโครงสร้างโหนด แทนที่จะวางชิ้นเนื้อลงในถังขยะที่ถูกต้อง ชิ้นที่อยู่รอบๆ ชิ้นที่จัดไว้ให้จะถูกตรวจสอบ หากชิ้นใดชิ้นหนึ่งเหล่านี้ว่าง เราก็สามารถรวมชิ้นส่วนต่างๆ เข้าด้วยกันเพื่อสร้างชิ้นที่ใหญ่ขึ้นได้ ในการรวบรวมชิ้นส่วนต่างๆ ส่วนท้ายจะใช้เพื่อรับโครงสร้างของโหนดของชิ้นส่วนก่อนหน้าและโครงสร้างของโหนดของชิ้นส่วนถัดไป ตัวอย่างเช่น สมมติว่าเรามีส่วนที่เรียกว่า to_free ในการรับชิ้นส่วนก่อนหน้าชิ้นส่วนนี้ เราจะลบ sizeof(footer_t) เพื่อให้ได้ส่วนท้ายของชิ้นส่วนก่อนหน้า ส่วนท้ายจะถือตัวชี้ไปที่ส่วนหัวของส่วนก่อนหน้า เพื่อให้ได้ชิ้นต่อไป เราเพียงแค่ได้ส่วนท้ายของ to_free แล้วเพิ่ม sizeof(footer_t) เพื่อที่จะได้ชิ้นถัดไป เมื่อทั้งหมดนี้เสร็จสิ้นและคำนวณขนาดใหม่แล้ว ชิ้นส่วนก็จะถูกวางกลับเข้าไปในถังขยะ
หมายเหตุ: เดิมโค้ดนี้ถูกคอมไพล์สำหรับเครื่อง 32 บิต ซึ่งหมายความว่าเมื่อใช้โค้ดนี้ ก็เป็นที่ยอมรับที่จะส่ง int ไปยังพอยน์เตอร์เนื่องจากทั้งสองมีขนาดเท่ากัน บนระบบ 64 บิต คอมไพลเลอร์จะเตือนคุณถึงขนาดที่แตกต่างกัน เพื่อปิดเสียงคำเตือนเหล่านี้ ฉันได้ใช้ uintptr_t เมื่อส่งจาก int ที่ไม่ได้ลงนามไปยังตัวชี้ สิ่งนี้จะทำให้การอ่านง่ายขึ้นเล็กน้อย และการคำนวณแบบแคสต์และพอยน์เตอร์บางส่วนนั้นมีรายละเอียดมาก ดังนั้นโปรดคำนึงถึงสิ่งนั้นเมื่ออ่านโค้ด
