4060. submdspan preconditions do not forbid creating invalid pointer

Section: 23.7.3.7.7 [mdspan.sub.sub] Status: WP Submitter: Mark Hoemmen Opened: 2024-03-26 Last modified: 2024-07-08

Priority: Not Prioritized

View all issues with WP status.

Discussion:

Oliver Lee and Ryan Wooster pointed out to us that creating a submdspan with zero-length tuple-like or strided_slice slice specifiers at the upper extent can cause the Standard submdspan_mapping overloads to access the input mdspan's mapping out of bounds. This happens in the following line of specification (23.7.3.7.6 [mdspan.sub.map] p8 in N4971 moved to [mdspan.sub.map.common] p8 after the merge of P2642R6).

Let offset be a value of type size_t equal to (*this)(first_<index_type, P>(slices...)...).

If data_handle_type is a pointer to an array, then the resulting offset can be larger than required_span_size(), thus making the pointer invalid (not just one past the end). In a constexpr context, the result is ill-formed. With the reference mdspan implementation, Clang can actually report a build error (e.g., for out-of-bounds access to a std::array). The contributed example illustrates this.

Oliver and Ryan offer the following example and analysis:

Example 1:

auto x = std::array<int, 3>{};
auto A = mdspan{x.data(), extents{3}}; 
auto B = submdspan(A, pair{3, 3});

B is an mdspan with zero elements.

Example 2:

auto y = std::array<int, 9>{};
auto C = mdspan{y.data(), extents{3, 3}}; 
auto D = submdspan(C, pair{3, 3}, pair{3, 3});

A precondition for each slice specifier is (23.7.3.7.5 [mdspan.sub.extents]):

0 ≤ first_<index_type, k>(slices...) ≤ last_<k>(src.extents(), slices...) ≤ src.extent(k).

Our understanding is that precondition is satisfied. In the second example, first_<0> is 3 and first_<1> is also 3.

However, the submapping offset is defined as (*this)(first_<index_type, P>(slices...)...), which then can result in an invalid data handle of the submdspan, even if the data handle is never accessed/dereferenced.

godbolt demo

We expect this situation to come up in practice.

Suppose we have an N x N mdspan representing a matrix A, and we want to partition it into a 2 x 2 "matrix of matrices" (also called a "block matrix"). This partitioning is a common operation in linear algebra algorithms such as matrix factorizations. Examples of this 2 x 2 partitioning appear in P2642 and P1673.

mdspan A{A_ptr, N, N};

size_t p = partition_point(N); // integer in 0, 1, …, N (inclusive)
auto A_00 = submdspan(A, tuple{0, p}, tuple{0, p});
auto A_10 = submdspan(A, tuple{p, N}, tuple{0, 0});
auto A_01 = submdspan(A, tuple{0, p}, tuple{p, N});
auto A_11 = submdspan(A, tuple{p, N}, tuple{p, N});

Table illustrating the resulting 2 x 2 block matrix follows:

It's valid for p to be 0. That makes every block but A_11 have zero size. Thus, it should also be valid for p to be N. That makes every block but A_00 have zero size. However, that leads to the aforementioned UB.

It doesn't make sense to change first_ or last_. The definitions of first_ and last_ are meant to turn the slice specifier into a pair of bounds. Since submdspan(A, tuple{p, N}, tuple{p, N}) is valid even if p equals N, then that strongly suggests that first_<0> and first_<1> should always be p, even if p equals N.

As a result, we find ourselves needing to change submdspan_mapping. This will affect both the Standard submdspan_mapping overloads, and any custom (user-defined) overloads.

[2024-05-08; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[St. Louis 2024-06-29; Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4971 after the merge of P2642R6.

1. Modify the new 23.7.3.7.6.1 [mdspan.sub.map.common] as indicated:

   -8- If first_<index_type, k>(slices...) equals extents().extent(k) for any rank index k of extents(), then lLet offset be a value of type size_t equal to (*this).required_span_size(). Otherwise, let offset be a value of type size_t equal to (*this)(first_<index_type, P>(slices...)...).

2. Modify 23.7.3.7.7 [mdspan.sub.sub] as indicated:

   As a drive-by readability fix, we also propose changing a variable name in paragraph 6 as indicated below.

   template<class ElementType, class Extents, class LayoutPolicy,
            class AccessorPolicy, class... SliceSpecifiers>
     constexpr auto submdspan(
       const mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>& src,
       SliceSpecifiers... slices) -> see below;
   

   -1- Let index_type be typename Extents::index_type.

   -2- Let sub_map_offset be the result of submdspan_mapping(src.mapping(), slices...).

   […]

   -3- Constraints: […]

   -4- Mandates: […]

   -5-Preconditions: […]

   -6- Effects: Equivalent to:

   auto sub_map_resultoffset = submdspan_mapping(src.mapping(), slices...);
   return mdspan(src.accessor().offset(src.data(), sub_map_resultoffset.offset),
                 sub_map_resultoffset.mapping,
                 AccessorPolicy::offset_policy(src.accessor()));