1#include <math/align.h>
2#include <math/min_max.h>
3#include <smp/domain.h>
4
5#include "internal.h"
6
7static bool try_push_page_onto_arena(struct domain_arena *arena,
8 paddr_t address) {
9 struct buddy_page *buddy = buddy_page_for_addr(address);
10 return domain_arena_push(arena, page: buddy);
11}
12
13static bool try_push_page_onto_domain_arenas(struct domain_buddy *domain,
14 paddr_t address) {
15 struct domain_arena *arena;
16 struct buddy_page *this_page = buddy_page_for_addr(address);
17
18 domain_for_each_arena(arena, domain) {
19 if (domain_arena_push(arena, page: this_page))
20 return true;
21 }
22
23 return false;
24}
25
26/* First we try and add to our arena cache. If that fails,
27 * we try the next one, until an arena cache is able to
28 * hold the freed page. If none of these succeed, we give up and just free it */
29static void free_from_local_domain_buddy(struct domain_buddy *local,
30 paddr_t address, size_t page_count) {
31 if (page_count > 1)
32 return free_from_buddy_internal(target: local, address, page_count);
33
34 struct domain_arena *local_arena = domain_arena_on_this_core();
35
36 /* Try local core first */
37 if (try_push_page_onto_arena(arena: local_arena, address))
38 return;
39
40 /* Try putting the page on other cores */
41 if (try_push_page_onto_domain_arenas(domain: local, address))
42 return;
43
44 /* No success? Let's flush it from the buddy */
45 free_from_buddy_internal(target: local, address, page_count);
46}
47
48/* First, we try and enqueue it onto the remote freequeue.
49 *
50 * If this fails, and we have a multi-page free, then we flush it to
51 * their buddy. If this fails, and we have a single-page free, then
52 * we first try to push the page onto the remote arenas.
53 *
54 * If that fails, (on single-page frees), then we flush it to their buddy
55 */
56static void free_from_remote_domain_buddy(struct domain_buddy *remote,
57 paddr_t address, size_t page_count) {
58 struct domain_free_queue *remote_freequeue = remote->free_queue;
59
60 if (domain_free_queue_enqueue(fq: remote_freequeue, addr: address, pages: page_count))
61 return;
62
63 if (page_count > 1)
64 return free_from_buddy_internal(target: remote, address, page_count);
65
66 if (try_push_page_onto_domain_arenas(domain: remote, address))
67 return;
68
69 free_from_buddy_internal(target: remote, address, page_count);
70}
71
72static inline struct domain_arena *
73domain_first_arena(struct domain_buddy *domain) {
74 return domain->arenas[0];
75}
76
77static struct domain_arena *get_next_domain_arena(struct domain_buddy *domain,
78 size_t *current_arena_idx) {
79 if (++*current_arena_idx < domain->core_count)
80 return domain->arenas[*current_arena_idx];
81
82 /* Nope, let's flush to the buddy */
83 return NULL;
84}
85
86static struct domain_arena *find_non_full_arena(struct domain_buddy *domain,
87 size_t *current_arena_idx) {
88 while (true) {
89 struct domain_arena *ret =
90 get_next_domain_arena(domain, current_arena_idx);
91 if (!ret)
92 return NULL;
93
94 if (atomic_load(&ret->num_pages) < ret->capacity)
95 return ret;
96 }
97}
98
99static size_t compute_min_elements_to_free(struct domain_buddy *domain,
100 struct domain_free_queue *queue) {
101
102 size_t total_slots_available = 0;
103 struct domain_arena *curr;
104
105 domain_for_each_arena(curr, domain) {
106 total_slots_available += curr->capacity - atomic_load(&curr->num_pages);
107 }
108
109 size_t target = atomic_load(&queue->num_elements) / 2;
110 size_t minimum = 1;
111 target = MIN(target, total_slots_available);
112 return MAX(target, minimum);
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 cc_ignore(arg);
202 struct domain_flush_worker *worker = &domain_buddy_on_this_core()->worker;
203 while (!worker->stop) {
204 semaphore_wait(s: &worker->sema);
205 struct domain_free_queue *fq = worker->domain->free_queue;
206 domain_flush_free_queue(domain: worker->domain, queue: fq);
207 atomic_store(&worker->enqueued, false);
208 }
209}
210
211void domain_enqueue_flush_worker(struct domain_flush_worker *worker) {
212 bool already = atomic_exchange(&worker->enqueued, true);
213 if (!already)
214 semaphore_post(s: &worker->sema);
215}
216