/* SPDX-License-Identifier: GPL-2.0 */
      /* Copyright (c) 2018 Facebook */
      
      #include <uapi/linux/btf.h>
      #include <uapi/linux/bpf.h>
      #include <uapi/linux/bpf_perf_event.h>
      #include <uapi/linux/types.h>
      #include <linux/seq_file.h>
      #include <linux/compiler.h>
      #include <linux/ctype.h>
      #include <linux/errno.h>
      #include <linux/slab.h>
      #include <linux/anon_inodes.h>
      #include <linux/file.h>
      #include <linux/uaccess.h>
      #include <linux/kernel.h>
      #include <linux/idr.h>
      #include <linux/sort.h>
      #include <linux/bpf_verifier.h>
      #include <linux/btf.h>
      #include <linux/btf_ids.h>
      #include <linux/skmsg.h>
      #include <linux/perf_event.h>
      #include <net/sock.h>
      
      /* BTF (BPF Type Format) is the meta data format which describes
       * the data types of BPF program/map.  Hence, it basically focus
       * on the C programming language which the modern BPF is primary
       * using.
       *
       * ELF Section:
       * ~~~~~~~~~~~
       * The BTF data is stored under the ".BTF" ELF section
       *
       * struct btf_type:
       * ~~~~~~~~~~~~~~~
       * Each 'struct btf_type' object describes a C data type.
       * Depending on the type it is describing, a 'struct btf_type'
       * object may be followed by more data.  F.e.
       * To describe an array, 'struct btf_type' is followed by
       * 'struct btf_array'.
       *
       * 'struct btf_type' and any extra data following it are
       * 4 bytes aligned.
       *
       * Type section:
       * ~~~~~~~~~~~~~
       * The BTF type section contains a list of 'struct btf_type' objects.
       * Each one describes a C type.  Recall from the above section
       * that a 'struct btf_type' object could be immediately followed by extra
       * data in order to desribe some particular C types.
       *
       * type_id:
       * ~~~~~~~
       * Each btf_type object is identified by a type_id.  The type_id
       * is implicitly implied by the location of the btf_type object in
       * the BTF type section.  The first one has type_id 1.  The second
       * one has type_id 2...etc.  Hence, an earlier btf_type has
       * a smaller type_id.
       *
       * A btf_type object may refer to another btf_type object by using
       * type_id (i.e. the "type" in the "struct btf_type").
       *
       * NOTE that we cannot assume any reference-order.
       * A btf_type object can refer to an earlier btf_type object
       * but it can also refer to a later btf_type object.
       *
       * For example, to describe "const void *".  A btf_type
       * object describing "const" may refer to another btf_type
       * object describing "void *".  This type-reference is done
       * by specifying type_id:
       *
       * [1] CONST (anon) type_id=2
       * [2] PTR (anon) type_id=0
       *
       * The above is the btf_verifier debug log:
       *   - Each line started with "[?]" is a btf_type object
       *   - [?] is the type_id of the btf_type object.
       *   - CONST/PTR is the BTF_KIND_XXX
       *   - "(anon)" is the name of the type.  It just
       *     happens that CONST and PTR has no name.
       *   - type_id=XXX is the 'u32 type' in btf_type
       *
       * NOTE: "void" has type_id 0
       *
       * String section:
       * ~~~~~~~~~~~~~~
       * The BTF string section contains the names used by the type section.
       * Each string is referred by an "offset" from the beginning of the
       * string section.
       *
       * Each string is '\0' terminated.
       *
       * The first character in the string section must be '\0'
       * which is used to mean 'anonymous'. Some btf_type may not
       * have a name.
       */
      
      /* BTF verification:
       *
       * To verify BTF data, two passes are needed.
       *
       * Pass #1
       * ~~~~~~~
       * The first pass is to collect all btf_type objects to
       * an array: "btf->types".
       *
       * Depending on the C type that a btf_type is describing,
       * a btf_type may be followed by extra data.  We don't know
       * how many btf_type is there, and more importantly we don't
       * know where each btf_type is located in the type section.
       *
       * Without knowing the location of each type_id, most verifications
       * cannot be done.  e.g. an earlier btf_type may refer to a later
       * btf_type (recall the "const void *" above), so we cannot
       * check this type-reference in the first pass.
       *
       * In the first pass, it still does some verifications (e.g.
       * checking the name is a valid offset to the string section).
       *
       * Pass #2
       * ~~~~~~~
       * The main focus is to resolve a btf_type that is referring
       * to another type.
       *
       * We have to ensure the referring type:
       * 1) does exist in the BTF (i.e. in btf->types[])
       * 2) does not cause a loop:
       *        struct A {
       *                struct B b;
       *        };
       *
       *        struct B {
       *                struct A a;
       *        };
       *
       * btf_type_needs_resolve() decides if a btf_type needs
       * to be resolved.
       *
       * The needs_resolve type implements the "resolve()" ops which
       * essentially does a DFS and detects backedge.
       *
       * During resolve (or DFS), different C types have different
       * "RESOLVED" conditions.
       *
       * When resolving a BTF_KIND_STRUCT, we need to resolve all its
       * members because a member is always referring to another
       * type.  A struct's member can be treated as "RESOLVED" if
       * it is referring to a BTF_KIND_PTR.  Otherwise, the
       * following valid C struct would be rejected:
       *
       *        struct A {
       *                int m;
       *                struct A *a;
       *        };
       *
       * When resolving a BTF_KIND_PTR, it needs to keep resolving if
       * it is referring to another BTF_KIND_PTR.  Otherwise, we cannot
       * detect a pointer loop, e.g.:
       * BTF_KIND_CONST -> BTF_KIND_PTR -> BTF_KIND_CONST -> BTF_KIND_PTR +
       *                        ^                                         |
       *                        +-----------------------------------------+
       *
       */
      
      #define BITS_PER_U128 (sizeof(u64) * BITS_PER_BYTE * 2)
      #define BITS_PER_BYTE_MASK (BITS_PER_BYTE - 1)
      #define BITS_PER_BYTE_MASKED(bits) ((bits) & BITS_PER_BYTE_MASK)
      #define BITS_ROUNDDOWN_BYTES(bits) ((bits) >> 3)
      #define BITS_ROUNDUP_BYTES(bits) \
              (BITS_ROUNDDOWN_BYTES(bits) + !!BITS_PER_BYTE_MASKED(bits))
      
      #define BTF_INFO_MASK 0x8f00ffff
      #define BTF_INT_MASK 0x0fffffff
      #define BTF_TYPE_ID_VALID(type_id) ((type_id) <= BTF_MAX_TYPE)
      #define BTF_STR_OFFSET_VALID(name_off) ((name_off) <= BTF_MAX_NAME_OFFSET)
      
      /* 16MB for 64k structs and each has 16 members and
       * a few MB spaces for the string section.
       * The hard limit is S32_MAX.
       */
      #define BTF_MAX_SIZE (16 * 1024 * 1024)
      
      #define for_each_member_from(i, from, struct_type, member)                \
              for (i = from, member = btf_type_member(struct_type) + from;        \
                   i < btf_type_vlen(struct_type);                                \
                   i++, member++)
      
      #define for_each_vsi(i, struct_type, member)                        \
              for (i = 0, member = btf_type_var_secinfo(struct_type);        \
                   i < btf_type_vlen(struct_type);                        \
                   i++, member++)
      
      #define for_each_vsi_from(i, from, struct_type, member)                                \
              for (i = from, member = btf_type_var_secinfo(struct_type) + from;        \
                   i < btf_type_vlen(struct_type);                                        \
                   i++, member++)
      
      DEFINE_IDR(btf_idr);
      DEFINE_SPINLOCK(btf_idr_lock);
      
      struct btf {
              void *data;
              struct btf_type **types;
              u32 *resolved_ids;
              u32 *resolved_sizes;
              const char *strings;
              void *nohdr_data;
              struct btf_header hdr;
              u32 nr_types;
              u32 types_size;
              u32 data_size;
              refcount_t refcnt;
              u32 id;
              struct rcu_head rcu;
      };
      
      enum verifier_phase {
              CHECK_META,
              CHECK_TYPE,
      };
      
      struct resolve_vertex {
              const struct btf_type *t;
              u32 type_id;
              u16 next_member;
      };
      
      enum visit_state {
              NOT_VISITED,
              VISITED,
              RESOLVED,
      };
      
      enum resolve_mode {
              RESOLVE_TBD,        /* To Be Determined */
              RESOLVE_PTR,        /* Resolving for Pointer */
              RESOLVE_STRUCT_OR_ARRAY,        /* Resolving for struct/union
                                               * or array
                                               */
      };
      
      #define MAX_RESOLVE_DEPTH 32
      
      struct btf_sec_info {
              u32 off;
              u32 len;
      };
      
      struct btf_verifier_env {
              struct btf *btf;
              u8 *visit_states;
              struct resolve_vertex stack[MAX_RESOLVE_DEPTH];
              struct bpf_verifier_log log;
              u32 log_type_id;
              u32 top_stack;
              enum verifier_phase phase;
              enum resolve_mode resolve_mode;
      };
      
      static const char * const btf_kind_str[NR_BTF_KINDS] = {
              [BTF_KIND_UNKN]                = "UNKNOWN",
              [BTF_KIND_INT]                = "INT",
              [BTF_KIND_PTR]                = "PTR",
              [BTF_KIND_ARRAY]        = "ARRAY",
              [BTF_KIND_STRUCT]        = "STRUCT",
              [BTF_KIND_UNION]        = "UNION",
              [BTF_KIND_ENUM]                = "ENUM",
              [BTF_KIND_FWD]                = "FWD",
              [BTF_KIND_TYPEDEF]        = "TYPEDEF",
              [BTF_KIND_VOLATILE]        = "VOLATILE",
              [BTF_KIND_CONST]        = "CONST",
              [BTF_KIND_RESTRICT]        = "RESTRICT",
              [BTF_KIND_FUNC]                = "FUNC",
              [BTF_KIND_FUNC_PROTO]        = "FUNC_PROTO",
              [BTF_KIND_VAR]                = "VAR",
              [BTF_KIND_DATASEC]        = "DATASEC",
      };
      
      static const char *btf_type_str(const struct btf_type *t)
      {
              return btf_kind_str[BTF_INFO_KIND(t->info)];
      }
      
      struct btf_kind_operations {
              s32 (*check_meta)(struct btf_verifier_env *env,
                                const struct btf_type *t,
                                u32 meta_left);
              int (*resolve)(struct btf_verifier_env *env,
                             const struct resolve_vertex *v);
              int (*check_member)(struct btf_verifier_env *env,
                                  const struct btf_type *struct_type,
                                  const struct btf_member *member,
                                  const struct btf_type *member_type);
              int (*check_kflag_member)(struct btf_verifier_env *env,
                                        const struct btf_type *struct_type,
                                        const struct btf_member *member,
                                        const struct btf_type *member_type);
              void (*log_details)(struct btf_verifier_env *env,
                                  const struct btf_type *t);
              void (*seq_show)(const struct btf *btf, const struct btf_type *t,
                               u32 type_id, void *data, u8 bits_offsets,
                               struct seq_file *m);
      };
      
      static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS];
      static struct btf_type btf_void;
      
      static int btf_resolve(struct btf_verifier_env *env,
                             const struct btf_type *t, u32 type_id);
      
      static bool btf_type_is_modifier(const struct btf_type *t)
      {
              /* Some of them is not strictly a C modifier
               * but they are grouped into the same bucket
               * for BTF concern:
               *   A type (t) that refers to another
               *   type through t->type AND its size cannot
               *   be determined without following the t->type.
               *
               * ptr does not fall into this bucket
               * because its size is always sizeof(void *).
               */
  242         switch (BTF_INFO_KIND(t->info)) {
              case BTF_KIND_TYPEDEF:
              case BTF_KIND_VOLATILE:
              case BTF_KIND_CONST:
              case BTF_KIND_RESTRICT:
                      return true;
              }
      
              return false;
      }
      
      bool btf_type_is_void(const struct btf_type *t)
      {
    5         return t == &btf_void;
      }
      
      static bool btf_type_is_fwd(const struct btf_type *t)
      {
  147         return BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
      }
      
      static bool btf_type_nosize(const struct btf_type *t)
      {
  147         return btf_type_is_void(t) || btf_type_is_fwd(t) ||
  161                btf_type_is_func(t) || btf_type_is_func_proto(t);
      }
      
      static bool btf_type_nosize_or_null(const struct btf_type *t)
      {
  161         return !t || btf_type_nosize(t);
      }
      
      /* union is only a special case of struct:
       * all its offsetof(member) == 0
       */
      static bool btf_type_is_struct(const struct btf_type *t)
      {
  228         u8 kind = BTF_INFO_KIND(t->info);
      
              return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
      }
      
      static bool __btf_type_is_struct(const struct btf_type *t)
      {
   19         return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;
      }
      
      static bool btf_type_is_array(const struct btf_type *t)
      {
              return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
      }
      
      static bool btf_type_is_var(const struct btf_type *t)
      {
   92         return BTF_INFO_KIND(t->info) == BTF_KIND_VAR;
      }
      
      static bool btf_type_is_datasec(const struct btf_type *t)
      {
   92         return BTF_INFO_KIND(t->info) == BTF_KIND_DATASEC;
      }
      
      s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
      {
              const struct btf_type *t;
              const char *tname;
              u32 i;
      
              for (i = 1; i <= btf->nr_types; i++) {
                      t = btf->types[i];
                      if (BTF_INFO_KIND(t->info) != kind)
                              continue;
      
                      tname = btf_name_by_offset(btf, t->name_off);
                      if (!strcmp(tname, name))
                              return i;
              }
      
              return -ENOENT;
      }
      
      const struct btf_type *btf_type_skip_modifiers(const struct btf *btf,
                                                     u32 id, u32 *res_id)
      {
              const struct btf_type *t = btf_type_by_id(btf, id);
      
              while (btf_type_is_modifier(t)) {
                      id = t->type;
                      t = btf_type_by_id(btf, t->type);
              }
      
              if (res_id)
                      *res_id = id;
      
              return t;
      }
      
      const struct btf_type *btf_type_resolve_ptr(const struct btf *btf,
                                                  u32 id, u32 *res_id)
      {
              const struct btf_type *t;
      
              t = btf_type_skip_modifiers(btf, id, NULL);
              if (!btf_type_is_ptr(t))
                      return NULL;
      
              return btf_type_skip_modifiers(btf, t->type, res_id);
      }
      
      const struct btf_type *btf_type_resolve_func_ptr(const struct btf *btf,
                                                       u32 id, u32 *res_id)
      {
              const struct btf_type *ptype;
      
              ptype = btf_type_resolve_ptr(btf, id, res_id);
              if (ptype && btf_type_is_func_proto(ptype))
                      return ptype;
      
              return NULL;
      }
      
      /* Types that act only as a source, not sink or intermediate
       * type when resolving.
       */
      static bool btf_type_is_resolve_source_only(const struct btf_type *t)
      {
   91         return btf_type_is_var(t) ||
                     btf_type_is_datasec(t);
      }
      
      /* What types need to be resolved?
       *
       * btf_type_is_modifier() is an obvious one.
       *
       * btf_type_is_struct() because its member refers to
       * another type (through member->type).
       *
       * btf_type_is_var() because the variable refers to
       * another type. btf_type_is_datasec() holds multiple
       * btf_type_is_var() types that need resolving.
       *
       * btf_type_is_array() because its element (array->type)
       * refers to another type.  Array can be thought of a
       * special case of struct while array just has the same
       * member-type repeated by array->nelems of times.
       */
      static bool btf_type_needs_resolve(const struct btf_type *t)
      {
  236         return btf_type_is_modifier(t) ||
                     btf_type_is_ptr(t) ||
  205                btf_type_is_struct(t) ||
                     btf_type_is_array(t) ||
  236                btf_type_is_var(t) ||
                     btf_type_is_datasec(t);
      }
      
      /* t->size can be used */
      static bool btf_type_has_size(const struct btf_type *t)
      {
  102         switch (BTF_INFO_KIND(t->info)) {
              case BTF_KIND_INT:
              case BTF_KIND_STRUCT:
              case BTF_KIND_UNION:
              case BTF_KIND_ENUM:
              case BTF_KIND_DATASEC:
                      return true;
              }
      
              return false;
      }
      
      static const char *btf_int_encoding_str(u8 encoding)
      {
    7         if (encoding == 0)
                      return "(none)";
              else if (encoding == BTF_INT_SIGNED)
                      return "SIGNED";
    6         else if (encoding == BTF_INT_CHAR)
                      return "CHAR";
    5         else if (encoding == BTF_INT_BOOL)
                      return "BOOL";
              else
                      return "UNKN";
      }
      
      static u32 btf_type_int(const struct btf_type *t)
      {
   54         return *(u32 *)(t + 1);
      }
      
      static const struct btf_array *btf_type_array(const struct btf_type *t)
      {
              return (const struct btf_array *)(t + 1);
      }
      
      static const struct btf_enum *btf_type_enum(const struct btf_type *t)
      {
              return (const struct btf_enum *)(t + 1);
      }
      
      static const struct btf_var *btf_type_var(const struct btf_type *t)
      {
              return (const struct btf_var *)(t + 1);
      }
      
      static const struct btf_var_secinfo *btf_type_var_secinfo(const struct btf_type *t)
      {
              return (const struct btf_var_secinfo *)(t + 1);
      }
      
      static const struct btf_kind_operations *btf_type_ops(const struct btf_type *t)
      {
  370         return kind_ops[BTF_INFO_KIND(t->info)];
      }
      
      static bool btf_name_offset_valid(const struct btf *btf, u32 offset)
      {
    7         return BTF_STR_OFFSET_VALID(offset) &&
   97                 offset < btf->hdr.str_len;
      }
      
   49 static bool __btf_name_char_ok(char c, bool first, bool dot_ok)
      {
              if ((first ? !isalpha(c) :
   76                      !isalnum(c)) &&
   49             c != '_' &&
   37             ((c == '.' && !dot_ok) ||
                    c != '.'))
                      return false;
              return true;
      }
      
      static bool __btf_name_valid(const struct btf *btf, u32 offset, bool dot_ok)
      {
              /* offset must be valid */
  114         const char *src = &btf->strings[offset];
              const char *src_limit;
      
   72         if (!__btf_name_char_ok(*src, true, dot_ok))
  114                 return false;
      
              /* set a limit on identifier length */
  102         src_limit = src + KSYM_NAME_LEN;
              src++;
    8         while (*src && src < src_limit) {
    8                 if (!__btf_name_char_ok(*src, false, dot_ok))
                              return false;
    6                 src++;
              }
      
              return !*src;
      }
      
      /* Only C-style identifier is permitted. This can be relaxed if
       * necessary.
       */
      static bool btf_name_valid_identifier(const struct btf *btf, u32 offset)
      {
   21         return __btf_name_valid(btf, offset, false);
      }
      
      static bool btf_name_valid_section(const struct btf *btf, u32 offset)
      {
              return __btf_name_valid(btf, offset, true);
      }
      
   87 static const char *__btf_name_by_offset(const struct btf *btf, u32 offset)
      {
  229         if (!offset)
                      return "(anon)";
   77         else if (offset < btf->hdr.str_len)
   83                 return &btf->strings[offset];
              else
                      return "(invalid-name-offset)";
      }
      
      const char *btf_name_by_offset(const struct btf *btf, u32 offset)
      {
   51         if (offset < btf->hdr.str_len)
   51                 return &btf->strings[offset];
      
              return NULL;
      }
      
      const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id)
      {
   13         if (type_id > btf->nr_types)
                      return NULL;
      
  245         return btf->types[type_id];
    2 }
      
      /*
       * Regular int is not a bit field and it must be either
       * u8/u16/u32/u64 or __int128.
       */
      static bool btf_type_int_is_regular(const struct btf_type *t)
      {
              u8 nr_bits, nr_bytes;
              u32 int_data;
      
   32         int_data = btf_type_int(t);
              nr_bits = BTF_INT_BITS(int_data);
   31         nr_bytes = BITS_ROUNDUP_BYTES(nr_bits);
              if (BITS_PER_BYTE_MASKED(nr_bits) ||
   32             BTF_INT_OFFSET(int_data) ||
                  (nr_bytes != sizeof(u8) && nr_bytes != sizeof(u16) &&
                   nr_bytes != sizeof(u32) && nr_bytes != sizeof(u64) &&
                   nr_bytes != (2 * sizeof(u64)))) {
                      return false;
              }
      
              return true;
      }
      
      /*
       * Check that given struct member is a regular int with expected
       * offset and size.
       */
      bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
                                 const struct btf_member *m,
                                 u32 expected_offset, u32 expected_size)
      {
              const struct btf_type *t;
              u32 id, int_data;
              u8 nr_bits;
      
              id = m->type;
              t = btf_type_id_size(btf, &id, NULL);
              if (!t || !btf_type_is_int(t))
                      return false;
      
              int_data = btf_type_int(t);
              nr_bits = BTF_INT_BITS(int_data);
              if (btf_type_kflag(s)) {
                      u32 bitfield_size = BTF_MEMBER_BITFIELD_SIZE(m->offset);
                      u32 bit_offset = BTF_MEMBER_BIT_OFFSET(m->offset);
      
                      /* if kflag set, int should be a regular int and
                       * bit offset should be at byte boundary.
                       */
                      return !bitfield_size &&
                             BITS_ROUNDUP_BYTES(bit_offset) == expected_offset &&
                             BITS_ROUNDUP_BYTES(nr_bits) == expected_size;
              }
      
              if (BTF_INT_OFFSET(int_data) ||
                  BITS_PER_BYTE_MASKED(m->offset) ||
                  BITS_ROUNDUP_BYTES(m->offset) != expected_offset ||
                  BITS_PER_BYTE_MASKED(nr_bits) ||
                  BITS_ROUNDUP_BYTES(nr_bits) != expected_size)
                      return false;
      
              return true;
      }
      
      __printf(2, 3) static void __btf_verifier_log(struct bpf_verifier_log *log,
                                                    const char *fmt, ...)
      {
              va_list args;
      
  289         va_start(args, fmt);
              bpf_verifier_vlog(log, fmt, args);
              va_end(args);
      }
      
      __printf(2, 3) static void btf_verifier_log(struct btf_verifier_env *env,
                                                  const char *fmt, ...)
      {
              struct bpf_verifier_log *log = &env->log;
              va_list args;
      
  271         if (!bpf_verifier_log_needed(log))
  251                 return;
      
  246         va_start(args, fmt);
              bpf_verifier_vlog(log, fmt, args);
              va_end(args);
      }
      
      __printf(4, 5) static void __btf_verifier_log_type(struct btf_verifier_env *env,
                                                         const struct btf_type *t,
                                                         bool log_details,
                                                         const char *fmt, ...)
      {
  205         struct bpf_verifier_log *log = &env->log;
              u8 kind = BTF_INFO_KIND(t->info);
              struct btf *btf = env->btf;
              va_list args;
      
  370         if (!bpf_verifier_log_needed(log))
  340                 return;
      
              /* btf verifier prints all types it is processing via
               * btf_verifier_log_type(..., fmt = NULL).
               * Skip those prints for in-kernel BTF verification.
               */
  295         if (log->level == BPF_LOG_KERNEL && !fmt)
                      return;
      
  205         __btf_verifier_log(log, "[%u] %s %s%s",
                                 env->log_type_id,
                                 btf_kind_str[kind],
                                 __btf_name_by_offset(btf, t->name_off),
                                 log_details ? " " : "");
      
              if (log_details)
  187                 btf_type_ops(t)->log_details(env, t);
      
  195         if (fmt && *fmt) {
  123                 __btf_verifier_log(log, " ");
                      va_start(args, fmt);
                      bpf_verifier_vlog(log, fmt, args);
                      va_end(args);
              }
      
  160         __btf_verifier_log(log, "\n");
      }
      
      #define btf_verifier_log_type(env, t, ...) \
              __btf_verifier_log_type((env), (t), true, __VA_ARGS__)
      #define btf_verifier_log_basic(env, t, ...) \
              __btf_verifier_log_type((env), (t), false, __VA_ARGS__)
      
      __printf(4, 5)
      static void btf_verifier_log_member(struct btf_verifier_env *env,
                                          const struct btf_type *struct_type,
                                          const struct btf_member *member,
                                          const char *fmt, ...)
      {
   61         struct bpf_verifier_log *log = &env->log;
   61         struct btf *btf = env->btf;
              va_list args;
      
   85         if (!bpf_verifier_log_needed(log))
   82                 return;
      
   80         if (log->level == BPF_LOG_KERNEL && !fmt)
                      return;
              /* The CHECK_META phase already did a btf dump.
               *
               * If member is logged again, it must hit an error in
               * parsing this member.  It is useful to print out which
               * struct this member belongs to.
               */
              if (env->phase != CHECK_META)
   43                 btf_verifier_log_type(env, struct_type, NULL);
      
              if (btf_type_kflag(struct_type))
   26                 __btf_verifier_log(log,
                                         "\t%s type_id=%u bitfield_size=%u bits_offset=%u",
                                         __btf_name_by_offset(btf, member->name_off),
                                         member->type,
                                         BTF_MEMBER_BITFIELD_SIZE(member->offset),
                                         BTF_MEMBER_BIT_OFFSET(member->offset));
              else
   35                 __btf_verifier_log(log, "\t%s type_id=%u bits_offset=%u",
                                         __btf_name_by_offset(btf, member->name_off),
                                         member->type, member->offset);
      
   61         if (fmt && *fmt) {
   52                 __btf_verifier_log(log, " ");
                      va_start(args, fmt);
                      bpf_verifier_vlog(log, fmt, args);
                      va_end(args);
              }
      
   45         __btf_verifier_log(log, "\n");
      }
      
      __printf(4, 5)
      static void btf_verifier_log_vsi(struct btf_verifier_env *env,
                                       const struct btf_type *datasec_type,
                                       const struct btf_var_secinfo *vsi,
                                       const char *fmt, ...)
      {
   18         struct bpf_verifier_log *log = &env->log;
              va_list args;
      
   19         if (!bpf_verifier_log_needed(log))
   18                 return;
   16         if (log->level == BPF_LOG_KERNEL && !fmt)
                      return;
   12         if (env->phase != CHECK_META)
    6                 btf_verifier_log_type(env, datasec_type, NULL);
      
   12         __btf_verifier_log(log, "\t type_id=%u offset=%u size=%u",
                                 vsi->type, vsi->offset, vsi->size);
   12         if (fmt && *fmt) {
   12                 __btf_verifier_log(log, " ");
                      va_start(args, fmt);
                      bpf_verifier_vlog(log, fmt, args);
                      va_end(args);
              }
      
   10         __btf_verifier_log(log, "\n");
      }
      
      static void btf_verifier_log_hdr(struct btf_verifier_env *env,
                                       u32 btf_data_size)
      {
  131         struct bpf_verifier_log *log = &env->log;
              const struct btf *btf = env->btf;
              const struct btf_header *hdr;
      
  348         if (!bpf_verifier_log_needed(log))
                      return;
      
  348         if (log->level == BPF_LOG_KERNEL)
                      return;
              hdr = &btf->hdr;
              __btf_verifier_log(log, "magic: 0x%x\n", hdr->magic);
              __btf_verifier_log(log, "version: %u\n", hdr->version);
              __btf_verifier_log(log, "flags: 0x%x\n", hdr->flags);
              __btf_verifier_log(log, "hdr_len: %u\n", hdr->hdr_len);
              __btf_verifier_log(log, "type_off: %u\n", hdr->type_off);
              __btf_verifier_log(log, "type_len: %u\n", hdr->type_len);
              __btf_verifier_log(log, "str_off: %u\n", hdr->str_off);
              __btf_verifier_log(log, "str_len: %u\n", hdr->str_len);
              __btf_verifier_log(log, "btf_total_size: %u\n", btf_data_size);
      }
      
      static int btf_add_type(struct btf_verifier_env *env, struct btf_type *t)
      {
  256         struct btf *btf = env->btf;
      
              /* < 2 because +1 for btf_void which is always in btf->types[0].
               * btf_void is not accounted in btf->nr_types because btf_void
               * does not come from the BTF file.
               */
              if (btf->types_size - btf->nr_types < 2) {
                      /* Expand 'types' array */
      
                      struct btf_type **new_types;
                      u32 expand_by, new_size;
      
  256                 if (btf->types_size == BTF_MAX_TYPE) {
                              btf_verifier_log(env, "Exceeded max num of types");
                              return -E2BIG;
                      }
      
  256                 expand_by = max_t(u32, btf->types_size >> 2, 16);
                      new_size = min_t(u32, BTF_MAX_TYPE,
                                       btf->types_size + expand_by);
      
                      new_types = kvcalloc(new_size, sizeof(*new_types),
                                           GFP_KERNEL | __GFP_NOWARN);
                      if (!new_types)
                              return -ENOMEM;
      
  256                 if (btf->nr_types == 0)
  256                         new_types[0] = &btf_void;
                      else
                              memcpy(new_types, btf->types,
                                     sizeof(*btf->types) * (btf->nr_types + 1));
      
  256                 kvfree(btf->types);
                      btf->types = new_types;
                      btf->types_size = new_size;
              }
      
  256         btf->types[++(btf->nr_types)] = t;
      
              return 0;
      }
      
      static int btf_alloc_id(struct btf *btf)
      {
              int id;
      
  132         idr_preload(GFP_KERNEL);
              spin_lock_bh(&btf_idr_lock);
              id = idr_alloc_cyclic(&btf_idr, btf, 1, INT_MAX, GFP_ATOMIC);
              if (id > 0)
  132                 btf->id = id;
  132         spin_unlock_bh(&btf_idr_lock);
  132         idr_preload_end();
      
  132         if (WARN_ON_ONCE(!id))
                      return -ENOSPC;
      
              return id > 0 ? 0 : id;
      }
      
      static void btf_free_id(struct btf *btf)
      {
              unsigned long flags;
      
              /*
               * In map-in-map, calling map_delete_elem() on outer
               * map will call bpf_map_put on the inner map.
               * It will then eventually call btf_free_id()
               * on the inner map.  Some of the map_delete_elem()
               * implementation may have irq disabled, so
               * we need to use the _irqsave() version instead
               * of the _bh() version.
               */
              spin_lock_irqsave(&btf_idr_lock, flags);
              idr_remove(&btf_idr, btf->id);
              spin_unlock_irqrestore(&btf_idr_lock, flags);
      }
      
      static void btf_free(struct btf *btf)
      {
              kvfree(btf->types);
              kvfree(btf->resolved_sizes);
              kvfree(btf->resolved_ids);
              kvfree(btf->data);
              kfree(btf);
      }
      
      static void btf_free_rcu(struct rcu_head *rcu)
      {
              struct btf *btf = container_of(rcu, struct btf, rcu);
      
              btf_free(btf);
      }
      
      void btf_put(struct btf *btf)
      {
  555         if (btf && refcount_dec_and_test(&btf->refcnt)) {
                      btf_free_id(btf);
                      call_rcu(&btf->rcu, btf_free_rcu);
              }
      }
      
      static int env_resolve_init(struct btf_verifier_env *env)
      {
              struct btf *btf = env->btf;
              u32 nr_types = btf->nr_types;
              u32 *resolved_sizes = NULL;
              u32 *resolved_ids = NULL;
              u8 *visit_states = NULL;
      
              /* +1 for btf_void */
              resolved_sizes = kvcalloc(nr_types + 1, sizeof(*resolved_sizes),
                                        GFP_KERNEL | __GFP_NOWARN);
              if (!resolved_sizes)
                      goto nomem;
      
  241         resolved_ids = kvcalloc(nr_types + 1, sizeof(*resolved_ids),
                                      GFP_KERNEL | __GFP_NOWARN);
              if (!resolved_ids)
                      goto nomem;
      
  240         visit_states = kvcalloc(nr_types + 1, sizeof(*visit_states),
                                      GFP_KERNEL | __GFP_NOWARN);
              if (!visit_states)
                      goto nomem;
      
  236         btf->resolved_sizes = resolved_sizes;
              btf->resolved_ids = resolved_ids;
              env->visit_states = visit_states;
      
              return 0;
      
      nomem:
              kvfree(resolved_sizes);
              kvfree(resolved_ids);
              kvfree(visit_states);
              return -ENOMEM;
      }
      
      static void btf_verifier_env_free(struct btf_verifier_env *env)
      {
  375         kvfree(env->visit_states);
              kfree(env);
      }
      
      static bool env_type_is_resolve_sink(const struct btf_verifier_env *env,
                                           const struct btf_type *next_type)
      {
  142         switch (env->resolve_mode) {
              case RESOLVE_TBD:
                      /* int, enum or void is a sink */
   53                 return !btf_type_needs_resolve(next_type);
              case RESOLVE_PTR:
                      /* int, enum, void, struct, array, func or func_proto is a sink
                       * for ptr
                       */
   42                 return !btf_type_is_modifier(next_type) &&
                              !btf_type_is_ptr(next_type);
              case RESOLVE_STRUCT_OR_ARRAY:
                      /* int, enum, void, ptr, func or func_proto is a sink
                       * for struct and array
                       */
  102                 return !btf_type_is_modifier(next_type) &&
                              !btf_type_is_array(next_type) &&
   83                         !btf_type_is_struct(next_type);
              default:
  142                 BUG();
              }
      }
      
      static bool env_type_is_resolved(const struct btf_verifier_env *env,
                                       u32 type_id)
      {
  208         return env->visit_states[type_id] == RESOLVED;
      }
      
  208 static int env_stack_push(struct btf_verifier_env *env,
                                const struct btf_type *t, u32 type_id)
      {
              struct resolve_vertex *v;
      
  208         if (env->top_stack == MAX_RESOLVE_DEPTH)
                      return -E2BIG;
      
  208         if (env->visit_states[type_id] != NOT_VISITED)
                      return -EEXIST;
      
  208         env->visit_states[type_id] = VISITED;
      
              v = &env->stack[env->top_stack++];
              v->t = t;
              v->type_id = type_id;
              v->next_member = 0;
      
  208         if (env->resolve_mode == RESOLVE_TBD) {
                      if (btf_type_is_ptr(t))
  208                         env->resolve_mode = RESOLVE_PTR;
  195                 else if (btf_type_is_struct(t) || btf_type_is_array(t))
  176                         env->resolve_mode = RESOLVE_STRUCT_OR_ARRAY;
              }
      
              return 0;
      }
      
      static void env_stack_set_next_member(struct btf_verifier_env *env,
                                            u16 next_member)
      {
              env->stack[env->top_stack - 1].next_member = next_member;
      }
      
      static void env_stack_pop_resolved(struct btf_verifier_env *env,
                                         u32 resolved_type_id,
                                         u32 resolved_size)
      {
  115         u32 type_id = env->stack[--(env->top_stack)].type_id;
              struct btf *btf = env->btf;
      
              btf->resolved_sizes[type_id] = resolved_size;
              btf->resolved_ids[type_id] = resolved_type_id;
              env->visit_states[type_id] = RESOLVED;
      }
      
      static const struct resolve_vertex *env_stack_peak(struct btf_verifier_env *env)
      {
  208         return env->top_stack ? &env->stack[env->top_stack - 1] : NULL;
      }
      
      /* Resolve the size of a passed-in "type"
       *
       * type: is an array (e.g. u32 array[x][y])
       * return type: type "u32[x][y]", i.e. BTF_KIND_ARRAY,
       * *type_size: (x * y * sizeof(u32)).  Hence, *type_size always
       *             corresponds to the return type.
       * *elem_type: u32
       * *total_nelems: (x * y).  Hence, individual elem size is
       *                (*type_size / *total_nelems)
       *
       * type: is not an array (e.g. const struct X)
       * return type: type "struct X"
       * *type_size: sizeof(struct X)
       * *elem_type: same as return type ("struct X")
       * *total_nelems: 1
       */
      const struct btf_type *
      btf_resolve_size(const struct btf *btf, const struct btf_type *type,
                       u32 *type_size, const struct btf_type **elem_type,
                       u32 *total_nelems)
      {
              const struct btf_type *array_type = NULL;
              const struct btf_array *array;
              u32 i, size, nelems = 1;
      
              for (i = 0; i < MAX_RESOLVE_DEPTH; i++) {
                      switch (BTF_INFO_KIND(type->info)) {
                      /* type->size can be used */
                      case BTF_KIND_INT:
                      case BTF_KIND_STRUCT:
                      case BTF_KIND_UNION:
                      case BTF_KIND_ENUM:
                              size = type->size;
                              goto resolved;
      
                      case BTF_KIND_PTR:
                              size = sizeof(void *);
                              goto resolved;
      
                      /* Modifiers */
                      case BTF_KIND_TYPEDEF:
                      case BTF_KIND_VOLATILE:
                      case BTF_KIND_CONST:
                      case BTF_KIND_RESTRICT:
                              type = btf_type_by_id(btf, type->type);
                              break;
      
                      case BTF_KIND_ARRAY:
                              if (!array_type)
                                      array_type = type;
                              array = btf_type_array(type);
                              if (nelems && array->nelems > U32_MAX / nelems)
                                      return ERR_PTR(-EINVAL);
                              nelems *= array->nelems;
                              type = btf_type_by_id(btf, array->type);
                              break;
      
                      /* type without size */
                      default:
                              return ERR_PTR(-EINVAL);
                      }
              }
      
              return ERR_PTR(-EINVAL);
      
      resolved:
              if (nelems && size > U32_MAX / nelems)
                      return ERR_PTR(-EINVAL);
      
              *type_size = nelems * size;
              if (total_nelems)
                      *total_nelems = nelems;
              if (elem_type)
                      *elem_type = type;
      
              return array_type ? : type;
      }
      
      /* The input param "type_id" must point to a needs_resolve type */
      static const struct btf_type *btf_type_id_resolve(const struct btf *btf,
                                                        u32 *type_id)
      {
   76         *type_id = btf->resolved_ids[*type_id];
   76         return btf_type_by_id(btf, *type_id);
      }
      
      const struct btf_type *btf_type_id_size(const struct btf *btf,
                                              u32 *type_id, u32 *ret_size)
      {
              const struct btf_type *size_type;
  131         u32 size_type_id = *type_id;
              u32 size = 0;
      
  130         size_type = btf_type_by_id(btf, size_type_id);
  130         if (btf_type_nosize_or_null(size_type))
                      return NULL;
      
  102         if (btf_type_has_size(size_type)) {
   72                 size = size_type->size;
   66         } else if (btf_type_is_array(size_type)) {
    9                 size = btf->resolved_sizes[size_type_id];
   58         } else if (btf_type_is_ptr(size_type)) {
                      size = sizeof(void *);
              } else {
   51                 if (WARN_ON_ONCE(!btf_type_is_modifier(size_type) &&
                                       !btf_type_is_var(size_type)))
  131                         return NULL;
      
   51                 size_type_id = btf->resolved_ids[size_type_id];
   51                 size_type = btf_type_by_id(btf, size_type_id);
   51                 if (btf_type_nosize_or_null(size_type))
                              return NULL;
   41                 else if (btf_type_has_size(size_type))
   31                         size = size_type->size;
   10                 else if (btf_type_is_array(size_type))
    1                         size = btf->resolved_sizes[size_type_id];
    9                 else if (btf_type_is_ptr(size_type))
                              size = sizeof(void *);
                      else
                              return NULL;
              }
      
   93         *type_id = size_type_id;
              if (ret_size)
   39                 *ret_size = size;
      
              return size_type;
      }
      
      static int btf_df_check_member(struct btf_verifier_env *env,
                                     const struct btf_type *struct_type,
                                     const struct btf_member *member,
                                     const struct btf_type *member_type)
      {
              btf_verifier_log_basic(env, struct_type,
                                     "Unsupported check_member");
              return -EINVAL;
      }
      
      static int btf_df_check_kflag_member(struct btf_verifier_env *env,
                                           const struct btf_type *struct_type,
                                           const struct btf_member *member,
                                           const struct btf_type *member_type)
      {
              btf_verifier_log_basic(env, struct_type,
                                     "Unsupported check_kflag_member");
              return -EINVAL;
      }
      
      /* Used for ptr, array and struct/union type members.
       * int, enum and modifier types have their specific callback functions.
       */
      static int btf_generic_check_kflag_member(struct btf_verifier_env *env,
                                                const struct btf_type *struct_type,
                                                const struct btf_member *member,
                                                const struct btf_type *member_type)
      {
   10         if (BTF_MEMBER_BITFIELD_SIZE(member->offset)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member bitfield_size");
                      return -EINVAL;
              }
      
              /* bitfield size is 0, so member->offset represents bit offset only.
               * It is safe to call non kflag check_member variants.
               */
    9         return btf_type_ops(member_type)->check_member(env, struct_type,
                                                             member,
                                                             member_type);
      }
      
      static int btf_df_resolve(struct btf_verifier_env *env,
                                const struct resolve_vertex *v)
      {
              btf_verifier_log_basic(env, v->t, "Unsupported resolve");
              return -EINVAL;
      }
      
      static void btf_df_seq_show(const struct btf *btf, const struct btf_type *t,
                                  u32 type_id, void *data, u8 bits_offsets,
                                  struct seq_file *m)
      {
              seq_printf(m, "<unsupported kind:%u>", BTF_INFO_KIND(t->info));
      }
      
      static int btf_int_check_member(struct btf_verifier_env *env,
                                      const struct btf_type *struct_type,
                                      const struct btf_member *member,
                                      const struct btf_type *member_type)
      {
    9         u32 int_data = btf_type_int(member_type);
              u32 struct_bits_off = member->offset;
              u32 struct_size = struct_type->size;
              u32 nr_copy_bits;
              u32 bytes_offset;
      
              if (U32_MAX - struct_bits_off < BTF_INT_OFFSET(int_data)) {
    6                 btf_verifier_log_member(env, struct_type, member,
                                              "bits_offset exceeds U32_MAX");
                      return -EINVAL;
              }
      
    9         struct_bits_off += BTF_INT_OFFSET(int_data);
              bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
              nr_copy_bits = BTF_INT_BITS(int_data) +
                      BITS_PER_BYTE_MASKED(struct_bits_off);
      
              if (nr_copy_bits > BITS_PER_U128) {
                      btf_verifier_log_member(env, struct_type, member,
                                              "nr_copy_bits exceeds 128");
                      return -EINVAL;
              }
      
    9         if (struct_size < bytes_offset ||
    8             struct_size - bytes_offset < BITS_ROUNDUP_BYTES(nr_copy_bits)) {
    3                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    8         return 0;
      }
      
      static int btf_int_check_kflag_member(struct btf_verifier_env *env,
                                            const struct btf_type *struct_type,
                                            const struct btf_member *member,
                                            const struct btf_type *member_type)
      {
              u32 struct_bits_off, nr_bits, nr_int_data_bits, bytes_offset;
   10         u32 int_data = btf_type_int(member_type);
              u32 struct_size = struct_type->size;
              u32 nr_copy_bits;
      
              /* a regular int type is required for the kflag int member */
              if (!btf_type_int_is_regular(member_type)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member base type");
                      return -EINVAL;
              }
      
              /* check sanity of bitfield size */
    8         nr_bits = BTF_MEMBER_BITFIELD_SIZE(member->offset);
              struct_bits_off = BTF_MEMBER_BIT_OFFSET(member->offset);
              nr_int_data_bits = BTF_INT_BITS(int_data);
              if (!nr_bits) {
                      /* Not a bitfield member, member offset must be at byte
                       * boundary.
                       */
    6                 if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
    2                         btf_verifier_log_member(env, struct_type, member,
                                                      "Invalid member offset");
                              return -EINVAL;
                      }
      
                      nr_bits = nr_int_data_bits;
    3         } else if (nr_bits > nr_int_data_bits) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member bitfield_size");
                      return -EINVAL;
              }
      
    4         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
              nr_copy_bits = nr_bits + BITS_PER_BYTE_MASKED(struct_bits_off);
              if (nr_copy_bits > BITS_PER_U128) {
                      btf_verifier_log_member(env, struct_type, member,
                                              "nr_copy_bits exceeds 128");
                      return -EINVAL;
              }
      
    4         if (struct_size < bytes_offset ||
    4             struct_size - bytes_offset < BITS_ROUNDUP_BYTES(nr_copy_bits)) {
    1                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    7         return 0;
      }
      
      static s32 btf_int_check_meta(struct btf_verifier_env *env,
                                    const struct btf_type *t,
                                    u32 meta_left)
      {
              u32 int_data, nr_bits, meta_needed = sizeof(int_data);
              u16 encoding;
      
   57         if (meta_left < meta_needed) {
    2                 btf_verifier_log_basic(env, t,
                                             "meta_left:%u meta_needed:%u",
                                             meta_left, meta_needed);
                      return -EINVAL;
              }
      
   55         if (btf_type_vlen(t)) {
    2                 btf_verifier_log_type(env, t, "vlen != 0");
                      return -EINVAL;
              }
      
   53         if (btf_type_kflag(t)) {
    1                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
                      return -EINVAL;
              }
      
   52         int_data = btf_type_int(t);
              if (int_data & ~BTF_INT_MASK) {
    2                 btf_verifier_log_basic(env, t, "Invalid int_data:%x",
                                             int_data);
                      return -EINVAL;
              }
      
   50         nr_bits = BTF_INT_BITS(int_data) + BTF_INT_OFFSET(int_data);
      
              if (nr_bits > BITS_PER_U128) {
    1                 btf_verifier_log_type(env, t, "nr_bits exceeds %zu",
                                            BITS_PER_U128);
                      return -EINVAL;
              }
      
   49         if (BITS_ROUNDUP_BYTES(nr_bits) > t->size) {
    2                 btf_verifier_log_type(env, t, "nr_bits exceeds type_size");
                      return -EINVAL;
              }
      
              /*
               * Only one of the encoding bits is allowed and it
               * should be sufficient for the pretty print purpose (i.e. decoding).
               * Multiple bits can be allowed later if it is found
               * to be insufficient.
               */
   47         encoding = BTF_INT_ENCODING(int_data);
              if (encoding &&
                  encoding != BTF_INT_SIGNED &&
    3             encoding != BTF_INT_CHAR &&
                  encoding != BTF_INT_BOOL) {
    2                 btf_verifier_log_type(env, t, "Unsupported encoding");
                      return -ENOTSUPP;
              }
      
   45         btf_verifier_log_type(env, t, NULL);
      
   54         return meta_needed;
      }
      
      static void btf_int_log(struct btf_verifier_env *env,
                              const struct btf_type *t)
      {
   14         int int_data = btf_type_int(t);
      
   14         btf_verifier_log(env,
                               "size=%u bits_offset=%u nr_bits=%u encoding=%s",
                               t->size, BTF_INT_OFFSET(int_data),
                               BTF_INT_BITS(int_data),
                               btf_int_encoding_str(BTF_INT_ENCODING(int_data)));
      }
      
      static void btf_int128_print(struct seq_file *m, void *data)
      {
              /* data points to a __int128 number.
               * Suppose
               *     int128_num = *(__int128 *)data;
               * The below formulas shows what upper_num and lower_num represents:
               *     upper_num = int128_num >> 64;
               *     lower_num = int128_num & 0xffffffffFFFFFFFFULL;
               */
              u64 upper_num, lower_num;
      
      #ifdef __BIG_ENDIAN_BITFIELD
              upper_num = *(u64 *)data;
              lower_num = *(u64 *)(data + 8);
      #else
              upper_num = *(u64 *)(data + 8);
              lower_num = *(u64 *)data;
      #endif
              if (upper_num == 0)
                      seq_printf(m, "0x%llx", lower_num);
              else
                      seq_printf(m, "0x%llx%016llx", upper_num, lower_num);
      }
      
      static void btf_int128_shift(u64 *print_num, u16 left_shift_bits,
                                   u16 right_shift_bits)
      {
              u64 upper_num, lower_num;
      
      #ifdef __BIG_ENDIAN_BITFIELD
              upper_num = print_num[0];
              lower_num = print_num[1];
      #else
              upper_num = print_num[1];
              lower_num = print_num[0];
      #endif
      
              /* shake out un-needed bits by shift/or operations */
              if (left_shift_bits >= 64) {
                      upper_num = lower_num << (left_shift_bits - 64);
                      lower_num = 0;
              } else {
                      upper_num = (upper_num << left_shift_bits) |
                                  (lower_num >> (64 - left_shift_bits));
                      lower_num = lower_num << left_shift_bits;
              }
      
              if (right_shift_bits >= 64) {
                      lower_num = upper_num >> (right_shift_bits - 64);
                      upper_num = 0;
              } else {
                      lower_num = (lower_num >> right_shift_bits) |
                                  (upper_num << (64 - right_shift_bits));
                      upper_num = upper_num >> right_shift_bits;
              }
      
      #ifdef __BIG_ENDIAN_BITFIELD
              print_num[0] = upper_num;
              print_num[1] = lower_num;
      #else
              print_num[0] = lower_num;
              print_num[1] = upper_num;
      #endif
      }
      
      static void btf_bitfield_seq_show(void *data, u8 bits_offset,
                                        u8 nr_bits, struct seq_file *m)
      {
              u16 left_shift_bits, right_shift_bits;
              u8 nr_copy_bytes;
              u8 nr_copy_bits;
              u64 print_num[2] = {};
      
              nr_copy_bits = nr_bits + bits_offset;
              nr_copy_bytes = BITS_ROUNDUP_BYTES(nr_copy_bits);
      
              memcpy(print_num, data, nr_copy_bytes);
      
      #ifdef __BIG_ENDIAN_BITFIELD
              left_shift_bits = bits_offset;
      #else
              left_shift_bits = BITS_PER_U128 - nr_copy_bits;
      #endif
              right_shift_bits = BITS_PER_U128 - nr_bits;
      
              btf_int128_shift(print_num, left_shift_bits, right_shift_bits);
              btf_int128_print(m, print_num);
      }
      
      
      static void btf_int_bits_seq_show(const struct btf *btf,
                                        const struct btf_type *t,
                                        void *data, u8 bits_offset,
                                        struct seq_file *m)
      {
              u32 int_data = btf_type_int(t);
              u8 nr_bits = BTF_INT_BITS(int_data);
              u8 total_bits_offset;
      
              /*
               * bits_offset is at most 7.
               * BTF_INT_OFFSET() cannot exceed 128 bits.
               */
              total_bits_offset = bits_offset + BTF_INT_OFFSET(int_data);
              data += BITS_ROUNDDOWN_BYTES(total_bits_offset);
              bits_offset = BITS_PER_BYTE_MASKED(total_bits_offset);
              btf_bitfield_seq_show(data, bits_offset, nr_bits, m);
      }
      
      static void btf_int_seq_show(const struct btf *btf, const struct btf_type *t,
                                   u32 type_id, void *data, u8 bits_offset,
                                   struct seq_file *m)
      {
              u32 int_data = btf_type_int(t);
              u8 encoding = BTF_INT_ENCODING(int_data);
              bool sign = encoding & BTF_INT_SIGNED;
              u8 nr_bits = BTF_INT_BITS(int_data);
      
              if (bits_offset || BTF_INT_OFFSET(int_data) ||
                  BITS_PER_BYTE_MASKED(nr_bits)) {
                      btf_int_bits_seq_show(btf, t, data, bits_offset, m);
                      return;
              }
      
              switch (nr_bits) {
              case 128:
                      btf_int128_print(m, data);
                      break;
              case 64:
                      if (sign)
                              seq_printf(m, "%lld", *(s64 *)data);
                      else
                              seq_printf(m, "%llu", *(u64 *)data);
                      break;
              case 32:
                      if (sign)
                              seq_printf(m, "%d", *(s32 *)data);
                      else
                              seq_printf(m, "%u", *(u32 *)data);
                      break;
              case 16:
                      if (sign)
                              seq_printf(m, "%d", *(s16 *)data);
                      else
                              seq_printf(m, "%u", *(u16 *)data);
                      break;
              case 8:
                      if (sign)
                              seq_printf(m, "%d", *(s8 *)data);
                      else
                              seq_printf(m, "%u", *(u8 *)data);
                      break;
              default:
                      btf_int_bits_seq_show(btf, t, data, bits_offset, m);
              }
      }
      
      static const struct btf_kind_operations int_ops = {
              .check_meta = btf_int_check_meta,
              .resolve = btf_df_resolve,
              .check_member = btf_int_check_member,
              .check_kflag_member = btf_int_check_kflag_member,
              .log_details = btf_int_log,
              .seq_show = btf_int_seq_show,
      };
      
      static int btf_modifier_check_member(struct btf_verifier_env *env,
                                           const struct btf_type *struct_type,
                                           const struct btf_member *member,
                                           const struct btf_type *member_type)
      {
              const struct btf_type *resolved_type;
   12         u32 resolved_type_id = member->type;
              struct btf_member resolved_member;
              struct btf *btf = env->btf;
      
              resolved_type = btf_type_id_size(btf, &resolved_type_id, NULL);
              if (!resolved_type) {
    3                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member");
                      return -EINVAL;
              }
      
    9         resolved_member = *member;
              resolved_member.type = resolved_type_id;
      
    8         return btf_type_ops(resolved_type)->check_member(env, struct_type,
                                                               &resolved_member,
                                                               resolved_type);
      }
      
      static int btf_modifier_check_kflag_member(struct btf_verifier_env *env,
                                                 const struct btf_type *struct_type,
                                                 const struct btf_member *member,
                                                 const struct btf_type *member_type)
      {
              const struct btf_type *resolved_type;
   10         u32 resolved_type_id = member->type;
              struct btf_member resolved_member;
              struct btf *btf = env->btf;
      
              resolved_type = btf_type_id_size(btf, &resolved_type_id, NULL);
              if (!resolved_type) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member");
                      return -EINVAL;
              }
      
    8         resolved_member = *member;
              resolved_member.type = resolved_type_id;
      
    7         return btf_type_ops(resolved_type)->check_kflag_member(env, struct_type,
                                                                     &resolved_member,
                                                                     resolved_type);
      }
      
      static int btf_ptr_check_member(struct btf_verifier_env *env,
                                      const struct btf_type *struct_type,
                                      const struct btf_member *member,
                                      const struct btf_type *member_type)
      {
              u32 struct_size, struct_bits_off, bytes_offset;
      
    9         struct_size = struct_type->size;
              struct_bits_off = member->offset;
              bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
      
              if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member is not byte aligned");
                      return -EINVAL;
              }
      
    7         if (struct_size - bytes_offset < sizeof(void *)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    8         return 0;
      }
      
      static int btf_ref_type_check_meta(struct btf_verifier_env *env,
                                         const struct btf_type *t,
                                         u32 meta_left)
      {
   94         if (btf_type_vlen(t)) {
    2                 btf_verifier_log_type(env, t, "vlen != 0");
                      return -EINVAL;
              }
      
   92         if (btf_type_kflag(t)) {
    1                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
                      return -EINVAL;
              }
      
   91         if (!BTF_TYPE_ID_VALID(t->type)) {
    2                 btf_verifier_log_type(env, t, "Invalid type_id");
                      return -EINVAL;
              }
      
              /* typedef type must have a valid name, and other ref types,
               * volatile, const, restrict, should have a null name.
               */
   89         if (BTF_INFO_KIND(t->info) == BTF_KIND_TYPEDEF) {
    6                 if (!t->name_off ||
    5                     !btf_name_valid_identifier(env->btf, t->name_off)) {
    4                         btf_verifier_log_type(env, t, "Invalid name");
                              return -EINVAL;
                      }
              } else {
   83                 if (t->name_off) {
                              btf_verifier_log_type(env, t, "Invalid name");
                              return -EINVAL;
                      }
              }
      
   85         btf_verifier_log_type(env, t, NULL);
      
   91         return 0;
      }
      
      static int btf_modifier_resolve(struct btf_verifier_env *env,
                                      const struct resolve_vertex *v)
      {
   45         const struct btf_type *t = v->t;
              const struct btf_type *next_type;
              u32 next_type_id = t->type;
              struct btf *btf = env->btf;
      
   43         next_type = btf_type_by_id(btf, next_type_id);
   43         if (!next_type || btf_type_is_resolve_source_only(next_type)) {
    3                 btf_verifier_log_type(env, v->t, "Invalid type_id");
                      return -EINVAL;
              }
      
   42         if (!env_type_is_resolve_sink(env, next_type) &&
   19             !env_type_is_resolved(env, next_type_id))
    8                 return env_stack_push(env, next_type, next_type_id);
      
              /* Figure out the resolved next_type_id with size.
               * They will be stored in the current modifier's
               * resolved_ids and resolved_sizes such that it can
               * save us a few type-following when we use it later (e.g. in
               * pretty print).
               */
   42         if (!btf_type_id_size(btf, &next_type_id, NULL)) {
   15                 if (env_type_is_resolved(env, next_type_id))
    3                         next_type = btf_type_id_resolve(btf, &next_type_id);
      
                      /* "typedef void new_void", "const void"...etc */
   15                 if (!btf_type_is_void(next_type) &&
    5                     !btf_type_is_fwd(next_type) &&
                          !btf_type_is_func_proto(next_type)) {
    2                         btf_verifier_log_type(env, v->t, "Invalid type_id");
                              return -EINVAL;
                      }
              }
      
   40         env_stack_pop_resolved(env, next_type_id, 0);
      
   44         return 0;
      }
      
      static int btf_var_resolve(struct btf_verifier_env *env,
                                 const struct resolve_vertex *v)
      {
              const struct btf_type *next_type;
   27         const struct btf_type *t = v->t;
              u32 next_type_id = t->type;
              struct btf *btf = env->btf;
      
   26         next_type = btf_type_by_id(btf, next_type_id);
   26         if (!next_type || btf_type_is_resolve_source_only(next_type)) {
    3                 btf_verifier_log_type(env, v->t, "Invalid type_id");
                      return -EINVAL;
              }
      
   24         if (!env_type_is_resolve_sink(env, next_type) &&
   22             !env_type_is_resolved(env, next_type_id))
   21                 return env_stack_push(env, next_type, next_type_id);
      
   24         if (btf_type_is_modifier(next_type)) {
                      const struct btf_type *resolved_type;
                      u32 resolved_type_id;
      
    5                 resolved_type_id = next_type_id;
    5                 resolved_type = btf_type_id_resolve(btf, &resolved_type_id);
      
    5                 if (btf_type_is_ptr(resolved_type) &&
                          !env_type_is_resolve_sink(env, resolved_type) &&
    4                     !env_type_is_resolved(env, resolved_type_id))
                              return env_stack_push(env, resolved_type,
                                                    resolved_type_id);
              }
      
              /* We must resolve to something concrete at this point, no
               * forward types or similar that would resolve to size of
               * zero is allowed.
               */
   24         if (!btf_type_id_size(btf, &next_type_id, NULL)) {
    2                 btf_verifier_log_type(env, v->t, "Invalid type_id");
                      return -EINVAL;
              }
      
   22         env_stack_pop_resolved(env, next_type_id, 0);
      
   25         return 0;
      }
      
      static int btf_ptr_resolve(struct btf_verifier_env *env,
                                 const struct resolve_vertex *v)
      {
              const struct btf_type *next_type;
   45         const struct btf_type *t = v->t;
              u32 next_type_id = t->type;
              struct btf *btf = env->btf;
      
   43         next_type = btf_type_by_id(btf, next_type_id);
   43         if (!next_type || btf_type_is_resolve_source_only(next_type)) {
    3                 btf_verifier_log_type(env, v->t, "Invalid type_id");
                      return -EINVAL;
              }
      
   42         if (!env_type_is_resolve_sink(env, next_type) &&
    7             !env_type_is_resolved(env, next_type_id))
    7                 return env_stack_push(env, next_type, next_type_id);
      
              /* If the modifier was RESOLVED during RESOLVE_STRUCT_OR_ARRAY,
               * the modifier may have stopped resolving when it was resolved
               * to a ptr (last-resolved-ptr).
               *
               * We now need to continue from the last-resolved-ptr to
               * ensure the last-resolved-ptr will not referring back to
               * the currenct ptr (t).
               */
   40         if (btf_type_is_modifier(next_type)) {
                      const struct btf_type *resolved_type;
                      u32 resolved_type_id;
      
    5                 resolved_type_id = next_type_id;
    5                 resolved_type = btf_type_id_resolve(btf, &resolved_type_id);
      
    5                 if (btf_type_is_ptr(resolved_type) &&
                          !env_type_is_resolve_sink(env, resolved_type) &&
    1                     !env_type_is_resolved(env, resolved_type_id))
                              return env_stack_push(env, resolved_type,
                                                    resolved_type_id);
              }
      
   40         if (!btf_type_id_size(btf, &next_type_id, NULL)) {
   39                 if (env_type_is_resolved(env, next_type_id))
    3                         next_type = btf_type_id_resolve(btf, &next_type_id);
      
   39                 if (!btf_type_is_void(next_type) &&
    4                     !btf_type_is_fwd(next_type) &&
                          !btf_type_is_func_proto(next_type)) {
    2                         btf_verifier_log_type(env, v->t, "Invalid type_id");
                              return -EINVAL;
                      }
              }
      
   38         env_stack_pop_resolved(env, next_type_id, 0);
      
   45         return 0;
      }
      
      static void btf_modifier_seq_show(const struct btf *btf,
                                        const struct btf_type *t,
                                        u32 type_id, void *data,
                                        u8 bits_offset, struct seq_file *m)
      {
              if (btf->resolved_ids)
                      t = btf_type_id_resolve(btf, &type_id);
              else
                      t = btf_type_skip_modifiers(btf, type_id, NULL);
      
              btf_type_ops(t)->seq_show(btf, t, type_id, data, bits_offset, m);
      }
      
      static void btf_var_seq_show(const struct btf *btf, const struct btf_type *t,
                                   u32 type_id, void *data, u8 bits_offset,
                                   struct seq_file *m)
      {
              t = btf_type_id_resolve(btf, &type_id);
      
              btf_type_ops(t)->seq_show(btf, t, type_id, data, bits_offset, m);
      }
      
      static void btf_ptr_seq_show(const struct btf *btf, const struct btf_type *t,
                                   u32 type_id, void *data, u8 bits_offset,
                                   struct seq_file *m)
      {
              /* It is a hashed value */
              seq_printf(m, "%p", *(void **)data);
      }
      
      static void btf_ref_type_log(struct btf_verifier_env *env,
                                   const struct btf_type *t)
      {
   51         btf_verifier_log(env, "type_id=%u", t->type);
      }
      
      static struct btf_kind_operations modifier_ops = {
              .check_meta = btf_ref_type_check_meta,
              .resolve = btf_modifier_resolve,
              .check_member = btf_modifier_check_member,
              .check_kflag_member = btf_modifier_check_kflag_member,
              .log_details = btf_ref_type_log,
              .seq_show = btf_modifier_seq_show,
      };
      
      static struct btf_kind_operations ptr_ops = {
              .check_meta = btf_ref_type_check_meta,
              .resolve = btf_ptr_resolve,
              .check_member = btf_ptr_check_member,
              .check_kflag_member = btf_generic_check_kflag_member,
              .log_details = btf_ref_type_log,
              .seq_show = btf_ptr_seq_show,
      };
      
      static s32 btf_fwd_check_meta(struct btf_verifier_env *env,
                                    const struct btf_type *t,
                                    u32 meta_left)
      {
   27         if (btf_type_vlen(t)) {
    2                 btf_verifier_log_type(env, t, "vlen != 0");
                      return -EINVAL;
              }
      
   25         if (t->type) {
    2                 btf_verifier_log_type(env, t, "type != 0");
                      return -EINVAL;
              }
      
              /* fwd type must have a valid name */
   23         if (!t->name_off ||
   21             !btf_name_valid_identifier(env->btf, t->name_off)) {
    3                 btf_verifier_log_type(env, t, "Invalid name");
                      return -EINVAL;
              }
      
   20         btf_verifier_log_type(env, t, NULL);
      
   25         return 0;
      }
      
      static void btf_fwd_type_log(struct btf_verifier_env *env,
                                   const struct btf_type *t)
      {
    9         btf_verifier_log(env, "%s", btf_type_kflag(t) ? "union" : "struct");
      }
      
      static struct btf_kind_operations fwd_ops = {
              .check_meta = btf_fwd_check_meta,
              .resolve = btf_df_resolve,
              .check_member = btf_df_check_member,
              .check_kflag_member = btf_df_check_kflag_member,
              .log_details = btf_fwd_type_log,
              .seq_show = btf_df_seq_show,
      };
      
      static int btf_array_check_member(struct btf_verifier_env *env,
                                        const struct btf_type *struct_type,
                                        const struct btf_member *member,
                                        const struct btf_type *member_type)
      {
    9         u32 struct_bits_off = member->offset;
              u32 struct_size, bytes_offset;
              u32 array_type_id, array_size;
              struct btf *btf = env->btf;
      
              if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member is not byte aligned");
                      return -EINVAL;
              }
      
    7         array_type_id = member->type;
              btf_type_id_size(btf, &array_type_id, &array_size);
              struct_size = struct_type->size;
              bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
              if (struct_size - bytes_offset < array_size) {
    5                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    9         return 0;
      }
      
      static s32 btf_array_check_meta(struct btf_verifier_env *env,
                                      const struct btf_type *t,
                                      u32 meta_left)
      {
              const struct btf_array *array = btf_type_array(t);
              u32 meta_needed = sizeof(*array);
      
   47         if (meta_left < meta_needed) {
    2                 btf_verifier_log_basic(env, t,
                                             "meta_left:%u meta_needed:%u",
                                             meta_left, meta_needed);
                      return -EINVAL;
              }
      
              /* array type should not have a name */
   45         if (t->name_off) {
    1                 btf_verifier_log_type(env, t, "Invalid name");
                      return -EINVAL;
              }
      
   44         if (btf_type_vlen(t)) {
    1                 btf_verifier_log_type(env, t, "vlen != 0");
                      return -EINVAL;
              }
      
   43         if (btf_type_kflag(t)) {
    1                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
                      return -EINVAL;
              }
      
   42         if (t->size) {
    1                 btf_verifier_log_type(env, t, "size != 0");
                      return -EINVAL;
              }
      
              /* Array elem type and index type cannot be in type void,
               * so !array->type and !array->index_type are not allowed.
               */
   41         if (!array->type || !BTF_TYPE_ID_VALID(array->type)) {
    3                 btf_verifier_log_type(env, t, "Invalid elem");
                      return -EINVAL;
              }
      
   38         if (!array->index_type || !BTF_TYPE_ID_VALID(array->index_type)) {
    2                 btf_verifier_log_type(env, t, "Invalid index");
                      return -EINVAL;
              }
      
   36         btf_verifier_log_type(env, t, NULL);
      
   43         return meta_needed;
      }
      
      static int btf_array_resolve(struct btf_verifier_env *env,
                                   const struct resolve_vertex *v)
      {
   32         const struct btf_array *array = btf_type_array(v->t);
              const struct btf_type *elem_type, *index_type;
              u32 elem_type_id, index_type_id;
              struct btf *btf = env->btf;
              u32 elem_size;
      
              /* Check array->index_type */
              index_type_id = array->index_type;
   30         index_type = btf_type_by_id(btf, index_type_id);
   30         if (btf_type_nosize_or_null(index_type) ||
                  btf_type_is_resolve_source_only(index_type)) {
    4                 btf_verifier_log_type(env, v->t, "Invalid index");
                      return -EINVAL;
              }
      
   28         if (!env_type_is_resolve_sink(env, index_type) &&
    4             !env_type_is_resolved(env, index_type_id))
                      return env_stack_push(env, index_type, index_type_id);
      
   27         index_type = btf_type_id_size(btf, &index_type_id, NULL);
   26         if (!index_type || !btf_type_is_int(index_type) ||
   24             !btf_type_int_is_regular(index_type)) {
    4                 btf_verifier_log_type(env, v->t, "Invalid index");
                      return -EINVAL;
              }
      
              /* Check array->type */
   23         elem_type_id = array->type;
   22         elem_type = btf_type_by_id(btf, elem_type_id);
   22         if (btf_type_nosize_or_null(elem_type) ||
                  btf_type_is_resolve_source_only(elem_type)) {
    4                 btf_verifier_log_type(env, v->t,
                                            "Invalid elem");
                      return -EINVAL;
              }
      
   19         if (!env_type_is_resolve_sink(env, elem_type) &&
    4             !env_type_is_resolved(env, elem_type_id))
    5                 return env_stack_push(env, elem_type, elem_type_id);
      
   19         elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
              if (!elem_type) {
    1                 btf_verifier_log_type(env, v->t, "Invalid elem");
                      return -EINVAL;
              }
      
   18         if (btf_type_is_int(elem_type) && !btf_type_int_is_regular(elem_type)) {
                      btf_verifier_log_type(env, v->t, "Invalid array of int");
                      return -EINVAL;
              }
      
   18         if (array->nelems && elem_size > U32_MAX / array->nelems) {
    2                 btf_verifier_log_type(env, v->t,
                                            "Array size overflows U32_MAX");
                      return -EINVAL;
              }
      
   16         env_stack_pop_resolved(env, elem_type_id, elem_size * array->nelems);
      
   28         return 0;
      }
      
      static void btf_array_log(struct btf_verifier_env *env,
                                const struct btf_type *t)
      {
              const struct btf_array *array = btf_type_array(t);
      
   26         btf_verifier_log(env, "type_id=%u index_type_id=%u nr_elems=%u",
                               array->type, array->index_type, array->nelems);
      }
      
      static void btf_array_seq_show(const struct btf *btf, const struct btf_type *t,
                                     u32 type_id, void *data, u8 bits_offset,
                                     struct seq_file *m)
      {
              const struct btf_array *array = btf_type_array(t);
              const struct btf_kind_operations *elem_ops;
              const struct btf_type *elem_type;
              u32 i, elem_size, elem_type_id;
      
              elem_type_id = array->type;
              elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
              elem_ops = btf_type_ops(elem_type);
              seq_puts(m, "[");
              for (i = 0; i < array->nelems; i++) {
                      if (i)
                              seq_puts(m, ",");
      
                      elem_ops->seq_show(btf, elem_type, elem_type_id, data,
                                         bits_offset, m);
                      data += elem_size;
              }
              seq_puts(m, "]");
      }
      
      static struct btf_kind_operations array_ops = {
              .check_meta = btf_array_check_meta,
              .resolve = btf_array_resolve,
              .check_member = btf_array_check_member,
              .check_kflag_member = btf_generic_check_kflag_member,
              .log_details = btf_array_log,
              .seq_show = btf_array_seq_show,
      };
      
      static int btf_struct_check_member(struct btf_verifier_env *env,
                                         const struct btf_type *struct_type,
                                         const struct btf_member *member,
                                         const struct btf_type *member_type)
      {
    8         u32 struct_bits_off = member->offset;
              u32 struct_size, bytes_offset;
      
              if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member is not byte aligned");
                      return -EINVAL;
              }
      
    6         struct_size = struct_type->size;
              bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
              if (struct_size - bytes_offset < member_type->size) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    6         return 0;
      }
      
      static s32 btf_struct_check_meta(struct btf_verifier_env *env,
                                       const struct btf_type *t,
                                       u32 meta_left)
      {
  177         bool is_union = BTF_INFO_KIND(t->info) == BTF_KIND_UNION;
              const struct btf_member *member;
              u32 meta_needed, last_offset;
              struct btf *btf = env->btf;
              u32 struct_size = t->size;
              u32 offset;
              u16 i;
      
              meta_needed = btf_type_vlen(t) * sizeof(*member);
              if (meta_left < meta_needed) {
    2                 btf_verifier_log_basic(env, t,
                                             "meta_left:%u meta_needed:%u",
                                             meta_left, meta_needed);
                      return -EINVAL;
              }
      
              /* struct type either no name or a valid one */
  175         if (t->name_off &&
    3             !btf_name_valid_identifier(env->btf, t->name_off)) {
    2                 btf_verifier_log_type(env, t, "Invalid name");
                      return -EINVAL;
              }
      
  173         btf_verifier_log_type(env, t, NULL);
      
              last_offset = 0;
              for_each_member(i, t, member) {
   85                 if (!btf_name_offset_valid(btf, member->name_off)) {
    4                         btf_verifier_log_member(env, t, member,
                                                      "Invalid member name_offset:%u",
                                                      member->name_off);
  171                         return -EINVAL;
                      }
      
                      /* struct member either no name or a valid one */
   81                 if (member->name_off &&
    5                     !btf_name_valid_identifier(btf, member->name_off)) {
    2                         btf_verifier_log_member(env, t, member, "Invalid name");
                              return -EINVAL;
                      }
                      /* A member cannot be in type void */
   79                 if (!member->type || !BTF_TYPE_ID_VALID(member->type)) {
    2                         btf_verifier_log_member(env, t, member,
                                                      "Invalid type_id");
                              return -EINVAL;
                      }
      
   77                 offset = btf_member_bit_offset(t, member);
   77                 if (is_union && offset) {
                              btf_verifier_log_member(env, t, member,
                                                      "Invalid member bits_offset");
                              return -EINVAL;
                      }
      
                      /*
                       * ">" instead of ">=" because the last member could be
                       * "char a[0];"
                       */
   76                 if (last_offset > offset) {
    2                         btf_verifier_log_member(env, t, member,
                                                      "Invalid member bits_offset");
                              return -EINVAL;
                      }
      
   48                 if (BITS_ROUNDUP_BYTES(offset) > struct_size) {
    1                         btf_verifier_log_member(env, t, member,
                                                      "Member bits_offset exceeds its struct size");
                              return -EINVAL;
                      }
      
   75                 btf_verifier_log_member(env, t, member, NULL);
                      last_offset = offset;
              }
      
  161         return meta_needed;
      }
      
      static int btf_struct_resolve(struct btf_verifier_env *env,
                                    const struct resolve_vertex *v)
      {
              const struct btf_member *member;
              int err;
              u16 i;
      
              /* Before continue resolving the next_member,
               * ensure the last member is indeed resolved to a
               * type with size info.
               */
  157         if (v->next_member) {
                      const struct btf_type *last_member_type;
                      const struct btf_member *last_member;
                      u16 last_member_type_id;
      
    8                 last_member = btf_type_member(v->t) + v->next_member - 1;
                      last_member_type_id = last_member->type;
                      if (WARN_ON_ONCE(!env_type_is_resolved(env,
                                                             last_member_type_id)))
                              return -EINVAL;
      
    8                 last_member_type = btf_type_by_id(env->btf,
                                                        last_member_type_id);
    8                 if (btf_type_kflag(v->t))
    4                         err = btf_type_ops(last_member_type)->check_kflag_member(env, v->t,
                                                                      last_member,
                                                                      last_member_type);
                      else
    4                         err = btf_type_ops(last_member_type)->check_member(env, v->t,
                                                                      last_member,
                                                                      last_member_type);
    5                 if (err)
                              return err;
              }
      
   26         for_each_member_from(i, v->next_member, v->t, member) {
   73                 u32 member_type_id = member->type;
   72                 const struct btf_type *member_type = btf_type_by_id(env->btf,
                                                                      member_type_id);
      
   72                 if (btf_type_nosize_or_null(member_type) ||
                          btf_type_is_resolve_source_only(member_type)) {
    5                         btf_verifier_log_member(env, v->t, member,
                                                      "Invalid member");
  144                         return -EINVAL;
                      }
      
   68                 if (!env_type_is_resolve_sink(env, member_type) &&
   37                     !env_type_is_resolved(env, member_type_id)) {
    9                         env_stack_set_next_member(env, i + 1);
                              return env_stack_push(env, member_type, member_type_id);
                      }
      
   59                 if (btf_type_kflag(v->t))
   27                         err = btf_type_ops(member_type)->check_kflag_member(env, v->t,
                                                                                  member,
                                                                                  member_type);
                      else
   32                         err = btf_type_ops(member_type)->check_member(env, v->t,
                                                                            member,
                                                                            member_type);
   47                 if (err)
                              return err;
              }
      
  115         env_stack_pop_resolved(env, 0, 0);
      
              return 0;
      }
      
      static void btf_struct_log(struct btf_verifier_env *env,
                                 const struct btf_type *t)
      {
   44         btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
      }
      
      /* find 'struct bpf_spin_lock' in map value.
       * return >= 0 offset if found
       * and < 0 in case of error
       */
      int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t)
      {
              const struct btf_member *member;
              u32 i, off = -ENOENT;
      
   19         if (!__btf_type_is_struct(t))
                      return -EINVAL;
      
    4         for_each_member(i, t, member) {
    2                 const struct btf_type *member_type = btf_type_by_id(btf,
                                                                          member->type);
    2                 if (!__btf_type_is_struct(member_type))
                              continue;
                      if (member_type->size != sizeof(struct bpf_spin_lock))
                              continue;
                      if (strcmp(__btf_name_by_offset(btf, member_type->name_off),
                                 "bpf_spin_lock"))
                              continue;
                      if (off != -ENOENT)
                              /* only one 'struct bpf_spin_lock' is allowed */
                              return -E2BIG;
                      off = btf_member_bit_offset(t, member);
                      if (off % 8)
                              /* valid C code cannot generate such BTF */
                              return -EINVAL;
                      off /= 8;
                      if (off % __alignof__(struct bpf_spin_lock))
                              /* valid struct bpf_spin_lock will be 4 byte aligned */
                              return -EINVAL;
              }
   19         return off;
      }
      
      static void btf_struct_seq_show(const struct btf *btf, const struct btf_type *t,
                                      u32 type_id, void *data, u8 bits_offset,
                                      struct seq_file *m)
      {
              const char *seq = BTF_INFO_KIND(t->info) == BTF_KIND_UNION ? "|" : ",";
              const struct btf_member *member;
              u32 i;
      
              seq_puts(m, "{");
              for_each_member(i, t, member) {
                      const struct btf_type *member_type = btf_type_by_id(btf,
                                                                      member->type);
                      const struct btf_kind_operations *ops;
                      u32 member_offset, bitfield_size;
                      u32 bytes_offset;
                      u8 bits8_offset;
      
                      if (i)
                              seq_puts(m, seq);
      
                      member_offset = btf_member_bit_offset(t, member);
                      bitfield_size = btf_member_bitfield_size(t, member);
                      bytes_offset = BITS_ROUNDDOWN_BYTES(member_offset);
                      bits8_offset = BITS_PER_BYTE_MASKED(member_offset);
                      if (bitfield_size) {
                              btf_bitfield_seq_show(data + bytes_offset, bits8_offset,
                                                    bitfield_size, m);
                      } else {
                              ops = btf_type_ops(member_type);
                              ops->seq_show(btf, member_type, member->type,
                                            data + bytes_offset, bits8_offset, m);
                      }
              }
              seq_puts(m, "}");
      }
      
      static struct btf_kind_operations struct_ops = {
              .check_meta = btf_struct_check_meta,
              .resolve = btf_struct_resolve,
              .check_member = btf_struct_check_member,
              .check_kflag_member = btf_generic_check_kflag_member,
              .log_details = btf_struct_log,
              .seq_show = btf_struct_seq_show,
      };
      
      static int btf_enum_check_member(struct btf_verifier_env *env,
                                       const struct btf_type *struct_type,
                                       const struct btf_member *member,
                                       const struct btf_type *member_type)
      {
              u32 struct_bits_off = member->offset;
              u32 struct_size, bytes_offset;
      
              if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
                      btf_verifier_log_member(env, struct_type, member,
                                              "Member is not byte aligned");
                      return -EINVAL;
              }
      
              struct_size = struct_type->size;
              bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
              if (struct_size - bytes_offset < member_type->size) {
                      btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
              return 0;
      }
      
      static int btf_enum_check_kflag_member(struct btf_verifier_env *env,
                                             const struct btf_type *struct_type,
                                             const struct btf_member *member,
                                             const struct btf_type *member_type)
      {
              u32 struct_bits_off, nr_bits, bytes_end, struct_size;
              u32 int_bitsize = sizeof(int) * BITS_PER_BYTE;
      
    9         struct_bits_off = BTF_MEMBER_BIT_OFFSET(member->offset);
              nr_bits = BTF_MEMBER_BITFIELD_SIZE(member->offset);
              if (!nr_bits) {
    6                 if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
    2                         btf_verifier_log_member(env, struct_type, member,
                                                      "Member is not byte aligned");
                              return -EINVAL;
                      }
      
                      nr_bits = int_bitsize;
    3         } else if (nr_bits > int_bitsize) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Invalid member bitfield_size");
                      return -EINVAL;
              }
      
    5         struct_size = struct_type->size;
              bytes_end = BITS_ROUNDUP_BYTES(struct_bits_off + nr_bits);
              if (struct_size < bytes_end) {
    2                 btf_verifier_log_member(env, struct_type, member,
                                              "Member exceeds struct_size");
                      return -EINVAL;
              }
      
    6         return 0;
      }
      
      static s32 btf_enum_check_meta(struct btf_verifier_env *env,
                                     const struct btf_type *t,
                                     u32 meta_left)
      {
              const struct btf_enum *enums = btf_type_enum(t);
   41         struct btf *btf = env->btf;
              u16 i, nr_enums;
              u32 meta_needed;
      
              nr_enums = btf_type_vlen(t);
              meta_needed = nr_enums * sizeof(*enums);
      
              if (meta_left < meta_needed) {
    2                 btf_verifier_log_basic(env, t,
                                             "meta_left:%u meta_needed:%u",
                                             meta_left, meta_needed);
                      return -EINVAL;
              }
      
   39         if (btf_type_kflag(t)) {
    2                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
                      return -EINVAL;
              }
      
   37         if (t->size > 8 || !is_power_of_2(t->size)) {
    4                 btf_verifier_log_type(env, t, "Unexpected size");
                      return -EINVAL;
              }
      
              /* enum type either no name or a valid one */
   33         if (t->name_off &&
    4             !btf_name_valid_identifier(env->btf, t->name_off)) {
    3                 btf_verifier_log_type(env, t, "Invalid name");
   37                 return -EINVAL;
              }
      
   32         btf_verifier_log_type(env, t, NULL);
      
    5         for (i = 0; i < nr_enums; i++) {
    8                 if (!btf_name_offset_valid(btf, enums[i].name_off)) {
    2                         btf_verifier_log(env, "\tInvalid name_offset:%u",
                                               enums[i].name_off);
                              return -EINVAL;
                      }
      
                      /* enum member must have a valid name */
    6                 if (!enums[i].name_off ||
    5                     !btf_name_valid_identifier(btf, enums[i].name_off)) {
                              btf_verifier_log_type(env, t, "Invalid name");
                              return -EINVAL;
                      }
      
    5                 if (env->log.level == BPF_LOG_KERNEL)
                              continue;
    3                 btf_verifier_log(env, "\t%s val=%d\n",
                                       __btf_name_by_offset(btf, enums[i].name_off),
                                       enums[i].val);
              }
      
   28         return meta_needed;
      }
      
      static void btf_enum_log(struct btf_verifier_env *env,
                               const struct btf_type *t)
      {
              btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
      }
      
      static void btf_enum_seq_show(const struct btf *btf, const struct btf_type *t,
                                    u32 type_id, void *data, u8 bits_offset,
                                    struct seq_file *m)
      {
              const struct btf_enum *enums = btf_type_enum(t);
              u32 i, nr_enums = btf_type_vlen(t);
              int v = *(int *)data;
      
              for (i = 0; i < nr_enums; i++) {
                      if (v == enums[i].val) {
                              seq_printf(m, "%s",
                                         __btf_name_by_offset(btf,
                                                              enums[i].name_off));
                              return;
                      }
              }
      
              seq_printf(m, "%d", v);
      }
      
      static struct btf_kind_operations enum_ops = {
              .check_meta = btf_enum_check_meta,
              .resolve = btf_df_resolve,
              .check_member = btf_enum_check_member,
              .check_kflag_member = btf_enum_check_kflag_member,
              .log_details = btf_enum_log,
              .seq_show = btf_enum_seq_show,
      };
      
      static s32 btf_func_proto_check_meta(struct btf_verifier_env *env,
                                           const struct btf_type *t,
                                           u32 meta_left)
      {
   60         u32 meta_needed = btf_type_vlen(t) * sizeof(struct btf_param);
      
              if (meta_left < meta_needed) {
    2                 btf_verifier_log_basic(env, t,
                                             "meta_left:%u meta_needed:%u",
                                             meta_left, meta_needed);
                      return -EINVAL;
              }
      
   58         if (t->name_off) {
    2                 btf_verifier_log_type(env, t, "Invalid name");
                      return -EINVAL;
              }
      
   56         if (btf_type_kflag(t)) {
    1                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
                      return -EINVAL;
              }
      
   55         btf_verifier_log_type(env, t, NULL);
      
   56         return meta_needed;
      }
      
      static void btf_func_proto_log(struct btf_verifier_env *env,
                                     const struct btf_type *t)
      {
   25         const struct btf_param *args = (const struct btf_param *)(t + 1);
   33         u16 nr_args = btf_type_vlen(t), i;
      
              btf_verifier_log(env, "return=%u args=(", t->type);
              if (!nr_args) {
    6                 btf_verifier_log(env, "void");
                      goto done;
              }
      
   28         if (nr_args == 1 && !args[0].type) {
                      /* Only one vararg */
    4                 btf_verifier_log(env, "vararg");
                      goto done;
              }
      
   25         btf_verifier_log(env, "%u %s", args[0].type,
   10                          __btf_name_by_offset(env->btf,
                                                    args[0].name_off));
              for (i = 1; i < nr_args - 1; i++)
   12                 btf_verifier_log(env, ", %u %s", args[i].type,
    8                                  __btf_name_by_offset(env->btf,
   12                                                       args[i].name_off));
      
   24         if (nr_args > 1) {
   20                 const struct btf_param *last_arg = &args[nr_args - 1];
      
                      if (last_arg->type)
    6                         btf_verifier_log(env, ", %u %s", last_arg->type,
    5                                          __btf_name_by_offset(env->btf,
                                                                    last_arg->name_off));
                      else
   14                         btf_verifier_log(env, ", vararg");
              }
      
      done:
   28         btf_verifier_log(env, ")");
      }
      
      static struct btf_kind_operations func_proto_ops = {
              .check_meta = btf_func_proto_check_meta,
              .resolve = btf_df_resolve,
              /*