ในช่วงกลางทศวรรษ 1990 เมื่อราคา RAM พุ่งสูงขึ้นและนักพัฒนาส่วนใหญ่ต้องทำงานกับหน่วยความจำที่จำกัดอย่างมาก ความหงุดหงิดของผู้ร่วมพัฒนา FreeBSD คนหนึ่งกับระบบ 4MB ของเขาได้นำไปสู่การคิดใหม่อย่างสมบูรณ์เกี่ยวกับวิธีที่ระบบปฏิบัติการจัดการการจัดสรรหน่วยความจำ Poul-Henning Kamp ซึ่งรู้จักในนาม PHK สังเกตเห็นว่าระบบของเขามีการเข้าถึงดิสก์อย่างหนักทุกครั้งที่คอมไพเลอร์ GCC ทำงานเสร็จ ซึ่งเป็นปรากฏการณ์ที่ไม่ควรเกิดขึ้นเมื่อโปรแกรมเพียงแค่กำลังปลดปล่อยหน่วยความจำก่อนปิดตัวลง
ข้อมูลจำเพาะของระบบ PHK (1994-1995)
- RAM: 4MB (มีข้อจำกัดอย่างมากสำหรับยุคนั้น)
- ภาระงานหลัก: การคอมไพล์ GCC ในฐานะ release engineer ของ FreeBSD
- ปัญหา: การใช้ paging มากเกินไปในระหว่างการสิ้นสุดโปรแกรม
- ไทม์ไลน์การแก้ไข: พัฒนาในช่วง 1994-1995 และ commit ในเดือนกันยายน 1995
ปัญหาหลัก: Virtual Memory พบกับโค้ดโบราณ
ปัญหาอยู่ที่การใช้งาน malloc ที่ FreeBSD สืบทอดมาจาก BSD ซึ่งอิงตามแนวทางคลาสสิกที่อธิบายไว้ใน The C Programming Language โดย Kernighan และ Ritchie วิธีการที่สง่างามนี้ทำงานได้อย่างสมบูรณ์แบบบนระบบ swapping รุ่นเก่าอย่าง PDP-11 ซึ่งกระบวนการทั้งหมดจะอยู่ในหน่วยความจำอย่างสมบูรณ์หรือไม่ทำงานเลย อย่างไรก็ตาม ระบบ virtual memory ได้เปลี่ยนกฎเกมไปโดยสิ้นเชิง
malloc เดิมเก็บบล็อกหน่วยความจำที่ว่างไว้ใน linked list โดยมี metadata เก็บไว้ที่จุดเริ่มต้นของแต่ละชิ้นที่ว่าง เมื่อปลดปล่อยหน่วยความจำ ระบบต้องเดินผ่านรายการทั้งหมดนี้ ซึ่งอาจต้องอ่านคำแรกๆ ของทุกบล็อกหน่วยความจำที่ไม่ได้ใช้ สิ่งนี้ทำให้เคอร์เนลต้อง page หน่วยความจำที่นอนอยู่บนดิสก์โดยไม่ได้ใช้งาน เพียงเพื่อทำเครื่องหมายว่าว่าง ซึ่งสร้างเอฟเฟกต์ death rattle ที่ PHK สังเกตเห็น
แฮ็กที่ชาญฉลาดซึ่งเกือบจะขจัดปัญหาได้
วิธีแก้ปัญหาแรกของ PHK นั้นโหดร้ายแต่มีประสิทธิภาพ แทนที่จะเก็บ metadata ภายในชิ้นหน่วยความจำที่ว่าง เขาจะตัดโครงสร้างขนาดเล็กจากด้านหน้าของชิ้นแรกที่ว่างใน free list และใช้สำหรับการจัดการบัญชี ซึ่งหมายความว่าหน่วยความจำที่ว่างจริงๆ ไม่จำเป็นต้องถูกสัมผัสอีกเลย เว้นแต่จะถูกจัดสรรใหม่
การอภิปรายในชุมชนเผยให้เห็นความชื่นชมต่อแนวทางที่นวัตกรรมของ PHK โดยเฉพาะการใช้ symbolic links เป็นไฟล์กำหนดค่า แทนที่จะแยกวิเคราะห์ไฟล์กำหนดค่าแบบดั้งเดิม (ซึ่งจะต้องใช้ malloc ที่ทำงานอยู่แล้ว) PHK ใช้ symbolic links เป็นไฟล์ข้อความขนาดเล็กเพื่อควบคุมพฤติกรรม malloc ในขณะรันไทม์
คุณสมบัติหลักของ phkmalloc
- การแยก metadata: เก็บ metadata ของการจัดสรรหน่วยความจำแยกออกจากส่วนของหน่วยความจำจริง
- รูปแบบ Binary buddy: ใช้สำหรับการจัดสรรที่มีขนาดเล็กกว่าหน้าเพจ
- การกำหนดค่าขณะรันไทม์: ผ่าน symbolic links (เช่น /etc/malloc.conf -> "AJ")
- การเสริมความปลอดภัย: ต้านทานการโจมตีแบบ buffer overflow ทั่วไป
- ความสามารถในการดีบัก: สามารถตรวจจับ double-free, buffer overruns และการใช้งาน malloc ที่ผิดพลาดอื่นๆ
 |
|---|
| กราฟแสดงการปรับปรุงประสิทธิภาพที่เกี่ยวข้องกับเทคนิคการจัดสรรหน่วยความจำของ PHK โดยแสดงให้เห็นผลกระทบของแนวทางที่เป็นนวัตกรรมของเขา |
ประโยชน์ด้านความปลอดภัยและข้อจำกัดของ Multi-Core
ด้วยการแยก metadata ออกจากชิ้นหน่วยความจำ phkmalloc กลายเป็นตัวที่ต้านทานการโจมตี buffer overflow ได้อย่างน่าประหลาดใจ ชุมชนสังเกตว่าสิ่งนี้นำไปสู่คำแนะนำด้านความปลอดภัยจำนวนมากที่กล่าวถึงว่า Linux, Solaris... มีช่องโหว่ แต่ FreeBSD ไม่มี แม้ว่า PHK จะเน้นว่า phkmalloc ยังสามารถถูกโจมตีได้ แต่มันให้เวลาผู้ดูแลระบบหลายเดือนแทนที่จะเป็นหลายชั่วโมงในการแก้ไขช่องโหว่
อย่างไรก็ตาม เมื่อระบบ multi-threading และ multi-CPU กลายเป็นเรื่องธรรมดา โครงสร้างข้อมูลที่รวมเข้าด้วยกันอย่างแน่นหนาของ phkmalloc ต้องการ mutex ขนาดใหญ่ตัวเดียวรอบการดำเนินการทั้งหมด สิ่งนี้ทำงานได้ดีสำหรับ CPU หนึ่งหรือสองตัว แต่กลายเป็นคอขวดด้านประสิทธิภาพเมื่อมี core สี่ตัวขึ้นไป
ผลการเปรียบเทียบประสิทธิภาพ
- ประสิทธิภาพ: เทียบเท่ากับ GNU malloc เมื่อมี RAM เพียงพอ
- ประสิทธิภาพการใช้หน่วยความจำ: ประสิทธิภาพยอดเยี่ยมเมื่อมี RAM จำกัด (8MB หรือต่ำกว่า)
- ข้อจำกัดของระบบหลายคอร์: ต้องใช้ mutex เดียว ทำให้เกิดคอขวดเมื่อใช้ 4 คอร์ขึ้นไป
- ตัวสืบทอด: ในที่สุดถูกแทนที่ด้วย jemalloc เพื่อรองรับการทำงานแบบหลายเธรดที่ดีกว่า
ความเกี่ยวข้องในปัจจุบันและความท้าทายของ NUMA
การอภิปรายในปัจจุบันสัมผัสถึงว่าระบบ NUMA ปัจจุบันที่มี core หลายร้อยตัวควรได้รับการออกแบบใหม่อย่างสมบูรณ์คล้ายกับการปฏิวัติของ PHK หรือไม่ allocator สมัยใหม่อย่าง jemalloc แก้ไขปัญหา multi-core ด้วย per-CPU arenas แม้ว่าสิ่งนี้อาจสร้างปัญหาใหม่เมื่อ thread ถูกจอดหรือหยุดการจัดสรรหน่วยความจำ หน่วยความจำที่จัดสรรของพวกมันอาจไม่เคยถูกปล่อยกลับสู่ระบบ
เรื่องราวของ phkmalloc แสดงให้เห็นว่าข้อจำกัดของฮาร์ดแวร์ขับเคลื่อนนวัตกรรมซอฟต์แวร์ สิ่งที่เริ่มต้นจากความหงุดหงิดของนักพัฒนาคนหนึ่งกับระบบ 4MB กลายเป็นการปรับปรุงพื้นฐานที่มีอิทธิพลต่อการจัดการหน่วยความจำในระบบปฏิบัติการหลายตัวและช่วยสร้างแนวปฏิบัติด้านความปลอดภัยที่ดีขึ้นซึ่งยังคงเกี่ยวข้องในปัจจุบัน
อ้างอิง: phkmalloc