# Get familiar with Rust

/*
 * struct bar {
 *   unsigned long x;
 * }
 *
 */
struct Bar {
    x: usize, 
}

/*
 * struct foo {
 *   struct bar b;
 *   int c;
 * }
 */
struct Foo {
    b: Bar
    c: i32
}

/* Generic types
 *
 * in C we usuall do
 * 
 * struct foo {
 *   spinlock_t lock;
 *   struct bar b;
 *   int c;
 * }
 */
struct Lock<T> {
    lock: SpinLock,
    data: UnsafeCell<T>,
}

// struct foo foo = ...;
let foo: SpinLock<Foo> = ...;

## Notations

* `T1` -> `T2`: describe a function type, sometimes it's useful to say we want to have a function with a certain type. For example `kzalloc()` is `size_t` -> `void *`

## References and borrows
* `&T`: immutable reference: Read-only, can have multiple immutable references
* `&expr`: immutable borrow: gives an immutable reference.

// struct foo *foo = &some_foo;
let foo: &Foo = &some_foo;

let b: &Foo = &some_foo;

// int c = foo->c;
let c: i32 = foo.c;

* `&mut T`: mutable reference: Exclusive, can only have one.
* `&mut expr`: mutable borrow: gives a mutable reference.

// struct foo *foo = &some_foo;
let foo: &mut Foo = &mut some_foo;

// let b: &i32 = &some_foo; // won't compile
// let b: &mut i32 = &mut some_foo; // won't compile either

// foo->b->x = 1
foo.b.x = 1;

// *foo = struct foo { ... };
*foo = Foo { b: Bar {x : 1}, c: 12};

## Pointer and `unsafe`
* `*const T`: const pointer
* `*mut T`: mutable pointer
* `*mut T` <-> `*const T`, can cast to each other freely.
* dereference of a pointer is `unsafe`, since compiler cannot guarantee no-UB.

let foo: *const Foo = &some_foo; // borrow expr can also provide a pointer

let c = unsafe { *foo }; // only work if Foo is Copy.

let reborrow: &Foo = unsafe { &*foo };

Note that having a `&mut` and `&` reference to the same location is generally considered as undefined behavior (bad bad):

let global_ptr: *const i32 = &something;

<thread 1>                <thread 2>
let x = unsafe { &mut *(global_ptr as *mut i32)};
                         
                          let y = unsafe { &*global_ptr };

## Method and `&self`/`&mut self`

impl Foo {
    // void set_c(struct foo *self, int new)
    pub fn set_c(&mut self, new: i32) {
        self.c = new;
    }
    
    // int get_c(struct foo *self)
    pub fn get_c(&self) -> i32 {
        self.c
    }
}

## interior mutable and `UnsafeCell`

How do I design a data type that support accesses from multiple threads?

* Attempt #1

impl Foo {
    pub fn set_c(&mut self, new: i32) { ... }
}

It doesn't work since previously we said having multiple mutable references is UB.

* Attempt #2

impl Foo {
    pub fn set_c(&self, new: i32) {
        self.c = new; // ERROR, we cannot modify self.
    }
}

* Building block: interior mutable, for example atomics

impl<T> AtomicPtr<T> {
    pub fn load(&self, ...) -> *mut T
    pub fn store(&self, new: *mut T, ...);
}

The "read" and "write" to the data must be done via some API taking `&self` (and there is some synchronization behind it)

* Try interior mutable

struct Foo {
    lock: SpinLock,
    b: Bar;
    c: i32;
}

impl Foo {
    pub fn set_c(&self, new: i32) { 
        self.lock.lock();
        self.c = new; // STILL not working
        self.lock.unlock();
    }
}

* Building block: `UnsafeCell<T>`

`&T` and `&UnsafeCell<T>` are treated differently in the language.

impl<T> UnsafeCell<T> {
    fn get(&self) -> *mut T;
}

struct Foo {
    lock: SpinLock,
    b: Bar;
    c: UnsafeCell<i32>;
}

impl Foo {
    pub fn set_c(&self, new: i32) {
        self.lock.lock();
        unsafe { *self.c.get() } = new;
        self.lock.unlock();
    }
}

## Lock and Guard

struct Lock<T> {
    lock: SpinLock;
    data: UnsafeCell<T>;
}

impl<T> Lock<T> {
    fn lock(&self) -> Guard<'_, T> {
        // spin_lock(&self->lock);
        self.lock.lock();
        
        return Guard { locked: self };
    }
}

struct Guard<'a, T> {
    lock: &'a Lock<T>
}

impl<'a, T> Drop for Guard<'a, T> {
    fn drop(&mut self) {
        // spin_unlock(&self->lock)
        self.locked.unlock();
    }
}

let foo: &'1 Lock<Foo> = ..;

let guard: &'2 Guard<'_, Foo> = foo.lock(); // '1 outlives '2

// use guard to access the locked data; 

drop(guard); // unlock

## `Deref` and `DerefMut`
Define pointer/reference-like type

impl<'a, T> Deref for Guard<'a, T> {
    type Target = T;
    
    fn deref(&self) -> &Self::Target {
        let ptr = self
                    .locked // => &Lock<T>
                    .data // => &UnsafeCell<T>
                    .get(); // *mut T
        // SAFETY: the existence of the Guard means
        // we hold the lock.
        unsafe { &*ptr }
    }
}

impl<'a, T> DerefMut for Guard<'a, T> {
    fn deref_mut(&self) -> &mut Self::Target {
        let ptr = self
                    .locked // => &Lock<T>
                    .data // => &UnsafeCell<T>
                    .get(); // *mut T
        // SAFETY: the existence of the Guard means
        // we hold the lock.
        unsafe { &mut *ptr }
    }
}

let foo: &'1 Lock<Foo> = ..;

let guard: &'2 Guard<'_, Foo> = foo.lock(); // '1 outlives '2

let foo_ref: &'3 Foo = guard.deref();
drop(foo_ref); // '3 ends here

let foo_mut: &'4 Foo = guard.deref_mut();
foo_mut.c = 11;
drop(foo_mut); // '4 ends here

guard.c = 11; // works as well

// use guard to access the locked data; 

drop(guard); // '2 ends here, unlock

# Here comes RCU

struct RcuReadGuard;

fn read_lock() -> RcuReadGuard {
    // rcu_read_lock()
    rcu_read_lock();
    
    return RcuReadGuard;
}

impl Drop for RcuReadGuard {
    fn drop(&mut self) {
        rcu_read_unlock();
    }
}

let reader: RcuReadGuard = read_lock();
// RCU read-side critical section
//drop(reader);

## RCU pointer API

/// A RCU protected pointer
/*
 * struct rcu {
 *   void *ptr;
 * }
 */
struct Rcu<T> {
    ptr: AtomicPtr<T>
}

impl<T> Rcu<T> {
    // rcu_dereference()
    fn dereference<'a, 'rcu: 'a>(&'a self, &'rcu RcuReadGuard) -> &'a T {
        unsafe { &*ptr.load(Acquire) };
    }
    
    // rcu_assign_pointer()
    fn swap(&self, new: *mut T) -> RcuOld<T> {
        // xchg_acqrel(self->ptr, new)
        let old_ptr = ptr.swap(new, AcqRel);
        
        return RcuOld { old_ptr };
    }
}

struct RcuOld<T> {
    ptr: *mut T
}

impl<T> Drop for RcuOld<T> {
    fn drop(&mut self) {
        synchronize_rcu();
        // and then we can free the object
    }
}

let r: &Rcu<i32> = ..;

let rcu_guard = read_lock();

let x: &'2 i32 = r.dereference(r, &'1 rcu_guard); // '1 outlives than '2

// drop(rcu_guard); ERROR

let v: i32 = *x;

## RCU pointer in a type

/*
 * struct foo {
 *   int a;
 *   struct bar __rcu *b;
 *   int __rcu *c;
 * }
 */
struct Foo {
    lock: SpinLock,
    a: i32,
    //a_: AtomicI32,
    b: Rcu<Bar>,
    c: Rcu<i32>,
}

/*
 * struct foo {
 *   spinlock_t lock;
 *   int a;
 *   struct bar __rcu *b;
 *   int __rcu *c;
 * }
 */
Lock<Foo>
NoLock<Foo>

We can certainly have a function do
* `Guard<'_, Foo>` -> `&Rcu<Bar>`

but we also want a:
* `&Lock<Foo>` -> `&Rcu<Bar>` for lockless reader.

`Guard<'_, Foo>` can be treated as `&mut Foo`, and `&Lock<Foo>` can be treated as `&Foo`. And the above two functions can run in the same time. Remember `&mut` and `&` at the same time is consider UB?

## Problem recap

* If we have a `Lock<Foo>`, we can get a `Guard<Foo>`
* `Guard<Foo>` can produce a `&mut Foo`, which allows us to access `Foo` freely (read and write)
* However, `&mut Foo` assumes no concurrent access, which is not true for RCU.
* We need to extend Rust Lock types to allow locklessly accesses.

## A magical way

struct Foo {
    a: i32,
    // int a;
    b: Rcu<Bar>,
    // struct bar __rcu *b;
    c: Rcu<i32>,
    // int __rcu *c;
    
    // int d; // access locklessly
    d: AtomicU32;
}

let lock: Lock<Foo> = ...;

// struct foo {
//     spinlock_t lock;
//     int a;
//     ...
// }

let rcu = rcu_read_lock();

// We magically get a reference to `b` from lock
let b_ref: &Bar = lock->b. // <= &Rcu<Bar>
                  dereference(&rcu);

let guard = lock.lock();
guard.d //

lock->d // &AtomicU32

let b_ref: &Bar =
    lock.project::<field_of!(Foo, b)>().dereference(&rcu);

If `->` is possible, it can solve half of our problem. The other half is

* `Guard<Foo>` shouldn't be able to generate `&mut Foo`, but
* `Guard<Foo>` should provide a way to modify `Foo::a`, i.e.

projection just gives us a way to access a field without holding lock.

`Container<T>`, we cannot get a reference to `T`, and projection provides a way to get a reference to a field of `T` through the `Container<T>`.

`Pin<&mut T>`: a poitner to T, the it cannot be moved, and you cannot directly get a `Pin<&mut Bar>`

let guard: Guard<Foo> = lock.lock();

let a_ref: &mut i32 = guard->a;

Another magic operator `->` for `Guard<Foo>`.

Actualy let's rename `Guard` to `Updater` since it make more sense for RCU

struct Updater<T> {
    lock: &Lock<T>
}

## Projections
Let's first try to implement `->b`

impl Lock<Foo> {
    pub fn project_b(&self) -> &Rcu<Bar> {
        // struct Lock<T> {
        //  lock: SpinLock;
        //  data: UnsafeCell<T>;
        // }
        let ptr = self.lock.data.get(); // the address of `Foo`.
        
        // return foo->b;
        unsafe { & (*ptr).b }
    }
}

This is not hard, right? We can also do that for `->c`

impl Lock<Foo> {
    pub fn project_c(&self) -> &Rcu<i32> {
        // struct Lock<T> {
        //  lock: SpinLock;
        //  data: UnsafeCell<T>;
        // }
        let ptr = self.data.get(); // the address of `Foo`.
        
        // return foo->c;
        unsafe { & (*ptr).c }
    }
}

Generify this

impl<T> Lock<T> {
    pub fn project<???>(&self) -> &Rcu<???> {
        let ptr = self.data.get();
        
        unsafe { & (*ptr).??? }
    }
}

Introduce `Field` trait

/// Describe a `Base` type has a field whose name is `name`
// and type is `Type`
// struct Base {
//   ...
//   name: Type
//   ...
// }
pub trait Field<Base> {
    type Type;
    const name: &'static str;
    
    fn field_of(base: *const Base) -> *const Self::Type;
}

Figure out the `???` above:

impl<T> Lock<T> {
    pub fn project<S, F: Field<T, Type=Rcu<S>>>(&self) -> &Rcu<S> {
        let ptr = self.data.get();
        
        unsafe { &* F::field_of(ptr) }
    }
}

And we impl a type for `foo->b`

struct FooB; // need to define an empty struct

impl Field<Foo> for FooB {
    type Type = Bar;
    const name: &'static str = "b";
    
    fn field_of(base: *const Foo) -> *const Self::Type {
        unsafe { core::ptr::addr_of!((*base).b) }
    }
}

#[rcu_project]
struct Foo {
    a: i32,
    b: Rcu<Bar>
    next: Rcu<Foo>,
    ...
}

let b_ref: &Bar =
    lock.project::<field_of!(Foo, b)>().dereference(&rcu);

We can generate all `impl` for `Field<Foo>` with macros.

## The other half

impl<T> Updater<T> {
    pub fn project_mut<S, F: Field<T, Type=S>>(&self) -> &mut S {
        let ptr = self.lock.data.get();
        
        unsafe { &* F::field_of(ptr) }
    }   
}

## Rest of the API

impl<T> Updater<T> {
    // similar as
    // spin_lock(&foo->lock);
    // struct bar* b = foo->b;
    // int x = b->x;
    // spin_unlock(&foo->lock);
    pub fn rcu_read<S, F: Field<T, Type=Rcu<S>>>(&self) -> &S {
        let ptr = self.lock.data.get();
        
        let rcu_ptr: &Rcu<S> = unsafe { &* F::field_of(ptr) };
        
        &* rcu_ptr.load(Relaxed); // since we hold the lock
    }
    
    // similar as
    // spin_lock(&foo->lock);
    // 
    // struct bar *old = rcu_replace_pointer(foo->b, new);
    // spin_unlock(&foo->lock);
    // synchronze_rcu();
    // kfree(old);
    pub fn update<S, F: Field<T, Type=Rcu<S>>>(&self, new: Rcu<S>) -> RcuOld<S> {
        let ptr = self.lock.data.get();
        
        let rcu_ptr: &Rcu<S> = unsafe { &* F::field_of(ptr) };
        
        rcu_ptr.swap(new) // swap can be non-atomic since we hold the lock.
    } 
}


impl Field<T> {
    type Type = RcuHead<>;
    
}