1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
3 | |
4 | #include "mmu_internal.h" |
5 | #include "tdp_iter.h" |
6 | #include "spte.h" |
7 | |
8 | /* |
9 | * Recalculates the pointer to the SPTE for the current GFN and level and |
10 | * reread the SPTE. |
11 | */ |
12 | static void tdp_iter_refresh_sptep(struct tdp_iter *iter) |
13 | { |
14 | iter->sptep = iter->pt_path[iter->level - 1] + |
15 | SPTE_INDEX(iter->gfn << PAGE_SHIFT, iter->level); |
16 | iter->old_spte = kvm_tdp_mmu_read_spte(sptep: iter->sptep); |
17 | } |
18 | |
19 | /* |
20 | * Return the TDP iterator to the root PT and allow it to continue its |
21 | * traversal over the paging structure from there. |
22 | */ |
23 | void tdp_iter_restart(struct tdp_iter *iter) |
24 | { |
25 | iter->yielded = false; |
26 | iter->yielded_gfn = iter->next_last_level_gfn; |
27 | iter->level = iter->root_level; |
28 | |
29 | iter->gfn = gfn_round_for_level(gfn: iter->next_last_level_gfn, level: iter->level); |
30 | tdp_iter_refresh_sptep(iter); |
31 | |
32 | iter->valid = true; |
33 | } |
34 | |
35 | /* |
36 | * Sets a TDP iterator to walk a pre-order traversal of the paging structure |
37 | * rooted at root_pt, starting with the walk to translate next_last_level_gfn. |
38 | */ |
39 | void tdp_iter_start(struct tdp_iter *iter, struct kvm_mmu_page *root, |
40 | int min_level, gfn_t next_last_level_gfn) |
41 | { |
42 | if (WARN_ON_ONCE(!root || (root->role.level < 1) || |
43 | (root->role.level > PT64_ROOT_MAX_LEVEL))) { |
44 | iter->valid = false; |
45 | return; |
46 | } |
47 | |
48 | iter->next_last_level_gfn = next_last_level_gfn; |
49 | iter->root_level = root->role.level; |
50 | iter->min_level = min_level; |
51 | iter->pt_path[iter->root_level - 1] = (tdp_ptep_t)root->spt; |
52 | iter->as_id = kvm_mmu_page_as_id(sp: root); |
53 | |
54 | tdp_iter_restart(iter); |
55 | } |
56 | |
57 | /* |
58 | * Given an SPTE and its level, returns a pointer containing the host virtual |
59 | * address of the child page table referenced by the SPTE. Returns null if |
60 | * there is no such entry. |
61 | */ |
62 | tdp_ptep_t spte_to_child_pt(u64 spte, int level) |
63 | { |
64 | /* |
65 | * There's no child entry if this entry isn't present or is a |
66 | * last-level entry. |
67 | */ |
68 | if (!is_shadow_present_pte(pte: spte) || is_last_spte(pte: spte, level)) |
69 | return NULL; |
70 | |
71 | return (tdp_ptep_t)__va(spte_to_pfn(spte) << PAGE_SHIFT); |
72 | } |
73 | |
74 | /* |
75 | * Steps down one level in the paging structure towards the goal GFN. Returns |
76 | * true if the iterator was able to step down a level, false otherwise. |
77 | */ |
78 | static bool try_step_down(struct tdp_iter *iter) |
79 | { |
80 | tdp_ptep_t child_pt; |
81 | |
82 | if (iter->level == iter->min_level) |
83 | return false; |
84 | |
85 | /* |
86 | * Reread the SPTE before stepping down to avoid traversing into page |
87 | * tables that are no longer linked from this entry. |
88 | */ |
89 | iter->old_spte = kvm_tdp_mmu_read_spte(sptep: iter->sptep); |
90 | |
91 | child_pt = spte_to_child_pt(spte: iter->old_spte, level: iter->level); |
92 | if (!child_pt) |
93 | return false; |
94 | |
95 | iter->level--; |
96 | iter->pt_path[iter->level - 1] = child_pt; |
97 | iter->gfn = gfn_round_for_level(gfn: iter->next_last_level_gfn, level: iter->level); |
98 | tdp_iter_refresh_sptep(iter); |
99 | |
100 | return true; |
101 | } |
102 | |
103 | /* |
104 | * Steps to the next entry in the current page table, at the current page table |
105 | * level. The next entry could point to a page backing guest memory or another |
106 | * page table, or it could be non-present. Returns true if the iterator was |
107 | * able to step to the next entry in the page table, false if the iterator was |
108 | * already at the end of the current page table. |
109 | */ |
110 | static bool try_step_side(struct tdp_iter *iter) |
111 | { |
112 | /* |
113 | * Check if the iterator is already at the end of the current page |
114 | * table. |
115 | */ |
116 | if (SPTE_INDEX(iter->gfn << PAGE_SHIFT, iter->level) == |
117 | (SPTE_ENT_PER_PAGE - 1)) |
118 | return false; |
119 | |
120 | iter->gfn += KVM_PAGES_PER_HPAGE(iter->level); |
121 | iter->next_last_level_gfn = iter->gfn; |
122 | iter->sptep++; |
123 | iter->old_spte = kvm_tdp_mmu_read_spte(sptep: iter->sptep); |
124 | |
125 | return true; |
126 | } |
127 | |
128 | /* |
129 | * Tries to traverse back up a level in the paging structure so that the walk |
130 | * can continue from the next entry in the parent page table. Returns true on a |
131 | * successful step up, false if already in the root page. |
132 | */ |
133 | static bool try_step_up(struct tdp_iter *iter) |
134 | { |
135 | if (iter->level == iter->root_level) |
136 | return false; |
137 | |
138 | iter->level++; |
139 | iter->gfn = gfn_round_for_level(gfn: iter->gfn, level: iter->level); |
140 | tdp_iter_refresh_sptep(iter); |
141 | |
142 | return true; |
143 | } |
144 | |
145 | /* |
146 | * Step to the next SPTE in a pre-order traversal of the paging structure. |
147 | * To get to the next SPTE, the iterator either steps down towards the goal |
148 | * GFN, if at a present, non-last-level SPTE, or over to a SPTE mapping a |
149 | * higher GFN. |
150 | * |
151 | * The basic algorithm is as follows: |
152 | * 1. If the current SPTE is a non-last-level SPTE, step down into the page |
153 | * table it points to. |
154 | * 2. If the iterator cannot step down, it will try to step to the next SPTE |
155 | * in the current page of the paging structure. |
156 | * 3. If the iterator cannot step to the next entry in the current page, it will |
157 | * try to step up to the parent paging structure page. In this case, that |
158 | * SPTE will have already been visited, and so the iterator must also step |
159 | * to the side again. |
160 | */ |
161 | void tdp_iter_next(struct tdp_iter *iter) |
162 | { |
163 | if (iter->yielded) { |
164 | tdp_iter_restart(iter); |
165 | return; |
166 | } |
167 | |
168 | if (try_step_down(iter)) |
169 | return; |
170 | |
171 | do { |
172 | if (try_step_side(iter)) |
173 | return; |
174 | } while (try_step_up(iter)); |
175 | iter->valid = false; |
176 | } |
177 | |
178 | |