verifier: better overflow handling & support for ctx type

[pchaigno]

This pull request contains a series of patches to allow your latest examples to work with the uBPF verifier. The first patch reworks the overflow handling to allow for larger ranges of values. The second cleans up some commented code prohibiting packet writes, used for Oko, but not needed anymore. The third fixes examples so that they implement the appropriate checks on packet lengths (those were inverted). The last patch adds support for a new CTX_PTR type and uses it to recognize helpers ubpf_packet_data and ubpf_adjust_head.

I haven't implemented support for bit shifts in the first patch. I remember there were some issues with that some time ago, so if you get an example program that doesn't pass the verifier because of that, please send it to me. Adding support shouldn't be too difficult.

In some cases, the length checks in the example programs may not be needed anymore. As long as you write within the added bytes at the beginning of the packet, checks are not needed. The verifier recognizes calls to ubpf_adjust_head and adjusts the packet bounds accordingly.

I've taken this opportunity to fix a few warnings in the verifier's code. There are many remaining warnings in the codebase though.

[osinstom]

Paul, thanks for the PR!

I've just tested it with files from examples/. It works!

However, when I tested your PR with the BPF programs generated from the P4 language by p4c-ubpf, I'm getting the following error, while loading program:

2020-01-24T12:55:27.507Z|01267|bpf|WARN|Failed to load code: invalid access to packet at PC 9

I'm getting this error for any BPF program generated from the reference P4 programs.

I'm pasting a sample BPF program, which is rejected by the BPF verifier:

test.c

/* Automatically generated by p4c-ubpf from ../examples/tunneling.p4 on Fri Jan 24 13:54:44 2020
 */
#include "test.h"
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include "ubpf_common.h"

#define BPF_MASK(t, w) ((((t)(1)) << (w)) - (t)1)
#define BYTES(w) ((w) / 8)

void* memcpy(void* dest, const void* src, size_t num);

static void *(*ubpf_map_lookup)(const void *, const void *) = (void *)1;
static int (*ubpf_map_update)(void *, const void *, void *) = (void *)2;
static int (*ubpf_map_delete)(void *, const void *) = (void *)3;
static int (*ubpf_map_add)(void *, const void *) = (void *)4;
static uint64_t (*ubpf_time_get_ns)() = (void *)5;
static uint32_t (*ubpf_hash)(const void *, uint64_t) = (void *)6;
static void (*ubpf_printf)(const char *fmt, ...) = (void *)7;
static void *(*ubpf_packet_data)(const void *) = (void *)9;
static void *(*ubpf_adjust_head)(const void *, uint64_t) = (void *)8;

#define write_partial(a, w, s, v) do { *((uint8_t*)a) = ((*((uint8_t*)a)) & ~(BPF_MASK(uint8_t, w) << s)) | (v << s) ; } while (0)
#define write_byte(base, offset, v) do { *(uint8_t*)((base) + (offset)) = (v); } while (0)

static uint32_t
bpf_htonl(uint32_t val) {
    return htonl(val);
}
static uint16_t
bpf_htons(uint16_t val) {
    return htons(val);
}
static uint64_t
bpf_htonll(uint64_t val) {
    return htonll(val);
}

uint64_t entry(void *ctx, uint64_t pkt_len){
    void *pkt = ubpf_packet_data(ctx);
    struct Headers_t headers = {
        .ethernet = {
            .ebpf_valid = 0
        },
        .mpls = {
            .ebpf_valid = 0
        },
        .ipv4 = {
            .ebpf_valid = 0
        },
    };
    struct metadata meta = {
    };
    int packetOffsetInBits = 0;
    uint8_t pass = 1;
    unsigned char ebpf_byte;
    int head_len = 0;

    if (sizeof(struct Headers_t) < pkt_len) {
        return 0;
    }

    goto start;
    start: {
        /* extract(headers.ethernet)*/

        headers.ethernet.dstAddr = (uint64_t)((load_dword(pkt, BYTES(packetOffsetInBits)) >> 16) & BPF_MASK(uint64_t, 48));
        packetOffsetInBits += 48;

        headers.ethernet.srcAddr = (uint64_t)((load_dword(pkt, BYTES(packetOffsetInBits)) >> 16) & BPF_MASK(uint64_t, 48));
        packetOffsetInBits += 48;

        headers.ethernet.etherType = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        headers.ethernet.ebpf_valid = 1;
        switch (headers.ethernet.etherType) {
            case 0x800: goto ipv4;
            case 0x8847: goto mpls;
            default: goto reject;
        }
    }
    mpls: {
        /* extract(headers.mpls)*/

        headers.mpls.label = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits)) >> 12) & BPF_MASK(uint32_t, 20));
        packetOffsetInBits += 20;

        headers.mpls.tc = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits)) >> 1) & BPF_MASK(uint8_t, 3));
        packetOffsetInBits += 3;

        headers.mpls.stack = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))) & BPF_MASK(uint8_t, 1));
        packetOffsetInBits += 1;

        headers.mpls.ttl = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        headers.mpls.ebpf_valid = 1;
        goto ipv4;
    }
    ipv4: {
        /* extract(headers.ipv4)*/

        headers.ipv4.version = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits)) >> 4) & BPF_MASK(uint8_t, 4));
        packetOffsetInBits += 4;

        headers.ipv4.ihl = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))) & BPF_MASK(uint8_t, 4));
        packetOffsetInBits += 4;

        headers.ipv4.diffserv = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        headers.ipv4.totalLen = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        headers.ipv4.identification = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        headers.ipv4.flags = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits)) >> 5) & BPF_MASK(uint8_t, 3));
        packetOffsetInBits += 3;

        headers.ipv4.fragOffset = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))) & BPF_MASK(uint16_t, 13));
        packetOffsetInBits += 13;

        headers.ipv4.ttl = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        headers.ipv4.protocol = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        headers.ipv4.hdrChecksum = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        headers.ipv4.srcAddr = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 32;

        headers.ipv4.dstAddr = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 32;

        headers.ipv4.ebpf_valid = 1;
        goto accept;
    }

    reject: { return 0; }

    accept:
    {
        {

            if (headers.mpls.ebpf_valid) {
                {
                    /* construct key */
                    struct pipe_upstream_tbl_key key = {};
                    key.headers_mpls_label = headers.mpls.label;
                    /* value */
                    struct pipe_upstream_tbl_value *value = NULL;
                    /* perform lookup */
                    value = ubpf_map_lookup(&pipe_upstream_tbl, &key);

                    if (value != NULL) {
                        /* run action */
                        switch (value->action) {
                            case pipe_mpls_decap: 
                            {
                                                                head_len -= 4;
                                headers.mpls.ebpf_valid = false;
headers.ethernet.etherType = 0x800;
                            }
                            break;
                            case pipe_upstream_tbl_NoAction: 
                            {

                            }
                            break;
                            default: return 0;
                        }
                    }
                    else return 0;
                }
;
            } else {
                {
                    /* construct key */
                    struct pipe_downstream_tbl_key key = {};
                    key.headers_ipv4_dstAddr = headers.ipv4.dstAddr;
                    /* value */
                    struct pipe_downstream_tbl_value *value = NULL;
                    /* perform lookup */
                    value = ubpf_map_lookup(&pipe_downstream_tbl, &key);

                    if (value != NULL) {
                        /* run action */
                        switch (value->action) {
                            case pipe_mpls_encap: 
                            {
                                                                head_len += 4;
                                headers.mpls.ebpf_valid = true;
headers.ethernet.etherType = 0x8847;headers.mpls.label = 20;headers.mpls.tc = 5;headers.mpls.stack = 1;headers.mpls.ttl = 64;
                            }
                            break;
                            case pipe_downstream_tbl_NoAction: 
                            {

                            }
                            break;
                            default: return 0;
                        }
                    }
                    else return 0;
                }
;
            }

        }    }
    packetOffsetInBits = 0;
    pkt = ubpf_adjust_head(ctx, head_len);
    if (headers.ethernet.ebpf_valid) {
        headers.ethernet.dstAddr = htonll(headers.ethernet.dstAddr << 16);
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[4];
        write_byte(pkt, BYTES(packetOffsetInBits) + 4, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.dstAddr))[5];
        write_byte(pkt, BYTES(packetOffsetInBits) + 5, (ebpf_byte));
        packetOffsetInBits += 48;

        headers.ethernet.srcAddr = htonll(headers.ethernet.srcAddr << 16);
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[4];
        write_byte(pkt, BYTES(packetOffsetInBits) + 4, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.srcAddr))[5];
        write_byte(pkt, BYTES(packetOffsetInBits) + 5, (ebpf_byte));
        packetOffsetInBits += 48;

        headers.ethernet.etherType = bpf_htons(headers.ethernet.etherType);
        ebpf_byte = ((char*)(&headers.ethernet.etherType))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ethernet.etherType))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

    }
;    if (headers.mpls.ebpf_valid) {
        headers.mpls.label = htonl(headers.mpls.label << 12);
        ebpf_byte = ((char*)(&headers.mpls.label))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.mpls.label))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.mpls.label))[2];
        write_partial(pkt + BYTES(packetOffsetInBits) + 2, 4, 4, (ebpf_byte >> 4));
        packetOffsetInBits += 20;

        ebpf_byte = ((char*)(&headers.mpls.tc))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 3, 1, (ebpf_byte >> 0));
        packetOffsetInBits += 3;

        ebpf_byte = ((char*)(&headers.mpls.stack))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 1, 0, (ebpf_byte >> 0));
        packetOffsetInBits += 1;

        ebpf_byte = ((char*)(&headers.mpls.ttl))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

    }
;    if (headers.ipv4.ebpf_valid) {
        ebpf_byte = ((char*)(&headers.ipv4.version))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 4, 4, (ebpf_byte >> 0));
        packetOffsetInBits += 4;

        ebpf_byte = ((char*)(&headers.ipv4.ihl))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 4, 0, (ebpf_byte >> 0));
        packetOffsetInBits += 4;

        ebpf_byte = ((char*)(&headers.ipv4.diffserv))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        headers.ipv4.totalLen = bpf_htons(headers.ipv4.totalLen);
        ebpf_byte = ((char*)(&headers.ipv4.totalLen))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.totalLen))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        headers.ipv4.identification = bpf_htons(headers.ipv4.identification);
        ebpf_byte = ((char*)(&headers.ipv4.identification))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.identification))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        ebpf_byte = ((char*)(&headers.ipv4.flags))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 3, 5, (ebpf_byte >> 0));
        packetOffsetInBits += 3;

        headers.ipv4.fragOffset = bpf_htons(headers.ipv4.fragOffset << 3);
        ebpf_byte = ((char*)(&headers.ipv4.fragOffset))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 5, 0, (ebpf_byte >> 3));
        write_partial(pkt + BYTES(packetOffsetInBits) + 0 + 1, 3, 5, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.fragOffset))[1];
        write_partial(pkt + BYTES(packetOffsetInBits) + 1, 5, 0, (ebpf_byte >> 3));
        packetOffsetInBits += 13;

        ebpf_byte = ((char*)(&headers.ipv4.ttl))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        ebpf_byte = ((char*)(&headers.ipv4.protocol))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        headers.ipv4.hdrChecksum = bpf_htons(headers.ipv4.hdrChecksum);
        ebpf_byte = ((char*)(&headers.ipv4.hdrChecksum))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.hdrChecksum))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        headers.ipv4.srcAddr = htonl(headers.ipv4.srcAddr);
        ebpf_byte = ((char*)(&headers.ipv4.srcAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.srcAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.srcAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.srcAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        packetOffsetInBits += 32;

        headers.ipv4.dstAddr = htonl(headers.ipv4.dstAddr);
        ebpf_byte = ((char*)(&headers.ipv4.dstAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.dstAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.dstAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&headers.ipv4.dstAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        packetOffsetInBits += 32;

    }
;    if (pass)
        return 1;
    else
        return 0;
}

test.h

/* Automatically generated by p4c-ubpf from ../examples/tunneling.p4 on Fri Jan 24 13:54:44 2020
 */
#ifndef _P4_GEN_HEADER_
#define _P4_GEN_HEADER_
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include "ubpf_common.h"

struct Ethernet_h {
    uint64_t dstAddr; /* EthernetAddress */
    uint64_t srcAddr; /* EthernetAddress */
    uint16_t etherType; /* bit<16> */
    uint8_t ebpf_valid;
};

struct IPv4_h {
    uint8_t version; /* bit<4> */
    uint8_t ihl; /* bit<4> */
    uint8_t diffserv; /* bit<8> */
    uint16_t totalLen; /* bit<16> */
    uint16_t identification; /* bit<16> */
    uint8_t flags; /* bit<3> */
    uint16_t fragOffset; /* bit<13> */
    uint8_t ttl; /* bit<8> */
    uint8_t protocol; /* bit<8> */
    uint16_t hdrChecksum; /* bit<16> */
    uint32_t srcAddr; /* IPv4Address */
    uint32_t dstAddr; /* IPv4Address */
    uint8_t ebpf_valid;
};

struct mpls_h {
    uint32_t label; /* bit<20> */
    uint8_t tc; /* bit<3> */
    uint8_t stack; /* bit<1> */
    uint8_t ttl; /* bit<8> */
    uint8_t ebpf_valid;
};

struct Headers_t {
    struct Ethernet_h ethernet; /* Ethernet_h */
    struct mpls_h mpls; /* mpls_h */
    struct IPv4_h ipv4; /* IPv4_h */
};

struct metadata {
};

enum ubpf_map_type {
    UBPF_MAP_TYPE_HASHMAP = 4,
};
struct ubpf_map_def {
    enum ubpf_map_type type;
    unsigned int key_size;
    unsigned int value_size;
    unsigned int max_entries;
    unsigned int nb_hash_functions;
};

struct pipe_downstream_tbl_key {
    uint32_t headers_ipv4_dstAddr; /* headers.ipv4.dstAddr */
};
enum downstream_tbl_0_actions {
    pipe_mpls_encap,
    pipe_downstream_tbl_NoAction,
};
struct pipe_downstream_tbl_value {
    enum downstream_tbl_0_actions action;
    union {
        struct {
        } pipe_mpls_encap;
        struct {
        } pipe_downstream_tbl_NoAction;
    } u;
};
struct pipe_upstream_tbl_key {
    uint32_t headers_mpls_label; /* headers.mpls.label */
};
enum upstream_tbl_0_actions {
    pipe_mpls_decap,
    pipe_upstream_tbl_NoAction,
};
struct pipe_upstream_tbl_value {
    enum upstream_tbl_0_actions action;
    union {
        struct {
        } pipe_mpls_decap;
        struct {
        } pipe_upstream_tbl_NoAction;
    } u;
};

struct ubpf_map_def pipe_downstream_tbl = {
    .type = UBPF_MAP_TYPE_HASHMAP,
    .key_size = sizeof(struct pipe_downstream_tbl_key),
    .value_size = sizeof(struct pipe_downstream_tbl_value),
    .max_entries = 65535,
    .nb_hash_functions = 0,
};
struct ubpf_map_def pipe_upstream_tbl = {
    .type = UBPF_MAP_TYPE_HASHMAP,
    .key_size = sizeof(struct pipe_upstream_tbl_key),
    .value_size = sizeof(struct pipe_upstream_tbl_value),
    .max_entries = 65535,
    .nb_hash_functions = 0,
};
#endif

ubpf_common.h

#ifndef ___constant_swab16
#define ___constant_swab16(x) ((uint16_t)(             \
    (((uint16_t)(x) & (uint16_t)0x00ffU) << 8) |          \
    (((uint16_t)(x) & (uint16_t)0xff00U) >> 8)))
#endif

#ifndef ___constant_swab32
#define ___constant_swab32(x) ((uint32_t)(             \
    (((uint32_t)(x) & (uint32_t)0x000000ffUL) << 24) |        \
    (((uint32_t)(x) & (uint32_t)0x0000ff00UL) <<  8) |        \
    (((uint32_t)(x) & (uint32_t)0x00ff0000UL) >>  8) |        \
    (((uint32_t)(x) & (uint32_t)0xff000000UL) >> 24)))
#endif

#ifndef ___constant_swab64
#define ___constant_swab64(x) ((uint64_t)(             \
    (((uint64_t)(x) & (uint64_t)0x00000000000000ffULL) << 56) |   \
    (((uint64_t)(x) & (uint64_t)0x000000000000ff00ULL) << 40) |   \
    (((uint64_t)(x) & (uint64_t)0x0000000000ff0000ULL) << 24) |   \
    (((uint64_t)(x) & (uint64_t)0x00000000ff000000ULL) <<  8) |   \
    (((uint64_t)(x) & (uint64_t)0x000000ff00000000ULL) >>  8) |   \
    (((uint64_t)(x) & (uint64_t)0x0000ff0000000000ULL) >> 24) |   \
    (((uint64_t)(x) & (uint64_t)0x00ff000000000000ULL) >> 40) |   \
    (((uint64_t)(x) & (uint64_t)0xff00000000000000ULL) >> 56)))
#endif

#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
#ifndef __constant_htonll
#define __constant_htonll(x) (___constant_swab64((x)))
#endif

#ifndef __constant_ntohll
#define __constant_ntohll(x) (___constant_swab64((x)))
#endif

#define __constant_htonl(x) (___constant_swab32((x)))
#define __constant_ntohl(x) (___constant_swab32(x))
#define __constant_htons(x) (___constant_swab16((x)))
#define __constant_ntohs(x) ___constant_swab16((x))

#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
# warning "I never tested BIG_ENDIAN machine!"
#define __constant_htonll(x) (x)
#define __constant_ntohll(X) (x)
#define __constant_htonl(x) (x)
#define __constant_ntohl(x) (x)
#define __constant_htons(x) (x)
#define __constant_ntohs(x) (x)

#else
# error "Fix your compiler's __BYTE_ORDER__?!"
#endif

#define htonl(d) __constant_htonl(d)
#define htons(d) __constant_htons(d)
#define htonll(d) __constant_htonll(d)
#define ntohl(d) __constant_ntohl(d)
#define ntohs(d) __constant_ntohs(d)
#define ntohll(d) __constant_ntohll(d)

#define load_byte(data, b) (*(((uint8_t*)(data)) + (b)))
#define load_half(data, b) __constant_ntohs(*(uint16_t *)((uint8_t*)(data) + (b)))
#define load_word(data, b) __constant_ntohl(*(uint32_t *)((uint8_t*)(data) + (b)))
#define load_dword(data, b) __constant_ntohll(*(uint64_t *)((uint8_t*)(data) + (b)))

It's compiled using clang-6.0:

clang-6.0 -O2 -I .. -target bpf -c test.c -o test.o

Could you take a look at it, please?

[pchaigno]

I just had a quick look so far, but that looks incorrect:

if (sizeof(struct Headers_t) < pkt_len) {
    return 0;
}

Don't you want to error out if the packet is smaller than struct Headers_t? So:

if (pkt_len < sizeof(struct Headers_t)) {
    return 0;
}

[osinstom]

This is the problem, indeed. So, it was on our side, sorry! (anyway, we need to implement more flexible solution for p4c-ubpf).

Unfortunately, once I applied your suggestion, I'm getting yet another error:

2020-01-24T14:33:45.455Z|02191|bpf|WARN|Failed to load code: invalid access to packet at PC 124

However, I'm not sure if the problem is with the verifier or if our deparsing code is buggy.

[pchaigno]

Actually, the packet length check is still not correct. You're comparing the packet length to struct Headers_t, the structure where you save the packet's info. You want to compare the packet length to the highest offset you read or write within the packet, which is different.

I don't think that's the source of the error you're seeing though. struct Headers_t looks larger than the largest packet offset you may need to access (there are addition ebpf_valid field + some bit-fields are oversized).

[osinstom]

Yep, I realized that our packet length's check is not well-implemented right after you suggested to modify the If statement. That I had in mind saying that we need more flexible solution for p4c-ubpf. The appropriate approach is implemented by p4c-ebpf.

However, I think the root cause of the problem I'm getting now is in the Deparser (the part after ubpf_adjust_head()), but we still need some time to analyze it.

[pchaigno]

I've updated the branch with a bit more detailed error messages for invalid accesses to the packet. Could you run it again? It should give us the access offset, which may help derive which part of the C code is rejected.

[osinstom]

Paul,

Now, I'm getting the following message:

2020-01-28T09:04:00.012Z|00818|bpf|WARN|Failed to load code: invalid access to packet (-1 + 1 > 64) at PC 111

[pchaigno]

I haven't implemented support for bit shifts in the first patch. I remember there were some issues with that some time ago, so if you get an example program that doesn't pass the verifier because of that, please send it to me. Adding support shouldn't be too difficult.

Looks like you just provided that example program :smiley: Verification fails because the verifier is currently unable to deduce bounds for R9 (max bound is UINT64_MAX or -1 in the error message):

111:    71 92 00 00 00 00 00 00 r2 = *(u8 *)(r9 + 0)

Tracking this through a few assignments, I found the culprit to be instruction 56:

        PC=53, class=0x7, opcode=0xbf
    R9 now has type 0x4, range [144;144] U [144;144]
        [...]
        PC=56, class=0x7, opcode=0x77
    R9 (t=4) has updated range [-9223372036854775808;18446744073709551615)

which is:

56: 77 09 00 00 03 00 00 00 r9 >>= 3

So, I'll add support for bit shifts operations and will notify you once it's done!

[pchaigno]

@osinstom I've updated the branch. Support for bitwise OR was needed on top of shifts for the above example to work. Please tell me if there are any issues remaining.

[osinstom]

I've just checked the above example and it works! Tomorrow, I will check other P4 programs.

[osinstom]

Paul, I've just checked the other programs. Good news: The problem with invalid access to packet is gone!

However, when testing e.g. packet-counter.p4 I encountered following error message:

2020-01-29T06:41:27.568Z|01515|bpf|WARN|Failed to load code: forbidden pointer arithmetic at PC 328

My quick analysis showed that it only occurs if the header's stack has several protocols. In the below example, if I would remove ICMP handling in deparser the verifier would accept the program. Programs with just Ethernet + IP are accepted.

Could you please take another look at the problem? Sorry for bothering you!

packet-counter.c

/* Automatically generated by p4c-ubpf from ../examples/packet-counter.p4 on Wed Jan 29 07:39:00 2020
 */
#include "packet-counter.h"
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include "ubpf_common.h"

#define BPF_MASK(t, w) ((((t)(1)) << (w)) - (t)1)
#define BYTES(w) ((w) / 8)

void* memcpy(void* dest, const void* src, size_t num);

static void *(*ubpf_map_lookup)(const void *, const void *) = (void *)1;
static int (*ubpf_map_update)(void *, const void *, void *) = (void *)2;
static int (*ubpf_map_delete)(void *, const void *) = (void *)3;
static int (*ubpf_map_add)(void *, const void *) = (void *)4;
static uint64_t (*ubpf_time_get_ns)() = (void *)5;
static uint32_t (*ubpf_hash)(const void *, uint64_t) = (void *)6;
static void (*ubpf_printf)(const char *fmt, ...) = (void *)7;
static void *(*ubpf_packet_data)(const void *) = (void *)9;
static void *(*ubpf_adjust_head)(const void *, uint64_t) = (void *)8;

#define write_partial(a, w, s, v) do { *((uint8_t*)a) = ((*((uint8_t*)a)) & ~(BPF_MASK(uint8_t, w) << s)) | (v << s) ; } while (0)
#define write_byte(base, offset, v) do { *(uint8_t*)((base) + (offset)) = (v); } while (0)

static uint32_t
bpf_htonl(uint32_t val) {
    return htonl(val);
}
static uint16_t
bpf_htons(uint16_t val) {
    return htons(val);
}
static uint64_t
bpf_htonll(uint64_t val) {
    return htonll(val);
}

uint64_t entry(void *ctx, uint64_t pkt_len){
    void *pkt = ubpf_packet_data(ctx);
    struct Headers_t hdr = {
        .ethernet = {
            .ebpf_valid = 0
        },
        .ipv4 = {
            .ebpf_valid = 0
        },
        .icmp = {
            .ebpf_valid = 0
        },
    };
    struct metadata meta = {
    };
    int packetOffsetInBits = 0;
    uint8_t pass = 1;
    unsigned char ebpf_byte;
    int head_len = 0;

    if (pkt_len < sizeof(struct Headers_t)) {
        return 0;
    }

    goto start;
    start: {
        /* extract(hdr.ethernet)*/

        hdr.ethernet.dstAddr = (uint64_t)((load_dword(pkt, BYTES(packetOffsetInBits)) >> 16) & BPF_MASK(uint64_t, 48));
        packetOffsetInBits += 48;

        hdr.ethernet.srcAddr = (uint64_t)((load_dword(pkt, BYTES(packetOffsetInBits)) >> 16) & BPF_MASK(uint64_t, 48));
        packetOffsetInBits += 48;

        hdr.ethernet.etherType = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        hdr.ethernet.ebpf_valid = 1;
        switch (hdr.ethernet.etherType) {
            case 0x800: goto parse_ipv4;
            default: goto accept;
        }
    }
    parse_ipv4: {
        /* extract(hdr.ipv4)*/

        hdr.ipv4.version = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits)) >> 4) & BPF_MASK(uint8_t, 4));
        packetOffsetInBits += 4;

        hdr.ipv4.ihl = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))) & BPF_MASK(uint8_t, 4));
        packetOffsetInBits += 4;

        hdr.ipv4.diffserv = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        hdr.ipv4.totalLen = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        hdr.ipv4.identification = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        hdr.ipv4.flags = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits)) >> 5) & BPF_MASK(uint8_t, 3));
        packetOffsetInBits += 3;

        hdr.ipv4.fragOffset = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))) & BPF_MASK(uint16_t, 13));
        packetOffsetInBits += 13;

        hdr.ipv4.ttl = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        hdr.ipv4.protocol = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        hdr.ipv4.hdrChecksum = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        hdr.ipv4.srcAddr = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 32;

        hdr.ipv4.dstAddr = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 32;

        hdr.ipv4.ebpf_valid = 1;
        switch (hdr.ipv4.protocol) {
            case 1: goto parce_icmp;
            default: goto accept;
        }
    }
    parce_icmp: {
        /* extract(hdr.icmp)*/

        hdr.icmp.type = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        hdr.icmp.code = (uint8_t)((load_byte(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 8;

        hdr.icmp.checksum = (uint16_t)((load_half(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 16;

        hdr.icmp.rest = (uint32_t)((load_word(pkt, BYTES(packetOffsetInBits))));
        packetOffsetInBits += 32;

        hdr.icmp.ebpf_valid = 1;
        goto accept;
    }

    reject: { return 0; }

    accept:
    {
        uint32_t* tmp;
        {

            uint32_t key_local_var = 0;
            tmp = ubpf_map_lookup(&packet_counter_reg_0, &key_local_var);
            if (tmp != NULL) {

                uint32_t key_local_var_0 = 0;
                uint32_t value_local_var = (*tmp + 1);
                ubpf_map_update(&packet_counter_reg_0, &key_local_var_0, &value_local_var);

            }
        }
    }
    packetOffsetInBits = 0;
    pkt = ubpf_adjust_head(ctx, head_len);
    if (hdr.ethernet.ebpf_valid) {
        hdr.ethernet.dstAddr = htonll(hdr.ethernet.dstAddr << 16);
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[4];
        write_byte(pkt, BYTES(packetOffsetInBits) + 4, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.dstAddr))[5];
        write_byte(pkt, BYTES(packetOffsetInBits) + 5, (ebpf_byte));
        packetOffsetInBits += 48;

        hdr.ethernet.srcAddr = htonll(hdr.ethernet.srcAddr << 16);
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[4];
        write_byte(pkt, BYTES(packetOffsetInBits) + 4, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.srcAddr))[5];
        write_byte(pkt, BYTES(packetOffsetInBits) + 5, (ebpf_byte));
        packetOffsetInBits += 48;

        hdr.ethernet.etherType = bpf_htons(hdr.ethernet.etherType);
        ebpf_byte = ((char*)(&hdr.ethernet.etherType))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ethernet.etherType))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

    }
;    if (hdr.ipv4.ebpf_valid) {
        ebpf_byte = ((char*)(&hdr.ipv4.version))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 4, 4, (ebpf_byte >> 0));
        packetOffsetInBits += 4;

        ebpf_byte = ((char*)(&hdr.ipv4.ihl))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 4, 0, (ebpf_byte >> 0));
        packetOffsetInBits += 4;

        ebpf_byte = ((char*)(&hdr.ipv4.diffserv))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        hdr.ipv4.totalLen = bpf_htons(hdr.ipv4.totalLen);
        ebpf_byte = ((char*)(&hdr.ipv4.totalLen))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.totalLen))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        hdr.ipv4.identification = bpf_htons(hdr.ipv4.identification);
        ebpf_byte = ((char*)(&hdr.ipv4.identification))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.identification))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        ebpf_byte = ((char*)(&hdr.ipv4.flags))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 3, 5, (ebpf_byte >> 0));
        packetOffsetInBits += 3;

        hdr.ipv4.fragOffset = bpf_htons(hdr.ipv4.fragOffset << 3);
        ebpf_byte = ((char*)(&hdr.ipv4.fragOffset))[0];
        write_partial(pkt + BYTES(packetOffsetInBits) + 0, 5, 0, (ebpf_byte >> 3));
        write_partial(pkt + BYTES(packetOffsetInBits) + 0 + 1, 3, 5, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.fragOffset))[1];
        write_partial(pkt + BYTES(packetOffsetInBits) + 1, 5, 0, (ebpf_byte >> 3));
        packetOffsetInBits += 13;

        ebpf_byte = ((char*)(&hdr.ipv4.ttl))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        ebpf_byte = ((char*)(&hdr.ipv4.protocol))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        hdr.ipv4.hdrChecksum = bpf_htons(hdr.ipv4.hdrChecksum);
        ebpf_byte = ((char*)(&hdr.ipv4.hdrChecksum))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.hdrChecksum))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        hdr.ipv4.srcAddr = htonl(hdr.ipv4.srcAddr);
        ebpf_byte = ((char*)(&hdr.ipv4.srcAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.srcAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.srcAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.srcAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        packetOffsetInBits += 32;

        hdr.ipv4.dstAddr = htonl(hdr.ipv4.dstAddr);
        ebpf_byte = ((char*)(&hdr.ipv4.dstAddr))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.dstAddr))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.dstAddr))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.ipv4.dstAddr))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        packetOffsetInBits += 32;

    }
;    if (hdr.icmp.ebpf_valid) {
        ebpf_byte = ((char*)(&hdr.icmp.type))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        ebpf_byte = ((char*)(&hdr.icmp.code))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        packetOffsetInBits += 8;

        hdr.icmp.checksum = bpf_htons(hdr.icmp.checksum);
        ebpf_byte = ((char*)(&hdr.icmp.checksum))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.icmp.checksum))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        packetOffsetInBits += 16;

        hdr.icmp.rest = htonl(hdr.icmp.rest);
        ebpf_byte = ((char*)(&hdr.icmp.rest))[0];
        write_byte(pkt, BYTES(packetOffsetInBits) + 0, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.icmp.rest))[1];
        write_byte(pkt, BYTES(packetOffsetInBits) + 1, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.icmp.rest))[2];
        write_byte(pkt, BYTES(packetOffsetInBits) + 2, (ebpf_byte));
        ebpf_byte = ((char*)(&hdr.icmp.rest))[3];
        write_byte(pkt, BYTES(packetOffsetInBits) + 3, (ebpf_byte));
        packetOffsetInBits += 32;

    }
;    if (pass)
        return 1;
    else
        return 0;
}

packet-counter.h

/* Automatically generated by p4c-ubpf from ../examples/packet-counter.p4 on Wed Jan 29 07:39:00 2020
 */
#ifndef _P4_GEN_HEADER_
#define _P4_GEN_HEADER_
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include "ubpf_common.h"

struct Ethernet_h {
    uint64_t dstAddr; /* EthernetAddress */
    uint64_t srcAddr; /* EthernetAddress */
    uint16_t etherType; /* bit<16> */
    uint8_t ebpf_valid;
};

struct IPv4_h {
    uint8_t version; /* bit<4> */
    uint8_t ihl; /* bit<4> */
    uint8_t diffserv; /* bit<8> */
    uint16_t totalLen; /* bit<16> */
    uint16_t identification; /* bit<16> */
    uint8_t flags; /* bit<3> */
    uint16_t fragOffset; /* bit<13> */
    uint8_t ttl; /* bit<8> */
    uint8_t protocol; /* bit<8> */
    uint16_t hdrChecksum; /* bit<16> */
    uint32_t srcAddr; /* IPv4Address */
    uint32_t dstAddr; /* IPv4Address */
    uint8_t ebpf_valid;
};

struct icmp_t {
    uint8_t type; /* bit<8> */
    uint8_t code; /* bit<8> */
    uint16_t checksum; /* bit<16> */
    uint32_t rest; /* bit<32> */
    uint8_t ebpf_valid;
};

struct Headers_t {
    struct Ethernet_h ethernet; /* Ethernet_h */
    struct IPv4_h ipv4; /* IPv4_h */
    struct icmp_t icmp; /* icmp_t */
};

struct metadata {
};

enum ubpf_map_type {
    UBPF_MAP_TYPE_HASHMAP = 4,
};
struct ubpf_map_def {
    enum ubpf_map_type type;
    unsigned int key_size;
    unsigned int value_size;
    unsigned int max_entries;
    unsigned int nb_hash_functions;
};

struct ubpf_map_def packet_counter_reg_0 = {
    .type = UBPF_MAP_TYPE_HASHMAP,
    .key_size = sizeof(uint32_t),
    .value_size = sizeof(uint32_t),
    .max_entries = 1,
    .nb_hash_functions = 0,
};
#endif

[pchaigno]

Ah, that one was fun! It was failing because this program uses a double-word load instruction to load an immediate. Neither the verifier nor the loader supported that; they both supposed that all double-word load instructions were meant to load maps. It's now fixed.

[osinstom]

Now, it works great, thanks again!