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