/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2014-2025 Yandex LLC
 * Copyright (c) 2014 Alexander V. Chernikov
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
/*
 * Multi-field value support for ipfw tables.
 *
 * This file contains necessary functions to convert
 * large multi-field values into u32 indices suitable to be fed
 * to various table algorithms. Other machinery like proper refcounting,
 * internal structures resizing are also kept here.
 */

#include "opt_ipfw.h"

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/malloc.h>
#include <sys/kernel.h>
#include <sys/hash.h>
#include <sys/lock.h>
#include <sys/rwlock.h>
#include <sys/rmlock.h>
#include <sys/socket.h>
#include <sys/socketvar.h>
#include <sys/queue.h>
#include <net/if.h>     /* ip_fw.h requires IFNAMSIZ */

#include <netinet/in.h>
#include <netinet/ip_var.h>     /* struct ipfw_rule_ref */
#include <netinet/ip_fw.h>

#include <netpfil/ipfw/ip_fw_private.h>
#include <netpfil/ipfw/ip_fw_table.h>

static uint32_t hash_table_value(struct namedobj_instance *ni, const void *key,
    uint32_t kopt);
static int cmp_table_value(struct named_object *no, const void *key,
    uint32_t kopt);

static int list_table_values(struct ip_fw_chain *ch, ip_fw3_opheader *op3,
    struct sockopt_data *sd);

static struct ipfw_sopt_handler scodes[] = {
    { IP_FW_TABLE_VLIST, IP_FW3_OPVER, HDIR_GET, list_table_values },
};

#define CHAIN_TO_VI(chain)      (CHAIN_TO_TCFG(chain)->valhash)

struct table_val_link
{
        struct named_object     no;
        struct table_value      *pval;  /* Pointer to real table value */
};
#define VALDATA_START_SIZE      64      /* Allocate 64-items array by default */
#define VALDATA_HASH_SIZE       65536

struct vdump_args {
        struct ip_fw_chain *ch;
        struct sockopt_data *sd;
        struct table_value *pval;
        int error;
};

static uint32_t
hash_table_value(struct namedobj_instance *ni, const void *key, uint32_t kopt)
{

        return (hash32_buf(key, 56, 0));
}

static int
cmp_table_value(struct named_object *no, const void *key, uint32_t kopt)
{

        return (memcmp(((struct table_val_link *)no)->pval, key, 56));
}

static void
mask_table_value(struct table_value *src, struct table_value *dst,
    uint32_t mask)
{
#define _MCPY(f, b)     if ((mask & (b)) != 0) { dst->f = src->f; }

        memset(dst, 0, sizeof(*dst));
        _MCPY(tag, IPFW_VTYPE_TAG);
        _MCPY(pipe, IPFW_VTYPE_PIPE);
        _MCPY(divert, IPFW_VTYPE_DIVERT);
        _MCPY(skipto, IPFW_VTYPE_SKIPTO);
        _MCPY(netgraph, IPFW_VTYPE_NETGRAPH);
        _MCPY(fib, IPFW_VTYPE_FIB);
        _MCPY(nat, IPFW_VTYPE_NAT);
        _MCPY(limit, IPFW_VTYPE_LIMIT);
        _MCPY(mark, IPFW_VTYPE_MARK);
        _MCPY(dscp, IPFW_VTYPE_DSCP);
        _MCPY(nh4, IPFW_VTYPE_NH4);
        _MCPY(nh6, IPFW_VTYPE_NH6);
        _MCPY(zoneid, IPFW_VTYPE_NH6);
#undef  _MCPY
}

static void
get_value_ptrs(struct ip_fw_chain *ch, struct table_config *tc,
    struct table_value **ptv, struct namedobj_instance **pvi)
{
        struct table_value *pval;
        struct namedobj_instance *vi;

        if (tc->vshared != 0) {
                pval = (struct table_value *)ch->valuestate;
                vi = CHAIN_TO_VI(ch);
        } else {
                pval = NULL;
                vi = NULL;
                //pval = (struct table_value *)&tc->ti.data;
        }

        if (ptv != NULL)
                *ptv = pval;
        if (pvi != NULL)
                *pvi = vi;
}

/*
 * Update pointers to real values after @pval change.
 */
static int
update_tvalue(struct namedobj_instance *ni, struct named_object *no, void *arg)
{
        struct vdump_args *da;
        struct table_val_link *ptv;
        struct table_value *pval;

        da = (struct vdump_args *)arg;
        ptv = (struct table_val_link *)no;

        pval = da->pval;
        ptv->pval = &pval[ptv->no.kidx];
        ptv->no.name = (char *)&pval[ptv->no.kidx];
        return (0);
}

/*
 * Grows value storage shared among all tables.
 * Notifies other running adds on @ch shared storage resize.
 * Note function does not guarantee that free space
 * will be available after invocation, so one caller needs
 * to roll cycle himself.
 *
 * Returns 0 if case of no errors.
 */
static int
resize_shared_value_storage(struct ip_fw_chain *ch)
{
        struct tables_config *tcfg;
        struct namedobj_instance *vi;
        struct table_value *pval, *valuestate, *old_valuestate;
        void *new_idx;
        struct vdump_args da;
        int new_blocks;
        int val_size, val_size_old;

        IPFW_UH_WLOCK_ASSERT(ch);

        valuestate = NULL;
        new_idx = NULL;

        pval = (struct table_value *)ch->valuestate;
        vi = CHAIN_TO_VI(ch);
        tcfg = CHAIN_TO_TCFG(ch);

        val_size = tcfg->val_size * 2;

        if (val_size == (1 << 30))
                return (ENOSPC);

        valuestate = malloc(sizeof(struct table_value) * val_size, M_IPFW,
            M_WAITOK | M_ZERO);
        ipfw_objhash_bitmap_alloc(val_size, (void *)&new_idx,
            &new_blocks);

        /*
         * Check if we still need to resize
         */
        if (tcfg->val_size >= val_size)
                goto done;

        /* Update pointers and notify everyone we're changing @ch */
        pval = (struct table_value *)ch->valuestate;

        /* Good. Let's merge */
        memcpy(valuestate, pval, sizeof(struct table_value) * tcfg->val_size);
        ipfw_objhash_bitmap_merge(CHAIN_TO_VI(ch), &new_idx, &new_blocks);

        IPFW_WLOCK(ch);
        /* Change pointers */
        old_valuestate = ch->valuestate;
        ch->valuestate = valuestate;
        valuestate = old_valuestate;
        ipfw_objhash_bitmap_swap(CHAIN_TO_VI(ch), &new_idx, &new_blocks);

        val_size_old = tcfg->val_size;
        tcfg->val_size = val_size;
        val_size = val_size_old;
        IPFW_WUNLOCK(ch);
        /* Update pointers to reflect resize */
        memset(&da, 0, sizeof(da));
        da.pval = (struct table_value *)ch->valuestate;
        ipfw_objhash_foreach(vi, update_tvalue, &da);

done:
        free(valuestate, M_IPFW);
        ipfw_objhash_bitmap_free(new_idx, new_blocks);

        return (0);
}

/*
 * Drops reference for table value with index @kidx, stored in @pval and
 * @vi. Frees value if it has no references.
 */
static void
unref_table_value(struct namedobj_instance *vi, struct table_value *pval,
    uint32_t kidx)
{
        struct table_val_link *ptvl;

        KASSERT(pval[kidx].refcnt > 0, ("Refcount is 0 on kidx %d", kidx));
        if (--pval[kidx].refcnt > 0)
                return;

        /* Last reference, delete item */
        ptvl = (struct table_val_link *)ipfw_objhash_lookup_kidx(vi, kidx);
        KASSERT(ptvl != NULL, ("lookup on value kidx %d failed", kidx));
        ipfw_objhash_del(vi, &ptvl->no);
        ipfw_objhash_free_idx(vi, kidx);
        free(ptvl, M_IPFW);
}

struct flush_args {
        struct ip_fw_chain *ch;
        struct table_algo *ta;
        struct table_info *ti;
        void *astate;
        ipfw_obj_tentry tent;
};

static int
unref_table_value_cb(void *e, void *arg)
{
        struct flush_args *fa;
        struct ip_fw_chain *ch;
        struct table_algo *ta;
        ipfw_obj_tentry *tent;
        int error;

        fa = (struct flush_args *)arg;

        ta = fa->ta;
        memset(&fa->tent, 0, sizeof(fa->tent));
        tent = &fa->tent;
        error = ta->dump_tentry(fa->astate, fa->ti, e, tent);
        if (error != 0)
                return (error);

        ch = fa->ch;

        unref_table_value(CHAIN_TO_VI(ch),
            (struct table_value *)ch->valuestate, tent->v.kidx);

        return (0);
}

/*
 * Drop references for each value used in @tc.
 */
void
ipfw_unref_table_values(struct ip_fw_chain *ch, struct table_config *tc,
    struct table_algo *ta, void *astate, struct table_info *ti)
{
        struct flush_args fa;

        IPFW_UH_WLOCK_ASSERT(ch);

        memset(&fa, 0, sizeof(fa));
        fa.ch = ch;
        fa.ta = ta;
        fa.astate = astate;
        fa.ti = ti;

        ta->foreach(astate, ti, unref_table_value_cb, &fa);
}

/*
 * Allocate new value index in either shared or per-table array.
 *
 * Returns 0 on success.
 */
static int
alloc_table_vidx(struct ip_fw_chain *ch, struct table_config *tc,
    struct namedobj_instance *vi, uint32_t *pvidx, uint8_t flags)
{
        int error, vlimit;
        uint32_t vidx;

        IPFW_UH_WLOCK_ASSERT(ch);

        if ((error = ipfw_objhash_alloc_idx(vi, &vidx)) != 0 &&
            (error = resize_shared_value_storage(ch)) != 0)
                return (error);

        vlimit = tc->ta->vlimit;
        if (vlimit != 0 && vidx >= vlimit && !(flags & IPFW_CTF_ATOMIC)) {
                /*
                 * Algorithm is not able to store given index.
                 * We have to rollback state, start using
                 * per-table value array or return error
                 * if we're already using it.
                 */
                if (tc->vshared != 0) {
                        /* shared -> per-table  */
                        return (ENOSPC); /* TODO: proper error */
                }

                /* per-table. Fail for now. */
                return (ENOSPC); /* TODO: proper error */
        }

        *pvidx = vidx;
        return (0);
}

/*
 * Drops value reference for unused values (updates, deletes, partially
 * successful adds or rollbacks).
 */
void
ipfw_garbage_table_values(struct ip_fw_chain *ch, struct table_config *tc,
    struct tentry_info *tei, uint32_t count, int rollback)
{
        int i;
        struct tentry_info *ptei;
        struct table_value *pval;
        struct namedobj_instance *vi;

        /*
         * We have two slightly different ADD cases here:
         * either (1) we are successful / partially successful,
         * in that case we need
         * * to ignore ADDED entries values
         * * rollback every other values if atomicity is not
         * * required (either UPDATED since old value has been
         *   stored there, or some failure like EXISTS or LIMIT
         *   or simply "ignored" case.
         *
         * (2): atomic rollback of partially successful operation
         * in that case we simply need to unref all entries.
         *
         * DELETE case is simpler: no atomic support there, so
         * we simply unref all non-zero values.
         */

        /*
         * Get current table value pointers.
         */
        get_value_ptrs(ch, tc, &pval, &vi);

        for (i = 0; i < count; i++) {
                ptei = &tei[i];

                if (ptei->value == 0) {
                        /*
                         * We may be deleting non-existing record.
                         * Skip.
                         */
                        continue;
                }

                if ((ptei->flags & TEI_FLAGS_ADDED) != 0 && rollback == 0) {
                        ptei->value = 0;
                        continue;
                }

                unref_table_value(vi, pval, ptei->value);
                ptei->value = 0;
        }
}

/*
 * Main function used to link values of entries going to be added,
 * to the index. Since we may perform many UH locks drops/acquires,
 * handle changes by checking tablestate "modified" field.
 *
 * Success: return 0.
 */
int
ipfw_link_table_values(struct ip_fw_chain *ch, struct table_config *tc,
    struct tentry_info *tei, uint32_t count, uint8_t flags)
{
        int error, i, found;
        struct namedobj_instance *vi;
        struct tentry_info *ptei;
        uint32_t vidx, vlimit;
        struct table_val_link *ptv;
        struct table_value tval, *pval;

        /*
         * Stage 1: reference all existing values and
         * save their indices.
         */
        IPFW_UH_WLOCK_ASSERT(ch);
        get_value_ptrs(ch, tc, &pval, &vi);

        error = 0;
        found = 0;
        vlimit = tc->ta->vlimit;
        vidx = 0;
        for (i = 0; i < count; i++) {
                ptei = &tei[i];
                ptei->value = 0; /* Ensure value is always 0 in the beginning */
                mask_table_value(ptei->pvalue, &tval, tc->vmask);
                ptv = (struct table_val_link *)ipfw_objhash_lookup_name(vi, 0,
                    (char *)&tval);
                if (ptv == NULL)
                        continue;
                /* Deal with vlimit later */
                if (vlimit > 0 && vlimit <= ptv->no.kidx)
                        continue;

                /* Value found. Bump refcount */
                ptv->pval->refcnt++;
                ptei->value = ptv->no.kidx;
                found++;
        }

        if (count == found) {
                /* We've found all values, no need to create new ones. */
                return (0);
        }

        /*
         * Stage 2: allocate objects for non-existing values.
         */
        for (i = 0; i < count; i++) {
                ptei = &tei[i];
                if (ptei->value != 0)
                        continue;
                if (ptei->ptv != NULL)
                        continue;
                ptei->ptv = malloc(sizeof(struct table_val_link), M_IPFW,
                    M_WAITOK | M_ZERO);
        }

        /*
         * Stage 3: allocate index numbers for new values
         * and link them to index.
         */
        KASSERT(pval == ch->valuestate, ("resize_storage() notify failure"));

        /* Let's try to link values */
        for (i = 0; i < count; i++) {
                ptei = &tei[i];

                /* Check if record has appeared */
                mask_table_value(ptei->pvalue, &tval, tc->vmask);
                ptv = (struct table_val_link *)ipfw_objhash_lookup_name(vi, 0,
                    (char *)&tval);
                if (ptv != NULL) {
                        ptv->pval->refcnt++;
                        ptei->value = ptv->no.kidx;
                        continue;
                }

                if ((error = alloc_table_vidx(ch, tc, vi, &vidx, flags)) != 0)
                        return (error);

                /* Finally, we have allocated valid index, let's add entry */
                ptei->value = vidx;
                ptv = (struct table_val_link *)ptei->ptv;
                ptei->ptv = NULL;

                ptv->no.kidx = vidx;
                ptv->no.name = (char *)&pval[vidx];
                ptv->pval = &pval[vidx];
                memcpy(ptv->pval, &tval, sizeof(struct table_value));
                pval[vidx].refcnt = 1;
                ipfw_objhash_add(vi, &ptv->no);
        }

        return (0);
}

/*
 * Imports table value from current userland format.
 * Saves value in kernel format to the same place.
 */
void
ipfw_import_table_value_v1(ipfw_table_value *iv)
{
        struct table_value v;

        memset(&v, 0, sizeof(v));
        v.tag = iv->tag;
        v.pipe = iv->pipe;
        v.divert = iv->divert;
        v.skipto = iv->skipto;
        v.netgraph = iv->netgraph;
        v.fib = iv->fib;
        v.nat = iv->nat;
        v.dscp = iv->dscp;
        v.nh4 = iv->nh4;
        v.nh6 = iv->nh6;
        v.limit = iv->limit;
        v.zoneid = iv->zoneid;
        v.mark = iv->mark;

        memcpy(iv, &v, sizeof(ipfw_table_value));
}

/*
 * Export real table value @v to current userland format.
 * Note that @v and @piv may point to the same memory.
 */
void
ipfw_export_table_value_v1(struct table_value *v, ipfw_table_value *piv)
{
        ipfw_table_value iv;

        memset(&iv, 0, sizeof(iv));
        iv.tag = v->tag;
        iv.pipe = v->pipe;
        iv.divert = v->divert;
        iv.skipto = v->skipto;
        iv.netgraph = v->netgraph;
        iv.fib = v->fib;
        iv.nat = v->nat;
        iv.dscp = v->dscp;
        iv.limit = v->limit;
        iv.nh4 = v->nh4;
        iv.nh6 = v->nh6;
        iv.zoneid = v->zoneid;
        iv.mark = v->mark;

        memcpy(piv, &iv, sizeof(iv));
}

/*
 * Exports real value data into ipfw_table_value structure including refcnt.
 */
static int
dump_tvalue(struct namedobj_instance *ni, struct named_object *no, void *arg)
{
        struct vdump_args *da;
        struct table_val_link *ptv;
        ipfw_table_value *v;

        da = (struct vdump_args *)arg;
        ptv = (struct table_val_link *)no;

        v = (ipfw_table_value *)ipfw_get_sopt_space(da->sd, sizeof(*v));
        /* Out of memory, returning */
        if (v == NULL) {
                da->error = ENOMEM;
                return (ENOMEM);
        }

        ipfw_export_table_value_v1(ptv->pval, v);
        v->refcnt = ptv->pval->refcnt;
        v->kidx = ptv->no.kidx;
        return (0);
}

/*
 * Dumps all shared/table value data
 * Data layout (v1)(current):
 * Request: [ ipfw_obj_lheader ], size = ipfw_obj_lheader.size
 * Reply: [ ipfw_obj_lheader ipfw_table_value x N ]
 *
 * Returns 0 on success
 */
static int
list_table_values(struct ip_fw_chain *ch, ip_fw3_opheader *op3,
    struct sockopt_data *sd)
{
        struct _ipfw_obj_lheader *olh;
        struct namedobj_instance *vi;
        struct vdump_args da;
        uint32_t count, size;

        olh = (struct _ipfw_obj_lheader *)ipfw_get_sopt_header(sd,sizeof(*olh));
        if (olh == NULL)
                return (EINVAL);
        if (sd->valsize < olh->size)
                return (EINVAL);

        IPFW_UH_RLOCK(ch);
        vi = CHAIN_TO_VI(ch);

        count = ipfw_objhash_count(vi);
        size = count * sizeof(ipfw_table_value) + sizeof(ipfw_obj_lheader);

        /* Fill in header regadless of buffer size */
        olh->count = count;
        olh->objsize = sizeof(ipfw_table_value);

        if (size > olh->size) {
                olh->size = size;
                IPFW_UH_RUNLOCK(ch);
                return (ENOMEM);
        }
        olh->size = size;

        /*
         * Do the actual value dump
         */
        memset(&da, 0, sizeof(da));
        da.ch = ch;
        da.sd = sd;
        ipfw_objhash_foreach(vi, dump_tvalue, &da);

        IPFW_UH_RUNLOCK(ch);

        return (0);
}

void
ipfw_table_value_init(struct ip_fw_chain *ch, int first)
{
        struct tables_config *tcfg;

        ch->valuestate = malloc(VALDATA_START_SIZE * sizeof(struct table_value),
            M_IPFW, M_WAITOK | M_ZERO);

        tcfg = ch->tblcfg;

        tcfg->val_size = VALDATA_START_SIZE;
        tcfg->valhash = ipfw_objhash_create(tcfg->val_size, VALDATA_HASH_SIZE);
        ipfw_objhash_set_funcs(tcfg->valhash, hash_table_value,
            cmp_table_value);

        IPFW_ADD_SOPT_HANDLER(first, scodes);
}

static int
destroy_value(struct namedobj_instance *ni, struct named_object *no,
    void *arg)
{

        free(no, M_IPFW);
        return (0);
}

void
ipfw_table_value_destroy(struct ip_fw_chain *ch, int last)
{

        IPFW_DEL_SOPT_HANDLER(last, scodes);

        free(ch->valuestate, M_IPFW);
        ipfw_objhash_foreach(CHAIN_TO_VI(ch), destroy_value, ch);
        ipfw_objhash_destroy(CHAIN_TO_VI(ch));
}