Rev 2071 | Rev 2089 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2071 | Rev 2087 | ||
---|---|---|---|
Line 91... | Line 91... | ||
91 | /** |
91 | /** |
92 | * Slab for as_t objects. |
92 | * Slab for as_t objects. |
93 | */ |
93 | */ |
94 | static slab_cache_t *as_slab; |
94 | static slab_cache_t *as_slab; |
95 | 95 | ||
- | 96 | /** |
|
96 | /** This lock protects inactive_as_with_asid_head list. It must be acquired before as_t mutex. */ |
97 | * This lock protects inactive_as_with_asid_head list. It must be acquired |
- | 98 | * before as_t mutex. |
|
- | 99 | */ |
|
97 | SPINLOCK_INITIALIZE(inactive_as_with_asid_lock); |
100 | SPINLOCK_INITIALIZE(inactive_as_with_asid_lock); |
98 | 101 | ||
99 | /** |
102 | /** |
100 | * This list contains address spaces that are not active on any |
103 | * This list contains address spaces that are not active on any |
101 | * processor and that have valid ASID. |
104 | * processor and that have valid ASID. |
Line 105... | Line 108... | ||
105 | /** Kernel address space. */ |
108 | /** Kernel address space. */ |
106 | as_t *AS_KERNEL = NULL; |
109 | as_t *AS_KERNEL = NULL; |
107 | 110 | ||
108 | static int area_flags_to_page_flags(int aflags); |
111 | static int area_flags_to_page_flags(int aflags); |
109 | static as_area_t *find_area_and_lock(as_t *as, uintptr_t va); |
112 | static as_area_t *find_area_and_lock(as_t *as, uintptr_t va); |
110 | static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, as_area_t *avoid_area); |
113 | static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, |
- | 114 | as_area_t *avoid_area); |
|
111 | static void sh_info_remove_reference(share_info_t *sh_info); |
115 | static void sh_info_remove_reference(share_info_t *sh_info); |
112 | 116 | ||
113 | static int as_constructor(void *obj, int flags) |
117 | static int as_constructor(void *obj, int flags) |
114 | { |
118 | { |
115 | as_t *as = (as_t *) obj; |
119 | as_t *as = (as_t *) obj; |
Line 134... | Line 138... | ||
134 | void as_init(void) |
138 | void as_init(void) |
135 | { |
139 | { |
136 | as_arch_init(); |
140 | as_arch_init(); |
137 | 141 | ||
138 | as_slab = slab_cache_create("as_slab", sizeof(as_t), 0, |
142 | as_slab = slab_cache_create("as_slab", sizeof(as_t), 0, |
139 | as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED); |
143 | as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED); |
140 | 144 | ||
141 | AS_KERNEL = as_create(FLAG_AS_KERNEL); |
145 | AS_KERNEL = as_create(FLAG_AS_KERNEL); |
142 | if (!AS_KERNEL) |
146 | if (!AS_KERNEL) |
143 | panic("can't create kernel address space\n"); |
147 | panic("can't create kernel address space\n"); |
144 | 148 | ||
Line 169... | Line 173... | ||
169 | return as; |
173 | return as; |
170 | } |
174 | } |
171 | 175 | ||
172 | /** Destroy adress space. |
176 | /** Destroy adress space. |
173 | * |
177 | * |
174 | * When there are no tasks referencing this address space (i.e. its refcount is zero), |
178 | * When there are no tasks referencing this address space (i.e. its refcount is |
175 | * the address space can be destroyed. |
179 | * zero), the address space can be destroyed. |
176 | */ |
180 | */ |
177 | void as_destroy(as_t *as) |
181 | void as_destroy(as_t *as) |
178 | { |
182 | { |
179 | ipl_t ipl; |
183 | ipl_t ipl; |
180 | bool cond; |
184 | bool cond; |
Line 201... | Line 205... | ||
201 | */ |
205 | */ |
202 | for (cond = true; cond; ) { |
206 | for (cond = true; cond; ) { |
203 | btree_node_t *node; |
207 | btree_node_t *node; |
204 | 208 | ||
205 | ASSERT(!list_empty(&as->as_area_btree.leaf_head)); |
209 | ASSERT(!list_empty(&as->as_area_btree.leaf_head)); |
206 | node = list_get_instance(as->as_area_btree.leaf_head.next, btree_node_t, leaf_link); |
210 | node = list_get_instance(as->as_area_btree.leaf_head.next, |
- | 211 | btree_node_t, leaf_link); |
|
207 | 212 | ||
208 | if ((cond = node->keys)) { |
213 | if ((cond = node->keys)) { |
209 | as_area_destroy(as, node->key[0]); |
214 | as_area_destroy(as, node->key[0]); |
210 | } |
215 | } |
211 | } |
216 | } |
Line 270... | Line 275... | ||
270 | a->sh_info = NULL; |
275 | a->sh_info = NULL; |
271 | a->backend = backend; |
276 | a->backend = backend; |
272 | if (backend_data) |
277 | if (backend_data) |
273 | a->backend_data = *backend_data; |
278 | a->backend_data = *backend_data; |
274 | else |
279 | else |
275 | memsetb((uintptr_t) &a->backend_data, sizeof(a->backend_data), 0); |
280 | memsetb((uintptr_t) &a->backend_data, sizeof(a->backend_data), |
- | 281 | 0); |
|
276 | 282 | ||
277 | btree_create(&a->used_space); |
283 | btree_create(&a->used_space); |
278 | 284 | ||
279 | btree_insert(&as->as_area_btree, base, (void *) a, NULL); |
285 | btree_insert(&as->as_area_btree, base, (void *) a, NULL); |
280 | 286 | ||
Line 285... | Line 291... | ||
285 | } |
291 | } |
286 | 292 | ||
287 | /** Find address space area and change it. |
293 | /** Find address space area and change it. |
288 | * |
294 | * |
289 | * @param as Address space. |
295 | * @param as Address space. |
290 | * @param address Virtual address belonging to the area to be changed. Must be page-aligned. |
296 | * @param address Virtual address belonging to the area to be changed. Must be |
- | 297 | * page-aligned. |
|
291 | * @param size New size of the virtual memory block starting at address. |
298 | * @param size New size of the virtual memory block starting at address. |
292 | * @param flags Flags influencing the remap operation. Currently unused. |
299 | * @param flags Flags influencing the remap operation. Currently unused. |
293 | * |
300 | * |
294 | * @return Zero on success or a value from @ref errno.h otherwise. |
301 | * @return Zero on success or a value from @ref errno.h otherwise. |
295 | */ |
302 | */ |
Line 354... | Line 361... | ||
354 | */ |
361 | */ |
355 | 362 | ||
356 | /* |
363 | /* |
357 | * Start TLB shootdown sequence. |
364 | * Start TLB shootdown sequence. |
358 | */ |
365 | */ |
359 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
366 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + |
- | 367 | pages * PAGE_SIZE, area->pages - pages); |
|
360 | 368 | ||
361 | /* |
369 | /* |
362 | * Remove frames belonging to used space starting from |
370 | * Remove frames belonging to used space starting from |
363 | * the highest addresses downwards until an overlap with |
371 | * the highest addresses downwards until an overlap with |
364 | * the resized address space area is found. Note that this |
372 | * the resized address space area is found. Note that this |
Line 367... | Line 375... | ||
367 | */ |
375 | */ |
368 | for (cond = true; cond;) { |
376 | for (cond = true; cond;) { |
369 | btree_node_t *node; |
377 | btree_node_t *node; |
370 | 378 | ||
371 | ASSERT(!list_empty(&area->used_space.leaf_head)); |
379 | ASSERT(!list_empty(&area->used_space.leaf_head)); |
- | 380 | node = |
|
372 | node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link); |
381 | list_get_instance(area->used_space.leaf_head.prev, |
- | 382 | btree_node_t, leaf_link); |
|
373 | if ((cond = (bool) node->keys)) { |
383 | if ((cond = (bool) node->keys)) { |
374 | uintptr_t b = node->key[node->keys - 1]; |
384 | uintptr_t b = node->key[node->keys - 1]; |
- | 385 | count_t c = |
|
375 | count_t c = (count_t) node->value[node->keys - 1]; |
386 | (count_t) node->value[node->keys - 1]; |
376 | int i = 0; |
387 | int i = 0; |
377 | 388 | ||
378 | if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) { |
389 | if (overlaps(b, c * PAGE_SIZE, area->base, |
- | 390 | pages*PAGE_SIZE)) { |
|
379 | 391 | ||
380 | if (b + c*PAGE_SIZE <= start_free) { |
392 | if (b + c * PAGE_SIZE <= start_free) { |
381 | /* |
393 | /* |
382 | * The whole interval fits completely |
394 | * The whole interval fits |
- | 395 | * completely in the resized |
|
383 | * in the resized address space area. |
396 | * address space area. |
384 | */ |
397 | */ |
385 | break; |
398 | break; |
386 | } |
399 | } |
387 | 400 | ||
388 | /* |
401 | /* |
389 | * Part of the interval corresponding to b and c |
402 | * Part of the interval corresponding |
390 | * overlaps with the resized address space area. |
403 | * to b and c overlaps with the resized |
- | 404 | * address space area. |
|
391 | */ |
405 | */ |
392 | 406 | ||
393 | cond = false; /* we are almost done */ |
407 | cond = false; /* we are almost done */ |
394 | i = (start_free - b) >> PAGE_WIDTH; |
408 | i = (start_free - b) >> PAGE_WIDTH; |
395 | if (!used_space_remove(area, start_free, c - i)) |
409 | if (!used_space_remove(area, start_free, |
- | 410 | c - i)) |
|
396 | panic("Could not remove used space.\n"); |
411 | panic("Could not remove used " |
- | 412 | "space.\n"); |
|
397 | } else { |
413 | } else { |
398 | /* |
414 | /* |
399 | * The interval of used space can be completely removed. |
415 | * The interval of used space can be |
- | 416 | * completely removed. |
|
400 | */ |
417 | */ |
401 | if (!used_space_remove(area, b, c)) |
418 | if (!used_space_remove(area, b, c)) |
402 | panic("Could not remove used space.\n"); |
419 | panic("Could not remove used " |
- | 420 | "space.\n"); |
|
403 | } |
421 | } |
404 | 422 | ||
405 | for (; i < c; i++) { |
423 | for (; i < c; i++) { |
406 | pte_t *pte; |
424 | pte_t *pte; |
407 | 425 | ||
408 | page_table_lock(as, false); |
426 | page_table_lock(as, false); |
409 | pte = page_mapping_find(as, b + i*PAGE_SIZE); |
427 | pte = page_mapping_find(as, b + |
- | 428 | i * PAGE_SIZE); |
|
410 | ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
429 | ASSERT(pte && PTE_VALID(pte) && |
- | 430 | PTE_PRESENT(pte)); |
|
- | 431 | if (area->backend && |
|
411 | if (area->backend && area->backend->frame_free) { |
432 | area->backend->frame_free) { |
412 | area->backend->frame_free(area, |
433 | area->backend->frame_free(area, |
- | 434 | b + i * PAGE_SIZE, |
|
413 | b + i*PAGE_SIZE, PTE_GET_FRAME(pte)); |
435 | PTE_GET_FRAME(pte)); |
414 | } |
436 | } |
415 | page_mapping_remove(as, b + i*PAGE_SIZE); |
437 | page_mapping_remove(as, b + |
- | 438 | i * PAGE_SIZE); |
|
416 | page_table_unlock(as, false); |
439 | page_table_unlock(as, false); |
417 | } |
440 | } |
418 | } |
441 | } |
419 | } |
442 | } |
420 | 443 | ||
421 | /* |
444 | /* |
422 | * Finish TLB shootdown sequence. |
445 | * Finish TLB shootdown sequence. |
423 | */ |
446 | */ |
424 | tlb_invalidate_pages(as->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
447 | tlb_invalidate_pages(as->asid, area->base + pages * PAGE_SIZE, |
- | 448 | area->pages - pages); |
|
425 | tlb_shootdown_finalize(); |
449 | tlb_shootdown_finalize(); |
426 | 450 | ||
427 | /* |
451 | /* |
428 | * Invalidate software translation caches (e.g. TSB on sparc64). |
452 | * Invalidate software translation caches (e.g. TSB on sparc64). |
429 | */ |
453 | */ |
430 | as_invalidate_translation_cache(as, area->base + pages*PAGE_SIZE, area->pages - pages); |
454 | as_invalidate_translation_cache(as, area->base + |
- | 455 | pages * PAGE_SIZE, area->pages - pages); |
|
431 | } else { |
456 | } else { |
432 | /* |
457 | /* |
433 | * Growing the area. |
458 | * Growing the area. |
434 | * Check for overlaps with other address space areas. |
459 | * Check for overlaps with other address space areas. |
435 | */ |
460 | */ |
436 | if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) { |
461 | if (!check_area_conflicts(as, address, pages * PAGE_SIZE, |
- | 462 | area)) { |
|
437 | mutex_unlock(&area->lock); |
463 | mutex_unlock(&area->lock); |
438 | mutex_unlock(&as->lock); |
464 | mutex_unlock(&as->lock); |
439 | interrupts_restore(ipl); |
465 | interrupts_restore(ipl); |
440 | return EADDRNOTAVAIL; |
466 | return EADDRNOTAVAIL; |
441 | } |
467 | } |
Line 482... | Line 508... | ||
482 | tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base, area->pages); |
508 | tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base, area->pages); |
483 | 509 | ||
484 | /* |
510 | /* |
485 | * Visit only the pages mapped by used_space B+tree. |
511 | * Visit only the pages mapped by used_space B+tree. |
486 | */ |
512 | */ |
- | 513 | for (cur = area->used_space.leaf_head.next; |
|
487 | for (cur = area->used_space.leaf_head.next; cur != &area->used_space.leaf_head; cur = cur->next) { |
514 | cur != &area->used_space.leaf_head; cur = cur->next) { |
488 | btree_node_t *node; |
515 | btree_node_t *node; |
489 | int i; |
516 | int i; |
490 | 517 | ||
491 | node = list_get_instance(cur, btree_node_t, leaf_link); |
518 | node = list_get_instance(cur, btree_node_t, leaf_link); |
492 | for (i = 0; i < node->keys; i++) { |
519 | for (i = 0; i < node->keys; i++) { |
Line 494... | Line 521... | ||
494 | count_t j; |
521 | count_t j; |
495 | pte_t *pte; |
522 | pte_t *pte; |
496 | 523 | ||
497 | for (j = 0; j < (count_t) node->value[i]; j++) { |
524 | for (j = 0; j < (count_t) node->value[i]; j++) { |
498 | page_table_lock(as, false); |
525 | page_table_lock(as, false); |
499 | pte = page_mapping_find(as, b + j*PAGE_SIZE); |
526 | pte = page_mapping_find(as, b + j * PAGE_SIZE); |
500 | ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
527 | ASSERT(pte && PTE_VALID(pte) && |
- | 528 | PTE_PRESENT(pte)); |
|
- | 529 | if (area->backend && |
|
501 | if (area->backend && area->backend->frame_free) { |
530 | area->backend->frame_free) { |
502 | area->backend->frame_free(area, |
531 | area->backend->frame_free(area, b + |
503 | b + j*PAGE_SIZE, PTE_GET_FRAME(pte)); |
532 | j * PAGE_SIZE, PTE_GET_FRAME(pte)); |
504 | } |
533 | } |
505 | page_mapping_remove(as, b + j*PAGE_SIZE); |
534 | page_mapping_remove(as, b + j * PAGE_SIZE); |
506 | page_table_unlock(as, false); |
535 | page_table_unlock(as, false); |
507 | } |
536 | } |
508 | } |
537 | } |
509 | } |
538 | } |
510 | 539 | ||
Line 513... | Line 542... | ||
513 | */ |
542 | */ |
514 | tlb_invalidate_pages(as->asid, area->base, area->pages); |
543 | tlb_invalidate_pages(as->asid, area->base, area->pages); |
515 | tlb_shootdown_finalize(); |
544 | tlb_shootdown_finalize(); |
516 | 545 | ||
517 | /* |
546 | /* |
518 | * Invalidate potential software translation caches (e.g. TSB on sparc64). |
547 | * Invalidate potential software translation caches (e.g. TSB on |
- | 548 | * sparc64). |
|
519 | */ |
549 | */ |
520 | as_invalidate_translation_cache(as, area->base, area->pages); |
550 | as_invalidate_translation_cache(as, area->base, area->pages); |
521 | 551 | ||
522 | btree_destroy(&area->used_space); |
552 | btree_destroy(&area->used_space); |
523 | 553 | ||
Line 603... | Line 633... | ||
603 | 633 | ||
604 | /* Share the cacheable flag from the original mapping */ |
634 | /* Share the cacheable flag from the original mapping */ |
605 | if (src_flags & AS_AREA_CACHEABLE) |
635 | if (src_flags & AS_AREA_CACHEABLE) |
606 | dst_flags_mask |= AS_AREA_CACHEABLE; |
636 | dst_flags_mask |= AS_AREA_CACHEABLE; |
607 | 637 | ||
- | 638 | if (src_size != acc_size || |
|
608 | if (src_size != acc_size || (src_flags & dst_flags_mask) != dst_flags_mask) { |
639 | (src_flags & dst_flags_mask) != dst_flags_mask) { |
609 | mutex_unlock(&src_area->lock); |
640 | mutex_unlock(&src_area->lock); |
610 | mutex_unlock(&src_as->lock); |
641 | mutex_unlock(&src_as->lock); |
611 | interrupts_restore(ipl); |
642 | interrupts_restore(ipl); |
612 | return EPERM; |
643 | return EPERM; |
613 | } |
644 | } |
Line 656... | Line 687... | ||
656 | * preliminary as_page_fault() calls. |
687 | * preliminary as_page_fault() calls. |
657 | * The flags of the source area are masked against dst_flags_mask |
688 | * The flags of the source area are masked against dst_flags_mask |
658 | * to support sharing in less privileged mode. |
689 | * to support sharing in less privileged mode. |
659 | */ |
690 | */ |
660 | dst_area = as_area_create(dst_as, dst_flags_mask, src_size, dst_base, |
691 | dst_area = as_area_create(dst_as, dst_flags_mask, src_size, dst_base, |
661 | AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data); |
692 | AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data); |
662 | if (!dst_area) { |
693 | if (!dst_area) { |
663 | /* |
694 | /* |
664 | * Destination address space area could not be created. |
695 | * Destination address space area could not be created. |
665 | */ |
696 | */ |
666 | sh_info_remove_reference(sh_info); |
697 | sh_info_remove_reference(sh_info); |
Line 774... | Line 805... | ||
774 | * the mapping has not been already inserted. |
805 | * the mapping has not been already inserted. |
775 | */ |
806 | */ |
776 | if ((pte = page_mapping_find(AS, page))) { |
807 | if ((pte = page_mapping_find(AS, page))) { |
777 | if (PTE_PRESENT(pte)) { |
808 | if (PTE_PRESENT(pte)) { |
778 | if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) || |
809 | if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) || |
779 | (access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) || |
810 | (access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) || |
780 | (access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) { |
811 | (access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) { |
781 | page_table_unlock(AS, false); |
812 | page_table_unlock(AS, false); |
782 | mutex_unlock(&area->lock); |
813 | mutex_unlock(&area->lock); |
783 | mutex_unlock(&AS->lock); |
814 | mutex_unlock(&AS->lock); |
784 | return AS_PF_OK; |
815 | return AS_PF_OK; |
785 | } |
816 | } |
Line 802... | Line 833... | ||
802 | return AS_PF_OK; |
833 | return AS_PF_OK; |
803 | 834 | ||
804 | page_fault: |
835 | page_fault: |
805 | if (THREAD->in_copy_from_uspace) { |
836 | if (THREAD->in_copy_from_uspace) { |
806 | THREAD->in_copy_from_uspace = false; |
837 | THREAD->in_copy_from_uspace = false; |
- | 838 | istate_set_retaddr(istate, |
|
807 | istate_set_retaddr(istate, (uintptr_t) &memcpy_from_uspace_failover_address); |
839 | (uintptr_t) &memcpy_from_uspace_failover_address); |
808 | } else if (THREAD->in_copy_to_uspace) { |
840 | } else if (THREAD->in_copy_to_uspace) { |
809 | THREAD->in_copy_to_uspace = false; |
841 | THREAD->in_copy_to_uspace = false; |
- | 842 | istate_set_retaddr(istate, |
|
810 | istate_set_retaddr(istate, (uintptr_t) &memcpy_to_uspace_failover_address); |
843 | (uintptr_t) &memcpy_to_uspace_failover_address); |
811 | } else { |
844 | } else { |
812 | return AS_PF_FAULT; |
845 | return AS_PF_FAULT; |
813 | } |
846 | } |
814 | 847 | ||
815 | return AS_PF_DEFER; |
848 | return AS_PF_DEFER; |
Line 843... | Line 876... | ||
843 | * any processor. It can be appended to the |
876 | * any processor. It can be appended to the |
844 | * list of inactive address spaces with assigned |
877 | * list of inactive address spaces with assigned |
845 | * ASID. |
878 | * ASID. |
846 | */ |
879 | */ |
847 | ASSERT(old->asid != ASID_INVALID); |
880 | ASSERT(old->asid != ASID_INVALID); |
848 | list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head); |
881 | list_append(&old->inactive_as_with_asid_link, |
- | 882 | &inactive_as_with_asid_head); |
|
849 | } |
883 | } |
850 | mutex_unlock(&old->lock); |
884 | mutex_unlock(&old->lock); |
851 | 885 | ||
852 | /* |
886 | /* |
853 | * Perform architecture-specific tasks when the address space |
887 | * Perform architecture-specific tasks when the address space |
Line 859... | Line 893... | ||
859 | /* |
893 | /* |
860 | * Second, prepare the new address space. |
894 | * Second, prepare the new address space. |
861 | */ |
895 | */ |
862 | mutex_lock_active(&new->lock); |
896 | mutex_lock_active(&new->lock); |
863 | if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) { |
897 | if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) { |
864 | if (new->asid != ASID_INVALID) |
898 | if (new->asid != ASID_INVALID) { |
865 | list_remove(&new->inactive_as_with_asid_link); |
899 | list_remove(&new->inactive_as_with_asid_link); |
866 | else |
900 | } else { |
- | 901 | /* |
|
867 | needs_asid = true; /* defer call to asid_get() until new->lock is released */ |
902 | * Defer call to asid_get() until new->lock is released. |
- | 903 | */ |
|
- | 904 | needs_asid = true; |
|
- | 905 | } |
|
868 | } |
906 | } |
869 | SET_PTL0_ADDRESS(new->page_table); |
907 | SET_PTL0_ADDRESS(new->page_table); |
870 | mutex_unlock(&new->lock); |
908 | mutex_unlock(&new->lock); |
871 | 909 | ||
872 | if (needs_asid) { |
910 | if (needs_asid) { |
Line 1004... | Line 1042... | ||
1004 | * The address space must be locked and interrupts must be disabled. |
1042 | * The address space must be locked and interrupts must be disabled. |
1005 | * |
1043 | * |
1006 | * @param as Address space. |
1044 | * @param as Address space. |
1007 | * @param va Virtual address. |
1045 | * @param va Virtual address. |
1008 | * |
1046 | * |
1009 | * @return Locked address space area containing va on success or NULL on failure. |
1047 | * @return Locked address space area containing va on success or NULL on |
- | 1048 | * failure. |
|
1010 | */ |
1049 | */ |
1011 | as_area_t *find_area_and_lock(as_t *as, uintptr_t va) |
1050 | as_area_t *find_area_and_lock(as_t *as, uintptr_t va) |
1012 | { |
1051 | { |
1013 | as_area_t *a; |
1052 | as_area_t *a; |
1014 | btree_node_t *leaf, *lnode; |
1053 | btree_node_t *leaf, *lnode; |
Line 1039... | Line 1078... | ||
1039 | 1078 | ||
1040 | /* |
1079 | /* |
1041 | * Second, locate the left neighbour and test its last record. |
1080 | * Second, locate the left neighbour and test its last record. |
1042 | * Because of its position in the B+tree, it must have base < va. |
1081 | * Because of its position in the B+tree, it must have base < va. |
1043 | */ |
1082 | */ |
1044 | if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) { |
1083 | lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); |
- | 1084 | if (lnode) { |
|
1045 | a = (as_area_t *) lnode->value[lnode->keys - 1]; |
1085 | a = (as_area_t *) lnode->value[lnode->keys - 1]; |
1046 | mutex_lock(&a->lock); |
1086 | mutex_lock(&a->lock); |
1047 | if (va < a->base + a->pages * PAGE_SIZE) { |
1087 | if (va < a->base + a->pages * PAGE_SIZE) { |
1048 | return a; |
1088 | return a; |
1049 | } |
1089 | } |
Line 1062... | Line 1102... | ||
1062 | * @param size Size of the area being tested. |
1102 | * @param size Size of the area being tested. |
1063 | * @param avoid_area Do not touch this area. |
1103 | * @param avoid_area Do not touch this area. |
1064 | * |
1104 | * |
1065 | * @return True if there is no conflict, false otherwise. |
1105 | * @return True if there is no conflict, false otherwise. |
1066 | */ |
1106 | */ |
1067 | bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, as_area_t *avoid_area) |
1107 | bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, |
- | 1108 | as_area_t *avoid_area) |
|
1068 | { |
1109 | { |
1069 | as_area_t *a; |
1110 | as_area_t *a; |
1070 | btree_node_t *leaf, *node; |
1111 | btree_node_t *leaf, *node; |
1071 | int i; |
1112 | int i; |
1072 | 1113 | ||
Line 1097... | Line 1138... | ||
1097 | mutex_unlock(&a->lock); |
1138 | mutex_unlock(&a->lock); |
1098 | return false; |
1139 | return false; |
1099 | } |
1140 | } |
1100 | mutex_unlock(&a->lock); |
1141 | mutex_unlock(&a->lock); |
1101 | } |
1142 | } |
1102 | if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) { |
1143 | node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf); |
- | 1144 | if (node) { |
|
1103 | a = (as_area_t *) node->value[0]; |
1145 | a = (as_area_t *) node->value[0]; |
1104 | mutex_lock(&a->lock); |
1146 | mutex_lock(&a->lock); |
1105 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
1147 | if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) { |
1106 | mutex_unlock(&a->lock); |
1148 | mutex_unlock(&a->lock); |
1107 | return false; |
1149 | return false; |
Line 1128... | Line 1170... | ||
1128 | * So far, the area does not conflict with other areas. |
1170 | * So far, the area does not conflict with other areas. |
1129 | * Check if it doesn't conflict with kernel address space. |
1171 | * Check if it doesn't conflict with kernel address space. |
1130 | */ |
1172 | */ |
1131 | if (!KERNEL_ADDRESS_SPACE_SHADOWED) { |
1173 | if (!KERNEL_ADDRESS_SPACE_SHADOWED) { |
1132 | return !overlaps(va, size, |
1174 | return !overlaps(va, size, |
- | 1175 | KERNEL_ADDRESS_SPACE_START, |
|
1133 | KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START); |
1176 | KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START); |
1134 | } |
1177 | } |
1135 | 1178 | ||
1136 | return true; |
1179 | return true; |
1137 | } |
1180 | } |
1138 | 1181 | ||
Line 1187... | Line 1230... | ||
1187 | return 1; |
1230 | return 1; |
1188 | } |
1231 | } |
1189 | 1232 | ||
1190 | node = btree_leaf_node_left_neighbour(&a->used_space, leaf); |
1233 | node = btree_leaf_node_left_neighbour(&a->used_space, leaf); |
1191 | if (node) { |
1234 | if (node) { |
1192 | uintptr_t left_pg = node->key[node->keys - 1], right_pg = leaf->key[0]; |
1235 | uintptr_t left_pg = node->key[node->keys - 1]; |
- | 1236 | uintptr_t right_pg = leaf->key[0]; |
|
1193 | count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0]; |
1237 | count_t left_cnt = (count_t) node->value[node->keys - 1]; |
- | 1238 | count_t right_cnt = (count_t) leaf->value[0]; |
|
1194 | 1239 | ||
1195 | /* |
1240 | /* |
1196 | * Examine the possibility that the interval fits |
1241 | * Examine the possibility that the interval fits |
1197 | * somewhere between the rightmost interval of |
1242 | * somewhere between the rightmost interval of |
1198 | * the left neigbour and the first interval of the leaf. |
1243 | * the left neigbour and the first interval of the leaf. |
1199 | */ |
1244 | */ |
1200 | 1245 | ||
1201 | if (page >= right_pg) { |
1246 | if (page >= right_pg) { |
1202 | /* Do nothing. */ |
1247 | /* Do nothing. */ |
1203 | } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1248 | } else if (overlaps(page, count * PAGE_SIZE, left_pg, |
- | 1249 | left_cnt * PAGE_SIZE)) { |
|
1204 | /* The interval intersects with the left interval. */ |
1250 | /* The interval intersects with the left interval. */ |
1205 | return 0; |
1251 | return 0; |
1206 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1252 | } else if (overlaps(page, count * PAGE_SIZE, right_pg, |
- | 1253 | right_cnt * PAGE_SIZE)) { |
|
1207 | /* The interval intersects with the right interval. */ |
1254 | /* The interval intersects with the right interval. */ |
1208 | return 0; |
1255 | return 0; |
1209 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1256 | } else if ((page == left_pg + left_cnt * PAGE_SIZE) && |
- | 1257 | (page + count * PAGE_SIZE == right_pg)) { |
|
- | 1258 | /* |
|
1210 | /* The interval can be added by merging the two already present intervals. */ |
1259 | * The interval can be added by merging the two already |
- | 1260 | * present intervals. |
|
- | 1261 | */ |
|
1211 | node->value[node->keys - 1] += count + right_cnt; |
1262 | node->value[node->keys - 1] += count + right_cnt; |
1212 | btree_remove(&a->used_space, right_pg, leaf); |
1263 | btree_remove(&a->used_space, right_pg, leaf); |
1213 | return 1; |
1264 | return 1; |
1214 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1265 | } else if (page == left_pg + left_cnt * PAGE_SIZE) { |
- | 1266 | /* |
|
1215 | /* The interval can be added by simply growing the left interval. */ |
1267 | * The interval can be added by simply growing the left |
- | 1268 | * interval. |
|
- | 1269 | */ |
|
1216 | node->value[node->keys - 1] += count; |
1270 | node->value[node->keys - 1] += count; |
1217 | return 1; |
1271 | return 1; |
1218 | } else if (page + count*PAGE_SIZE == right_pg) { |
1272 | } else if (page + count * PAGE_SIZE == right_pg) { |
1219 | /* |
1273 | /* |
1220 | * The interval can be addded by simply moving base of the right |
1274 | * The interval can be addded by simply moving base of |
1221 | * interval down and increasing its size accordingly. |
1275 | * the right interval down and increasing its size |
- | 1276 | * accordingly. |
|
1222 | */ |
1277 | */ |
1223 | leaf->value[0] += count; |
1278 | leaf->value[0] += count; |
1224 | leaf->key[0] = page; |
1279 | leaf->key[0] = page; |
1225 | return 1; |
1280 | return 1; |
1226 | } else { |
1281 | } else { |
1227 | /* |
1282 | /* |
1228 | * The interval is between both neigbouring intervals, |
1283 | * The interval is between both neigbouring intervals, |
1229 | * but cannot be merged with any of them. |
1284 | * but cannot be merged with any of them. |
1230 | */ |
1285 | */ |
1231 | btree_insert(&a->used_space, page, (void *) count, leaf); |
1286 | btree_insert(&a->used_space, page, (void *) count, |
- | 1287 | leaf); |
|
1232 | return 1; |
1288 | return 1; |
1233 | } |
1289 | } |
1234 | } else if (page < leaf->key[0]) { |
1290 | } else if (page < leaf->key[0]) { |
1235 | uintptr_t right_pg = leaf->key[0]; |
1291 | uintptr_t right_pg = leaf->key[0]; |
1236 | count_t right_cnt = (count_t) leaf->value[0]; |
1292 | count_t right_cnt = (count_t) leaf->value[0]; |
1237 | 1293 | ||
1238 | /* |
1294 | /* |
1239 | * Investigate the border case in which the left neighbour does not |
1295 | * Investigate the border case in which the left neighbour does |
1240 | * exist but the interval fits from the left. |
1296 | * not exist but the interval fits from the left. |
1241 | */ |
1297 | */ |
1242 | 1298 | ||
1243 | if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1299 | if (overlaps(page, count * PAGE_SIZE, right_pg, |
- | 1300 | right_cnt * PAGE_SIZE)) { |
|
1244 | /* The interval intersects with the right interval. */ |
1301 | /* The interval intersects with the right interval. */ |
1245 | return 0; |
1302 | return 0; |
1246 | } else if (page + count*PAGE_SIZE == right_pg) { |
1303 | } else if (page + count * PAGE_SIZE == right_pg) { |
1247 | /* |
1304 | /* |
1248 | * The interval can be added by moving the base of the right interval down |
1305 | * The interval can be added by moving the base of the |
1249 | * and increasing its size accordingly. |
1306 | * right interval down and increasing its size |
- | 1307 | * accordingly. |
|
1250 | */ |
1308 | */ |
1251 | leaf->key[0] = page; |
1309 | leaf->key[0] = page; |
1252 | leaf->value[0] += count; |
1310 | leaf->value[0] += count; |
1253 | return 1; |
1311 | return 1; |
1254 | } else { |
1312 | } else { |
1255 | /* |
1313 | /* |
1256 | * The interval doesn't adjoin with the right interval. |
1314 | * The interval doesn't adjoin with the right interval. |
1257 | * It must be added individually. |
1315 | * It must be added individually. |
1258 | */ |
1316 | */ |
1259 | btree_insert(&a->used_space, page, (void *) count, leaf); |
1317 | btree_insert(&a->used_space, page, (void *) count, |
- | 1318 | leaf); |
|
1260 | return 1; |
1319 | return 1; |
1261 | } |
1320 | } |
1262 | } |
1321 | } |
1263 | 1322 | ||
1264 | node = btree_leaf_node_right_neighbour(&a->used_space, leaf); |
1323 | node = btree_leaf_node_right_neighbour(&a->used_space, leaf); |
1265 | if (node) { |
1324 | if (node) { |
1266 | uintptr_t left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0]; |
1325 | uintptr_t left_pg = leaf->key[leaf->keys - 1]; |
- | 1326 | uintptr_t right_pg = node->key[0]; |
|
1267 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0]; |
1327 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1]; |
- | 1328 | count_t right_cnt = (count_t) node->value[0]; |
|
1268 | 1329 | ||
1269 | /* |
1330 | /* |
1270 | * Examine the possibility that the interval fits |
1331 | * Examine the possibility that the interval fits |
1271 | * somewhere between the leftmost interval of |
1332 | * somewhere between the leftmost interval of |
1272 | * the right neigbour and the last interval of the leaf. |
1333 | * the right neigbour and the last interval of the leaf. |
1273 | */ |
1334 | */ |
1274 | 1335 | ||
1275 | if (page < left_pg) { |
1336 | if (page < left_pg) { |
1276 | /* Do nothing. */ |
1337 | /* Do nothing. */ |
1277 | } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1338 | } else if (overlaps(page, count * PAGE_SIZE, left_pg, |
- | 1339 | left_cnt * PAGE_SIZE)) { |
|
1278 | /* The interval intersects with the left interval. */ |
1340 | /* The interval intersects with the left interval. */ |
1279 | return 0; |
1341 | return 0; |
1280 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1342 | } else if (overlaps(page, count * PAGE_SIZE, right_pg, |
- | 1343 | right_cnt * PAGE_SIZE)) { |
|
1281 | /* The interval intersects with the right interval. */ |
1344 | /* The interval intersects with the right interval. */ |
1282 | return 0; |
1345 | return 0; |
1283 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1346 | } else if ((page == left_pg + left_cnt * PAGE_SIZE) && |
- | 1347 | (page + count * PAGE_SIZE == right_pg)) { |
|
- | 1348 | /* |
|
1284 | /* The interval can be added by merging the two already present intervals. */ |
1349 | * The interval can be added by merging the two already |
- | 1350 | * present intervals. |
|
- | 1351 | * */ |
|
1285 | leaf->value[leaf->keys - 1] += count + right_cnt; |
1352 | leaf->value[leaf->keys - 1] += count + right_cnt; |
1286 | btree_remove(&a->used_space, right_pg, node); |
1353 | btree_remove(&a->used_space, right_pg, node); |
1287 | return 1; |
1354 | return 1; |
1288 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1355 | } else if (page == left_pg + left_cnt * PAGE_SIZE) { |
- | 1356 | /* |
|
1289 | /* The interval can be added by simply growing the left interval. */ |
1357 | * The interval can be added by simply growing the left |
- | 1358 | * interval. |
|
- | 1359 | * */ |
|
1290 | leaf->value[leaf->keys - 1] += count; |
1360 | leaf->value[leaf->keys - 1] += count; |
1291 | return 1; |
1361 | return 1; |
1292 | } else if (page + count*PAGE_SIZE == right_pg) { |
1362 | } else if (page + count * PAGE_SIZE == right_pg) { |
1293 | /* |
1363 | /* |
1294 | * The interval can be addded by simply moving base of the right |
1364 | * The interval can be addded by simply moving base of |
1295 | * interval down and increasing its size accordingly. |
1365 | * the right interval down and increasing its size |
- | 1366 | * accordingly. |
|
1296 | */ |
1367 | */ |
1297 | node->value[0] += count; |
1368 | node->value[0] += count; |
1298 | node->key[0] = page; |
1369 | node->key[0] = page; |
1299 | return 1; |
1370 | return 1; |
1300 | } else { |
1371 | } else { |
1301 | /* |
1372 | /* |
1302 | * The interval is between both neigbouring intervals, |
1373 | * The interval is between both neigbouring intervals, |
1303 | * but cannot be merged with any of them. |
1374 | * but cannot be merged with any of them. |
1304 | */ |
1375 | */ |
1305 | btree_insert(&a->used_space, page, (void *) count, leaf); |
1376 | btree_insert(&a->used_space, page, (void *) count, |
- | 1377 | leaf); |
|
1306 | return 1; |
1378 | return 1; |
1307 | } |
1379 | } |
1308 | } else if (page >= leaf->key[leaf->keys - 1]) { |
1380 | } else if (page >= leaf->key[leaf->keys - 1]) { |
1309 | uintptr_t left_pg = leaf->key[leaf->keys - 1]; |
1381 | uintptr_t left_pg = leaf->key[leaf->keys - 1]; |
1310 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1]; |
1382 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1]; |
1311 | 1383 | ||
1312 | /* |
1384 | /* |
1313 | * Investigate the border case in which the right neighbour does not |
1385 | * Investigate the border case in which the right neighbour |
1314 | * exist but the interval fits from the right. |
1386 | * does not exist but the interval fits from the right. |
1315 | */ |
1387 | */ |
1316 | 1388 | ||
1317 | if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1389 | if (overlaps(page, count * PAGE_SIZE, left_pg, |
- | 1390 | left_cnt * PAGE_SIZE)) { |
|
1318 | /* The interval intersects with the left interval. */ |
1391 | /* The interval intersects with the left interval. */ |
1319 | return 0; |
1392 | return 0; |
1320 | } else if (left_pg + left_cnt*PAGE_SIZE == page) { |
1393 | } else if (left_pg + left_cnt * PAGE_SIZE == page) { |
- | 1394 | /* |
|
1321 | /* The interval can be added by growing the left interval. */ |
1395 | * The interval can be added by growing the left |
- | 1396 | * interval. |
|
- | 1397 | */ |
|
1322 | leaf->value[leaf->keys - 1] += count; |
1398 | leaf->value[leaf->keys - 1] += count; |
1323 | return 1; |
1399 | return 1; |
1324 | } else { |
1400 | } else { |
1325 | /* |
1401 | /* |
1326 | * The interval doesn't adjoin with the left interval. |
1402 | * The interval doesn't adjoin with the left interval. |
1327 | * It must be added individually. |
1403 | * It must be added individually. |
1328 | */ |
1404 | */ |
1329 | btree_insert(&a->used_space, page, (void *) count, leaf); |
1405 | btree_insert(&a->used_space, page, (void *) count, |
- | 1406 | leaf); |
|
1330 | return 1; |
1407 | return 1; |
1331 | } |
1408 | } |
1332 | } |
1409 | } |
1333 | 1410 | ||
1334 | /* |
1411 | /* |
1335 | * Note that if the algorithm made it thus far, the interval can fit only |
1412 | * Note that if the algorithm made it thus far, the interval can fit |
1336 | * between two other intervals of the leaf. The two border cases were already |
1413 | * only between two other intervals of the leaf. The two border cases |
1337 | * resolved. |
1414 | * were already resolved. |
1338 | */ |
1415 | */ |
1339 | for (i = 1; i < leaf->keys; i++) { |
1416 | for (i = 1; i < leaf->keys; i++) { |
1340 | if (page < leaf->key[i]) { |
1417 | if (page < leaf->key[i]) { |
1341 | uintptr_t left_pg = leaf->key[i - 1], right_pg = leaf->key[i]; |
1418 | uintptr_t left_pg = leaf->key[i - 1]; |
- | 1419 | uintptr_t right_pg = leaf->key[i]; |
|
1342 | count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i]; |
1420 | count_t left_cnt = (count_t) leaf->value[i - 1]; |
- | 1421 | count_t right_cnt = (count_t) leaf->value[i]; |
|
1343 | 1422 | ||
1344 | /* |
1423 | /* |
1345 | * The interval fits between left_pg and right_pg. |
1424 | * The interval fits between left_pg and right_pg. |
1346 | */ |
1425 | */ |
1347 | 1426 | ||
1348 | if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1427 | if (overlaps(page, count * PAGE_SIZE, left_pg, |
- | 1428 | left_cnt * PAGE_SIZE)) { |
|
- | 1429 | /* |
|
1349 | /* The interval intersects with the left interval. */ |
1430 | * The interval intersects with the left |
- | 1431 | * interval. |
|
- | 1432 | */ |
|
1350 | return 0; |
1433 | return 0; |
1351 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1434 | } else if (overlaps(page, count * PAGE_SIZE, right_pg, |
- | 1435 | right_cnt * PAGE_SIZE)) { |
|
- | 1436 | /* |
|
1352 | /* The interval intersects with the right interval. */ |
1437 | * The interval intersects with the right |
- | 1438 | * interval. |
|
- | 1439 | */ |
|
1353 | return 0; |
1440 | return 0; |
1354 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1441 | } else if ((page == left_pg + left_cnt * PAGE_SIZE) && |
- | 1442 | (page + count * PAGE_SIZE == right_pg)) { |
|
- | 1443 | /* |
|
1355 | /* The interval can be added by merging the two already present intervals. */ |
1444 | * The interval can be added by merging the two |
- | 1445 | * already present intervals. |
|
- | 1446 | */ |
|
1356 | leaf->value[i - 1] += count + right_cnt; |
1447 | leaf->value[i - 1] += count + right_cnt; |
1357 | btree_remove(&a->used_space, right_pg, leaf); |
1448 | btree_remove(&a->used_space, right_pg, leaf); |
1358 | return 1; |
1449 | return 1; |
1359 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1450 | } else if (page == left_pg + left_cnt * PAGE_SIZE) { |
- | 1451 | /* |
|
1360 | /* The interval can be added by simply growing the left interval. */ |
1452 | * The interval can be added by simply growing |
- | 1453 | * the left interval. |
|
- | 1454 | */ |
|
1361 | leaf->value[i - 1] += count; |
1455 | leaf->value[i - 1] += count; |
1362 | return 1; |
1456 | return 1; |
1363 | } else if (page + count*PAGE_SIZE == right_pg) { |
1457 | } else if (page + count * PAGE_SIZE == right_pg) { |
1364 | /* |
1458 | /* |
1365 | * The interval can be addded by simply moving base of the right |
1459 | * The interval can be addded by simply moving |
- | 1460 | * base of the right interval down and |
|
1366 | * interval down and increasing its size accordingly. |
1461 | * increasing its size accordingly. |
1367 | */ |
1462 | */ |
1368 | leaf->value[i] += count; |
1463 | leaf->value[i] += count; |
1369 | leaf->key[i] = page; |
1464 | leaf->key[i] = page; |
1370 | return 1; |
1465 | return 1; |
1371 | } else { |
1466 | } else { |
1372 | /* |
1467 | /* |
1373 | * The interval is between both neigbouring intervals, |
1468 | * The interval is between both neigbouring |
1374 | * but cannot be merged with any of them. |
1469 | * intervals, but cannot be merged with any of |
- | 1470 | * them. |
|
1375 | */ |
1471 | */ |
1376 | btree_insert(&a->used_space, page, (void *) count, leaf); |
1472 | btree_insert(&a->used_space, page, |
- | 1473 | (void *) count, leaf); |
|
1377 | return 1; |
1474 | return 1; |
1378 | } |
1475 | } |
1379 | } |
1476 | } |
1380 | } |
1477 | } |
1381 | 1478 | ||
1382 | panic("Inconsistency detected while adding %d pages of used space at %p.\n", count, page); |
1479 | panic("Inconsistency detected while adding %d pages of used space at " |
- | 1480 | "%p.\n", count, page); |
|
1383 | } |
1481 | } |
1384 | 1482 | ||
1385 | /** Mark portion of address space area as unused. |
1483 | /** Mark portion of address space area as unused. |
1386 | * |
1484 | * |
1387 | * The address space area must be already locked. |
1485 | * The address space area must be already locked. |
Line 1416... | Line 1514... | ||
1416 | * Find the respective interval. |
1514 | * Find the respective interval. |
1417 | * Decrease its size and relocate its start address. |
1515 | * Decrease its size and relocate its start address. |
1418 | */ |
1516 | */ |
1419 | for (i = 0; i < leaf->keys; i++) { |
1517 | for (i = 0; i < leaf->keys; i++) { |
1420 | if (leaf->key[i] == page) { |
1518 | if (leaf->key[i] == page) { |
1421 | leaf->key[i] += count*PAGE_SIZE; |
1519 | leaf->key[i] += count * PAGE_SIZE; |
1422 | leaf->value[i] -= count; |
1520 | leaf->value[i] -= count; |
1423 | return 1; |
1521 | return 1; |
1424 | } |
1522 | } |
1425 | } |
1523 | } |
1426 | goto error; |
1524 | goto error; |
Line 1430... | Line 1528... | ||
1430 | node = btree_leaf_node_left_neighbour(&a->used_space, leaf); |
1528 | node = btree_leaf_node_left_neighbour(&a->used_space, leaf); |
1431 | if (node && page < leaf->key[0]) { |
1529 | if (node && page < leaf->key[0]) { |
1432 | uintptr_t left_pg = node->key[node->keys - 1]; |
1530 | uintptr_t left_pg = node->key[node->keys - 1]; |
1433 | count_t left_cnt = (count_t) node->value[node->keys - 1]; |
1531 | count_t left_cnt = (count_t) node->value[node->keys - 1]; |
1434 | 1532 | ||
1435 | if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) { |
1533 | if (overlaps(left_pg, left_cnt * PAGE_SIZE, page, |
- | 1534 | count * PAGE_SIZE)) { |
|
- | 1535 | if (page + count * PAGE_SIZE == |
|
1436 | if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) { |
1536 | left_pg + left_cnt * PAGE_SIZE) { |
1437 | /* |
1537 | /* |
1438 | * The interval is contained in the rightmost interval |
1538 | * The interval is contained in the rightmost |
1439 | * of the left neighbour and can be removed by |
1539 | * interval of the left neighbour and can be |
1440 | * updating the size of the bigger interval. |
1540 | * removed by updating the size of the bigger |
- | 1541 | * interval. |
|
1441 | */ |
1542 | */ |
1442 | node->value[node->keys - 1] -= count; |
1543 | node->value[node->keys - 1] -= count; |
1443 | return 1; |
1544 | return 1; |
1444 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1545 | } else if (page + count * PAGE_SIZE < |
- | 1546 | left_pg + left_cnt*PAGE_SIZE) { |
|
1445 | count_t new_cnt; |
1547 | count_t new_cnt; |
1446 | 1548 | ||
1447 | /* |
1549 | /* |
1448 | * The interval is contained in the rightmost interval |
1550 | * The interval is contained in the rightmost |
1449 | * of the left neighbour but its removal requires |
1551 | * interval of the left neighbour but its |
- | 1552 | * removal requires both updating the size of |
|
1450 | * both updating the size of the original interval and |
1553 | * the original interval and also inserting a |
1451 | * also inserting a new interval. |
1554 | * new interval. |
1452 | */ |
1555 | */ |
- | 1556 | new_cnt = ((left_pg + left_cnt * PAGE_SIZE) - |
|
1453 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
1557 | (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
1454 | node->value[node->keys - 1] -= count + new_cnt; |
1558 | node->value[node->keys - 1] -= count + new_cnt; |
- | 1559 | btree_insert(&a->used_space, page + |
|
1455 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1560 | count * PAGE_SIZE, (void *) new_cnt, leaf); |
1456 | return 1; |
1561 | return 1; |
1457 | } |
1562 | } |
1458 | } |
1563 | } |
1459 | return 0; |
1564 | return 0; |
1460 | } else if (page < leaf->key[0]) { |
1565 | } else if (page < leaf->key[0]) { |
Line 1463... | Line 1568... | ||
1463 | 1568 | ||
1464 | if (page > leaf->key[leaf->keys - 1]) { |
1569 | if (page > leaf->key[leaf->keys - 1]) { |
1465 | uintptr_t left_pg = leaf->key[leaf->keys - 1]; |
1570 | uintptr_t left_pg = leaf->key[leaf->keys - 1]; |
1466 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1]; |
1571 | count_t left_cnt = (count_t) leaf->value[leaf->keys - 1]; |
1467 | 1572 | ||
1468 | if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) { |
1573 | if (overlaps(left_pg, left_cnt * PAGE_SIZE, page, |
- | 1574 | count * PAGE_SIZE)) { |
|
- | 1575 | if (page + count * PAGE_SIZE == |
|
1469 | if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) { |
1576 | left_pg + left_cnt * PAGE_SIZE) { |
1470 | /* |
1577 | /* |
1471 | * The interval is contained in the rightmost interval |
1578 | * The interval is contained in the rightmost |
1472 | * of the leaf and can be removed by updating the size |
1579 | * interval of the leaf and can be removed by |
1473 | * of the bigger interval. |
1580 | * updating the size of the bigger interval. |
1474 | */ |
1581 | */ |
1475 | leaf->value[leaf->keys - 1] -= count; |
1582 | leaf->value[leaf->keys - 1] -= count; |
1476 | return 1; |
1583 | return 1; |
1477 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1584 | } else if (page + count * PAGE_SIZE < left_pg + |
- | 1585 | left_cnt * PAGE_SIZE) { |
|
1478 | count_t new_cnt; |
1586 | count_t new_cnt; |
1479 | 1587 | ||
1480 | /* |
1588 | /* |
1481 | * The interval is contained in the rightmost interval |
1589 | * The interval is contained in the rightmost |
1482 | * of the leaf but its removal requires both updating |
1590 | * interval of the leaf but its removal |
1483 | * the size of the original interval and |
1591 | * requires both updating the size of the |
1484 | * also inserting a new interval. |
1592 | * original interval and also inserting a new |
- | 1593 | * interval. |
|
1485 | */ |
1594 | */ |
1486 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
1595 | new_cnt = ((left_pg + left_cnt * PAGE_SIZE) - |
- | 1596 | (page + count * PAGE_SIZE)) >> PAGE_WIDTH; |
|
1487 | leaf->value[leaf->keys - 1] -= count + new_cnt; |
1597 | leaf->value[leaf->keys - 1] -= count + new_cnt; |
- | 1598 | btree_insert(&a->used_space, page + |
|
1488 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1599 | count * PAGE_SIZE, (void *) new_cnt, leaf); |
1489 | return 1; |
1600 | return 1; |
1490 | } |
1601 | } |
1491 | } |
1602 | } |
1492 | return 0; |
1603 | return 0; |
1493 | } |
1604 | } |
Line 1500... | Line 1611... | ||
1500 | if (page < leaf->key[i]) { |
1611 | if (page < leaf->key[i]) { |
1501 | uintptr_t left_pg = leaf->key[i - 1]; |
1612 | uintptr_t left_pg = leaf->key[i - 1]; |
1502 | count_t left_cnt = (count_t) leaf->value[i - 1]; |
1613 | count_t left_cnt = (count_t) leaf->value[i - 1]; |
1503 | 1614 | ||
1504 | /* |
1615 | /* |
1505 | * Now the interval is between intervals corresponding to (i - 1) and i. |
1616 | * Now the interval is between intervals corresponding |
- | 1617 | * to (i - 1) and i. |
|
1506 | */ |
1618 | */ |
1507 | if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) { |
1619 | if (overlaps(left_pg, left_cnt * PAGE_SIZE, page, |
- | 1620 | count * PAGE_SIZE)) { |
|
- | 1621 | if (page + count * PAGE_SIZE == |
|
1508 | if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) { |
1622 | left_pg + left_cnt*PAGE_SIZE) { |
1509 | /* |
1623 | /* |
1510 | * The interval is contained in the interval (i - 1) |
1624 | * The interval is contained in the |
- | 1625 | * interval (i - 1) of the leaf and can |
|
1511 | * of the leaf and can be removed by updating the size |
1626 | * be removed by updating the size of |
1512 | * of the bigger interval. |
1627 | * the bigger interval. |
1513 | */ |
1628 | */ |
1514 | leaf->value[i - 1] -= count; |
1629 | leaf->value[i - 1] -= count; |
1515 | return 1; |
1630 | return 1; |
1516 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1631 | } else if (page + count * PAGE_SIZE < |
- | 1632 | left_pg + left_cnt * PAGE_SIZE) { |
|
1517 | count_t new_cnt; |
1633 | count_t new_cnt; |
1518 | 1634 | ||
1519 | /* |
1635 | /* |
1520 | * The interval is contained in the interval (i - 1) |
1636 | * The interval is contained in the |
- | 1637 | * interval (i - 1) of the leaf but its |
|
1521 | * of the leaf but its removal requires both updating |
1638 | * removal requires both updating the |
1522 | * the size of the original interval and |
1639 | * size of the original interval and |
1523 | * also inserting a new interval. |
1640 | * also inserting a new interval. |
1524 | */ |
1641 | */ |
- | 1642 | new_cnt = ((left_pg + |
|
- | 1643 | left_cnt * PAGE_SIZE) - |
|
1525 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
1644 | (page + count * PAGE_SIZE)) >> |
- | 1645 | PAGE_WIDTH; |
|
1526 | leaf->value[i - 1] -= count + new_cnt; |
1646 | leaf->value[i - 1] -= count + new_cnt; |
- | 1647 | btree_insert(&a->used_space, page + |
|
1527 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1648 | count * PAGE_SIZE, (void *) new_cnt, |
- | 1649 | leaf); |
|
1528 | return 1; |
1650 | return 1; |
1529 | } |
1651 | } |
1530 | } |
1652 | } |
1531 | return 0; |
1653 | return 0; |
1532 | } |
1654 | } |
1533 | } |
1655 | } |
1534 | 1656 | ||
1535 | error: |
1657 | error: |
1536 | panic("Inconsistency detected while removing %d pages of used space from %p.\n", count, page); |
1658 | panic("Inconsistency detected while removing %d pages of used space " |
- | 1659 | "from %p.\n", count, page); |
|
1537 | } |
1660 | } |
1538 | 1661 | ||
1539 | /** Remove reference to address space area share info. |
1662 | /** Remove reference to address space area share info. |
1540 | * |
1663 | * |
1541 | * If the reference count drops to 0, the sh_info is deallocated. |
1664 | * If the reference count drops to 0, the sh_info is deallocated. |
Line 1554... | Line 1677... | ||
1554 | 1677 | ||
1555 | /* |
1678 | /* |
1556 | * Now walk carefully the pagemap B+tree and free/remove |
1679 | * Now walk carefully the pagemap B+tree and free/remove |
1557 | * reference from all frames found there. |
1680 | * reference from all frames found there. |
1558 | */ |
1681 | */ |
- | 1682 | for (cur = sh_info->pagemap.leaf_head.next; |
|
1559 | for (cur = sh_info->pagemap.leaf_head.next; cur != &sh_info->pagemap.leaf_head; cur = cur->next) { |
1683 | cur != &sh_info->pagemap.leaf_head; cur = cur->next) { |
1560 | btree_node_t *node; |
1684 | btree_node_t *node; |
1561 | int i; |
1685 | int i; |
1562 | 1686 | ||
1563 | node = list_get_instance(cur, btree_node_t, leaf_link); |
1687 | node = list_get_instance(cur, btree_node_t, leaf_link); |
1564 | for (i = 0; i < node->keys; i++) |
1688 | for (i = 0; i < node->keys; i++) |
Line 1579... | Line 1703... | ||
1579 | */ |
1703 | */ |
1580 | 1704 | ||
1581 | /** Wrapper for as_area_create(). */ |
1705 | /** Wrapper for as_area_create(). */ |
1582 | unative_t sys_as_area_create(uintptr_t address, size_t size, int flags) |
1706 | unative_t sys_as_area_create(uintptr_t address, size_t size, int flags) |
1583 | { |
1707 | { |
1584 | if (as_area_create(AS, flags | AS_AREA_CACHEABLE, size, address, AS_AREA_ATTR_NONE, &anon_backend, NULL)) |
1708 | if (as_area_create(AS, flags | AS_AREA_CACHEABLE, size, address, |
- | 1709 | AS_AREA_ATTR_NONE, &anon_backend, NULL)) |
|
1585 | return (unative_t) address; |
1710 | return (unative_t) address; |
1586 | else |
1711 | else |
1587 | return (unative_t) -1; |
1712 | return (unative_t) -1; |
1588 | } |
1713 | } |
1589 | 1714 | ||
Line 1610... | Line 1735... | ||
1610 | ipl = interrupts_disable(); |
1735 | ipl = interrupts_disable(); |
1611 | mutex_lock(&as->lock); |
1736 | mutex_lock(&as->lock); |
1612 | 1737 | ||
1613 | /* print out info about address space areas */ |
1738 | /* print out info about address space areas */ |
1614 | link_t *cur; |
1739 | link_t *cur; |
- | 1740 | for (cur = as->as_area_btree.leaf_head.next; |
|
1615 | for (cur = as->as_area_btree.leaf_head.next; cur != &as->as_area_btree.leaf_head; cur = cur->next) { |
1741 | cur != &as->as_area_btree.leaf_head; cur = cur->next) { |
- | 1742 | btree_node_t *node; |
|
- | 1743 | ||
1616 | btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link); |
1744 | node = list_get_instance(cur, btree_node_t, leaf_link); |
1617 | 1745 | ||
1618 | int i; |
1746 | int i; |
1619 | for (i = 0; i < node->keys; i++) { |
1747 | for (i = 0; i < node->keys; i++) { |
1620 | as_area_t *area = node->value[i]; |
1748 | as_area_t *area = node->value[i]; |
1621 | 1749 | ||
1622 | mutex_lock(&area->lock); |
1750 | mutex_lock(&area->lock); |
1623 | printf("as_area: %p, base=%p, pages=%d (%p - %p)\n", |
1751 | printf("as_area: %p, base=%p, pages=%d (%p - %p)\n", |
1624 | area, area->base, area->pages, area->base, area->base + area->pages*PAGE_SIZE); |
1752 | area, area->base, area->pages, area->base, |
- | 1753 | area->base + area->pages*PAGE_SIZE); |
|
1625 | mutex_unlock(&area->lock); |
1754 | mutex_unlock(&area->lock); |
1626 | } |
1755 | } |
1627 | } |
1756 | } |
1628 | 1757 | ||
1629 | mutex_unlock(&as->lock); |
1758 | mutex_unlock(&as->lock); |