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