Title: Theory / Unimportant / CS / Programming / Rust / Atomics and locks

Typ: Send
Meaning: Trait of types whose ownership can be sent to another thread
Page: https://doc.rust-lang.org/book/ch16-03-shared-state.html
https://marabos.nl/atomics/basics.html
Language: Rust
Chapter: 16

Name: Sync
Definition: Trait indicating that a type can be referenced in multiple thread
Page: https://doc.rust-lang.org/book/ch16-03-shared-state.html
https://marabos.nl/atomics/basics.html
Chapter: 16
Context: Rust
Definition2: Type T such that &T is Send
Example: primitive types
Example2: Types composed uniquely of primitive types

Name: The main thread
Definition: The thread executing `main`
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Instruction: std::thread::spawn(f)
Page: https://marabos.nl/atomics/basics.html
Effect: Execute f in a new thread
Context: Rust
Chapter: 1
Assuming: f has static lifetime

Instruction: std::thread::current()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: The current thread

Instruction: thread.id()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: The id of the current thread
Variables: thread thread

Question: What can be done with thread ids
Answer: only comparing for equality and assigning them
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Variables: thread thread
Context: Rust

Instruction: thread.join()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: Waits for thread to ends, with the potential panick message
Variables: thread thread

Instruction: tsd::thread::scope(f)
Page: https://marabos.nl/atomics/basics.html
Effect: Execute f(s) with s the current scope
Context: Rust
Chapter: 1
Variables: thread thread

Instruction: s.spawn(f)
Page: https://marabos.nl/atomics/basics.html
Effect: Execute f
Context: Rust
Chapter: 1
Returns: The created thread id
Variables: scope s
Assuming: f don't outlive current scope

Instruction: Box::leak(value)
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: value on the stack, with static duration, undroppable

Question: What are the way to share ownership
Answer: static value
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Answer2: Box::leak value
Answer3: Reference counting with Arc

Instruction: std::rc::Rc::new(value)
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: An object, owning value, that can have multiple owner. Gets dropped when last owner drop it.

Instruction: std::rc::Arc::new(value)
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: A thread safe object, owning value, that can have multiple owner. Gets dropped when last owner drop it.

Instruction: ref.clone()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: Another reference to the same value as ref
Variables: ref: std::rc::Arc<T>

Question: What's the best name for a clone of a Rc or Arc named ref
Answer: Also ref, shadowing the original value
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Variables: ref: std::rc::Arc<T>
Context: Rust

Name: Immutable reference
Definition: A reference that allows other reference to the same object to exists
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Name2: Shared reference

Name: Mutable reference
Definition: A reference such that no other reference can be made to the object, and the object can't be directly used either
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Definition2: Exclusive reference

Typ: std::cell:Cell<T>
Meaning: A container of a value of type T, that can still be mutated, but only used in a single thread
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Instruction: cell.get()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: A copy of the value contained in cell
Variables: cell: std::cell::Cell<T>
Assuming: T is copyable

Instruction: cell.Take()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: The value contained in cell, leaving it with a new default value
Variables: cell: std::cell::Cell<T>
Assuming: T is copyable

Instruction: cell.set(v)
Page: https://marabos.nl/atomics/basics.html
Effect: change the value of cell to v
Context: Rust
Chapter: 1
Variables: cell: std::cell::Cell<T>
Assuming: T is copyable

Instruction: refScell.borrow_mut()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: A mut ref to the value in refCell
Variables: refCell: std::cell::RefCell<T>
Assuming: T is copyable

Typ: std::Refcell:Cell<T>
Meaning: A single-threaded container of a value of type T, that can be borrowed, but check borrow rules at runtime
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Typ: RwLock<T>
Meaning: A concurrent RefCell, whose borrow sleed until it can be satisifed
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Name: Reader-writer lock

Instruction: rwLock.borrow()
Page: https://marabos.nl/atomics/basics.html
Effect: Sleep until borrow can occur
Context: Rust
Chapter: 1
Returns: A reference to the value owned by rwLock
Variables: rwLock: RwLock<T>
Name: Locking

Typ: std::sync::Mutex<T>
Meaning: Similar to RwLock<T>, but with exclusive borrow only
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Name: T with Mutual Exclusion

Typ: AtomicT
Meaning: A thread safe container of a value of type T, that the processor allow to atomically access and mutate
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Typ: UnsafeCell<T>
Meaning: A cell that can only be used in unsafe environment, that does no check
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Typ: std::marker::PhatonData<T>
Meaning: Treated as type T but does not actually exists
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Question: How to get Send/Sync types
Answer: primitive atomic type
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Answer2: Struct using only Send/Sync type
Answer3: unsafe impl

Name: A poisoned mutex
Definition: A mutex which was locked by a thread, while the thread panicked
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Instruction: std::thread::park()
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: Park the current thread.

Instruction: t.thread.unpark(thread_id)
Page: https://marabos.nl/atomics/basics.html
Context: Rust
Chapter: 1
Returns: Unpark t, or cancel its next park()
Variables: t a thread

Name: A parked thread
Definition: A thread that is sleeping, waiting for another thread to wake it up
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust

Typ: std::sync::Condvar
Meaning: A variable that can transmit notification and wait for notifications
Page: https://marabos.nl/atomics/basics.html
Chapter: 1
Context: Rust
Name: Condition variable

Instruction: condvar.wait(lock)
Page: https://marabos.nl/atomics/basics.html
Effect: unlock lock, wait until condvar receives a notification, locks again
Context: Rust
Chapter: 1
Returns: The new lock, in a Result
Variables: condvar: Condvar

Instruction: condvar.notify_one()
Page: https://marabos.nl/atomics/basics.html
Effect: notify one place condvar is waiting
Context: Rust
Chapter: 1
Variables: condvar: Condvar

Instruction: condvar.notify_all()
Page: https://marabos.nl/atomics/basics.html
Effect: notify each place condvar is waiting
Context: Rust
Chapter: 1
Variables: condvar: Condvar

Typ: std::sync::atomic::Ordering
Meaning: The level of guarantee one request regarding atomic operation
Page: https://marabos.nl/atomics/atomics.html
Chapter: 2
Context: Rust
Variables: condvar: Condvar

Instruction: at.load(ordering)
Page: https://marabos.nl/atomics/atomics.html
Context: Rust
Chapter: 2
Returns: The value stored in at
Variables: at: AtomicT

Instruction: at.store(value, ordering)
Page: https://marabos.nl/atomics/atomics.html
Effect: set the value in at to value
Context: Rust
Chapter: 2
Returns: The value stored in at
Variables: at: AtomicT

Instruction: thread.park_timeout(duration)
Page: https://marabos.nl/atomics/atomics.html
Effect: Park for at most duration
Context: Rust
Chapter: 2

Instruction: at.fetch_op(arg, ordering)
Page: https://marabos.nl/atomics/atomics.html
Effect: set the value to (*at `op` arg)
Context: Rust
Chapter: 2
Returns: The value previously stored in at
Variables: at: AtomicT

Instruction: at.swap(value, ordering)
Page: https://marabos.nl/atomics/atomics.html
Effect: set the value in at to value
Context: Rust
Chapter: 2
Returns: The value previously stored in at
Variables: at: AtomicT

Instruction: at.compare_exchange(expected, new, success_ordering, failure_order)
Page: https://marabos.nl/atomics/atomics.html
Effect: Atomically set at to new IF it is expected
Context: Rust
Chapter: 2
Returns: The value previously stored in at
Variables: at: AtomicT

Page: https://marabos.nl/atomics/atomics.html
Implementation: fn atomic_f(at: &AtomicT) {
    let mut current = at.load(Relaxed);
    loop {
        let new = f(current);
        match at.compare_exchange(current, new, Relaxed, Relaxed) {
            Ok(_) => return current,
            Err(v) => current = v,
        }
    }
}
Chapter: 2
Variables: f(T) -> T
Returns: Atomically applies f to its argument
Context: Rust
Assuming: f is purely functional

Instruction: at.fetch_update(ordering, ordering, f)
Page: https://marabos.nl/atomics/atomics.html
Effect: atomically applies f to at
Context: Rust
Chapter: 2
Variables: at: AtomicT
f(T) -> T
Assuming: f behaves correctly if at is set multiple time to the same value

Page: https://marabos.nl/atomics/memory-ordering.html
Definition: instr1 is garanteed to happens before instr2
Chapter: 3
Variables: instr1, instr2
Name: instr1 happens-before instr2
Context: Rust
Example: instruction in the same function, or in function called
Assuming: f behaves correctly if at is set multiple time to the same value
Example2: code before a spawn, and code executed in the thread, and code after join

Name: out-of-thin-air value
Definition: A case where the memory model allow to create new value due to concurrency issues, while actually this can't occur.
Page: https://marabos.nl/atomics/memory-ordering.html
Chapter: 3
Context: Rust
Example: static X: AtomicI32 = AtomicI32::new(0);
static Y: AtomicI32 = AtomicI32::new(0);
fn main() {
    let a = thread::spawn(|| {
        let x = X.load(Relaxed);
        Y.store(x, Relaxed);
    });
    let b = thread::spawn(|| {
        let y = Y.load(Relaxed);
        X.store(y, Relaxed);
    });
    a.join().unwrap();
    b.join().unwrap();
    assert_eq!(X.load(Relaxed), 0); // Might fail?
    assert_eq!(Y.load(Relaxed), 0); // Might fail?
}
Assuming: f behaves correctly if at is set multiple time to the same value

Constant: Release
Meaning: This is in happen-before relation with any Acquire reading the same value
Page: https://marabos.nl/atomics/memory-ordering.html
Language: Rust
Context: Atomic ordering

Constant: Acquire
Meaning: This is the "after" part of the happen-before relation with any RELEASE storing the same value
Page: https://marabos.nl/atomics/memory-ordering.html
Language: Rust
Context: Atomic ordering

Constant: Ordering::Consume
Meaning: A version of Ordering::Acquire, limited to only expressinos depending on the curently acquired value
Page: https://marabos.nl/atomics/memory-ordering.html
Language: Rust
Context: Atomic ordering
Extra: Implemented as Acquire, because actually defining it properly is not known today

Constant: Ordering::SeqCst
Meaning: this operation is ordered in a way all threads agree on
Page: https://marabos.nl/atomics/memory-ordering.html
Language: Rust
Context: Atomic ordering
Extra: Sequentially Consistent Ordering

Instruction: std::sync::atomic::fence(Ordering)
Page: https://marabos.nl/atomics/memory-ordering.html
Effect: Similar to an atomic operation with Ordering, but not touching any atomic store
Language: Rust

Instruction: std::sync::atomic::compiler_fence(Ordering)
Page: https://marabos.nl/atomics/memory-ordering.html
Effect: Similar to an atomic operation with Ordering, but not touching any atomic store, and limited to compiler. Processer can reorder freely
Language: Rust

Question: Why disabling optimization does not stop out-of-order execution
Answer: because the processor also execute out-of-order
Page: https://marabos.nl/atomics/memory-ordering.html
Chapter: Rust

Typ: SpinLock
Meaning: A lock, that does not sleep, but retry locking until it succeed
Page: https://marabos.nl/atomics/memory-ordering.html
Context: Rust
Intuition: Useful if we expect lock to be short lived, as going to sleep and waking up is costly

Instruction: std::hint::spin_loop()
Page: https://marabos.nl/atomics/memory-ordering.html
Effect: Tells the processor we are waiting for something, so other thread can be prioritized
Context: Rust

Question: How to ensure, using the type system, that a function is the last thing to occur on an object
Answer: this function should take the object by value and not reference (assuming the value is not Copy)
Page: https://marabos.nl/atomics/building-channels.html
Context: Rust

Typ: std:: mem:: MaybeUninit<T>
Meaning: T but potentially unitialized
Page: https://marabos.nl/atomics/building-channels.html
Context: Rust

Typ: std::ptr::NonNull<T>
Meaning: A non-null pointer to T
Page: https://marabos.nl/atomics/building-channels.html
Context: Rust

Name: Miri
Definition: tool to check unsafe code for various forms of undefined behavior.
Page: https://marabos.nl/atomics/building-arc.html
Context: Rust

Question: If you want to implement a method m on Foo<T>, how to ensure ft.m() is not implemented as ft.deref().m()?
Answer: Implement a function m that does not take self as argument, but a regular argument.
Page: https://marabos.nl/atomics/building-arc.html
Variables: impl<T> Deref for Foo<T> {
  type Target  T;
  ...
}
ft: Foo<T>
Context: Rust

Typ: std::mem::ManuallyDrop<T>
Meaning: A value of type T that can be manually droped any time
Page: https://marabos.nl/atomics/building-arc.html
Context: Rust

Name: Cache coherence protocol
Definition: a protocol defines how exactly the caches operate and communicate with each other to keep everything in a consistent state.
Page: https://marabos.nl/atomics/hardware.html
Context: Rust

Name: write-through cache coherence protocol
Definition: writes are not cached but immediately sent through to the next layer. Every caches listen to write, in order to update immediately
Page: https://marabos.nl/atomics/hardware.html
Context: Rust

Name: MESI cache coherence protocol
Definition: A protocol where a cache asks caches of the same level if they have the requested memory, before asking next level. If so, note the cache as Shared.
Page: https://marabos.nl/atomics/hardware.html
Context: Rust
Etymology: Modified, Exclusive, Shared, Invalid

Name: Modified mode
Definition: used for cache lines that contain data that has been modified but not yet written to memory
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Name: Exclusive mode
Definition: Cache lines that contain unmodified data that's not cahchen id any other cache (at the same level)
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Name: Shared mode
Definition: Unmodified cache line that might also appear in one or more of the other (same level) caches
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Name: Invalid state
Definition: Unused cache lines
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Question: How does MESI protocol deals with cach misses
Answer: Asks other cache at the same level for the data. If it gets it, they are in shared mode now
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache
Answer2: Otherwise, gets data from lower level, in Exclusive mode

Question: How does MESI protocol in Exclusive mode deals with write
Answer: Does the write locally and move to Modified mode
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Question: How does MESI protocol in Shared mode deals with write
Answer: Ask other cache to move this line to Invalid, and write it, in Modified mode
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Question: How does MESI protocol in Modified mode deals with data request
Answer: It writes the line to lower level and send it to the other cache who did the request
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Question: How does MESI protocol in Exclusive mode deals with data request
Answer: It moves to shared mode and send the data as it to the other cache
Page: https://marabos.nl/atomics/hardware.html
Context: MESI cache

Instruction: std::hint::black_box(i)
Page: https://marabos.nl/atomics/hardware.html
Effect: identity function, that can't be optimized in any way
Context: Rust

Instruction: #[repr(align(n))]
struct StructDef;
Page: https://marabos.nl/atomics/hardware.html
Meaning: This must be aligned at, at least, multiple of n
Language: Rust
Similar to: struct StructDef;

Question: Why can store/load on different variables can be as slow as store/load on the same variable
Answer: Because both variables are on the same cache line
Page: https://marabos.nl/atomics/hardware.html
Context: Rust

Name: Other-multi-copy atomicity
Definition: write operations, once they are visible to any core, become visible to all cores at the same time.
Page: https://marabos.nl/atomics/hardware.html
Context: Rust

Question: Examples of case where a struct can't be moved
Answer: It has pointer to its adress.
Page: https://marabos.nl/atomics/os-primitives.html

Question: How to deal with object that should not be moved
Answer: Encapsulate them in a Box<>
Page: https://marabos.nl/atomics/os-primitives.html
Context: Rust

Name: Priority inversion
Definition: When a high priority thread waits on a low priority one
Page: https://marabos.nl/atomics/os-primitives.html
Context: Rust

Name: Priority inheritance
Definition: Ensuring that every thread has a priority at least as high as every thread depending on it
Page: https://marabos.nl/atomics/os-primitives.html
Context: Rust

Name: A robust mutex
Definition: a mutex that can gracefully handle a situation where its "owning" thread unexpectedly terminates.
Page: https://marabos.nl/atomics/os-primitives.html
Context: Rust

Instruction: #[cold]
Page: https://marabos.nl/atomics/os-primitives.html
Effect: Tells the compiler the next function is rarely called
Context: Rust

Instruction: #[inline]
Page: https://marabos.nl/atomics/os-primitives.html
Effect: Tells the compiler the next function definition should be inlined if possible for efficiency
Context: Rust