k-vmiter.hh 8.67 KB
Newer Older
Eddie Kohler's avatar
Eddie Kohler committed
1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef CHICKADEE_K_VMITER_HH
#define CHICKADEE_K_VMITER_HH
#include "kernel.hh"

// `vmiter` and `ptiter` are iterator types for x86-64 page tables.


// `vmiter` walks over virtual address mappings.
// `pa()` and `perm()` read current addresses and permissions;
// `map()` installs new mappings.

class vmiter {
  public:
Eddie Kohler's avatar
Eddie Kohler committed
14
    // Initialize a `vmiter` for `pt`, with initial virtual address `va`
Eddie Kohler's avatar
Eddie Kohler committed
15
16
17
    inline vmiter(x86_64_pagetable* pt, uintptr_t va = 0);
    inline vmiter(const proc* p, uintptr_t va = 0);

Eddie Kohler's avatar
Eddie Kohler committed
18
19
20
21
22
23
24
25
26
27
28
    // Return current virtual address
    inline uintptr_t va() const;
    // Return one past last virtual address in this mapping range
    inline uintptr_t last_va() const;
    // Return true iff `va() <= VA_LOWMAX` (is a low canonical address)
    inline bool low() const;
    // Return physical address mapped at `va()`,
    // or `(uintptr_t) -1` if `va()` is unmapped
    inline uint64_t pa() const;
    // Return a kernel-accessible pointer corresponding to `pa()`,
    // or `nullptr` if `va()` is unmapped
Eddie Kohler's avatar
Eddie Kohler committed
29
    template <typename T = void*>
Eddie Kohler's avatar
Eddie Kohler committed
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    inline T kptr() const;

    // Return permissions of current mapping.
    // Returns 0 unless `PTE_P` is set.
    inline uint64_t perm() const;
    // Return true iff `va()` is present (`PTE_P`)
    inline bool present() const;
    // Return true iff `va()` is present and writable (`PTE_P|PTE_W`)
    inline bool writable() const;
    // Return true iff `va()` is present and unprivileged (`PTE_P|PTE_U`)
    inline bool user() const;
    // Return intersection of permissions in [va(), va() + sz)
    uint64_t range_perm(size_t sz) const;
    // Return true iff `(perm() & desired_perm) == desired_perm`
    inline bool perm(uint64_t desired_perm) const;
    // Return true iff `(range_perm(sz) & desired_perm) == desired_perm`
    inline bool range_perm(size_t sz, uint64_t desired_perm) const;
Eddie Kohler's avatar
Eddie Kohler committed
47
48


Eddie Kohler's avatar
Eddie Kohler committed
49
50
51
52
53
54
55
56
57
58
    // Move to virtual address `va`; return `*this`
    inline vmiter& find(uintptr_t va);
    // Advance to virtual address `va() + delta`; return `*this`
    inline vmiter& operator+=(intptr_t delta);
    // Advance to virtual address `va() - delta`; return `*this`
    inline vmiter& operator-=(intptr_t delta);
    // Move to next larger page-aligned virtual address, skipping large
    // non-present regions
    void next();
    // Move to `last_va()`
Eddie Kohler's avatar
Eddie Kohler committed
59
60
    void next_range();

Eddie Kohler's avatar
Eddie Kohler committed
61
62
63
    // Map current virtual address to `pa` with permissions `perm`.
    // The current virtual address must be page-aligned. Calls `kalloc`
    // to allocate page table pages if necessary; panics on failure.
Eddie Kohler's avatar
Eddie Kohler committed
64
    inline void map(uintptr_t pa, int perm);
Eddie Kohler's avatar
Eddie Kohler committed
65
    // Same, but map a kernel pointer
Eddie Kohler's avatar
Eddie Kohler committed
66
67
    inline void map(void* kptr, int perm);

Eddie Kohler's avatar
Eddie Kohler committed
68
69
70
71
72
73
    // Map current virtual address to `pa` with permissions `perm`.
    // The current virtual address must be page-aligned. Calls `kalloc`
    // to allocate page table pages if necessary; returns 0 on success
    // and -1 on failure.
    [[gnu::warn_unused_result]] int try_map(uintptr_t pa, int perm);
    [[gnu::warn_unused_result]] inline int try_map(void* kptr, int perm);
Eddie Kohler's avatar
Eddie Kohler committed
74

Eddie Kohler's avatar
Eddie Kohler committed
75
    // Free mapped page and clear mapping. Like `kfree(kptr()); map(0, 0)`
Eddie Kohler's avatar
Eddie Kohler committed
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
    inline void kfree_page();

  private:
    x86_64_pagetable* pt_;
    x86_64_pageentry_t* pep_;
    int level_;
    int perm_;
    uintptr_t va_;

    static constexpr int initial_perm = 0xFFF;
    static const x86_64_pageentry_t zero_pe;

    void down();
    void real_find(uintptr_t va);
};


// `ptiter` walks over the page table pages in a page table,
// returning them in depth-first order.
// This is mainly useful when freeing a page table, as in:
// ```
// for (ptiter it(pt); it.low(); it.next()) {
//     it.kfree_ptp();
// }
// kfree(pt);
// ```
Eddie Kohler's avatar
Eddie Kohler committed
102
// Note that `ptiter` will never visit the root (level-4) page table page.
Eddie Kohler's avatar
Eddie Kohler committed
103
104
105

class ptiter {
  public:
Eddie Kohler's avatar
Eddie Kohler committed
106
    // Initialize a physical iterator for `pt` with initial virtual address 0
benkma's avatar
benkma committed
107
108
    inline ptiter(x86_64_pagetable* pt, uintptr_t va);
    inline ptiter(const proc* p, uintptr_t va);
Eddie Kohler's avatar
Eddie Kohler committed
109
110
111
112
113
114
115
116
117
118

    // Return true once `ptiter` has iterated over all page table pages
    // (not including the top-level page table page)
    inline bool done() const;

    // Return physical address of current page table page
    inline uintptr_t pa() const;
    // Return kernel-accessible pointer to the current page table page
    inline x86_64_pagetable* kptr() const;
    // Move to next page table page in depth-first order
Eddie Kohler's avatar
Eddie Kohler committed
119
120
    inline void next();

Eddie Kohler's avatar
Eddie Kohler committed
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
    // Return current virtual address
    inline uintptr_t va() const;
    // Return one past the last virtual address in this mapping range
    inline uintptr_t last_va() const;
    // Return true iff `va() <= VA_LOWMAX` (is low canonical)
    inline bool low() const;
    // Return level of current page table page (0-2)
    inline int level() const;

    // Return first virtual address covered by entry `idx` in current pt
    inline uintptr_t entry_va(unsigned idx) const;
    // Return one past the last virtual address covered by entry
    inline uintptr_t entry_last_va(unsigned idx) const;
    // Return current page table entry
    inline x86_64_pageentry_t entry(unsigned idx) const;

    // Free current page table page (`kptr()`) and unmap current entry
    inline void kfree_ptp();

Eddie Kohler's avatar
Eddie Kohler committed
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
  private:
    x86_64_pagetable* pt_;
    x86_64_pageentry_t* pep_;
    int level_;
    uintptr_t va_;

    void go(uintptr_t va);
    void down(bool skip);
};


inline vmiter::vmiter(x86_64_pagetable* pt, uintptr_t va)
    : pt_(pt), pep_(&pt_->entry[0]), level_(3), perm_(initial_perm), va_(0) {
    real_find(va);
}
inline vmiter::vmiter(const proc* p, uintptr_t va)
    : vmiter(p->pagetable_, va) {
}
inline uintptr_t vmiter::va() const {
    return va_;
}
inline uintptr_t vmiter::last_va() const {
    return (va_ | pageoffmask(level_)) + 1;
}
inline bool vmiter::low() const {
    return va_ <= VA_LOWMAX;
}
inline uint64_t vmiter::pa() const {
    if (*pep_ & PTE_P) {
        uintptr_t pa = *pep_ & PTE_PAMASK;
        if (level_ > 0) {
            pa &= ~0x1000UL;
        }
        return pa + (va_ & pageoffmask(level_));
    } else {
        return -1;
    }
}
template <typename T>
inline T vmiter::kptr() const {
    if (*pep_ & PTE_P) {
Eddie Kohler's avatar
Eddie Kohler committed
181
        return pa2kptr<T>(pa());
Eddie Kohler's avatar
Eddie Kohler committed
182
    } else {
Eddie Kohler's avatar
Eddie Kohler committed
183
        return nullptr;
Eddie Kohler's avatar
Eddie Kohler committed
184
185
    }
}
Eddie Kohler's avatar
Eddie Kohler committed
186
187
188
189
190
191
192
193
inline uint64_t vmiter::perm() const {
    // Returns 0-0xFFF. (XXX Does not track PTE_XD.)
    // Returns 0 unless `(*pep_ & perm_ & PTE_P) != 0`.
    uint64_t ph = *pep_ & perm_;
    return ph & -(ph & PTE_P);
}
inline bool vmiter::perm(uint64_t desired_perm) const {
    return (perm() & desired_perm) == desired_perm;
Eddie Kohler's avatar
Eddie Kohler committed
194
195
}
inline bool vmiter::present() const {
Eddie Kohler's avatar
Eddie Kohler committed
196
    return perm(PTE_P);
Eddie Kohler's avatar
Eddie Kohler committed
197
198
199
200
201
202
203
}
inline bool vmiter::writable() const {
    return perm(PTE_P | PTE_W);
}
inline bool vmiter::user() const {
    return perm(PTE_P | PTE_U);
}
Eddie Kohler's avatar
Eddie Kohler committed
204
205
206
inline bool vmiter::range_perm(size_t sz, uint64_t desired_perm) const {
    return (range_perm(sz) & desired_perm) == desired_perm;
}
Eddie Kohler's avatar
Eddie Kohler committed
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
inline vmiter& vmiter::find(uintptr_t va) {
    real_find(va);
    return *this;
}
inline vmiter& vmiter::operator+=(intptr_t delta) {
    return find(va_ + delta);
}
inline vmiter& vmiter::operator-=(intptr_t delta) {
    return find(va_ - delta);
}
inline void vmiter::next_range() {
    real_find(last_va());
}
inline void vmiter::map(uintptr_t pa, int perm) {
    int r = try_map(pa, perm);
Eddie Kohler's avatar
Eddie Kohler committed
222
    assert(r == 0, "vmiter::map failed");
Eddie Kohler's avatar
Eddie Kohler committed
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
}
inline void vmiter::map(void* kp, int perm) {
    map(kptr2pa(kp), perm);
}
inline int vmiter::try_map(void* kp, int perm) {
    return try_map(kptr2pa(kp), perm);
}
inline void vmiter::kfree_page() {
    assert((va_ & (PAGESIZE - 1)) == 0);
    if (*pep_ & PTE_P) {
        kfree(kptr<void*>());
    }
    *pep_ = 0;
}

benkma's avatar
benkma committed
238
inline ptiter::ptiter(x86_64_pagetable* pt, uintptr_t va)
Eddie Kohler's avatar
Eddie Kohler committed
239
    : pt_(pt) {
benkma's avatar
benkma committed
240
    go(va);
Eddie Kohler's avatar
Eddie Kohler committed
241
}
benkma's avatar
benkma committed
242
243
inline ptiter::ptiter(const proc* p,  uintptr_t va)
    : ptiter(p->pagetable_, va) {
Eddie Kohler's avatar
Eddie Kohler committed
244
245
246
247
248
249
250
251
252
253
}
inline uintptr_t ptiter::va() const {
    return va_ & ~pageoffmask(level_);
}
inline uintptr_t ptiter::last_va() const {
    return (va_ | pageoffmask(level_)) + 1;
}
inline bool ptiter::low() const {
    return va_ <= VA_LOWMAX;
}
Eddie Kohler's avatar
Eddie Kohler committed
254
255
256
inline bool ptiter::done() const {
    return va_ > VA_NONCANONMAX;
}
Eddie Kohler's avatar
Eddie Kohler committed
257
258
259
260
261
262
inline int ptiter::level() const {
    return level_ - 1;
}
inline void ptiter::next() {
    down(true);
}
Eddie Kohler's avatar
Eddie Kohler committed
263
inline uintptr_t ptiter::pa() const {
Eddie Kohler's avatar
Eddie Kohler committed
264
265
    return *pep_ & PTE_PAMASK;
}
Eddie Kohler's avatar
Eddie Kohler committed
266
267
268
269
270
271
272
273
274
275
276
277
inline x86_64_pagetable* ptiter::kptr() const {
    return pa2kptr<x86_64_pagetable*>(pa());
}
inline uintptr_t ptiter::entry_va(unsigned idx) const {
    return va() + idx * (pageoffmask(level_ - 1) + 1);
}
inline uintptr_t ptiter::entry_last_va(unsigned idx) const {
    return va() + (idx + 1) * (pageoffmask(level_ - 1) + 1);
}
inline x86_64_pageentry_t ptiter::entry(unsigned idx) const {
    assert(idx < (1U << PAGEINDEXBITS));
    return kptr()->entry[idx];
Eddie Kohler's avatar
Eddie Kohler committed
278
279
}
inline void ptiter::kfree_ptp() {
Eddie Kohler's avatar
Eddie Kohler committed
280
    kfree(kptr());
Eddie Kohler's avatar
Eddie Kohler committed
281
282
283
284
    *pep_ = 0;
}

#endif