1#include <math/align.h>
2#include <smp/domain.h>
3
4#include "internal.h"
5
6static bool try_push_page_onto_arena(struct domain_arena *arena,
7 paddr_t address) {
8 struct buddy_page *buddy = buddy_page_for_addr(address);
9 return domain_arena_push(arena, page: buddy);
10}
11
12static bool try_push_page_onto_domain_arenas(struct domain_buddy *domain,
13 paddr_t address) {
14 struct domain_arena *arena;
15 struct buddy_page *this_page = buddy_page_for_addr(address);
16
17 domain_for_each_arena(domain, arena) {
18 if (domain_arena_push(arena, page: this_page))
19 return true;
20 }
21
22 return false;
23}
24
25/* First we try and add to our arena cache. If that fails,
26 * we try the next one, until an arena cache is able to
27 * hold the freed page. If none of these succeed, we give up and just free it */
28static void free_from_local_domain_buddy(struct domain_buddy *local,
29 paddr_t address, size_t page_count) {
30 if (page_count > 1)
31 return free_from_buddy_internal(target: local, address, page_count);
32
33 struct domain_arena *local_arena = domain_arena_on_this_core();
34
35 /* Try local core first */
36 if (try_push_page_onto_arena(arena: local_arena, address))
37 return;
38
39 /* Try putting the page on other cores */
40 if (try_push_page_onto_domain_arenas(domain: local, address))
41 return;
42
43 /* No success? Let's flush it from the buddy */
44 free_from_buddy_internal(target: local, address, page_count);
45}
46
47/* First, we try and enqueue it onto the remote freequeue.
48 *
49 * If this fails, and we have a multi-page free, then we flush it to
50 * their buddy. If this fails, and we have a single-page free, then
51 * we first try to push the page onto the remote arenas.
52 *
53 * If that fails, (on single-page frees), then we flush it to their buddy
54 */
55static void free_from_remote_domain_buddy(struct domain_buddy *remote,
56 paddr_t address, size_t page_count) {
57 struct domain_free_queue *remote_freequeue = remote->free_queue;
58
59 if (domain_free_queue_enqueue(fq: remote_freequeue, addr: address, pages: page_count))
60 return;
61
62 if (page_count > 1)
63 return free_from_buddy_internal(target: remote, address, page_count);
64
65 if (try_push_page_onto_domain_arenas(domain: remote, address))
66 return;
67
68 free_from_buddy_internal(target: remote, address, page_count);
69}
70
71static inline struct domain_arena *
72domain_first_arena(struct domain_buddy *domain) {
73 return domain->arenas[0];
74}
75
76static struct domain_arena *get_next_domain_arena(struct domain_buddy *domain,
77 size_t *current_arena_idx) {
78 if (++*current_arena_idx < domain->core_count)
79 return domain->arenas[*current_arena_idx];
80
81 /* Nope, let's flush to the buddy */
82 return NULL;
83}
84
85static struct domain_arena *find_non_full_arena(struct domain_buddy *domain,
86 size_t *current_arena_idx) {
87 while (true) {
88 struct domain_arena *ret =
89 get_next_domain_arena(domain, current_arena_idx);
90 if (!ret)
91 return NULL;
92
93 if (atomic_load(&ret->num_pages) < ret->capacity)
94 return ret;
95 }
96}
97
98static size_t compute_min_elements_to_free(struct domain_buddy *domain,
99 struct domain_free_queue *queue) {
100
101 size_t total_slots_available = 0;
102 struct domain_arena *curr;
103
104 domain_for_each_arena(domain, curr) {
105 total_slots_available += curr->capacity - atomic_load(&curr->num_pages);
106 }
107
108 size_t target = atomic_load(&queue->num_elements) / 2;
109 if (target > total_slots_available)
110 target = total_slots_available;
111
112 return target > 0 ? target : 1;
113}
114
115static void flush_free_queue_internal(struct domain_buddy *domain,
116 struct domain_free_queue *queue,
117 size_t minimum_to_free) {
118 /* current_arena becomes NULL once we have filled all arenas */
119 struct domain_arena *current_arena = domain_first_arena(domain);
120 size_t current_arena_idx = 0;
121 for (size_t i = 0; i < minimum_to_free; i++) {
122 size_t addr = 0, page_count = 0;
123 domain_free_queue_dequeue(fq: queue, addr_out: &addr, pages_out: &page_count);
124
125 /* We are done. Free queue is empty */
126 if (addr == 0)
127 return;
128
129 if (page_count > 1 || current_arena == NULL) {
130 free_from_buddy_internal(target: domain, address: addr, page_count);
131 continue;
132 }
133
134 struct buddy_page *this = buddy_page_for_addr(address: addr);
135 if (domain_arena_push(arena: current_arena, page: this)) /* Pushed it onto arena */
136 continue;
137
138 /* Arena was full. Let's move onto the next one */
139 current_arena = find_non_full_arena(domain, current_arena_idx: &current_arena_idx);
140 if (!current_arena) {
141 free_from_buddy_internal(target: domain, address: addr, page_count);
142 } else {
143 domain_arena_push(arena: current_arena, page: this);
144 }
145 }
146}
147
148/* Flushing our free queue goes as follows:
149 *
150 * First, we figure out how many elements we should AT LEAST
151 * free. We free until that is met, or if we have
152 * freed everything in the freequeue.
153 *
154 * done = freed_minimum || freequeue_empty
155 *
156 * As we flush the freequeue, we set a target arena to fill.
157 *
158 * If we are flushing single pages, we try and enqueue onto
159 * this arena. If the arena is full, then we move onto the
160 * next arena. If all arenas are full, then we actually
161 * start flushing to the main buddy.
162 *
163 * For frees of more than one page, we don't bother with
164 * the arenas, and we just flush to the main buddy.
165 */
166void domain_flush_free_queue(struct domain_buddy *domain,
167 struct domain_free_queue *queue) {
168 if (is_free_in_progress(fq: queue))
169 return;
170
171 mark_free_in_progress(fq: queue, true);
172 size_t minimum_to_free = compute_min_elements_to_free(domain, queue);
173
174 flush_free_queue_internal(domain, queue, minimum_to_free);
175
176 mark_free_in_progress(fq: queue, false);
177}
178
179void domain_free(paddr_t address, size_t page_count) {
180 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
181
182 struct domain_buddy *local = domain_buddy_on_this_core();
183 struct domain_buddy *target = domain_buddy_for_addr(addr: address);
184 struct domain_free_queue *free_queue = domain_free_queue_on_this_core();
185
186 domain_stat_free(d: target);
187
188 if (local == target) {
189 free_from_local_domain_buddy(local: target, address, page_count);
190 } else {
191 free_from_remote_domain_buddy(remote: target, address, page_count);
192 }
193
194 domain_enqueue_flush_worker(worker: &local->worker);
195 domain_flush_free_queue(domain: local, queue: free_queue);
196
197 irql_lower(old_level: irql);
198}
199
200void domain_flush_thread(void *arg) {
201 struct domain_flush_worker *worker = &domain_buddy_on_this_core()->worker;
202 while (!worker->stop) {
203 semaphore_wait(s: &worker->sema);
204 struct domain_free_queue *fq = worker->domain->free_queue;
205 domain_flush_free_queue(domain: worker->domain, queue: fq);
206 atomic_store(&worker->enqueued, false);
207 }
208}
209
210void domain_enqueue_flush_worker(struct domain_flush_worker *worker) {
211 bool already = atomic_exchange(&worker->enqueued, true);
212 if (!already)
213 semaphore_post(s: &worker->sema);
214}
215