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

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

[Wei Fang]

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;
}

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

[Pablo Neira Ayuso]

On Tue, Aug 11, 2026 at 05:22:01PM +0800, Wei Fang wrote:
[...]
> 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.

What do you mean by "hides the ordering"? It sounds negative, actually
what is does is to pass a list of elements to the kernel that make
sense when interpreting the interval?

Ordering is paramount in this loose interface, your program does:

        ...
        put_interval_elem(&q, 0, E1_END, 1);
        put_interval_elem(&q, 1, E1, 0);

Deleting E1_END element before E1, makes no sense, the interval
representation is reversed.

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

[Wei Fang]

Hi,

Understood - thank you for the explanation.  I accept the
ordering point: the reproducer's delete message sent the END
element before the START element of its interval, which does not
follow the element ordering this interface relies on.

Thanks again for your time.

Best regards,