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