ic-sqlite-vfs 2.0.0

SQLite VFS backed directly by Internet Computer stable memory
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

//! Verus model for MemoryManager::grow bucket arithmetic.
//!
//! This proof isolates the grow path that maps logical memory pages to backing
//! buckets. It checks monotonic bucket demand and the subtraction/grow deltas
//! used by the production implementation.

use vstd::prelude::*;

verus! {

spec fn default_bucket_size_in_pages() -> nat {
    128
}

spec fn max_num_buckets() -> nat {
    32_768
}

spec fn buckets_offset_in_pages() -> nat {
    1
}

spec fn u64_max() -> nat {
    18_446_744_073_709_551_615
}

spec fn u16_max() -> nat {
    65_535
}

spec fn div_ceil(numerator: nat, denominator: nat) -> nat {
    if numerator == 0 {
        0
    } else {
        (((numerator - 1) / (denominator as int)) + 1) as nat
    }
}

spec fn num_buckets_needed(pages: nat, bucket_size: nat) -> nat {
    div_ceil(pages, bucket_size)
}

spec fn checked_add(left: nat, right: nat) -> Option<nat> {
    if left + right <= u64_max() {
        Some(left + right)
    } else {
        None
    }
}

spec fn checked_sub(left: nat, right: nat) -> Option<nat> {
    if right <= left {
        Some((left - right) as nat)
    } else {
        None
    }
}

spec fn pages_needed_for_buckets(target_buckets: nat, bucket_size: nat) -> nat {
    buckets_offset_in_pages() + bucket_size * target_buckets
}

proof fn div_ceil_monotonic(left: nat, right: nat, bucket_size: nat)
    by (nonlinear_arith)
    requires
        left <= right,
        bucket_size > 0,
    ensures
        div_ceil(left, bucket_size) <= div_ceil(right, bucket_size),
{
}

proof fn bucket_need_is_monotonic(old_size: nat, new_size: nat, bucket_size: nat)
    requires
        old_size <= new_size,
        bucket_size > 0,
    ensures
        num_buckets_needed(old_size, bucket_size) <= num_buckets_needed(new_size, bucket_size),
{
    div_ceil_monotonic(old_size, new_size, bucket_size);
}

proof fn checked_add_pages_implies_bucket_subtraction_safe(
    old_size: nat,
    pages: nat,
    new_size: nat,
    bucket_size: nat,
)
    requires
        checked_add(old_size, pages) == Some(new_size),
        bucket_size > 0,
    ensures
        old_size <= new_size,
        num_buckets_needed(old_size, bucket_size) <= num_buckets_needed(new_size, bucket_size),
        matches!(
            checked_sub(
                num_buckets_needed(new_size, bucket_size),
                num_buckets_needed(old_size, bucket_size),
            ),
            Some(_),
        ),
{
    bucket_need_is_monotonic(old_size, new_size, bucket_size);
}

proof fn target_bucket_count_within_max(
    allocated_buckets: nat,
    new_buckets: nat,
    target_allocated_buckets: nat,
)
    requires
        checked_add(allocated_buckets, new_buckets) == Some(target_allocated_buckets),
        target_allocated_buckets <= max_num_buckets(),
    ensures
        target_allocated_buckets <= max_num_buckets(),
        allocated_buckets <= target_allocated_buckets,
{
}

proof fn pages_needed_for_max_buckets_fits_u64(target_allocated_buckets: nat)
    by (nonlinear_arith)
    requires
        target_allocated_buckets <= max_num_buckets(),
        default_bucket_size_in_pages() <= u16_max(),
    ensures
        pages_needed_for_buckets(target_allocated_buckets, default_bucket_size_in_pages())
            <= u64_max(),
{
}

proof fn pages_needed_for_positive_bucket_size_fits_u64(
    target_allocated_buckets: nat,
    bucket_size: nat,
)
    by (nonlinear_arith)
    requires
        target_allocated_buckets <= max_num_buckets(),
        0 < bucket_size <= u16_max(),
    ensures
        pages_needed_for_buckets(target_allocated_buckets, bucket_size) <= u64_max(),
{
}

proof fn backing_grow_delta_is_safe(current_pages: nat, pages_needed: nat)
    requires
        current_pages <= pages_needed,
    ensures
        checked_sub(pages_needed, current_pages) == Some((pages_needed - current_pages) as nat),
{
}

proof fn backing_pages_cover_target_buckets(target_allocated_buckets: nat, bucket_size: nat)
    requires
        bucket_size > 0,
    ensures
        pages_needed_for_buckets(target_allocated_buckets, bucket_size)
            == buckets_offset_in_pages() + bucket_size * target_allocated_buckets,
{
}

}