/* SPDX-License-Identifier: GPL-2.0 */

/* Copyright (c) 2018 Facebook */

#include <uapi/linux/btf.h>

#include <uapi/linux/types.h>

#include <linux/seq_file.h>

#include <linux/compiler.h>

#include <linux/ctype.h>

#include <linux/errno.h>

#include <linux/slab.h>

#include <linux/anon_inodes.h>

#include <linux/file.h>

#include <linux/uaccess.h>

#include <linux/kernel.h>

#include <linux/idr.h>

#include <linux/sort.h>

#include <linux/bpf_verifier.h>

#include <linux/btf.h>

/* BTF (BPF Type Format) is the meta data format which describes

* the data types of BPF program/map. Hence, it basically focus

* on the C programming language which the modern BPF is primary

* using.

*

* ELF Section:

* ~~~~~~~~~~~

* The BTF data is stored under the ".BTF" ELF section

*

* struct btf_type:

* ~~~~~~~~~~~~~~~

* Each 'struct btf_type' object describes a C data type.

* Depending on the type it is describing, a 'struct btf_type'

* object may be followed by more data. F.e.

* To describe an array, 'struct btf_type' is followed by

* 'struct btf_array'.

*

* 'struct btf_type' and any extra data following it are

* 4 bytes aligned.

*

* Type section:

* ~~~~~~~~~~~~~

* The BTF type section contains a list of 'struct btf_type' objects.

* Each one describes a C type. Recall from the above section

* that a 'struct btf_type' object could be immediately followed by extra

* data in order to desribe some particular C types.

*

* type_id:

* ~~~~~~~

* Each btf_type object is identified by a type_id. The type_id

* is implicitly implied by the location of the btf_type object in

* the BTF type section. The first one has type_id 1. The second

* one has type_id 2...etc. Hence, an earlier btf_type has

* a smaller type_id.

*

* A btf_type object may refer to another btf_type object by using

* type_id (i.e. the "type" in the "struct btf_type").

*

* NOTE that we cannot assume any reference-order.

* A btf_type object can refer to an earlier btf_type object

* but it can also refer to a later btf_type object.

*

* For example, to describe "const void *". A btf_type

* object describing "const" may refer to another btf_type

* object describing "void *". This type-reference is done

* by specifying type_id:

*

* [1] CONST (anon) type_id=2

* [2] PTR (anon) type_id=0

*

* The above is the btf_verifier debug log:

* - Each line started with "[?]" is a btf_type object

* - [?] is the type_id of the btf_type object.

* - CONST/PTR is the BTF_KIND_XXX

* - "(anon)" is the name of the type. It just

* happens that CONST and PTR has no name.

* - type_id=XXX is the 'u32 type' in btf_type

*

* NOTE: "void" has type_id 0

*

* String section:

* ~~~~~~~~~~~~~~

* The BTF string section contains the names used by the type section.

* Each string is referred by an "offset" from the beginning of the

* string section.

*

* Each string is '\0' terminated.

*

* The first character in the string section must be '\0'

* which is used to mean 'anonymous'. Some btf_type may not

* have a name.

*/

/* BTF verification:

*

* To verify BTF data, two passes are needed.

*

* Pass #1

* ~~~~~~~

* The first pass is to collect all btf_type objects to

* an array: "btf->types".

*

* Depending on the C type that a btf_type is describing,

* a btf_type may be followed by extra data. We don't know

* how many btf_type is there, and more importantly we don't

* know where each btf_type is located in the type section.

*

* Without knowing the location of each type_id, most verifications

* cannot be done. e.g. an earlier btf_type may refer to a later

* btf_type (recall the "const void *" above), so we cannot

* check this type-reference in the first pass.

*

* In the first pass, it still does some verifications (e.g.

* checking the name is a valid offset to the string section).

*

* Pass #2

* ~~~~~~~

* The main focus is to resolve a btf_type that is referring

* to another type.

*

* We have to ensure the referring type:

* 1) does exist in the BTF (i.e. in btf->types[])

* 2) does not cause a loop:

* struct A {

* struct B b;

* };

*

* struct B {

* struct A a;

* };

*

* btf_type_needs_resolve() decides if a btf_type needs

* to be resolved.

*

* The needs_resolve type implements the "resolve()" ops which

* essentially does a DFS and detects backedge.

*

* During resolve (or DFS), different C types have different

* "RESOLVED" conditions.

*

* When resolving a BTF_KIND_STRUCT, we need to resolve all its

* members because a member is always referring to another

* type. A struct's member can be treated as "RESOLVED" if

* it is referring to a BTF_KIND_PTR. Otherwise, the

* following valid C struct would be rejected:

*

* struct A {

* int m;

* struct A *a;

* };

*

* When resolving a BTF_KIND_PTR, it needs to keep resolving if

* it is referring to another BTF_KIND_PTR. Otherwise, we cannot

* detect a pointer loop, e.g.:

* BTF_KIND_CONST -> BTF_KIND_PTR -> BTF_KIND_CONST -> BTF_KIND_PTR +

* ^ |

* +-----------------------------------------+

*

*/

#define BITS_PER_U128 (sizeof(u64) * BITS_PER_BYTE * 2)

#define BITS_PER_BYTE_MASK (BITS_PER_BYTE - 1)

#define BITS_PER_BYTE_MASKED(bits) ((bits) & BITS_PER_BYTE_MASK)

#define BITS_ROUNDDOWN_BYTES(bits) ((bits) >> 3)

#define BITS_ROUNDUP_BYTES(bits) \

(BITS_ROUNDDOWN_BYTES(bits) + !!BITS_PER_BYTE_MASKED(bits))

#define BTF_INFO_MASK 0x8f00ffff

#define BTF_INT_MASK 0x0fffffff

#define BTF_TYPE_ID_VALID(type_id) ((type_id) <= BTF_MAX_TYPE)

#define BTF_STR_OFFSET_VALID(name_off) ((name_off) <= BTF_MAX_NAME_OFFSET)

/* 16MB for 64k structs and each has 16 members and

* a few MB spaces for the string section.

* The hard limit is S32_MAX.

*/

#define BTF_MAX_SIZE (16 * 1024 * 1024)

#define for_each_member(i, struct_type, member) \

for (i = 0, member = btf_type_member(struct_type); \

i < btf_type_vlen(struct_type); \

i++, member++)

#define for_each_member_from(i, from, struct_type, member) \

for (i = from, member = btf_type_member(struct_type) + from; \

i < btf_type_vlen(struct_type); \

i++, member++)

static DEFINE_IDR(btf_idr);

static DEFINE_SPINLOCK(btf_idr_lock);

struct btf {

void *data;

struct btf_type **types;

u32 *resolved_ids;

u32 *resolved_sizes;

const char *strings;

void *nohdr_data;

struct btf_header hdr;

u32 nr_types;

u32 types_size;

u32 data_size;

refcount_t refcnt;

u32 id;

struct rcu_head rcu;

};

enum verifier_phase {

CHECK_META,

CHECK_TYPE,

};

struct resolve_vertex {

const struct btf_type *t;

u32 type_id;

u16 next_member;

};

enum visit_state {

NOT_VISITED,

VISITED,

RESOLVED,

};

enum resolve_mode {

RESOLVE_TBD, /* To Be Determined */

RESOLVE_PTR, /* Resolving for Pointer */

RESOLVE_STRUCT_OR_ARRAY, /* Resolving for struct/union

* or array

*/

};

#define MAX_RESOLVE_DEPTH 32

struct btf_sec_info {

u32 off;

u32 len;

};

struct btf_verifier_env {

struct btf *btf;

u8 *visit_states;

struct resolve_vertex stack[MAX_RESOLVE_DEPTH];

struct bpf_verifier_log log;

u32 log_type_id;

u32 top_stack;

enum verifier_phase phase;

enum resolve_mode resolve_mode;

};

static const char * const btf_kind_str[NR_BTF_KINDS] = {

[BTF_KIND_UNKN] = "UNKNOWN",

[BTF_KIND_INT] = "INT",

[BTF_KIND_PTR] = "PTR",

[BTF_KIND_ARRAY] = "ARRAY",

[BTF_KIND_STRUCT] = "STRUCT",

[BTF_KIND_UNION] = "UNION",

[BTF_KIND_ENUM] = "ENUM",

[BTF_KIND_FWD] = "FWD",

[BTF_KIND_TYPEDEF] = "TYPEDEF",

[BTF_KIND_VOLATILE] = "VOLATILE",

[BTF_KIND_CONST] = "CONST",

[BTF_KIND_RESTRICT] = "RESTRICT",

[BTF_KIND_FUNC] = "FUNC",

[BTF_KIND_FUNC_PROTO] = "FUNC_PROTO",

};

struct btf_kind_operations {

s32 (*check_meta)(struct btf_verifier_env *env,

const struct btf_type *t,

u32 meta_left);

int (*resolve)(struct btf_verifier_env *env,

const struct resolve_vertex *v);

int (*check_member)(struct btf_verifier_env *env,

const struct btf_type *struct_type,

const struct btf_member *member,

const struct btf_type *member_type);

int (*check_kflag_member)(struct btf_verifier_env *env,

const struct btf_type *struct_type,

const struct btf_member *member,

const struct btf_type *member_type);

void (*log_details)(struct btf_verifier_env *env,

const struct btf_type *t);

void (*seq_show)(const struct btf *btf, const struct btf_type *t,

u32 type_id, void *data, u8 bits_offsets,

struct seq_file *m);

};

static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS];

static struct btf_type btf_void;

static int btf_resolve(struct btf_verifier_env *env,

const struct btf_type *t, u32 type_id);

static bool btf_type_is_modifier(const struct btf_type *t)

{

/* Some of them is not strictly a C modifier

* but they are grouped into the same bucket

* for BTF concern:

* A type (t) that refers to another

* type through t->type AND its size cannot

* be determined without following the t->type.

*

* ptr does not fall into this bucket

* because its size is always sizeof(void *).

*/

switch (BTF_INFO_KIND(t->info)) {

case BTF_KIND_TYPEDEF:

case BTF_KIND_VOLATILE:

case BTF_KIND_CONST:

case BTF_KIND_RESTRICT:

return true;

}

return false;

}

static bool btf_type_is_void(const struct btf_type *t)

{

return t == &btf_void;

}

static bool btf_type_is_fwd(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_FWD;

}

static bool btf_type_is_func(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC;

}

static bool btf_type_is_func_proto(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC_PROTO;

}

static bool btf_type_nosize(const struct btf_type *t)

{

return btf_type_is_void(t) || btf_type_is_fwd(t) ||

btf_type_is_func(t) || btf_type_is_func_proto(t);

}

static bool btf_type_nosize_or_null(const struct btf_type *t)

{

return !t || btf_type_nosize(t);

}

/* union is only a special case of struct:

* all its offsetof(member) == 0

*/

static bool btf_type_is_struct(const struct btf_type *t)

{

u8 kind = BTF_INFO_KIND(t->info);

return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;

}

static bool __btf_type_is_struct(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;

}

static bool btf_type_is_array(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;

}

static bool btf_type_is_ptr(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_PTR;

}

static bool btf_type_is_int(const struct btf_type *t)

{

return BTF_INFO_KIND(t->info) == BTF_KIND_INT;

}

/* What types need to be resolved?

*

* btf_type_is_modifier() is an obvious one.

*

* btf_type_is_struct() because its member refers to

* another type (through member->type).

* btf_type_is_array() because its element (array->type)

* refers to another type. Array can be thought of a

* special case of struct while array just has the same

* member-type repeated by array->nelems of times.

*/

static bool btf_type_needs_resolve(const struct btf_type *t)

{

return btf_type_is_modifier(t) ||

btf_type_is_ptr(t) ||

btf_type_is_struct(t) ||

btf_type_is_array(t);

}

/* t->size can be used */

static bool btf_type_has_size(const struct btf_type *t)

{

switch (BTF_INFO_KIND(t->info)) {

case BTF_KIND_INT:

case BTF_KIND_STRUCT:

case BTF_KIND_UNION:

case BTF_KIND_ENUM:

return true;

}

return false;

}

static const char *btf_int_encoding_str(u8 encoding)

{

if (encoding == 0)

return "(none)";

else if (encoding == BTF_INT_SIGNED)

return "SIGNED";

else if (encoding == BTF_INT_CHAR)

return "CHAR";

else if (encoding == BTF_INT_BOOL)

return "BOOL";

else

return "UNKN";

}

static u16 btf_type_vlen(const struct btf_type *t)

{

return BTF_INFO_VLEN(t->info);

}

static bool btf_type_kflag(const struct btf_type *t)

{

return BTF_INFO_KFLAG(t->info);

}

static u32 btf_member_bit_offset(const struct btf_type *struct_type,

const struct btf_member *member)

{

return btf_type_kflag(struct_type) ? BTF_MEMBER_BIT_OFFSET(member->offset)

: member->offset;

}

static u32 btf_member_bitfield_size(const struct btf_type *struct_type,

const struct btf_member *member)

{

return btf_type_kflag(struct_type) ? BTF_MEMBER_BITFIELD_SIZE(member->offset)

: 0;

}

static u32 btf_type_int(const struct btf_type *t)

{

return *(u32 *)(t + 1);

}

static const struct btf_array *btf_type_array(const struct btf_type *t)

{

return (const struct btf_array *)(t + 1);

}

static const struct btf_member *btf_type_member(const struct btf_type *t)

{

return (const struct btf_member *)(t + 1);

}

static const struct btf_enum *btf_type_enum(const struct btf_type *t)

{

return (const struct btf_enum *)(t + 1);

}

static const struct btf_kind_operations *btf_type_ops(const struct btf_type *t)

{

return kind_ops[BTF_INFO_KIND(t->info)];

}

static bool btf_name_offset_valid(const struct btf *btf, u32 offset)

{

return BTF_STR_OFFSET_VALID(offset) &&

offset < btf->hdr.str_len;

}

/* Only C-style identifier is permitted. This can be relaxed if

* necessary.

*/

static bool btf_name_valid_identifier(const struct btf *btf, u32 offset)

{

/* offset must be valid */

const char *src = &btf->strings[offset];

const char *src_limit;

if (!isalpha(*src) && *src != '_')

return false;

/* set a limit on identifier length */

src_limit = src + KSYM_NAME_LEN;

src++;

while (*src && src < src_limit) {

if (!isalnum(*src) && *src != '_')

return false;

src++;

}

return !*src;

}

static const char *__btf_name_by_offset(const struct btf *btf, u32 offset)

{

if (!offset)

return "(anon)";

else if (offset < btf->hdr.str_len)

return &btf->strings[offset];

else

return "(invalid-name-offset)";

}

const char *btf_name_by_offset(const struct btf *btf, u32 offset)

{

if (offset < btf->hdr.str_len)

return &btf->strings[offset];

return NULL;

}

const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id)

{

if (type_id > btf->nr_types)

return NULL;

return btf->types[type_id];

}

/*

* Regular int is not a bit field and it must be either

* u8/u16/u32/u64 or __int128.

*/

static bool btf_type_int_is_regular(const struct btf_type *t)

{

u8 nr_bits, nr_bytes;

u32 int_data;

int_data = btf_type_int(t);

nr_bits = BTF_INT_BITS(int_data);

nr_bytes = BITS_ROUNDUP_BYTES(nr_bits);

if (BITS_PER_BYTE_MASKED(nr_bits) ||

BTF_INT_OFFSET(int_data) ||

(nr_bytes != sizeof(u8) && nr_bytes != sizeof(u16) &&

nr_bytes != sizeof(u32) && nr_bytes != sizeof(u64) &&

nr_bytes != (2 * sizeof(u64)))) {

return false;

}

return true;

}

/*

* Check that given struct member is a regular int with expected

* offset and size.

*/

bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,

const struct btf_member *m,

u32 expected_offset, u32 expected_size)

{

const struct btf_type *t;

u32 id, int_data;

u8 nr_bits;

id = m->type;

t = btf_type_id_size(btf, &id, NULL);

if (!t || !btf_type_is_int(t))

return false;

int_data = btf_type_int(t);

nr_bits = BTF_INT_BITS(int_data);

if (btf_type_kflag(s)) {

u32 bitfield_size = BTF_MEMBER_BITFIELD_SIZE(m->offset);

u32 bit_offset = BTF_MEMBER_BIT_OFFSET(m->offset);

/* if kflag set, int should be a regular int and

* bit offset should be at byte boundary.

*/

return !bitfield_size &&

BITS_ROUNDUP_BYTES(bit_offset) == expected_offset &&

BITS_ROUNDUP_BYTES(nr_bits) == expected_size;

}

if (BTF_INT_OFFSET(int_data) ||

BITS_PER_BYTE_MASKED(m->offset) ||

BITS_ROUNDUP_BYTES(m->offset) != expected_offset ||

BITS_PER_BYTE_MASKED(nr_bits) ||

BITS_ROUNDUP_BYTES(nr_bits) != expected_size)

return false;

return true;

}

__printf(2, 3) static void __btf_verifier_log(struct bpf_verifier_log *log,

const char *fmt, ...)

{

va_list args;

va_start(args, fmt);

bpf_verifier_vlog(log, fmt, args);

va_end(args);

}

__printf(2, 3) static void btf_verifier_log(struct btf_verifier_env *env,

const char *fmt, ...)

{

struct bpf_verifier_log *log = &env->log;

va_list args;

if (!bpf_verifier_log_needed(log))

return;

va_start(args, fmt);

bpf_verifier_vlog(log, fmt, args);

va_end(args);

}

__printf(4, 5) static void __btf_verifier_log_type(struct btf_verifier_env *env,

const struct btf_type *t,

bool log_details,

const char *fmt, ...)

{

struct bpf_verifier_log *log = &env->log;

u8 kind = BTF_INFO_KIND(t->info);

struct btf *btf = env->btf;

va_list args;

if (!bpf_verifier_log_needed(log))

return;

__btf_verifier_log(log, "[%u] %s %s%s",

env->log_type_id,

btf_kind_str[kind],

__btf_name_by_offset(btf, t->name_off),

log_details ? " " : "");

if (log_details)

btf_type_ops(t)->log_details(env, t);

if (fmt && *fmt) {

__btf_verifier_log(log, " ");

va_start(args, fmt);

bpf_verifier_vlog(log, fmt, args);

va_end(args);

}

__btf_verifier_log(log, "\n");

}

#define btf_verifier_log_type(env, t, ...) \

__btf_verifier_log_type((env), (t), true, __VA_ARGS__)

#define btf_verifier_log_basic(env, t, ...) \

__btf_verifier_log_type((env), (t), false, __VA_ARGS__)

__printf(4, 5)

static void btf_verifier_log_member(struct btf_verifier_env *env,

const struct btf_type *struct_type,

const struct btf_member *member,

const char *fmt, ...)

{

struct bpf_verifier_log *log = &env->log;

struct btf *btf = env->btf;

va_list args;

if (!bpf_verifier_log_needed(log))

return;

/* The CHECK_META phase already did a btf dump.

*

* If member is logged again, it must hit an error in

* parsing this member. It is useful to print out which

* struct this member belongs to.

*/

if (env->phase != CHECK_META)

btf_verifier_log_type(env, struct_type, NULL);

if (btf_type_kflag(struct_type))

__btf_verifier_log(log,

"\t%s type_id=%u bitfield_size=%u bits_offset=%u",

__btf_name_by_offset(btf, member->name_off),

member->type,

BTF_MEMBER_BITFIELD_SIZE(member->offset),

BTF_MEMBER_BIT_OFFSET(member->offset));

else

__btf_verifier_log(log, "\t%s type_id=%u bits_offset=%u",

__btf_name_by_offset(btf, member->name_off),

member->type, member->offset);

if (fmt && *fmt) {

__btf_verifier_log(log, " ");

va_start(args, fmt);

bpf_verifier_vlog(log, fmt, args);

va_end(args);

}

__btf_verifier_log(log, "\n");

}

static void btf_verifier_log_hdr(struct btf_verifier_env *env,

u32 btf_data_size)

{

struct bpf_verifier_log *log = &env->log;

const struct btf *btf = env->btf;

const struct btf_header *hdr;

if (!bpf_verifier_log_needed(log))

return;

hdr = &btf->hdr;

__btf_verifier_log(log, "magic: 0x%x\n", hdr->magic);

__btf_verifier_log(log, "version: %u\n", hdr->version);

__btf_verifier_log(log, "flags: 0x%x\n", hdr->flags);

__btf_verifier_log(log, "hdr_len: %u\n", hdr->hdr_len);

__btf_verifier_log(log, "type_off: %u\n", hdr->type_off);

__btf_verifier_log(log, "type_len: %u\n", hdr->type_len);

__btf_verifier_log(log, "str_off: %u\n", hdr->str_off);

__btf_verifier_log(log, "str_len: %u\n", hdr->str_len);

__btf_verifier_log(log, "btf_total_size: %u\n", btf_data_size);

}

static int btf_add_type(struct btf_verifier_env *env, struct btf_type *t)

{

struct btf *btf = env->btf;

/* < 2 because +1 for btf_void which is always in btf->types[0].

* btf_void is not accounted in btf->nr_types because btf_void

* does not come from the BTF file.

*/

if (btf->types_size - btf->nr_types < 2) {

/* Expand 'types' array */

struct btf_type **new_types;

u32 expand_by, new_size;

if (btf->types_size == BTF_MAX_TYPE) {

btf_verifier_log(env, "Exceeded max num of types");

return -E2BIG;

}

expand_by = max_t(u32, btf->types_size >> 2, 16);

new_size = min_t(u32, BTF_MAX_TYPE,

btf->types_size + expand_by);

new_types = kvcalloc(new_size, sizeof(*new_types),

GFP_KERNEL | __GFP_NOWARN);

if (!new_types)

return -ENOMEM;

if (btf->nr_types == 0)

new_types[0] = &btf_void;

else

memcpy(new_types, btf->types,

sizeof(*btf->types) * (btf->nr_types + 1));

kvfree(btf->types);

btf->types = new_types;

btf->types_size = new_size;

}

btf->types[++(btf->nr_types)] = t;

return 0;

}

static int btf_alloc_id(struct btf *btf)

{

int id;

idr_preload(GFP_KERNEL);

spin_lock_bh(&btf_idr_lock);

id = idr_alloc_cyclic(&btf_idr, btf, 1, INT_MAX, GFP_ATOMIC);

if (id > 0)

btf->id = id;

spin_unlock_bh(&btf_idr_lock);

idr_preload_end();

if (WARN_ON_ONCE(!id))

return -ENOSPC;

return id > 0 ? 0 : id;

}

static void btf_free_id(struct btf *btf)

{

unsigned long flags;

/*

* In map-in-map, calling map_delete_elem() on outer

* map will call bpf_map_put on the inner map.

* It will then eventually call btf_free_id()

* on the inner map. Some of the map_delete_elem()

* implementation may have irq disabled, so

* we need to use the _irqsave() version instead

* of the _bh() version.

*/

spin_lock_irqsave(&btf_idr_lock, flags);

idr_remove(&btf_idr, btf->id);

spin_unlock_irqrestore(&btf_idr_lock, flags);

}

static void btf_free(struct btf *btf)

{

kvfree(btf->types);

kvfree(btf->resolved_sizes);

kvfree(btf->resolved_ids);

kvfree(btf->data);

kfree(btf);

}

static void btf_free_rcu(struct rcu_head *rcu)

{

struct btf *btf = container_of(rcu, struct btf, rcu);

btf_free(btf);

}

void btf_put(struct btf *btf)

{

if (btf && refcount_dec_and_test(&btf->refcnt)) {

btf_free_id(btf);

call_rcu(&btf->rcu, btf_free_rcu);

}

}

static int env_resolve_init(struct btf_verifier_env *env)

{

struct btf *btf = env->btf;

u32 nr_types = btf->nr_types;

u32 *resolved_sizes = NULL;

u32 *resolved_ids = NULL;

u8 *visit_states = NULL;

/* +1 for btf_void */

resolved_sizes = kvcalloc(nr_types + 1, sizeof(*resolved_sizes),

GFP_KERNEL | __GFP_NOWARN);

if (!resolved_sizes)

goto nomem;

resolved_ids = kvcalloc(nr_types + 1, sizeof(*resolved_ids),

GFP_KERNEL | __GFP_NOWARN);

if (!resolved_ids)

goto nomem;

visit_states = kvcalloc(nr_types + 1, sizeof(*visit_states),

GFP_KERNEL | __GFP_NOWARN);

if (!visit_states)

goto nomem;

btf->resolved_sizes = resolved_sizes;

btf->resolved_ids = resolved_ids;

env->visit_states = visit_states;

return 0;

nomem:

kvfree(resolved_sizes);

kvfree(resolved_ids);

kvfree(visit_states);

return -ENOMEM;

}

static void btf_verifier_env_free(struct btf_verifier_env *env)

{

kvfree(env->visit_states);

kfree(env);

}

static bool env_type_is_resolve_sink(const struct btf_verifier_env *env,

const struct btf_type *next_type)

{

switch (env->resolve_mode) {

case RESOLVE_TBD:

/* int, enum or void is a sink */

return !btf_type_needs_resolve(next_type);

case RESOLVE_PTR:

/* int, enum, void, struct, array, func or func_proto is a sink

* for ptr

*/

return !btf_type_is_modifier(next_type) &&

!btf_type_is_ptr(next_type);

case RESOLVE_STRUCT_OR_ARRAY:

/* int, enum, void, ptr, func or func_proto is a sink

* for struct and array

*/

return !btf_type_is_modifier(next_type) &&

!btf_type_is_array(next_type) &&

!btf_type_is_struct(next_type);

default:

BUG();

}

}

static bool env_type_is_resolved(const struct btf_verifier_env *env,

u32 type_id)

{

return env->visit_states[type_id] == RESOLVED;

}

static int env_stack_push(struct btf_verifier_env *env,

const struct btf_type *t, u32 type_id)

{

struct resolve_vertex *v;

if (env->top_stack == MAX_RESOLVE_DEPTH)

return -E2BIG;

if (env->visit_states[type_id] != NOT_VISITED)

return -EEXIST;

env->visit_states[type_id] = VISITED;

v = &env->stack[env->top_stack++];

v->t = t;

v->type_id = type_id;

v->next_member = 0;

if (env->resolve_mode == RESOLVE_TBD) {

if (btf_type_is_ptr(t))

env->resolve_mode = RESOLVE_PTR;

else if (btf_type_is_struct(t) || btf_type_is_array(t))

env->resolve_mode = RESOLVE_STRUCT_OR_ARRAY;

}

return 0;

}

static void env_stack_set_next_member(struct btf_verifier_env *env,

u16 next_member)

{

env->stack[env->top_stack - 1].next_member = next_member;

}

static void env_stack_pop_resolved(struct btf_verifier_env *env,

u32 resolved_type_id,

u32 resolved_size)

{

u32 type_id = env->stack[--(env->top_stack)].type_id;

struct btf *btf = env->btf;

btf->resolved_sizes[type_id] = resolved_size;

btf->resolved_ids[type_id] = resolved_type_id;

env->visit_states[type_id] = RESOLVED;

}

static const struct resolve_vertex *env_stack_peak(struct btf_verifier_env *env)

{

return env->top_stack ? &env->stack[env->top_stack - 1] : NULL;

}

/* The input param "type_id" must point to a needs_resolve type */

static const struct btf_type *btf_type_id_resolve(const struct btf *btf,

u32 *type_id)

{

*type_id = btf->resolved_ids[*type_id];

return btf_type_by_id(btf, *type_id);

}

const struct btf_type *btf_type_id_size(const struct btf *btf,

u32 *type_id, u32 *ret_size)

{

const struct btf_type *size_type;

u32 size_type_id = *type_id;

u32 size = 0;

size_type = btf_type_by_id(btf, size_type_id);

if (btf_type_nosize_or_null(size_type))

return NULL;

if (btf_type_has_size(size_type)) {

size = size_type->size;

} else if (btf_type_is_array(size_type)) {

size = btf->resolved_sizes[size_type_id];

} else if (btf_type_is_ptr(size_type)) {

size = sizeof(void *);

} else {

if (WARN_ON_ONCE(!btf_type_is_modifier(size_type)))

return NULL;

size = btf->resolved_sizes[size_type_id];

size_type_id = btf->resolved_ids[size_type_id];

size_type = btf_type_by_id(btf, size_type_id);

if (btf_type_nosize_or_null(size_type))

return NULL;

}

*type_id = size_type_id;

if (ret_size)

*ret_size = size;

return size_type;

}

static int btf_df_check_member(struct btf_verifier_env *env,

const struct btf_type *struct_type,

const struct btf_member *member,

const struct btf_type *member_type)

{

btf_verifier_log_basic(env, struct_type,

"Unsupported check_member");