פתרון פרויקט ספריית רשומות בינאריות

הגבול המרכזי בפרויקט הוא בין בדיקת קלט לבין שינוי המצב הקיים. אין סיבה למחוק את הרשומות הישנות לפני שהצלחנו לבנות את החדשות. לכן משתמשים במכולה מועמדת עם אותו משאב, ומחליפים אותה במצב הקיים רק אחרי הצלחה מלאה.

התוכנית הבאה מממשת את הליבה ואת בדיקות הכשל. שומרים אותה בשם records.cpp ובונים ללא NDEBUG. הבדיקות משתמשות בפונקציה שאינה נעלמת ב־release, כך שגם גרסת בדיקה אופטימלית מפעילה אותן.

#include <array>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <memory_resource>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <vector>

void require(bool condition) {
    if (!condition) std::abort();
}

template<std::unsigned_integral T>
requires (!std::same_as<T, bool>)
T read_le(std::span<const std::byte> bytes, std::size_t offset) {
    if (offset > bytes.size() || sizeof(T) > bytes.size() - offset)
        throw std::runtime_error("truncated integer");
    T value = 0;
    for (std::size_t i = 0; i < sizeof(T); ++i) {
        auto part = static_cast<T>(
            std::to_integer<unsigned char>(bytes[offset + i]));
        value = static_cast<T>(value | static_cast<T>(part << (i * 8)));
    }
    return value;
}

class BudgetResource final : public std::pmr::memory_resource {
public:
    std::size_t remaining = std::numeric_limits<std::size_t>::max();
    std::size_t live_blocks = 0;
    std::size_t live_bytes = 0;
    std::size_t peak_bytes = 0;
private:
    void* do_allocate(std::size_t size, std::size_t alignment) override {
        if (remaining == 0) throw std::bad_alloc();
        void* result =
            std::pmr::new_delete_resource()->allocate(size, alignment);
        --remaining;
        ++live_blocks;
        live_bytes += size;
        if (live_bytes > peak_bytes) peak_bytes = live_bytes;
        return result;
    }
    void do_deallocate(void* pointer, std::size_t size,
                       std::size_t alignment) override {
        require(live_blocks != 0 && live_bytes >= size);
        --live_blocks;
        live_bytes -= size;
        std::pmr::new_delete_resource()->deallocate(pointer, size, alignment);
    }
    bool do_is_equal(const std::pmr::memory_resource& other)
        const noexcept override {
        return this == &other;
    }
};

class RecordStore {
    std::pmr::vector<std::uint32_t> values_;
    static std::pmr::memory_resource* checked(
        std::pmr::memory_resource* resource) {
        if (!resource) throw std::invalid_argument("null resource");
        return resource;
    }
public:
    explicit RecordStore(std::pmr::memory_resource* resource)
        : values_(checked(resource)) {}

    std::span<const std::uint32_t> values() const noexcept {
        return values_;
    }

    void replace(std::span<const std::byte> bytes) {
        const auto count = read_le<std::uint32_t>(bytes, 0);
        if (count > 4096) throw std::runtime_error("too many records");
        const std::size_t tail = bytes.size() - sizeof(std::uint32_t);
        if (tail % 4 != 0 || tail / 4 != count)
            throw std::runtime_error("invalid length");

        std::pmr::vector<std::uint32_t> candidate(
            values_.get_allocator().resource());
        candidate.reserve(count);
        for (std::size_t i = 0; i < count; ++i)
            candidate.push_back(read_le<std::uint32_t>(bytes, 4 + i * 4));
        values_.swap(candidate);
    }
};

int main() {
    const std::array good{
        std::byte{2}, std::byte{0}, std::byte{0}, std::byte{0},
        std::byte{7}, std::byte{0}, std::byte{0}, std::byte{0},
        std::byte{9}, std::byte{0}, std::byte{0}, std::byte{0}};
    BudgetResource resource;
    {
        RecordStore store(&resource);
        store.replace(good);
        require(store.values().size() == 2 && store.values()[0] == 7);

        resource.remaining = 0;
        bool allocation_failed = false;
        try { store.replace(good); }
        catch (const std::bad_alloc&) { allocation_failed = true; }
        require(allocation_failed);
        require(store.values().size() == 2 && store.values()[1] == 9);

        resource.remaining = 10;
        for (std::size_t length = 0; length < good.size(); ++length) {
            bool rejected = false;
            try {
                store.replace(std::span<const std::byte>(good).first(length));
            } catch (const std::runtime_error&) {
                rejected = true;
            }
            require(rejected);
            require(store.values().size() == 2 && store.values()[0] == 7);
        }

        const std::array empty{
            std::byte{0}, std::byte{0}, std::byte{0}, std::byte{0}};
        store.replace(empty);
        require(store.values().empty());
    }
    require(resource.live_blocks == 0 && resource.live_bytes == 0);
    std::printf("peak=%zu\n", resource.peak_bytes);
}

cl /nologo /std:c++20 /EHsc /W4 /Zi records.cpp /Ferecords.exe
.\records.exe

הבדיקה ב־read_le משתמשת בחיסור רק אחרי שווידאנו שה־offset אינו גדול מהאורך. כתיבת offset + sizeof(T) > size הייתה פותחת אפשרות לגלישה בחיבור. בגוף ה־parser כבר ידוע שקיימים לפחות ארבעה בתים, כי קריאת הכותרת הצליחה. לכן החיסור שמחשב את הזנב חוקי.

ההזזה מתאימה לטיפוס unsigned ברוחבים המקובלים של היעד, שבו בית הוא שמונה ביט. עבור טיפוסים קטנים פועלים גם כללי integer promotions; הערכים בכל הזזה נשארים בתחום המותר בדוגמה. אם הספרייה מיועדת לפלטפורמה אחרת, צריך לקבע את הנחת CHAR_BIT == 8 ולהוסיף בדיקה מפורשת.

ה־swap מתבצע בין שתי מכולות עם אותו משאב. השוויון בין ה־allocators הוא תנאי חשוב: החלפת buffers בין משאבים שאינם רשאים לשחרר זה את ההקצאות של זה עלולה להפר את חוזה המכולה. המועמדת מקבלת לאחר ההחלפה את הנתונים הישנים ומשחררת אותם ביציאה מהפונקציה.

הבנאי בודק את המשאב באמצעות פונקציית עזר ברשימת האתחול, לפני בניית המכולה. בדיקה בגוף הבנאי הייתה מגיעה מאוחר מדי אם בניית המכולה עצמה דורשת משאב תקין. המיקום של הבדיקה הוא חלק מהוכחת החוזה, ולא רק עניין של סגנון.

התרגיל דורש גם זנב עודף וספירה גדולה מדי. עבור זנב עודף מוסיפים בית יחיד ל־good ומוודאים דחייה. עבור ספירה גדולה מדי יוצרים כותרת שמייצגת 4097, ומוודאים שהכשל קורה לפני בקשת הקצאה. מונה ההקצאות מאפשר לבדוק זאת באופן ממוקד.

הרחבת ממשק C יכולה לחשוף records_create, records_replace, records_count, records_copy ו־records_destroy. הפעולה שמעתיקה צריכה לקבל capacity ומספר מועתק, ולדחות buffer קטן בלי כתיבה חלקית אם זו הערבות שנבחרה. בכניסה ל־records_replace מתרגמים חריגת קלט לקוד שגיאה אחר מ־bad_alloc. אין דרך לגיטימית לאמת כל מצביע שרירותי באמצעות בדיקת null בלבד; תקפות טווחי הקלט נשארת חלק מחוזה הקריאה.

למדידה מול arena יוצרים monotonic_buffer_resource מחוץ למכולה ומספקים לו upstream סופר. מדידה כזו סופרת בקשות מה־arena כלפי מעלה, ולא כל בקשה מהמכולה אל ה־arena. צריך לציין באיזו שכבה נמצא המונה. אין להשוות שני מספרים שנאספו בשכבות שונות ולקרוא להפרש שיפור.

הפתרון מדגים ערבות חזקה לשינוי הרשומות. הוא אינו מבטיח שלא תהיה הקצאה נוספת, ואינו תומך בשימוש מקביל. אלה הרחבות שדורשות חוזה חדש, בדיקות חדשות והבנה של המנגנונים שנלמד בפרקים הבאים.