Title
submdspan preconditions do not forbid creating invalid pointer
Status
ready
Section
[mdspan.submdspan.submdspan]
Submitter
Mark Hoemmen

Created on 2024-03-26.00:00:00 last changed 1 month ago

Messages

Date: 2024-05-08.10:36:29

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 [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()));
    
Date: 2024-05-15.00:00:00

[ 2024-05-08; Reflector poll ]

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

Date: 2024-03-27.15:01:23

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.

History
Date User Action Args
2024-05-08 10:36:29adminsetmessages: + msg14119
2024-05-08 10:36:29adminsetstatus: new -> ready
2024-03-26 11:39:16adminsetmessages: + msg14026
2024-03-26 00:00:00admincreate