1. 31 Aug, 2024 1 commit
  2. 25 Aug, 2024 5 commits
  3. 24 Aug, 2024 1 commit
  4. 23 Aug, 2024 11 commits
    • Alice Ryhl's avatar
      rust: list: add ListArcField · b204bbc5
      Alice Ryhl authored
      One way to explain what `ListArc` does is that it controls exclusive
      access to the prev/next pointer field in a refcounted object. The
      feature of having a special reference to a refcounted object with
      exclusive access to specific fields is useful for other things, so
      provide a general utility for that.
      
      This is used by Rust Binder to keep track of which processes have a
      reference to a given node. This involves an object for each process/node
      pair, that is referenced by both the process and the node. For some
      fields in this object, only the process's reference needs to access
      them (and it needs mutable access), so Binder uses a ListArc to give the
      process's reference exclusive access.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-10-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      b204bbc5
    • Alice Ryhl's avatar
      rust: list: support heterogeneous lists · 2003c04b
      Alice Ryhl authored
      Support linked lists that can hold many different structs at once. This
      is generally done using trait objects. The main challenge is figuring
      what the struct is given only a pointer to the ListLinks.
      
      We do this by storing a pointer to the struct next to the ListLinks
      field. The container_of operation will then just read that pointer. When
      the type is a trait object, that pointer will be a fat pointer whose
      metadata is a vtable that tells you what kind of struct it is.
      
      Heterogeneous lists are heavily used by Rust Binder. There are a lot of
      so-called todo lists containing various events that need to be delivered
      to userspace next time userspace calls into the driver. And there are
      quite a few different todo item types: incoming transaction, changes to
      refcounts, death notifications, and more.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-9-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      2003c04b
    • Alice Ryhl's avatar
      rust: list: add cursor · 9078a4f9
      Alice Ryhl authored
      The cursor is very similar to the list iterator, but it has one
      important feature that the iterator doesn't: it can be used to remove
      items from the linked list.
      
      This feature cannot be added to the iterator because the references you
      get from the iterator are considered borrows of the original list,
      rather than borrows of the iterator. This means that there's no way to
      prevent code like this:
      
      let item = iter.next();
      iter.remove();
      use(item);
      
      If `iter` was a cursor instead of an iterator, then `item` will be
      considered a borrow of `iter`. Since `remove` destroys `iter`, this
      means that the borrow-checker will prevent uses of `item` after the call
      to `remove`.
      
      So there is a trade-off between supporting use in traditional for loops,
      and supporting removal of elements as you iterate. Iterators and cursors
      represents two different choices on that spectrum.
      
      Rust Binder needs cursors for the list of death notifications that a
      process is currently handling. When userspace tells Binder that it has
      finished processing the death notification, Binder will iterate the list
      to search for the relevant item and remove it.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-8-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      9078a4f9
    • Alice Ryhl's avatar
      rust: list: add iterators · deeecc9c
      Alice Ryhl authored
      Rust Binder has lists containing stuff such as all contexts or all
      processes, and sometimes needs to iterate over them. This patch enables
      Rust Binder to do that using a normal for loop.
      
      The iterator returns the ArcBorrow type, so it is possible to grab a
      refcount to values while iterating.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-7-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      deeecc9c
    • Alice Ryhl's avatar
      rust: list: add List · db841866
      Alice Ryhl authored
      Add the actual linked list itself.
      
      The linked list uses the following design: The List type itself just has
      a single pointer to the first element of the list. And the actual list
      items then form a cycle. So the last item is `first->prev`.
      
      This is slightly different from the usual kernel linked list. Matching
      that exactly would amount to giving List two pointers, and having it be
      part of the cycle of items. This alternate design has the advantage that
      the cycle is never completely empty, which can reduce the number of
      branches in some cases. However, it also has the disadvantage that List
      must be pinned, which this design is trying to avoid.
      
      Having the list items form a cycle rather than having null pointers at
      the beginning/end is convenient for several reasons. For one, it lets us
      store only one pointer in List, and it simplifies the implementation of
      several functions.
      
      Unfortunately, the `remove` function that removes an arbitrary element
      from the list has to be unsafe. This is needed because there is no way
      to handle the case where you pass an element from the wrong list. For
      example, if it is the first element of some other list, then that other
      list's `first` pointer would not be updated. Similarly, it could be a
      data race if you try to remove it from two different lists in parallel.
      (There's no problem with passing `remove` an item that's not in any
      list. Additionally, other removal methods such as `pop_front` need not
      be unsafe, as they can't be used to remove items from another list.)
      
      A future patch in this series will introduce support for cursors that
      can be used to remove arbitrary items without unsafe code.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-6-f5f5e8075da0@google.com
      [ Fixed a few typos. - Miguel ]
      Signed-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      db841866
    • Alice Ryhl's avatar
      rust: list: add macro for implementing ListItem · 40c53294
      Alice Ryhl authored
      Adds a macro for safely implementing the ListItem trait. As part of the
      implementation of the macro, we also provide a HasListLinks trait
      similar to the workqueue's HasWorkItem trait.
      
      The HasListLinks trait is only necessary if you are implementing
      ListItem using the impl_list_item macro.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-5-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      40c53294
    • Alice Ryhl's avatar
      rust: list: add struct with prev/next pointers · 14176295
      Alice Ryhl authored
      Define the ListLinks struct, which wraps the prev/next pointers that
      will be used to insert values into a List in a future patch. Also
      define the ListItem trait, which is implemented by structs that have a
      ListLinks field.
      
      The ListItem trait provides four different methods that are all
      essentially container_of or the reverse of container_of. Two of them are
      used before inserting/after removing an item from the list, and the two
      others are used when looking at a value without changing whether it is
      in a list. This distinction is introduced because it is needed for the
      patch that adds support for heterogeneous lists, which are implemented
      by adding a third pointer field with a fat pointer to the full struct.
      When inserting into the heterogeneous list, the pointer-to-self is
      updated to have the right vtable, and the container_of operation is
      implemented by just returning that pointer instead of using the real
      container_of operation.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-4-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      14176295
    • Alice Ryhl's avatar
      rust: list: add tracking for ListArc · a4802631
      Alice Ryhl authored
      Add the ability to track whether a ListArc exists for a given value,
      allowing for the creation of ListArcs without going through UniqueArc.
      
      The `impl_list_arc_safe!` macro is extended with a `tracked_by` strategy
      that defers the tracking of ListArcs to a field of the struct.
      Additionally, the AtomicListArcTracker type is introduced, which can
      track whether a ListArc exists using an atomic. By deferring the
      tracking to a field of type AtomicListArcTracker, structs gain the
      ability to create ListArcs without going through a UniqueArc.
      
      Rust Binder uses this for some objects where we want to be able to
      insert them into a linked list at any time. Using the
      AtomicListArcTracker, we are able to check whether an item is already in
      the list, and if not, we can create a `ListArc` and push it.
      
      The macro has the ability to defer the tracking of ListArcs to a field,
      using whatever strategy that field has. Since we don't add any
      strategies other than AtomicListArcTracker, another similar option would
      be to hard-code that the field should be an AtomicListArcTracker.
      However, Rust Binder has a case where the AtomicListArcTracker is not
      stored directly in the struct, but in a sub-struct. Furthermore, the
      outer struct is generic:
      
      struct Wrapper<T: ?Sized> {
          links: ListLinks,
          inner: T,
      }
      
      Here, the Wrapper struct implements ListArcSafe with `tracked_by inner`,
      and then the various types used with `inner` also uses the macro to
      implement ListArcSafe. Some of them use the untracked strategy, and some
      of them use tracked_by with an AtomicListArcTracker. This way, Wrapper
      just inherits whichever choice `inner` has made.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-3-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      a4802631
    • Alice Ryhl's avatar
      rust: list: add ListArc · 6cd34171
      Alice Ryhl authored
      The `ListArc` type can be thought of as a special reference to a
      refcounted object that owns the permission to manipulate the
      `next`/`prev` pointers stored in the refcounted object. By ensuring that
      each object has only one `ListArc` reference, the owner of that
      reference is assured exclusive access to the `next`/`prev` pointers.
      When a `ListArc` is inserted into a `List`, the `List` takes ownership
      of the `ListArc` reference.
      
      There are various strategies for ensuring that a value has only one
      `ListArc` reference. The simplest is to convert a `UniqueArc` into a
      `ListArc`. However, the refcounted object could also keep track of
      whether a `ListArc` exists using a boolean, which could allow for the
      creation of new `ListArc` references from an `Arc` reference. Whatever
      strategy is used, the relevant tracking is referred to as "the tracking
      inside `T`", and the `ListArcSafe` trait (and its subtraits) are used to
      update the tracking when a `ListArc` is created or destroyed.
      
      Note that we allow the case where the tracking inside `T` thinks that a
      `ListArc` exists, but actually, there isn't a `ListArc`. However, we do
      not allow the opposite situation where a `ListArc` exists, but the
      tracking thinks it doesn't. This is because the former can at most
      result in us failing to create a `ListArc` when the operation could
      succeed, whereas the latter can result in the creation of two `ListArc`
      references. Only the latter situation can lead to memory safety issues.
      
      This patch introduces the `impl_list_arc_safe!` macro that allows you to
      implement `ListArcSafe` for types using the strategy where a `ListArc`
      can only be created from a `UniqueArc`. Other strategies are introduced
      in later patches.
      
      This is part of the linked list that Rust Binder will use for many
      different things. The strategy where a `ListArc` can only be created
      from a `UniqueArc` is actually sufficient for most of the objects that
      Rust Binder needs to insert into linked lists. Usually, these are todo
      items that are created and then immediately inserted into a queue.
      
      The const generic ID allows objects to have several prev/next pointer
      pairs so that the same object can be inserted into several different
      lists. You are able to have several `ListArc` references as long as they
      correspond to different pointer pairs. The ID itself is purely a
      compile-time concept and will not be present in the final binary. Both
      the `List` and the `ListArc` will need to agree on the ID for them to
      work together. Rust Binder uses this in a few places (e.g. death
      recipients) where the same object can be inserted into both generic todo
      lists and some other lists for tracking the status of the object.
      
      The ID is a const generic rather than a type parameter because the
      `pair_from_unique` method needs to be able to assert that the two ids
      are different. There's no easy way to assert that when using types
      instead of integers.
      Reviewed-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-2-f5f5e8075da0@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      6cd34171
    • Benno Lossin's avatar
      rust: init: add `assert_pinned` macro · 0528ca0a
      Benno Lossin authored
      Add a macro to statically check if a field of a struct is marked with
      `#[pin]` ie that it is structurally pinned. This can be used when
      `unsafe` code needs to rely on fields being structurally pinned.
      
      The macro has a special "inline" mode for the case where the type
      depends on generic parameters from the surrounding scope.
      Signed-off-by: default avatarBenno Lossin <benno.lossin@proton.me>
      Co-developed-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Link: https://lore.kernel.org/r/20240814-linked-list-v5-1-f5f5e8075da0@google.com
      [ Replaced `compile_fail` with `ignore` and a TODO note. Removed
        `pub` from example to clean `unreachable_pub` lint. - Miguel ]
      Signed-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      0528ca0a
    • Matthew Maurer's avatar
      rust: support arrays in target JSON · c6945aca
      Matthew Maurer authored
      Some configuration options such as the supported sanitizer list are
      arrays. To support using Rust with sanitizers on x86, we must update the
      target.json generator to support this case.
      
      The Push trait is removed in favor of the From trait because the Push
      trait doesn't work well in the nested case where you are not really
      pushing values to a TargetSpec.
      Signed-off-by: default avatarMatthew Maurer <mmaurer@google.com>
      Signed-off-by: default avatarAlice Ryhl <aliceryhl@google.com>
      Reviewed-by: default avatarGary Guo <gary@garyguo.net>
      Tested-by: default avatarGatlin Newhouse <gatlin.newhouse@gmail.com>
      Link: https://lore.kernel.org/r/20240730-target-json-arrays-v1-1-2b376fd0ecf4@google.comSigned-off-by: default avatarMiguel Ojeda <ojeda@kernel.org>
      c6945aca
  5. 21 Aug, 2024 2 commits
  6. 20 Aug, 2024 2 commits
  7. 19 Aug, 2024 1 commit
  8. 18 Aug, 2024 17 commits