On Mon, May 26, 2025 at 1:32 PM Luc Grosheintz <luc.groshei...@gmail.com> wrote:
> > > On 5/26/25 11:43, Tomasz Kaminski wrote: > > On Mon, May 26, 2025 at 11:35 AM Luc Grosheintz < > luc.groshei...@gmail.com> > > wrote: > > > >> > >> > >> On 5/22/25 15:21, Tomasz Kaminski wrote: > >>> > >>> For the stride and product computation, we should perform them in > >>> Extent::size_type, not index_type. > >>> The latter may be signed, and we may hit UB in multiplying non-zero > >>> extents, before reaching the zero. > >>> > >> > >> Then I observe the following issues: > >> > >> 1. When computing products, the integer promotion rules can interfere. > >> For simplicity let's assume that int is a 32 bit integer. Then the > >> relevant case is `uint16_t` (or unsigned short). Which is unsigned; and > >> therefore overflow shouldn't be UB. I observe that the expression > >> > >> prod *= n; > >> > >> will overflow as `int` (for large enough `n`). I believe that during the > >> computation of `prod * n` both sides are promoted to int (because the > >> range of uint16_t is contained in the range of `int`) and then > >> overflows, e.g. for n = 2**16-1. > >> > >> Note that many other small, both signed and unsigned, integers > >> semantically also overflow, but it's neither UB that's detected by > >> -fsanitize=undefined, nor a compiler error. Likely because the > >> "overflow" happens during conversion, which (in C++23) is uniquely > >> defined in [conv.integral], i.e. not UB. > >> > >> draft: https://eel.is/c++draft/conv.integral > >> N4950: 7.3.9 on p. 101 > >> > >> The solution I've come up is to not use `size_type` but > >> make_unsigned_t<decltype(index_type{} * index_type{})> > >> > >> Please let me know if there's a better solution to forcing unsigned > >> math. > >> > > I think at this point we should perform stride computation in > std::size_t. > > Because accessors are defined to accept size_t, the required_span_size() > > cannot be greater > > than maximum of size_t, and that limits our product of extents. > > > > I looked into this in the context of computing the product of > static extents. The stumbling block was that I couldn't find > a clear statement that sizeof(int) <= sizeof(size_t), or that > size_t is exempted from the integer conversion rules. > > Therefore, the concern was that the overflow issue would come > back on systems with 16-bit size_t and 32-bit int. > We could cast elements of __dyn_exts to size_t before multiplying in __ext_prod. Even use size_t in for loop: for (size_t x ; __dyn_ext()). > > I'm slightly unhappy that (on common systems) we need to use > 64-bit integers for 32-bit (or less) operations; but as you > point out, this only affects code that shouldn't be performance > sensitive. > > >> > >> Godbolt: https://godbolt.org/z/PnvaYT7vd > >> > >> 2. Let's assume we compute `__extents_prod` safely, e.g. by doing all > >> math as unsigned integers. There's several places we need to be careful: > >> > >> 2.1. layout_{right,left}::stride, these still compute products, that > >> overflow and might not be multiplied by `0` to make the answer > >> unambiguous. For an empty extent, any number is a valid stride. > Hence, > >> this only requires that we don't run into UB. > >> > >> 2.2. The default ctor of layout_stride computes the layout_right > >> strides on the fly. We can use __unsigned_prod to keep computing the > >> extents in linear time. The only requirement I'm aware of is that > the > >> strides are the same as those for layout_right (but the actual value > >> in not defined directly). > >> > >> 2.3 layout_stride::required_span_size, the current implementation > >> first scans for zeros; and only if there are none does it proceed > with > >> computing the required span size in index_type. This is safe, > because > >> the all terms in the sum are non-negative and the mandate states > that > >> the total is a representable number. Hence, all the involved terms > are > >> representable too. > >> > >> 3. For those interested in what the other two implementions do: both > >> fail in some subset of the corner cases. > >> > >> Godbolt: https://godbolt.org/z/vEYxEvMWs > >> > >> > > > >
