This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4060. submdspan preconditions do not forbid creating invalid pointer

Section: 99 [mdspan.submdspan.submdspan] Status: New Submitter: Mark Hoemmen Opened: 2024-03-26 Last modified: 2024-03-27

Priority: Not Prioritized

View all issues with New 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 ( [mdspan.submdspan.mapping] p8 in N4971 moved to [mdspan.submdspan.mapping.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 ( [mdspan.submdspan.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:

A_00 A_01
A_10 A_11

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.

Proposed resolution:

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

  1. Modify the new [mdspan.submdspan.mapping.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 99 [mdspan.submdspan.submdspan] 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()));