Changeset c8fccf5 in mainline
- Timestamp:
- 2012-11-06T23:24:45Z (12 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 2708f6a
- Parents:
- f048658
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/cht.c
rf048658 rc8fccf5 2349 2349 * cas(x, 0 -> 1), succeeds 2350 2350 * cas(x, 0 -> 1), fails 2351 * MB 2351 * MB, to order load of x in cas and store to y 2352 2352 * y = 7 2353 2353 * sees y == 7 … … 2355 2355 * 2356 2356 * If cas() did not work this way: 2357 * -our head move protocol would not be correct.2358 * -freeing an item linked to a moved head after another item was2357 * a) our head move protocol would not be correct. 2358 * b) freeing an item linked to a moved head after another item was 2359 2359 * inserted in front of it, would require more than one grace period. 2360 */ 2361 void *ret = atomic_cas_ptr((void**)link, (void *)cur, (void *)new); 2362 return (marked_ptr_t) ret; 2360 * 2361 * Ad (a): In the following example, cpu1 starts moving old_head 2362 * to new_head, cpu2 completes the move and cpu3 notices cpu2 2363 * completed the move before cpu1 gets a chance to notice cpu2 2364 * had already completed the move. Our requirements for cas() 2365 * assume cpu3 will see a valid and mutable value in new_head 2366 * after issuing a load memory barrier once it has determined 2367 * the old_head's value had been successfully moved to new_head 2368 * (because it sees old_head marked invalid). 2369 * 2370 * cpu1 cpu2 cpu3 2371 * cas(old_head, <addr, N>, <addr, Const>), succeeds 2372 * cas-order-barrier 2373 * // Move from old_head to new_head started, now the interesting stuff: 2374 * cas(new_head, <0, Inv>, <addr, N>), succeeds 2375 * 2376 * cas(new_head, <0, Inv>, <addr, N>), but fails 2377 * cas-order-barrier 2378 * cas(old_head, <addr, Const>, <addr, Inv>), succeeds 2379 * 2380 * Sees old_head marked Inv (by cpu2) 2381 * load-MB 2382 * assert(new_head == <addr, N>) 2383 * 2384 * cas-order-barrier 2385 * 2386 * Even though cpu1 did not yet issue a cas-order-barrier, cpu1's store 2387 * to new_head (successful cas()) must be made visible to cpu3 with 2388 * a load memory barrier if cpu1's store to new_head is visible 2389 * on another cpu (cpu2) and that cpu's (cpu2's) store to old_head 2390 * is already visible to cpu3. * 2391 */ 2392 void *expected = (void*)cur; 2393 2394 /* 2395 * Use the acquire-release model, although we could probably 2396 * get away even with the relaxed memory model due to our use 2397 * of explicit memory barriers. 2398 */ 2399 __atomic_compare_exchange_n((void**)link, &expected, (void *)new, false, 2400 __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE); 2401 2402 return (marked_ptr_t) expected; 2363 2403 } 2364 2404
Note:
See TracChangeset
for help on using the changeset viewer.