การเก็บขยะ PDF ใน Delphi ด้วย Mark and Sweep

การลบหน้าออกจาก PDF ไม่ได้ลบฟอนต์ ภาพ หรือ content stream ที่หน้านั้นใช้อยู่ไปด้วย losLab PDF Library แก้ปัญหานี้ด้วย mark-sweep collector ที่ไล่ตาม object graph จาก trailer roots ไปข้างหน้า แล้วลบ indirect object ทุกตัวที่ไม่มีอะไรอ้างถึงอีกต่อไป กระบวนการนี้ทำงานตอน full save เท่านั้น ปิดไว้เป็นค่าเริ่มต้น และคืนค่าจำนวนอ็อบเจกต์ที่ถูกกำจัดออกไป

ทำไมการลบหน้า PDF ถึงไม่ทำให้ไฟล์เล็กลง

เพราะการลบหน้าเป็นการแก้ไข reference ไม่ใช่การจัดการ storage DeletePages(StartPage, PageCount) ตัดการเชื่อมโยงของ page object ออกจาก page tree และซ่อมแซม outline entry ที่เคยชี้มาที่มัน สิ่งที่มันทำไม่ได้คือตัดสินว่าฟอนต์โปรแกรม content stream และ image XObject ที่หน้าเหล่านั้นเคยใช้ตอนนี้ตายแล้วหรือยัง เพราะในขณะที่ลบนั้นไม่มีอะไรในไฟล์บันทึกไว้ว่ายังมีใครอ้างถึงมันอยู่หรือไม่ อ็อบเจกต์เหล่านี้จึงยังคงอยู่ใน document object list และการ full save ก็เขียนมันกลับออกไปทุกตัว ผลลัพธ์คือคำร้องเรียนที่พบบ่อยที่สุดในสาย support: ลูกค้าลบหน้าไปเก้าสิบเปอร์เซ็นต์ เซฟไฟล์ แล้วไฟล์เล็กลงแค่สองเปอร์เซ็นต์ ที่แย่กว่านั้นคือปัญหาการรั่วไหลนี้สะสมทบต้น โหลด ลบ เซฟ โหลดใหม่ ลบอีก เซฟอีก ไฟล์จะโตขึ้นเรื่อย ๆ ในขณะที่จำนวนหน้าลดลง นี่เป็นปัญหาคนละแบบกับที่ font subsetting และ image downsampling แก้ไข ซึ่งทำให้อ็อบเจกต์ที่ยังมีชีวิตอยู่มีขนาดเล็กลง แต่ในกรณีนี้อ็อบเจกต์ไม่ได้ใหญ่เกินไป มันแค่ไม่ได้เป็นส่วนหนึ่งของเอกสารอีกต่อไปแล้ว

Root set คือ trailer ไม่ใช่ page tree

Object graph ของ PDF ไม่มีฟิลด์ reverse-reference รูปแบบไฟล์ไม่ได้กำหนด reference count หรือ back-pointer list ใด ๆ ไว้ และคีย์ /Parent ที่มีอยู่จริงก็เป็นของโครงสร้างเฉพาะอย่าง page tree ไม่ใช่ของ object graph ทั้งหมด ไม่มีสิ่งใดใน indirect object บอกได้ว่าใครอ้างถึงมันบ้าง ดังนั้นคำถามที่ว่า "ยังมีใครใช้อ็อบเจกต์ 47 อยู่ไหม" จึงมีคำตอบเดียวคือไล่ไปข้างหน้าจาก root ที่รู้จักแล้วดูว่าจะไปถึงมันหรือไม่ นี่คือเหตุผลที่ collector ใน losLab PDF Library เป็น mark-sweep collector ไม่ใช่ refcount scheme

Root มาจาก file trailer (ISO 32000-1 §7.5.5) มีสามคีย์ที่บรรจุ root ไว้คือ /Root ซึ่งเป็น document catalog ตาม §7.7.2 ที่ page tree, names, outlines, AcroForm และ metadata ทั้งหมดห้อยอยู่ด้วย /Info ซึ่งเป็น document information dictionary และ /Encrypt ซึ่งเป็น encryption dictionary ส่วนคีย์ trailer อีกสองตัวที่เหลือเป็นตัวหลอก /ID เป็น array ของ byte string สองตัว และ /Prev เป็น integer byte offset ไปยัง cross-reference section ก่อนหน้า ทั้งสองไม่ใช่ indirect reference จึงไม่นับเป็น root losLab PDF Library จึงเข้าคิว (enqueue) ทั้ง trailer dictionary แทนที่จะเลือกเฉพาะสามคีย์ที่ตั้งชื่อไว้ ซึ่งไม่มีต้นทุนเพิ่มเติมและยังทำให้ trailer extension เฉพาะของแต่ละไฟล์ยังคงอยู่ต่อไปได้

การไล่ตามนี้เป็นแบบวนซ้ำ (iterative) ไม่ใช่ recursive เมื่อการไล่ตามพบ indirect reference มันจะบันทึกแค่ object number กับ generation ทำเครื่องหมายที่ slot ที่ตรงกัน แล้วผลักเข้าไปใน FIFO queue แทนที่จะ dereference ทันที ซึ่งทำให้ page tree ที่ลึกมากและ outline chain ที่ยาวมากไม่ไปกินพื้นที่ call stack และป้องกันไม่ให้อ็อบเจกต์เดียวกันถูก decode ซ้ำสอง dictionary, array และ stream dictionary ที่เป็น direct จะอยู่ในอีก queue หนึ่งที่มี visited set คอยป้องกัน เพราะเอกสารจริงมี cycle แท้ ๆ อยู่ เช่น /Parent ของหน้าหนึ่งชี้กลับไปที่ node ของ page tree ตัวเอง และ outline item ก็เชื่อมกันผ่าน /Prev กับ /Next ทั้งสองทิศทาง หมายเลข generation เป็นส่วนหนึ่งของการจับคู่ ไม่ใช่แค่ตกแต่ง reference จะ resolve ได้ก็ต่อเมื่อ object number กับ generation ตรงกันทั้งคู่เท่านั้น ส่วน reference ที่ชี้ไปยังหมายเลขที่มีอยู่จริงแต่คนละ generation จะถูกถือว่าเป็น null object ตามที่สเปกกำหนด ไม่มีทางถูกนับเป็น edge ที่มีชีวิตได้เลย

จะเปิดใช้ garbage collection ตอนเซฟได้อย่างไร

Garbage collection เป็นแบบ opt-in และอยู่ใน save options record ค่าเริ่มต้นคือ False เพราะ collector เป็น pass ที่ทำลายล้างต่อ object graph และไม่มีไลบรารีใดควรลบอ็อบเจกต์ที่ผู้เรียกไม่เคยขอให้มันตรวจสอบโดยเงียบ ๆ

var
  Pdf: TPDFlib;
  Opt: TPDFlibSaveOptions;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('report-500pages.pdf', '') <> 1 then
      Exit;
    Pdf.DeletePages(11, 490);          // keep the first ten pages

    FillChar(Opt, SizeOf(Opt), 0);
    Opt.CompressContent := True;
    Opt.CompressFonts := True;
    Opt.OptimizeContentStreams := True;
    Opt.PackObjectStreams := True;
    Opt.GarbageCollect := True;        // drop everything the pages left behind
    Pdf.SaveToFileOptions('report-10pages.pdf', Opt);
  finally
    Pdf.Free;
  end;
end;

มีจุดเรียกใช้อีกสองแบบที่ไปถึง collector ตัวเดียวกัน SetGarbageCollect(1) ตั้งค่า flag ไว้ที่เอกสารที่เลือกอยู่ เพื่อให้ SaveToFile แบบปกติทำตามนั้น ส่วน GarbageCollectObjects จะรัน pass นี้ทันทีและคืนค่าจำนวน indirect object ที่ถูกทิ้งขว้างและถูกลบไป รูปแบบหลังนี้เหมาะกับตอนที่ต้องการตัวเลขไว้ log หรือ assert และควรตรวจสอบให้ดี เพราะค่าที่คืนเป็นลบไม่ได้หมายถึงจำนวนนับ

var
  Removed: Integer;
begin
  Pdf.DeletePages(11, 490);
  Removed := Pdf.GarbageCollectObjects;
  if Removed < 0 then
    // The graph could not be fully decoded. Nothing was swept and the
    // document is unchanged; save it without GC or reject the input.
    LogWarning('object graph incomplete, GC skipped')
  else
    LogInfo(Format('reclaimed %d orphaned objects', [Removed]));
end;

เส้นทางความล้มเหลวนี้สำคัญกว่าที่เห็น อ็อบเจกต์ถูก decode แบบ lazy และอ็อบเจกต์ที่ไม่เคย decode มาก่อนจะไม่เปิดเผย reference ใด ๆ เลย ถ้า collector ปฏิบัติต่ออ็อบเจกต์ที่ decode ไม่ได้เหมือนเป็น node ว่างเปล่า มันจะกวาดทิ้งทุกอย่างที่เข้าถึงได้ผ่านมันไปหมด ดังนั้น การไล่ตามจะบังคับ decode ทุกครั้งที่แตะอ็อบเจกต์แต่ละตัว และหาก decode ผิดพลาดแม้เพียงครั้งเดียวก็จะยกเลิก pass ทั้งหมดพร้อมคืนค่าลบ และทิ้งเอกสารไว้เหมือนเดิมทุก byte การกวาดล้าง graph ที่คุณเข้าใจเพียงบางส่วนคือวิธีที่ collector จะเปลี่ยนไฟล์เสียหายให้กลายเป็นไฟล์พังไปเลย

อะไรที่ทำให้ PDF collector แบบไร้เดียงสาพัง

มีสองรายละเอียดที่ล้มเหลวแบบเงียบ ๆ ไม่ใช่แบบดังเอ๊ะอะ อย่างแรกคือ object stream ตั้งแต่ PDF 1.5 เป็นต้นมา อ็อบเจกต์ที่ไม่ใช่ stream สามารถถูกบีบอัดอยู่ภายใน container ชนิด /ObjStm ได้ (§7.5.7) และ cross-reference entry ของมันก็เป็น type 2 entry ที่ระบุชื่อ container บวก index ภายในนั้น อ็อบเจกต์ที่ถูกบีบอัดจึงเข้าถึงได้ผ่าน container ของมันเท่านั้น ถ้า mark สมาชิกไว้แต่ sweep container ทิ้งเพราะไม่มีใครอ้างถึงมันในฐานะ document object คุณก็จะได้ไฟล์ที่ xref ชี้เข้าไปยังอ็อบเจกต์ที่ไม่มีอยู่แล้ว container เป็น structural storage ไม่ใช่ document data จึงไม่มีวันปรากฏเป็น edge ใน object graph ที่กำลังไล่ตามอยู่ losLab PDF Library จัดการเรื่องนี้ด้วยการแยกสมาชิกที่บีบอัดทุกตัวที่ยังรอดออกจาก container ต้นทางก่อนที่ container จะหายไป จากนั้นตอนเซฟจะบรรจุสมาชิกที่รอดเหล่านั้นเข้า object stream ใหม่อีกครั้ง รายละเอียดที่สองคือสิ่งที่ stream object อ้างถึงจริง ๆ ไบต์ข้อมูลไม่ได้เป็นส่วนหนึ่งของ graph content stream ที่วาดข้อความด้วย /F1 12 Tf อ้างถึงฟอนต์ด้วยชื่อ resource และชื่อนั้นถูก resolve ผ่าน page /Resources dictionary ดังนั้น reachability edge จึงวิ่งจาก page → /Resources → /Font → font object ไม่เคยผ่าน stream payload เลย reference เดียวที่ stream มีส่วนร่วมมาจาก dictionary ของมัน ซึ่ง /Length, /Filter และ /DecodeParms ล้วนได้รับอนุญาตให้เป็น indirect ได้ collector ที่ parse stream bytes เพื่อหา reference กำลังทำงานที่แพงโดยเปล่าประโยชน์ ส่วน collector ที่ข้าม stream dictionary ไปเลยจะทำให้ length object หายไปและไฟล์เสียหาย

เกิดอะไรขึ้นกับ object number ที่ถูกปล่อยว่าง

มันกลายเป็น free entry และจะไม่ถูกนำกลับมาใช้ใหม่ในการเซฟรอบเดียวกัน การ sweep จะไล่ object list จากมากไปน้อยเพื่อให้ index ยังคงเสถียรระหว่างการลบ สร้าง lookup index ใหม่แค่ครั้งเดียวตอนจบแทนที่จะทำหลังลบทุกครั้ง และสำหรับอ็อบเจกต์ที่ถูกลบแต่ละตัวจะบันทึกหมายเลขไว้ใน free list พร้อมเพิ่ม generation ขึ้นอีกหนึ่ง ตรงตามที่ §7.5.4 กำหนดไว้สำหรับ entry ที่อาจถูกนำกลับมาใช้ใหม่ในภายหลัง ส่วน generation ที่ถึง 65535 แล้วจะค้างอยู่ที่นั่น หมายความว่าหมายเลขนั้นถูกปลดระวางถาวร object number จงใจไม่ถูกบีบอัดให้ต่อเนื่องกัน หลังการ collection ไฟล์ยังคงมีช่องว่างอยู่ เช่น อ็อบเจกต์ 12 อาจว่างในขณะที่ 13 กับ 14 ยังใช้งานอยู่ และ trailer /Size ก็ยังคงรายงานหมายเลขสูงสุดบวกหนึ่ง ไม่ใช่จำนวนที่รอดจริง นี่คือเรื่องถูกต้องและปกติ การเรียงหมายเลขใหม่จะประหยัด byte ใน cross-reference table ได้แค่หยิบมือ แต่ต้องเขียน reference ทุกตัวในเอกสารใหม่ทั้งหมด ซึ่งเป็นการเปลี่ยนแปลงที่จะทำให้สิ่งใดก็ตามที่ถือ object number จากภายนอกใช้ไม่ได้อย่างเงียบ ๆ ขนาดไฟล์ที่ได้กลับมาจึงมาจากตัวเนื้อหาอ็อบเจกต์ ไม่ใช่จาก xref table

เมื่อใดที่ห้ามรัน collector

ห้ามรันบน incremental update เด็ดขาด collector ถูกล็อกให้ทำงานเฉพาะตอน full save และ flag ก็จะไม่ถูกอ่านเลยเมื่อเอกสารกำลังถูก append เข้าไป และการล็อกนี้ไม่ใช่ข้อจำกัดที่ต้องหาทางหลบเลี่ยง incremental update (§7.5.6) จะไม่แตะต้อง byte เดิมเลยและ append cross-reference section ใหม่ที่เชื่อมกับอันก่อนหน้าผ่าน /Prev ทุก revision ก่อนหน้ายังคงชี้ไปที่อ็อบเจกต์ที่มันเคยชี้อยู่เสมอ ดังนั้นอ็อบเจกต์ที่เข้าถึงไม่ได้ใน revision ปัจจุบันอาจยังเข้าถึงได้อย่างสมบูรณ์ใน revision เก่ากว่า การลบมันทิ้งจะทำลาย revision ทุกอันยกเว้นอันล่าสุด กลไกเบื้องหลังเรื่องนี้อธิบายไว้ในบทความเรื่อง incremental update และ append-mode save เหตุผลเดียวกันนี้ก็ห้ามใช้ garbage collection บนเอกสารที่เซ็นชื่อไว้แล้วด้วย เพราะการเขียนใหม่ทั้งหมดที่ทำให้ collection เป็นไปได้นั้นเองที่จะทำให้ลายเซ็นเป็นโมฆะ

ควรทำความเข้าใจให้ชัดด้วยว่า collection ไม่ใช่อะไร มันไม่ใช่ sanitizer collector ลบเฉพาะอ็อบเจกต์ที่ไม่มีอะไรอ้างถึง มันไม่มีความเห็นว่าเนื้อหาข้างในอ่อนไหวหรือไม่ และอ็อบเจกต์ที่ยังถูกอ้างถึงอยู่ก็ยังคงเป็นแบบเดิมทุกอย่าง ถ้าเป้าหมายคือทำให้ข้อมูลกู้คืนไม่ได้แทนที่จะทำให้ไฟล์เล็กลง object graph ก็เป็น layer ที่ผิด และ การทำ redaction ระดับ instruction และการ sanitize เอกสาร ต่างหากที่ถูกต้อง ทั้งสองอย่างประกอบกันได้ดีตามลำดับนี้คือ redact และ sanitise ก่อน แล้วค่อย collect เพื่อให้อ็อบเจกต์ที่ redaction ตัดขาดออกไปแล้วออกจากไฟล์จริง ๆ การจับคู่แบบเดียวกันนี้ก็มีอยู่ใน resource purge API ด้วย ซึ่งถ้าส่ง garbage-collect option เข้าไป การ purge จะรัน collection ต่อท้ายและรายงานอ็อบเจกต์กำพร้าที่มันลบไว้ใน OrphanObjectsRemoved

อีกนิสัยหนึ่งที่ควรฝึกไว้คือ log ค่าที่คืนจาก GarbageCollectObjects ไว้ใน batch job ที่ทำการลบหน้าของคุณ แล้วเฝ้าดูมันตลอดสองสามสัปดาห์กับเอกสารจริง ค่าศูนย์บนไฟล์ที่คุณเพิ่งตัดออกไปครึ่งหนึ่งหมายความว่ามีบางอย่าง upstream ยังถือ reference ที่คุณไม่คาดคิดอยู่ ซึ่งมักเป็น name tree entry, outline destination หรือ AcroForm field ที่รอดมาจากหน้าที่มันเคยติดอยู่ collector คือ reachability debugger ที่ถูกที่สุดที่คุณจะมีวันได้ใช้ เพราะมันตอบคำถามที่ตัวรูปแบบ PDF เองปฏิเสธที่จะตอบ

Garbage collector, save-options record และ resource purge API ที่อธิบายไว้ที่นี่เป็นส่วนหนึ่งของ losLab PDF Library สำหรับ Delphi และ C++Builder ซึ่งหน้าผลิตภัณฑ์มีเอกสารอ้างอิงของ save-pipeline แบบเต็ม รวมถึงปฏิสัมพันธ์ระหว่าง collection, object-stream packing และ linearization