Simple API for configuring a lock marker DAG #2
Description
Netstack3 suffers from impl_lock_after!() being both overzealous, preventing them from creating the DAG they say they want and also too simplistic to actually see the relationship. This proposal addresses both pain points. It also avoids the 1st problem mentioned in issue #1.
Playing with the more interesting parts of their DAG, I come up with this:
lock_dag! { // dot: // list:
DeviceLayerState => {
FilterState<Ipv4>,
FilterState<Ipv6>,
},
FilterState<Ipv4> =>
IpState<Ipv4> => {
IpStateCache<Ipv4, Pmtu>,
IpStateCache<Ipv4, Fragment>,
},
FilterState<Ipv6> =>
IpState<Ipv6> => {
IpStateCache<Ipv6, Pmtu>,
IpStateCache<Ipv6, Fragment>,
},
{
IpState<Ipv4>,
IpState<Ipv6>
} =>
LoopbackTxQueue => {
LoopbackRxQueue,
EthernetIpv4Arp
},
}
// Workaround: The above gives only one blanket impl, recursing back to DeviceLayerState.
// The other branch is only a simple impl, so this one got missed:
lock_dag! { [FilterState<Ipv6>] => LoopbackTxQueue }Actually, while writing, I uncommented the 1st line, which, rather than implementing the Before/After relationships, returns:
Then I replace dot: by list: which I can sort and insert into the following simple type creator. It is just a little utility to avoid bolerplate – nothing fancy. Here I added random visibilities, just for illlustration.
lock_markers! {
// Generic distinguishers:
pub Ipv4,
pub Ipv6,
Pmtu,
Fragment,
// Actual lock marker types:
DeviceLayerState,
pub(crate) EthernetIpv4Arp,
FilterState<IpvN>,
IpState<IpvN>,
IpStateCache<IpvN, Item>,
LoopbackRxQueue,
LoopbackTxQueue,
}Also based on the list: output I specify a holder struct, from which the locks get accessed via the Marker types. The example gets a bit messy here, as Netstack3’s frequent generic markers don’t allow generating member names in a macro by example (without pulling in a proc-macro dependency.) Therefore quite a few of these use the syntax for optionally providing an identifier.
Format is [member /] Marker: Lock<Inner> [= default]. The lock types and default values are random, just for illustration:
lock_holder! {
#[derive(Default)]
pub const Locks {
DeviceLayerState:
Mutex<u8> = 1,
EthernetIpv4Arp:
RwLock<bool> = false,
// if you have multiple generic markers, all (except maybe one) must prefix their member name:
FilterState<Ipv4>:
Mutex<u8> = 1,
filter_state_ipv6 / FilterState<Ipv6>:
Mutex<u8> = 1,
ip_state_ipv4 / IpState<Ipv4>:
Mutex<u8> = 2,
ip_state_ipv6 / IpState<Ipv6>:
Mutex<u8> = 2,
ip_state_cache_ipv4_pmtu / IpStateCache<Ipv4, Pmtu>:
Mutex<&'static str> = "cache",
ip_state_cache_ipv4_fragment / IpStateCache<Ipv4, Fragment>:
Mutex<&'static str> = "me if",
ip_state_cache_ipv6_pmtu / IpStateCache<Ipv6, Pmtu>:
Mutex<&'static str> = "you",
ip_state_cache_ipv6_fragment / IpStateCache<Ipv6, Fragment>:
Mutex<&'static str> = "can",
LoopbackRxQueue:
Mutex<u8> = 2,
LoopbackTxQueue:
Mutex<u8> = 3,
}
}
static LOCKS: Locks = Locks::new();Now in each thread you can create a new lock session with the unlocked “root” lock level (empty tuple).
let mut locked_unlocked = LOCKS.init();
// Access locked states.
let (dls, mut locked_dls) = locked_unlocked.lock_and::<DeviceLayerState>();
let (fs4, mut locked_fs4) = locked_dls.lock_and::<FilterState<Ipv4>>();
{
let e4a = locked_fs4.read_lock::<EthernetIpv4Arp>();
}
// by dropping e4a we fell back to locked_fs4 being accessible again
let isc4p = locked_fs4.lock::<IpStateCache<Ipv4, Pmtu>>();Here’s the proposed source code, open for suggestions and bikeshedding. It avoids the alphabetic ordering of $A and $B, which runs counter to abbreviating “before” and “after”:
/**
Arrange your lock marker types in a [Directed Acyclic Graph (DAG)](https://en.wikipedia.org/wiki/Directed_acyclic_graph)
which describes the pathes and order in which their marked locks can be obtained.
The body is a `,` separated list of type chains. This are either single types, or groups of `,` separated types
`{ T1, T2, … }` joined by `=>` (Rust doesn’t allow `->` here.) Each member of a group comes after the preceding type
in the chain and before the following type. The first type or group implicitly follows `lock_tree::Unlocked`.
An enhanced sub-DAG of Fuchsia’s Netstack3 (where this came from) could be defined thus:
```
lock_dag! { // dot:
DeviceLayerState => {
FilterState<Ipv4>,
FilterState<Ipv6>,
},
FilterState<Ipv4> =>
IpState<Ipv4> => {
IpStateCache<Ipv4, Pmtu>,
IpStateCache<Ipv4, Fragment>,
},
FilterState<Ipv6> =>
IpState<Ipv6> => {
IpStateCache<Ipv6, Pmtu>,
IpStateCache<Ipv6, Fragment>,
},
{
IpState<Ipv4>,
IpState<Ipv6>
} =>
LoopbackTxQueue => {
LoopbackRxQueue,
EthernetIpv4Arp
},
}
```
### Caveats
As only one inbound marker may recurse to `Unlocked` (else you get “conflicting implementations of
trait `LockAfter<_>` for type `C`”) and we can only choose it when seeing them all at once, you must
combine them
```dot
A => C, B => C // undecidable, do this instead:
{ A, B } => C
```
Assuming your DAG looks like this, `D` will thus get a blanket implementation on `C1`, making it also come after `B1`
and `A`. However, to avoid an ambiguous relationship with `A` and `Unlocked`, it only creates an explicit before/after
relationship with `C2` and `C3`.
```text
┌─────────────┐
│ A │
└┬─────┬─────┬┘
┌▽───┐┌▽───┐┌▽───┐
│ B1 ││ B2 ││ B3 │
└┬───┘└┬───┘└┬───┘
┌▽───┐┌▽───┐┌▽───┐
│ C1 ││ C2 ││ C3 │
└┬───┘└┬───┘└┬───┘
┌▽─────▽─────▽┐
│ D │
└─────────────┘
```
Even though the DAG expresses that `D` should also come after `B2` and `B3`, it seems beyond the reach of a macro by
example to do such housekeeping. To avoid the need for an expensive proc macro, in such rare cases you yourself must
apply the following workaround, listing in `[]` also each non-direct predecessor that was not accounted for, i.e. not
coming before the 1st marker type in a preceding group. This must be done in a separate macro invocation, which can
again have multiple such relationships separated by `,`:
```
lock_dag! { /* …, */ B3 => C3, { C1, C2, C3 } => D }
// workaround to register before relationships not recursively handled via C1
lock_dag! { [B2, B3] => D }
```
### Analysis with `dot:` and `list:`
While designing you may insert `dot:` immediately at the start of the macro. The marker types
do not yet have to exist for this. It will instead return an equivalent string representation in
[Graphviz DOT](https://graphviz.org/doc/info/lang.html). You can pipe it to `dot -Tsvg`.
Once you’re happy that it’s cycle free and every marker is reachable from `Unlocked`, instead prefix
it with `list:` to get your inventory. You can pipe it to `sort -u` or `sed 's/<.*>/<T>/' | sort -u`.
*/
#[macro_export]
macro_rules! lock_dag {
(dot: $($rest:tt)+) => {
lock_dag_inner!(dot: Unlocked => $($rest)+)
};
(list: $(
$before:ty
$(,)?
$(=>)?
$(
{ $($after:ty),+ }
$(=>)?
$(,)?
)*
)+) => {
concat!($(
stringify!($before), ",\n",
$(
$(stringify!($after), ",\n",)+
)*
)+)
};
($([$($before:ty),+] => $after:ty),+ $(,)?) => {
$(
$(
lock_dag_inner!(1 $before => $after);
)+
)+
};
($($rest:tt)+) => {
lock_dag_inner!(1 lock_tree::Unlocked => $($rest)+);
};
}
#[macro_export]
#[doc(hidden)]
macro_rules! lock_dag_inner {
// discriminator 1 means: Let the default LockBefore impl handle the reverse
(? 1 $before:ty => $after:ty) => {};
// discriminator * means: Blanket LockBefore impl
(? * $before:ty => $after:ty) => {
impl<X: lock_tree::relation::LockBefore<$before>> lock_tree::relation::LockAfter<X> for $after {}
};
////////////
// { Group, … } => { Group, … }
(@ * $before:tt => {$($after:ty),+ $(,)?}) => {
$(
lock_dag_inner!(@ * $before => $after);
)+
};
// { Group, … } => Single
(@ * {$before:ty, $($before_rest:ty),+ $(,)?} => $after:ty) => {
lock_dag_inner!(@ * $before => $after);
$(
// To avoid ambiguity, $before_rest can’t be blanket impl.
lock_dag_inner!(@ 1 $before_rest => $after);
)+
};
// Single => { Group, … }
(@ $discriminator:tt $before:ty => {$($after:ty),+ $(,)?}) => {
$(
lock_dag_inner!(@ $discriminator $before => $after);
)+
};
// Single => Single, more flexible impl_lock_after
(@ $discriminator:tt $before:ty => $after:ty) => {
impl lock_tree::relation::LockAfter<$before> for $after {}
lock_dag_inner!(? $discriminator $before => $after);
};
////////////
// Poor man’s $( $( single $| group )=>+ ),+ – I so wish we had an alternatives-operator!
(dot: $(
$before:ty
$(,)?
// X_arrow dummy is to capture whether we get an arrow
$(=> $($before_arrow:literal)?)?
$(
{ $($after:ty),+ }
$(,)?
$(=> $($after_arrow:literal)?)?
)*
)+) => {
concat!(
"digraph { node [shape = box];\n",
$(
"\"", stringify!($before), "\"\n",
$(" -> ", $($before_arrow)?)?
$(
"{\n",
$(" \"", stringify!($after), "\"\n",)+
" }\n",
$(" -> ", $($after_arrow)?)?
)*
)+
"}"
)
};
////////////
// Must distinguish all combinations of ty & tt, because generic ty matches more than one tt
(*) => {};
// Single => Single
($discriminator:tt $before:ty => $after:ty $(=> $($rest:tt)+)?) => {
lock_dag_inner!(@ $discriminator $before => $after);
$(
// What came after in this match, will be the before of the next match to try
lock_dag_inner!(* $after => $($rest)+);
)?
};
// previous rule caught $after sans trailing `,`
($discriminator:tt $before:ty => $after:ty, $($rest:tt)*) => {
lock_dag_inner!(@ $discriminator $before => $after);
lock_dag_inner!(* $($rest)*);
};
// Single => { Group, … }
($discriminator:tt $before:ty => $after:tt $(=> $($rest:tt)+)?) => {
lock_dag_inner!(@ $discriminator $before => $after);
$(
// What came after in this match, will be the before of the next match to try
lock_dag_inner!(* $after => $($rest)+);
)?
};
// previous rule caught $after sans trailing `,`
($discriminator:tt $before:ty => $after:tt, $($rest:tt)*) => {
lock_dag_inner!(@ $discriminator $before => $after);
lock_dag_inner!(* $($rest)*);
};
// { Group, … } => Single
(* $before:tt => $after:ty $(=> $($rest:tt)+)?) => {
lock_dag_inner!(@ * $before => $after);
$(
// What came after in this match, will be the before of the next match to try
lock_dag_inner!(* $after => $($rest)+);
)?
};
// previous rule caught $after sans trailing `,`
(* $before:tt => $after:ty, $($rest:tt)*) => {
lock_dag_inner!(@ * $before => $after);
lock_dag_inner!(* $($rest)*);
};
// { Group, … } => { Group, … }
(* $before:tt => $after:tt $(=> $($rest:tt)+)?) => {
lock_dag_inner!(@ * $before => $after);
$(
// What came after in this match, will be the before of the next match to try
lock_dag_inner!(* $after => $($rest)+);
)?
};
// previous rule caught $after sans trailing `,`
(* $before:tt => $after:tt, $($rest:tt)*) => {
lock_dag_inner!(@ * $before => $after);
lock_dag_inner!(* $($rest)*);
};
}
/**
Create uninstantiable marker types, which can be used for marking locks.
It takes a `,` separated list of optional visibility and type. If the type is a simple identifier, this creates
it as an `enum`. If there are generic type arguments, this creates it as a `struct` containing `PhantomData`.
```
lock_markers! {
pub LockA,
pub(crate) LockB,
LockC<T1, T2>,
LockD,
}
```
*/
#[macro_export]
macro_rules! lock_markers {
(@ $vis:vis $marker:ident) => {
$vis enum $marker {}
};
(@ $vis:vis $marker:ident<$($gen:ident),+>) => {
// While an empty enum is not instantiable, PhantomData is, so add a ZST that also is not.
$vis struct $marker<$($gen),+>(core::marker::PhantomData<($($gen),+,)>, core::convert::Infallible);
};
($($vis:vis $marker:ident$(<$($gen:ident),+ $(,)?>)?),+ $(,)?) => {
$(
lock_markers!(@ $vis $marker$(<$($gen),+>)?);
)+
};
}
/**
Define a struct for holding all your locks.
This starts with the following
- Optional attributes to apply to the struct, e.g. `#[derive(Default)]`. If you give no default values as below,
the generated `new` function will do exactly the same.
- An optional visibility for the struct, e.g. `pub(crate)`
- An optional keyword `const` which applies to the generated `new` function. As long as `default()` can’t be
const, this requires giving an explicit default value to each lock.
- The identifier for the struct type.
- A `,` separated list of lock specifications enclosed in `{}`.
Each specification consists of the following
- An optional identifier for the field to store the lock in. It must be followed by `/` if present. It is only
necessary when the marker type is generic, and even then you can omit it for one of the repetitions of the similar
type.
- The marker type (which you can create with `lock_markers! {}` and put in relation with `lock_dag! {}`) for addressing
this lock.
- `:`
- A “fake” lock type like `Mutex<u8>` or `RwLock<MyType>`. `Mutex` and `RwLock` are actually callback macros here.
If you want to use other lock types, create your own macros mimicing either of these.
- Optional `=` followed by a default inner value for the lock. The generated `new` function will assign this if given,
else `default()`.
Generate the struct with `new()` and in each thread obtain an unlocked handle by calling `init()` on it.
*/
#[macro_export]
macro_rules! lock_holder {
($(#[$meta:meta])* $vis:vis const $holder:ident $spec:tt) => {
lock_holder_inner!($(#[$meta])* $vis const, $holder $spec);
};
($(#[$meta:meta])* $vis:vis $holder:ident $spec:tt) => {
lock_holder_inner!($(#[$meta])* $vis, $holder $spec);
};
}
#[macro_export]
#[doc(hidden)]
macro_rules! lock_holder_inner {
(@ $($member:ident $lock:ident $ty:ty),+) => { $($member: $lock<$ty>),+ };
// invert originally optional $marker and $member, skipping the latter if it was also given
([$(<$($gen:ident),+>)?] $marker:ident $($_:ident)?) => { $marker$(<$($gen),+>)? };
// match the whole lock_holder DSL, having a comma after const, which allows it become optional
($(#[$meta:meta])* $vis:vis $($const:ident)?, $holder:ident {
$(
$member:ident $(/ $marker:ident)?$(<$($gen:ident),+ $(,)?>)?:
$lock:ident<$ty:ty> $(= $default:expr)?
),+ $(,)?
}) => {
$(#[$meta])*
// $member may often be a type name in snake case
#[allow(non_snake_case)]
$vis struct $holder {
$($member: $lock!(type $ty)),+
}
impl $holder {
$vis $($const)? fn new() -> Self {
Self {
$(
$member: $lock!(new $($default)?)
),+
}
}
$vis fn init(&self) -> lock_tree::Locked<&Self, lock_tree::Unlocked> {
lock_tree::Locked::new(self)
}
}
$(
$lock!(impl $holder, $member, lock_holder_inner!([$(<$($gen),+>)?] $($marker)? $member), $ty);
)+
};
}
// Have one macro like this for each similar type: TokioMutex, OrderedMutex…
macro_rules! Mutex {
(type $ty:ty) => {
std::sync::Mutex<$ty>
};
(new) => {
std::sync::Mutex::default()
};
(new $new:expr) => {
std::sync::Mutex::new($new)
};
(impl $holder:ident, $member:ident, $marker:ty, $ty:ty) => {
impl lock_tree::lock::LockFor<$marker> for $holder {
type Data = $ty;
type Guard<'l>
= std::sync::MutexGuard<'l, $ty>
where
Self: 'l;
fn lock(&self) -> Self::Guard<'_> {
self.$member.lock().unwrap()
}
}
};
}
// Have one macro like this for each similar type: TokioRwLock, SnapshotLock…
macro_rules! RwLock {
(type $ty:ty) => {
std::sync::RwLock<$ty>
};
(new) => {
std::sync::RwLock::default()
};
(new $new:expr) => {
std::sync::RwLock::new($new)
};
(impl $holder:ident, $member:ident, $marker:ty, $ty:ty) => {
impl lock_tree::lock::RwLockFor<$marker> for $holder {
type Data = $ty;
type ReadGuard<'l>
= std::sync::RwLockReadGuard<'l, $ty>
where
Self: 'l;
type WriteGuard<'l>
= std::sync::RwLockWriteGuard<'l, $ty>
where
Self: 'l;
fn read_lock(&self) -> Self::ReadGuard<'_> {
self.$member.read().unwrap()
}
fn write_lock(&self) -> Self::WriteGuard<'_> {
self.$member.write().unwrap()
}
}
};
}