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/errno.h>
   9 #include <linux/slab.h>
  10 #include <linux/anon_inodes.h>
  11 #include <linux/file.h>
  12 #include <linux/uaccess.h>
  13 #include <linux/kernel.h>
  14 #include <linux/idr.h>
  15 #include <linux/sort.h>
  16 #include <linux/bpf_verifier.h>
  17 #include <linux/btf.h>
  18
  19 /* BTF (BPF Type Format) is the meta data format which describes
  20  * the data types of BPF program/map.  Hence, it basically focus
  21  * on the C programming language which the modern BPF is primary
  22  * using.
  23  *
  24  * ELF Section:
  25  * ~~~~~~~~~~~
  26  * The BTF data is stored under the ".BTF" ELF section
  27  *
  28  * struct btf_type:
  29  * ~~~~~~~~~~~~~~~
  30  * Each 'struct btf_type' object describes a C data type.
  31  * Depending on the type it is describing, a 'struct btf_type'
  32  * object may be followed by more data.  F.e.
  33  * To describe an array, 'struct btf_type' is followed by
  34  * 'struct btf_array'.
  35  *
  36  * 'struct btf_type' and any extra data following it are
  37  * 4 bytes aligned.
  38  *
  39  * Type section:
  40  * ~~~~~~~~~~~~~
  41  * The BTF type section contains a list of 'struct btf_type' objects.
  42  * Each one describes a C type.  Recall from the above section
  43  * that a 'struct btf_type' object could be immediately followed by extra
  44  * data in order to desribe some particular C types.
  45  *
  46  * type_id:
  47  * ~~~~~~~
  48  * Each btf_type object is identified by a type_id.  The type_id
  49  * is implicitly implied by the location of the btf_type object in
  50  * the BTF type section.  The first one has type_id 1.  The second
  51  * one has type_id 2...etc.  Hence, an earlier btf_type has
  52  * a smaller type_id.
  53  *
  54  * A btf_type object may refer to another btf_type object by using
  55  * type_id (i.e. the "type" in the "struct btf_type").
  56  *
  57  * NOTE that we cannot assume any reference-order.
  58  * A btf_type object can refer to an earlier btf_type object
  59  * but it can also refer to a later btf_type object.
  60  *
  61  * For example, to describe "const void *".  A btf_type
  62  * object describing "const" may refer to another btf_type
  63  * object describing "void *".  This type-reference is done
  64  * by specifying type_id:
  65  *
  66  * [1] CONST (anon) type_id=2
  67  * [2] PTR (anon) type_id=0
  68  *
  69  * The above is the btf_verifier debug log:
  70  *   - Each line started with "[?]" is a btf_type object
  71  *   - [?] is the type_id of the btf_type object.
  72  *   - CONST/PTR is the BTF_KIND_XXX
  73  *   - "(anon)" is the name of the type.  It just
  74  *     happens that CONST and PTR has no name.
  75  *   - type_id=XXX is the 'u32 type' in btf_type
  76  *
  77  * NOTE: "void" has type_id 0
  78  *
  79  * String section:
  80  * ~~~~~~~~~~~~~~
  81  * The BTF string section contains the names used by the type section.
  82  * Each string is referred by an "offset" from the beginning of the
  83  * string section.
  84  *
  85  * Each string is '\0' terminated.
  86  *
  87  * The first character in the string section must be '\0'
  88  * which is used to mean 'anonymous'. Some btf_type may not
  89  * have a name.
  90  */
  91
  92 /* BTF verification:
  93  *
  94  * To verify BTF data, two passes are needed.
  95  *
  96  * Pass #1
  97  * ~~~~~~~
  98  * The first pass is to collect all btf_type objects to
  99  * an array: "btf->types".
 100  *
 101  * Depending on the C type that a btf_type is describing,
 102  * a btf_type may be followed by extra data.  We don't know
 103  * how many btf_type is there, and more importantly we don't
 104  * know where each btf_type is located in the type section.
 105  *
 106  * Without knowing the location of each type_id, most verifications
 107  * cannot be done.  e.g. an earlier btf_type may refer to a later
 108  * btf_type (recall the "const void *" above), so we cannot
 109  * check this type-reference in the first pass.
 110  *
 111  * In the first pass, it still does some verifications (e.g.
 112  * checking the name is a valid offset to the string section).
 113  *
 114  * Pass #2
 115  * ~~~~~~~
 116  * The main focus is to resolve a btf_type that is referring
 117  * to another type.
 118  *
 119  * We have to ensure the referring type:
 120  * 1) does exist in the BTF (i.e. in btf->types[])
 121  * 2) does not cause a loop:
 122  *      struct A {
 123  *              struct B b;
 124  *      };
 125  *
 126  *      struct B {
 127  *              struct A a;
 128  *      };
 129  *
 130  * btf_type_needs_resolve() decides if a btf_type needs
 131  * to be resolved.
 132  *
 133  * The needs_resolve type implements the "resolve()" ops which
 134  * essentially does a DFS and detects backedge.
 135  *
 136  * During resolve (or DFS), different C types have different
 137  * "RESOLVED" conditions.
 138  *
 139  * When resolving a BTF_KIND_STRUCT, we need to resolve all its
 140  * members because a member is always referring to another
 141  * type.  A struct's member can be treated as "RESOLVED" if
 142  * it is referring to a BTF_KIND_PTR.  Otherwise, the
 143  * following valid C struct would be rejected:
 144  *
 145  *      struct A {
 146  *              int m;
 147  *              struct A *a;
 148  *      };
 149  *
 150  * When resolving a BTF_KIND_PTR, it needs to keep resolving if
 151  * it is referring to another BTF_KIND_PTR.  Otherwise, we cannot
 152  * detect a pointer loop, e.g.:
 153  * BTF_KIND_CONST -> BTF_KIND_PTR -> BTF_KIND_CONST -> BTF_KIND_PTR +
 154  *                        ^                                         |
 155  *                        +-----------------------------------------+
 156  *
 157  */
 158
 159 #define BITS_PER_U64 (sizeof(u64) * BITS_PER_BYTE)
 160 #define BITS_PER_BYTE_MASK (BITS_PER_BYTE - 1)
 161 #define BITS_PER_BYTE_MASKED(bits) ((bits) & BITS_PER_BYTE_MASK)
 162 #define BITS_ROUNDDOWN_BYTES(bits) ((bits) >> 3)
 163 #define BITS_ROUNDUP_BYTES(bits) \
 164         (BITS_ROUNDDOWN_BYTES(bits) + !!BITS_PER_BYTE_MASKED(bits))
 165
 166 #define BTF_INFO_MASK 0x0f00ffff
 167 #define BTF_INT_MASK 0x0fffffff
 168 #define BTF_TYPE_ID_VALID(type_id) ((type_id) <= BTF_MAX_TYPE)
 169 #define BTF_STR_OFFSET_VALID(name_off) ((name_off) <= BTF_MAX_NAME_OFFSET)
 170
 171 /* 16MB for 64k structs and each has 16 members and
 172  * a few MB spaces for the string section.
 173  * The hard limit is S32_MAX.
 174  */
 175 #define BTF_MAX_SIZE (16 * 1024 * 1024)
 176
 177 #define for_each_member(i, struct_type, member)                 \
 178         for (i = 0, member = btf_type_member(struct_type);      \
 179              i < btf_type_vlen(struct_type);                    \
 180              i++, member++)
 181
 182 #define for_each_member_from(i, from, struct_type, member)              \
 183         for (i = from, member = btf_type_member(struct_type) + from;    \
 184              i < btf_type_vlen(struct_type);                            \
 185              i++, member++)
 186
 187 static DEFINE_IDR(btf_idr);
 188 static DEFINE_SPINLOCK(btf_idr_lock);
 189
 190 struct btf {
 191         void *data;
 192         struct btf_type **types;
 193         u32 *resolved_ids;
 194         u32 *resolved_sizes;
 195         const char *strings;
 196         void *nohdr_data;
 197         struct btf_header hdr;
 198         u32 nr_types;
 199         u32 types_size;
 200         u32 data_size;
 201         refcount_t refcnt;
 202         u32 id;
 203         struct rcu_head rcu;
 204 };
 205
 206 enum verifier_phase {
 207         CHECK_META,
 208         CHECK_TYPE,
 209 };
 210
 211 struct resolve_vertex {
 212         const struct btf_type *t;
 213         u32 type_id;
 214         u16 next_member;
 215 };
 216
 217 enum visit_state {
 218         NOT_VISITED,
 219         VISITED,
 220         RESOLVED,
 221 };
 222
 223 enum resolve_mode {
 224         RESOLVE_TBD,    /* To Be Determined */
 225         RESOLVE_PTR,    /* Resolving for Pointer */
 226         RESOLVE_STRUCT_OR_ARRAY,        /* Resolving for struct/union
 227                                          * or array
 228                                          */
 229 };
 230
 231 #define MAX_RESOLVE_DEPTH 32
 232
 233 struct btf_sec_info {
 234         u32 off;
 235         u32 len;
 236 };
 237
 238 struct btf_verifier_env {
 239         struct btf *btf;
 240         u8 *visit_states;
 241         struct resolve_vertex stack[MAX_RESOLVE_DEPTH];
 242         struct bpf_verifier_log log;
 243         u32 log_type_id;
 244         u32 top_stack;
 245         enum verifier_phase phase;
 246         enum resolve_mode resolve_mode;
 247 };
 248
 249 static const char * const btf_kind_str[NR_BTF_KINDS] = {
 250         [BTF_KIND_UNKN]         = "UNKNOWN",
 251         [BTF_KIND_INT]          = "INT",
 252         [BTF_KIND_PTR]          = "PTR",
 253         [BTF_KIND_ARRAY]        = "ARRAY",
 254         [BTF_KIND_STRUCT]       = "STRUCT",
 255         [BTF_KIND_UNION]        = "UNION",
 256         [BTF_KIND_ENUM]         = "ENUM",
 257         [BTF_KIND_FWD]          = "FWD",
 258         [BTF_KIND_TYPEDEF]      = "TYPEDEF",
 259         [BTF_KIND_VOLATILE]     = "VOLATILE",
 260         [BTF_KIND_CONST]        = "CONST",
 261         [BTF_KIND_RESTRICT]     = "RESTRICT",
 262 };
 263
 264 struct btf_kind_operations {
 265         s32 (*check_meta)(struct btf_verifier_env *env,
 266                           const struct btf_type *t,
 267                           u32 meta_left);
 268         int (*resolve)(struct btf_verifier_env *env,
 269                        const struct resolve_vertex *v);
 270         int (*check_member)(struct btf_verifier_env *env,
 271                             const struct btf_type *struct_type,
 272                             const struct btf_member *member,
 273                             const struct btf_type *member_type);
 274         void (*log_details)(struct btf_verifier_env *env,
 275                             const struct btf_type *t);
 276         void (*seq_show)(const struct btf *btf, const struct btf_type *t,
 277                          u32 type_id, void *data, u8 bits_offsets,
 278                          struct seq_file *m);
 279 };
 280
 281 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS];
 282 static struct btf_type btf_void;
 283
 284 static bool btf_type_is_modifier(const struct btf_type *t)
 285 {
 286         /* Some of them is not strictly a C modifier
 287          * but they are grouped into the same bucket
 288          * for BTF concern:
 289          *   A type (t) that refers to another
 290          *   type through t->type AND its size cannot
 291          *   be determined without following the t->type.
 292          *
 293          * ptr does not fall into this bucket
 294          * because its size is always sizeof(void *).
 295          */
 296         switch (BTF_INFO_KIND(t->info)) {
 297         case BTF_KIND_TYPEDEF:
 298         case BTF_KIND_VOLATILE:
 299         case BTF_KIND_CONST:
 300         case BTF_KIND_RESTRICT:
 301                 return true;
 302         }
 303
 304         return false;
 305 }
 306
 307 static bool btf_type_is_void(const struct btf_type *t)
 308 {
 309         /* void => no type and size info.
 310          * Hence, FWD is also treated as void.
 311          */
 312         return t == &btf_void || BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
 313 }
 314
 315 static bool btf_type_is_void_or_null(const struct btf_type *t)
 316 {
 317         return !t || btf_type_is_void(t);
 318 }
 319
 320 /* union is only a special case of struct:
 321  * all its offsetof(member) == 0
 322  */
 323 static bool btf_type_is_struct(const struct btf_type *t)
 324 {
 325         u8 kind = BTF_INFO_KIND(t->info);
 326
 327         return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
 328 }
 329
 330 static bool btf_type_is_array(const struct btf_type *t)
 331 {
 332         return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
 333 }
 334
 335 static bool btf_type_is_ptr(const struct btf_type *t)
 336 {
 337         return BTF_INFO_KIND(t->info) == BTF_KIND_PTR;
 338 }
 339
 340 static bool btf_type_is_int(const struct btf_type *t)
 341 {
 342         return BTF_INFO_KIND(t->info) == BTF_KIND_INT;
 343 }
 344
 345 /* What types need to be resolved?
 346  *
 347  * btf_type_is_modifier() is an obvious one.
 348  *
 349  * btf_type_is_struct() because its member refers to
 350  * another type (through member->type).
 351
 352  * btf_type_is_array() because its element (array->type)
 353  * refers to another type.  Array can be thought of a
 354  * special case of struct while array just has the same
 355  * member-type repeated by array->nelems of times.
 356  */
 357 static bool btf_type_needs_resolve(const struct btf_type *t)
 358 {
 359         return btf_type_is_modifier(t) ||
 360                 btf_type_is_ptr(t) ||
 361                 btf_type_is_struct(t) ||
 362                 btf_type_is_array(t);
 363 }
 364
 365 /* t->size can be used */
 366 static bool btf_type_has_size(const struct btf_type *t)
 367 {
 368         switch (BTF_INFO_KIND(t->info)) {
 369         case BTF_KIND_INT:
 370         case BTF_KIND_STRUCT:
 371         case BTF_KIND_UNION:
 372         case BTF_KIND_ENUM:
 373                 return true;
 374         }
 375
 376         return false;
 377 }
 378
 379 static const char *btf_int_encoding_str(u8 encoding)
 380 {
 381         if (encoding == 0)
 382                 return "(none)";
 383         else if (encoding == BTF_INT_SIGNED)
 384                 return "SIGNED";
 385         else if (encoding == BTF_INT_CHAR)
 386                 return "CHAR";
 387         else if (encoding == BTF_INT_BOOL)
 388                 return "BOOL";
 389         else
 390                 return "UNKN";
 391 }
 392
 393 static u16 btf_type_vlen(const struct btf_type *t)
 394 {
 395         return BTF_INFO_VLEN(t->info);
 396 }
 397
 398 static u32 btf_type_int(const struct btf_type *t)
 399 {
 400         return *(u32 *)(t + 1);
 401 }
 402
 403 static const struct btf_array *btf_type_array(const struct btf_type *t)
 404 {
 405         return (const struct btf_array *)(t + 1);
 406 }
 407
 408 static const struct btf_member *btf_type_member(const struct btf_type *t)
 409 {
 410         return (const struct btf_member *)(t + 1);
 411 }
 412
 413 static const struct btf_enum *btf_type_enum(const struct btf_type *t)
 414 {
 415         return (const struct btf_enum *)(t + 1);
 416 }
 417
 418 static const struct btf_kind_operations *btf_type_ops(const struct btf_type *t)
 419 {
 420         return kind_ops[BTF_INFO_KIND(t->info)];
 421 }
 422
 423 static bool btf_name_offset_valid(const struct btf *btf, u32 offset)
 424 {
 425         return BTF_STR_OFFSET_VALID(offset) &&
 426                 offset < btf->hdr.str_len;
 427 }
 428
 429 static const char *btf_name_by_offset(const struct btf *btf, u32 offset)
 430 {
 431         if (!offset)
 432                 return "(anon)";
 433         else if (offset < btf->hdr.str_len)
 434                 return &btf->strings[offset];
 435         else
 436                 return "(invalid-name-offset)";
 437 }
 438
 439 static const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id)
 440 {
 441         if (type_id > btf->nr_types)
 442                 return NULL;
 443
 444         return btf->types[type_id];
 445 }
 446
 447 /*
 448  * Regular int is not a bit field and it must be either
 449  * u8/u16/u32/u64.
 450  */
 451 static bool btf_type_int_is_regular(const struct btf_type *t)
 452 {
 453         u16 nr_bits, nr_bytes;
 454         u32 int_data;
 455
 456         int_data = btf_type_int(t);
 457         nr_bits = BTF_INT_BITS(int_data);
 458         nr_bytes = BITS_ROUNDUP_BYTES(nr_bits);
 459         if (BITS_PER_BYTE_MASKED(nr_bits) ||
 460             BTF_INT_OFFSET(int_data) ||
 461             (nr_bytes != sizeof(u8) && nr_bytes != sizeof(u16) &&
 462              nr_bytes != sizeof(u32) && nr_bytes != sizeof(u64))) {
 463                 return false;
 464         }
 465
 466         return true;
 467 }
 468
 469 __printf(2, 3) static void __btf_verifier_log(struct bpf_verifier_log *log,
 470                                               const char *fmt, ...)
 471 {
 472         va_list args;
 473
 474         va_start(args, fmt);
 475         bpf_verifier_vlog(log, fmt, args);
 476         va_end(args);
 477 }
 478
 479 __printf(2, 3) static void btf_verifier_log(struct btf_verifier_env *env,
 480                                             const char *fmt, ...)
 481 {
 482         struct bpf_verifier_log *log = &env->log;
 483         va_list args;
 484
 485         if (!bpf_verifier_log_needed(log))
 486                 return;
 487
 488         va_start(args, fmt);
 489         bpf_verifier_vlog(log, fmt, args);
 490         va_end(args);
 491 }
 492
 493 __printf(4, 5) static void __btf_verifier_log_type(struct btf_verifier_env *env,
 494                                                    const struct btf_type *t,
 495                                                    bool log_details,
 496                                                    const char *fmt, ...)
 497 {
 498         struct bpf_verifier_log *log = &env->log;
 499         u8 kind = BTF_INFO_KIND(t->info);
 500         struct btf *btf = env->btf;
 501         va_list args;
 502
 503         if (!bpf_verifier_log_needed(log))
 504                 return;
 505
 506         __btf_verifier_log(log, "[%u] %s %s%s",
 507                            env->log_type_id,
 508                            btf_kind_str[kind],
 509                            btf_name_by_offset(btf, t->name_off),
 510                            log_details ? " " : "");
 511
 512         if (log_details)
 513                 btf_type_ops(t)->log_details(env, t);
 514
 515         if (fmt && *fmt) {
 516                 __btf_verifier_log(log, " ");
 517                 va_start(args, fmt);
 518                 bpf_verifier_vlog(log, fmt, args);
 519                 va_end(args);
 520         }
 521
 522         __btf_verifier_log(log, "\n");
 523 }
 524
 525 #define btf_verifier_log_type(env, t, ...) \
 526         __btf_verifier_log_type((env), (t), true, __VA_ARGS__)
 527 #define btf_verifier_log_basic(env, t, ...) \
 528         __btf_verifier_log_type((env), (t), false, __VA_ARGS__)
 529
 530 __printf(4, 5)
 531 static void btf_verifier_log_member(struct btf_verifier_env *env,
 532                                     const struct btf_type *struct_type,
 533                                     const struct btf_member *member,
 534                                     const char *fmt, ...)
 535 {
 536         struct bpf_verifier_log *log = &env->log;
 537         struct btf *btf = env->btf;
 538         va_list args;
 539
 540         if (!bpf_verifier_log_needed(log))
 541                 return;
 542
 543         /* The CHECK_META phase already did a btf dump.
 544          *
 545          * If member is logged again, it must hit an error in
 546          * parsing this member.  It is useful to print out which
 547          * struct this member belongs to.
 548          */
 549         if (env->phase != CHECK_META)
 550                 btf_verifier_log_type(env, struct_type, NULL);
 551
 552         __btf_verifier_log(log, "\t%s type_id=%u bits_offset=%u",
 553                            btf_name_by_offset(btf, member->name_off),
 554                            member->type, member->offset);
 555
 556         if (fmt && *fmt) {
 557                 __btf_verifier_log(log, " ");
 558                 va_start(args, fmt);
 559                 bpf_verifier_vlog(log, fmt, args);
 560                 va_end(args);
 561         }
 562
 563         __btf_verifier_log(log, "\n");
 564 }
 565
 566 static void btf_verifier_log_hdr(struct btf_verifier_env *env,
 567                                  u32 btf_data_size)
 568 {
 569         struct bpf_verifier_log *log = &env->log;
 570         const struct btf *btf = env->btf;
 571         const struct btf_header *hdr;
 572
 573         if (!bpf_verifier_log_needed(log))
 574                 return;
 575
 576         hdr = &btf->hdr;
 577         __btf_verifier_log(log, "magic: 0x%x\n", hdr->magic);
 578         __btf_verifier_log(log, "version: %u\n", hdr->version);
 579         __btf_verifier_log(log, "flags: 0x%x\n", hdr->flags);
 580         __btf_verifier_log(log, "hdr_len: %u\n", hdr->hdr_len);
 581         __btf_verifier_log(log, "type_off: %u\n", hdr->type_off);
 582         __btf_verifier_log(log, "type_len: %u\n", hdr->type_len);
 583         __btf_verifier_log(log, "str_off: %u\n", hdr->str_off);
 584         __btf_verifier_log(log, "str_len: %u\n", hdr->str_len);
 585         __btf_verifier_log(log, "btf_total_size: %u\n", btf_data_size);
 586 }
 587
 588 static int btf_add_type(struct btf_verifier_env *env, struct btf_type *t)
 589 {
 590         struct btf *btf = env->btf;
 591
 592         /* < 2 because +1 for btf_void which is always in btf->types[0].
 593          * btf_void is not accounted in btf->nr_types because btf_void
 594          * does not come from the BTF file.
 595          */
 596         if (btf->types_size - btf->nr_types < 2) {
 597                 /* Expand 'types' array */
 598
 599                 struct btf_type **new_types;
 600                 u32 expand_by, new_size;
 601
 602                 if (btf->types_size == BTF_MAX_TYPE) {
 603                         btf_verifier_log(env, "Exceeded max num of types");
 604                         return -E2BIG;
 605                 }
 606
 607                 expand_by = max_t(u32, btf->types_size >> 2, 16);
 608                 new_size = min_t(u32, BTF_MAX_TYPE,
 609                                  btf->types_size + expand_by);
 610
 611                 new_types = kvcalloc(new_size, sizeof(*new_types),
 612                                      GFP_KERNEL | __GFP_NOWARN);
 613                 if (!new_types)
 614                         return -ENOMEM;
 615
 616                 if (btf->nr_types == 0)
 617                         new_types[0] = &btf_void;
 618                 else
 619                         memcpy(new_types, btf->types,
 620                                sizeof(*btf->types) * (btf->nr_types + 1));
 621
 622                 kvfree(btf->types);
 623                 btf->types = new_types;
 624                 btf->types_size = new_size;
 625         }
 626
 627         btf->types[++(btf->nr_types)] = t;
 628
 629         return 0;
 630 }
 631
 632 static int btf_alloc_id(struct btf *btf)
 633 {
 634         int id;
 635
 636         idr_preload(GFP_KERNEL);
 637         spin_lock_bh(&btf_idr_lock);
 638         id = idr_alloc_cyclic(&btf_idr, btf, 1, INT_MAX, GFP_ATOMIC);
 639         if (id > 0)
 640                 btf->id = id;
 641         spin_unlock_bh(&btf_idr_lock);
 642         idr_preload_end();
 643
 644         if (WARN_ON_ONCE(!id))
 645                 return -ENOSPC;
 646
 647         return id > 0 ? 0 : id;
 648 }
 649
 650 static void btf_free_id(struct btf *btf)
 651 {
 652         unsigned long flags;
 653
 654         /*
 655          * In map-in-map, calling map_delete_elem() on outer
 656          * map will call bpf_map_put on the inner map.
 657          * It will then eventually call btf_free_id()
 658          * on the inner map.  Some of the map_delete_elem()
 659          * implementation may have irq disabled, so
 660          * we need to use the _irqsave() version instead
 661          * of the _bh() version.
 662          */
 663         spin_lock_irqsave(&btf_idr_lock, flags);
 664         idr_remove(&btf_idr, btf->id);
 665         spin_unlock_irqrestore(&btf_idr_lock, flags);
 666 }
 667
 668 static void btf_free(struct btf *btf)
 669 {
 670         kvfree(btf->types);
 671         kvfree(btf->resolved_sizes);
 672         kvfree(btf->resolved_ids);
 673         kvfree(btf->data);
 674         kfree(btf);
 675 }
 676
 677 static void btf_free_rcu(struct rcu_head *rcu)
 678 {
 679         struct btf *btf = container_of(rcu, struct btf, rcu);
 680
 681         btf_free(btf);
 682 }
 683
 684 void btf_put(struct btf *btf)
 685 {
 686         if (btf && refcount_dec_and_test(&btf->refcnt)) {
 687                 btf_free_id(btf);
 688                 call_rcu(&btf->rcu, btf_free_rcu);
 689         }
 690 }
 691
 692 static int env_resolve_init(struct btf_verifier_env *env)
 693 {
 694         struct btf *btf = env->btf;
 695         u32 nr_types = btf->nr_types;
 696         u32 *resolved_sizes = NULL;
 697         u32 *resolved_ids = NULL;
 698         u8 *visit_states = NULL;
 699
 700         /* +1 for btf_void */
 701         resolved_sizes = kvcalloc(nr_types + 1, sizeof(*resolved_sizes),
 702                                   GFP_KERNEL | __GFP_NOWARN);
 703         if (!resolved_sizes)
 704                 goto nomem;
 705
 706         resolved_ids = kvcalloc(nr_types + 1, sizeof(*resolved_ids),
 707                                 GFP_KERNEL | __GFP_NOWARN);
 708         if (!resolved_ids)
 709                 goto nomem;
 710
 711         visit_states = kvcalloc(nr_types + 1, sizeof(*visit_states),
 712                                 GFP_KERNEL | __GFP_NOWARN);
 713         if (!visit_states)
 714                 goto nomem;
 715
 716         btf->resolved_sizes = resolved_sizes;
 717         btf->resolved_ids = resolved_ids;
 718         env->visit_states = visit_states;
 719
 720         return 0;
 721
 722 nomem:
 723         kvfree(resolved_sizes);
 724         kvfree(resolved_ids);
 725         kvfree(visit_states);
 726         return -ENOMEM;
 727 }
 728
 729 static void btf_verifier_env_free(struct btf_verifier_env *env)
 730 {
 731         kvfree(env->visit_states);
 732         kfree(env);
 733 }
 734
 735 static bool env_type_is_resolve_sink(const struct btf_verifier_env *env,
 736                                      const struct btf_type *next_type)
 737 {
 738         switch (env->resolve_mode) {
 739         case RESOLVE_TBD:
 740                 /* int, enum or void is a sink */
 741                 return !btf_type_needs_resolve(next_type);
 742         case RESOLVE_PTR:
 743                 /* int, enum, void, struct or array is a sink for ptr */
 744                 return !btf_type_is_modifier(next_type) &&
 745                         !btf_type_is_ptr(next_type);
 746         case RESOLVE_STRUCT_OR_ARRAY:
 747                 /* int, enum, void or ptr is a sink for struct and array */
 748                 return !btf_type_is_modifier(next_type) &&
 749                         !btf_type_is_array(next_type) &&
 750                         !btf_type_is_struct(next_type);
 751         default:
 752                 BUG();
 753         }
 754 }
 755
 756 static bool env_type_is_resolved(const struct btf_verifier_env *env,
 757                                  u32 type_id)
 758 {
 759         return env->visit_states[type_id] == RESOLVED;
 760 }
 761
 762 static int env_stack_push(struct btf_verifier_env *env,
 763                           const struct btf_type *t, u32 type_id)
 764 {
 765         struct resolve_vertex *v;
 766
 767         if (env->top_stack == MAX_RESOLVE_DEPTH)
 768                 return -E2BIG;
 769
 770         if (env->visit_states[type_id] != NOT_VISITED)
 771                 return -EEXIST;
 772
 773         env->visit_states[type_id] = VISITED;
 774
 775         v = &env->stack[env->top_stack++];
 776         v->t = t;
 777         v->type_id = type_id;
 778         v->next_member = 0;
 779
 780         if (env->resolve_mode == RESOLVE_TBD) {
 781                 if (btf_type_is_ptr(t))
 782                         env->resolve_mode = RESOLVE_PTR;
 783                 else if (btf_type_is_struct(t) || btf_type_is_array(t))
 784                         env->resolve_mode = RESOLVE_STRUCT_OR_ARRAY;
 785         }
 786
 787         return 0;
 788 }
 789
 790 static void env_stack_set_next_member(struct btf_verifier_env *env,
 791                                       u16 next_member)
 792 {
 793         env->stack[env->top_stack - 1].next_member = next_member;
 794 }
 795
 796 static void env_stack_pop_resolved(struct btf_verifier_env *env,
 797                                    u32 resolved_type_id,
 798                                    u32 resolved_size)
 799 {
 800         u32 type_id = env->stack[--(env->top_stack)].type_id;
 801         struct btf *btf = env->btf;
 802
 803         btf->resolved_sizes[type_id] = resolved_size;
 804         btf->resolved_ids[type_id] = resolved_type_id;
 805         env->visit_states[type_id] = RESOLVED;
 806 }
 807
 808 static const struct resolve_vertex *env_stack_peak(struct btf_verifier_env *env)
 809 {
 810         return env->top_stack ? &env->stack[env->top_stack - 1] : NULL;
 811 }
 812
 813 /* The input param "type_id" must point to a needs_resolve type */
 814 static const struct btf_type *btf_type_id_resolve(const struct btf *btf,
 815                                                   u32 *type_id)
 816 {
 817         *type_id = btf->resolved_ids[*type_id];
 818         return btf_type_by_id(btf, *type_id);
 819 }
 820
 821 const struct btf_type *btf_type_id_size(const struct btf *btf,
 822                                         u32 *type_id, u32 *ret_size)
 823 {
 824         const struct btf_type *size_type;
 825         u32 size_type_id = *type_id;
 826         u32 size = 0;
 827
 828         size_type = btf_type_by_id(btf, size_type_id);
 829         if (btf_type_is_void_or_null(size_type))
 830                 return NULL;
 831
 832         if (btf_type_has_size(size_type)) {
 833                 size = size_type->size;
 834         } else if (btf_type_is_array(size_type)) {
 835                 size = btf->resolved_sizes[size_type_id];
 836         } else if (btf_type_is_ptr(size_type)) {
 837                 size = sizeof(void *);
 838         } else {
 839                 if (WARN_ON_ONCE(!btf_type_is_modifier(size_type)))
 840                         return NULL;
 841
 842                 size = btf->resolved_sizes[size_type_id];
 843                 size_type_id = btf->resolved_ids[size_type_id];
 844                 size_type = btf_type_by_id(btf, size_type_id);
 845                 if (btf_type_is_void(size_type))
 846                         return NULL;
 847         }
 848
 849         *type_id = size_type_id;
 850         if (ret_size)
 851                 *ret_size = size;
 852
 853         return size_type;
 854 }
 855
 856 static int btf_df_check_member(struct btf_verifier_env *env,
 857                                const struct btf_type *struct_type,
 858                                const struct btf_member *member,
 859                                const struct btf_type *member_type)
 860 {
 861         btf_verifier_log_basic(env, struct_type,
 862                                "Unsupported check_member");
 863         return -EINVAL;
 864 }
 865
 866 static int btf_df_resolve(struct btf_verifier_env *env,
 867                           const struct resolve_vertex *v)
 868 {
 869         btf_verifier_log_basic(env, v->t, "Unsupported resolve");
 870         return -EINVAL;
 871 }
 872
 873 static void btf_df_seq_show(const struct btf *btf, const struct btf_type *t,
 874                             u32 type_id, void *data, u8 bits_offsets,
 875                             struct seq_file *m)
 876 {
 877         seq_printf(m, "<unsupported kind:%u>", BTF_INFO_KIND(t->info));
 878 }
 879
 880 static int btf_int_check_member(struct btf_verifier_env *env,
 881                                 const struct btf_type *struct_type,
 882                                 const struct btf_member *member,
 883                                 const struct btf_type *member_type)
 884 {
 885         u32 int_data = btf_type_int(member_type);
 886         u32 struct_bits_off = member->offset;
 887         u32 struct_size = struct_type->size;
 888         u32 nr_copy_bits;
 889         u32 bytes_offset;
 890
 891         if (U32_MAX - struct_bits_off < BTF_INT_OFFSET(int_data)) {
 892                 btf_verifier_log_member(env, struct_type, member,
 893                                         "bits_offset exceeds U32_MAX");
 894                 return -EINVAL;
 895         }
 896
 897         struct_bits_off += BTF_INT_OFFSET(int_data);
 898         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
 899         nr_copy_bits = BTF_INT_BITS(int_data) +
 900                 BITS_PER_BYTE_MASKED(struct_bits_off);
 901
 902         if (nr_copy_bits > BITS_PER_U64) {
 903                 btf_verifier_log_member(env, struct_type, member,
 904                                         "nr_copy_bits exceeds 64");
 905                 return -EINVAL;
 906         }
 907
 908         if (struct_size < bytes_offset ||
 909             struct_size - bytes_offset < BITS_ROUNDUP_BYTES(nr_copy_bits)) {
 910                 btf_verifier_log_member(env, struct_type, member,
 911                                         "Member exceeds struct_size");
 912                 return -EINVAL;
 913         }
 914
 915         return 0;
 916 }
 917
 918 static s32 btf_int_check_meta(struct btf_verifier_env *env,
 919                               const struct btf_type *t,
 920                               u32 meta_left)
 921 {
 922         u32 int_data, nr_bits, meta_needed = sizeof(int_data);
 923         u16 encoding;
 924
 925         if (meta_left < meta_needed) {
 926                 btf_verifier_log_basic(env, t,
 927                                        "meta_left:%u meta_needed:%u",
 928                                        meta_left, meta_needed);
 929                 return -EINVAL;
 930         }
 931
 932         if (btf_type_vlen(t)) {
 933                 btf_verifier_log_type(env, t, "vlen != 0");
 934                 return -EINVAL;
 935         }
 936
 937         int_data = btf_type_int(t);
 938         if (int_data & ~BTF_INT_MASK) {
 939                 btf_verifier_log_basic(env, t, "Invalid int_data:%x",
 940                                        int_data);
 941                 return -EINVAL;
 942         }
 943
 944         nr_bits = BTF_INT_BITS(int_data) + BTF_INT_OFFSET(int_data);
 945
 946         if (nr_bits > BITS_PER_U64) {
 947                 btf_verifier_log_type(env, t, "nr_bits exceeds %zu",
 948                                       BITS_PER_U64);
 949                 return -EINVAL;
 950         }
 951
 952         if (BITS_ROUNDUP_BYTES(nr_bits) > t->size) {
 953                 btf_verifier_log_type(env, t, "nr_bits exceeds type_size");
 954                 return -EINVAL;
 955         }
 956
 957         /*
 958          * Only one of the encoding bits is allowed and it
 959          * should be sufficient for the pretty print purpose (i.e. decoding).
 960          * Multiple bits can be allowed later if it is found
 961          * to be insufficient.
 962          */
 963         encoding = BTF_INT_ENCODING(int_data);
 964         if (encoding &&
 965             encoding != BTF_INT_SIGNED &&
 966             encoding != BTF_INT_CHAR &&
 967             encoding != BTF_INT_BOOL) {
 968                 btf_verifier_log_type(env, t, "Unsupported encoding");
 969                 return -ENOTSUPP;
 970         }
 971
 972         btf_verifier_log_type(env, t, NULL);
 973
 974         return meta_needed;
 975 }
 976
 977 static void btf_int_log(struct btf_verifier_env *env,
 978                         const struct btf_type *t)
 979 {
 980         int int_data = btf_type_int(t);
 981
 982         btf_verifier_log(env,
 983                          "size=%u bits_offset=%u nr_bits=%u encoding=%s",
 984                          t->size, BTF_INT_OFFSET(int_data),
 985                          BTF_INT_BITS(int_data),
 986                          btf_int_encoding_str(BTF_INT_ENCODING(int_data)));
 987 }
 988
 989 static void btf_int_bits_seq_show(const struct btf *btf,
 990                                   const struct btf_type *t,
 991                                   void *data, u8 bits_offset,
 992                                   struct seq_file *m)
 993 {
 994         u16 left_shift_bits, right_shift_bits;
 995         u32 int_data = btf_type_int(t);
 996         u16 nr_bits = BTF_INT_BITS(int_data);
 997         u16 total_bits_offset;
 998         u16 nr_copy_bytes;
 999         u16 nr_copy_bits;
1000         u64 print_num;
1001
1002         total_bits_offset = bits_offset + BTF_INT_OFFSET(int_data);
1003         data += BITS_ROUNDDOWN_BYTES(total_bits_offset);
1004         bits_offset = BITS_PER_BYTE_MASKED(total_bits_offset);
1005         nr_copy_bits = nr_bits + bits_offset;
1006         nr_copy_bytes = BITS_ROUNDUP_BYTES(nr_copy_bits);
1007
1008         print_num = 0;
1009         memcpy(&print_num, data, nr_copy_bytes);
1010
1011 #ifdef __BIG_ENDIAN_BITFIELD
1012         left_shift_bits = bits_offset;
1013 #else
1014         left_shift_bits = BITS_PER_U64 - nr_copy_bits;
1015 #endif
1016         right_shift_bits = BITS_PER_U64 - nr_bits;
1017
1018         print_num <<= left_shift_bits;
1019         print_num >>= right_shift_bits;
1020
1021         seq_printf(m, "0x%llx", print_num);
1022 }
1023
1024 static void btf_int_seq_show(const struct btf *btf, const struct btf_type *t,
1025                              u32 type_id, void *data, u8 bits_offset,
1026                              struct seq_file *m)
1027 {
1028         u32 int_data = btf_type_int(t);
1029         u8 encoding = BTF_INT_ENCODING(int_data);
1030         bool sign = encoding & BTF_INT_SIGNED;
1031         u32 nr_bits = BTF_INT_BITS(int_data);
1032
1033         if (bits_offset || BTF_INT_OFFSET(int_data) ||
1034             BITS_PER_BYTE_MASKED(nr_bits)) {
1035                 btf_int_bits_seq_show(btf, t, data, bits_offset, m);
1036                 return;
1037         }
1038
1039         switch (nr_bits) {
1040         case 64:
1041                 if (sign)
1042                         seq_printf(m, "%lld", *(s64 *)data);
1043                 else
1044                         seq_printf(m, "%llu", *(u64 *)data);
1045                 break;
1046         case 32:
1047                 if (sign)
1048                         seq_printf(m, "%d", *(s32 *)data);
1049                 else
1050                         seq_printf(m, "%u", *(u32 *)data);
1051                 break;
1052         case 16:
1053                 if (sign)
1054                         seq_printf(m, "%d", *(s16 *)data);
1055                 else
1056                         seq_printf(m, "%u", *(u16 *)data);
1057                 break;
1058         case 8:
1059                 if (sign)
1060                         seq_printf(m, "%d", *(s8 *)data);
1061                 else
1062                         seq_printf(m, "%u", *(u8 *)data);
1063                 break;
1064         default:
1065                 btf_int_bits_seq_show(btf, t, data, bits_offset, m);
1066         }
1067 }
1068
1069 static const struct btf_kind_operations int_ops = {
1070         .check_meta = btf_int_check_meta,
1071         .resolve = btf_df_resolve,
1072         .check_member = btf_int_check_member,
1073         .log_details = btf_int_log,
1074         .seq_show = btf_int_seq_show,
1075 };
1076
1077 static int btf_modifier_check_member(struct btf_verifier_env *env,
1078                                      const struct btf_type *struct_type,
1079                                      const struct btf_member *member,
1080                                      const struct btf_type *member_type)
1081 {
1082         const struct btf_type *resolved_type;
1083         u32 resolved_type_id = member->type;
1084         struct btf_member resolved_member;
1085         struct btf *btf = env->btf;
1086
1087         resolved_type = btf_type_id_size(btf, &resolved_type_id, NULL);
1088         if (!resolved_type) {
1089                 btf_verifier_log_member(env, struct_type, member,
1090                                         "Invalid member");
1091                 return -EINVAL;
1092         }
1093
1094         resolved_member = *member;
1095         resolved_member.type = resolved_type_id;
1096
1097         return btf_type_ops(resolved_type)->check_member(env, struct_type,
1098                                                          &resolved_member,
1099                                                          resolved_type);
1100 }
1101
1102 static int btf_ptr_check_member(struct btf_verifier_env *env,
1103                                 const struct btf_type *struct_type,
1104                                 const struct btf_member *member,
1105                                 const struct btf_type *member_type)
1106 {
1107         u32 struct_size, struct_bits_off, bytes_offset;
1108
1109         struct_size = struct_type->size;
1110         struct_bits_off = member->offset;
1111         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1112
1113         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1114                 btf_verifier_log_member(env, struct_type, member,
1115                                         "Member is not byte aligned");
1116                 return -EINVAL;
1117         }
1118
1119         if (struct_size - bytes_offset < sizeof(void *)) {
1120                 btf_verifier_log_member(env, struct_type, member,
1121                                         "Member exceeds struct_size");
1122                 return -EINVAL;
1123         }
1124
1125         return 0;
1126 }
1127
1128 static int btf_ref_type_check_meta(struct btf_verifier_env *env,
1129                                    const struct btf_type *t,
1130                                    u32 meta_left)
1131 {
1132         if (btf_type_vlen(t)) {
1133                 btf_verifier_log_type(env, t, "vlen != 0");
1134                 return -EINVAL;
1135         }
1136
1137         if (!BTF_TYPE_ID_VALID(t->type)) {
1138                 btf_verifier_log_type(env, t, "Invalid type_id");
1139                 return -EINVAL;
1140         }
1141
1142         btf_verifier_log_type(env, t, NULL);
1143
1144         return 0;
1145 }
1146
1147 static int btf_modifier_resolve(struct btf_verifier_env *env,
1148                                 const struct resolve_vertex *v)
1149 {
1150         const struct btf_type *t = v->t;
1151         const struct btf_type *next_type;
1152         u32 next_type_id = t->type;
1153         struct btf *btf = env->btf;
1154         u32 next_type_size = 0;
1155
1156         next_type = btf_type_by_id(btf, next_type_id);
1157         if (!next_type) {
1158                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1159                 return -EINVAL;
1160         }
1161
1162         /* "typedef void new_void", "const void"...etc */
1163         if (btf_type_is_void(next_type))
1164                 goto resolved;
1165
1166         if (!env_type_is_resolve_sink(env, next_type) &&
1167             !env_type_is_resolved(env, next_type_id))
1168                 return env_stack_push(env, next_type, next_type_id);
1169
1170         /* Figure out the resolved next_type_id with size.
1171          * They will be stored in the current modifier's
1172          * resolved_ids and resolved_sizes such that it can
1173          * save us a few type-following when we use it later (e.g. in
1174          * pretty print).
1175          */
1176         if (!btf_type_id_size(btf, &next_type_id, &next_type_size) &&
1177             !btf_type_is_void(btf_type_id_resolve(btf, &next_type_id))) {
1178                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1179                 return -EINVAL;
1180         }
1181
1182 resolved:
1183         env_stack_pop_resolved(env, next_type_id, next_type_size);
1184
1185         return 0;
1186 }
1187
1188 static int btf_ptr_resolve(struct btf_verifier_env *env,
1189                            const struct resolve_vertex *v)
1190 {
1191         const struct btf_type *next_type;
1192         const struct btf_type *t = v->t;
1193         u32 next_type_id = t->type;
1194         struct btf *btf = env->btf;
1195         u32 next_type_size = 0;
1196
1197         next_type = btf_type_by_id(btf, next_type_id);
1198         if (!next_type) {
1199                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1200                 return -EINVAL;
1201         }
1202
1203         /* "void *" */
1204         if (btf_type_is_void(next_type))
1205                 goto resolved;
1206
1207         if (!env_type_is_resolve_sink(env, next_type) &&
1208             !env_type_is_resolved(env, next_type_id))
1209                 return env_stack_push(env, next_type, next_type_id);
1210
1211         /* If the modifier was RESOLVED during RESOLVE_STRUCT_OR_ARRAY,
1212          * the modifier may have stopped resolving when it was resolved
1213          * to a ptr (last-resolved-ptr).
1214          *
1215          * We now need to continue from the last-resolved-ptr to
1216          * ensure the last-resolved-ptr will not referring back to
1217          * the currenct ptr (t).
1218          */
1219         if (btf_type_is_modifier(next_type)) {
1220                 const struct btf_type *resolved_type;
1221                 u32 resolved_type_id;
1222
1223                 resolved_type_id = next_type_id;
1224                 resolved_type = btf_type_id_resolve(btf, &resolved_type_id);
1225
1226                 if (btf_type_is_ptr(resolved_type) &&
1227                     !env_type_is_resolve_sink(env, resolved_type) &&
1228                     !env_type_is_resolved(env, resolved_type_id))
1229                         return env_stack_push(env, resolved_type,
1230                                               resolved_type_id);
1231         }
1232
1233         if (!btf_type_id_size(btf, &next_type_id, &next_type_size) &&
1234             !btf_type_is_void(btf_type_id_resolve(btf, &next_type_id))) {
1235                 btf_verifier_log_type(env, v->t, "Invalid type_id");
1236                 return -EINVAL;
1237         }
1238
1239 resolved:
1240         env_stack_pop_resolved(env, next_type_id, 0);
1241
1242         return 0;
1243 }
1244
1245 static void btf_modifier_seq_show(const struct btf *btf,
1246                                   const struct btf_type *t,
1247                                   u32 type_id, void *data,
1248                                   u8 bits_offset, struct seq_file *m)
1249 {
1250         t = btf_type_id_resolve(btf, &type_id);
1251
1252         btf_type_ops(t)->seq_show(btf, t, type_id, data, bits_offset, m);
1253 }
1254
1255 static void btf_ptr_seq_show(const struct btf *btf, const struct btf_type *t,
1256                              u32 type_id, void *data, u8 bits_offset,
1257                              struct seq_file *m)
1258 {
1259         /* It is a hashed value */
1260         seq_printf(m, "%p", *(void **)data);
1261 }
1262
1263 static void btf_ref_type_log(struct btf_verifier_env *env,
1264                              const struct btf_type *t)
1265 {
1266         btf_verifier_log(env, "type_id=%u", t->type);
1267 }
1268
1269 static struct btf_kind_operations modifier_ops = {
1270         .check_meta = btf_ref_type_check_meta,
1271         .resolve = btf_modifier_resolve,
1272         .check_member = btf_modifier_check_member,
1273         .log_details = btf_ref_type_log,
1274         .seq_show = btf_modifier_seq_show,
1275 };
1276
1277 static struct btf_kind_operations ptr_ops = {
1278         .check_meta = btf_ref_type_check_meta,
1279         .resolve = btf_ptr_resolve,
1280         .check_member = btf_ptr_check_member,
1281         .log_details = btf_ref_type_log,
1282         .seq_show = btf_ptr_seq_show,
1283 };
1284
1285 static s32 btf_fwd_check_meta(struct btf_verifier_env *env,
1286                               const struct btf_type *t,
1287                               u32 meta_left)
1288 {
1289         if (btf_type_vlen(t)) {
1290                 btf_verifier_log_type(env, t, "vlen != 0");
1291                 return -EINVAL;
1292         }
1293
1294         if (t->type) {
1295                 btf_verifier_log_type(env, t, "type != 0");
1296                 return -EINVAL;
1297         }
1298
1299         btf_verifier_log_type(env, t, NULL);
1300
1301         return 0;
1302 }
1303
1304 static struct btf_kind_operations fwd_ops = {
1305         .check_meta = btf_fwd_check_meta,
1306         .resolve = btf_df_resolve,
1307         .check_member = btf_df_check_member,
1308         .log_details = btf_ref_type_log,
1309         .seq_show = btf_df_seq_show,
1310 };
1311
1312 static int btf_array_check_member(struct btf_verifier_env *env,
1313                                   const struct btf_type *struct_type,
1314                                   const struct btf_member *member,
1315                                   const struct btf_type *member_type)
1316 {
1317         u32 struct_bits_off = member->offset;
1318         u32 struct_size, bytes_offset;
1319         u32 array_type_id, array_size;
1320         struct btf *btf = env->btf;
1321
1322         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1323                 btf_verifier_log_member(env, struct_type, member,
1324                                         "Member is not byte aligned");
1325                 return -EINVAL;
1326         }
1327
1328         array_type_id = member->type;
1329         btf_type_id_size(btf, &array_type_id, &array_size);
1330         struct_size = struct_type->size;
1331         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1332         if (struct_size - bytes_offset < array_size) {
1333                 btf_verifier_log_member(env, struct_type, member,
1334                                         "Member exceeds struct_size");
1335                 return -EINVAL;
1336         }
1337
1338         return 0;
1339 }
1340
1341 static s32 btf_array_check_meta(struct btf_verifier_env *env,
1342                                 const struct btf_type *t,
1343                                 u32 meta_left)
1344 {
1345         const struct btf_array *array = btf_type_array(t);
1346         u32 meta_needed = sizeof(*array);
1347
1348         if (meta_left < meta_needed) {
1349                 btf_verifier_log_basic(env, t,
1350                                        "meta_left:%u meta_needed:%u",
1351                                        meta_left, meta_needed);
1352                 return -EINVAL;
1353         }
1354
1355         if (btf_type_vlen(t)) {
1356                 btf_verifier_log_type(env, t, "vlen != 0");
1357                 return -EINVAL;
1358         }
1359
1360         if (t->size) {
1361                 btf_verifier_log_type(env, t, "size != 0");
1362                 return -EINVAL;
1363         }
1364
1365         /* Array elem type and index type cannot be in type void,
1366          * so !array->type and !array->index_type are not allowed.
1367          */
1368         if (!array->type || !BTF_TYPE_ID_VALID(array->type)) {
1369                 btf_verifier_log_type(env, t, "Invalid elem");
1370                 return -EINVAL;
1371         }
1372
1373         if (!array->index_type || !BTF_TYPE_ID_VALID(array->index_type)) {
1374                 btf_verifier_log_type(env, t, "Invalid index");
1375                 return -EINVAL;
1376         }
1377
1378         btf_verifier_log_type(env, t, NULL);
1379
1380         return meta_needed;
1381 }
1382
1383 static int btf_array_resolve(struct btf_verifier_env *env,
1384                              const struct resolve_vertex *v)
1385 {
1386         const struct btf_array *array = btf_type_array(v->t);
1387         const struct btf_type *elem_type, *index_type;
1388         u32 elem_type_id, index_type_id;
1389         struct btf *btf = env->btf;
1390         u32 elem_size;
1391
1392         /* Check array->index_type */
1393         index_type_id = array->index_type;
1394         index_type = btf_type_by_id(btf, index_type_id);
1395         if (btf_type_is_void_or_null(index_type)) {
1396                 btf_verifier_log_type(env, v->t, "Invalid index");
1397                 return -EINVAL;
1398         }
1399
1400         if (!env_type_is_resolve_sink(env, index_type) &&
1401             !env_type_is_resolved(env, index_type_id))
1402                 return env_stack_push(env, index_type, index_type_id);
1403
1404         index_type = btf_type_id_size(btf, &index_type_id, NULL);
1405         if (!index_type || !btf_type_is_int(index_type) ||
1406             !btf_type_int_is_regular(index_type)) {
1407                 btf_verifier_log_type(env, v->t, "Invalid index");
1408                 return -EINVAL;
1409         }
1410
1411         /* Check array->type */
1412         elem_type_id = array->type;
1413         elem_type = btf_type_by_id(btf, elem_type_id);
1414         if (btf_type_is_void_or_null(elem_type)) {
1415                 btf_verifier_log_type(env, v->t,
1416                                       "Invalid elem");
1417                 return -EINVAL;
1418         }
1419
1420         if (!env_type_is_resolve_sink(env, elem_type) &&
1421             !env_type_is_resolved(env, elem_type_id))
1422                 return env_stack_push(env, elem_type, elem_type_id);
1423
1424         elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
1425         if (!elem_type) {
1426                 btf_verifier_log_type(env, v->t, "Invalid elem");
1427                 return -EINVAL;
1428         }
1429
1430         if (btf_type_is_int(elem_type) && !btf_type_int_is_regular(elem_type)) {
1431                 btf_verifier_log_type(env, v->t, "Invalid array of int");
1432                 return -EINVAL;
1433         }
1434
1435         if (array->nelems && elem_size > U32_MAX / array->nelems) {
1436                 btf_verifier_log_type(env, v->t,
1437                                       "Array size overflows U32_MAX");
1438                 return -EINVAL;
1439         }
1440
1441         env_stack_pop_resolved(env, elem_type_id, elem_size * array->nelems);
1442
1443         return 0;
1444 }
1445
1446 static void btf_array_log(struct btf_verifier_env *env,
1447                           const struct btf_type *t)
1448 {
1449         const struct btf_array *array = btf_type_array(t);
1450
1451         btf_verifier_log(env, "type_id=%u index_type_id=%u nr_elems=%u",
1452                          array->type, array->index_type, array->nelems);
1453 }
1454
1455 static void btf_array_seq_show(const struct btf *btf, const struct btf_type *t,
1456                                u32 type_id, void *data, u8 bits_offset,
1457                                struct seq_file *m)
1458 {
1459         const struct btf_array *array = btf_type_array(t);
1460         const struct btf_kind_operations *elem_ops;
1461         const struct btf_type *elem_type;
1462         u32 i, elem_size, elem_type_id;
1463
1464         elem_type_id = array->type;
1465         elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
1466         elem_ops = btf_type_ops(elem_type);
1467         seq_puts(m, "[");
1468         for (i = 0; i < array->nelems; i++) {
1469                 if (i)
1470                         seq_puts(m, ",");
1471
1472                 elem_ops->seq_show(btf, elem_type, elem_type_id, data,
1473                                    bits_offset, m);
1474                 data += elem_size;
1475         }
1476         seq_puts(m, "]");
1477 }
1478
1479 static struct btf_kind_operations array_ops = {
1480         .check_meta = btf_array_check_meta,
1481         .resolve = btf_array_resolve,
1482         .check_member = btf_array_check_member,
1483         .log_details = btf_array_log,
1484         .seq_show = btf_array_seq_show,
1485 };
1486
1487 static int btf_struct_check_member(struct btf_verifier_env *env,
1488                                    const struct btf_type *struct_type,
1489                                    const struct btf_member *member,
1490                                    const struct btf_type *member_type)
1491 {
1492         u32 struct_bits_off = member->offset;
1493         u32 struct_size, bytes_offset;
1494
1495         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1496                 btf_verifier_log_member(env, struct_type, member,
1497                                         "Member is not byte aligned");
1498                 return -EINVAL;
1499         }
1500
1501         struct_size = struct_type->size;
1502         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1503         if (struct_size - bytes_offset < member_type->size) {
1504                 btf_verifier_log_member(env, struct_type, member,
1505                                         "Member exceeds struct_size");
1506                 return -EINVAL;
1507         }
1508
1509         return 0;
1510 }
1511
1512 static s32 btf_struct_check_meta(struct btf_verifier_env *env,
1513                                  const struct btf_type *t,
1514                                  u32 meta_left)
1515 {
1516         bool is_union = BTF_INFO_KIND(t->info) == BTF_KIND_UNION;
1517         const struct btf_member *member;
1518         struct btf *btf = env->btf;
1519         u32 struct_size = t->size;
1520         u32 meta_needed;
1521         u16 i;
1522
1523         meta_needed = btf_type_vlen(t) * sizeof(*member);
1524         if (meta_left < meta_needed) {
1525                 btf_verifier_log_basic(env, t,
1526                                        "meta_left:%u meta_needed:%u",
1527                                        meta_left, meta_needed);
1528                 return -EINVAL;
1529         }
1530
1531         btf_verifier_log_type(env, t, NULL);
1532
1533         for_each_member(i, t, member) {
1534                 if (!btf_name_offset_valid(btf, member->name_off)) {
1535                         btf_verifier_log_member(env, t, member,
1536                                                 "Invalid member name_offset:%u",
1537                                                 member->name_off);
1538                         return -EINVAL;
1539                 }
1540
1541                 /* A member cannot be in type void */
1542                 if (!member->type || !BTF_TYPE_ID_VALID(member->type)) {
1543                         btf_verifier_log_member(env, t, member,
1544                                                 "Invalid type_id");
1545                         return -EINVAL;
1546                 }
1547
1548                 if (is_union && member->offset) {
1549                         btf_verifier_log_member(env, t, member,
1550                                                 "Invalid member bits_offset");
1551                         return -EINVAL;
1552                 }
1553
1554                 if (BITS_ROUNDUP_BYTES(member->offset) > struct_size) {
1555                         btf_verifier_log_member(env, t, member,
1556                                                 "Memmber bits_offset exceeds its struct size");
1557                         return -EINVAL;
1558                 }
1559
1560                 btf_verifier_log_member(env, t, member, NULL);
1561         }
1562
1563         return meta_needed;
1564 }
1565
1566 static int btf_struct_resolve(struct btf_verifier_env *env,
1567                               const struct resolve_vertex *v)
1568 {
1569         const struct btf_member *member;
1570         int err;
1571         u16 i;
1572
1573         /* Before continue resolving the next_member,
1574          * ensure the last member is indeed resolved to a
1575          * type with size info.
1576          */
1577         if (v->next_member) {
1578                 const struct btf_type *last_member_type;
1579                 const struct btf_member *last_member;
1580                 u16 last_member_type_id;
1581
1582                 last_member = btf_type_member(v->t) + v->next_member - 1;
1583                 last_member_type_id = last_member->type;
1584                 if (WARN_ON_ONCE(!env_type_is_resolved(env,
1585                                                        last_member_type_id)))
1586                         return -EINVAL;
1587
1588                 last_member_type = btf_type_by_id(env->btf,
1589                                                   last_member_type_id);
1590                 err = btf_type_ops(last_member_type)->check_member(env, v->t,
1591                                                         last_member,
1592                                                         last_member_type);
1593                 if (err)
1594                         return err;
1595         }
1596
1597         for_each_member_from(i, v->next_member, v->t, member) {
1598                 u32 member_type_id = member->type;
1599                 const struct btf_type *member_type = btf_type_by_id(env->btf,
1600                                                                 member_type_id);
1601
1602                 if (btf_type_is_void_or_null(member_type)) {
1603                         btf_verifier_log_member(env, v->t, member,
1604                                                 "Invalid member");
1605                         return -EINVAL;
1606                 }
1607
1608                 if (!env_type_is_resolve_sink(env, member_type) &&
1609                     !env_type_is_resolved(env, member_type_id)) {
1610                         env_stack_set_next_member(env, i + 1);
1611                         return env_stack_push(env, member_type, member_type_id);
1612                 }
1613
1614                 err = btf_type_ops(member_type)->check_member(env, v->t,
1615                                                               member,
1616                                                               member_type);
1617                 if (err)
1618                         return err;
1619         }
1620
1621         env_stack_pop_resolved(env, 0, 0);
1622
1623         return 0;
1624 }
1625
1626 static void btf_struct_log(struct btf_verifier_env *env,
1627                            const struct btf_type *t)
1628 {
1629         btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
1630 }
1631
1632 static void btf_struct_seq_show(const struct btf *btf, const struct btf_type *t,
1633                                 u32 type_id, void *data, u8 bits_offset,
1634                                 struct seq_file *m)
1635 {
1636         const char *seq = BTF_INFO_KIND(t->info) == BTF_KIND_UNION ? "|" : ",";
1637         const struct btf_member *member;
1638         u32 i;
1639
1640         seq_puts(m, "{");
1641         for_each_member(i, t, member) {
1642                 const struct btf_type *member_type = btf_type_by_id(btf,
1643                                                                 member->type);
1644                 u32 member_offset = member->offset;
1645                 u32 bytes_offset = BITS_ROUNDDOWN_BYTES(member_offset);
1646                 u8 bits8_offset = BITS_PER_BYTE_MASKED(member_offset);
1647                 const struct btf_kind_operations *ops;
1648
1649                 if (i)
1650                         seq_puts(m, seq);
1651
1652                 ops = btf_type_ops(member_type);
1653                 ops->seq_show(btf, member_type, member->type,
1654                               data + bytes_offset, bits8_offset, m);
1655         }
1656         seq_puts(m, "}");
1657 }
1658
1659 static struct btf_kind_operations struct_ops = {
1660         .check_meta = btf_struct_check_meta,
1661         .resolve = btf_struct_resolve,
1662         .check_member = btf_struct_check_member,
1663         .log_details = btf_struct_log,
1664         .seq_show = btf_struct_seq_show,
1665 };
1666
1667 static int btf_enum_check_member(struct btf_verifier_env *env,
1668                                  const struct btf_type *struct_type,
1669                                  const struct btf_member *member,
1670                                  const struct btf_type *member_type)
1671 {
1672         u32 struct_bits_off = member->offset;
1673         u32 struct_size, bytes_offset;
1674
1675         if (BITS_PER_BYTE_MASKED(struct_bits_off)) {
1676                 btf_verifier_log_member(env, struct_type, member,
1677                                         "Member is not byte aligned");
1678                 return -EINVAL;
1679         }
1680
1681         struct_size = struct_type->size;
1682         bytes_offset = BITS_ROUNDDOWN_BYTES(struct_bits_off);
1683         if (struct_size - bytes_offset < sizeof(int)) {
1684                 btf_verifier_log_member(env, struct_type, member,
1685                                         "Member exceeds struct_size");
1686                 return -EINVAL;
1687         }
1688
1689         return 0;
1690 }
1691
1692 static s32 btf_enum_check_meta(struct btf_verifier_env *env,
1693                                const struct btf_type *t,
1694                                u32 meta_left)
1695 {
1696         const struct btf_enum *enums = btf_type_enum(t);
1697         struct btf *btf = env->btf;
1698         u16 i, nr_enums;
1699         u32 meta_needed;
1700
1701         nr_enums = btf_type_vlen(t);
1702         meta_needed = nr_enums * sizeof(*enums);
1703
1704         if (meta_left < meta_needed) {
1705                 btf_verifier_log_basic(env, t,
1706                                        "meta_left:%u meta_needed:%u",
1707                                        meta_left, meta_needed);
1708                 return -EINVAL;
1709         }
1710
1711         if (t->size != sizeof(int)) {
1712                 btf_verifier_log_type(env, t, "Expected size:%zu",
1713                                       sizeof(int));
1714                 return -EINVAL;
1715         }
1716
1717         btf_verifier_log_type(env, t, NULL);
1718
1719         for (i = 0; i < nr_enums; i++) {
1720                 if (!btf_name_offset_valid(btf, enums[i].name_off)) {
1721                         btf_verifier_log(env, "\tInvalid name_offset:%u",
1722                                          enums[i].name_off);
1723                         return -EINVAL;
1724                 }
1725
1726                 btf_verifier_log(env, "\t%s val=%d\n",
1727                                  btf_name_by_offset(btf, enums[i].name_off),
1728                                  enums[i].val);
1729         }
1730
1731         return meta_needed;
1732 }
1733
1734 static void btf_enum_log(struct btf_verifier_env *env,
1735                          const struct btf_type *t)
1736 {
1737         btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
1738 }
1739
1740 static void btf_enum_seq_show(const struct btf *btf, const struct btf_type *t,
1741                               u32 type_id, void *data, u8 bits_offset,
1742                               struct seq_file *m)
1743 {
1744         const struct btf_enum *enums = btf_type_enum(t);
1745         u32 i, nr_enums = btf_type_vlen(t);
1746         int v = *(int *)data;
1747
1748         for (i = 0; i < nr_enums; i++) {
1749                 if (v == enums[i].val) {
1750                         seq_printf(m, "%s",
1751                                    btf_name_by_offset(btf, enums[i].name_off));
1752                         return;
1753                 }
1754         }
1755
1756         seq_printf(m, "%d", v);
1757 }
1758
1759 static struct btf_kind_operations enum_ops = {
1760         .check_meta = btf_enum_check_meta,
1761         .resolve = btf_df_resolve,
1762         .check_member = btf_enum_check_member,
1763         .log_details = btf_enum_log,
1764         .seq_show = btf_enum_seq_show,
1765 };
1766
1767 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS] = {
1768         [BTF_KIND_INT] = &int_ops,
1769         [BTF_KIND_PTR] = &ptr_ops,
1770         [BTF_KIND_ARRAY] = &array_ops,
1771         [BTF_KIND_STRUCT] = &struct_ops,
1772         [BTF_KIND_UNION] = &struct_ops,
1773         [BTF_KIND_ENUM] = &enum_ops,
1774         [BTF_KIND_FWD] = &fwd_ops,
1775         [BTF_KIND_TYPEDEF] = &modifier_ops,
1776         [BTF_KIND_VOLATILE] = &modifier_ops,
1777         [BTF_KIND_CONST] = &modifier_ops,
1778         [BTF_KIND_RESTRICT] = &modifier_ops,
1779 };
1780
1781 static s32 btf_check_meta(struct btf_verifier_env *env,
1782                           const struct btf_type *t,
1783                           u32 meta_left)
1784 {
1785         u32 saved_meta_left = meta_left;
1786         s32 var_meta_size;
1787
1788         if (meta_left < sizeof(*t)) {
1789                 btf_verifier_log(env, "[%u] meta_left:%u meta_needed:%zu",
1790                                  env->log_type_id, meta_left, sizeof(*t));
1791                 return -EINVAL;
1792         }
1793         meta_left -= sizeof(*t);
1794
1795         if (t->info & ~BTF_INFO_MASK) {
1796                 btf_verifier_log(env, "[%u] Invalid btf_info:%x",
1797                                  env->log_type_id, t->info);
1798                 return -EINVAL;
1799         }
1800
1801         if (BTF_INFO_KIND(t->info) > BTF_KIND_MAX ||
1802             BTF_INFO_KIND(t->info) == BTF_KIND_UNKN) {
1803                 btf_verifier_log(env, "[%u] Invalid kind:%u",
1804                                  env->log_type_id, BTF_INFO_KIND(t->info));
1805                 return -EINVAL;
1806         }
1807
1808         if (!btf_name_offset_valid(env->btf, t->name_off)) {
1809                 btf_verifier_log(env, "[%u] Invalid name_offset:%u",
1810                                  env->log_type_id, t->name_off);
1811                 return -EINVAL;
1812         }
1813
1814         var_meta_size = btf_type_ops(t)->check_meta(env, t, meta_left);
1815         if (var_meta_size < 0)
1816                 return var_meta_size;
1817
1818         meta_left -= var_meta_size;
1819
1820         return saved_meta_left - meta_left;
1821 }
1822
1823 static int btf_check_all_metas(struct btf_verifier_env *env)
1824 {
1825         struct btf *btf = env->btf;
1826         struct btf_header *hdr;
1827         void *cur, *end;
1828
1829         hdr = &btf->hdr;
1830         cur = btf->nohdr_data + hdr->type_off;
1831         end = btf->nohdr_data + hdr->type_len;
1832
1833         env->log_type_id = 1;
1834         while (cur < end) {
1835                 struct btf_type *t = cur;
1836                 s32 meta_size;
1837
1838                 meta_size = btf_check_meta(env, t, end - cur);
1839                 if (meta_size < 0)
1840                         return meta_size;
1841
1842                 btf_add_type(env, t);
1843                 cur += meta_size;
1844                 env->log_type_id++;
1845         }
1846
1847         return 0;
1848 }
1849
1850 static int btf_resolve(struct btf_verifier_env *env,
1851                        const struct btf_type *t, u32 type_id)
1852 {
1853         const struct resolve_vertex *v;
1854         int err = 0;
1855
1856         env->resolve_mode = RESOLVE_TBD;
1857         env_stack_push(env, t, type_id);
1858         while (!err && (v = env_stack_peak(env))) {
1859                 env->log_type_id = v->type_id;
1860                 err = btf_type_ops(v->t)->resolve(env, v);
1861         }
1862
1863         env->log_type_id = type_id;
1864         if (err == -E2BIG)
1865                 btf_verifier_log_type(env, t,
1866                                       "Exceeded max resolving depth:%u",
1867                                       MAX_RESOLVE_DEPTH);
1868         else if (err == -EEXIST)
1869                 btf_verifier_log_type(env, t, "Loop detected");
1870
1871         return err;
1872 }
1873
1874 static bool btf_resolve_valid(struct btf_verifier_env *env,
1875                               const struct btf_type *t,
1876                               u32 type_id)
1877 {
1878         struct btf *btf = env->btf;
1879
1880         if (!env_type_is_resolved(env, type_id))
1881                 return false;
1882
1883         if (btf_type_is_struct(t))
1884                 return !btf->resolved_ids[type_id] &&
1885                         !btf->resolved_sizes[type_id];
1886
1887         if (btf_type_is_modifier(t) || btf_type_is_ptr(t)) {
1888                 t = btf_type_id_resolve(btf, &type_id);
1889                 return t && !btf_type_is_modifier(t);
1890         }
1891
1892         if (btf_type_is_array(t)) {
1893                 const struct btf_array *array = btf_type_array(t);
1894                 const struct btf_type *elem_type;
1895                 u32 elem_type_id = array->type;
1896                 u32 elem_size;
1897
1898                 elem_type = btf_type_id_size(btf, &elem_type_id, &elem_size);
1899                 return elem_type && !btf_type_is_modifier(elem_type) &&
1900                         (array->nelems * elem_size ==
1901                          btf->resolved_sizes[type_id]);
1902         }
1903
1904         return false;
1905 }
1906
1907 static int btf_check_all_types(struct btf_verifier_env *env)
1908 {
1909         struct btf *btf = env->btf;
1910         u32 type_id;
1911         int err;
1912
1913         err = env_resolve_init(env);
1914         if (err)
1915                 return err;
1916
1917         env->phase++;
1918         for (type_id = 1; type_id <= btf->nr_types; type_id++) {
1919                 const struct btf_type *t = btf_type_by_id(btf, type_id);
1920
1921                 env->log_type_id = type_id;
1922                 if (btf_type_needs_resolve(t) &&
1923                     !env_type_is_resolved(env, type_id)) {
1924                         err = btf_resolve(env, t, type_id);
1925                         if (err)
1926                                 return err;
1927                 }
1928
1929                 if (btf_type_needs_resolve(t) &&
1930                     !btf_resolve_valid(env, t, type_id)) {
1931                         btf_verifier_log_type(env, t, "Invalid resolve state");
1932                         return -EINVAL;
1933                 }
1934         }
1935
1936         return 0;
1937 }
1938
1939 static int btf_parse_type_sec(struct btf_verifier_env *env)
1940 {
1941         const struct btf_header *hdr = &env->btf->hdr;
1942         int err;
1943
1944         /* Type section must align to 4 bytes */
1945         if (hdr->type_off & (sizeof(u32) - 1)) {
1946                 btf_verifier_log(env, "Unaligned type_off");
1947                 return -EINVAL;
1948         }
1949
1950         if (!hdr->type_len) {
1951                 btf_verifier_log(env, "No type found");
1952                 return -EINVAL;
1953         }
1954
1955         err = btf_check_all_metas(env);
1956         if (err)
1957                 return err;
1958
1959         return btf_check_all_types(env);
1960 }
1961
1962 static int btf_parse_str_sec(struct btf_verifier_env *env)
1963 {
1964         const struct btf_header *hdr;
1965         struct btf *btf = env->btf;
1966         const char *start, *end;
1967
1968         hdr = &btf->hdr;
1969         start = btf->nohdr_data + hdr->str_off;
1970         end = start + hdr->str_len;
1971
1972         if (end != btf->data + btf->data_size) {
1973                 btf_verifier_log(env, "String section is not at the end");
1974                 return -EINVAL;
1975         }
1976
1977         if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_NAME_OFFSET ||
1978             start[0] || end[-1]) {
1979                 btf_verifier_log(env, "Invalid string section");
1980                 return -EINVAL;
1981         }
1982
1983         btf->strings = start;
1984
1985         return 0;
1986 }
1987
1988 static const size_t btf_sec_info_offset[] = {
1989         offsetof(struct btf_header, type_off),
1990         offsetof(struct btf_header, str_off),
1991 };
1992
1993 static int btf_sec_info_cmp(const void *a, const void *b)
1994 {
1995         const struct btf_sec_info *x = a;
1996         const struct btf_sec_info *y = b;
1997
1998         return (int)(x->off - y->off) ? : (int)(x->len - y->len);
1999 }
2000
2001 static int btf_check_sec_info(struct btf_verifier_env *env,
2002                               u32 btf_data_size)
2003 {
2004         struct btf_sec_info secs[ARRAY_SIZE(btf_sec_info_offset)];
2005         u32 total, expected_total, i;
2006         const struct btf_header *hdr;
2007         const struct btf *btf;
2008
2009         btf = env->btf;
2010         hdr = &btf->hdr;
2011
2012         /* Populate the secs from hdr */
2013         for (i = 0; i < ARRAY_SIZE(btf_sec_info_offset); i++)
2014                 secs[i] = *(struct btf_sec_info *)((void *)hdr +
2015                                                    btf_sec_info_offset[i]);
2016
2017         sort(secs, ARRAY_SIZE(btf_sec_info_offset),
2018              sizeof(struct btf_sec_info), btf_sec_info_cmp, NULL);
2019
2020         /* Check for gaps and overlap among sections */
2021         total = 0;
2022         expected_total = btf_data_size - hdr->hdr_len;
2023         for (i = 0; i < ARRAY_SIZE(btf_sec_info_offset); i++) {
2024                 if (expected_total < secs[i].off) {
2025                         btf_verifier_log(env, "Invalid section offset");
2026                         return -EINVAL;
2027                 }
2028                 if (total < secs[i].off) {
2029                         /* gap */
2030                         btf_verifier_log(env, "Unsupported section found");
2031                         return -EINVAL;
2032                 }
2033                 if (total > secs[i].off) {
2034                         btf_verifier_log(env, "Section overlap found");
2035                         return -EINVAL;
2036                 }
2037                 if (expected_total - total < secs[i].len) {
2038                         btf_verifier_log(env,
2039                                          "Total section length too long");
2040                         return -EINVAL;
2041                 }
2042                 total += secs[i].len;
2043         }
2044
2045         /* There is data other than hdr and known sections */
2046         if (expected_total != total) {
2047                 btf_verifier_log(env, "Unsupported section found");
2048                 return -EINVAL;
2049         }
2050
2051         return 0;
2052 }
2053
2054 static int btf_parse_hdr(struct btf_verifier_env *env, void __user *btf_data,
2055                          u32 btf_data_size)
2056 {
2057         const struct btf_header *hdr;
2058         u32 hdr_len, hdr_copy;
2059         /*
2060          * Minimal part of the "struct btf_header" that
2061          * contains the hdr_len.
2062          */
2063         struct btf_min_header {
2064                 u16     magic;
2065                 u8      version;
2066                 u8      flags;
2067                 u32     hdr_len;
2068         } __user *min_hdr;
2069         struct btf *btf;
2070         int err;
2071
2072         btf = env->btf;
2073         min_hdr = btf_data;
2074
2075         if (btf_data_size < sizeof(*min_hdr)) {
2076                 btf_verifier_log(env, "hdr_len not found");
2077                 return -EINVAL;
2078         }
2079
2080         if (get_user(hdr_len, &min_hdr->hdr_len))
2081                 return -EFAULT;
2082
2083         if (btf_data_size < hdr_len) {
2084                 btf_verifier_log(env, "btf_header not found");
2085                 return -EINVAL;
2086         }
2087
2088         err = bpf_check_uarg_tail_zero(btf_data, sizeof(btf->hdr), hdr_len);
2089         if (err) {
2090                 if (err == -E2BIG)
2091                         btf_verifier_log(env, "Unsupported btf_header");
2092                 return err;
2093         }
2094
2095         hdr_copy = min_t(u32, hdr_len, sizeof(btf->hdr));
2096         if (copy_from_user(&btf->hdr, btf_data, hdr_copy))
2097                 return -EFAULT;
2098
2099         hdr = &btf->hdr;
2100
2101         btf_verifier_log_hdr(env, btf_data_size);
2102
2103         if (hdr->magic != BTF_MAGIC) {
2104                 btf_verifier_log(env, "Invalid magic");
2105                 return -EINVAL;
2106         }
2107
2108         if (hdr->version != BTF_VERSION) {
2109                 btf_verifier_log(env, "Unsupported version");
2110                 return -ENOTSUPP;
2111         }
2112
2113         if (hdr->flags) {
2114                 btf_verifier_log(env, "Unsupported flags");
2115                 return -ENOTSUPP;
2116         }
2117
2118         if (btf_data_size == hdr->hdr_len) {
2119                 btf_verifier_log(env, "No data");
2120                 return -EINVAL;
2121         }
2122
2123         err = btf_check_sec_info(env, btf_data_size);
2124         if (err)
2125                 return err;
2126
2127         return 0;
2128 }
2129
2130 static struct btf *btf_parse(void __user *btf_data, u32 btf_data_size,
2131                              u32 log_level, char __user *log_ubuf, u32 log_size)
2132 {
2133         struct btf_verifier_env *env = NULL;
2134         struct bpf_verifier_log *log;
2135         struct btf *btf = NULL;
2136         u8 *data;
2137         int err;
2138
2139         if (btf_data_size > BTF_MAX_SIZE)
2140                 return ERR_PTR(-E2BIG);
2141
2142         env = kzalloc(sizeof(*env), GFP_KERNEL | __GFP_NOWARN);
2143         if (!env)
2144                 return ERR_PTR(-ENOMEM);
2145
2146         log = &env->log;
2147         if (log_level || log_ubuf || log_size) {
2148                 /* user requested verbose verifier output
2149                  * and supplied buffer to store the verification trace
2150                  */
2151                 log->level = log_level;
2152                 log->ubuf = log_ubuf;
2153                 log->len_total = log_size;
2154
2155                 /* log attributes have to be sane */
2156                 if (log->len_total < 128 || log->len_total > UINT_MAX >> 8 ||
2157                     !log->level || !log->ubuf) {
2158                         err = -EINVAL;
2159                         goto errout;
2160                 }
2161         }
2162
2163         btf = kzalloc(sizeof(*btf), GFP_KERNEL | __GFP_NOWARN);
2164         if (!btf) {
2165                 err = -ENOMEM;
2166                 goto errout;
2167         }
2168         env->btf = btf;
2169
2170         err = btf_parse_hdr(env, btf_data, btf_data_size);
2171         if (err)
2172                 goto errout;
2173
2174         data = kvmalloc(btf_data_size, GFP_KERNEL | __GFP_NOWARN);
2175         if (!data) {
2176                 err = -ENOMEM;
2177                 goto errout;
2178         }
2179
2180         btf->data = data;
2181         btf->data_size = btf_data_size;
2182         btf->nohdr_data = btf->data + btf->hdr.hdr_len;
2183
2184         if (copy_from_user(data, btf_data, btf_data_size)) {
2185                 err = -EFAULT;
2186                 goto errout;
2187         }
2188
2189         err = btf_parse_str_sec(env);
2190         if (err)
2191                 goto errout;
2192
2193         err = btf_parse_type_sec(env);
2194         if (err)
2195                 goto errout;
2196
2197         if (log->level && bpf_verifier_log_full(log)) {
2198                 err = -ENOSPC;
2199                 goto errout;
2200         }
2201
2202         btf_verifier_env_free(env);
2203         refcount_set(&btf->refcnt, 1);
2204         return btf;
2205
2206 errout:
2207         btf_verifier_env_free(env);
2208         if (btf)
2209                 btf_free(btf);
2210         return ERR_PTR(err);
2211 }
2212
2213 void btf_type_seq_show(const struct btf *btf, u32 type_id, void *obj,
2214                        struct seq_file *m)
2215 {
2216         const struct btf_type *t = btf_type_by_id(btf, type_id);
2217
2218         btf_type_ops(t)->seq_show(btf, t, type_id, obj, 0, m);
2219 }
2220
2221 static int btf_release(struct inode *inode, struct file *filp)
2222 {
2223         btf_put(filp->private_data);
2224         return 0;
2225 }
2226
2227 const struct file_operations btf_fops = {
2228         .release        = btf_release,
2229 };
2230
2231 static int __btf_new_fd(struct btf *btf)
2232 {
2233         return anon_inode_getfd("btf", &btf_fops, btf, O_RDONLY | O_CLOEXEC);
2234 }
2235
2236 int btf_new_fd(const union bpf_attr *attr)
2237 {
2238         struct btf *btf;
2239         int ret;
2240
2241         btf = btf_parse(u64_to_user_ptr(attr->btf),
2242                         attr->btf_size, attr->btf_log_level,
2243                         u64_to_user_ptr(attr->btf_log_buf),
2244                         attr->btf_log_size);
2245         if (IS_ERR(btf))
2246                 return PTR_ERR(btf);
2247
2248         ret = btf_alloc_id(btf);
2249         if (ret) {
2250                 btf_free(btf);
2251                 return ret;
2252         }
2253
2254         /*
2255          * The BTF ID is published to the userspace.
2256          * All BTF free must go through call_rcu() from
2257          * now on (i.e. free by calling btf_put()).
2258          */
2259
2260         ret = __btf_new_fd(btf);
2261         if (ret < 0)
2262                 btf_put(btf);
2263
2264         return ret;
2265 }
2266
2267 struct btf *btf_get_by_fd(int fd)
2268 {
2269         struct btf *btf;
2270         struct fd f;
2271
2272         f = fdget(fd);
2273
2274         if (!f.file)
2275                 return ERR_PTR(-EBADF);
2276
2277         if (f.file->f_op != &btf_fops) {
2278                 fdput(f);
2279                 return ERR_PTR(-EINVAL);
2280         }
2281
2282         btf = f.file->private_data;
2283         refcount_inc(&btf->refcnt);
2284         fdput(f);
2285
2286         return btf;
2287 }
2288
2289 int btf_get_info_by_fd(const struct btf *btf,
2290                        const union bpf_attr *attr,
2291                        union bpf_attr __user *uattr)
2292 {
2293         struct bpf_btf_info __user *uinfo;
2294         struct bpf_btf_info info = {};
2295         u32 info_copy, btf_copy;
2296         void __user *ubtf;
2297         u32 uinfo_len;
2298
2299         uinfo = u64_to_user_ptr(attr->info.info);
2300         uinfo_len = attr->info.info_len;
2301
2302         info_copy = min_t(u32, uinfo_len, sizeof(info));
2303         if (copy_from_user(&info, uinfo, info_copy))
2304                 return -EFAULT;
2305
2306         info.id = btf->id;
2307         ubtf = u64_to_user_ptr(info.btf);
2308         btf_copy = min_t(u32, btf->data_size, info.btf_size);
2309         if (copy_to_user(ubtf, btf->data, btf_copy))
2310                 return -EFAULT;
2311         info.btf_size = btf->data_size;
2312
2313         if (copy_to_user(uinfo, &info, info_copy) ||
2314             put_user(info_copy, &uattr->info.info_len))
2315                 return -EFAULT;
2316
2317         return 0;
2318 }
2319
2320 int btf_get_fd_by_id(u32 id)
2321 {
2322         struct btf *btf;
2323         int fd;
2324
2325         rcu_read_lock();
2326         btf = idr_find(&btf_idr, id);
2327         if (!btf || !refcount_inc_not_zero(&btf->refcnt))
2328                 btf = ERR_PTR(-ENOENT);
2329         rcu_read_unlock();
2330
2331         if (IS_ERR(btf))
2332                 return PTR_ERR(btf);
2333
2334         fd = __btf_new_fd(btf);
2335         if (fd < 0)
2336                 btf_put(btf);
2337
2338         return fd;
2339 }
2340
2341 u32 btf_id(const struct btf *btf)
2342 {
2343         return btf->id;
2344 }