Commit | Line | Data |
---|---|---|
c9180b72 | 1 | // SPDX-License-Identifier: GPL-2.0 |
8d20bd63 | 2 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
c9180b72 BG |
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] + | |
2ca3129e | 15 | SPTE_INDEX(iter->gfn << PAGE_SHIFT, iter->level); |
0e587aa7 | 16 | iter->old_spte = kvm_tdp_mmu_read_spte(iter->sptep); |
c9180b72 BG |
17 | } |
18 | ||
b601c3bc BG |
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 | { | |
3a0f64de | 25 | iter->yielded = false; |
b601c3bc BG |
26 | iter->yielded_gfn = iter->next_last_level_gfn; |
27 | iter->level = iter->root_level; | |
28 | ||
c667a3ba | 29 | iter->gfn = gfn_round_for_level(iter->next_last_level_gfn, iter->level); |
b601c3bc BG |
30 | tdp_iter_refresh_sptep(iter); |
31 | ||
32 | iter->valid = true; | |
33 | } | |
34 | ||
c9180b72 BG |
35 | /* |
36 | * Sets a TDP iterator to walk a pre-order traversal of the paging structure | |
74953d35 | 37 | * rooted at root_pt, starting with the walk to translate next_last_level_gfn. |
c9180b72 | 38 | */ |
77aa6075 | 39 | void tdp_iter_start(struct tdp_iter *iter, struct kvm_mmu_page *root, |
74953d35 | 40 | int min_level, gfn_t next_last_level_gfn) |
c9180b72 | 41 | { |
2c6d4c27 SC |
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 | } | |
c9180b72 | 47 | |
74953d35 | 48 | iter->next_last_level_gfn = next_last_level_gfn; |
2c6d4c27 | 49 | iter->root_level = root->role.level; |
c9180b72 | 50 | iter->min_level = min_level; |
77aa6075 DM |
51 | iter->pt_path[iter->root_level - 1] = (tdp_ptep_t)root->spt; |
52 | iter->as_id = kvm_mmu_page_as_id(root); | |
c9180b72 | 53 | |
b601c3bc | 54 | tdp_iter_restart(iter); |
c9180b72 BG |
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 | */ | |
7cca2d0b | 62 | tdp_ptep_t spte_to_child_pt(u64 spte, int level) |
c9180b72 BG |
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(spte) || is_last_spte(spte, level)) | |
69 | return NULL; | |
70 | ||
7cca2d0b | 71 | return (tdp_ptep_t)__va(spte_to_pfn(spte) << PAGE_SHIFT); |
c9180b72 BG |
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 | { | |
7cca2d0b | 80 | tdp_ptep_t child_pt; |
c9180b72 BG |
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 | */ | |
0e587aa7 | 89 | iter->old_spte = kvm_tdp_mmu_read_spte(iter->sptep); |
c9180b72 BG |
90 | |
91 | child_pt = spte_to_child_pt(iter->old_spte, iter->level); | |
92 | if (!child_pt) | |
93 | return false; | |
94 | ||
95 | iter->level--; | |
96 | iter->pt_path[iter->level - 1] = child_pt; | |
c667a3ba | 97 | iter->gfn = gfn_round_for_level(iter->next_last_level_gfn, iter->level); |
c9180b72 BG |
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 | */ | |
2ca3129e SC |
116 | if (SPTE_INDEX(iter->gfn << PAGE_SHIFT, iter->level) == |
117 | (SPTE_ENT_PER_PAGE - 1)) | |
c9180b72 BG |
118 | return false; |
119 | ||
120 | iter->gfn += KVM_PAGES_PER_HPAGE(iter->level); | |
74953d35 | 121 | iter->next_last_level_gfn = iter->gfn; |
c9180b72 | 122 | iter->sptep++; |
0e587aa7 | 123 | iter->old_spte = kvm_tdp_mmu_read_spte(iter->sptep); |
c9180b72 BG |
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++; | |
c667a3ba | 139 | iter->gfn = gfn_round_for_level(iter->gfn, iter->level); |
c9180b72 BG |
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 | |
54aa699e | 149 | * higher GFN. |
c9180b72 BG |
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 | { | |
3a0f64de SC |
163 | if (iter->yielded) { |
164 | tdp_iter_restart(iter); | |
165 | return; | |
166 | } | |
167 | ||
c9180b72 BG |
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 |