Changeset 88cc71c0 in mainline
- Timestamp:
- 2018-11-06T09:39:24Z (6 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- d9d0088
- Parents:
- 4a8d0dd1
- git-author:
- Jiri Svoboda <jiri@…> (2018-10-05 18:38:50)
- git-committer:
- Jiri Svoboda <jiri@…> (2018-11-06 09:39:24)
- 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
r4a8d0dd1 r88cc71c0 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
r4a8d0dd1 r88cc71c0 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
r4a8d0dd1 r88cc71c0 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
r4a8d0dd1 r88cc71c0 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 { … … 156 160 (void) as_create_arch(as, 0); 157 161 158 btree_create(&as->as_area_btree);162 odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp); 159 163 160 164 if (flags & FLAG_AS_KERNEL) … … 230 234 /* 231 235 * Destroy address space areas of the address space. 232 * The B+tree must be walked carefully because it is 233 * also being destroyed. 234 */ 235 bool cond = true; 236 while (cond) { 237 assert(!list_empty(&as->as_area_btree.leaf_list)); 238 239 btree_node_t *node = 240 list_get_instance(list_first(&as->as_area_btree.leaf_list), 241 btree_node_t, leaf_link); 242 243 if ((cond = node->keys)) 244 as_area_destroy(as, node->key[0]); 245 } 246 247 btree_destroy(&as->as_area_btree); 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); 248 250 249 251 #ifdef AS_PAGE_TABLE … … 283 285 } 284 286 287 /** Return first address space area. 288 * 289 * @param as Address space 290 * @return First area in @a as (i.e. area with the lowest base address) 291 * or @c NULL if there is none 292 */ 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 area 305 * @return Next area in the same address space or @c NULL if @a cur is the 306 * 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 with 318 * 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 */ 328 NO_TRACE static bool area_is_conflicting(uintptr_t addr, 329 size_t count, bool guarded, as_area_t *area) 330 { 331 assert((addr % PAGE_SIZE) == 0); 332 333 /* Add guard page size unless area is at the end of VA domain */ 334 size_t gsize = P2SZ(count); 335 if (guarded && !overflows(addr, P2SZ(count))) 336 gsize += PAGE_SIZE; 337 338 /* Add guard page size unless area is at the end of VA domain */ 339 size_t agsize = P2SZ(area->pages); 340 if ((area->flags & AS_AREA_GUARD) != 0 && 341 !overflows(area->base, P2SZ(area->pages))) 342 agsize += PAGE_SIZE; 343 344 return overlaps(addr, gsize, area->base, agsize); 345 346 } 347 285 348 /** Check area conflicts with other areas. 286 349 * … … 289 352 * @param count Number of pages in the area being tested. 290 353 * @param guarded True if the area being tested is protected by guard pages. 291 * @param avoid Do not touch this area. 354 * @param avoid Do not touch this area. I.e. this area is not considered 355 * as presenting a conflict. 292 356 * 293 357 * @return True if there is no conflict, false otherwise. … … 314 378 315 379 /* 316 * The leaf node is found in O(log n), where n is proportional to 317 * the number of address space areas belonging to as. 318 * The check for conflicts is then attempted on the rightmost 319 * record in the left neighbour, the leftmost record in the right 320 * neighbour and all records in the leaf node itself. 321 */ 322 btree_node_t *leaf; 323 as_area_t *area = 324 (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf); 325 if (area) { 326 if (area != avoid) 327 return false; 328 } 329 330 /* First, check the two border cases. */ 331 btree_node_t *node = 332 btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); 333 if (node) { 334 area = (as_area_t *) node->value[node->keys - 1]; 380 * To determine if we overlap with another area, we just need 381 * to look at overlap with the last area with base address <= 382 * to ours and on the first area with base address > than ours. 383 * 384 * First find last area with <= base address. 385 */ 386 odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL); 387 if (odlink != NULL) { 388 as_area_t *area = odict_get_instance(odlink, as_area_t, 389 las_areas); 335 390 336 391 if (area != avoid) { 337 392 mutex_lock(&area->lock); 338 339 /* 340 * If at least one of the two areas are protected 341 * by the AS_AREA_GUARD flag then we must be sure 342 * that they are separated by at least one unmapped 343 * page. 344 */ 345 int const gp = (guarded || 346 (area->flags & AS_AREA_GUARD)) ? 1 : 0; 347 348 /* 349 * The area comes from the left neighbour node, which 350 * means that there already are some areas in the leaf 351 * node, which in turn means that adding gp is safe and 352 * will not cause an integer overflow. 353 */ 354 if (overlaps(addr, P2SZ(count), area->base, 355 P2SZ(area->pages + gp))) { 393 if (area_is_conflicting(addr, count, guarded, area)) { 356 394 mutex_unlock(&area->lock); 357 395 return false; … … 360 398 mutex_unlock(&area->lock); 361 399 } 362 } 363 364 node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf); 365 if (node) { 366 area = (as_area_t *) node->value[0]; 400 401 /* Next area */ 402 odlink = odict_next(odlink, &as->as_areas); 403 } 404 405 /* Next area, if any, is the first with base > than our base address */ 406 if (odlink != NULL) { 407 as_area_t *area = odict_get_instance(odlink, as_area_t, 408 las_areas); 367 409 368 410 if (area != avoid) { 369 int gp;370 371 411 mutex_lock(&area->lock); 372 373 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0; 374 if (gp && overflows(addr, P2SZ(count))) { 375 /* 376 * Guard page not needed if the supposed area 377 * is adjacent to the end of the address space. 378 * We already know that the following test is 379 * going to fail... 380 */ 381 gp--; 382 } 383 384 if (overlaps(addr, P2SZ(count + gp), area->base, 385 P2SZ(area->pages))) { 412 if (area_is_conflicting(addr, count, guarded, area)) { 386 413 mutex_unlock(&area->lock); 387 414 return false; … … 390 417 mutex_unlock(&area->lock); 391 418 } 392 }393 394 /* Second, check the leaf node. */395 btree_key_t i;396 for (i = 0; i < leaf->keys; i++) {397 area = (as_area_t *) leaf->value[i];398 int agp;399 int gp;400 401 if (area == avoid)402 continue;403 404 mutex_lock(&area->lock);405 406 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;407 agp = gp;408 409 /*410 * Sanitize the two possible unsigned integer overflows.411 */412 if (gp && overflows(addr, P2SZ(count)))413 gp--;414 if (agp && overflows(area->base, P2SZ(area->pages)))415 agp--;416 417 if (overlaps(addr, P2SZ(count + gp), area->base,418 P2SZ(area->pages + agp))) {419 mutex_unlock(&area->lock);420 return false;421 }422 423 mutex_unlock(&area->lock);424 419 } 425 420 … … 488 483 489 484 /* Eventually check the addresses behind each area */ 490 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) { 491 492 for (btree_key_t i = 0; i < node->keys; i++) { 493 as_area_t *area = (as_area_t *) node->value[i]; 494 495 mutex_lock(&area->lock); 496 497 addr = 498 ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE); 499 500 if (guarded || area->flags & AS_AREA_GUARD) { 501 /* 502 * We must leave an unmapped page 503 * between the two areas. 504 */ 505 addr += P2SZ(1); 506 } 507 508 bool avail = 509 ((addr >= bound) && (addr >= area->base) && 510 (check_area_conflicts(as, addr, pages, guarded, area))); 511 512 mutex_unlock(&area->lock); 513 514 if (avail) 515 return addr; 516 } 485 as_area_t *area = as_area_first(as); 486 while (area != NULL) { 487 mutex_lock(&area->lock); 488 489 addr = ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE); 490 491 if (guarded || area->flags & AS_AREA_GUARD) { 492 /* 493 * We must leave an unmapped page 494 * between the two areas. 495 */ 496 addr += P2SZ(1); 497 } 498 499 bool avail = 500 ((addr >= bound) && (addr >= area->base) && 501 (check_area_conflicts(as, addr, pages, guarded, area))); 502 503 mutex_unlock(&area->lock); 504 505 if (avail) 506 return addr; 507 508 area = as_area_next(area); 517 509 } 518 510 … … 629 621 630 622 area->as = as; 623 odlink_initialize(&area->las_areas); 631 624 area->flags = flags; 632 625 area->attributes = attrs; … … 686 679 687 680 btree_create(&area->used_space); 688 btree_insert(&as->as_area_btree, *base, (void *) area, 689 NULL); 681 odict_insert(&area->las_areas, &as->as_areas, NULL); 690 682 691 683 mutex_unlock(&as->lock); … … 707 699 assert(mutex_locked(&as->lock)); 708 700 709 btree_node_t *leaf; 710 as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, 711 &leaf); 712 if (area) { 713 /* va is the base address of an address space area */ 714 mutex_lock(&area->lock); 701 odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL); 702 if (odlink == NULL) 703 return NULL; 704 705 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas); 706 mutex_lock(&area->lock); 707 708 assert(area->base <= va); 709 710 if (va <= area->base + (P2SZ(area->pages) - 1)) 715 711 return area; 716 } 717 718 /* 719 * Search the leaf node and the rightmost record of its left neighbour 720 * to find out whether this is a miss or va belongs to an address 721 * space area found there. 722 */ 723 724 /* First, search the leaf node itself. */ 725 btree_key_t i; 726 727 for (i = 0; i < leaf->keys; i++) { 728 area = (as_area_t *) leaf->value[i]; 729 730 mutex_lock(&area->lock); 731 732 if ((area->base <= va) && 733 (va <= area->base + (P2SZ(area->pages) - 1))) 734 return area; 735 736 mutex_unlock(&area->lock); 737 } 738 739 /* 740 * Second, locate the left neighbour and test its last record. 741 * Because of its position in the B+tree, it must have base < va. 742 */ 743 btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, 744 leaf); 745 if (lnode) { 746 area = (as_area_t *) lnode->value[lnode->keys - 1]; 747 748 mutex_lock(&area->lock); 749 750 if (va <= area->base + (P2SZ(area->pages) - 1)) 751 return area; 752 753 mutex_unlock(&area->lock); 754 } 755 712 713 mutex_unlock(&area->lock); 756 714 return NULL; 757 715 } … … 991 949 area->backend->destroy(area); 992 950 993 uintptr_t base = area->base;994 995 951 page_table_lock(as, false); 996 952 … … 1059 1015 * Remove the empty area from address space. 1060 1016 */ 1061 btree_remove(&as->as_area_btree, base, NULL);1017 odict_remove(&area->las_areas); 1062 1018 1063 1019 free(area); … … 1614 1570 1615 1571 return area_flags_to_page_flags(area->flags); 1572 } 1573 1574 /** Get key function for the @c as_t.as_areas ordered dictionary. 1575 * 1576 * @param odlink Link 1577 * @return Pointer to task ID cast as 'void *' 1578 */ 1579 static void *as_areas_getkey(odlink_t *odlink) 1580 { 1581 as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas); 1582 return (void *) &area->base; 1583 } 1584 1585 /** Key comparison function for the @c as_t.as_areas ordered dictionary. 1586 * 1587 * @param a Pointer to area A base 1588 * @param b Pointer to area B base 1589 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B 1590 */ 1591 static int as_areas_cmp(void *a, void *b) 1592 { 1593 uintptr_t base_a = *(uintptr_t *)a; 1594 uintptr_t base_b = *(uintptr_t *)b; 1595 1596 if (base_a < base_b) 1597 return -1; 1598 else if (base_a == base_b) 1599 return 0; 1600 else 1601 return +1; 1616 1602 } 1617 1603 … … 2248 2234 mutex_lock(&as->lock); 2249 2235 2250 /* First pass, count number of areas. */ 2251 2252 size_t area_cnt = 0; 2253 2254 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2255 node) { 2256 area_cnt += node->keys; 2257 } 2236 /* Count number of areas. */ 2237 size_t area_cnt = odict_count(&as->as_areas); 2258 2238 2259 2239 size_t isize = area_cnt * sizeof(as_area_info_t); 2260 2240 as_area_info_t *info = nfmalloc(isize); 2261 2241 2262 /* Second pass, recorddata. */2242 /* Record area data. */ 2263 2243 2264 2244 size_t area_idx = 0; 2265 2245 2266 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2267 node) { 2268 btree_key_t i; 2269 2270 for (i = 0; i < node->keys; i++) { 2271 as_area_t *area = node->value[i]; 2272 2273 assert(area_idx < area_cnt); 2274 mutex_lock(&area->lock); 2275 2276 info[area_idx].start_addr = area->base; 2277 info[area_idx].size = P2SZ(area->pages); 2278 info[area_idx].flags = area->flags; 2279 ++area_idx; 2280 2281 mutex_unlock(&area->lock); 2282 } 2246 as_area_t *area = as_area_first(as); 2247 while (area != NULL) { 2248 assert(area_idx < area_cnt); 2249 mutex_lock(&area->lock); 2250 2251 info[area_idx].start_addr = area->base; 2252 info[area_idx].size = P2SZ(area->pages); 2253 info[area_idx].flags = area->flags; 2254 ++area_idx; 2255 2256 mutex_unlock(&area->lock); 2257 area = as_area_next(area); 2283 2258 } 2284 2259 … … 2299 2274 2300 2275 /* Print out info about address space areas */ 2301 list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, 2302 node) { 2303 btree_key_t i; 2304 2305 for (i = 0; i < node->keys; i++) { 2306 as_area_t *area = node->value[i]; 2307 2308 mutex_lock(&area->lock); 2309 printf("as_area: %p, base=%p, pages=%zu" 2310 " (%p - %p)\n", area, (void *) area->base, 2311 area->pages, (void *) area->base, 2312 (void *) (area->base + P2SZ(area->pages))); 2313 mutex_unlock(&area->lock); 2314 } 2276 as_area_t *area = as_area_first(as); 2277 while (area != NULL) { 2278 mutex_lock(&area->lock); 2279 printf("as_area: %p, base=%p, pages=%zu" 2280 " (%p - %p)\n", area, (void *) area->base, 2281 area->pages, (void *) area->base, 2282 (void *) (area->base + P2SZ(area->pages))); 2283 mutex_unlock(&area->lock); 2284 2285 area = as_area_next(area); 2315 2286 } 2316 2287 -
kernel/generic/src/proc/task.c
r4a8d0dd1 r88cc71c0 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
r4a8d0dd1 r88cc71c0 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.
