[libc] Prevent printf index mode crashes

[michaelrj]

Summary

The posix standard defines an alternate mode for printf where the
conversions also have an index that describes which argument to select.
Due to how variadic arguments work in C, to reach the nth argument all
n-1 previous arguments must be read with their correct types. If the
format string does not specify the types for a continuous set of
arguments, then the arguments after the discontinuity cannot be safely
read. This patch causes all conversions requesting an argument that
comes after a gap be treated as raw (i.e. the conversion string is
printed literally).

[michaelrj]

fix another small bug found with the fuzzer

[sivachandra]

Mostly LGTM but I left a style comment inline.

libc/src/stdio/printf_core/parser.cpp

39–46

Readers would expect that a macro named GET_<> would be used a function macro which returns something. That aside, can this macro be replaced by a lambda?

[michaelrj]

rename macro

libc/src/stdio/printf_core/parser.cpp

39–46

I don't think this macro can be replaced by a lambda because it needs to also take a type, and templating lambdas is a C++20 feature from what I can tell.

libc/src/stdio/printf_core/core_structs.h

if (has_conv) {
         return (conv_val_ptr == other.conv_val_ptr);
       else if (conv_name != '%')
         return (conv_val_raw == other.conv_val_raw);
     }
     return true;
   }
 };
 
-enum PrimaryType : uint8_t { Integer = 0, Float = 1, Pointer = 2 };
+enum PrimaryType : uint8_t { Unknown = 0, Float = 1, Pointer = 2, Integer = 3 };
 
 // TypeDesc stores the information about a type that is relevant to printf in
 // a relatively compact manner.
 struct TypeDesc {
   uint8_t size;
   PrimaryType primary_type;
   LIBC_INLINE constexpr bool operator==(const TypeDesc &other) const {
     return (size == other.size) && (primary_type == other.primary_type);
   }
 };
 
 template <typename T> LIBC_INLINE constexpr TypeDesc type_desc_from_type() {
   if constexpr (cpp::is_same_v<T, void>) {
-    return TypeDesc{0, PrimaryType::Integer};
+    return TypeDesc{0, PrimaryType::Unknown};
   } else {
     constexpr bool isPointer = cpp::is_pointer_v<T>;
     constexpr bool isFloat = cpp::is_floating_point_v<T>;
     return TypeDesc{sizeof(T), isPointer ? PrimaryType::Pointer
                                : isFloat ? PrimaryType::Float
                                          : PrimaryType::Integer};
   }
 }

libc/src/stdio/printf_core/parser.h

 //===-- Format string parser for printf -------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SRC_STDIO_PRINTF_CORE_PARSER_H
 #define LLVM_LIBC_SRC_STDIO_PRINTF_CORE_PARSER_H
 
+#include "src/__support/CPP/optional.h"
 #include "src/__support/CPP/type_traits.h"
 #include "src/__support/arg_list.h"
 #include "src/__support/common.h"
 #include "src/stdio/printf_core/core_structs.h"
 #include "src/stdio/printf_core/printf_config.h"
 
 #include <stddef.h>
 
#ifndef LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
   // Defined in printf_config.h
   static constexpr size_t DESC_ARR_LEN = LIBC_COPT_PRINTF_INDEX_ARR_LEN;
 
   // desc_arr stores the sizes of the variables in the ArgProvider. This is used
   // in index mode to reduce repeated string parsing. The sizes are stored as
   // TypeDesc objects, which store the size as well as minimal type information.
   // This is necessary because some systems separate the floating point and
   // integer values in va_args.
-  TypeDesc desc_arr[DESC_ARR_LEN] = {{0, Integer}};
+  TypeDesc desc_arr[DESC_ARR_LEN] = {type_desc_from_type<void>()};
 
   // TODO: Look into object stores for optimization.
 
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 
 public:
 #ifndef LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
   LIBC_INLINE Parser(const char *__restrict new_str, ArgProvider &args)
#ifndef LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 
   LIBC_INLINE void set_type_desc(size_t index, TypeDesc value) {
     if (index != 0 && index <= DESC_ARR_LEN)
       desc_arr[index - 1] = value;
   }
 
   // get_arg_value gets the value from the arg list at index (starting at 1).
   // This may require parsing the format string. An index of 0 is interpreted as
-  // the next value.
-  template <class T> LIBC_INLINE T get_arg_value(size_t index) {
-    if (!(index == 0 || index == args_index))
-      args_to_index(index);
+  // the next value. If the format string is not valid, it may have gaps in its
+  // indexes. Requesting the value for any index after a gap will fail, since
+  // the arg list must be read in order and with the correct types.
+  template <class T> LIBC_INLINE cpp::optional<T> get_arg_value(size_t index) {
+    if (!(index == 0 || index == args_index)) {
+      bool success = args_to_index(index);
+      if (!success) {
+        // If we can't get to this index, then the value of the arg can't be
+        // found.
+        return cpp::optional<T>();
+      }
+    }
 
     set_type_desc(index, type_desc_from_type<T>());
 
     ++args_index;
     return get_next_arg_value<T>();
   }
 
   // the ArgProvider can only return the next item in the list. This function is
   // used in index mode when the item that needs to be read is not the next one.
   // It moves cur_args to the index requested so the the appropriate value may
   // be read. This may involve parsing the format string, and is in the worst
   // case an O(n^2) operation.
-  void args_to_index(size_t index);
+  bool args_to_index(size_t index);
 
   // get_type_desc assumes that this format string uses index mode. It iterates
   // through the format string until it finds a format specifier that defines
   // the type of index, and returns a TypeDesc describing that type. It does not
   // modify cur_pos.
   TypeDesc get_type_desc(size_t index);
 
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 };
 
 } // namespace printf_core
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_PARSER_H

libc/src/stdio/printf_core/parser.cpp

 //===-- Format string parser implementation for printf ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // #define LIBC_COPT_PRINTF_DISABLE_INDEX_MODE 1 // This will be a compile flag.
 
 #include "parser.h"
 
 #include "src/__support/arg_list.h"
 
 #include "src/__support/CPP/bit.h"
+#include "src/__support/CPP/optional.h"
 #include "src/__support/CPP/string_view.h"
+#include "src/__support/CPP/type_traits.h"
 #include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/ctype_utils.h"
 #include "src/__support/str_to_integer.h"
 #include "src/stdio/printf_core/core_structs.h"
 
 namespace __llvm_libc {
 namespace printf_core {
 
+template <typename T> struct int_type_of {
+  using type = T;
+};
+template <> struct int_type_of<double> {
+  using type = fputil::FPBits<double>::UIntType;
+};
+template <> struct int_type_of<long double> {
+  using type = fputil::FPBits<long double>::UIntType;
+};
+template <typename T> using int_type_of_v = typename int_type_of<T>::type;
+
 #ifndef LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
-#define GET_ARG_VAL_SIMPLEST(arg_type, index) get_arg_value<arg_type>(index)
+#define WRITE_ARG_VAL_SIMPLEST(dst, arg_type, index)                           \
+  {                                                                            \
+    auto temp = get_arg_value<arg_type>(index);                                \
+    if (!temp.has_value()) {                                                   \
+      section.has_conv = false;                                                \
+    }                                                                          \
+    dst = cpp::bit_cast<int_type_of_v<arg_type>>(temp.value());                \
+  }
 #else
-#define GET_ARG_VAL_SIMPLEST(arg_type, _) get_next_arg_value<arg_type>()
+#define WRITE_ARG_VAL_SIMPLEST(dst, arg_type, _)                               \
+  dst = cpp::bit_cast<int_type_of_v<arg_type>>(get_next_arg_value<arg_type>())
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 
 FormatSection Parser::get_next_section() {
   FormatSection section;
   size_t starting_pos = cur_pos;
   if (str[cur_pos] == '%') {
     // format section
     section.has_conv = true;
 
     ++cur_pos;
     [[maybe_unused]] size_t conv_index = 0;
 
 #ifndef LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
     conv_index = parse_index(&cur_pos);
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 
     section.flags = parse_flags(&cur_pos);
 
     // handle width
     section.min_width = 0;
     if (str[cur_pos] == '*') {
       ++cur_pos;
 
-      section.min_width = GET_ARG_VAL_SIMPLEST(int, parse_index(&cur_pos));
+      WRITE_ARG_VAL_SIMPLEST(section.min_width, int, parse_index(&cur_pos));
     } else if (internal::isdigit(str[cur_pos])) {
       auto result = internal::strtointeger<int>(str + cur_pos, 10);
       section.min_width = result.value;
       cur_pos = cur_pos + result.parsed_len;
     }
     if (section.min_width < 0) {
       section.min_width = -section.min_width;
       section.flags =
           static_cast<FormatFlags>(section.flags | FormatFlags::LEFT_JUSTIFIED);
     }
 
     // handle precision
     section.precision = -1; // negative precisions are ignored.
     if (str[cur_pos] == '.') {
       ++cur_pos;
       section.precision = 0; // if there's a . but no specified precision, the
                              // precision is implicitly 0.
       if (str[cur_pos] == '*') {
         ++cur_pos;
 
-        section.precision = GET_ARG_VAL_SIMPLEST(int, parse_index(&cur_pos));
+        WRITE_ARG_VAL_SIMPLEST(section.precision, int, parse_index(&cur_pos));
 
       } else if (internal::isdigit(str[cur_pos])) {
         auto result = internal::strtointeger<int>(str + cur_pos, 10);
         section.precision = result.value;
         cur_pos = cur_pos + result.parsed_len;
       }
     }
 
     LengthModifier lm = parse_length_modifier(&cur_pos);
 
     section.length_modifier = lm;
     section.conv_name = str[cur_pos];
     switch (str[cur_pos]) {
     case ('%'):
       break;
     case ('c'):
-      section.conv_val_raw = GET_ARG_VAL_SIMPLEST(int, conv_index);
+      WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, int, conv_index);
       break;
     case ('d'):
     case ('i'):
     case ('o'):
     case ('x'):
     case ('X'):
     case ('u'):
       switch (lm) {
       case (LengthModifier::hh):
       case (LengthModifier::h):
       case (LengthModifier::none):
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(int, conv_index);
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, int, conv_index);
         break;
       case (LengthModifier::l):
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(long, conv_index);
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, long, conv_index);
         break;
       case (LengthModifier::ll):
       case (LengthModifier::L): // This isn't in the standard, but is in other
                                 // libc implementations.
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(long long, conv_index);
+
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, long long, conv_index);
         break;
       case (LengthModifier::j):
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(intmax_t, conv_index);
+
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, intmax_t, conv_index);
         break;
       case (LengthModifier::z):
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(size_t, conv_index);
+
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, size_t, conv_index);
         break;
       case (LengthModifier::t):
-        section.conv_val_raw = GET_ARG_VAL_SIMPLEST(ptrdiff_t, conv_index);
+
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, ptrdiff_t, conv_index);
         break;
       }
       break;
 #ifndef LIBC_COPT_PRINTF_DISABLE_FLOAT
     case ('f'):
     case ('F'):
     case ('e'):
     case ('E'):
     case ('a'):
     case ('A'):
     case ('g'):
     case ('G'):
-      if (lm != LengthModifier::L)
-        section.conv_val_raw =
-            cpp::bit_cast<uint64_t>(GET_ARG_VAL_SIMPLEST(double, conv_index));
-      else
-        section.conv_val_raw =
-            cpp::bit_cast<fputil::FPBits<long double>::UIntType>(
-                GET_ARG_VAL_SIMPLEST(long double, conv_index));
+      if (lm != LengthModifier::L) {
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, double, conv_index);
+      } else {
+        WRITE_ARG_VAL_SIMPLEST(section.conv_val_raw, long double, conv_index);
+      }
       break;
 #endif // LIBC_COPT_PRINTF_DISABLE_FLOAT
 #ifndef LIBC_COPT_PRINTF_DISABLE_WRITE_INT
     case ('n'):
 #endif // LIBC_COPT_PRINTF_DISABLE_WRITE_INT
     case ('p'):
     case ('s'):
-      section.conv_val_ptr = GET_ARG_VAL_SIMPLEST(void *, conv_index);
+      WRITE_ARG_VAL_SIMPLEST(section.conv_val_ptr, void *, conv_index);
       break;
     default:
       // if the conversion is undefined, change this to a raw section.
       section.has_conv = false;
       break;
     }
     // If the end of the format section is on the '\0'. This means we need to
     // not advance the cur_pos.
if (str[local_pos] == '%') {
 
       LengthModifier lm = parse_length_modifier(&local_pos);
 
       // if we don't have an index for this conversion, then its position is
       // unknown and all this information is irrelevant. The rest of this logic
       // has been for skipping past this conversion properly to avoid
       // weirdness with %%.
       if (conv_index == 0) {
+        if (str[local_pos] != '\0')
           ++local_pos;
         continue;
       }
 
       TypeDesc conv_size = type_desc_from_type<void>();
       switch (str[local_pos]) {
       case ('%'):
         conv_size = type_desc_from_type<void>();
         break;
#endif // LIBC_COPT_PRINTF_DISABLE_WRITE_INT
         return conv_size;
     }
     // If the end of the format section is on the '\0'. This means we need to
     // not advance the local_pos.
     if (str[local_pos] != '\0')
       ++local_pos;
   }
 
-  // If there is no size for the requested index, then just guess that it's an
-  // int.
-  return type_desc_from_type<int>();
+  // If there is no size for the requested index, then it's unknown. Return
+  // void.
+  return type_desc_from_type<void>();
 }
 
-void Parser::args_to_index(size_t index) {
+bool Parser::args_to_index(size_t index) {
   if (args_index > index) {
     args_index = 1;
     args_cur = args_start;
   }
 
   while (args_index < index) {
     TypeDesc cur_type_desc = type_desc_from_type<void>();
     if (args_index <= DESC_ARR_LEN)
       cur_type_desc = desc_arr[args_index - 1];
 
     if (cur_type_desc == type_desc_from_type<void>())
       cur_type_desc = get_type_desc(args_index);
 
+    // A type of void represents the type being unknown. If the type for the
+    // requested index isn't in the desc_arr and isn't found by parsing the
+    // string, then then advancing to the requested index is impossible. In that
+    // case the function returns false.
+    if (cur_type_desc == type_desc_from_type<void>())
+      return false;
+
     if (cur_type_desc == type_desc_from_type<uint32_t>())
       args_cur.next_var<uint32_t>();
     else if (cur_type_desc == type_desc_from_type<uint64_t>())
       args_cur.next_var<uint64_t>();
 #ifndef LIBC_COPT_PRINTF_DISABLE_FLOAT
     // Floating point numbers are stored separately from the other arguments.
     else if (cur_type_desc == type_desc_from_type<double>())
       args_cur.next_var<double>();
     else if (cur_type_desc == type_desc_from_type<long double>())
       args_cur.next_var<long double>();
 #endif // LIBC_COPT_PRINTF_DISABLE_FLOAT
     // pointers may be stored separately from normal values.
     else if (cur_type_desc == type_desc_from_type<void *>())
       args_cur.next_var<void *>();
     else
       args_cur.next_var<uint32_t>();
 
     ++args_index;
   }
+  return true;
 }
 
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE
 
 } // namespace printf_core
 } // namespace __llvm_libc

libc/test/src/stdio/printf_core/parser_test.cpp

TEST(LlvmLibcPrintfParserTest, IndexModeComplexParsing) {
   expected9.min_width = 1;
   expected9.precision = 1;
   expected9.conv_val_raw = arg1;
   expected9.conv_name = 'c';
 
   EXPECT_PFORMAT_EQ(expected9, format_arr[9]);
 }
 
+TEST(LlvmLibcPrintfParserTest, IndexModeGapCheck) {
+  __llvm_libc::printf_core::FormatSection format_arr[10];
+  const char *str = "%1$d%2$d%4$d";
+  int arg1 = 1;
+  int arg2 = 2;
+  int arg3 = 3;
+  int arg4 = 4;
+
+  evaluate(format_arr, str, arg1, arg2, arg3, arg4);
+
+  __llvm_libc::printf_core::FormatSection expected0, expected1, expected2;
+
+  expected0.has_conv = true;
+  expected0.raw_string = {str, 4};
+  expected0.conv_val_raw = arg1;
+  expected0.conv_name = 'd';
+
+  EXPECT_PFORMAT_EQ(expected0, format_arr[0]);
+
+  expected1.has_conv = true;
+  expected1.raw_string = {str + 4, 4};
+  expected1.conv_val_raw = arg2;
+  expected1.conv_name = 'd';
+
+  EXPECT_PFORMAT_EQ(expected1, format_arr[1]);
+
+  expected2.has_conv = false;
+  expected2.raw_string = {str + 8, 4};
+
+  EXPECT_PFORMAT_EQ(expected2, format_arr[2]);
+}
+
+TEST(LlvmLibcPrintfParserTest, IndexModeTrailingPercentCrash) {
+  __llvm_libc::printf_core::FormatSection format_arr[10];
+  const char *str = "%2$d%";
+  evaluate(format_arr, str, 1, 2);
+
+  __llvm_libc::printf_core::FormatSection expected0, expected1;
+  expected0.has_conv = false;
+
+  expected0.raw_string = {str, 4};
+  EXPECT_PFORMAT_EQ(expected0, format_arr[0]);
+
+  expected1.has_conv = false;
+
+  expected1.raw_string = {str + 4, 1};
+  EXPECT_PFORMAT_EQ(expected1, format_arr[1]);
+}
+
 #endif // LIBC_COPT_PRINTF_DISABLE_INDEX_MODE