1/* @title: Page Table */
2#pragma once
3#include <asm.h>
4#include <irq/irq.h>
5#include <mem/page.h>
6#include <sch/irql.h>
7#include <stdatomic.h>
8#include <stdint.h>
9
10#define PT_LEVELS 4
11
12#define PT_SHIFT_L1 12
13#define PT_SHIFT_L2 21
14#define PT_SHIFT_L3 30
15#define PT_SHIFT_L4 39
16
17#define PT_STRIDE 9
18
19#define PTE_LOCK_SHIFT 9
20#define PTE_AVAIL2_SHIFT 10
21#define PTE_LOCK_BIT ((uint64_t) 1 << PTE_LOCK_SHIFT)
22#define PTE_AVAIL2_BIT ((uint64_t) 1 << PTE_AVAIL2_SHIFT)
23
24/* Mark an entry whose child table is shared with other entries, this is what
25 * we use in aliasing. The subtree should never be freed through this entry,
26 * since every other entry pointing at it would see the change too. This
27 * should only ever be set on present entries */
28#define PTE_SHARED_SHIFT 11
29#define PTE_SHARED_BIT ((uint64_t) 1 << PTE_SHARED_SHIFT)
30
31static inline bool pte_is_shared(uint64_t pte) {
32 return (pte & PAGE_PRESENT) && (pte & PTE_SHARED_BIT);
33}
34
35/* Packed layout:
36 *
37 * bit 0 P = 0
38 * bits 1-2 type
39 * bits 3-8 payload low (6 bits)
40 * bit 9 LOCK (not payload)
41 * bit 10 AVAIL2 (not payload)
42 * bits 11-63 payload high (53 bits)
43 *
44 * Do note that SHARED is not accounted for here, because
45 * that bit is only ever set on PRESENT entries
46 */
47#define PTE_TAGGED_TYPE_SHIFT (PAGE_PRESENT_SHIFT + 1)
48#define PTE_TAGGED_TYPE_MASK 0x3ULL
49
50#define PTE_TAGGED_PAYLOAD_LOW_BITS 6
51#define PTE_TAGGED_PAYLOAD_LOW_SHIFT 3 /* packed position of the low chunk */
52#define PTE_TAGGED_PAYLOAD_HIGH_SHIFT \
53 11 /* packed position of the high chunk \
54 */
55#define PTE_TAGGED_PAYLOAD_LOW_MASK ((1ULL << PTE_TAGGED_PAYLOAD_LOW_BITS) - 1)
56#define PTE_TAGGED_PAYLOAD_BITS \
57 (PTE_TAGGED_PAYLOAD_LOW_BITS + (64 - PTE_TAGGED_PAYLOAD_HIGH_SHIFT))
58
59#define PTE_TAGGED_GET_TYPE(pte) \
60 (((pte) >> PTE_TAGGED_TYPE_SHIFT) & PTE_TAGGED_TYPE_MASK)
61#define PTE_TAGGED_SET_TYPE(type) ((uint64_t) (type) << PTE_TAGGED_TYPE_SHIFT)
62
63typedef _Atomic uint64_t pte_atomic_t;
64
65/* Packed into the low X bits */
66enum pte_tag_type : uint8_t {
67 PTE_TAG_TYPE_NONE = 0,
68 PTE_TAG_TYPE_DEMAND_PAGED = 1,
69};
70
71/* This is a bit like a tagged pointer, just
72 * that the payload moseys around LOCK_BIT and AVAIL2,
73 * and the type sits right above PRESENT
74 *
75 * The layout is effectively
76 *
77 * [ payload higher ] [ LOCK + AVAIL2 ] [ payload lower ] [ type ] [ P = 0 ]
78 */
79struct pte_tagged {
80 enum pte_tag_type type;
81 uint64_t payload; /* NOTE: higher 5 bits MUST be zero */
82};
83
84static inline void pte_tagged_check(struct pte_tagged *pt) {
85 kassert(pt->type != PTE_TAG_TYPE_NONE);
86 kassert((pt->payload >> PTE_TAGGED_PAYLOAD_BITS) == 0);
87}
88
89static inline uint64_t pte_tagged_pack(struct pte_tagged *pt) {
90 /* We leave LOCK + AVAIL2 zeroed here, whoever uses this must OR it into a
91 * PTE that already holds those bits, probably atomically */
92 uint64_t low = pt->payload & PTE_TAGGED_PAYLOAD_LOW_MASK;
93 uint64_t high = pt->payload >> PTE_TAGGED_PAYLOAD_LOW_BITS;
94
95 return PTE_TAGGED_SET_TYPE(pt->type) |
96 (low << PTE_TAGGED_PAYLOAD_LOW_SHIFT) |
97 (high << PTE_TAGGED_PAYLOAD_HIGH_SHIFT);
98}
99
100static inline struct pte_tagged pte_tagged_unpack(pte_t pte) {
101 struct pte_tagged pt;
102 pt.type = PTE_TAGGED_GET_TYPE(pte);
103
104 uint64_t low =
105 (pte >> PTE_TAGGED_PAYLOAD_LOW_SHIFT) & PTE_TAGGED_PAYLOAD_LOW_MASK;
106 uint64_t high = pte >> PTE_TAGGED_PAYLOAD_HIGH_SHIFT;
107
108 pt.payload = (high << PTE_TAGGED_PAYLOAD_LOW_BITS) | low;
109 return pt;
110}
111
112static inline bool pte_locked(pte_atomic_t *pte) {
113 return atomic_load_explicit(pte, memory_order_relaxed) & PTE_LOCK_BIT;
114}
115
116static inline uint64_t pte_read(pte_atomic_t *pte) {
117 return atomic_load_explicit(pte, memory_order_relaxed);
118}
119
120static inline uint64_t pte_or(pte_atomic_t *pte, uint64_t val) {
121 return atomic_fetch_or_explicit(pte, val, memory_order_acq_rel);
122}
123
124static inline void pte_unlock_internal(pte_atomic_t *pte) {
125 kassert(
126 atomic_fetch_and_explicit(pte, ~PTE_LOCK_BIT, memory_order_release) &
127 PTE_LOCK_BIT);
128}
129
130/* TODO: use bit_spinlock.h */
131static inline void pte_lock_internal(pte_atomic_t *pte) {
132 for (;;) {
133 uint64_t old = atomic_load_explicit(pte, memory_order_relaxed);
134
135 if (old & PTE_LOCK_BIT) {
136 cpu_relax();
137 continue;
138 }
139
140 if (atomic_compare_exchange_weak_explicit(pte, &old, old | PTE_LOCK_BIT,
141 memory_order_acquire,
142 memory_order_relaxed))
143 return;
144
145 cpu_relax();
146 }
147}
148
149static inline enum irql pte_lock_irql(pte_atomic_t *pte) {
150 enum irql old_irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
151 pte_lock_internal(pte);
152 return old_irql;
153}
154
155static inline void pte_unlock_irql(pte_atomic_t *pte, enum irql old_irql) {
156 pte_unlock_internal(pte);
157 irql_lower(old_level: old_irql);
158}
159
160static inline bool pte_has_tag(pte_atomic_t *pte) {
161 kassert(!(pte_read(pte) & PAGE_PRESENT));
162 return (pte_read(pte) & ~(PAGE_PRESENT | PTE_LOCK_BIT | PTE_AVAIL2_BIT)) !=
163 0;
164}
165
166static inline uint64_t pte_tag_pte(pte_atomic_t *pte, struct pte_tagged *ptag) {
167 kassert(pte_locked(pte));
168 kassert(!pte_has_tag(pte));
169 pte_tagged_check(pt: ptag);
170 uint64_t packed = pte_tagged_pack(pt: ptag);
171 return pte_or(pte, val: packed);
172}
173
174static inline struct pte_tagged pte_read_tag(pte_atomic_t *pte) {
175 kassert(pte_has_tag(pte));
176 return pte_tagged_unpack(pte: pte_read(pte));
177}
178
179static inline bool pte_in_use(pte_atomic_t *pte) {
180 if (pte_read(pte) & PAGE_PRESENT)
181 return true;
182
183 return pte_has_tag(pte);
184}
185