Changes in kernel/generic/src/mm/as.c [6785b88b:ac9e79d] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/mm/as.c (modified) (19 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/mm/as.c
r6785b88b rac9e79d 1 1 /* 2 2 * Copyright (c) 2010 Jakub Jermar 3 * Copyright (c) 2018 Jiri Svoboda4 3 * All rights reserved. 5 4 * … … 112 111 as_t *AS_KERNEL = NULL; 113 112 114 static void *as_areas_getkey(odlink_t *);115 static int as_areas_cmp(void *, void *);116 117 113 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags) 118 114 { … … 141 137 if (!AS_KERNEL) 142 138 panic("Cannot create kernel address space."); 143 144 /*145 * Make sure the kernel address space146 * reference count never drops to zero.147 */148 as_hold(AS_KERNEL);149 139 } 150 140 … … 160 150 (void) as_create_arch(as, 0); 161 151 162 odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp);152 btree_create(&as->as_area_btree); 163 153 164 154 if (flags & FLAG_AS_KERNEL) … … 234 224 /* 235 225 * Destroy address space areas of the address space. 236 * Need to start from the beginning each time since we are destroying 237 * the areas. 238 */ 239 as_area_t *area = as_area_first(as); 240 while (area != NULL) { 241 /* 242 * XXX We already have as_area_t, but as_area_destroy will 243 * have to search for it. This could be made faster. 244 */ 245 as_area_destroy(as, area->base); 246 area = as_area_first(as); 247 } 248 249 odict_finalize(&as->as_areas); 226 * The B+tree must be walked carefully because it is 227 * also being destroyed. 228 */ 229 bool cond = true; 230 while (cond) { 231 assert(!list_empty(&as->as_area_btree.leaf_list)); 232 233 btree_node_t *node = 234 list_get_instance(list_first(&as->as_area_btree.leaf_list), 235 btree_node_t, leaf_link); 236 237 if ((cond = node->keys)) 238 as_area_destroy(as, node->key[0]); 239 } 240 241 btree_destroy(&as->as_area_btree); 250 242 251 243 #ifdef AS_PAGE_TABLE … … 285 277 } 286 278 287 /** Return first address space area.288 *289 * @param as Address space290 * @return First area in @a as (i.e. area with the lowest base address)291 * or @c NULL if there is none292 */293 as_area_t *as_area_first(as_t *as)294 {295 odlink_t *odlink = odict_first(&as->as_areas);296 if (odlink == NULL)297 return NULL;298 299 return odict_get_instance(odlink, as_area_t, las_areas);300 }301 302 /** Return next address space area.303 *304 * @param cur Current area305 * @return Next area in the same address space or @c NULL if @a cur is the306 * last area.307 */308 as_area_t *as_area_next(as_area_t *cur)309 {310 odlink_t *odlink = odict_next(&cur->las_areas, &cur->as->as_areas);311 if (odlink == NULL)312 return NULL;313 314 return odict_get_instance(odlink, as_area_t, las_areas);315 }316 317 /** Determine if area with specified parameters would conflict with318 * a specific existing address space area.319 *320 * @param addr Starting virtual address of the area being tested.321 * @param count Number of pages in the area being tested.322 * @param guarded True if the area being tested is protected by guard pages.323 * @param area Area against which we are testing.324 *325 * @return True if the two areas conflict, false otherwise.326 */327 NO_TRACE static bool area_is_conflicting(uintptr_t addr,328 size_t count, bool guarded, as_area_t *area)329 {330 assert((addr % PAGE_SIZE) == 0);331 332 size_t gsize = P2SZ(count);333 size_t agsize = P2SZ(area->pages);334 335 /*336 * A guarded area has one guard page before, one page after.337 * What we do here is: if either area is guarded, we add338 * PAGE_SIZE to the size of both areas. That guarantees339 * they will be spaced at least one page apart.340 */341 if (guarded || (area->flags & AS_AREA_GUARD) != 0) {342 /* Add guard page size unless area is at the end of VA domain */343 if (!overflows(addr, P2SZ(count)))344 gsize += PAGE_SIZE;345 346 /* Add guard page size unless area is at the end of VA domain */347 if (!overflows(area->base, P2SZ(area->pages)))348 agsize += PAGE_SIZE;349 }350 351 return overlaps(addr, gsize, area->base, agsize);352 353 }354 355 279 /** Check area conflicts with other areas. 356 280 * … … 359 283 * @param count Number of pages in the area being tested. 360 284 * @param guarded True if the area being tested is protected by guard pages. 361 * @param avoid Do not touch this area. I.e. this area is not considered 362 * as presenting a conflict. 285 * @param avoid Do not touch this area. 363 286 * 364 287 * @return True if there is no conflict, false otherwise. … … 385 308 386 309 /* 387 * To determine if we overlap with another area, we just need 388 * to look at overlap with the last area with base address <= 389 * to ours and on the first area with base address > than ours. 390 * 391 * First find last area with <= base address. 392 */ 393 odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL); 394 if (odlink != NULL) { 395 as_area_t *area = odict_get_instance(odlink, as_area_t, 396 las_areas); 310 * The leaf node is found in O(log n), where n is proportional to 311 * the number of address space areas belonging to as. 312 * The check for conflicts is then attempted on the rightmost 313 * record in the left neighbour, the leftmost record in the right 314 * neighbour and all records in the leaf node itself. 315 */ 316 btree_node_t *leaf; 317 as_area_t *area = 318 (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf); 319 if (area) { 320 if (area != avoid) 321 return false; 322 } 323 324 /* First, check the two border cases. */ 325 btree_node_t *node = 326 btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); 327 if (node) { 328 area = (as_area_t *) node->value[node->keys - 1]; 397 329 398 330 if (area != avoid) { 399 331 mutex_lock(&area->lock); 400 if (area_is_conflicting(addr, count, guarded, area)) { 332 333 /* 334 * If at least one of the two areas are protected 335 * by the AS_AREA_GUARD flag then we must be sure 336 * that they are separated by at least one unmapped 337 * page. 338 */ 339 int const gp = (guarded || 340 (area->flags & AS_AREA_GUARD)) ? 1 : 0; 341 342 /* 343 * The area comes from the left neighbour node, which 344 * means that there already are some areas in the leaf 345 * node, which in turn means that adding gp is safe and 346 * will not cause an integer overflow. 347 */ 348 if (overlaps(addr, P2SZ(count), area->base, 349 P2SZ(area->pages + gp))) { 401 350 mutex_unlock(&area->lock); 402 351 return false; … … 405 354 mutex_unlock(&area->lock); 406 355 } 407 408 /* Next area */ 409 odlink = odict_next(odlink, &as->as_areas); 410 } 411 412 /* 413 * Next area, if any, is the first with base > than our base address. 414 * If there was no area with <= base, we need to look at the first area. 415 */ 416 if (odlink == NULL) 417 odlink = odict_first(&as->as_areas); 418 419 if (odlink != NULL) { 420 as_area_t *area = odict_get_instance(odlink, as_area_t, 421 las_areas); 356 } 357 358 node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf); 359 if (node) { 360 area = (as_area_t *) node->value[0]; 422 361 423 362 if (area != avoid) { 363 int gp; 364 424 365 mutex_lock(&area->lock); 425 if (area_is_conflicting(addr, count, guarded, area)) { 366 367 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0; 368 if (gp && overflows(addr, P2SZ(count))) { 369 /* 370 * Guard page not needed if the supposed area 371 * is adjacent to the end of the address space. 372 * We already know that the following test is 373 * going to fail... 374 */ 375 gp--; 376 } 377 378 if (overlaps(addr, P2SZ(count + gp), area->base, 379 P2SZ(area->pages))) { 426 380 mutex_unlock(&area->lock); 427 381 return false; … … 430 384 mutex_unlock(&area->lock); 431 385 } 386 } 387 388 /* Second, check the leaf node. */ 389 btree_key_t i; 390 for (i = 0; i < leaf->keys; i++) { 391 area = (as_area_t *) leaf->value[i]; 392 int agp; 393 int gp; 394 395 if (area == avoid) 396 continue; 397 398 mutex_lock(&area->lock); 399 400 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0; 401 agp = gp; 402 403 /* 404 * Sanitize the two possible unsigned integer overflows. 405 */ 406 if (gp && overflows(addr, P2SZ(count))) 407 gp--; 408 if (agp && overflows(area->base, P2SZ(area->pages))) 409 agp--; 410 411 if (overlaps(addr, P2SZ(count + gp), area->base, 412 P2SZ(area->pages + agp))) { 413 mutex_unlock(&area->lock); 414 return false; 415 } 416 417 mutex_unlock(&area->lock); 432 418 } 433 419 … … 496 482 497 483 /* Eventually check the addresses behind each area */ 498 as_area_t *area = as_area_first(as); 499 while (area != NULL) { 500 mutex_lock(&area->lock); 501 502 addr = area->base + P2SZ(area->pages); 503 504 if (guarded || area->flags & AS_AREA_GUARD) { 505 /* 506 * We must leave an unmapped page 507 * between the two areas. 508 */ 509 addr += P2SZ(1); 510 } 511 512 bool avail = 513 ((addr >= bound) && (addr >= area->base) && 514 (check_area_conflicts(as, addr, pages, guarded, area))); 515 516 mutex_unlock(&area->lock); 517 518 if (avail) 519 return addr; 520 521 area = as_area_next(area); 484 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) { 485 486 for (btree_key_t i = 0; i < node->keys; i++) { 487 as_area_t *area = (as_area_t *) node->value[i]; 488 489 mutex_lock(&area->lock); 490 491 addr = 492 ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE); 493 494 if (guarded || area->flags & AS_AREA_GUARD) { 495 /* 496 * We must leave an unmapped page 497 * between the two areas. 498 */ 499 addr += P2SZ(1); 500 } 501 502 bool avail = 503 ((addr >= bound) && (addr >= area->base) && 504 (check_area_conflicts(as, addr, pages, guarded, area))); 505 506 mutex_unlock(&area->lock); 507 508 if (avail) 509 return addr; 510 } 522 511 } 523 512 … … 634 623 635 624 area->as = as; 636 odlink_initialize(&area->las_areas);637 625 area->flags = flags; 638 626 area->attributes = attrs; … … 692 680 693 681 btree_create(&area->used_space); 694 odict_insert(&area->las_areas, &as->as_areas, NULL); 682 btree_insert(&as->as_area_btree, *base, (void *) area, 683 NULL); 695 684 696 685 mutex_unlock(&as->lock); … … 712 701 assert(mutex_locked(&as->lock)); 713 702 714 odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL); 715 if (odlink == NULL) 716 return NULL; 717 718 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas); 719 mutex_lock(&area->lock); 720 721 assert(area->base <= va); 722 723 if (va <= area->base + (P2SZ(area->pages) - 1)) 703 btree_node_t *leaf; 704 as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, 705 &leaf); 706 if (area) { 707 /* va is the base address of an address space area */ 708 mutex_lock(&area->lock); 724 709 return area; 725 726 mutex_unlock(&area->lock); 710 } 711 712 /* 713 * Search the leaf node and the rightmost record of its left neighbour 714 * to find out whether this is a miss or va belongs to an address 715 * space area found there. 716 */ 717 718 /* First, search the leaf node itself. */ 719 btree_key_t i; 720 721 for (i = 0; i < leaf->keys; i++) { 722 area = (as_area_t *) leaf->value[i]; 723 724 mutex_lock(&area->lock); 725 726 if ((area->base <= va) && 727 (va <= area->base + (P2SZ(area->pages) - 1))) 728 return area; 729 730 mutex_unlock(&area->lock); 731 } 732 733 /* 734 * Second, locate the left neighbour and test its last record. 735 * Because of its position in the B+tree, it must have base < va. 736 */ 737 btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, 738 leaf); 739 if (lnode) { 740 area = (as_area_t *) lnode->value[lnode->keys - 1]; 741 742 mutex_lock(&area->lock); 743 744 if (va <= area->base + (P2SZ(area->pages) - 1)) 745 return area; 746 747 mutex_unlock(&area->lock); 748 } 749 727 750 return NULL; 728 751 } … … 962 985 area->backend->destroy(area); 963 986 987 uintptr_t base = area->base; 988 964 989 page_table_lock(as, false); 965 990 … … 1028 1053 * Remove the empty area from address space. 1029 1054 */ 1030 odict_remove(&area->las_areas);1055 btree_remove(&as->as_area_btree, base, NULL); 1031 1056 1032 1057 free(area); … … 1583 1608 1584 1609 return area_flags_to_page_flags(area->flags); 1585 }1586 1587 /** Get key function for the @c as_t.as_areas ordered dictionary.1588 *1589 * @param odlink Link1590 * @return Pointer to task ID cast as 'void *'1591 */1592 static void *as_areas_getkey(odlink_t *odlink)1593 {1594 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);1595 return (void *) &area->base;1596 }1597 1598 /** Key comparison function for the @c as_t.as_areas ordered dictionary.1599 *1600 * @param a Pointer to area A base1601 * @param b Pointer to area B base1602 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B1603 */1604 static int as_areas_cmp(void *a, void *b)1605 {1606 uintptr_t base_a = *(uintptr_t *)a;1607 uintptr_t base_b = *(uintptr_t *)b;1608 1609 if (base_a < base_b)1610 return -1;1611 else if (base_a == base_b)1612 return 0;1613 else1614 return +1;1615 1610 } 1616 1611 … … 2247 2242 mutex_lock(&as->lock); 2248 2243 2249 /* Count number of areas. */ 2250 size_t area_cnt = odict_count(&as->as_areas); 2244 /* First pass, count number of areas. */ 2245 2246 size_t area_cnt = 0; 2247 2248 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2249 node) { 2250 area_cnt += node->keys; 2251 } 2251 2252 2252 2253 size_t isize = area_cnt * sizeof(as_area_info_t); 2253 2254 as_area_info_t *info = nfmalloc(isize); 2254 2255 2255 /* Record areadata. */2256 /* Second pass, record data. */ 2256 2257 2257 2258 size_t area_idx = 0; 2258 2259 2259 as_area_t *area = as_area_first(as); 2260 while (area != NULL) { 2261 assert(area_idx < area_cnt); 2262 mutex_lock(&area->lock); 2263 2264 info[area_idx].start_addr = area->base; 2265 info[area_idx].size = P2SZ(area->pages); 2266 info[area_idx].flags = area->flags; 2267 ++area_idx; 2268 2269 mutex_unlock(&area->lock); 2270 area = as_area_next(area); 2260 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2261 node) { 2262 btree_key_t i; 2263 2264 for (i = 0; i < node->keys; i++) { 2265 as_area_t *area = node->value[i]; 2266 2267 assert(area_idx < area_cnt); 2268 mutex_lock(&area->lock); 2269 2270 info[area_idx].start_addr = area->base; 2271 info[area_idx].size = P2SZ(area->pages); 2272 info[area_idx].flags = area->flags; 2273 ++area_idx; 2274 2275 mutex_unlock(&area->lock); 2276 } 2271 2277 } 2272 2278 … … 2287 2293 2288 2294 /* Print out info about address space areas */ 2289 as_area_t *area = as_area_first(as); 2290 while (area != NULL) { 2291 mutex_lock(&area->lock); 2292 printf("as_area: %p, base=%p, pages=%zu" 2293 " (%p - %p)\n", area, (void *) area->base, 2294 area->pages, (void *) area->base, 2295 (void *) (area->base + P2SZ(area->pages))); 2296 mutex_unlock(&area->lock); 2297 2298 area = as_area_next(area); 2295 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2296 node) { 2297 btree_key_t i; 2298 2299 for (i = 0; i < node->keys; i++) { 2300 as_area_t *area = node->value[i]; 2301 2302 mutex_lock(&area->lock); 2303 printf("as_area: %p, base=%p, pages=%zu" 2304 " (%p - %p)\n", area, (void *) area->base, 2305 area->pages, (void *) area->base, 2306 (void *) (area->base + P2SZ(area->pages))); 2307 mutex_unlock(&area->lock); 2308 } 2299 2309 } 2300 2310
Note:
See TracChangeset
for help on using the changeset viewer.
