פתרון סורק קבצים מוגבל זיכרון¶
נפריד בין שלושה תקציבים שונים: גודל קלט שאפשר לתאר ב־offset של שישים וארבעה ביט, מספר הבתים שאנחנו ממפים בכל רגע ומספר הבתים שההיסטוגרמה מבקשת מן המקצה. ההפרדה מאפשרת לסרוק קובץ גדול בלי לטעון אותו כולו, אבל אינה מבטיחה תושבות או זמן ריצה קבועים.
התוכנית הבאה מלאה עבור Windows ב־x64 ו־C++20. שמרו אותה בשם mapped_scan.cpp ובנו בסביבת הפיתוח של MSVC:
הקוד אינו כותב לקלט ואינו יוצר אותו:
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <memory_resource>
#include <new>
#include <stdexcept>
#include <system_error>
#include <vector>
[[noreturn]] void win_error(const char* operation) {
const DWORD error = GetLastError();
throw std::system_error(
static_cast<int>(error), std::system_category(), operation);
}
class Handle {
HANDLE value_ = nullptr;
public:
explicit Handle(HANDLE value = nullptr) noexcept : value_(value) {}
~Handle() {
if (value_ && value_ != INVALID_HANDLE_VALUE) CloseHandle(value_);
}
Handle(const Handle&) = delete;
Handle& operator=(const Handle&) = delete;
HANDLE get() const noexcept { return value_; }
};
class View {
const std::byte* data_ = nullptr;
public:
View(HANDLE mapping, std::uint64_t offset, std::size_t count) {
data_ = static_cast<const std::byte*>(MapViewOfFile(
mapping, FILE_MAP_READ,
static_cast<DWORD>(offset >> 32),
static_cast<DWORD>(offset & 0xffffffffULL), count));
if (!data_) win_error("MapViewOfFile");
}
~View() { if (data_) UnmapViewOfFile(data_); }
View(const View&) = delete;
View& operator=(const View&) = delete;
const std::byte* data() const noexcept { return data_; }
};
class Budget final : public std::pmr::memory_resource {
std::size_t limit_, live_ = 0, peak_ = 0;
std::pmr::memory_resource* upstream_ =
std::pmr::new_delete_resource();
void* do_allocate(std::size_t bytes, std::size_t alignment) override {
if (bytes > limit_ - live_) throw std::bad_alloc{};
void* result = upstream_->allocate(bytes, alignment);
live_ += bytes;
peak_ = std::max(peak_, live_);
return result;
}
void do_deallocate(void* p, std::size_t bytes,
std::size_t alignment) override {
upstream_->deallocate(p, bytes, alignment);
live_ -= bytes;
}
bool do_is_equal(
const std::pmr::memory_resource& other) const noexcept override {
return this == &other;
}
public:
explicit Budget(std::size_t limit) : limit_(limit) {}
std::size_t peak() const noexcept { return peak_; }
std::size_t live() const noexcept { return live_; }
};
int wmain(int argc, wchar_t** argv) {
if (argc != 2) {
std::wcerr << L"usage: mapped_scan.exe file\n";
return 2;
}
Budget budget(8192);
try {
std::pmr::vector<std::uint64_t> counts(256, 0, &budget);
Handle file(CreateFileW(argv[1], GENERIC_READ, FILE_SHARE_READ,
nullptr, OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL, nullptr));
if (file.get() == INVALID_HANDLE_VALUE) win_error("CreateFileW");
LARGE_INTEGER signed_size{};
if (!GetFileSizeEx(file.get(), &signed_size))
win_error("GetFileSizeEx");
if (signed_size.QuadPart < 0)
throw std::runtime_error("negative file size");
const auto size = static_cast<std::uint64_t>(signed_size.QuadPart);
std::size_t largest_view = 0;
if (size != 0) {
Handle mapping(CreateFileMappingW(
file.get(), nullptr, PAGE_READONLY, 0, 0, nullptr));
if (!mapping.get()) win_error("CreateFileMappingW");
SYSTEM_INFO info{};
GetSystemInfo(&info);
const std::uint64_t granularity = info.dwAllocationGranularity;
if (granularity == 0)
throw std::runtime_error("invalid allocation granularity");
constexpr std::uint64_t chunk = 1024 * 1024;
std::uint64_t cursor = 0;
while (cursor < size) {
const auto logical_count = std::min(chunk, size - cursor);
const auto aligned = cursor - cursor % granularity;
const auto delta = cursor - aligned;
const auto max_size = std::numeric_limits<std::size_t>::max();
if (delta > max_size ||
logical_count > max_size - delta)
throw std::length_error("mapping window too large");
const auto view_count =
static_cast<std::size_t>(delta + logical_count);
largest_view = std::max(largest_view, view_count);
{
View view(mapping.get(), aligned, view_count);
const auto* data =
view.data() + static_cast<std::size_t>(delta);
for (std::size_t i = 0;
i < static_cast<std::size_t>(logical_count); ++i) {
++counts[std::to_integer<unsigned char>(data[i])];
}
}
cursor += logical_count;
}
}
std::uint64_t total = 0;
for (std::size_t byte = 0; byte < counts.size(); ++byte) {
total += counts[byte];
if (counts[byte] != 0)
std::cout << byte << ": " << counts[byte] << '\n';
}
if (total != size) throw std::runtime_error("count invariant failed");
std::cout << "bytes=" << total
<< " largest-view=" << largest_view
<< " requested-peak=" << budget.peak() << '\n';
} catch (const std::exception& error) {
std::cerr << error.what() << '\n';
return 1;
}
if (budget.live() != 0) {
std::cerr << "resource lifetime invariant failed\n";
return 1;
}
return 0;
}
הוכחת גבולות החלון¶
המשתנה cursor מתאר את הבית הלוגי הבא שעוד לא נספר. בתחילת כל איטרציה הוא קטן מגודל הקובץ. לכן החיסור size - cursor בטוח, וגודל העבודה נקבע כמינימום בין היתרה לבין גודל החלון. בסוף האיטרציה ההתקדמות אינה עוברת את סוף הקובץ.
ה־offset של מיפוי חייב להתאים ל־allocation granularity. אנחנו מעגלים כלפי מטה ומחשבים את delta, שהוא המרחק מן הבסיס הממופה אל הבית הראשון שרוצים לקרוא. מספר הבתים של המיפוי כולל גם את הקידומת הזו. הבדיקה לפני החיבור מונעת overflow בזמן ההמרה ל־size_t. הכתובת שעליה רצים אינה בסיס המיפוי, אבל ה־View שומר את הבסיס המקורי לצורך השחרור.
התחום הפנימי סביב View מבטיח שהחלון נסגר לפני שנוצר הבא. גם אם מיפוי חדש נכשל, אין רשימת views ישנים שממשיכה לצמוח. הסכום של המונים אינו יכול לעבור את גודל הקובץ במסלול התקין, וגודל הקובץ המקובל כאן קטן מן הגבול החיובי של מספר חתום בן שישים וארבעה ביט.
קובץ ריק וחיי משאבים¶
הקוד מדלג על יצירת mapping כאשר הגודל אפס. אין להשתמש ב־MapViewOfFile עם אורך אפס כדי לייצג חלון ריק: משמעות האורך הזה היא מיפוי עד סוף אובייקט המיפוי. תוצאה ריקה עדיין מחזירה היסטוגרמה תקינה וסכום אפס.
סדר האובייקטים גורם להיסטוגרמה להיהרס לפני המשאב. המיפוי נסגר אחרי כל ה־views שלו, והקובץ נסגר אחרי יציאתנו מתחום העבודה. כשל constructor של View אינו משאיר view שנוצר בהצלחה, משום שהכשל מזוהה לפי ערך ההחזרה. במעטפת מלאה אפשר להוסיף רישום לכשל נדיר ב־UnmapViewOfFile או CloseHandle; destructor אינו מקום לזרוק חריגה נוספת בזמן unwinding.
יציבות הקלט וכשל גישה¶
פתיחת הקובץ עם FILE_SHARE_READ מאפשרת קוראים נוספים, אבל אינה מסכימה לפתיחות כתיבה או מחיקה רגילות שאינן תואמות את השיתוף. בקשת פתיחה מתנגשת נכשלת במקום ליצור snapshot מדומה. המדיניות מיועדת לקובץ מקומי רגיל; היא אינה הבטחה כללית נגד כל רכיב מערכת, שינוי חיצוני לאחסון או תקלה באמצעי האחסון.
גם אחרי ש־MapViewOfFile הצליחה, גישה לדף יכולה להיכשל ב־in-page error. תחת אפשרות הבנייה /EHsc, ה־catch של std::exception אינו טיפול כללי בחריגות מערכת כאלה. הרחבת ייצור סבירה מריצה את הסריקה בתהליך עובד, שומרת את התוצאה זמנית ומפרסמת אותה רק אחרי שהעובד הסתיים בהצלחה והסכום נבדק. ההורה יכול לדחות תוצאה חלקית ולשמור dump של העובד, בלי להמשיך מתוך לולאה שמצבה אינו ידוע.
בדיקות שניתן לשחזר¶
לקובץ שמכיל פעם אחת כל ערך בין אפס למאתיים חמישים וחמש צריך להיות מונה אחד לכל ערך וסכום מאתיים חמישים ושש. לקובץ שמכיל מיליון וחמישה בתים זהים צריך להיות מונה יחיד בגודל הזה, בלי תלות בגבול החלון. עבור קובץ ריק הסכום אפס והגודל המרבי של view אפס.
בדיקת התקציב משנה את הערך 8192 לערך 1024. במקרה הזה ההיסטוגרמה לבדה דורשת יותר מן המותר, והכלי נכשל לפני פתיחת הקובץ. בדיקה נוספת משנה את גודל החלון, אך משאירה את הקלט זהה ומשווה את כל המונים. ההשוואה היא לתוצאה חיצונית פשוטה, ולא רק לאותו אלגוריתם עם שם משתנה אחר.
הקוד מוצג כפתרון לבנייה ולהרצה במעבדה; אין כאן טענה שנמדדה תושבות או שנבדק כשל אחסון בפועל. תיעוד מיפוי חלון קובץ מגדיר את חוזי ה־offset והגישה שעליהם נשענת ההוכחה.