1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12
13 #include <chcore/memory.h>
14 #include <chcore/container/rbtree_plus.h>
15 #include <chcore/defs.h>
16 #include <chcore/syscall.h>
17 #include <chcore/bug.h>
18 #include <errno.h>
19 #include <pthread.h>
20 #include <assert.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23
24 #define MEM_AUTO_ALLOC_REGION (0x3000UL << (4 * sizeof(long)))
25 #define MEM_AUTO_ALLOC_REGION_SIZE (0x1000UL << (4 * sizeof(long)))
26
27 /**
28 * @brief This struct represents a continuous virtual address range
29 * [start, start + len) in the process's address space allocated by this module.
30 * And all ranges managed by this module are organized into an rbtree plus
31 * to provide efficent alloc/free operations.
32 */
33 struct user_vmr {
34 struct rbp_node node;
35 vaddr_t start;
36 vaddr_t len;
37 };
38
39 /**
40 * @brief This struct is used to control virtual address region allocation for
41 * a userspace process. By default, the total virtual address range managed by
42 * this struct is [MEM_AUTO_ALLOC_REGION, MEM_AUTO_ALLOC_REGION +
43 * MEM_AUTO_ALLOC_REGION_SIZE).
44 *
45 * In ChCore, the usage of virtual address space of a process is controlled by
46 * the process itself, and we provide chcore_alloc/free_vaddr in libc to help
47 * userspace process to allocate/free non-overlapped continuous virtual address
48 * regions. And some of our syscall implementation rely on these interfaces,
49 * e.g. mmap. Users can implement their own allocation strategy of course.
50 */
51 struct user_mm_struct {
52 pthread_spinlock_t mu;
53 struct rbtree_plus user_vmr_tree;
54 /**
55 * The last known virtual address which is the start address of
56 * a free virtual address region.
57 */
58 vaddr_t free_addr_cache;
59 vaddr_t start_addr;
60 vaddr_t end_addr;
61 };
62
cmp_user_vmr_node(const void * key,const struct rbp_node * node)63 static int cmp_user_vmr_node(const void *key, const struct rbp_node *node)
64 {
65 const struct user_vmr *rhs = container_of(node, struct user_vmr, node);
66 const struct user_vmr *lhs = key;
67
68 /**
69 * !! Attention: a user_vmr represents a left-closed right-open
70 * interval, so we have to use <= and >= to compare them.
71 */
72 if (lhs->start + lhs->len <= rhs->start) {
73 return -1;
74 } else if (lhs->start >= rhs->start + rhs->len) {
75 return 1;
76 } else {
77 return 0;
78 }
79 }
80
less_vmr_node(const struct rbp_node * lhs,const struct rbp_node * rhs)81 static bool less_vmr_node(const struct rbp_node *lhs,
82 const struct rbp_node *rhs)
83 {
84 const struct user_vmr *lhs_vmr = container_of(lhs, struct user_vmr, node);
85 const struct user_vmr *rhs_vmr = container_of(rhs, struct user_vmr, node);
86 return lhs_vmr->start + lhs_vmr->len <= rhs_vmr->start;
87 }
88
89 struct user_mm_struct user_mm;
90 pthread_once_t user_mm_once = PTHREAD_ONCE_INIT;
91
user_mm_init(void)92 void user_mm_init(void)
93 {
94 init_rbtree_plus(&user_mm.user_vmr_tree);
95 user_mm.free_addr_cache = MEM_AUTO_ALLOC_REGION;
96 pthread_spin_init(&user_mm.mu, 0);
97 user_mm.start_addr = MEM_AUTO_ALLOC_REGION;
98 user_mm.end_addr = MEM_AUTO_ALLOC_REGION + MEM_AUTO_ALLOC_REGION_SIZE;
99 }
100
101 // clang-format off
102 /**
103 * @brief Search in the virtual address range managed by user_mm_struct to find
104 * a free virtual address region with length at least ROUND_UP(size, PAGE_SIZE).
105 *
106 * Consider following virtual address range layout after several alloc/free operations:
107 * free_vaddr_cache
108 * │
109 * │
110 * │
111 * │
112 * ┌──────┬─────────────┬─────▼──────┬────────────────────┬────────┬────────────┬──────────┐
113 * │ │ │ │ │ │ │ │
114 * │ │ │ │ │ │ │ │
115 * │ A │ VMR 1 │ B │ VMR ... │ B │ VMR N │ C │
116 * │ │ │ │ │ │ │ │
117 * │ │ │ │ │ │ │ │
118 * └──────┴─────────────┴────────────┴────────────────────┴────────┴────────────┴──────────┘
119 * To allocate a non-overlapped continuous virtual address region, there are three possible cases,
120 * indicated by A,B and C in the diagram above. First, we start from free_vaddr_cache, and search
121 * towards user_mm.end_addr. It's possible for us to find an appropriate free region between two
122 * allocated regions(case B). We can also figure out that there is enough space after the last
123 * allocated region(case C). However, it's still possible that there is no such free region after
124 * free_vaddr_cache. If so, we would perform a rewind search, i.e., starting from user_mm.start_addr
125 * again, search until we meet free_vaddr_cache(case A). In the end, if we still didn't encounter
126 * a feasible free region, this allocation request cannot be satisfied and a NULL would be returned.
127 *
128 */
129 // clang-format on
chcore_alloc_vaddr(unsigned long size)130 unsigned long chcore_alloc_vaddr(unsigned long size)
131 {
132 unsigned long ret = 0, cmp;
133 struct rbp_node *node, *iter;
134 struct user_vmr *nearest_vmr, *iter_vmr, *new_vmr;
135 struct user_vmr query;
136 bool found = false;
137
138 if (!size) {
139 return ret;
140 }
141
142 pthread_once(&user_mm_once, user_mm_init);
143 pthread_spin_lock(&user_mm.mu);
144
145 size = ROUND_UP(size, PAGE_SIZE);
146
147 query.start = user_mm.free_addr_cache;
148 query.len = size;
149 node =
150 rbp_search_nearest(&user_mm.user_vmr_tree, &query, cmp_user_vmr_node);
151
152 // If there isn't any allocated user_vmr, just check it's out of bound
153 // or not. If not, allocate and insert it directly.
154 if (node == NULL) {
155 if (query.start + size > user_mm.end_addr) {
156 // out of bound
157 goto out;
158 }
159 new_vmr = malloc(sizeof(struct user_vmr));
160 new_vmr->start = query.start;
161 new_vmr->len = size;
162 user_mm.free_addr_cache += size;
163 rbp_insert(&user_mm.user_vmr_tree, &new_vmr->node, less_vmr_node);
164 ret = new_vmr->start;
165 goto out;
166 }
167
168 // start from the user_vmr nearest to [free_vaddr_cache,
169 // free_vaddr_cache + size)
170 nearest_vmr = container_of(node, struct user_vmr, node);
171 for (iter = node; iter; iter = rbp_next(&user_mm.user_vmr_tree, iter)) {
172 iter_vmr = container_of(iter, struct user_vmr, node);
173 if (cmp_user_vmr_node(&query, iter) >= 0) {
174 // go over the iter_vmr.
175 query.start = iter_vmr->start + iter_vmr->len;
176 } else {
177 // Case B
178 found = true;
179 break;
180 }
181 }
182
183 if (!found) {
184 // check area after the last user_vmr(iter)
185 if (query.start + size <= user_mm.end_addr) {
186 // Case C
187 found = true;
188 } else {
189 // rewind search
190 query.start = user_mm.start_addr;
191 rbp_for_each(&user_mm.user_vmr_tree, iter)
192 {
193 iter_vmr = container_of(iter, struct user_vmr, node);
194 // rewind done, not found
195 if (iter_vmr == nearest_vmr) {
196 break;
197 }
198 if (cmp_user_vmr_node(&query, iter) >= 0) {
199 // go over the iter_vmr.
200 query.start = iter_vmr->start + iter_vmr->len;
201 } else {
202 // Case A
203 found = true;
204 break;
205 }
206 }
207 }
208 }
209
210 if (!found) {
211 goto out;
212 } else {
213 new_vmr = malloc(sizeof(struct user_vmr));
214 new_vmr->start = query.start;
215 new_vmr->len = size;
216 rbp_insert(&user_mm.user_vmr_tree, &new_vmr->node, less_vmr_node);
217 ret = new_vmr->start;
218 user_mm.free_addr_cache = ret + size;
219 }
220
221 out:
222 pthread_spin_unlock(&user_mm.mu);
223 return ret;
224 }
225
chcore_free_vaddr(unsigned long vaddr,unsigned long size)226 void chcore_free_vaddr(unsigned long vaddr, unsigned long size)
227 {
228 struct rbp_node *iter, *tmp;
229 struct user_vmr *vmr;
230 struct user_vmr query;
231 int updated = 0;
232
233 pthread_once(&user_mm_once, user_mm_init);
234 pthread_spin_lock(&user_mm.mu);
235
236 query.start = vaddr;
237 query.len = size;
238
239 rbp_for_each_safe(&user_mm.user_vmr_tree, iter, tmp)
240 {
241 vmr = container_of(iter, struct user_vmr, node);
242 if (query.start <= vmr->start
243 && query.start + query.len >= vmr->start + vmr->len) {
244 if (!updated) {
245 user_mm.free_addr_cache = vmr->start;
246 updated = 1;
247 }
248 rbp_erase(&user_mm.user_vmr_tree, iter);
249 free(vmr);
250 } else if (cmp_user_vmr_node(&query, iter) == 0) {
251 continue;
252 }
253 }
254
255 pthread_spin_unlock(&user_mm.mu);
256 }
257
chcore_auto_map_pmo(cap_t pmo,unsigned long size,unsigned long perm)258 void *chcore_auto_map_pmo(cap_t pmo, unsigned long size, unsigned long perm)
259 {
260 unsigned long vaddr = chcore_alloc_vaddr(size);
261 if (vaddr == 0) {
262 errno = EINVAL;
263 return NULL;
264 }
265 int ret = usys_map_pmo(SELF_CAP, pmo, vaddr, perm);
266 if (ret != 0) {
267 chcore_free_vaddr(vaddr, size);
268 errno = -ret;
269 return NULL;
270 }
271 return (void *)vaddr;
272 }
273
chcore_auto_unmap_pmo(cap_t pmo,unsigned long vaddr,unsigned long size)274 void chcore_auto_unmap_pmo(cap_t pmo, unsigned long vaddr, unsigned long size)
275 {
276 usys_unmap_pmo(SELF_CAP, pmo, vaddr);
277 chcore_free_vaddr(vaddr, size);
278 }
279
chcore_alloc_dma_mem(unsigned long size,struct chcore_dma_handle * dma_handle)280 void *chcore_alloc_dma_mem(unsigned long size,
281 struct chcore_dma_handle *dma_handle)
282 {
283 int ret;
284
285 if (dma_handle == NULL) {
286 return NULL;
287 }
288
289 dma_handle->size = size;
290
291 dma_handle->pmo = usys_create_pmo(size, PMO_DATA_NOCACHE);
292 if (dma_handle->pmo < 0) {
293 return NULL;
294 }
295
296 void *res = chcore_auto_map_pmo(dma_handle->pmo, size, VM_READ | VM_WRITE);
297 if (res == NULL) {
298 return NULL;
299 }
300
301 ret = usys_get_phys_addr(res, &dma_handle->paddr);
302 if (ret != 0) {
303 return NULL;
304 }
305 dma_handle->vaddr = (unsigned long)res;
306
307 return res;
308 }
309
chcore_free_dma_mem(struct chcore_dma_handle * dma_handle)310 void chcore_free_dma_mem(struct chcore_dma_handle *dma_handle)
311 {
312 if (dma_handle == NULL || dma_handle->pmo < 0 || dma_handle->vaddr == 0) {
313 BUG("dma_handle is invalid");
314 }
315
316 chcore_auto_unmap_pmo(dma_handle->pmo, dma_handle->vaddr, dma_handle->size);
317 usys_revoke_cap(dma_handle->pmo, false);
318
319 // usys_unmap_pmo(SELF_CAP, dma_handle->pmo, dma_handle->vaddr);
320 }
321