kernel/bpf/btf.c

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /* Copyright (c) 2018 Facebook */
   3
   4 #include <uapi/linux/btf.h>
   5 #include <uapi/linux/types.h>
   6 #include <linux/seq_file.h>
   7 #include <linux/compiler.h>
   8 #include <linux/ctype.h>
   9 #include <linux/errno.h>
  10 #include <linux/slab.h>
  11 #include <linux/anon_inodes.h>
  12 #include <linux/file.h>
  13 #include <linux/uaccess.h>
  14 #include <linux/kernel.h>
  15 #include <linux/idr.h>
  16 #include <linux/sort.h>
  17 #include <linux/bpf_verifier.h>
  18 #include <linux/btf.h>
  19
  20 /* BTF (BPF Type Format) is the meta data format which describes
  21  * the data types of BPF program/map.  Hence, it basically focus
  22  * on the C programming language which the modern BPF is primary
  23  * using.
  24  *
  25  * ELF Section:
  26  * ~~~~~~~~~~~
  27  * The BTF data is stored under the ".BTF" ELF section
  28  *
  29  * struct btf_type:
  30  * ~~~~~~~~~~~~~~~
  31  * Each 'struct btf_type' object describes a C data type.
  32  * Depending on the type it is describing, a 'struct btf_type'
  33  * object may be followed by more data.  F.e.
  34  * To describe an array, 'struct btf_type' is followed by
  35  * 'struct btf_array'.
  36  *
  37  * 'struct btf_type' and any extra data following it are
  38  * 4 bytes aligned.
  39  *
  40  * Type section:
  41  * ~~~~~~~~~~~~~
  42  * The BTF type section contains a list of 'struct btf_type' objects.
  43  * Each one describes a C type.  Recall from the above section
  44  * that a 'struct btf_type' object could be immediately followed by extra
  45  * data in order to desribe some particular C types.
  46  *
  47  * type_id:
  48  * ~~~~~~~
  49  * Each btf_type object is identified by a type_id.  The type_id
  50  * is implicitly implied by the location of the btf_type object in
  51  * the BTF type section.  The first one has type_id 1.  The second
  52  * one has type_id 2...etc.  Hence, an earlier btf_type has
  53  * a smaller type_id.
  54  *
  55  * A btf_type object may refer to another btf_type object by using
  56  * type_id (i.e. the "type" in the "struct btf_type").
  57  *
  58  * NOTE that we cannot assume any reference-order.
  59  * A btf_type object can refer to an earlier btf_type object
  60  * but it can also refer to a later btf_type object.
  61  *
  62  * For example, to describe "const void *".  A btf_type
  63  * object describing "const" may refer to another btf_type
  64  * object describing "void *".  This type-reference is done
  65  * by specifying type_id:
  66  *
  67  * [1] CONST (anon) type_id=2
  68  * [2] PTR (anon) type_id=0
  69  *
  70  * The above is the btf_verifier debug log:
  71  *   - Each line started with "[?]" is a btf_type object
  72  *   - [?] is the type_id of the btf_type object.
  73  *   - CONST/PTR is the BTF_KIND_XXX
  74  *   - "(anon)" is the name of the type.  It just
  75  *     happens that CONST and PTR has no name.
  76  *   - type_id=XXX is the 'u32 type' in btf_type
  77  *
  78  * NOTE: "void" has type_id 0
  79  *
  80  * String section:
  81  * ~~~~~~~~~~~~~~
  82  * The BTF string section contains the names used by the type section.
  83  * Each string is referred by an "offset" from the beginning of the
  84  * string section.
  85  *
  86  * Each string is '\0' terminated.
  87  *
  88  * The first character in the string section must be '\0'
  89  * which is used to mean 'anonymous'. Some btf_type may not
  90  * have a name.
  91  */
  92
  93 /* BTF verification:
  94  *
  95  * To verify BTF data, two passes are needed.
  96  *
  97  * Pass #1
  98  * ~~~~~~~
  99  * The first pass is to collect all btf_type objects to
 100  * an array: "btf->types".
 101  *
 102  * Depending on the C type that a btf_type is describing,
 103  * a btf_type may be followed by extra data.  We don't know
 104  * how many btf_type is there, and more importantly we don't
 105  * know where each btf_type is located in the type section.
 106  *
 107  * Without knowing the location of each type_id, most verifications
 108  * cannot be done.  e.g. an earlier btf_type may refer to a later
 109  * btf_type (recall the "const void *" above), so we cannot
 110  * check this type-reference in the first pass.
 111  *
 112  * In the first pass, it still does some verifications (e.g.
 113  * checking the name is a valid offset to the string section).
 114  *
 115  * Pass #2
 116  * ~~~~~~~
 117  * The main focus is to resolve a btf_type that is referring
 118  * to another type.
 119  *
 120  * We have to ensure the referring type:
 121  * 1) does exist in the BTF (i.e. in btf->types[])
 122  * 2) does not cause a loop:
 123  *      struct A {
 124  *              struct B b;
 125  *      };
 126  *
 127  *      struct B {
 128  *              struct A a;
 129  *      };
 130  *
 131  * btf_type_needs_resolve() decides if a btf_type needs
 132  * to be resolved.
 133  *
 134  * The needs_resolve type implements the "resolve()" ops which
 135  * essentially does a DFS and detects backedge.
 136  *
 137  * During resolve (or DFS), different C types have different
 138  * "RESOLVED" conditions.
 139  *
 140  * When resolving a BTF_KIND_STRUCT, we need to resolve all its
 141  * members because a member is always referring to another
 142  * type.  A struct's member can be treated as "RESOLVED" if
 143  * it is referring to a BTF_KIND_PTR.  Otherwise, the
 144  * following valid C struct would be rejected:
 145  *
 146  *      struct A {
 147  *              int m;
 148  *              struct A *a;
 149  *      };
 150  *
 151  * When resolving a BTF_KIND_PTR, it needs to keep resolving if
 152  * it is referring to another BTF_KIND_PTR.  Otherwise, we cannot
 153  * detect a pointer loop, e.g.:
 154  * BTF_KIND_CONST -> BTF_KIND_PTR -> BTF_KIND_CONST -> BTF_KIND_PTR +
 155  *                        ^                                         |
 156  *                        +-----------------------------------------+
 157  *
 158  */
 159
 160 #define BITS_PER_U128 (sizeof(u64) * BITS_PER_BYTE * 2)
 161 #define BITS_PER_BYTE_MASK (BITS_PER_BYTE - 1)
 162 #define BITS_PER_BYTE_MASKED(bits) ((bits) & BITS_PER_BYTE_MASK)
 163 #define BITS_ROUNDDOWN_BYTES(bits) ((bits) >> 3)
 164 #define BITS_ROUNDUP_BYTES(bits) \
 165         (BITS_ROUNDDOWN_BYTES(bits) + !!BITS_PER_BYTE_MASKED(bits))
 166
 167 #define BTF_INFO_MASK 0x8f00ffff
 168 #define BTF_INT_MASK 0x0fffffff
 169 #define BTF_TYPE_ID_VALID(type_id) ((type_id) <= BTF_MAX_TYPE)
 170 #define BTF_STR_OFFSET_VALID(name_off) ((name_off) <= BTF_MAX_NAME_OFFSET)
 171
 172 /* 16MB for 64k structs and each has 16 members and
 173  * a few MB spaces for the string section.
 174  * The hard limit is S32_MAX.
 175  */
 176 #define BTF_MAX_SIZE (16 * 1024 * 1024)
 177
 178 #define for_each_member(i, struct_type, member)                 \
 179         for (i = 0, member = btf_type_member(struct_type);      \
 180              i < btf_type_vlen(struct_type);                    \
 181              i++, member++)
 182
 183 #define for_each_member_from(i, from, struct_type, member)              \
 184         for (i = from, member = btf_type_member(struct_type) + from;    \
 185              i < btf_type_vlen(struct_type);                            \
 186              i++, member++)
 187
 188 static DEFINE_IDR(btf_idr);
 189 static DEFINE_SPINLOCK(btf_idr_lock);
 190
 191 struct btf {
 192         void *data;
 193         struct btf_type **types;
 194         u32 *resolved_ids;
 195         u32 *resolved_sizes;
 196         const char *strings;
 197         void *nohdr_data;
 198         struct btf_header hdr;
 199         u32 nr_types;
 200         u32 types_size;
 201         u32 data_size;
 202         refcount_t refcnt;
 203         u32 id;
 204         struct rcu_head rcu;
 205 };
 206
 207 enum verifier_phase {
 208         CHECK_META,
 209         CHECK_TYPE,
 210 };
 211
 212 struct resolve_vertex {
 213         const struct btf_type *t;
 214         u32 type_id;
 215         u16 next_member;
 216 };
 217
 218 enum visit_state {
 219         NOT_VISITED,
 220         VISITED,
 221         RESOLVED,
 222 };
 223
 224 enum resolve_mode {
 225         RESOLVE_TBD,    /* To Be Determined */
 226         RESOLVE_PTR,    /* Resolving for Pointer */
 227         RESOLVE_STRUCT_OR_ARRAY,        /* Resolving for struct/union
 228                                          * or array
 229                                          */
 230 };
 231
 232 #define MAX_RESOLVE_DEPTH 32
 233
 234 struct btf_sec_info {
 235         u32 off;
 236         u32 len;
 237 };
 238
 239 struct btf_verifier_env {
 240         struct btf *btf;
 241         u8 *visit_states;
 242         struct resolve_vertex stack[MAX_RESOLVE_DEPTH];
 243         struct bpf_verifier_log log;
 244         u32 log_type_id;
 245         u32 top_stack;
 246         enum verifier_phase phase;
 247         enum resolve_mode resolve_mode;
 248 };
 249
 250 static const char * const btf_kind_str[NR_BTF_KINDS] = {
 251         [BTF_KIND_UNKN]         = "UNKNOWN",
 252         [BTF_KIND_INT]          = "INT",
 253         [BTF_KIND_PTR]          = "PTR",
 254         [BTF_KIND_ARRAY]        = "ARRAY",
 255         [BTF_KIND_STRUCT]       = "STRUCT",
 256         [BTF_KIND_UNION]        = "UNION",
 257         [BTF_KIND_ENUM]         = "ENUM",
 258         [BTF_KIND_FWD]          = "FWD",
 259         [BTF_KIND_TYPEDEF]      = "TYPEDEF",
 260         [BTF_KIND_VOLATILE]     = "VOLATILE",
 261         [BTF_KIND_CONST]        = "CONST",
 262         [BTF_KIND_RESTRICT]     = "RESTRICT",
 263         [BTF_KIND_FUNC]         = "FUNC",
 264         [BTF_KIND_FUNC_PROTO]   = "FUNC_PROTO",
 265 };
 266
 267 struct btf_kind_operations {
 268         s32 (*check_meta)(struct btf_verifier_env *env,
 269                           const struct btf_type *t,
 270                           u32 meta_left);
 271         int (*resolve)(struct btf_verifier_env *env,
 272                        const struct resolve_vertex *v);
 273         int (*check_member)(struct btf_verifier_env *env,
 274                             const struct btf_type *struct_type,
 275                             const struct btf_member *member,
 276                             const struct btf_type *member_type);
 277         int (*check_kflag_member)(struct btf_verifier_env *env,
 278                                   const struct btf_type *struct_type,
 279                                   const struct btf_member *member,
 280                                   const struct btf_type *member_type);
 281         void (*log_details)(struct btf_verifier_env *env,
 282                             const struct btf_type *t);
 283         void (*seq_show)(const struct btf *btf, const struct btf_type *t,
 284                          u32 type_id, void *data, u8 bits_offsets,
 285                          struct seq_file *m);
 286 };
 287
 288 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS];
 289 static struct btf_type btf_void;
 290
 291 static int btf_resolve(struct btf_verifier_env *env,
 292                        const struct btf_type *t, u32 type_id);
 293
 294 static bool btf_type_is_modifier(const struct btf_type *t)
 295 {
 296         /* Some of them is not strictly a C modifier
 297          * but they are grouped into the same bucket
 298          * for BTF concern:
 299          *   A type (t) that refers to another
 300          *   type through t->type AND its size cannot
 301          *   be determined without following the t->type.
 302          *
 303          * ptr does not fall into this bucket
 304          * because its size is always sizeof(void *).
 305          */
 306         switch (BTF_INFO_KIND(t->info)) {
 307         case BTF_KIND_TYPEDEF:
 308         case BTF_KIND_VOLATILE:
 309         case BTF_KIND_CONST:
 310         case BTF_KIND_RESTRICT:
 311                 return true;
 312         }
 313
 314         return false;
 315 }
 316
 317 static bool btf_type_is_void(const struct btf_type *t)
 318 {
 319         return t == &btf_void;
 320 }
 321
 322 static bool btf_type_is_fwd(const struct btf_type *t)
 323 {
 324         return BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
 325 }
 326
 327 static bool btf_type_is_func(const struct btf_type *t)
 328 {
 329         return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC;
 330 }
 331
 332 static bool btf_type_is_func_proto(const struct btf_type *t)
 333 {
 334         return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC_PROTO;
 335 }
 336
 337 static bool btf_type_nosize(const struct btf_type *t)
 338 {
 339         return btf_type_is_void(t) || btf_type_is_fwd(t) ||
 340                btf_type_is_func(t) || btf_type_is_func_proto(t);
 341 }
 342
 343 static bool btf_type_nosize_or_null(const struct btf_type *t)
 344 {
 345         return !t || btf_type_nosize(t);
 346 }
 347
 348 /* union is only a special case of struct:
 349  * all its offsetof(member) == 0
 350  */
 351 static bool btf_type_is_struct(const struct btf_type *t)
 352 {
 353         u8 kind = BTF_INFO_KIND(t->info);
 354
 355         return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
 356 }
 357
 358 static bool __btf_type_is_struct(const struct btf_type *t)
 359 {
 360         return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;
 361 }
 362
 363 static bool btf_type_is_array(const struct btf_type *t)
 364 {
 365         return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
 366 }
 367
 368 static bool btf_type_is_ptr(const struct btf_type *t)
 369 {
 370         return BTF_INFO_KIND(t->info) == BTF_KIND_PTR;
 371 }
 372
 373 static bool btf_type_is_int(const struct btf_type *t)
 374 {
 375         return BTF_INFO_KIND(t->info) == BTF_KIND_INT;
 376 }
 377
 378 /* What types need to be resolved?
 379  *
 380  * btf_type_is_modifier() is an obvious one.
 381  *
 382  * btf_type_is_struct() because its member refers to
 383  * another type (through member->type).
 384
 385  * btf_type_is_array() because its element (array->type)
 386  * refers to another type.  Array can be thought of a
 387  * special case of struct while array just has the same
 388  * member-type repeated by array->nelems of times.
 389  */
 390 static bool btf_type_needs_resolve(const struct btf_type *t)
 391 {
 392         return btf_type_is_modifier(t) ||
 393                 btf_type_is_ptr(t) ||
 394                 btf_type_is_struct(t) ||
 395                 btf_type_is_array(t);
 396 }
 397
 398 /* t->size can be used */
 399 static bool btf_type_has_size(const struct btf_type *t)
 400 {
 401         switch (BTF_INFO_KIND(t->info)) {
 402         case BTF_KIND_INT:
 403         case BTF_KIND_STRUCT:
 404         case BTF_KIND_UNION:
 405         case BTF_KIND_ENUM:
 406                 return true;
 407         }
 408
 409         return false;
 410 }
 411
 412 static const char *btf_int_encoding_str(u8 encoding)
 413 {
 414         if (encoding == 0)
 415                 return "(none)";
 416         else if (encoding == BTF_INT_SIGNED)
 417                 return "SIGNED";
 418         else if (encoding == BTF_INT_CHAR)
 419                 return "CHAR";
 420         else if (encoding == BTF_INT_BOOL)
 421                 return "BOOL";
 422         else
 423                 return "UNKN";
 424 }
 425
 426 static u16 btf_type_vlen(const struct btf_type *t)
 427 {
 428         return BTF_INFO_VLEN(t->info);
 429 }
 430
 431 static bool btf_type_kflag(const struct btf_type *t)
 432 {
 433         return BTF_INFO_KFLAG(t->info);
 434 }
 435
 436 static u32 btf_member_bit_offset(const struct btf_type *struct_type,
 437                              const struct btf_member *member)
 438 {
 439         return btf_type_kflag(struct_type) ? BTF_MEMBER_BIT_OFFSET(member->offset)
 440                                            : member->offset;
 441 }
 442
 443 static u32 btf_member_bitfield_size(const struct btf_type *struct_type,
 444                                     const struct btf_member *member)
 445 {
 446         return btf_type_kflag(struct_type) ? BTF_MEMBER_BITFIELD_SIZE(member->offset)
 447                                            : 0;
 448 }
 449
 450 static u32 btf_type_int(const struct btf_type *t)
 451 {
 452         return *(u32 *)(t + 1);
 453 }
 454
 455 static const struct btf_array *btf_type_array(const struct btf_type *t)
 456 {
 457         return (const struct btf_array *)(t + 1);
 458 }
 459
 460 static const struct btf_member *btf_type_member(const struct btf_type *t)
 461 {
 462         return (const struct btf_member *)(t + 1);
 463 }
 464
 465 static const struct btf_enum *btf_type_enum(const struct btf_type *t)
 466 {
 467         return (const struct btf_enum *)(t + 1);
 468 }
 469
 470 static const struct btf_kind_operations *btf_type_ops(const struct btf_type *t)
 471 {
 472         return kind_ops[BTF_INFO_KIND(t->info)];
 473 }
 474
 475 static bool btf_name_offset_valid(const struct btf *btf, u32 offset)
 476 {
 477         return BTF_STR_OFFSET_VALID(offset) &&
 478                 offset < btf->hdr.str_len;
 479 }
 480
 481 /* Only C-style identifier is permitted. This can be relaxed if
 482  * necessary.
 483  */
 484 static bool btf_name_valid_identifier(const struct btf *btf, u32 offset)
 485 {
 486         /* offset must be valid */
 487         const char *src = &btf->strings[offset];
 488         const char *src_limit;
 489
 490         if (!isalpha(*src) && *src != '_')
 491                 return false;
 492
 493         /* set a limit on identifier length */
 494         src_limit = src + KSYM_NAME_LEN;
 495         src++;
 496         while (*src && src < src_limit) {
 497                 if (!isalnum(*src) && *src != '_')
 498                         return false;
 499                 src++;
 500         }
 501
 502         return !*src;
 503 }
 504
 505 static const char *__btf_name_by_offset(const struct btf *btf, u32 offset)
 506 {
 507         if (!offset)
 508                 return "(anon)";
 509         else if (offset < btf->hdr.str_len)
 510                 return &btf->strings[offset];
 511         else
 512                 return "(invalid-name-offset)";
 513 }
 514
 515 const char *btf_name_by_offset(const struct btf *btf, u32 offset)
 516 {
 517         if (offset < btf->hdr.str_len)
 518                 return &btf->strings[offset];
 519
 520         return NULL;
 521 }
 522
 523 const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id)
 524 {
 525         if (type_id > btf->nr_types)
 526                 return NULL;
 527
 528         return btf->types[type_id];
 529 }
 530
 531 /*
 532  * Regular int is not a bit field and it must be either
 533  * u8/u16/u32/u64 or __int128.
 534  */
 535 static bool btf_type_int_is_regular(const struct btf_type *t)
 536 {
 537         u8 nr_bits, nr_bytes;
 538         u32 int_data;
 539
 540         int_data = btf_type_int(t);
 541         nr_bits = BTF_INT_BITS(int_data);
 542         nr_bytes = BITS_ROUNDUP_BYTES(nr_bits);
 543         if (BITS_PER_BYTE_MASKED(nr_bits) ||
 544             BTF_INT_OFFSET(int_data) ||
 545             (nr_bytes != sizeof(u8) && nr_bytes != sizeof(u16) &&
 546              nr_bytes != sizeof(u32) && nr_bytes != sizeof(u64) &&
 547              nr_bytes != (2 * sizeof(u64)))) {
 548                 return false;
 549         }
 550
 551         return true;
 552 }
 553
 554 /*
 555  * Check that given struct member is a regular int with expected
 556  * offset and size.
 557  */
 558 bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
 559                            const struct btf_member *m,
 560                            u32 expected_offset, u32 expected_size)
 561 {
 562         const struct btf_type *t;
 563         u32 id, int_data;
 564         u8 nr_bits;
 565
 566         id = m->type;
 567         t = btf_type_id_size(btf, &id, NULL);
 568         if (!t || !btf_type_is_int(t))
 569                 return false;
 570
 571         int_data = btf_type_int(t);
 572         nr_bits = BTF_INT_BITS(int_data);
 573         if (btf_type_kflag(s)) {
 574                 u32 bitfield_size = BTF_MEMBER_BITFIELD_SIZE(m->offset);
 575                 u32 bit_offset = BTF_MEMBER_BIT_OFFSET(m->offset);
 576
 577                 /* if kflag set, int should be a regular int and
 578                  * bit offset should be at byte boundary.
 579                  */
 580                 return !bitfield_size &&
 581                        BITS_ROUNDUP_BYTES(bit_offset) == expected_offset &&
 582                        BITS_ROUNDUP_BYTES(nr_bits) == expected_size;
 583         }
 584
 585         if (BTF_INT_OFFSET(int_data) ||
 586             BITS_PER_BYTE_MASKED(m->offset) ||
 587             BITS_ROUNDUP_BYTES(m->offset) != expected_offset ||
 588             BITS_PER_BYTE_MASKED(nr_bits) ||
 589             BITS_ROUNDUP_BYTES(nr_bits) != expected_size)
 590                 return false;
 591
 592         return true;
 593 }
 594
 595 __printf(2, 3) static void __btf_verifier_log(struct bpf_verifier_log *log,
 596                                               const char *fmt, ...)
 597 {
 598         va_list args;
 599
 600         va_start(args, fmt);
 601         bpf_verifier_vlog(log, fmt, args);
 602         va_end(args);
 603 }
 604
 605 __printf(2, 3) static void btf_verifier_log(struct btf_verifier_env *env,
 606                                             const char *fmt, ...)
 607 {
 608         struct bpf_verifier_log *log = &env->log;
 609         va_list args;
 610
 611         if (!bpf_verifier_log_needed(log))
 612                 return;
 613
 614         va_start(args, fmt);
 615         bpf_verifier_vlog(log, fmt, args);
 616         va_end(args);
 617 }
 618
 619 __printf(4, 5) static void __btf_verifier_log_type(struct btf_verifier_env *env,
 620                                                    const struct btf_type *t,
 621                                                    bool log_details,
 622                                                    const char *fmt, ...)
 623 {
 624         struct bpf_verifier_log *log = &env->log;
 625         u8 kind = BTF_INFO_KIND(t->info);
 626         struct btf *btf = env->btf;
 627         va_list args;
 628
 629         if (!bpf_verifier_log_needed(log))
 630                 return;
 631
 632         __btf_verifier_log(log, "[%u] %s %s%s",
 633                            env->log_type_id,
 634                            btf_kind_str[kind],
 635                            __btf_name_by_offset(btf, t->name_off),
 636                            log_details ? " " : "");
 637
 638         if (log_details)
 639                 btf_type_ops(t)->log_details(env, t);
 640
 641         if (fmt && *fmt) {
 642                 __btf_verifier_log(log, " ");
 643                 va_start(args, fmt);
 644                 bpf_verifier_vlog(log, fmt, args);
 645                 va_end(args);
 646         }
 647
 648         __btf_verifier_log(log, "\n");
 649 }
 650
 651 #define btf_verifier_log_type(env, t, ...) \
 652         __btf_verifier_log_type((env), (t), true, __VA_ARGS__)
 653 #define btf_verifier_log_basic(env, t, ...) \
 654         __btf_verifier_log_type((env), (t), false, __VA_ARGS__)
 655
 656 __printf(4, 5)
 657 static void btf_verifier_log_member(struct btf_verifier_env *env,
 658                                     const struct btf_type *struct_type,
 659                                     const struct btf_member *member,
 660                                     const char *fmt, ...)
 661 {
 662         struct bpf_verifier_log *log = &env->log;
 663         struct btf *btf = env->btf;
 664         va_list args;
 665
 666         if (!bpf_verifier_log_needed(log))
 667                 return;
 668
 669         /* The CHECK_META phase already did a btf dump.
 670          *
 671          * If member is logged again, it must hit an error in
 672          * parsing this member.  It is useful to print out which
 673          * struct this member belongs to.
 674          */
 675         if (env->phase != CHECK_META)
 676                 btf_verifier_log_type(env, struct_type, NULL);
 677
 678         if (btf_type_kflag(struct_type))
 679                 __btf_verifier_log(log,
 680                                    "\t%s type_id=%u bitfield_size=%u bits_offset=%u",
 681                                    __btf_name_by_offset(btf, member->name_off),
 682                                    member->type,
 683                                    BTF_MEMBER_BITFIELD_SIZE(member->offset),
 684                                    BTF_MEMBER_BIT_OFFSET(member->offset));
 685         else
 686                 __btf_verifier_log(log, "\t%s type_id=%u bits_offset=%u",
 687                                    __btf_name_by_offset(btf, member->name_off),
 688                                    member->type, member->offset);
 689
 690         if (fmt && *fmt) {
 691                 __btf_verifier_log(log, " ");
 692                 va_start(args, fmt);
 693                 bpf_verifier_vlog(log, fmt, args);
 694                 va_end(args);
 695         }
 696
 697         __btf_verifier_log(log, "\n");
 698 }
 699
 700 static void btf_verifier_log_hdr(struct btf_verifier_env *env,
 701                                  u32 btf_data_size)
 702 {
 703         struct bpf_verifier_log *log = &env->log;
 704         const struct btf *btf = env->btf;
 705         const struct btf_header *hdr;
 706
 707         if (!bpf_verifier_log_needed(log))
 708                 return;
 709
 710         hdr = &btf->hdr;
 711         __btf_verifier_log(log, "magic: 0x%x\n", hdr->magic);
 712         __btf_verifier_log(log, "version: %u\n", hdr->version);
 713         __btf_verifier_log(log, "flags: 0x%x\n", hdr->flags);
 714         __btf_verifier_log(log, "hdr_len: %u\n", hdr->hdr_len);
 715         __btf_verifier_log(log, "type_off: %u\n", hdr->type_off);
 716         __btf_verifier_log(log, "type_len: %u\n", hdr->type_len);
 717         __btf_verifier_log(log, "str_off: %u\n", hdr->str_off);
 718         __btf_verifier_log(log, "str_len: %u\n", hdr->str_len);
 719         __btf_verifier_log(log, "btf_total_size: %u\n", btf_data_size);
 720 }
 721
 722 static int btf_add_type(struct btf_verifier_env *env, struct btf_type *t)
 723 {
 724         struct btf *btf = env->btf;
 725
 726         /* < 2 because +1 for btf_void which is always in btf->types[0].
 727          * btf_void is not accounted in btf->nr_types because btf_void
 728          * does not come from the BTF file.
 729          */
 730         if (btf->types_size - btf->nr_types < 2) {
 731                 /* Expand 'types' array */
 732
 733                 struct btf_type **new_types;
 734                 u32 expand_by, new_size;
 735
 736                 if (btf->types_size == BTF_MAX_TYPE) {
 737                         btf_verifier_log(env, "Exceeded max num of types");
 738                         return -E2BIG;
 739                 }
 740
 741                 expand_by = max_t(u32, btf->types_size >> 2, 16);
 742                 new_size = min_t(u32, BTF_MAX_TYPE,
 743                                  btf->types_size + expand_by);
 744
 745                 new_types = kvcalloc(new_size, sizeof(*new_types),
 746                                      GFP_KERNEL | __GFP_NOWARN);
 747                 if (!new_types)
 748                         return -ENOMEM;
 749
 750                 if (btf->nr_types == 0)
 751                         new_types[0] = &btf_void;
 752                 else
 753                         memcpy(new_types, btf->types,
 754                                sizeof(*btf->types) * (btf->nr_types + 1));
 755
 756                 kvfree(btf->types);
 757                 btf->types = new_types;
 758                 btf->types_size = new_size;
 759         }
 760
 761         btf->types[++(btf->nr_types)] = t;
 762
 763         return 0;
 764 }
 765
 766 static int btf_alloc_id(struct btf *btf)
 767 {
 768         int id;
 769
 770         idr_preload(GFP_KERNEL);
 771         spin_lock_bh(&btf_idr_lock);
 772         id = idr_alloc_cyclic(&btf_idr, btf, 1, INT_MAX, GFP_ATOMIC);
 773         if (id > 0)
 774                 btf->id = id;
 775         spin_unlock_bh(&btf_idr_lock);
 776         idr_preload_end();
 777
 778         if (WARN_ON_ONCE(!id))
 779                 return -ENOSPC;
 780
 781         return id > 0 ? 0 : id;
 782 }
 783
 784 static void btf_free_id(struct btf *btf)
 785 {
 786         unsigned long flags;
 787
 788         /*
 789          * In map-in-map, calling map_delete_elem() on outer
 790          * map will call bpf_map_put on the inner map.
 791          * It will then eventually call btf_free_id()
 792          * on the inner map.  Some of the map_delete_elem()
 793          * implementation may have irq disabled, so
 794          * we need to use the _irqsave() version instead
 795          * of the _bh() version.
 796          */
 797         spin_lock_irqsave(&btf_idr_lock, flags);
 798         idr_remove(&btf_idr, btf->id);
 799         spin_unlock_irqrestore(&btf_idr_lock, flags);
 800 }
 801
 802 static void btf_free(struct btf *btf)
 803 {
 804         kvfree(btf->types);
 805         kvfree(btf->resolved_sizes);
 806         kvfree(btf->resolved_ids);
 807         kvfree(btf->data);
 808         kfree(btf);
 809 }
 810
 811 static void btf_free_rcu(struct rcu_head *rcu)
 812 {
 813         struct btf *btf = container_of(rcu, struct btf, rcu);
 814
 815         btf_free(btf);
 816 }
 817
 818 void btf_put(struct btf *btf)
 819 {
 820         if (btf && refcount_dec_and_test(&btf->refcnt)) {
 821                 btf_free_id(btf);
 822                 call_rcu(&btf->rcu, btf_free_rcu);
 823         }
 824 }
 825
 826 static int env_resolve_init(struct btf_verifier_env *env)
 827 {
 828         struct btf *btf = env->btf;
 829         u32 nr_types = btf->nr_types;
 830         u32 *resolved_sizes = NULL;
 831         u32 *resolved_ids = NULL;
 832         u8 *visit_states = NULL;
 833
 834         /* +1 for btf_void */
 835         resolved_sizes = kvcalloc(nr_types + 1, sizeof(*resolved_sizes),
 836                                   GFP_KERNEL | __GFP_NOWARN);
 837         if (!resolved_sizes)
 838                 goto nomem;
 839
 840         resolved_ids = kvcalloc(nr_types + 1, sizeof(*resolved_ids),
 841                                 GFP_KERNEL | __GFP_NOWARN);
 842         if (!resolved_ids)
 843                 goto nomem;
 844
 845         visit_states = kvcalloc(nr_types + 1, sizeof(*visit_states),
 846                                 GFP_KERNEL | __GFP_NOWARN);
 847         if (!visit_states)
 848                 goto nomem;
 849
 850         btf->resolved_sizes = resolved_sizes;
 851         btf->resolved_ids = resolved_ids;
 852         env->visit_states = visit_states;
 853
 854         return 0;
 855
 856 nomem:
 857         kvfree(resolved_sizes);
 858         kvfree(resolved_ids);
 859         kvfree(visit_states);
 860         return -ENOMEM;
 861 }
 862
 863 static void btf_verifier_env_free(struct btf_verifier_env *env)
 864 {
 865         kvfree(env->visit_states);
 866         kfree(env);
 867 }
 868
 869 static bool env_type_is_resolve_sink(const struct btf_verifier_env *env,
 870                                      const struct btf_type *next_type)
 871 {
 872         switch (env->resolve_mode) {
 873         case RESOLVE_TBD:
 874                 /* int, enum or void is a sink */
 875                 return !btf_type_needs_resolve(next_type);
 876         case RESOLVE_PTR:
 877                 /* int, enum, void, struct, array, func or func_proto is a sink
 878                  * for ptr
 879                  */
 880                 return !btf_type_is_modifier(next_type) &&
 881                         !btf_type_is_ptr(next_type);
 882         case RESOLVE_STRUCT_OR_ARRAY:
 883                 /* int, enum, void, ptr, func or func_proto is a sink
 884                  * for struct and array
 885                  */
 886                 return !btf_type_is_modifier(next_type) &&
 887                         !btf_type_is_array(next_type) &&
 888                         !btf_type_is_struct(next_type);
 889         default:
 890                 BUG();
 891         }
 892 }
 893
 894 static bool env_type_is_resolved(const struct btf_verifier_env *env,
 895                                  u32 type_id)
 896 {
 897         return env->visit_states[type_id] == RESOLVED;
 898 }
 899
 900 static int env_stack_push(struct btf_verifier_env *env,
 901                           const struct btf_type *t, u32 type_id)
 902 {
 903         struct resolve_vertex *v;
 904
 905         if (env->top_stack == MAX_RESOLVE_DEPTH)
 906                 return -E2BIG;
 907
 908         if (env->visit_states[type_id] != NOT_VISITED)
 909                 return -EEXIST;
 910
 911         env->visit_states[type_id] = VISITED;
 912
 913         v = &env->stack[env->top_stack++];
 914         v->t = t;
 915         v->type_id = type_id;
 916         v->next_member = 0;
 917
 918         if (env->resolve_mode == RESOLVE_TBD) {
 919                 if (btf_type_is_ptr(t))
 920                         env->resolve_mode = RESOLVE_PTR;
 921                 else if (btf_type_is_struct(t) || btf_type_is_array(t))
 922                         env->resolve_mode = RESOLVE_STRUCT_OR_ARRAY;
 923         }
 924
 925         return 0;
 926 }
 927
 928 static void env_stack_set_next_member(struct btf_verifier_env *env,
 929                                       u16 next_member)
 930 {
 931         env->stack[env->top_stack - 1].next_member = next_member;
 932 }
 933
 934 static void env_stack_pop_resolved(struct btf_verifier_env *env,
 935                                    u32 resolved_type_id,
 936                                    u32 resolved_size)
 937 {
 938         u32 type_id = env->stack[--(env->top_stack)].type_id;
 939         struct btf *btf = env->btf;
 940
 941         btf->resolved_sizes[type_id] = resolved_size;
 942         btf->resolved_ids[type_id] = resolved_type_id;
 943         env->visit_states[type_id] = RESOLVED;
 944 }
 945
 946 static const struct resolve_vertex *env_stack_peak(struct btf_verifier_env *env)
 947 {
 948         return env->top_stack ? &env->stack[env->top_stack - 1] : NULL;
 949 }
 950
 951 /* The input param "type_id" must point to a needs_resolve type */
 952 static const struct btf_type *btf_type_id_resolve(const struct btf *btf,
 953                                                   u32 *type_id)
 954 {
 955         *type_id = btf->resolved_ids[*type_id];
 956         return btf_type_by_id(btf, *type_id);
 957 }
 958
 959 const struct btf_type *btf_type_id_size(const struct btf *btf,
 960                                         u32 *type_id, u32 *ret_size)
 961 {
 962         const struct btf_type *size_type;
 963         u32 size_type_id = *type_id;
 964         u32 size = 0;
 965
 966         size_type = btf_type_by_id(btf, size_type_id);
 967         if (btf_type_nosize_or_null(size_type))
 968                 return NULL;
 969
 970         if (btf_type_has_size(size_type)) {
 971                 size = size_type->size;
 972         } else if (btf_type_is_array(size_type)) {
 973                 size = btf->resolved_sizes[size_type_id];
 974         } else if (btf_type_is_ptr(size_type)) {
 975                 size = sizeof(void *);
 976         } else {
 977                 if (WARN_ON_ONCE(!btf_type_is_modifier(size_type)))
 978                         return NULL;
 979
 980                 size = btf->resolved_sizes[size_type_id];
 981                 size_type_id = btf->resolved_ids[size_type_id];
 982                 size_type = btf_type_by_id(btf, size_type_id);
 983                 if (btf_type_nosize_or_null(size_type))
 984                         return NULL;
 985         }
 986
 987         *type_id = size_type_id;
 988         if (ret_size)
 989                 *ret_size = size;
 990
 991         return size_type;
 992 }
 993
 994 static int btf_df_check_member(struct btf_verifier_env *env,
 995                                const struct btf_type *struct_type,
 996                                const struct btf_member *member,
 997                                const struct btf_type *member_type)
 998 {
 999         btf_verifier_log_basic(env, struct_type,
1000                                "Unsupported check_member");
1001         return -EINVAL;
1002 }
1003
1004 static int btf_df_check_kflag_member(struct btf_verifier_env *env,
1005                                      const struct btf_type *struct_type,
1006                                      const struct btf_member *member,
1007                                      const struct btf_type *member_type)
1008 {
1009         btf_verifier_log_basic(env, struct_type,
1010                                "Unsupported check_kflag_member");
1011         return -EINVAL;
1012 }
1013
1014 /* Used for ptr, array and struct/union type members.
1015  * int, enum and modifier types have their specific callback functions.
1016  */
1017 static int btf_generic_check_kflag_member(struct btf_verifier_env *env,
1018                                           const struct btf_type *struct_type,
1019                                           const struct btf_member *member,
1020                                           const struct btf_type *member_type)
1021 {
1022         if (BTF_MEMBER_BITFIELD_SIZE(member->offset)) {
1023                 btf_verifier_log_member(env, struct_type, member,
1024                                         "Invalid member bitfield_size");
1025                 return -EINVAL;
1026         }
1027
1028         /* bitfield size is 0, so member->offset represents bit offset only.
1029          * It is safe to call non kflag check_member variants.
1030          */
1031         return btf_type_ops(member_type)->check_member(env, struct_type,
1032                                                        member,
1033                                                        member_type);
1034 }
1035
1036 static int btf_df_resolve(struct btf_verifier_env *env,
1037                           const struct resolve_vertex *v)
1038 {
1039         btf_verifier_log_basic(env, v->t, "Unsupported resolve");
1040         return -EINVAL;
1041 }
1042
1043 static void btf_df_seq_show(const struct btf *btf, const struct btf_type *t,
1044                             u32 type_id, void *data, u8 bits_offsets,
1045                             struct seq_file *m)
1046 {
1047         seq_printf(m, "<unsupported kind:%u>", BTF_INFO_KIND(t->info));
1048 }
1049
1050 static int btf_int_check_member(struct btf_verifier_env *env,
1051                                 const struct btf_type *struct_type,
1052                                 const struct btf_member *member,
1053                                 const struct btf_type *member_type)
1054 {
1055         u32 int_data = btf_type_int(member_type);
1056         u32 struct_bits_off = member->offset;
1057         u32 struct_size = struct_type->size;
1058         u32 nr_copy_bits;
1059         u32 bytes_offset;
1060
1061         if (U32_MAX - struct_bits_off < BTF_INT_OFFSET(int_data)) {
1062                 btf_verifier_log_member(env, struct_type, member,
1063                                         "bits_offset exceeds U32_MAX");
1064                 return -EINVAL;
1065         }
1066
1067         struct_bits_off += BTF_INT_OFFSET(int_data);
1068         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1069         nr_copy_bits = BTF_INT_BITS(int_data) +
1070                 BITS_PER_BYTE_MASKED(struct_bits_off);
1071
1072         if (nr_copy_bits > BITS_PER_U128) {
1073                 btf_verifier_log_member(env, struct_type, member,
1074                                         "nr_copy_bits exceeds 128");
1075                 return -EINVAL;
1076         }
1077
1078         if (struct_size < bytes_offset ||
1079             struct_size - bytes_offset < BITS_ROUNDUP_BYTES(nr_copy_bits)) {
1080                 btf_verifier_log_member(env, struct_type, member,
1081                                         "Member exceeds struct_size");
1082                 return -EINVAL;
1083         }
1084
1085         return 0;
1086 }
1087
1088 static int btf_int_check_kflag_member(struct btf_verifier_env *env,
1089                                       const struct btf_type *struct_type,
1090                                       const struct btf_member *member,
1091                                       const struct btf_type *member_type)
1092 {
1093         u32 struct_bits_off, nr_bits, nr_int_data_bits, bytes_offset;
1094         u32 int_data = btf_type_int(member_type);
1095         u32 struct_size = struct_type->size;
1096         u32 nr_copy_bits;
1097
1098         /* a regular int type is required for the kflag int member */
1099         if (!btf_type_int_is_regular(member_type)) {
1100                 btf_verifier_log_member(env, struct_type, member,
1101                                         "Invalid member base type");
1102                 return -EINVAL;
1103         }
1104
1105         /* check sanity of bitfield size */
1106         nr_bits = BTF_MEMBER_BITFIELD_SIZE(member->offset);
1107         struct_bits_off = BTF_MEMBER_BIT_OFFSET(member->offset);
1108         nr_int_data_bits = BTF_INT_BITS(int_data);
1109         if (!nr_bits) {
1110                 /* Not a bitfield member, member offset must be at byte
1111                  * boundary.
1112                  */
1113                 if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1114                         btf_verifier_log_member(env, struct_type, member,
1115                                                 "Invalid member offset");
1116                         return -EINVAL;
1117                 }
1118
1119                 nr_bits = nr_int_data_bits;
1120         } else if (nr_bits > nr_int_data_bits) {
1121                 btf_verifier_log_member(env, struct_type, member,
1122                                         "Invalid member bitfield_size");
1123                 return -EINVAL;
1124         }
1125
1126         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1127         nr_copy_bits = nr_bits + BITS_PER_BYTE_MASKED(struct_bits_off);
1128         if (nr_copy_bits > BITS_PER_U128) {
1129                 btf_verifier_log_member(env, struct_type, member,
1130                                         "nr_copy_bits exceeds 128");
1131                 return -EINVAL;
1132         }
1133
1134         if (struct_size < bytes_offset ||
1135             struct_size - bytes_offset < BITS_ROUNDUP_BYTES(nr_copy_bits)) {
1136                 btf_verifier_log_member(env, struct_type, member,
1137                                         "Member exceeds struct_size");
1138                 return -EINVAL;
1139         }
1140
1141         return 0;
1142 }
1143
1144 static s32 btf_int_check_meta(struct btf_verifier_env *env,
1145                               const struct btf_type *t,
1146                               u32 meta_left)
1147 {
1148         u32 int_data, nr_bits, meta_needed = sizeof(int_data);
1149         u16 encoding;
1150
1151         if (meta_left < meta_needed) {
1152                 btf_verifier_log_basic(env, t,
1153                                        "meta_left:%u meta_needed:%u",
1154                                        meta_left, meta_needed);
1155                 return -EINVAL;
1156         }
1157
1158         if (btf_type_vlen(t)) {
1159                 btf_verifier_log_type(env, t, "vlen != 0");
1160                 return -EINVAL;
1161         }
1162
1163         if (btf_type_kflag(t)) {
1164                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
1165                 return -EINVAL;
1166         }
1167
1168         int_data = btf_type_int(t);
1169         if (int_data & ~BTF_INT_MASK) {
1170                 btf_verifier_log_basic(env, t, "Invalid int_data:%x",
1171                                        int_data);
1172                 return -EINVAL;
1173         }
1174
1175         nr_bits = BTF_INT_BITS(int_data) + BTF_INT_OFFSET(int_data);
1176
1177         if (nr_bits > BITS_PER_U128) {
1178                 btf_verifier_log_type(env, t, "nr_bits exceeds %zu",
1179                                       BITS_PER_U128);
1180                 return -EINVAL;
1181         }
1182
1183         if (BITS_ROUNDUP_BYTES(nr_bits) > t->size) {
1184                 btf_verifier_log_type(env, t, "nr_bits exceeds type_size");
1185                 return -EINVAL;
1186         }
1187
1188         /*
1189          * Only one of the encoding bits is allowed and it
1190          * should be sufficient for the pretty print purpose (i.e. decoding).
1191          * Multiple bits can be allowed later if it is found
1192          * to be insufficient.
1193          */
1194         encoding = BTF_INT_ENCODING(int_data);
1195         if (encoding &&
1196             encoding != BTF_INT_SIGNED &&
1197             encoding != BTF_INT_CHAR &&
1198             encoding != BTF_INT_BOOL) {
1199                 btf_verifier_log_type(env, t, "Unsupported encoding");
1200                 return -ENOTSUPP;
1201         }
1202
1203         btf_verifier_log_type(env, t, NULL);
1204
1205         return meta_needed;
1206 }
1207
1208 static void btf_int_log(struct btf_verifier_env *env,
1209                         const struct btf_type *t)
1210 {
1211         int int_data = btf_type_int(t);
1212
1213         btf_verifier_log(env,
1214                          "size=%u bits_offset=%u nr_bits=%u encoding=%s",
1215                          t->size, BTF_INT_OFFSET(int_data),
1216                          BTF_INT_BITS(int_data),
1217                          btf_int_encoding_str(BTF_INT_ENCODING(int_data)));
1218 }
1219
1220 static void btf_int128_print(struct seq_file *m, void *data)
1221 {
1222         /* data points to a __int128 number.
1223          * Suppose
1224          *     int128_num = *(__int128 *)data;
1225          * The below formulas shows what upper_num and lower_num represents:
1226          *     upper_num = int128_num >> 64;
1227          *     lower_num = int128_num & 0xffffffffFFFFFFFFULL;
1228          */
1229         u64 upper_num, lower_num;
1230
1231 #ifdef __BIG_ENDIAN_BITFIELD
1232         upper_num = *(u64 *)data;
1233         lower_num = *(u64 *)(data + 8);
1234 #else
1235         upper_num = *(u64 *)(data + 8);
1236         lower_num = *(u64 *)data;
1237 #endif
1238         if (upper_num == 0)
1239                 seq_printf(m, "0x%llx", lower_num);
1240         else
1241                 seq_printf(m, "0x%llx%016llx", upper_num, lower_num);
1242 }
1243
1244 static void btf_int128_shift(u64 *print_num, u16 left_shift_bits,
1245                              u16 right_shift_bits)
1246 {
1247         u64 upper_num, lower_num;
1248
1249 #ifdef __BIG_ENDIAN_BITFIELD
1250         upper_num = print_num[0];
1251         lower_num = print_num[1];
1252 #else
1253         upper_num = print_num[1];
1254         lower_num = print_num[0];
1255 #endif
1256
1257         /* shake out un-needed bits by shift/or operations */
1258         if (left_shift_bits >= 64) {
1259                 upper_num = lower_num << (left_shift_bits - 64);
1260                 lower_num = 0;
1261         } else {
1262                 upper_num = (upper_num << left_shift_bits) |
1263                             (lower_num >> (64 - left_shift_bits));
1264                 lower_num = lower_num << left_shift_bits;
1265         }
1266
1267         if (right_shift_bits >= 64) {
1268                 lower_num = upper_num >> (right_shift_bits - 64);
1269                 upper_num = 0;
1270         } else {
1271                 lower_num = (lower_num >> right_shift_bits) |
1272                             (upper_num << (64 - right_shift_bits));
1273                 upper_num = upper_num >> right_shift_bits;
1274         }
1275
1276 #ifdef __BIG_ENDIAN_BITFIELD
1277         print_num[0] = upper_num;
1278         print_num[1] = lower_num;
1279 #else
1280         print_num[0] = lower_num;
1281         print_num[1] = upper_num;
1282 #endif
1283 }
1284
1285 static void btf_bitfield_seq_show(void *data, u8 bits_offset,
1286                                   u8 nr_bits, struct seq_file *m)
1287 {
1288         u16 left_shift_bits, right_shift_bits;
1289         u8 nr_copy_bytes;
1290         u8 nr_copy_bits;
1291         u64 print_num[2] = {};
1292
1293         nr_copy_bits = nr_bits + bits_offset;
1294         nr_copy_bytes = BITS_ROUNDUP_BYTES(nr_copy_bits);
1295
1296         memcpy(print_num, data, nr_copy_bytes);
1297
1298 #ifdef __BIG_ENDIAN_BITFIELD
1299         left_shift_bits = bits_offset;
1300 #else
1301         left_shift_bits = BITS_PER_U128 - nr_copy_bits;
1302 #endif
1303         right_shift_bits = BITS_PER_U128 - nr_bits;
1304
1305         btf_int128_shift(print_num, left_shift_bits, right_shift_bits);
1306         btf_int128_print(m, print_num);
1307 }
1308
1309
1310 static void btf_int_bits_seq_show(const struct btf *btf,
1311                                   const struct btf_type *t,
1312                                   void *data, u8 bits_offset,
1313                                   struct seq_file *m)
1314 {
1315         u32 int_data = btf_type_int(t);
1316         u8 nr_bits = BTF_INT_BITS(int_data);
1317         u8 total_bits_offset;
1318
1319         /*
1320          * bits_offset is at most 7.
1321          * BTF_INT_OFFSET() cannot exceed 128 bits.
1322          */
1323         total_bits_offset = bits_offset + BTF_INT_OFFSET(int_data);
1324         data += BITS_ROUNDDOWN_BYTES(total_bits_offset);
1325         bits_offset = BITS_PER_BYTE_MASKED(total_bits_offset);
1326         btf_bitfield_seq_show(data, bits_offset, nr_bits, m);
1327 }
1328
1329 static void btf_int_seq_show(const struct btf *btf, const struct btf_type *t,
1330                              u32 type_id, void *data, u8 bits_offset,
1331                              struct seq_file *m)
1332 {
1333         u32 int_data = btf_type_int(t);
1334         u8 encoding = BTF_INT_ENCODING(int_data);
1335         bool sign = encoding & BTF_INT_SIGNED;
1336         u8 nr_bits = BTF_INT_BITS(int_data);
1337
1338         if (bits_offset || BTF_INT_OFFSET(int_data) ||
1339             BITS_PER_BYTE_MASKED(nr_bits)) {
1340                 btf_int_bits_seq_show(btf, t, data, bits_offset, m);
1341                 return;
1342         }
1343
1344         switch (nr_bits) {
1345         case 128:
1346                 btf_int128_print(m, data);
1347                 break;
1348         case 64:
1349                 if (sign)
1350                         seq_printf(m, "%lld", *(s64 *)data);
1351                 else
1352                         seq_printf(m, "%llu", *(u64 *)data);
1353                 break;
1354         case 32:
1355                 if (sign)
1356                         seq_printf(m, "%d", *(s32 *)data);
1357                 else
1358                         seq_printf(m, "%u", *(u32 *)data);
1359                 break;
1360         case 16:
1361                 if (sign)
1362                         seq_printf(m, "%d", *(s16 *)data);
1363                 else
1364                         seq_printf(m, "%u", *(u16 *)data);
1365                 break;
1366         case 8:
1367                 if (sign)
1368                         seq_printf(m, "%d", *(s8 *)data);
1369                 else
1370                         seq_printf(m, "%u", *(u8 *)data);
1371                 break;
1372         default:
1373                 btf_int_bits_seq_show(btf, t, data, bits_offset, m);
1374         }
1375 }
1376
1377 static const struct btf_kind_operations int_ops = {
1378         .check_meta = btf_int_check_meta,
1379         .resolve = btf_df_resolve,
1380         .check_member = btf_int_check_member,
1381         .check_kflag_member = btf_int_check_kflag_member,
1382         .log_details = btf_int_log,
1383         .seq_show = btf_int_seq_show,
1384 };
1385
1386 static int btf_modifier_check_member(struct btf_verifier_env *env,
1387                                      const struct btf_type *struct_type,
1388                                      const struct btf_member *member,
1389                                      const struct btf_type *member_type)
1390 {
1391         const struct btf_type *resolved_type;
1392         u32 resolved_type_id = member->type;
1393         struct btf_member resolved_member;
1394         struct btf *btf = env->btf;
1395
1396         resolved_type = btf_type_id_size(btf, &resolved_type_id, NULL);
1397         if (!resolved_type) {
1398                 btf_verifier_log_member(env, struct_type, member,
1399                                         "Invalid member");
1400                 return -EINVAL;
1401         }
1402
1403         resolved_member = *member;
1404         resolved_member.type = resolved_type_id;
1405
1406         return btf_type_ops(resolved_type)->check_member(env, struct_type,
1407                                                          &resolved_member,
1408                                                          resolved_type);
1409 }
1410
1411 static int btf_modifier_check_kflag_member(struct btf_verifier_env *env,
1412                                            const struct btf_type *struct_type,
1413                                            const struct btf_member *member,
1414                                            const struct btf_type *member_type)
1415 {
1416         const struct btf_type *resolved_type;
1417         u32 resolved_type_id = member->type;
1418         struct btf_member resolved_member;
1419         struct btf *btf = env->btf;
1420
1421         resolved_type = btf_type_id_size(btf, &resolved_type_id, NULL);
1422         if (!resolved_type) {
1423                 btf_verifier_log_member(env, struct_type, member,
1424                                         "Invalid member");
1425                 return -EINVAL;
1426         }
1427
1428         resolved_member = *member;
1429         resolved_member.type = resolved_type_id;
1430
1431         return btf_type_ops(resolved_type)->check_kflag_member(env, struct_type,
1432                                                                &resolved_member,
1433                                                                resolved_type);
1434 }
1435
1436 static int btf_ptr_check_member(struct btf_verifier_env *env,
1437                                 const struct btf_type *struct_type,
1438                                 const struct btf_member *member,
1439                                 const struct btf_type *member_type)
1440 {
1441         u32 struct_size, struct_bits_off, bytes_offset;
1442
1443         struct_size = struct_type->size;
1444         struct_bits_off = member->offset;
1445         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1446
1447         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1448                 btf_verifier_log_member(env, struct_type, member,
1449                                         "Member is not byte aligned");
1450                 return -EINVAL;
1451         }
1452
1453         if (struct_size - bytes_offset < sizeof(void *)) {
1454                 btf_verifier_log_member(env, struct_type, member,
1455                                         "Member exceeds struct_size");
1456                 return -EINVAL;
1457         }
1458
1459         return 0;
1460 }
1461
1462 static int btf_ref_type_check_meta(struct btf_verifier_env *env,
1463                                    const struct btf_type *t,
1464                                    u32 meta_left)
1465 {
1466         if (btf_type_vlen(t)) {
1467                 btf_verifier_log_type(env, t, "vlen != 0");
1468                 return -EINVAL;
1469         }
1470
1471         if (btf_type_kflag(t)) {
1472                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
1473                 return -EINVAL;
1474         }
1475
1476         if (!BTF_TYPE_ID_VALID(t->type)) {
1477                 btf_verifier_log_type(env, t, "Invalid type_id");
1478                 return -EINVAL;
1479         }
1480
1481         /* typedef type must have a valid name, and other ref types,
1482          * volatile, const, restrict, should have a null name.
1483          */
1484         if (BTF_INFO_KIND(t->info) == BTF_KIND_TYPEDEF) {
1485                 if (!t->name_off ||
1486                     !btf_name_valid_identifier(env->btf, t->name_off)) {
1487                         btf_verifier_log_type(env, t, "Invalid name");
1488                         return -EINVAL;
1489                 }
1490         } else {
1491                 if (t->name_off) {
1492                         btf_verifier_log_type(env, t, "Invalid name");
1493                         return -EINVAL;
1494                 }
1495         }
1496
1497         btf_verifier_log_type(env, t, NULL);
1498
1499         return 0;
1500 }
1501
1502 static int btf_modifier_resolve(struct btf_verifier_env *env,
1503                                 const struct resolve_vertex *v)
1504 {
1505         const struct btf_type *t = v->t;
1506         const struct btf_type *next_type;
1507         u32 next_type_id = t->type;
1508         struct btf *btf = env->btf;
1509         u32 next_type_size = 0;
1510
1511         next_type = btf_type_by_id(btf, next_type_id);
1512         if (!next_type) {
1513                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1514                 return -EINVAL;
1515         }
1516
1517         if (!env_type_is_resolve_sink(env, next_type) &&
1518             !env_type_is_resolved(env, next_type_id))
1519                 return env_stack_push(env, next_type, next_type_id);
1520
1521         /* Figure out the resolved next_type_id with size.
1522          * They will be stored in the current modifier's
1523          * resolved_ids and resolved_sizes such that it can
1524          * save us a few type-following when we use it later (e.g. in
1525          * pretty print).
1526          */
1527         if (!btf_type_id_size(btf, &next_type_id, &next_type_size)) {
1528                 if (env_type_is_resolved(env, next_type_id))
1529                         next_type = btf_type_id_resolve(btf, &next_type_id);
1530
1531                 /* "typedef void new_void", "const void"...etc */
1532                 if (!btf_type_is_void(next_type) &&
1533                     !btf_type_is_fwd(next_type)) {
1534                         btf_verifier_log_type(env, v->t, "Invalid type_id");
1535                         return -EINVAL;
1536                 }
1537         }
1538
1539         env_stack_pop_resolved(env, next_type_id, next_type_size);
1540
1541         return 0;
1542 }
1543
1544 static int btf_ptr_resolve(struct btf_verifier_env *env,
1545                            const struct resolve_vertex *v)
1546 {
1547         const struct btf_type *next_type;
1548         const struct btf_type *t = v->t;
1549         u32 next_type_id = t->type;
1550         struct btf *btf = env->btf;
1551
1552         next_type = btf_type_by_id(btf, next_type_id);
1553         if (!next_type) {
1554                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1555                 return -EINVAL;
1556         }
1557
1558         if (!env_type_is_resolve_sink(env, next_type) &&
1559             !env_type_is_resolved(env, next_type_id))
1560                 return env_stack_push(env, next_type, next_type_id);
1561
1562         /* If the modifier was RESOLVED during RESOLVE_STRUCT_OR_ARRAY,
1563          * the modifier may have stopped resolving when it was resolved
1564          * to a ptr (last-resolved-ptr).
1565          *
1566          * We now need to continue from the last-resolved-ptr to
1567          * ensure the last-resolved-ptr will not referring back to
1568          * the currenct ptr (t).
1569          */
1570         if (btf_type_is_modifier(next_type)) {
1571                 const struct btf_type *resolved_type;
1572                 u32 resolved_type_id;
1573
1574                 resolved_type_id = next_type_id;
1575                 resolved_type = btf_type_id_resolve(btf, &resolved_type_id);
1576
1577                 if (btf_type_is_ptr(resolved_type) &&
1578                     !env_type_is_resolve_sink(env, resolved_type) &&
1579                     !env_type_is_resolved(env, resolved_type_id))
1580                         return env_stack_push(env, resolved_type,
1581                                               resolved_type_id);
1582         }
1583
1584         if (!btf_type_id_size(btf, &next_type_id, NULL)) {
1585                 if (env_type_is_resolved(env, next_type_id))
1586                         next_type = btf_type_id_resolve(btf, &next_type_id);
1587
1588                 if (!btf_type_is_void(next_type) &&
1589                     !btf_type_is_fwd(next_type) &&
1590                     !btf_type_is_func_proto(next_type)) {
1591                         btf_verifier_log_type(env, v->t, "Invalid type_id");
1592                         return -EINVAL;
1593                 }
1594         }
1595
1596         env_stack_pop_resolved(env, next_type_id, 0);
1597
1598         return 0;
1599 }
1600
1601 static void btf_modifier_seq_show(const struct btf *btf,
1602                                   const struct btf_type *t,
1603                                   u32 type_id, void *data,
1604                                   u8 bits_offset, struct seq_file *m)
1605 {
1606         t = btf_type_id_resolve(btf, &type_id);
1607
1608         btf_type_ops(t)->seq_show(btf, t, type_id, data, bits_offset, m);
1609 }
1610
1611 static void btf_ptr_seq_show(const struct btf *btf, const struct btf_type *t,
1612                              u32 type_id, void *data, u8 bits_offset,
1613                              struct seq_file *m)
1614 {
1615         /* It is a hashed value */
1616         seq_printf(m, "%p", *(void **)data);
1617 }
1618
1619 static void btf_ref_type_log(struct btf_verifier_env *env,
1620                              const struct btf_type *t)
1621 {
1622         btf_verifier_log(env, "type_id=%u", t->type);
1623 }
1624
1625 static struct btf_kind_operations modifier_ops = {
1626         .check_meta = btf_ref_type_check_meta,
1627         .resolve = btf_modifier_resolve,
1628         .check_member = btf_modifier_check_member,
1629         .check_kflag_member = btf_modifier_check_kflag_member,
1630         .log_details = btf_ref_type_log,
1631         .seq_show = btf_modifier_seq_show,
1632 };
1633
1634 static struct btf_kind_operations ptr_ops = {
1635         .check_meta = btf_ref_type_check_meta,
1636         .resolve = btf_ptr_resolve,
1637         .check_member = btf_ptr_check_member,
1638         .check_kflag_member = btf_generic_check_kflag_member,
1639         .log_details = btf_ref_type_log,
1640         .seq_show = btf_ptr_seq_show,
1641 };
1642
1643 static s32 btf_fwd_check_meta(struct btf_verifier_env *env,
1644                               const struct btf_type *t,
1645                               u32 meta_left)
1646 {
1647         if (btf_type_vlen(t)) {
1648                 btf_verifier_log_type(env, t, "vlen != 0");
1649                 return -EINVAL;
1650         }
1651
1652         if (t->type) {
1653                 btf_verifier_log_type(env, t, "type != 0");
1654                 return -EINVAL;
1655         }
1656
1657         /* fwd type must have a valid name */
1658         if (!t->name_off ||
1659             !btf_name_valid_identifier(env->btf, t->name_off)) {
1660                 btf_verifier_log_type(env, t, "Invalid name");
1661                 return -EINVAL;
1662         }
1663
1664         btf_verifier_log_type(env, t, NULL);
1665
1666         return 0;
1667 }
1668
1669 static void btf_fwd_type_log(struct btf_verifier_env *env,
1670                              const struct btf_type *t)
1671 {
1672         btf_verifier_log(env, "%s", btf_type_kflag(t) ? "union" : "struct");
1673 }
1674
1675 static struct btf_kind_operations fwd_ops = {
1676         .check_meta = btf_fwd_check_meta,
1677         .resolve = btf_df_resolve,
1678         .check_member = btf_df_check_member,
1679         .check_kflag_member = btf_df_check_kflag_member,
1680         .log_details = btf_fwd_type_log,
1681         .seq_show = btf_df_seq_show,
1682 };
1683
1684 static int btf_array_check_member(struct btf_verifier_env *env,
1685                                   const struct btf_type *struct_type,
1686                                   const struct btf_member *member,
1687                                   const struct btf_type *member_type)
1688 {
1689         u32 struct_bits_off = member->offset;
1690         u32 struct_size, bytes_offset;
1691         u32 array_type_id, array_size;
1692         struct btf *btf = env->btf;
1693
1694         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1695                 btf_verifier_log_member(env, struct_type, member,
1696                                         "Member is not byte aligned");
1697                 return -EINVAL;
1698         }
1699
1700         array_type_id = member->type;
1701         btf_type_id_size(btf, &array_type_id, &array_size);
1702         struct_size = struct_type->size;
1703         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1704         if (struct_size - bytes_offset < array_size) {
1705                 btf_verifier_log_member(env, struct_type, member,
1706                                         "Member exceeds struct_size");
1707                 return -EINVAL;
1708         }
1709
1710         return 0;
1711 }
1712
1713 static s32 btf_array_check_meta(struct btf_verifier_env *env,
1714                                 const struct btf_type *t,
1715                                 u32 meta_left)
1716 {
1717         const struct btf_array *array = btf_type_array(t);
1718         u32 meta_needed = sizeof(*array);
1719
1720         if (meta_left < meta_needed) {
1721                 btf_verifier_log_basic(env, t,
1722                                        "meta_left:%u meta_needed:%u",
1723                                        meta_left, meta_needed);
1724                 return -EINVAL;
1725         }
1726
1727         /* array type should not have a name */
1728         if (t->name_off) {
1729                 btf_verifier_log_type(env, t, "Invalid name");
1730                 return -EINVAL;
1731         }
1732
1733         if (btf_type_vlen(t)) {
1734                 btf_verifier_log_type(env, t, "vlen != 0");
1735                 return -EINVAL;
1736         }
1737
1738         if (btf_type_kflag(t)) {
1739                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
1740                 return -EINVAL;
1741         }
1742
1743         if (t->size) {
1744                 btf_verifier_log_type(env, t, "size != 0");
1745                 return -EINVAL;
1746         }
1747
1748         /* Array elem type and index type cannot be in type void,
1749          * so !array->type and !array->index_type are not allowed.
1750          */
1751         if (!array->type || !BTF_TYPE_ID_VALID(array->type)) {
1752                 btf_verifier_log_type(env, t, "Invalid elem");
1753                 return -EINVAL;
1754         }
1755
1756         if (!array->index_type || !BTF_TYPE_ID_VALID(array->index_type)) {
1757                 btf_verifier_log_type(env, t, "Invalid index");
1758                 return -EINVAL;
1759         }
1760
1761         btf_verifier_log_type(env, t, NULL);
1762
1763         return meta_needed;
1764 }
1765
1766 static int btf_array_resolve(struct btf_verifier_env *env,
1767                              const struct resolve_vertex *v)
1768 {
1769         const struct btf_array *array = btf_type_array(v->t);
1770         const struct btf_type *elem_type, *index_type;
1771         u32 elem_type_id, index_type_id;
1772         struct btf *btf = env->btf;
1773         u32 elem_size;
1774
1775         /* Check array->index_type */
1776         index_type_id = array->index_type;
1777         index_type = btf_type_by_id(btf, index_type_id);
1778         if (btf_type_nosize_or_null(index_type)) {
1779                 btf_verifier_log_type(env, v->t, "Invalid index");
1780                 return -EINVAL;
1781         }
1782
1783         if (!env_type_is_resolve_sink(env, index_type) &&
1784             !env_type_is_resolved(env, index_type_id))
1785                 return env_stack_push(env, index_type, index_type_id);
1786
1787         index_type = btf_type_id_size(btf, &index_type_id, NULL);
1788         if (!index_type || !btf_type_is_int(index_type) ||
1789             !btf_type_int_is_regular(index_type)) {
1790                 btf_verifier_log_type(env, v->t, "Invalid index");
1791                 return -EINVAL;
1792         }
1793
1794         /* Check array->type */
1795         elem_type_id = array->type;
1796         elem_type = btf_type_by_id(btf, elem_type_id);
1797         if (btf_type_nosize_or_null(elem_type)) {
1798                 btf_verifier_log_type(env, v->t,
1799                                       "Invalid elem");
1800                 return -EINVAL;
1801         }
1802
1803         if (!env_type_is_resolve_sink(env, elem_type) &&
1804             !env_type_is_resolved(env, elem_type_id))
1805                 return env_stack_push(env, elem_type, elem_type_id);
1806
1807         elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
1808         if (!elem_type) {
1809                 btf_verifier_log_type(env, v->t, "Invalid elem");
1810                 return -EINVAL;
1811         }
1812
1813         if (btf_type_is_int(elem_type) && !btf_type_int_is_regular(elem_type)) {
1814                 btf_verifier_log_type(env, v->t, "Invalid array of int");
1815                 return -EINVAL;
1816         }
1817
1818         if (array->nelems && elem_size > U32_MAX / array->nelems) {
1819                 btf_verifier_log_type(env, v->t,
1820                                       "Array size overflows U32_MAX");
1821                 return -EINVAL;
1822         }
1823
1824         env_stack_pop_resolved(env, elem_type_id, elem_size * array->nelems);
1825
1826         return 0;
1827 }
1828
1829 static void btf_array_log(struct btf_verifier_env *env,
1830                           const struct btf_type *t)
1831 {
1832         const struct btf_array *array = btf_type_array(t);
1833
1834         btf_verifier_log(env, "type_id=%u index_type_id=%u nr_elems=%u",
1835                          array->type, array->index_type, array->nelems);
1836 }
1837
1838 static void btf_array_seq_show(const struct btf *btf, const struct btf_type *t,
1839                                u32 type_id, void *data, u8 bits_offset,
1840                                struct seq_file *m)
1841 {
1842         const struct btf_array *array = btf_type_array(t);
1843         const struct btf_kind_operations *elem_ops;
1844         const struct btf_type *elem_type;
1845         u32 i, elem_size, elem_type_id;
1846
1847         elem_type_id = array->type;
1848         elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
1849         elem_ops = btf_type_ops(elem_type);
1850         seq_puts(m, "[");
1851         for (i = 0; i < array->nelems; i++) {
1852                 if (i)
1853                         seq_puts(m, ",");
1854
1855                 elem_ops->seq_show(btf, elem_type, elem_type_id, data,
1856                                    bits_offset, m);
1857                 data += elem_size;
1858         }
1859         seq_puts(m, "]");
1860 }
1861
1862 static struct btf_kind_operations array_ops = {
1863         .check_meta = btf_array_check_meta,
1864         .resolve = btf_array_resolve,
1865         .check_member = btf_array_check_member,
1866         .check_kflag_member = btf_generic_check_kflag_member,
1867         .log_details = btf_array_log,
1868         .seq_show = btf_array_seq_show,
1869 };
1870
1871 static int btf_struct_check_member(struct btf_verifier_env *env,
1872                                    const struct btf_type *struct_type,
1873                                    const struct btf_member *member,
1874                                    const struct btf_type *member_type)
1875 {
1876         u32 struct_bits_off = member->offset;
1877         u32 struct_size, bytes_offset;
1878
1879         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1880                 btf_verifier_log_member(env, struct_type, member,
1881                                         "Member is not byte aligned");
1882                 return -EINVAL;
1883         }
1884
1885         struct_size = struct_type->size;
1886         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1887         if (struct_size - bytes_offset < member_type->size) {
1888                 btf_verifier_log_member(env, struct_type, member,
1889                                         "Member exceeds struct_size");
1890                 return -EINVAL;
1891         }
1892
1893         return 0;
1894 }
1895
1896 static s32 btf_struct_check_meta(struct btf_verifier_env *env,
1897                                  const struct btf_type *t,
1898                                  u32 meta_left)
1899 {
1900         bool is_union = BTF_INFO_KIND(t->info) == BTF_KIND_UNION;
1901         const struct btf_member *member;
1902         u32 meta_needed, last_offset;
1903         struct btf *btf = env->btf;
1904         u32 struct_size = t->size;
1905         u32 offset;
1906         u16 i;
1907
1908         meta_needed = btf_type_vlen(t) * sizeof(*member);
1909         if (meta_left < meta_needed) {
1910                 btf_verifier_log_basic(env, t,
1911                                        "meta_left:%u meta_needed:%u",
1912                                        meta_left, meta_needed);
1913                 return -EINVAL;
1914         }
1915
1916         /* struct type either no name or a valid one */
1917         if (t->name_off &&
1918             !btf_name_valid_identifier(env->btf, t->name_off)) {
1919                 btf_verifier_log_type(env, t, "Invalid name");
1920                 return -EINVAL;
1921         }
1922
1923         btf_verifier_log_type(env, t, NULL);
1924
1925         last_offset = 0;
1926         for_each_member(i, t, member) {
1927                 if (!btf_name_offset_valid(btf, member->name_off)) {
1928                         btf_verifier_log_member(env, t, member,
1929                                                 "Invalid member name_offset:%u",
1930                                                 member->name_off);
1931                         return -EINVAL;
1932                 }
1933
1934                 /* struct member either no name or a valid one */
1935                 if (member->name_off &&
1936                     !btf_name_valid_identifier(btf, member->name_off)) {
1937                         btf_verifier_log_member(env, t, member, "Invalid name");
1938                         return -EINVAL;
1939                 }
1940                 /* A member cannot be in type void */
1941                 if (!member->type || !BTF_TYPE_ID_VALID(member->type)) {
1942                         btf_verifier_log_member(env, t, member,
1943                                                 "Invalid type_id");
1944                         return -EINVAL;
1945                 }
1946
1947                 offset = btf_member_bit_offset(t, member);
1948                 if (is_union && offset) {
1949                         btf_verifier_log_member(env, t, member,
1950                                                 "Invalid member bits_offset");
1951                         return -EINVAL;
1952                 }
1953
1954                 /*
1955                  * ">" instead of ">=" because the last member could be
1956                  * "char a[0];"
1957                  */
1958                 if (last_offset > offset) {
1959                         btf_verifier_log_member(env, t, member,
1960                                                 "Invalid member bits_offset");
1961                         return -EINVAL;
1962                 }
1963
1964                 if (BITS_ROUNDUP_BYTES(offset) > struct_size) {
1965                         btf_verifier_log_member(env, t, member,
1966                                                 "Member bits_offset exceeds its struct size");
1967                         return -EINVAL;
1968                 }
1969
1970                 btf_verifier_log_member(env, t, member, NULL);
1971                 last_offset = offset;
1972         }
1973
1974         return meta_needed;
1975 }
1976
1977 static int btf_struct_resolve(struct btf_verifier_env *env,
1978                               const struct resolve_vertex *v)
1979 {
1980         const struct btf_member *member;
1981         int err;
1982         u16 i;
1983
1984         /* Before continue resolving the next_member,
1985          * ensure the last member is indeed resolved to a
1986          * type with size info.
1987          */
1988         if (v->next_member) {
1989                 const struct btf_type *last_member_type;
1990                 const struct btf_member *last_member;
1991                 u16 last_member_type_id;
1992
1993                 last_member = btf_type_member(v->t) + v->next_member - 1;
1994                 last_member_type_id = last_member->type;
1995                 if (WARN_ON_ONCE(!env_type_is_resolved(env,
1996                                                        last_member_type_id)))
1997                         return -EINVAL;
1998
1999                 last_member_type = btf_type_by_id(env->btf,
2000                                                   last_member_type_id);
2001                 if (btf_type_kflag(v->t))
2002                         err = btf_type_ops(last_member_type)->check_kflag_member(env, v->t,
2003                                                                 last_member,
2004                                                                 last_member_type);
2005                 else
2006                         err = btf_type_ops(last_member_type)->check_member(env, v->t,
2007                                                                 last_member,
2008                                                                 last_member_type);
2009                 if (err)
2010                         return err;
2011         }
2012
2013         for_each_member_from(i, v->next_member, v->t, member) {
2014                 u32 member_type_id = member->type;
2015                 const struct btf_type *member_type = btf_type_by_id(env->btf,
2016                                                                 member_type_id);
2017
2018                 if (btf_type_nosize_or_null(member_type)) {
2019                         btf_verifier_log_member(env, v->t, member,
2020                                                 "Invalid member");
2021                         return -EINVAL;
2022                 }
2023
2024                 if (!env_type_is_resolve_sink(env, member_type) &&
2025                     !env_type_is_resolved(env, member_type_id)) {
2026                         env_stack_set_next_member(env, i + 1);
2027                         return env_stack_push(env, member_type, member_type_id);
2028                 }
2029
2030                 if (btf_type_kflag(v->t))
2031                         err = btf_type_ops(member_type)->check_kflag_member(env, v->t,
2032                                                                             member,
2033                                                                             member_type);
2034                 else
2035                         err = btf_type_ops(member_type)->check_member(env, v->t,
2036                                                                       member,
2037                                                                       member_type);
2038                 if (err)
2039                         return err;
2040         }
2041
2042         env_stack_pop_resolved(env, 0, 0);
2043
2044         return 0;
2045 }
2046
2047 static void btf_struct_log(struct btf_verifier_env *env,
2048                            const struct btf_type *t)
2049 {
2050         btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
2051 }
2052
2053 /* find 'struct bpf_spin_lock' in map value.
2054  * return >= 0 offset if found
2055  * and < 0 in case of error
2056  */
2057 int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t)
2058 {
2059         const struct btf_member *member;
2060         u32 i, off = -ENOENT;
2061
2062         if (!__btf_type_is_struct(t))
2063                 return -EINVAL;
2064
2065         for_each_member(i, t, member) {
2066                 const struct btf_type *member_type = btf_type_by_id(btf,
2067                                                                     member->type);
2068                 if (!__btf_type_is_struct(member_type))
2069                         continue;
2070                 if (member_type->size != sizeof(struct bpf_spin_lock))
2071                         continue;
2072                 if (strcmp(__btf_name_by_offset(btf, member_type->name_off),
2073                            "bpf_spin_lock"))
2074                         continue;
2075                 if (off != -ENOENT)
2076                         /* only one 'struct bpf_spin_lock' is allowed */
2077                         return -E2BIG;
2078                 off = btf_member_bit_offset(t, member);
2079                 if (off % 8)
2080                         /* valid C code cannot generate such BTF */
2081                         return -EINVAL;
2082                 off /= 8;
2083                 if (off % __alignof__(struct bpf_spin_lock))
2084                         /* valid struct bpf_spin_lock will be 4 byte aligned */
2085                         return -EINVAL;
2086         }
2087         return off;
2088 }
2089
2090 static void btf_struct_seq_show(const struct btf *btf, const struct btf_type *t,
2091                                 u32 type_id, void *data, u8 bits_offset,
2092                                 struct seq_file *m)
2093 {
2094         const char *seq = BTF_INFO_KIND(t->info) == BTF_KIND_UNION ? "|" : ",";
2095         const struct btf_member *member;
2096         u32 i;
2097
2098         seq_puts(m, "{");
2099         for_each_member(i, t, member) {
2100                 const struct btf_type *member_type = btf_type_by_id(btf,
2101                                                                 member->type);
2102                 const struct btf_kind_operations *ops;
2103                 u32 member_offset, bitfield_size;
2104                 u32 bytes_offset;
2105                 u8 bits8_offset;
2106
2107                 if (i)
2108                         seq_puts(m, seq);
2109
2110                 member_offset = btf_member_bit_offset(t, member);
2111                 bitfield_size = btf_member_bitfield_size(t, member);
2112                 bytes_offset = BITS_ROUNDDOWN_BYTES(member_offset);
2113                 bits8_offset = BITS_PER_BYTE_MASKED(member_offset);
2114                 if (bitfield_size) {
2115                         btf_bitfield_seq_show(data + bytes_offset, bits8_offset,
2116                                               bitfield_size, m);
2117                 } else {
2118                         ops = btf_type_ops(member_type);
2119                         ops->seq_show(btf, member_type, member->type,
2120                                       data + bytes_offset, bits8_offset, m);
2121                 }
2122         }
2123         seq_puts(m, "}");
2124 }
2125
2126 static struct btf_kind_operations struct_ops = {
2127         .check_meta = btf_struct_check_meta,
2128         .resolve = btf_struct_resolve,
2129         .check_member = btf_struct_check_member,
2130         .check_kflag_member = btf_generic_check_kflag_member,
2131         .log_details = btf_struct_log,
2132         .seq_show = btf_struct_seq_show,
2133 };
2134
2135 static int btf_enum_check_member(struct btf_verifier_env *env,
2136                                  const struct btf_type *struct_type,
2137                                  const struct btf_member *member,
2138                                  const struct btf_type *member_type)
2139 {
2140         u32 struct_bits_off = member->offset;
2141         u32 struct_size, bytes_offset;
2142
2143         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
2144                 btf_verifier_log_member(env, struct_type, member,
2145                                         "Member is not byte aligned");
2146                 return -EINVAL;
2147         }
2148
2149         struct_size = struct_type->size;
2150         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
2151         if (struct_size - bytes_offset < sizeof(int)) {
2152                 btf_verifier_log_member(env, struct_type, member,
2153                                         "Member exceeds struct_size");
2154                 return -EINVAL;
2155         }
2156
2157         return 0;
2158 }
2159
2160 static int btf_enum_check_kflag_member(struct btf_verifier_env *env,
2161                                        const struct btf_type *struct_type,
2162                                        const struct btf_member *member,
2163                                        const struct btf_type *member_type)
2164 {
2165         u32 struct_bits_off, nr_bits, bytes_end, struct_size;
2166         u32 int_bitsize = sizeof(int) * BITS_PER_BYTE;
2167
2168         struct_bits_off = BTF_MEMBER_BIT_OFFSET(member->offset);
2169         nr_bits = BTF_MEMBER_BITFIELD_SIZE(member->offset);
2170         if (!nr_bits) {
2171                 if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
2172                         btf_verifier_log_member(env, struct_type, member,
2173                                                 "Member is not byte aligned");
2174                                 return -EINVAL;
2175                 }
2176
2177                 nr_bits = int_bitsize;
2178         } else if (nr_bits > int_bitsize) {
2179                 btf_verifier_log_member(env, struct_type, member,
2180                                         "Invalid member bitfield_size");
2181                 return -EINVAL;
2182         }
2183
2184         struct_size = struct_type->size;
2185         bytes_end = BITS_ROUNDUP_BYTES(struct_bits_off + nr_bits);
2186         if (struct_size < bytes_end) {
2187                 btf_verifier_log_member(env, struct_type, member,
2188                                         "Member exceeds struct_size");
2189                 return -EINVAL;
2190         }
2191
2192         return 0;
2193 }
2194
2195 static s32 btf_enum_check_meta(struct btf_verifier_env *env,
2196                                const struct btf_type *t,
2197                                u32 meta_left)
2198 {
2199         const struct btf_enum *enums = btf_type_enum(t);
2200         struct btf *btf = env->btf;
2201         u16 i, nr_enums;
2202         u32 meta_needed;
2203
2204         nr_enums = btf_type_vlen(t);
2205         meta_needed = nr_enums * sizeof(*enums);
2206
2207         if (meta_left < meta_needed) {
2208                 btf_verifier_log_basic(env, t,
2209                                        "meta_left:%u meta_needed:%u",
2210                                        meta_left, meta_needed);
2211                 return -EINVAL;
2212         }
2213
2214         if (btf_type_kflag(t)) {
2215                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
2216                 return -EINVAL;
2217         }
2218
2219         if (t->size != sizeof(int)) {
2220                 btf_verifier_log_type(env, t, "Expected size:%zu",
2221                                       sizeof(int));
2222                 return -EINVAL;
2223         }
2224
2225         /* enum type either no name or a valid one */
2226         if (t->name_off &&
2227             !btf_name_valid_identifier(env->btf, t->name_off)) {
2228                 btf_verifier_log_type(env, t, "Invalid name");
2229                 return -EINVAL;
2230         }
2231
2232         btf_verifier_log_type(env, t, NULL);
2233
2234         for (i = 0; i < nr_enums; i++) {
2235                 if (!btf_name_offset_valid(btf, enums[i].name_off)) {
2236                         btf_verifier_log(env, "\tInvalid name_offset:%u",
2237                                          enums[i].name_off);
2238                         return -EINVAL;
2239                 }
2240
2241                 /* enum member must have a valid name */
2242                 if (!enums[i].name_off ||
2243                     !btf_name_valid_identifier(btf, enums[i].name_off)) {
2244                         btf_verifier_log_type(env, t, "Invalid name");
2245                         return -EINVAL;
2246                 }
2247
2248
2249                 btf_verifier_log(env, "\t%s val=%d\n",
2250                                  __btf_name_by_offset(btf, enums[i].name_off),
2251                                  enums[i].val);
2252         }
2253
2254         return meta_needed;
2255 }
2256
2257 static void btf_enum_log(struct btf_verifier_env *env,
2258                          const struct btf_type *t)
2259 {
2260         btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
2261 }
2262
2263 static void btf_enum_seq_show(const struct btf *btf, const struct btf_type *t,
2264                               u32 type_id, void *data, u8 bits_offset,
2265                               struct seq_file *m)
2266 {
2267         const struct btf_enum *enums = btf_type_enum(t);
2268         u32 i, nr_enums = btf_type_vlen(t);
2269         int v = *(int *)data;
2270
2271         for (i = 0; i < nr_enums; i++) {
2272                 if (v == enums[i].val) {
2273                         seq_printf(m, "%s",
2274                                    __btf_name_by_offset(btf,
2275                                                         enums[i].name_off));
2276                         return;
2277                 }
2278         }
2279
2280         seq_printf(m, "%d", v);
2281 }
2282
2283 static struct btf_kind_operations enum_ops = {
2284         .check_meta = btf_enum_check_meta,
2285         .resolve = btf_df_resolve,
2286         .check_member = btf_enum_check_member,
2287         .check_kflag_member = btf_enum_check_kflag_member,
2288         .log_details = btf_enum_log,
2289         .seq_show = btf_enum_seq_show,
2290 };
2291
2292 static s32 btf_func_proto_check_meta(struct btf_verifier_env *env,
2293                                      const struct btf_type *t,
2294                                      u32 meta_left)
2295 {
2296         u32 meta_needed = btf_type_vlen(t) * sizeof(struct btf_param);
2297
2298         if (meta_left < meta_needed) {
2299                 btf_verifier_log_basic(env, t,
2300                                        "meta_left:%u meta_needed:%u",
2301                                        meta_left, meta_needed);
2302                 return -EINVAL;
2303         }
2304
2305         if (t->name_off) {
2306                 btf_verifier_log_type(env, t, "Invalid name");
2307                 return -EINVAL;
2308         }
2309
2310         if (btf_type_kflag(t)) {
2311                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
2312                 return -EINVAL;
2313         }
2314
2315         btf_verifier_log_type(env, t, NULL);
2316
2317         return meta_needed;
2318 }
2319
2320 static void btf_func_proto_log(struct btf_verifier_env *env,
2321                                const struct btf_type *t)
2322 {
2323         const struct btf_param *args = (const struct btf_param *)(t + 1);
2324         u16 nr_args = btf_type_vlen(t), i;
2325
2326         btf_verifier_log(env, "return=%u args=(", t->type);
2327         if (!nr_args) {
2328                 btf_verifier_log(env, "void");
2329                 goto done;
2330         }
2331
2332         if (nr_args == 1 && !args[0].type) {
2333                 /* Only one vararg */
2334                 btf_verifier_log(env, "vararg");
2335                 goto done;
2336         }
2337
2338         btf_verifier_log(env, "%u %s", args[0].type,
2339                          __btf_name_by_offset(env->btf,
2340                                               args[0].name_off));
2341         for (i = 1; i < nr_args - 1; i++)
2342                 btf_verifier_log(env, ", %u %s", args[i].type,
2343                                  __btf_name_by_offset(env->btf,
2344                                                       args[i].name_off));
2345
2346         if (nr_args > 1) {
2347                 const struct btf_param *last_arg = &args[nr_args - 1];
2348
2349                 if (last_arg->type)
2350                         btf_verifier_log(env, ", %u %s", last_arg->type,
2351                                          __btf_name_by_offset(env->btf,
2352                                                               last_arg->name_off));
2353                 else
2354                         btf_verifier_log(env, ", vararg");
2355         }
2356
2357 done:
2358         btf_verifier_log(env, ")");
2359 }
2360
2361 static struct btf_kind_operations func_proto_ops = {
2362         .check_meta = btf_func_proto_check_meta,
2363         .resolve = btf_df_resolve,
2364         /*
2365          * BTF_KIND_FUNC_PROTO cannot be directly referred by
2366          * a struct's member.
2367          *
2368          * It should be a funciton pointer instead.
2369          * (i.e. struct's member -> BTF_KIND_PTR -> BTF_KIND_FUNC_PROTO)
2370          *
2371          * Hence, there is no btf_func_check_member().
2372          */
2373         .check_member = btf_df_check_member,
2374         .check_kflag_member = btf_df_check_kflag_member,
2375         .log_details = btf_func_proto_log,
2376         .seq_show = btf_df_seq_show,
2377 };
2378
2379 static s32 btf_func_check_meta(struct btf_verifier_env *env,
2380                                const struct btf_type *t,
2381                                u32 meta_left)
2382 {
2383         if (!t->name_off ||
2384             !btf_name_valid_identifier(env->btf, t->name_off)) {
2385                 btf_verifier_log_type(env, t, "Invalid name");
2386                 return -EINVAL;
2387         }
2388
2389         if (btf_type_vlen(t)) {
2390                 btf_verifier_log_type(env, t, "vlen != 0");
2391                 return -EINVAL;
2392         }
2393
2394         if (btf_type_kflag(t)) {
2395                 btf_verifier_log_type(env, t, "Invalid btf_info kind_flag");
2396                 return -EINVAL;
2397         }
2398
2399         btf_verifier_log_type(env, t, NULL);
2400
2401         return 0;
2402 }
2403
2404 static struct btf_kind_operations func_ops = {
2405         .check_meta = btf_func_check_meta,
2406         .resolve = btf_df_resolve,
2407         .check_member = btf_df_check_member,
2408         .check_kflag_member = btf_df_check_kflag_member,
2409         .log_details = btf_ref_type_log,
2410         .seq_show = btf_df_seq_show,
2411 };
2412
2413 static int btf_func_proto_check(struct btf_verifier_env *env,
2414                                 const struct btf_type *t)
2415 {
2416         const struct btf_type *ret_type;
2417         const struct btf_param *args;
2418         const struct btf *btf;
2419         u16 nr_args, i;
2420         int err;
2421
2422         btf = env->btf;
2423         args = (const struct btf_param *)(t + 1);
2424         nr_args = btf_type_vlen(t);
2425
2426         /* Check func return type which could be "void" (t->type == 0) */
2427         if (t->type) {
2428                 u32 ret_type_id = t->type;
2429
2430                 ret_type = btf_type_by_id(btf, ret_type_id);
2431                 if (!ret_type) {
2432                         btf_verifier_log_type(env, t, "Invalid return type");
2433                         return -EINVAL;
2434                 }
2435
2436                 if (btf_type_needs_resolve(ret_type) &&
2437                     !env_type_is_resolved(env, ret_type_id)) {
2438                         err = btf_resolve(env, ret_type, ret_type_id);
2439                         if (err)
2440                                 return err;
2441                 }
2442
2443                 /* Ensure the return type is a type that has a size */
2444                 if (!btf_type_id_size(btf, &ret_type_id, NULL)) {
2445                         btf_verifier_log_type(env, t, "Invalid return type");
2446                         return -EINVAL;
2447                 }
2448         }
2449
2450         if (!nr_args)
2451                 return 0;
2452
2453         /* Last func arg type_id could be 0 if it is a vararg */
2454         if (!args[nr_args - 1].type) {
2455                 if (args[nr_args - 1].name_off) {
2456                         btf_verifier_log_type(env, t, "Invalid arg#%u",
2457                                               nr_args);
2458                         return -EINVAL;
2459                 }
2460                 nr_args--;
2461         }
2462
2463         err = 0;
2464         for (i = 0; i < nr_args; i++) {
2465                 const struct btf_type *arg_type;
2466                 u32 arg_type_id;
2467
2468                 arg_type_id = args[i].type;
2469                 arg_type = btf_type_by_id(btf, arg_type_id);
2470                 if (!arg_type) {
2471                         btf_verifier_log_type(env, t, "Invalid arg#%u", i + 1);
2472                         err = -EINVAL;
2473                         break;
2474                 }
2475
2476                 if (args[i].name_off &&
2477                     (!btf_name_offset_valid(btf, args[i].name_off) ||
2478                      !btf_name_valid_identifier(btf, args[i].name_off))) {
2479                         btf_verifier_log_type(env, t,
2480                                               "Invalid arg#%u", i + 1);
2481                         err = -EINVAL;
2482                         break;
2483                 }
2484
2485                 if (btf_type_needs_resolve(arg_type) &&
2486                     !env_type_is_resolved(env, arg_type_id)) {
2487                         err = btf_resolve(env, arg_type, arg_type_id);
2488                         if (err)
2489                                 break;
2490                 }
2491
2492                 if (!btf_type_id_size(btf, &arg_type_id, NULL)) {
2493                         btf_verifier_log_type(env, t, "Invalid arg#%u", i + 1);
2494                         err = -EINVAL;
2495                         break;
2496                 }
2497         }
2498
2499         return err;
2500 }
2501
2502 static int btf_func_check(struct btf_verifier_env *env,
2503                           const struct btf_type *t)
2504 {
2505         const struct btf_type *proto_type;
2506         const struct btf_param *args;
2507         const struct btf *btf;
2508         u16 nr_args, i;
2509
2510         btf = env->btf;
2511         proto_type = btf_type_by_id(btf, t->type);
2512
2513         if (!proto_type || !btf_type_is_func_proto(proto_type)) {
2514                 btf_verifier_log_type(env, t, "Invalid type_id");
2515                 return -EINVAL;
2516         }
2517
2518         args = (const struct btf_param *)(proto_type + 1);
2519         nr_args = btf_type_vlen(proto_type);
2520         for (i = 0; i < nr_args; i++) {
2521                 if (!args[i].name_off && args[i].type) {
2522                         btf_verifier_log_type(env, t, "Invalid arg#%u", i + 1);
2523                         return -EINVAL;
2524                 }
2525         }
2526
2527         return 0;
2528 }
2529
2530 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS] = {
2531         [BTF_KIND_INT] = &int_ops,
2532         [BTF_KIND_PTR] = &ptr_ops,
2533         [BTF_KIND_ARRAY] = &array_ops,
2534         [BTF_KIND_STRUCT] = &struct_ops,
2535         [BTF_KIND_UNION] = &struct_ops,
2536         [BTF_KIND_ENUM] = &enum_ops,
2537         [BTF_KIND_FWD] = &fwd_ops,
2538         [BTF_KIND_TYPEDEF] = &modifier_ops,
2539         [BTF_KIND_VOLATILE] = &modifier_ops,
2540         [BTF_KIND_CONST] = &modifier_ops,
2541         [BTF_KIND_RESTRICT] = &modifier_ops,
2542         [BTF_KIND_FUNC] = &func_ops,
2543         [BTF_KIND_FUNC_PROTO] = &func_proto_ops,
2544 };
2545
2546 static s32 btf_check_meta(struct btf_verifier_env *env,
2547                           const struct btf_type *t,
2548                           u32 meta_left)
2549 {
2550         u32 saved_meta_left = meta_left;
2551         s32 var_meta_size;
2552
2553         if (meta_left < sizeof(*t)) {
2554                 btf_verifier_log(env, "[%u] meta_left:%u meta_needed:%zu",
2555                                  env->log_type_id, meta_left, sizeof(*t));
2556                 return -EINVAL;
2557         }
2558         meta_left -= sizeof(*t);
2559
2560         if (t->info & ~BTF_INFO_MASK) {
2561                 btf_verifier_log(env, "[%u] Invalid btf_info:%x",
2562                                  env->log_type_id, t->info);
2563                 return -EINVAL;
2564         }
2565
2566         if (BTF_INFO_KIND(t->info) > BTF_KIND_MAX ||
2567             BTF_INFO_KIND(t->info) == BTF_KIND_UNKN) {
2568                 btf_verifier_log(env, "[%u] Invalid kind:%u",
2569                                  env->log_type_id, BTF_INFO_KIND(t->info));
2570                 return -EINVAL;
2571         }
2572
2573         if (!btf_name_offset_valid(env->btf, t->name_off)) {
2574                 btf_verifier_log(env, "[%u] Invalid name_offset:%u",
2575                                  env->log_type_id, t->name_off);
2576                 return -EINVAL;
2577         }
2578
2579         var_meta_size = btf_type_ops(t)->check_meta(env, t, meta_left);
2580         if (var_meta_size < 0)
2581                 return var_meta_size;
2582
2583         meta_left -= var_meta_size;
2584
2585         return saved_meta_left - meta_left;
2586 }
2587
2588 static int btf_check_all_metas(struct btf_verifier_env *env)
2589 {
2590         struct btf *btf = env->btf;
2591         struct btf_header *hdr;
2592         void *cur, *end;
2593
2594         hdr = &btf->hdr;
2595         cur = btf->nohdr_data + hdr->type_off;
2596         end = cur + hdr->type_len;
2597
2598         env->log_type_id = 1;
2599         while (cur < end) {
2600                 struct btf_type *t = cur;
2601                 s32 meta_size;
2602
2603                 meta_size = btf_check_meta(env, t, end - cur);
2604                 if (meta_size < 0)
2605                         return meta_size;
2606
2607                 btf_add_type(env, t);
2608                 cur += meta_size;
2609                 env->log_type_id++;
2610         }
2611
2612         return 0;
2613 }
2614
2615 static bool btf_resolve_valid(struct btf_verifier_env *env,
2616                               const struct btf_type *t,
2617                               u32 type_id)
2618 {
2619         struct btf *btf = env->btf;
2620
2621         if (!env_type_is_resolved(env, type_id))
2622                 return false;
2623
2624         if (btf_type_is_struct(t))
2625                 return !btf->resolved_ids[type_id] &&
2626                         !btf->resolved_sizes[type_id];
2627
2628         if (btf_type_is_modifier(t) || btf_type_is_ptr(t)) {
2629                 t = btf_type_id_resolve(btf, &type_id);
2630                 return t && !btf_type_is_modifier(t);
2631         }
2632
2633         if (btf_type_is_array(t)) {
2634                 const struct btf_array *array = btf_type_array(t);
2635                 const struct btf_type *elem_type;
2636                 u32 elem_type_id = array->type;
2637                 u32 elem_size;
2638
2639                 elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
2640                 return elem_type && !btf_type_is_modifier(elem_type) &&
2641                         (array->nelems * elem_size ==
2642                          btf->resolved_sizes[type_id]);
2643         }
2644
2645         return false;
2646 }
2647
2648 static int btf_resolve(struct btf_verifier_env *env,
2649                        const struct btf_type *t, u32 type_id)
2650 {
2651         u32 save_log_type_id = env->log_type_id;
2652         const struct resolve_vertex *v;
2653         int err = 0;
2654
2655         env->resolve_mode = RESOLVE_TBD;
2656         env_stack_push(env, t, type_id);
2657         while (!err && (v = env_stack_peak(env))) {
2658                 env->log_type_id = v->type_id;
2659                 err = btf_type_ops(v->t)->resolve(env, v);
2660         }
2661
2662         env->log_type_id = type_id;
2663         if (err == -E2BIG) {
2664                 btf_verifier_log_type(env, t,
2665                                       "Exceeded max resolving depth:%u",
2666                                       MAX_RESOLVE_DEPTH);
2667         } else if (err == -EEXIST) {
2668                 btf_verifier_log_type(env, t, "Loop detected");
2669         }
2670
2671         /* Final sanity check */
2672         if (!err && !btf_resolve_valid(env, t, type_id)) {
2673                 btf_verifier_log_type(env, t, "Invalid resolve state");
2674                 err = -EINVAL;
2675         }
2676
2677         env->log_type_id = save_log_type_id;
2678         return err;
2679 }
2680
2681 static int btf_check_all_types(struct btf_verifier_env *env)
2682 {
2683         struct btf *btf = env->btf;
2684         u32 type_id;
2685         int err;
2686
2687         err = env_resolve_init(env);
2688         if (err)
2689                 return err;
2690
2691         env->phase++;
2692         for (type_id = 1; type_id <= btf->nr_types; type_id++) {
2693                 const struct btf_type *t = btf_type_by_id(btf, type_id);
2694
2695                 env->log_type_id = type_id;
2696                 if (btf_type_needs_resolve(t) &&
2697                     !env_type_is_resolved(env, type_id)) {
2698                         err = btf_resolve(env, t, type_id);
2699                         if (err)
2700                                 return err;
2701                 }
2702
2703                 if (btf_type_is_func_proto(t)) {
2704                         err = btf_func_proto_check(env, t);
2705                         if (err)
2706                                 return err;
2707                 }
2708
2709                 if (btf_type_is_func(t)) {
2710                         err = btf_func_check(env, t);
2711                         if (err)
2712                                 return err;
2713                 }
2714         }
2715
2716         return 0;
2717 }
2718
2719 static int btf_parse_type_sec(struct btf_verifier_env *env)
2720 {
2721         const struct btf_header *hdr = &env->btf->hdr;
2722         int err;
2723
2724         /* Type section must align to 4 bytes */
2725         if (hdr->type_off & (sizeof(u32) - 1)) {
2726                 btf_verifier_log(env, "Unaligned type_off");
2727                 return -EINVAL;
2728         }
2729
2730         if (!hdr->type_len) {
2731                 btf_verifier_log(env, "No type found");
2732                 return -EINVAL;
2733         }
2734
2735         err = btf_check_all_metas(env);
2736         if (err)
2737                 return err;
2738
2739         return btf_check_all_types(env);
2740 }
2741
2742 static int btf_parse_str_sec(struct btf_verifier_env *env)
2743 {
2744         const struct btf_header *hdr;
2745         struct btf *btf = env->btf;
2746         const char *start, *end;
2747
2748         hdr = &btf->hdr;
2749         start = btf->nohdr_data + hdr->str_off;
2750         end = start + hdr->str_len;
2751
2752         if (end != btf->data + btf->data_size) {
2753                 btf_verifier_log(env, "String section is not at the end");
2754                 return -EINVAL;
2755         }
2756
2757         if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_NAME_OFFSET ||
2758             start[0] || end[-1]) {
2759                 btf_verifier_log(env, "Invalid string section");
2760                 return -EINVAL;
2761         }
2762
2763         btf->strings = start;
2764
2765         return 0;
2766 }
2767
2768 static const size_t btf_sec_info_offset[] = {
2769         offsetof(struct btf_header, type_off),
2770         offsetof(struct btf_header, str_off),
2771 };
2772
2773 static int btf_sec_info_cmp(const void *a, const void *b)
2774 {
2775         const struct btf_sec_info *x = a;
2776         const struct btf_sec_info *y = b;
2777
2778         return (int)(x->off - y->off) ? : (int)(x->len - y->len);
2779 }
2780
2781 static int btf_check_sec_info(struct btf_verifier_env *env,
2782                               u32 btf_data_size)
2783 {
2784         struct btf_sec_info secs[ARRAY_SIZE(btf_sec_info_offset)];
2785         u32 total, expected_total, i;
2786         const struct btf_header *hdr;
2787         const struct btf *btf;
2788
2789         btf = env->btf;
2790         hdr = &btf->hdr;
2791
2792         /* Populate the secs from hdr */
2793         for (i = 0; i < ARRAY_SIZE(btf_sec_info_offset); i++)
2794                 secs[i] = *(struct btf_sec_info *)((void *)hdr +
2795                                                    btf_sec_info_offset[i]);
2796
2797         sort(secs, ARRAY_SIZE(btf_sec_info_offset),
2798              sizeof(struct btf_sec_info), btf_sec_info_cmp, NULL);
2799
2800         /* Check for gaps and overlap among sections */
2801         total = 0;
2802         expected_total = btf_data_size - hdr->hdr_len;
2803         for (i = 0; i < ARRAY_SIZE(btf_sec_info_offset); i++) {
2804                 if (expected_total < secs[i].off) {
2805                         btf_verifier_log(env, "Invalid section offset");
2806                         return -EINVAL;
2807                 }
2808                 if (total < secs[i].off) {
2809                         /* gap */
2810                         btf_verifier_log(env, "Unsupported section found");
2811                         return -EINVAL;
2812                 }
2813                 if (total > secs[i].off) {
2814                         btf_verifier_log(env, "Section overlap found");
2815                         return -EINVAL;
2816                 }
2817                 if (expected_total - total < secs[i].len) {
2818                         btf_verifier_log(env,
2819                                          "Total section length too long");
2820                         return -EINVAL;
2821                 }
2822                 total += secs[i].len;
2823         }
2824
2825         /* There is data other than hdr and known sections */
2826         if (expected_total != total) {
2827                 btf_verifier_log(env, "Unsupported section found");
2828                 return -EINVAL;
2829         }
2830
2831         return 0;
2832 }
2833
2834 static int btf_parse_hdr(struct btf_verifier_env *env)
2835 {
2836         u32 hdr_len, hdr_copy, btf_data_size;
2837         const struct btf_header *hdr;
2838         struct btf *btf;
2839         int err;
2840
2841         btf = env->btf;
2842         btf_data_size = btf->data_size;
2843
2844         if (btf_data_size <
2845             offsetof(struct btf_header, hdr_len) + sizeof(hdr->hdr_len)) {
2846                 btf_verifier_log(env, "hdr_len not found");
2847                 return -EINVAL;
2848         }
2849
2850         hdr = btf->data;
2851         hdr_len = hdr->hdr_len;
2852         if (btf_data_size < hdr_len) {
2853                 btf_verifier_log(env, "btf_header not found");
2854                 return -EINVAL;
2855         }
2856
2857         /* Ensure the unsupported header fields are zero */
2858         if (hdr_len > sizeof(btf->hdr)) {
2859                 u8 *expected_zero = btf->data + sizeof(btf->hdr);
2860                 u8 *end = btf->data + hdr_len;
2861
2862                 for (; expected_zero < end; expected_zero++) {
2863                         if (*expected_zero) {
2864                                 btf_verifier_log(env, "Unsupported btf_header");
2865                                 return -E2BIG;
2866                         }
2867                 }
2868         }
2869
2870         hdr_copy = min_t(u32, hdr_len, sizeof(btf->hdr));
2871         memcpy(&btf->hdr, btf->data, hdr_copy);
2872
2873         hdr = &btf->hdr;
2874
2875         btf_verifier_log_hdr(env, btf_data_size);
2876
2877         if (hdr->magic != BTF_MAGIC) {
2878                 btf_verifier_log(env, "Invalid magic");
2879                 return -EINVAL;
2880         }
2881
2882         if (hdr->version != BTF_VERSION) {
2883                 btf_verifier_log(env, "Unsupported version");
2884                 return -ENOTSUPP;
2885         }
2886
2887         if (hdr->flags) {
2888                 btf_verifier_log(env, "Unsupported flags");
2889                 return -ENOTSUPP;
2890         }
2891
2892         if (btf_data_size == hdr->hdr_len) {
2893                 btf_verifier_log(env, "No data");
2894                 return -EINVAL;
2895         }
2896
2897         err = btf_check_sec_info(env, btf_data_size);
2898         if (err)
2899                 return err;
2900
2901         return 0;
2902 }
2903
2904 static struct btf *btf_parse(void __user *btf_data, u32 btf_data_size,
2905                              u32 log_level, char __user *log_ubuf, u32 log_size)
2906 {
2907         struct btf_verifier_env *env = NULL;
2908         struct bpf_verifier_log *log;
2909         struct btf *btf = NULL;
2910         u8 *data;
2911         int err;
2912
2913         if (btf_data_size > BTF_MAX_SIZE)
2914                 return ERR_PTR(-E2BIG);
2915
2916         env = kzalloc(sizeof(*env), GFP_KERNEL | __GFP_NOWARN);
2917         if (!env)
2918                 return ERR_PTR(-ENOMEM);
2919
2920         log = &env->log;
2921         if (log_level || log_ubuf || log_size) {
2922                 /* user requested verbose verifier output
2923                  * and supplied buffer to store the verification trace
2924                  */
2925                 log->level = log_level;
2926                 log->ubuf = log_ubuf;
2927                 log->len_total = log_size;
2928
2929                 /* log attributes have to be sane */
2930                 if (log->len_total < 128 || log->len_total > UINT_MAX >> 8 ||
2931                     !log->level || !log->ubuf) {
2932                         err = -EINVAL;
2933                         goto errout;
2934                 }
2935         }
2936
2937         btf = kzalloc(sizeof(*btf), GFP_KERNEL | __GFP_NOWARN);
2938         if (!btf) {
2939                 err = -ENOMEM;
2940                 goto errout;
2941         }
2942         env->btf = btf;
2943
2944         data = kvmalloc(btf_data_size, GFP_KERNEL | __GFP_NOWARN);
2945         if (!data) {
2946                 err = -ENOMEM;
2947                 goto errout;
2948         }
2949
2950         btf->data = data;
2951         btf->data_size = btf_data_size;
2952
2953         if (copy_from_user(data, btf_data, btf_data_size)) {
2954                 err = -EFAULT;
2955                 goto errout;
2956         }
2957
2958         err = btf_parse_hdr(env);
2959         if (err)
2960                 goto errout;
2961
2962         btf->nohdr_data = btf->data + btf->hdr.hdr_len;
2963
2964         err = btf_parse_str_sec(env);
2965         if (err)
2966                 goto errout;
2967
2968         err = btf_parse_type_sec(env);
2969         if (err)
2970                 goto errout;
2971
2972         if (log->level && bpf_verifier_log_full(log)) {
2973                 err = -ENOSPC;
2974                 goto errout;
2975         }
2976
2977         btf_verifier_env_free(env);
2978         refcount_set(&btf->refcnt, 1);
2979         return btf;
2980
2981 errout:
2982         btf_verifier_env_free(env);
2983         if (btf)
2984                 btf_free(btf);
2985         return ERR_PTR(err);
2986 }
2987
2988 void btf_type_seq_show(const struct btf *btf, u32 type_id, void *obj,
2989                        struct seq_file *m)
2990 {
2991         const struct btf_type *t = btf_type_by_id(btf, type_id);
2992
2993         btf_type_ops(t)->seq_show(btf, t, type_id, obj, 0, m);
2994 }
2995
2996 static int btf_release(struct inode *inode, struct file *filp)
2997 {
2998         btf_put(filp->private_data);
2999         return 0;
3000 }
3001
3002 const struct file_operations btf_fops = {
3003         .release        = btf_release,
3004 };
3005
3006 static int __btf_new_fd(struct btf *btf)
3007 {
3008         return anon_inode_getfd("btf", &btf_fops, btf, O_RDONLY | O_CLOEXEC);
3009 }
3010
3011 int btf_new_fd(const union bpf_attr *attr)
3012 {
3013         struct btf *btf;
3014         int ret;
3015
3016         btf = btf_parse(u64_to_user_ptr(attr->btf),
3017                         attr->btf_size, attr->btf_log_level,
3018                         u64_to_user_ptr(attr->btf_log_buf),
3019                         attr->btf_log_size);
3020         if (IS_ERR(btf))
3021                 return PTR_ERR(btf);
3022
3023         ret = btf_alloc_id(btf);
3024         if (ret) {
3025                 btf_free(btf);
3026                 return ret;
3027         }
3028
3029         /*
3030          * The BTF ID is published to the userspace.
3031          * All BTF free must go through call_rcu() from
3032          * now on (i.e. free by calling btf_put()).
3033          */
3034
3035         ret = __btf_new_fd(btf);
3036         if (ret < 0)
3037                 btf_put(btf);
3038
3039         return ret;
3040 }
3041
3042 struct btf *btf_get_by_fd(int fd)
3043 {
3044         struct btf *btf;
3045         struct fd f;
3046
3047         f = fdget(fd);
3048
3049         if (!f.file)
3050                 return ERR_PTR(-EBADF);
3051
3052         if (f.file->f_op != &btf_fops) {
3053                 fdput(f);
3054                 return ERR_PTR(-EINVAL);
3055         }
3056
3057         btf = f.file->private_data;
3058         refcount_inc(&btf->refcnt);
3059         fdput(f);
3060
3061         return btf;
3062 }
3063
3064 int btf_get_info_by_fd(const struct btf *btf,
3065                        const union bpf_attr *attr,
3066                        union bpf_attr __user *uattr)
3067 {
3068         struct bpf_btf_info __user *uinfo;
3069         struct bpf_btf_info info = {};
3070         u32 info_copy, btf_copy;
3071         void __user *ubtf;
3072         u32 uinfo_len;
3073
3074         uinfo = u64_to_user_ptr(attr->info.info);
3075         uinfo_len = attr->info.info_len;
3076
3077         info_copy = min_t(u32, uinfo_len, sizeof(info));
3078         if (copy_from_user(&info, uinfo, info_copy))
3079                 return -EFAULT;
3080
3081         info.id = btf->id;
3082         ubtf = u64_to_user_ptr(info.btf);
3083         btf_copy = min_t(u32, btf->data_size, info.btf_size);
3084         if (copy_to_user(ubtf, btf->data, btf_copy))
3085                 return -EFAULT;
3086         info.btf_size = btf->data_size;
3087
3088         if (copy_to_user(uinfo, &info, info_copy) ||
3089             put_user(info_copy, &uattr->info.info_len))
3090                 return -EFAULT;
3091
3092         return 0;
3093 }
3094
3095 int btf_get_fd_by_id(u32 id)
3096 {
3097         struct btf *btf;
3098         int fd;
3099
3100         rcu_read_lock();
3101         btf = idr_find(&btf_idr, id);
3102         if (!btf || !refcount_inc_not_zero(&btf->refcnt))
3103                 btf = ERR_PTR(-ENOENT);
3104         rcu_read_unlock();
3105
3106         if (IS_ERR(btf))
3107                 return PTR_ERR(btf);
3108
3109         fd = __btf_new_fd(btf);
3110         if (fd < 0)
3111                 btf_put(btf);
3112
3113         return fd;
3114 }
3115
3116 u32 btf_id(const struct btf *btf)
3117 {
3118         return btf->id;
3119 }