Commit | Line | Data |
---|---|---|
800f879a AT |
1 | /* |
2 | * Copyright 2010-2017 Intel Corporation. | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or modify | |
5 | * it under the terms of the GNU General Public License, version 2, | |
6 | * as published by the Free Software Foundation. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
11 | * General Public License for more details. | |
12 | * | |
13 | * Disclaimer: The codes contained in these modules may be specific to | |
14 | * the Intel Software Development Platform codenamed Knights Ferry, | |
15 | * and the Intel product codenamed Knights Corner, and are not backward | |
16 | * compatible with other Intel products. Additionally, Intel will NOT | |
17 | * support the codes or instruction set in future products. | |
18 | * | |
19 | * Intel offers no warranty of any kind regarding the code. This code is | |
20 | * licensed on an "AS IS" basis and Intel is not obligated to provide | |
21 | * any support, assistance, installation, training, or other services | |
22 | * of any kind. Intel is also not obligated to provide any updates, | |
23 | * enhancements or extensions. Intel specifically disclaims any warranty | |
24 | * of merchantability, non-infringement, fitness for any particular | |
25 | * purpose, and any other warranty. | |
26 | * | |
27 | * Further, Intel disclaims all liability of any kind, including but | |
28 | * not limited to liability for infringement of any proprietary rights, | |
29 | * relating to the use of the code, even if Intel is notified of the | |
30 | * possibility of such liability. Except as expressly stated in an Intel | |
31 | * license agreement provided with this code and agreed upon with Intel, | |
32 | * no license, express or implied, by estoppel or otherwise, to any | |
33 | * intellectual property rights is granted herein. | |
34 | */ | |
35 | ||
36 | /* ************************************************************************* *\ | |
37 | generate a virtual address for a given size | |
38 | \* ************************************************************************* */ | |
39 | #include "mic/micscif.h" | |
40 | ||
41 | /* ************************************************************************* *\ | |
42 | FUNCTION: VaGenAddress::Initialize | |
43 | ||
44 | DESCRIPTION: Initialize VaGenAddress to point to one node of size = range | |
45 | \* ************************************************************************* */ | |
46 | static int | |
47 | va_gen_init_internal(struct va_gen_addr *addr, uint64_t range) | |
48 | { | |
49 | struct va_node *node; | |
50 | int err; | |
51 | ||
52 | va_node_init(&addr->allocator); | |
53 | if ((err = va_node_alloc(&addr->allocator, &addr->hole_list)) < 0) | |
54 | goto init_err; | |
55 | if (va_node_is_valid(addr->hole_list)) { | |
56 | node = va_node_get(&addr->allocator, addr->hole_list); | |
57 | node->next = invalid_va_node_index; | |
58 | node->base = 0; | |
59 | node->range = range; | |
60 | } | |
61 | addr->claims_list = invalid_va_node_index; | |
62 | init_err: | |
63 | return err; | |
64 | } | |
65 | ||
66 | /* ************************************************************************* *\ | |
67 | FUNCTION: VaGenAddress::Alloc | |
68 | Allocate virtual memory by searching through free virtual memory | |
69 | linked list for first range >= desired range. | |
70 | ||
71 | Note: Free list is sorted by base, we are searching for range. | |
72 | ||
73 | Return: Offset to allocated virtual address if successful (in pages). | |
74 | INVALID_VA_PAGE_INDEX if failed | |
75 | \* ************************************************************************* */ | |
76 | static uint64_t | |
77 | va_gen_alloc_internal(struct va_gen_addr *addr, uint64_t range) | |
78 | { | |
79 | //========================================================================== | |
80 | // Search for a sufficiently large memory hole (first-fit). | |
81 | //-------------------------------------------------------------------------- | |
82 | ||
83 | // Search for first available hole of sufficient size. | |
84 | uint32_t index = addr->hole_list; | |
85 | struct va_node *pFind; | |
86 | // Used to handle case of an exact range match. | |
87 | struct va_node *pPrev = 0; | |
88 | uint64_t base; | |
89 | ||
90 | if (0 == range || !va_node_is_valid(addr->hole_list)) | |
91 | return INVALID_VA_PAGE_INDEX; | |
92 | ||
93 | pFind = va_node_get(&addr->allocator, index); | |
94 | ||
95 | for ( ; ; ) { | |
96 | if (pFind->range >= range) | |
97 | break; | |
98 | else { | |
99 | index = pFind->next; | |
100 | // No hole sufficiently large. | |
101 | if (!va_node_is_valid(index)) | |
102 | return INVALID_VA_PAGE_INDEX; | |
103 | pPrev = pFind; | |
104 | pFind = va_node_get(&addr->allocator, index); | |
105 | } | |
106 | } | |
107 | ||
108 | // Found an adequate hole. Get its base. | |
109 | base = pFind->base; | |
110 | ||
111 | //============================================================================ | |
112 | // Uncommon case: pFind->range == in_range | |
113 | // Remove node from the hole list when exact fit. Note, could leave the | |
114 | // hole list empty. | |
115 | //---------------------------------------------------------------------------- | |
116 | ||
117 | if (pFind->range == range) { | |
118 | // first node? | |
119 | if (addr->hole_list == index) | |
120 | addr->hole_list = pFind->next; | |
121 | else { | |
122 | BUG_ON(!pPrev); | |
123 | pPrev->next = pFind->next; | |
124 | } | |
125 | va_node_free(&addr->allocator, index); | |
126 | return base; | |
127 | } | |
128 | ||
129 | //================================================================================ | |
130 | // Shrink an existing node that is too large. | |
131 | //-------------------------------------------------------------------------------- | |
132 | ||
133 | else { | |
134 | pFind->base += range; | |
135 | pFind->range -= range; | |
136 | } | |
137 | ||
138 | return base; | |
139 | } | |
140 | ||
141 | /* ************************************************************************* *\ | |
142 | FUNCTION: VaGenAddress::FreeClaim | |
143 | ||
144 | DESCRIPTION: | |
145 | Removes claimed range from the claims list. | |
146 | \* ************************************************************************* */ | |
147 | static void | |
148 | va_gen_free_claim(struct va_gen_addr *addr, uint64_t base, uint64_t range) | |
149 | { | |
150 | struct va_node *pNode = 0; | |
151 | struct va_node *pPrev = 0; | |
152 | uint32_t index, new_index; | |
153 | struct va_node *pNewNode; | |
154 | int err; | |
155 | ||
156 | if (0 == range) | |
157 | return; | |
158 | ||
159 | for (index = addr->claims_list; va_node_is_valid(index); index = pNode->next) { | |
160 | pNode = va_node_get(&addr->allocator, index); | |
161 | ||
162 | if (pNode->base <= base && pNode->base + pNode->range >= base + range) { | |
163 | if (pNode->base == base) { | |
164 | pNode->base += range; | |
165 | pNode->range -= range; | |
166 | if (0 == pNode->range) { | |
167 | if (pPrev) | |
168 | pPrev->next = pNode->next; | |
169 | else | |
170 | addr->claims_list = pNode->next; | |
171 | va_node_free(&addr->allocator, index); | |
172 | } | |
173 | } else if (pNode->base + pNode->range == base + range) { | |
174 | pNode->range -= range; | |
175 | } else { | |
176 | err = va_node_alloc(&addr->allocator, &new_index); | |
177 | BUG_ON(err < 0); | |
178 | pNewNode = va_node_get(&addr->allocator, new_index); | |
179 | pNewNode->base = base + range; | |
180 | pNewNode->range = pNode->range - pNewNode->base; | |
181 | pNewNode->next = pNode->next; | |
182 | pNode->range = base - pNode->base; | |
183 | pNode->next = new_index; | |
184 | } | |
185 | return; | |
186 | } | |
187 | if (pNode->base > base + range) { | |
188 | pr_debug("Freed claim not found in the list\n"); | |
189 | return; | |
190 | } | |
191 | ||
192 | if ((pNode->base < base) ? | |
193 | (pNode->base + pNode->range > base) : | |
194 | (base + range > pNode->base)) { | |
195 | pr_debug("Freed claim partially overlaps the list\n"); | |
196 | return; | |
197 | } | |
198 | pPrev = pNode; | |
199 | } | |
200 | } | |
201 | ||
202 | /* ************************************************************************* *\ | |
203 | FUNCTION: VaGenAddress::InsertAndCoalesce | |
204 | ||
205 | DESCRIPTION: | |
206 | O(n) search through free list sorted by base | |
207 | should average O(n/2), and free list should be much less than the # allocated | |
208 | coalesce with node before/after if possible | |
209 | 3 possible outcomes: | |
210 | 1. freed node is inserted into list (0 deallocated) | |
211 | 2. freed node range coalesced with existing node, | |
212 | so freed node can be deallocated (1 deallocated) | |
213 | 3. freed node + another node are coalesced + deallocated | |
214 | (2 deallocated) | |
215 | Fails if there is full or partial overlap between inserted | |
216 | range and ranges in the list | |
217 | ||
218 | returns false if insert failed | |
219 | \* ************************************************************************* */ | |
220 | static int | |
221 | va_gen_insert_and_coalesce(struct va_node_allocator *allocator, uint32_t *list, | |
222 | uint64_t base, uint64_t range) | |
223 | { | |
224 | // search through free list, insert ordered | |
225 | // also check for coalesce | |
226 | uint32_t findPtr = *list; | |
227 | uint32_t prev = *list; | |
228 | uint64_t end_range = base + range; | |
229 | uint32_t nextPtr, ptr; | |
230 | struct va_node *nextNode, *node; | |
231 | int err; | |
232 | ||
233 | while (va_node_is_valid(findPtr)) { | |
234 | struct va_node *find = va_node_get(allocator, findPtr); | |
235 | // overlap? | |
236 | // A.start < B.start && A.end > B.start A-B==A-B A-B==B-A otherwise A-A B-B | |
237 | // B.start < A.start && B.end > A.start B-A==B-A B-A==A-B otherwise B-B A-A | |
238 | // => | |
239 | // A.start < B.start ? A.end > B.start : B.end > A.start | |
240 | ||
241 | if ((find->base < base) ? | |
242 | (find->base + find->range > base) : | |
243 | (end_range > find->base)) { | |
244 | return -1; | |
245 | } | |
246 | //---------------------------------------------------------- | |
247 | // coalesce? 2 possibilities: | |
248 | // 1. (pFind->base + pFind->range) == current.base | |
249 | // coalesce, check next node base = endrange, | |
250 | // coalesce with next if possible, deallocate next, exit | |
251 | // 2. end_range == pFind->base | |
252 | // coalesce, exit | |
253 | if (end_range == find->base) { | |
254 | // pr_debug("Coalesce base %lld before %lld\n", base, find->base); | |
255 | find->base = base; | |
256 | find->range += range; | |
257 | return 0; | |
258 | } else if ((find->base + find->range) == base) { | |
259 | // pr_debug("Coalesce base %lld after %lld\n", base, find->base); | |
260 | // leave the base unchanged | |
261 | find->range += range; | |
262 | // check the next node to see if it coalesces too | |
263 | nextPtr = find->next; | |
264 | if (va_node_is_valid(nextPtr)) { | |
265 | nextNode = va_node_get(allocator, nextPtr); | |
266 | // end_range is the same after prior coalesce | |
267 | if (nextNode->base == end_range) { | |
268 | // pr_debug("Double Coalesce index %d before %d\n", findPtr, nextPtr); | |
269 | find->range += nextNode->range; | |
270 | find->next = nextNode->next; | |
271 | va_node_free(allocator, nextPtr); | |
272 | } | |
273 | } | |
274 | return 0; | |
275 | } | |
276 | // end coalesce | |
277 | ||
278 | //---------------------------------------------------------- | |
279 | // insert if found a node at a greater address | |
280 | else if (find->base > end_range) | |
281 | // exit loop, insert node | |
282 | break; | |
283 | // nothing found yet, next index | |
284 | prev = findPtr; | |
285 | findPtr = find->next; | |
286 | } | |
287 | ||
288 | //---------------------------------------------------------- | |
289 | // insert or append if node | |
290 | // could be at the end or empty free list (find index = INVALID) | |
291 | // or, next node has larger base | |
292 | //---------------------------------------------------------- | |
293 | err = va_node_alloc(allocator, &ptr); | |
294 | BUG_ON(err < 0); | |
295 | if (!va_node_is_valid(ptr)) { | |
296 | printk(KERN_ERR "FAILED to add hole! base = %lld, range = %lld\n", base, range); | |
297 | return 0; | |
298 | } | |
299 | node = va_node_get(allocator, ptr); | |
300 | node->base = base; | |
301 | node->range = range; | |
302 | node->next = findPtr; | |
303 | // First node or empty list (Alloc() can empty the list) | |
304 | if (findPtr == *list) | |
305 | // pr_debug("List now starts with %d\n", ptr); | |
306 | *list = ptr; | |
307 | else { // reached the end of the list or insertion | |
308 | BUG_ON(!va_node_is_valid(prev)); | |
309 | // pr_debug("Append index %d after %d\n", ptr, prev); | |
310 | (va_node_get(allocator, prev))->next = ptr; | |
311 | } | |
312 | return 0; | |
313 | } | |
314 | ||
315 | /* ************************************************************************* *\ | |
316 | FUNCTION: VaGenAddress::Free | |
317 | ||
318 | DESCRIPTION: | |
319 | Frees allocated Virtual Address. Inserts freed range in the list of holes | |
320 | (available virtual addresses) | |
321 | \* ************************************************************************* */ | |
322 | static void | |
323 | va_gen_free_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range) | |
324 | { | |
325 | int result = va_gen_insert_and_coalesce(&addr->allocator, &addr->hole_list, base, range); | |
326 | BUG_ON(result < 0); | |
327 | } | |
328 | ||
329 | /* ************************************************************************* *\ | |
330 | FUNCTION: VaGenAddress::Alloc | |
331 | Allocate virtual memory space. | |
332 | ||
333 | Note: "Quick and dirty" implementation of aligned Alloc on top of | |
334 | non-aligned Alloc. | |
335 | ||
336 | Return: Offset to allocated virtual address if successful (in pages). | |
337 | INVALID_VA_PAGE_INDEX if failed | |
338 | \* ************************************************************************* */ | |
339 | static uint64_t | |
340 | va_gen_alloc_aligned(struct va_gen_addr *addr, uint64_t range, uint32_t unit_align) | |
341 | { | |
342 | uint64_t base_address = va_gen_alloc_internal(addr, range + unit_align - 1); | |
343 | uint64_t aligned_base = base_address; | |
344 | if (0 == range || 0 == unit_align) | |
345 | return INVALID_VA_PAGE_INDEX; | |
346 | //BUG_ON(IsPowerOfTwo(in_unitAlign)); | |
347 | ||
348 | if (unit_align == 1 || base_address == INVALID_VA_PAGE_INDEX) | |
349 | return base_address; | |
350 | ||
351 | if (aligned_base > base_address) | |
352 | va_gen_free_internal(addr, base_address, aligned_base - base_address); | |
353 | ||
354 | if (aligned_base + range < base_address + unit_align - 1) | |
355 | va_gen_free_internal(addr, aligned_base + range, | |
356 | base_address + unit_align - 1 - aligned_base - range); | |
357 | return aligned_base; | |
358 | } | |
359 | ||
360 | /* ************************************************************************* *\ | |
361 | FUNCTION: VaGenAddress::Claim | |
362 | ||
363 | DESCRIPTION: | |
364 | Claims a SVAS range. Checks if range was claimed before; if not, records | |
365 | the claim in the claims list | |
366 | ||
367 | returns false if claim failed | |
368 | \* ************************************************************************* */ | |
369 | static int | |
370 | va_gen_claim_internal(struct va_gen_addr *addr, uint64_t base, uint64_t range) | |
371 | { | |
372 | return va_gen_insert_and_coalesce(&addr->allocator, &addr->claims_list, base, range); | |
373 | } | |
374 | ||
375 | /* ************************************************************************* *\ | |
376 | FUNCTION: VaGenAddressMutex::Alloc | |
377 | Allocate virtual memory space. | |
378 | ||
379 | Note: Wrapper for unit-testable address generator to add critical | |
380 | section and convert bytes to pages. | |
381 | Note: Free() selects between Free[Alloc] and FreeClaim based on | |
382 | the address range of the freed address. | |
383 | ||
384 | Return: Allocated virtual address if successful (in bytes) | |
385 | INVALID_VA_GEN_ADDRESS if failed | |
386 | \* ************************************************************************* */ | |
387 | uint64_t | |
388 | va_gen_alloc(struct va_gen_addr *addr, uint64_t num_bytes, uint32_t align_bytes) | |
389 | { | |
390 | // Convert input bytes to pages which is our unit for the address generator. | |
391 | uint64_t num_pages = (uint64_t)(((PAGE_SIZE - 1) + num_bytes) / PAGE_SIZE); | |
392 | uint64_t align_pages = align_bytes / PAGE_SIZE; | |
393 | uint64_t va_page_index, ret; | |
394 | ||
395 | if (align_bytes < PAGE_SIZE) { | |
396 | ret = INVALID_VA_GEN_ADDRESS; | |
397 | WARN_ON(1); | |
398 | goto done; | |
399 | } | |
400 | ||
401 | if (num_bytes > (0xffffffffULL * PAGE_SIZE)) { | |
402 | ret = INVALID_VA_GEN_ADDRESS; | |
403 | WARN_ON(1); | |
404 | goto done; | |
405 | } | |
406 | va_page_index = va_gen_alloc_aligned(addr, num_pages, (uint32_t)(align_pages % 0xffffffff) ); | |
407 | ||
408 | if (va_page_index == INVALID_VA_PAGE_INDEX) | |
409 | return INVALID_VA_GEN_ADDRESS; | |
410 | ||
411 | // Convert page number to virtual address, adding base. | |
412 | ret = va_page_index << PAGE_SHIFT; | |
413 | ret += addr->base; | |
414 | done: | |
415 | return ret; | |
416 | } | |
417 | ||
418 | // Claims ownership of a memory region | |
419 | uint64_t | |
420 | va_gen_claim(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes) | |
421 | { | |
422 | uint64_t va, num_pages; | |
423 | int result; | |
424 | ||
425 | if (address + num_bytes > addr->base) | |
426 | address = INVALID_VA_GEN_ADDRESS; | |
427 | else if (address & (PAGE_SIZE - 1)) | |
428 | // address not aligned | |
429 | address = INVALID_VA_GEN_ADDRESS; | |
430 | else { | |
431 | va = (uint64_t)(address >> PAGE_SHIFT); | |
432 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); | |
433 | // convert input bytes to pages, our unit for the address generator | |
434 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); | |
435 | if ((result = va_gen_claim_internal(addr, va, num_pages)) < 0) | |
436 | address = INVALID_VA_GEN_ADDRESS; | |
437 | } | |
438 | return address; | |
439 | } | |
440 | ||
441 | // frees the address range so the pages may be re-assigned | |
442 | void | |
443 | va_gen_free(struct va_gen_addr *addr, uint64_t address, uint64_t num_bytes) | |
444 | { | |
445 | uint64_t va, num_pages; | |
446 | ||
447 | if (address >= addr->base) { | |
448 | // convert virtual address to page number, subtracting base | |
449 | address -= addr->base; | |
450 | va = (uint64_t)(address >> PAGE_SHIFT); | |
451 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); | |
452 | // convert input bytes to pages, our unit for the address generator | |
453 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); | |
454 | va_gen_free_internal(addr, va, num_pages); | |
455 | } else { | |
456 | va = (uint64_t)(address >> PAGE_SHIFT); | |
457 | // pr_debug("%s %d (%#llx,%llx)\n", __func__, __LINE__, va, num_bytes); | |
458 | // convert input bytes to pages, our unit for the address generator | |
459 | num_pages = (uint64_t)(((PAGE_SIZE-1) + num_bytes) / PAGE_SIZE); | |
460 | va_gen_free_claim(addr, va, num_pages); | |
461 | } | |
462 | } | |
463 | ||
464 | // base and range in bytes, though internal va generator works in pages | |
465 | int | |
466 | va_gen_init(struct va_gen_addr *addr, uint64_t base, uint64_t range) | |
467 | { | |
468 | uint64_t rangeInPages = (uint64_t)(range >> PAGE_SHIFT); | |
469 | int ret; | |
470 | ||
471 | if (!(ret = va_gen_init_internal(addr, rangeInPages))) | |
472 | addr->base = base; | |
473 | return ret; | |
474 | } | |
475 | ||
476 | void | |
477 | va_gen_destroy(struct va_gen_addr *addr) | |
478 | { | |
479 | va_node_destroy(&addr->allocator); | |
480 | } |