[nf_tables] rbtree interval set: in one batch, re-adding element E0 makes deleting an unrelated interval E1 fail with -ENOENT

The following nf_tables issue was found by metamorphic testing on
linux-next 7.2.0-rc6-next-20260803 (x86_64) and reproduced on four
independent VMs.  The reproducer is a single self-contained C program
that uses only the raw netlink API (no nft CLI involved).

This report is about the rbtree interval-set backend: re-adding an
existing interval element in the same batch as deleting an unrelated
interval makes the delete fail with -ENOENT, although the same two
operations succeed when sent separately.

Problem
-------
On an interval set that already contains two intervals, one batch
that does both of the following fails on the second operation:

1. re-add element E0 without NLM_F_EXCL (update semantics);
2. delete a different interval E1.

The delete returns -ENOENT.  Sending the same two operations in
separate messages succeeds.  A transaction must not change what an
operation does: batched and unbatched execution must behave the same.

Steps to reproduce
------------------
One batch on an ipv4_addr INTERVAL set with two existing intervals:

1. re-add E0 = [10.0.1.0..10.0.2.0) without NLM_F_EXCL;
2. delete E1 = [10.0.2.0..10.0.3.0).

Raw netlink is required: the nft CLI re-sorts interval elements and
hides the ordering.

Expected vs. actual
-------------------
expected (observed when sent separately): all operations ack 0
actual (single batch): [0, 0, 0, 0, -2] - the delete of E1 fails
with -ENOENT

Root cause
----------
net/netfilter/nft_set_rbtree.c: when the re-add takes the in-batch
EEXIST path, nft_rbtree_insert() records the matched start element
in priv->start_rbe_cookie (nft_rbtree_set_start_cookie()).  Later in
the same batch, deleting E1 reaches the END node of the interval
being deleted and calls nft_rbtree_deactivate_same_interval(), which
compares against that cookie.  The cookie still points at E0's start
element instead of E1's, the comparison fails, the deactivate
returns NULL, and __nft_setelem_deactivate() (nf_tables_api.c)
turns that into -ENOENT.

Reproducer
---------------

#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h>
#include <linux/netfilter/nf_tables.h>
#include <linux/netfilter/nfnetlink.h>
#include <linux/netlink.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <time.h>
#include <unistd.h>

/* NFT_MSG_* enum values come directly from <linux/netfilter/nf_tables.h>
 * (NEWTABLE=0, GETTABLE=1, DELTABLE=2, NEWCHAIN=3, ..., NEWRULE=6) --
 * do not #define the same names; that would break the header enum. */
#define NFT_MSG_TYPE(s, m) (((s) << 8) | (m))

/* ---------------- encoding helpers (wire format matches the Python
version) ---------------- */

static void put_u16(char **p, uint16_t v) { memcpy(*p, &v, 2); *p += 2; }
static void put_u32(char **p, uint32_t v) { memcpy(*p, &v, 4); *p += 4; }

/* attr: little-endian len/type header + payload, 4-byte tail
alignment (len excludes pad) */
static void put_attr(char **p, uint16_t type, const void *data, uint16_t len)
{
    put_u16(p, 4 + len);
    put_u16(p, type);
    if (len)
        memcpy(*p, data, len);
    *p += len;
    while ((uintptr_t)*p % 4) {
        **p = 0;
        (*p)++;
    }
}

static void put_attr_be32(char **p, uint16_t type, uint32_t v)
{
    uint32_t be = htonl(v);
    put_attr(p, type, &be, 4);
}

static void put_attr_str(char **p, uint16_t type, const char *s)
{
    put_attr(p, type, s, strlen(s) + 1);
}

static void put_nfgenmsg(char **p, uint8_t family, uint16_t res_id)
{
    char *q = *p;
    q[0] = family;
    q[1] = 0;
    uint16_t be = htons(res_id);
    memcpy(q + 2, &be, 2);
    *p += 4;
}

/* nlmsghdr + nfgenmsg + attrs; returns total length including header */
static int build_msg(char *buf, uint16_t type, uint16_t flags, uint32_t seq,
                     uint8_t family, uint16_t res_id, char *attrs, int alen)
{
    char *p = buf;
    put_u32(&p, 0);
    put_u16(&p, type);
    put_u16(&p, flags);
    put_u32(&p, seq);
    put_u32(&p, 0);
    put_nfgenmsg(&p, family, res_id);
    memcpy(p, attrs, alen);
    p += alen;
    int total = (int)(p - buf);
    memcpy(buf, &total, 4);
    return total;
}

/* BEGIN/END: nlmsghdr(type=0x10/0x11) + nfgenmsg(res=htons(10)) */
static int build_batch_frame(char *buf, uint16_t type, uint16_t flags,
                             uint32_t seq)
{
    return build_msg(buf, type, flags, seq, 0, NFNL_SUBSYS_NFTABLES, NULL, 0);
}

/* ---------------- netlink session (same as b16.c) ---------------- */

static int nl_fd = -1;

static void nl_open(void)
{
    nl_fd = socket(AF_NETLINK, SOCK_RAW, NETLINK_NETFILTER);
    if (nl_fd < 0) { perror("socket"); exit(1); }
    struct sockaddr_nl sa = { .nl_family = AF_NETLINK };
    if (bind(nl_fd, (struct sockaddr *)&sa, sizeof(sa)) < 0) {
        perror("bind"); exit(1);
    }
    int fl = fcntl(nl_fd, F_GETFL, 0);
    fcntl(nl_fd, F_SETFL, fl | O_NONBLOCK);
}

static int collect_acks(uint32_t *wanted, int nwanted, int *errs,
                        int wait_ms)
{
    int got = 0;
    struct timeval tv = { .tv_sec = wait_ms / 1000,
                          .tv_usec = (wait_ms % 1000) * 1000 };
    setsockopt(nl_fd, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof(tv));
    int deadline = (int)time(NULL) + wait_ms / 1000 + 1;
    while (got < nwanted && time(NULL) < deadline) {
        char buf[65536];
        int n = recv(nl_fd, buf, sizeof(buf), 0);
        if (n < 0) {
            if (errno == EAGAIN || errno == EWOULDBLOCK) continue;
            break;
        }
        for (int off = 0; off + 16 <= n;) {
            struct nlmsghdr *h = (struct nlmsghdr *)(buf + off);
            int len = h->nlmsg_len;
            if (len < 16 || off + len > n) break;
            if (h->nlmsg_type == NLMSG_ERROR && len >= 20) {
                struct nlmsgerr *e = (struct nlmsgerr *)(h + 1);
                for (int i = 0; i < nwanted; i++) {
                    if (wanted[i] == h->nlmsg_seq && errs[i] == 0x7fffffff) {
                        errs[i] = e->error;
                        got++;
                        break;
                    }
                }
            }
            off += NLMSG_ALIGN(len);
        }
    }
    return got;
}

static int E(int v) { return v == 0x7fffffff ? -1 : v; }

/* send batch (BEGIN + n body msgs + END); collect body acks into errs[] */
static void send_and_collect(char msgs[][512], int *lens, uint32_t *seqs,
                             int n, uint32_t begin_seq, uint32_t end_seq,
                             int *errs, int wait_ms)
{
    char blob[4096], *p = blob;
    int b = build_batch_frame(p, NFNL_MSG_BATCH_BEGIN, NLM_F_REQUEST,
                              begin_seq);
    p += b;
    for (int i = 0; i < n; i++) { memcpy(p, msgs[i], lens[i]); p += lens[i]; }
    int e = build_batch_frame(p, NFNL_MSG_BATCH_END, NLM_F_REQUEST, end_seq);
    p += e;
    send(nl_fd, blob, (int)(p - blob), 0);
    for (int i = 0; i < n; i++) errs[i] = 0x7fffffff;
    collect_acks(seqs, n, errs, wait_ms);
}

/* DELTABLE inside a batch; deleting a nonexistent table is harmless
(-ENOENT), used to clean leftovers */
static void del_table(uint8_t family, const char *tbl)
{
    char blob[1024], *p = blob;
    int b = build_batch_frame(p, NFNL_MSG_BATCH_BEGIN, NLM_F_REQUEST, 900);
    p += b;
    char attrs[64], *q = attrs;
    put_attr_str(&q, NFTA_TABLE_NAME, tbl);
    int len = build_msg(p, NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES, NFT_MSG_DELTABLE),
                        NLM_F_REQUEST | NLM_F_ACK, 901, family, 0, attrs,
                        (int)(q - attrs));
    p += len;
    int e = build_batch_frame(p, NFNL_MSG_BATCH_END, NLM_F_REQUEST, 902);
    p += e;
    send(nl_fd, blob, (int)(p - blob), 0);
    uint32_t w = 901;
    int er = 0x7fffffff;
    collect_acks(&w, 1, &er, 500);
}

/* ---------------- scenario construction ---------------- */

/* interval endpoints (network-order bytes, same as v_a1.py) */
static const uint8_t E0[4]     = { 0x0a, 0x00, 0x01, 0x00 };  /* 10.0.1.0 */
static const uint8_t E0_END[4] = { 0x0a, 0x00, 0x02, 0x00 };  /* 10.0.2.0 */
static const uint8_t E1[4]     = { 0x0a, 0x00, 0x02, 0x00 };  /* 10.0.2.0 */
static const uint8_t E1_END[4] = { 0x0a, 0x00, 0x03, 0x00 };  /* 10.0.3.0 */

/* Single interval element: attr type (1+idx), payload = [FLAGS(3)=1 for END
 * only] + KEY(1){ DATA(1)=4-byte key } (elems_raw_interval encoding).
 * Containers never set NLA_F_NESTED (kernel nla_parse_nested_deprecated
 * does not check the flag). */
static void put_interval_elem(char **p, int idx, const uint8_t key[4],
                              int is_end)
{
    char inner[64], *q = inner;
    if (is_end)
        put_attr_be32(&q, NFTA_SET_ELEM_FLAGS, NFT_SET_ELEM_INTERVAL_END);
    char kd[16], *k = kd;
    put_attr(&k, NFTA_DATA_VALUE, key, 4);
    put_attr(&q, NFTA_SET_ELEM_KEY, kd, (int)(k - kd));
    put_attr(p, 1 + idx, inner, (int)(q - inner));
}

/* install batch: table t + set s(interval, ipv4_addr) + 4 interval elements */
static void mk_install(char (*msgs)[512], int *lens, uint32_t *seqs)
{
    char attrs[256], *p;
    int alen;

    p = attrs;
    put_attr_str(&p, NFTA_TABLE_NAME, "t");
    alen = (int)(p - attrs);
    lens[0] = build_msg(msgs[0], NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES,
                        NFT_MSG_NEWTABLE),
                        NLM_F_REQUEST | NLM_F_ACK | NLM_F_CREATE, seqs[0], 2,
                        0, attrs, alen);

    /* NEWSET: TABLE(1) NAME(2) FLAGS(3)=INTERVAL KEY_TYPE(4)=7 KEY_LEN(5)=4
     * ID(10)=0 (NFTA_SET_ID is mandatory) */
    p = attrs;
    put_attr_str(&p, NFTA_SET_TABLE, "t");
    put_attr_str(&p, NFTA_SET_NAME, "s");
    put_attr_be32(&p, NFTA_SET_FLAGS, NFT_SET_INTERVAL);
    put_attr_be32(&p, NFTA_SET_KEY_TYPE, 7);      /* ipv4_addr */
    put_attr_be32(&p, NFTA_SET_KEY_LEN, 4);
    put_attr_be32(&p, NFTA_SET_ID, 0);
    alen = (int)(p - attrs);
    lens[1] = build_msg(msgs[1], NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES,
                        NFT_MSG_NEWSET),
                        NLM_F_REQUEST | NLM_F_ACK | NLM_F_CREATE, seqs[1], 2,
                        0, attrs, alen);

    /* NEWSETELEM: TABLE(1) NAME(2) ELEMENTS(3){ elems type=1..4 } */
    p = attrs;
    put_attr_str(&p, NFTA_SET_ELEM_LIST_TABLE, "t");
    put_attr_str(&p, NFTA_SET_ELEM_LIST_SET, "s");
    {
        char elems[256], *q = elems;
        const uint8_t *keys[4] = { E0, E0_END, E1, E1_END };
        int ends[4] = { 0, 1, 0, 1 };
        for (int i = 0; i < 4; i++)
            put_interval_elem(&q, i, keys[i], ends[i]);
        put_attr(&p, NFTA_SET_ELEM_LIST_ELEMENTS, elems, (int)(q - elems));
    }
    alen = (int)(p - attrs);
    lens[2] = build_msg(msgs[2], NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES,
                        NFT_MSG_NEWSETELEM),
                        NLM_F_REQUEST | NLM_F_ACK | NLM_F_CREATE, seqs[2], 2,
                        0, attrs, alen);
}

/* re-add e0 (single point, no EXCL -> update semantics, errno 0) */
static void mk_readd(char *buf, int *len, uint32_t seq)
{
    char attrs[256], *p = attrs;
    put_attr_str(&p, NFTA_SET_ELEM_LIST_TABLE, "t");
    put_attr_str(&p, NFTA_SET_ELEM_LIST_SET, "s");
    {
        char elems[64], *q = elems;
        put_interval_elem(&q, 0, E0, 0);
        put_attr(&p, NFTA_SET_ELEM_LIST_ELEMENTS, elems, (int)(q - elems));
    }
    *len = build_msg(buf, NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES,
NFT_MSG_NEWSETELEM),
                     NLM_F_REQUEST | NLM_F_ACK | NLM_F_CREATE, seq, 2, 0,
                     attrs, (int)(p - attrs));
}

/* delete interval 2 (END element first, then start, same order as v_a1.py) */
static void mk_del(char *buf, int *len, uint32_t seq)
{
    char attrs[256], *p = attrs;
    put_attr_str(&p, NFTA_SET_ELEM_LIST_TABLE, "t");
    put_attr_str(&p, NFTA_SET_ELEM_LIST_SET, "s");
    {
        char elems[64], *q = elems;
        put_interval_elem(&q, 0, E1_END, 1);
        put_interval_elem(&q, 1, E1, 0);
        put_attr(&p, NFTA_SET_ELEM_LIST_ELEMENTS, elems, (int)(q - elems));
    }
    *len = build_msg(buf, NFT_MSG_TYPE(NFNL_SUBSYS_NFTABLES,
NFT_MSG_DELSETELEM),
                     NLM_F_REQUEST | NLM_F_ACK, seq, 2, 0, attrs,
                     (int)(p - attrs));
}

/* ---------------- main ---------------- */

int main(void)
{
    char msgs[5][512];
    int lens[5];
    uint32_t seqs[5];
    int errs[5];

    nl_open();
    del_table(2, "t");              /* clean up leftovers from previous run */

    /* control batch: install only -> all errno 0 */
    seqs[0] = 11; seqs[1] = 12; seqs[2] = 13;
    mk_install(msgs, lens, seqs);
    send_and_collect(msgs, lens, seqs, 3, 10, 14, errs, 1500);
    printf("control ack errno: [%d, %d, %d] (expected all 0)\n",
           E(errs[0]), E(errs[1]), E(errs[2]));
    del_table(2, "t");

    /* variant batch: install + re-add e0 + delete interval 2 -> readd
0, delete should be 0; bug: delete -2 */
    seqs[0] = 101; seqs[1] = 102; seqs[2] = 103;
    mk_install(msgs, lens, seqs);
    seqs[3] = 104;
    mk_readd(msgs[3], &lens[3], seqs[3]);
    seqs[4] = 105;
    mk_del(msgs[4], &lens[4], seqs[4]);
    send_and_collect(msgs, lens, seqs, 5, 100, 106, errs, 2000);
    int readd = E(errs[3]), dele = E(errs[4]);
    printf("variant ack errno: [%d, %d, %d, %d, %d] (last two =
re-add/delete)\n",
           E(errs[0]), E(errs[1]), E(errs[2]), readd, dele);
    del_table(2, "t");

    if (readd == 0 && dele == -2)
        printf("REPRODUCED: in-batch re-add of e0 makes deleting interval 2 "
               "fail with -ENOENT (rbtree start_rbe_cookie intra-batch
pollution)\n");
    else if (readd == 0 && dele == 0)
        printf("NOT_REPRODUCED: delete succeeds after the re-add "
               "(no pollution)\n");
    else
        printf("UNAVAILABLE: unexpected observation (readd=%d, del=%d)\n",
               readd, dele);

    close(nl_fd);
    return 0;
}