Changes in / [ac9e79d:b294126] in mainline
- Location:
- kernel/generic
- Files:
-
- 6 edited
-
include/adt/odict.h (modified) (1 diff)
-
include/mm/as.h (modified) (4 diffs)
-
src/adt/odict.c (modified) (1 diff)
-
src/mm/as.c (modified) (18 diffs)
-
src/proc/task.c (modified) (1 diff)
-
src/sysinfo/stats.c (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/include/adt/odict.h
rac9e79d rb294126 45 45 46 46 extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t); 47 extern void odict_finalize(odict_t *); 47 48 extern void odlink_initialize(odlink_t *); 48 49 extern void odict_insert(odlink_t *, odict_t *, odlink_t *); -
kernel/generic/include/mm/as.h
rac9e79d rb294126 46 46 #include <adt/list.h> 47 47 #include <adt/btree.h> 48 #include <adt/odict.h> 48 49 #include <lib/elf.h> 49 50 #include <arch.h> … … 115 116 mutex_t lock; 116 117 117 /** B+tree of address space areas. */ 118 btree_t as_area_btree; 118 /** Address space areas in this address space by base address. 119 * 120 * Members are of type as_area_t. 121 */ 122 odict_t as_areas; 119 123 120 124 /** Non-generic content. */ … … 204 208 as_t *as; 205 209 210 /** Link to @c as->as_areas */ 211 odlink_t las_areas; 212 206 213 /** Memory flags. */ 207 214 unsigned int flags; … … 273 280 uintptr_t *, uintptr_t); 274 281 extern errno_t as_area_change_flags(as_t *, unsigned int, uintptr_t); 282 extern as_area_t *as_area_first(as_t *); 283 extern as_area_t *as_area_next(as_area_t *); 275 284 276 285 extern unsigned int as_area_get_flags(as_area_t *); -
kernel/generic/src/adt/odict.c
rac9e79d rb294126 204 204 odict->getkey = getkey; 205 205 odict->cmp = cmp; 206 } 207 208 /** Finalize ordered dictionary. 209 * 210 * @param odict Ordered dictionary (must be empty) 211 */ 212 void odict_finalize(odict_t *odict) 213 { 214 assert(odict->root == NULL); 206 215 } 207 216 -
kernel/generic/src/mm/as.c
rac9e79d rb294126 1 1 /* 2 2 * Copyright (c) 2010 Jakub Jermar 3 * Copyright (c) 2018 Jiri Svoboda 3 4 * All rights reserved. 4 5 * … … 111 112 as_t *AS_KERNEL = NULL; 112 113 114 static void *as_areas_getkey(odlink_t *); 115 static int as_areas_cmp(void *, void *); 116 113 117 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags) 114 118 { … … 150 154 (void) as_create_arch(as, 0); 151 155 152 btree_create(&as->as_area_btree);156 odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp); 153 157 154 158 if (flags & FLAG_AS_KERNEL) … … 224 228 /* 225 229 * Destroy address space areas of the address space. 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); 230 * Need to start from the beginning each time since we are destroying 231 * the areas. 232 */ 233 as_area_t *area = as_area_first(as); 234 while (area != NULL) { 235 /* 236 * XXX We already have as_area_t, but as_area_destroy will 237 * have to search for it. This could be made faster. 238 */ 239 as_area_destroy(as, area->base); 240 area = as_area_first(as); 241 } 242 243 odict_finalize(&as->as_areas); 242 244 243 245 #ifdef AS_PAGE_TABLE … … 277 279 } 278 280 281 /** Return first address space area. 282 * 283 * @param as Address space 284 * @return First area in @a as (i.e. area with the lowest base address) 285 * or @c NULL if there is none 286 */ 287 as_area_t *as_area_first(as_t *as) 288 { 289 odlink_t *odlink = odict_first(&as->as_areas); 290 if (odlink == NULL) 291 return NULL; 292 293 return odict_get_instance(odlink, as_area_t, las_areas); 294 } 295 296 /** Return next address space area. 297 * 298 * @param cur Current area 299 * @return Next area in the same address space or @c NULL if @a cur is the 300 * last area. 301 */ 302 as_area_t *as_area_next(as_area_t *cur) 303 { 304 odlink_t *odlink = odict_next(&cur->las_areas, &cur->as->as_areas); 305 if (odlink == NULL) 306 return NULL; 307 308 return odict_get_instance(odlink, as_area_t, las_areas); 309 } 310 311 /** Determine if area with specified parameters would conflict with 312 * a specific existing address space area. 313 * 314 * @param addr Starting virtual address of the area being tested. 315 * @param count Number of pages in the area being tested. 316 * @param guarded True if the area being tested is protected by guard pages. 317 * @param area Area against which we are testing. 318 * 319 * @return True if the two areas conflict, false otherwise. 320 */ 321 NO_TRACE static bool area_is_conflicting(uintptr_t addr, 322 size_t count, bool guarded, as_area_t *area) 323 { 324 assert((addr % PAGE_SIZE) == 0); 325 326 size_t gsize = P2SZ(count); 327 size_t agsize = P2SZ(area->pages); 328 329 /* 330 * A guarded area has one guard page before, one page after. 331 * What we do here is: if either area is guarded, we add 332 * PAGE_SIZE to the size of both areas. That guarantees 333 * they will be spaced at least one page apart. 334 */ 335 if (guarded || (area->flags & AS_AREA_GUARD) != 0) { 336 /* Add guard page size unless area is at the end of VA domain */ 337 if (!overflows(addr, P2SZ(count))) 338 gsize += PAGE_SIZE; 339 340 /* Add guard page size unless area is at the end of VA domain */ 341 if (!overflows(area->base, P2SZ(area->pages))) 342 agsize += PAGE_SIZE; 343 } 344 345 return overlaps(addr, gsize, area->base, agsize); 346 347 } 348 279 349 /** Check area conflicts with other areas. 280 350 * … … 283 353 * @param count Number of pages in the area being tested. 284 354 * @param guarded True if the area being tested is protected by guard pages. 285 * @param avoid Do not touch this area. 355 * @param avoid Do not touch this area. I.e. this area is not considered 356 * as presenting a conflict. 286 357 * 287 358 * @return True if there is no conflict, false otherwise. … … 308 379 309 380 /* 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]; 381 * To determine if we overlap with another area, we just need 382 * to look at overlap with the last area with base address <= 383 * to ours and on the first area with base address > than ours. 384 * 385 * First find last area with <= base address. 386 */ 387 odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL); 388 if (odlink != NULL) { 389 as_area_t *area = odict_get_instance(odlink, as_area_t, 390 las_areas); 329 391 330 392 if (area != avoid) { 331 393 mutex_lock(&area->lock); 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))) { 394 if (area_is_conflicting(addr, count, guarded, area)) { 350 395 mutex_unlock(&area->lock); 351 396 return false; … … 354 399 mutex_unlock(&area->lock); 355 400 } 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]; 401 402 /* Next area */ 403 odlink = odict_next(odlink, &as->as_areas); 404 } 405 406 /* 407 * Next area, if any, is the first with base > than our base address. 408 * If there was no area with <= base, we need to look at the first area. 409 */ 410 if (odlink == NULL) 411 odlink = odict_first(&as->as_areas); 412 413 if (odlink != NULL) { 414 as_area_t *area = odict_get_instance(odlink, as_area_t, 415 las_areas); 361 416 362 417 if (area != avoid) { 363 int gp;364 365 418 mutex_lock(&area->lock); 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))) { 419 if (area_is_conflicting(addr, count, guarded, area)) { 380 420 mutex_unlock(&area->lock); 381 421 return false; … … 384 424 mutex_unlock(&area->lock); 385 425 } 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);418 426 } 419 427 … … 482 490 483 491 /* Eventually check the addresses behind each 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 } 492 as_area_t *area = as_area_first(as); 493 while (area != NULL) { 494 mutex_lock(&area->lock); 495 496 addr = area->base + P2SZ(area->pages); 497 498 if (guarded || area->flags & AS_AREA_GUARD) { 499 /* 500 * We must leave an unmapped page 501 * between the two areas. 502 */ 503 addr += P2SZ(1); 504 } 505 506 bool avail = 507 ((addr >= bound) && (addr >= area->base) && 508 (check_area_conflicts(as, addr, pages, guarded, area))); 509 510 mutex_unlock(&area->lock); 511 512 if (avail) 513 return addr; 514 515 area = as_area_next(area); 511 516 } 512 517 … … 623 628 624 629 area->as = as; 630 odlink_initialize(&area->las_areas); 625 631 area->flags = flags; 626 632 area->attributes = attrs; … … 680 686 681 687 btree_create(&area->used_space); 682 btree_insert(&as->as_area_btree, *base, (void *) area, 683 NULL); 688 odict_insert(&area->las_areas, &as->as_areas, NULL); 684 689 685 690 mutex_unlock(&as->lock); … … 701 706 assert(mutex_locked(&as->lock)); 702 707 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); 708 odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL); 709 if (odlink == NULL) 710 return NULL; 711 712 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas); 713 mutex_lock(&area->lock); 714 715 assert(area->base <= va); 716 717 if (va <= area->base + (P2SZ(area->pages) - 1)) 709 718 return area; 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 719 720 mutex_unlock(&area->lock); 750 721 return NULL; 751 722 } … … 985 956 area->backend->destroy(area); 986 957 987 uintptr_t base = area->base;988 989 958 page_table_lock(as, false); 990 959 … … 1053 1022 * Remove the empty area from address space. 1054 1023 */ 1055 btree_remove(&as->as_area_btree, base, NULL);1024 odict_remove(&area->las_areas); 1056 1025 1057 1026 free(area); … … 1608 1577 1609 1578 return area_flags_to_page_flags(area->flags); 1579 } 1580 1581 /** Get key function for the @c as_t.as_areas ordered dictionary. 1582 * 1583 * @param odlink Link 1584 * @return Pointer to task ID cast as 'void *' 1585 */ 1586 static void *as_areas_getkey(odlink_t *odlink) 1587 { 1588 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas); 1589 return (void *) &area->base; 1590 } 1591 1592 /** Key comparison function for the @c as_t.as_areas ordered dictionary. 1593 * 1594 * @param a Pointer to area A base 1595 * @param b Pointer to area B base 1596 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B 1597 */ 1598 static int as_areas_cmp(void *a, void *b) 1599 { 1600 uintptr_t base_a = *(uintptr_t *)a; 1601 uintptr_t base_b = *(uintptr_t *)b; 1602 1603 if (base_a < base_b) 1604 return -1; 1605 else if (base_a == base_b) 1606 return 0; 1607 else 1608 return +1; 1610 1609 } 1611 1610 … … 2242 2241 mutex_lock(&as->lock); 2243 2242 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 } 2243 /* Count number of areas. */ 2244 size_t area_cnt = odict_count(&as->as_areas); 2252 2245 2253 2246 size_t isize = area_cnt * sizeof(as_area_info_t); 2254 2247 as_area_info_t *info = nfmalloc(isize); 2255 2248 2256 /* Second pass, recorddata. */2249 /* Record area data. */ 2257 2250 2258 2251 size_t area_idx = 0; 2259 2252 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 } 2253 as_area_t *area = as_area_first(as); 2254 while (area != NULL) { 2255 assert(area_idx < area_cnt); 2256 mutex_lock(&area->lock); 2257 2258 info[area_idx].start_addr = area->base; 2259 info[area_idx].size = P2SZ(area->pages); 2260 info[area_idx].flags = area->flags; 2261 ++area_idx; 2262 2263 mutex_unlock(&area->lock); 2264 area = as_area_next(area); 2277 2265 } 2278 2266 … … 2293 2281 2294 2282 /* Print out info about address space areas */ 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 } 2283 as_area_t *area = as_area_first(as); 2284 while (area != NULL) { 2285 mutex_lock(&area->lock); 2286 printf("as_area: %p, base=%p, pages=%zu" 2287 " (%p - %p)\n", area, (void *) area->base, 2288 area->pages, (void *) area->base, 2289 (void *) (area->base + P2SZ(area->pages))); 2290 mutex_unlock(&area->lock); 2291 2292 area = as_area_next(area); 2309 2293 } 2310 2294 -
kernel/generic/src/proc/task.c
rac9e79d rb294126 64 64 IRQ_SPINLOCK_INITIALIZE(tasks_lock); 65 65 66 /** Ordered dictionary of active tasks. 66 /** Ordered dictionary of active tasks by task ID. 67 * 68 * Members are task_t structures. 67 69 * 68 70 * The task is guaranteed to exist after it was found in the @c tasks -
kernel/generic/src/sysinfo/stats.c
rac9e79d rb294126 145 145 size_t pages = 0; 146 146 147 /* Walk the B+ tree and count pages */ 148 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 149 node) { 150 unsigned int i; 151 for (i = 0; i < node->keys; i++) { 152 as_area_t *area = node->value[i]; 153 154 if (mutex_trylock(&area->lock) != EOK) 155 continue; 156 157 pages += area->pages; 158 mutex_unlock(&area->lock); 159 } 147 /* Walk areas in the address space and count pages */ 148 as_area_t *area = as_area_first(as); 149 while (area != NULL) { 150 if (mutex_trylock(&area->lock) != EOK) 151 continue; 152 153 pages += area->pages; 154 mutex_unlock(&area->lock); 155 area = as_area_next(area); 160 156 } 161 157 … … 186 182 size_t pages = 0; 187 183 188 /* Walk the B+ tree and count pages */ 189 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) { 190 unsigned int i; 191 for (i = 0; i < node->keys; i++) { 192 as_area_t *area = node->value[i]; 193 194 if (mutex_trylock(&area->lock) != EOK) 195 continue; 196 197 pages += area->resident; 198 mutex_unlock(&area->lock); 199 } 184 /* Walk areas in the address space and count pages */ 185 as_area_t *area = as_area_first(as); 186 while (area != NULL) { 187 if (mutex_trylock(&area->lock) != EOK) 188 continue; 189 190 pages += area->resident; 191 mutex_unlock(&area->lock); 192 area = as_area_next(area); 200 193 } 201 194
Note:
See TracChangeset
for help on using the changeset viewer.
