// Copyright 2024 The gVisor Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package nftables

import (
	"fmt"
	"math"
	"slices"

	"gvisor.dev/gvisor/pkg/abi/linux"
	"gvisor.dev/gvisor/pkg/atomicbitops"
	"gvisor.dev/gvisor/pkg/log"
	"gvisor.dev/gvisor/pkg/rand"
	"gvisor.dev/gvisor/pkg/sentry/socket/netlink/nlmsg"
	"gvisor.dev/gvisor/pkg/syserr"
	"gvisor.dev/gvisor/pkg/tcpip"
	"gvisor.dev/gvisor/pkg/tcpip/stack"
)

//
// Interface-Related Methods
//

// CheckPrerouting checks at the Prerouting hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckPrerouting(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFPrerouting)
}

// CheckInput checks at the Input hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckInput(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFInput)
}

// CheckForward checks at the Forward hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckForward(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFForward)
}

// CheckOutput checks at the Output hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckOutput(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFOutput)
}

// CheckPostrouting checks at the Postrouting hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckPostrouting(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFPostrouting)
}

// CheckIngress checks at the Ingress hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckIngress(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFIngress)
}

// CheckEgress checks at the Egress hook if the packet should continue traversing the stack.
func (nf *NFTables) CheckEgress(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily) bool {
	return nf.checkHook(pkt, route, af, stack.NFEgress)
}

// checkHook returns true if the packet should continue traversing the stack or false
// if the packet should be dropped.
// If NFTables is not enabled, the packet is always allowed to continue traversing the stack.
func (nf *NFTables) checkHook(pkt *stack.PacketBuffer, route *stack.Route, af stack.AddressFamily, hook stack.NFHook) bool {
	if !IsNFTablesEnabled() {
		return true
	}
	v, err := nf.EvaluateHook(af, hook, pkt, route)

	if err != nil {
		return false
	}

	return v.Code == VC(linux.NF_ACCEPT)
}

// isTerminalCode returns if the hook evaluation should terminate now.
func isTerminalCode(code uint32) bool {
	// NF_ACCEPT should continue the evaluation of the other base chains.
	switch code {
	case VC(linux.NF_DROP), VC(linux.NF_STOLEN), VC(linux.NF_QUEUE):
		return true
	}
	return false
}

//
// Core Evaluation Functions
//

// evaluateNATBaseChains evaluates the packet through the NAT base chains;
// if NAT has not been configured for this packet.
// Reserves a no-op NAT if no rules matched.
// Returns error and whether NAT is/was configured.
func (nf *NFTables) evaluateNATBaseChains(pkt *stack.PacketBuffer, route *stack.Route, hook stack.NFHook, family stack.AddressFamily, regs *registerSet) (*syserr.AnnotatedError, bool) {
	natType := stack.NfHookToNATType(hook)
	if natType == stack.NATUnknown {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("invalid hook: %s for NATType: %s", hook, natType)), false
	}
	// Check if NAT has already been configured for this packet.
	// If so, skip the evaluation of the NAT base chains.
	if pkt.IsNATConfigured(natType) {
		return nil, true
	}
	baseChains, err := nf.getBaseChainsForEvaluation(family, hook, true /* natChains */)
	if err != nil {
		return err, false
	}
	evalCtx := opEvalCtx{
		pkt:      pkt,
		route:    route,
		hook:     hook,
		nftState: nf,
	}
	for _, bc := range baseChains {
		if _, dormant := bc.table.flagSet[TableFlagDormant]; dormant {
			continue
		}
		// Evaluate the packet through the base chain.
		if err := bc.evaluate(regs, evalCtx); err != nil {
			return err, false
		}
		// If the verdict is a terminal code, NAT will not be configured for this
		// packet.
		if isTerminalCode(regs.Verdict().Code) {
			return nil, false
		}
		// If the current base chain configured NAT for this packet, work is done.
		if pkt.IsNATConfigured(natType) {
			return nil, true
		}
	}
	// If none of the base chains configured NAT for this packet, reserve a no-op NAT.
	// As NAT rules should be only evaluated once for a connection, a no-op NAT must be reserved
	// to ensure the packet skips the NAT base chains again.
	if !pkt.ConfigureNoopNAT(natType) {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("failed to reserve no-op NAT for packet: %v", pkt)), false
	}
	return nil, true
}

// evaluateNAT evaluates then applies NAT to the packet.
func (nf *NFTables) evaluateNAT(pkt *stack.PacketBuffer, route *stack.Route, hook stack.NFHook, family stack.AddressFamily, regs *registerSet) *syserr.AnnotatedError {
	if !pkt.IsConnTrackConfigured() {
		log.Warningf("ConnTrack should be configured before NAT")
		return nil
	}

	err, natConfigured := nf.evaluateNATBaseChains(pkt, route, hook, family, regs)
	if err != nil {
		return err
	}
	// If NAT is not configured for this packet, nothing to do.
	if !natConfigured {
		return nil
	}
	// Apply NAT to the packet;
	// i.e. rewrite the packet headers and update the conntrack state.
	_ = stack.NFTApplyNAT(pkt, hook, route)
	regs.verdict.Code = VC(linux.NF_ACCEPT)
	return nil
}

// extraEvaluator is a struct that holds a priority and a function to call during
// functions other than base chain evaluations.
type extraEvaluator struct {
	priority int
	handle   func() *syserr.AnnotatedError
}

// getExtraEvaluators returns a list of extra evaluators beside the nft chains.
func (nf *NFTables) getExtraEvaluators(family stack.AddressFamily, hook stack.NFHook, pkt *stack.PacketBuffer, route *stack.Route, regs *registerSet) []*extraEvaluator {
	var e []*extraEvaluator
	// Get ConnTrack evaluator.
	connTrackHookPriority, connTrackOk := stack.NfConnTrackPriority(hook)
	if nf.connTrack != nil && connTrackOk {
		e = append(e, &extraEvaluator{
			priority: connTrackHookPriority,
			handle: func() *syserr.AnnotatedError {
				switch hook {
				case stack.NFPrerouting, stack.NFOutput:
					nf.connTrack.GetConnAndUpdatePkt(pkt, hook == stack.NFOutput /* skipChecksumValidation */)
				case stack.NFInput, stack.NFPostrouting:
					if !pkt.FinalizeConnTrack() {
						return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("failed to finalize connTrack for packet: %v", pkt))
					}
				}
				return nil
			}})
	}
	// Get NAT evaluator.
	natHookPriority, natOk := stack.NfNATPriority(hook)
	if nf.natEnabled && natOk {
		e = append(e, &extraEvaluator{
			priority: natHookPriority,
			handle: func() *syserr.AnnotatedError {
				return nf.evaluateNAT(pkt, route, hook, family, regs)
			},
		})
	}
	// Sort the evaluators by priority.
	slices.SortFunc(e, func(a, b *extraEvaluator) int {
		return a.priority - b.priority
	})
	return e
}

func (nf *NFTables) getBaseChainsForEvaluation(family stack.AddressFamily, hook stack.NFHook, natChains bool) ([]*Chain, *syserr.AnnotatedError) {
	getBaseChains := func(hf *hookFunctionStack) []*Chain {
		if natChains {
			return hf.natBaseChains
		}
		return hf.baseChains
	}
	switch family {
	case stack.IP:
		return getBaseChains(&nf.ip4InetBaseChains[hook]), nil
	case stack.IP6:
		return getBaseChains(&nf.ip6InetBaseChains[hook]), nil
	case stack.Inet:
		// A packet can be of only IP or IP6 address family.
		return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "inet address family is not supported for hook evaluation")
	}
	if nf.filters[family] == nil {
		return nil, nil
	}
	filter := nf.filters[family]
	if filter.hfStacks[hook] == nil {
		return nil, nil
	}
	return getBaseChains(filter.hfStacks[hook]), nil
}

// EvaluateHook evaluates a packet using the rules of the given hook for the
// given address family, returning a netfilter verdict and modifying the packet
// in place.
// Returns an error if address family or hook is invalid or they don't match.
// TODO(b/345684870): Consider removing error case if we never return an error.
func (nf *NFTables) EvaluateHook(family stack.AddressFamily, hook stack.NFHook, pkt *stack.PacketBuffer, route *stack.Route) (Verdict, *syserr.AnnotatedError) {
	// Note: none of the other evaluate functions are public because they require
	// jumping to different chains in the same table, so all chains, rules, and
	// operations must be tied to a table. Thus, calling evaluate for standalone
	// chains, rules, or operations can be misleading and dangerous.

	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return Verdict{}, err
	}

	// Ensures hook is valid.
	if err := validateHook(hook, family); err != nil {
		return Verdict{}, err
	}

	baseChains, err := nf.getBaseChainsForEvaluation(family, hook, false /* natChains */)
	if err != nil {
		return Verdict{}, err
	}

	// Create a new register set for the evaluation.
	regs := newRegisterSet()
	// Evaluates packet through all base chains for given hook in priority order.
	extraEvaluators := nf.getExtraEvaluators(family, hook, pkt, route, &regs)
	ei := 0 // Extra evaluator iterator.
	numExtraHooks := len(extraEvaluators)
	ci := 0 // Base chain iterator.
	numBaseChains := len(baseChains)

	// If there's nothing to evaluate, return accept.
	if numBaseChains == 0 && numExtraHooks == 0 {
		return Verdict{Code: VC(linux.NF_ACCEPT)}, nil
	}
	var lastEvaluatedChain *Chain
	evalCtx := opEvalCtx{
		pkt:      pkt,
		route:    route,
		hook:     hook,
		nftState: nf,
	}
	// Evaluate base chains and extra evaluators in priority order.
	for ei < numExtraHooks || ci < numBaseChains {
		selectExtra := (ci == numBaseChains) || (ei < numExtraHooks && extraEvaluators[ei].priority < baseChains[ci].GetBaseChainInfo().Priority.GetValue())
		if selectExtra {
			if err := extraEvaluators[ei].handle(); err != nil {
				return Verdict{}, err
			}
			ei++
		} else {
			bc := baseChains[ci]
			ci++
			// Doesn't evaluate chain if it's table is flagged as dormant.
			if _, dormant := bc.table.flagSet[TableFlagDormant]; dormant {
				continue
			}
			if err := bc.evaluate(&regs, evalCtx); err != nil {
				return Verdict{}, err
			}
			lastEvaluatedChain = bc
		}

		// Terminates immediately on netfilter terminal verdicts.
		if v := regs.Verdict(); isTerminalCode(v.Code) {
			return v, nil
		}
	}

	// Returns policy verdict of the last base chain evaluated if no terminal
	// verdict was issued.
	switch regs.Verdict().Code {
	case VC(linux.NFT_CONTINUE), VC(linux.NFT_RETURN):
		if lastEvaluatedChain != nil && lastEvaluatedChain.GetBaseChainInfo().PolicyDrop {
			return Verdict{Code: VC(linux.NF_DROP)}, nil
		}
		return Verdict{Code: VC(linux.NF_ACCEPT)}, nil
	case VC(linux.NF_ACCEPT):
		return Verdict{Code: VC(linux.NF_ACCEPT)}, nil
	}

	panic(fmt.Sprintf("unexpected verdict from hook evaluation: %s", VerdictCodeToString(regs.Verdict().Code)))
}

// evaluateFromRule is a helper function for Chain.evaluate that evaluates the
// packet through the rules in the chain starting at the specified rule index.
func (c *Chain) evaluateFromRule(rIdx int, jumpDepth int, regs *registerSet, evalCtx opEvalCtx) *syserr.AnnotatedError {
	if jumpDepth >= nestedJumpLimit {
		return syserr.NewAnnotatedError(syserr.ErrTooManyLinks, fmt.Sprintf("exceeded nested jump limit of %d", nestedJumpLimit))
	}

	// Resets verdict to continue for the next rule.
	regs.verdict.Code = VC(linux.NFT_CONTINUE)

	// Evaluates all rules in the chain (breaking on terminal verdicts).
evalLoop:
	for ; rIdx < len(c.rules); rIdx++ {
		rule := c.rules[rIdx]
		evalCtx.rule = rule
		if err := rule.evaluate(regs, evalCtx); err != nil {
			return err
		}

		// Continues evaluation at target chains for jump and goto verdicts.
		jumped := false
		v := regs.Verdict()
		switch v.Code {
		case VC(linux.NFT_JUMP):
			jumpDepth++
			jumped = true
			fallthrough
		case VC(linux.NFT_GOTO):
			nextChain := v.Chain
			if nextChain == nil {
				return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "chain not found for jump/goto verdict")
			}
			if err := nextChain.evaluateFromRule(0, jumpDepth, regs, evalCtx); err != nil {
				return err
			}
			// Ends evaluation for goto (and continues evaluation for jump).
			if !jumped {
				break evalLoop
			}
			jumpDepth--
		}

		// Update verdict after jumps/gotos.
		v = regs.Verdict()

		// Only continues evaluation for Continue and Break verdicts.
		switch v.Code {
		case VC(linux.NFT_BREAK):
			// Resets verdict for next rule (after breaking from a single operation).
			regs.verdict.Code = VC(linux.NFT_CONTINUE)
		case VC(linux.NFT_CONTINUE):
			// Goes to next rule.
			continue
		default:
			// Break evaluation for all the netfilter verdicts.
			break evalLoop
		}
	}
	return nil
}

// evaluate for Chain evaluates the packet through the chain's rules and returns
// the verdict and modifies the packet in place.
func (c *Chain) evaluate(regs *registerSet, evalCtx opEvalCtx) *syserr.AnnotatedError {
	return c.evaluateFromRule(0, 0, regs, evalCtx)
}

// evaluate evaluates the rule on the given packet and register set, changing
// the register set and possibly the packet in place.
// The verdict in regs.Verdict() may be an nf table internal verdict or a
// netfilter terminal verdict.
func (r *Rule) evaluate(regs *registerSet, evalCtx opEvalCtx) *syserr.AnnotatedError {
	for _, op := range r.ops {
		op.evaluate(regs, evalCtx)
		if regs.Verdict().Code != VC(linux.NFT_CONTINUE) {
			break
		}
	}
	return nil
}

//
// Top-Level NFTables Functions
// Note: Provides wrapper functions for the creation and deletion of tables,
// chains, and rules for convenience.
//

// NewNFTables creates a new NFTables state object using the given clock for
// timing operations.
// Note: Expects random number generator to be initialized with a seed.
func NewNFTables(stack *stack.Stack, clock tcpip.Clock, rng rand.RNG) *NFTables {
	if clock == nil {
		panic("nftables state must be initialized with a non-nil clock")
	}
	if rng.Reader == nil {
		panic("nftables state must be initialized with a non-nil random number generator")
	}
	return &NFTables{stack: stack, clock: clock, startTime: clock.Now(), rng: rng, tableHandleCounter: atomicbitops.Uint64{}, genid: 1}
}

// GetGenID returns the generation ID for the NFTables object.
func (nf *NFTables) GetGenID() uint32 {
	return nf.genid
}

// SetGenID sets the generation ID for the NFTables object.
func (nf *NFTables) SetGenID(genid uint32) {
	nf.genid = genid
}

// PruneUnused deletes unused/non-referenced internal objects.
func (nf *NFTables) PruneUnused() {
	for _, filter := range nf.filters {
		if filter == nil {
			continue
		}
		for _, tab := range filter.tables {
			tab.pruneUnused()
		}
	}
}

// CanCommitChains checks that all the new bounded chains are valid.
// Ref: net/netfilter/nf_tables_api.c:nf_tables_commit()
func (nf *NFTables) CanCommitChains(newChains []*Chain) *syserr.AnnotatedError {
	for _, chain := range newChains {
		if !chain.IsAnonymousChain() {
			continue
		}
		if !chain.IsBound() {
			return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "anonymous chains must have jump/goto reference")
		}
		if chain.GetChainUse() > 1 {
			return syserr.NewAnnotatedError(syserr.ErrBusy, "anonymous chain already in use")
		}
	}
	return nil
}

// Flush clears all data for all address families or
// a specific family/table if filtered.
// It skips tables that are not owned by the given owner.
func (nf *NFTables) Flush(familyFilter stack.AddressFamily, attrs map[uint16]nlmsg.BytesView, owner uint32) *syserr.AnnotatedError {
	for family := range stack.NumAFs {
		if familyFilter != stack.Unspec &&
			stack.AddressFamily(family) != familyFilter {
			continue
		}
		afFilter := nf.filters[family]
		if afFilter == nil {
			continue
		}

		var attrName *string = nil
		if nameBytes, ok := attrs[linux.NFTA_TABLE_NAME]; ok {
			name := nameBytes.String()
			attrName = &name
		}
		var tablesToDelete []TableInfo
		for name, table := range afFilter.tables {
			// Caller cannot delete a table they do not own.
			if table.HasOwner() && table.GetOwner() != owner {
				continue
			}

			if attrName != nil && *attrName != table.GetName() {
				continue
			}

			for _, chain := range table.chains {
				if err := nf.removeChainFromCache(chain); err != nil {
					return err
				}
			}

			table.destroy()

			tablesToDelete = append(tablesToDelete, TableInfo{Name: name, Handle: table.GetHandle()})
		}

		for _, tableData := range tablesToDelete {
			delete(afFilter.tables, tableData.Name)
			delete(afFilter.tableHandles, tableData.Handle)
		}
	}
	return nil
}

// FlushAddressFamily clears ruleset and all data for the given address family,
// returning an error if the address family is invalid.
func (nf *NFTables) FlushAddressFamily(family stack.AddressFamily) *syserr.AnnotatedError {
	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return err
	}

	nf.filters[family] = nil
	return nil
}

// GetAddressFamilyTables returns the tables for the given address family.
func (nf *NFTables) GetAddressFamilyTables(family stack.AddressFamily) map[string]*Table {
	afFilter := nf.filters[family]
	if afFilter == nil {
		// An empty map is safe to iterate over.
		return nil
	}

	return afFilter.tables
}

// GetTable validates the inputs and gets a table if it exists, error otherwise.
func (nf *NFTables) GetTable(family stack.AddressFamily, tableName string, portID uint32) (*Table, *syserr.AnnotatedError) {
	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return nil, err
	}

	// Checks if the table map for the address family has been initialized.
	if nf.filters[family] == nil || nf.filters[family].tables == nil {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("table map for address family %v has no tables", family))
	}

	// Gets the corresponding table map for the address family.
	tableMap := nf.filters[family].tables

	// Checks if a table with the name exists.
	t, exists := tableMap[tableName]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("table %s not found for address family %v", tableName, family))
	}

	// If the table has an owner, it must match the Netlink portID of the calling process.
	// User space processes only have non-zero port ids.
	// Only the kernel can have a zero port id.
	if t.HasOwner() && portID != 0 && portID != t.GetOwner() {
		return nil, syserr.NewAnnotatedError(syserr.ErrNotPermitted, fmt.Sprintf("table %s has owner %d, which does not match the Netlink portID of the calling process %d", tableName, t.GetOwner(), portID))
	}

	return t, nil
}

// GetTableByHandle validates the inputs and gets a table by its handle and family if it exists,
// error otherwise.
func (nf *NFTables) GetTableByHandle(family stack.AddressFamily, handle uint64, portID uint32) (*Table, *syserr.AnnotatedError) {
	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return nil, err
	}

	// Checks if the table handle map for the address family has been initialized.
	if nf.filters[family] == nil || nf.filters[family].tableHandles == nil {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("table handle map for address family %v has no tables", family))
	}

	// Gets the corresponding table map for the address family.
	tableHandleMap := nf.filters[family].tableHandles

	// Checks if a table with the name exists.
	t, exists := tableHandleMap[handle]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("table with handle %d not found for address family %v", handle, family))
	}

	// If the table has an owner, it must match the Netlink portID of the calling process.
	// User space processes only have non-zero port ids.
	// Only the kernel can have a zero port id.
	if t.HasOwner() && portID != 0 && portID != t.GetOwner() {
		return nil, syserr.NewAnnotatedError(syserr.ErrNotPermitted, fmt.Sprintf("table with handle %d has owner %d, which does not match the Netlink portID of the calling process %d", handle, t.GetOwner(), portID))
	}

	return t, nil
}

// AddTable makes a new table for the specified address family, returning an
// error if the address family is invalid. Can return an error if a table by the
// same name already exists if errorOnDuplicate is true. Can be used to get an
// existing table by the same name if errorOnDuplicate is false.
// Note: if the table already exists, the existing table is returned without any
// modifications.
// Note: Table initialized as not dormant.
func (nf *NFTables) AddTable(family stack.AddressFamily, name string,
	errorOnDuplicate bool) (*Table, *syserr.AnnotatedError) {
	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return nil, err
	}

	// Initializes filter if first table for the address family.
	if nf.filters[family] == nil {
		nf.filters[family] = &addressFamilyFilter{
			family:       family,
			nftState:     nf,
			tables:       make(map[string]*Table),
			tableHandles: make(map[uint64]*Table),
			hfStacks:     make(map[stack.NFHook]*hookFunctionStack),
		}
	}

	// Gets the corresponding table map for the address family.
	tableMap := nf.filters[family].tables
	tableHandleMap := nf.filters[family].tableHandles

	// Checks if a table with the same name already exists. If so, returns the
	// existing table (unless errorOnDuplicate is true).
	if existingTable, exists := tableMap[name]; exists {
		if errorOnDuplicate {
			return nil, syserr.NewAnnotatedError(syserr.ErrExists, fmt.Sprintf("table %s already exists in address family %v", name, family))
		}
		return existingTable, nil
	}

	// Creates the new table and add it to the table map.
	t := &Table{
		name:          name,
		afFilter:      nf.filters[family],
		chains:        make(map[string]*Chain),
		chainHandles:  make(map[uint64]*Chain),
		flagSet:       make(map[TableFlag]struct{}),
		handle:        nf.getNewTableHandle(),
		handleCounter: atomicbitops.Uint64{},
		sets:          make(map[string]*nftSet),
		setHandles:    make(map[uint64]*nftSet),
	}
	tableMap[name] = t
	tableHandleMap[t.handle] = t

	return t, nil
}

// getNewTableHandle returns a new table handle for the NFTables object.
func (nf *NFTables) getNewTableHandle() uint64 {
	return nf.tableHandleCounter.Add(1)
}

// CreateTable makes a new table for the specified address family like AddTable
// but also returns an error if a table by the same name already exists.
// Note: this interface mirrors the difference between the create and add
// commands within the nft binary.
func (nf *NFTables) CreateTable(family stack.AddressFamily, name string) (*Table, *syserr.AnnotatedError) {
	return nf.AddTable(family, name, true)
}

// DeleteTable deletes the specified table from the NFTables object returning
// true if the table was deleted and false if the table doesn't exist. Returns
// an error if the address family is invalid.
func (nf *NFTables) DeleteTable(family stack.AddressFamily, tableName string) (bool, *syserr.AnnotatedError) {
	// Ensures address family is valid.
	if err := validateAddressFamily(family); err != nil {
		return false, err
	}

	// Gets and checks the table.
	t, err := nf.GetTable(family, tableName, 0)
	if err != nil {
		return false, err
	}

	for _, c := range t.chains {
		if err := nf.removeChainFromCache(c); err != nil {
			return false, err
		}
	}

	t.destroy()

	// Deletes the table from the table map and from the table handle map.
	delete(nf.filters[family].tables, tableName)
	delete(nf.filters[family].tableHandles, t.handle)
	return true, nil
}

// GetChain validates the inputs and gets a chain if it exists, error otherwise.
func (nf *NFTables) GetChain(family stack.AddressFamily, tableName string, chainName string) (*Chain, *syserr.AnnotatedError) {
	// Gets and checks the table.
	t, err := nf.GetTable(family, tableName, 0)
	if err != nil {
		return nil, err
	}

	return t.GetChain(chainName)
}

// AddChainToTable makes a new chain for the corresponding table and adds it to the
// chain map and hook function list, returning an error if the address family is
// invalid or the table doesn't exist. Can return an error if a chain by the
// same name already exists if errorOnDuplicate is true. Can be used to get an
// existing chain by the same name if errorOnDuplicate is false.
// Note: if the chain already exists, the existing chain is returned without any
// modifications.
// Note: if the chain is not a base chain, info should be nil.
func (nf *NFTables) AddChainToTable(tab *Table, chainName string, bcInfo *BaseChainInfo, comment string, errorOnDuplicate bool, chainFlags uint32, udata []byte, policy uint8) (*Chain, *syserr.AnnotatedError) {
	// Add the chain to the table, appending, by priority, to the stack of base
	// chains for the hook.
	chain, err := tab.addChain(chainName, bcInfo, comment, errorOnDuplicate)
	if err != nil {
		return nil, err
	}
	chain.SetFlags(uint8(chainFlags))
	if udata != nil {
		if err := chain.SetUserData(udata); err != nil {
			return nil, err
		}
	}
	if chain.IsBaseChain() {
		info := chain.GetBaseChainInfo()
		if info == nil {
			return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("base chain info is nil for chain %s", chainName))
		}
		info.PolicyDrop = policy == linux.NF_DROP
		if err := nf.addChainToCache(chain); err != nil {
			return nil, err
		}

		// Initialize ConnTrack and NAT when the first nat expression is added to the rule.
		// No locks are needed as each update happens
		// in a new copy.
		if bcInfo.BcType == BaseChainTypeNat {
			nf.InitConnTrackOnce()
			nf.SetNATState(true /*enabled*/)
		}
	}
	return chain, nil
}

// getNewHandle returns a new handle for a chain or rule.
func (t *Table) getNewHandle() uint64 {
	return t.handleCounter.Add(1)
}

// DeleteChainFromTable deletes the specified chain from the NFTables object returning
// true if the chain was deleted and false if the chain doesn't exist. Returns
// an error if the address family is invalid or the table doesn't exist.
func (nf *NFTables) DeleteChainFromTable(tab *Table, chainName string) (bool, *syserr.AnnotatedError) {
	// Checks if the chain exists.
	c, exists := tab.chains[chainName]
	if !exists {
		return false, nil
	}
	if err := nf.removeChainFromCache(c); err != nil {
		return false, err
	}
	return tab.deleteChain(c), nil
}

// TableCount returns the number of tables in the NFTables object.
func (nf *NFTables) TableCount() int {
	return len(nf.filters)
}

// removeChainFromCache removes the specified chain from the cache.
// The cache is composed of base chains.
func (nf *NFTables) removeChainFromCache(c *Chain) *syserr.AnnotatedError {
	if !c.IsBaseChain() {
		return nil
	}
	hook := c.GetBaseChainInfo().Hook
	af := c.GetAddressFamily()
	switch af {
	case stack.IP:
		return nf.ip4InetBaseChains[hook].detachBaseChain(c)
	case stack.IP6:
		return nf.ip6InetBaseChains[hook].detachBaseChain(c)
	case stack.Inet:
		if err := nf.ip4InetBaseChains[hook].detachBaseChain(c); err != nil {
			return err
		}
		return nf.ip6InetBaseChains[hook].detachBaseChain(c)
	}
	return nil
}

// addChainToCache adds the base chain to the cache.
// The cache is just a merged list of base chains for IPv4-inet and IPv6-inet
// address families. The list is sorted by priority.
func (nf *NFTables) addChainToCache(c *Chain) *syserr.AnnotatedError {
	if !c.IsBaseChain() {
		return nil
	}
	hook := c.GetBaseChainInfo().Hook
	af := c.GetAddressFamily()
	switch af {
	case stack.IP:
		return nf.ip4InetBaseChains[hook].attachBaseChain(c)
	case stack.IP6:
		return nf.ip6InetBaseChains[hook].attachBaseChain(c)
	case stack.Inet:
		if err := nf.ip4InetBaseChains[hook].attachBaseChain(c); err != nil {
			return err
		}
		if err := nf.ip6InetBaseChains[hook].attachBaseChain(c); err != nil {
			return err
		}
	}
	return nil
}

// InitConnTrackOnce initializes the conntrack.
// No need to lock the mutex as each NFTables update
// happens in a new copy of the NFTables struct.
func (nf *NFTables) InitConnTrackOnce() {
	if nf.connTrack == nil {
		nf.connTrack, nf.connTrackReaper = stack.NewConnTrackWithReaper(nf.clock, &nf.rng, nil /* seed */)
	}
}

// GetConnTrack returns the conntrack.
func (nf *NFTables) GetConnTrack() *stack.ConnTrack {
	return nf.connTrack
}

// SetNATState sets the NAT state of the NFTables object.
// Every new connection needs to go through the NAT configuration
// even if there are no NAT rules to apply.
// This variable is used to skip these NAT configurations
// for the new connections and gets only
// enabled when a NAT chain is added.
func (nf *NFTables) SetNATState(enabled bool) {
	nf.natEnabled = enabled
}

//
// Table Functions
//

// GetName returns the name of the table.
func (t *Table) GetName() string {
	return t.name
}

// GetAddressFamily returns the address family of the table.
func (t *Table) GetAddressFamily() stack.AddressFamily {
	return t.afFilter.family
}

// GetHandle returns the handle of the table.
func (t *Table) GetHandle() uint64 {
	return t.handle
}

// GetOwner returns the owner of the table.
func (t *Table) GetOwner() uint32 {
	return t.owner
}

// SetOwner sets the owner of the table. If the table already has an owner, it
// is not updated.
func (t *Table) SetOwner(nlpid uint32) *syserr.AnnotatedError {
	// This should only be called once, when setting the owner of a table for the first time.
	if t.HasOwner() {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("table %s already has an owner", t.name))
	}

	t.flagSet[TableFlagOwner] = struct{}{}
	t.owner = nlpid
	return nil
}

// HasOwner returns whether the table has an owner.
func (t *Table) HasOwner() bool {
	_, ok := t.flagSet[TableFlagOwner]
	return ok
}

// GetUserData returns the user data of the table.
func (t *Table) GetUserData() []byte {
	return t.userData
}

// HasUserData returns whether the table has user data.
func (t *Table) HasUserData() bool {
	return t.userData != nil
}

// SetUserData sets the user data of the table.
func (t *Table) SetUserData(data []byte) *syserr.AnnotatedError {
	// User data should only be set once.
	if t.userData != nil {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("table %s already has user data", t.name))
	}

	t.userData = make([]byte, len(data))
	copy(t.userData, data)
	return nil
}

// IsDormant returns whether the table is dormant.
func (t *Table) IsDormant() bool {
	_, dormant := t.flagSet[TableFlagDormant]
	return dormant
}

// SetDormant sets the dormant flag for the table.
func (t *Table) SetDormant(dormant bool) {
	if dormant {
		t.flagSet[TableFlagDormant] = struct{}{}
	} else {
		delete(t.flagSet, TableFlagDormant)
	}
}

// GetLinuxFlagSet returns the flag set of the table.
// Although user flags map to uint8 space, internal flags could eventually be
// supported, which together map to a uint32 space.
func (t *Table) GetLinuxFlagSet() (uint32, *syserr.AnnotatedError) {
	var flags uint32 = 0
	for flag := range t.flagSet {
		switch flag {
		case TableFlagDormant:
			flags |= linux.NFT_TABLE_F_DORMANT
		case TableFlagOwner:
			flags |= linux.NFT_TABLE_F_OWNER
		default:
			return 0, syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("unsupported flag %v", flag))
		}
	}

	return flags, nil
}

// GetLinuxUserFlagSet returns the user flag set of the table.
func (t *Table) GetLinuxUserFlagSet() (uint8, *syserr.AnnotatedError) {
	flags, err := t.GetLinuxFlagSet()
	if err != nil {
		return 0, err
	}
	return uint8(flags & linux.NFT_TABLE_F_MASK), nil
}

// GetChain returns the chain with the specified name if it exists, error
// otherwise.
func (t *Table) GetChain(chainName string) (*Chain, *syserr.AnnotatedError) {
	// Checks if a chain with the name exists.
	c, exists := t.chains[chainName]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("chain %s not found for table %s", chainName, t.name))
	}
	return c, nil
}

// GetChainByHandle returns the chain with the specified handle if it exists, error otherwise.
func (t *Table) GetChainByHandle(chainHandle uint64) (*Chain, *syserr.AnnotatedError) {
	// Checks if a chain with the handle exists. We don't support transactions/generations of tables
	// or chains, so those checks are not needed.
	c, exists := t.chainHandles[chainHandle]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("chain %d not found for table %s", chainHandle, t.name))
	}
	return c, nil
}

// GetChainByID returns the chain with the specified transaction ID if it exists.
func (t *Table) GetChainByID(chainID uint32) (*Chain, *syserr.AnnotatedError) {
	c, exists := t.chainIDs[chainID]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("chain ID %d not found for table %s", chainID, t.name))
	}
	return c, nil
}

// RegisterChainID registers a temporary batch transaction chain ID.
func (t *Table) RegisterChainID(chainID uint32, c *Chain) {
	if t.chainIDs == nil {
		t.chainIDs = make(map[uint32]*Chain)
	}
	// Ref: net/netfilter/nf_tables_api.c:nft_trans_chain_add()
	// Linux allows overwriting the chain ID.
	// No need to check for duplicates.
	t.chainIDs[chainID] = c
}

// ClearChainIDs clears all temporary transaction chain IDs in the table.
func (t *Table) ClearChainIDs() {
	t.chainIDs = nil
}

// pruneUnused removes unused/unreferenced table objects.
func (t *Table) pruneUnused() {
	// Garbage collect unbounded chains.
	// Unbounded chains are anonymous but have no references.
	// So, no rule can hit them.
	for {
		var toDelete []*Chain
		for _, c := range t.chains {
			if c.IsAnonymousChain() && !c.IsBound() {
				toDelete = append(toDelete, c)
			}
		}
		if len(toDelete) == 0 {
			break
		}
		for _, c := range toDelete {
			t.deleteChain(c)
		}
	}
	// Clear temporary transaction chain IDs.
	t.ClearChainIDs()
}

// GetChains returns a map of all chains for the table.
func (t *Table) GetChains() map[string]*Chain {
	return t.chains
}

// addChain makes a new chain for the table. Can return an error if a chain by
// the same name already exists if errorOnDuplicate is true.
func (t *Table) addChain(name string, info *BaseChainInfo, comment string, errorOnDuplicate bool) (*Chain, *syserr.AnnotatedError) {
	// Checks if a chain with the same name already exists. If so, returns the
	// existing chain (unless errorOnDuplicate is true).
	if existingChain, exists := t.chains[name]; exists {
		if errorOnDuplicate {
			return nil, syserr.NewAnnotatedError(syserr.ErrExists, fmt.Sprintf("chain %s already exists for table %s", name, t.name))
		}
		return existingChain, nil
	}

	// Creates a new chain.
	c := &Chain{
		name:          name,
		table:         t,
		baseChainInfo: info,
		comment:       comment,
		handleToRule:  make(map[uint64]*Rule),
	}

	// Sets the base chain info if it's a base chain (and validates it).
	if info != nil {
		if err := c.setBaseChainInfo(info); err != nil {
			return nil, err
		}
	}

	// Only assign a chain handle after error checks.
	c.handle = t.getNewHandle()

	// Adds the chain to the chain map (after successfully doing everything else).
	t.chains[name] = c
	t.chainHandles[c.handle] = c

	return c, nil
}

// deleteChain deletes the specified chain from the table returning true if the
// chain was deleted and false if the chain doesn't exist.
func (t *Table) deleteChain(c *Chain) bool {
	// Detaches the chain from the pipeline if it's a base chain.
	if c.baseChainInfo != nil {
		hfStack := t.afFilter.hfStacks[c.baseChainInfo.Hook]
		if err := hfStack.detachBaseChain(c); err != nil {
			panic(fmt.Sprintf("failed to detach base chain %s from hook %v: %v", c.GetName(), c.baseChainInfo.Hook, err))
		}
		if len(hfStack.baseChains) == 0 && len(hfStack.natBaseChains) == 0 {
			delete(t.afFilter.hfStacks, c.baseChainInfo.Hook)
		}
	}

	// Deletes chain.
	delete(t.chains, c.name)
	delete(t.chainHandles, c.handle)
	c.destroy()
	return true
}

// deleteSet deletes the specified set from the table returning true if the
// set was deleted and false if the set doesn't exist.
func (t *Table) deleteSet(s *nftSet) bool {
	if _, ok := t.sets[s.name]; !ok {
		return false
	}
	delete(t.sets, s.name)
	delete(t.setHandles, s.handle)
	s.destroy()
	return true
}

func (t *Table) destroy() {
	// Destroy all rules in the table first to handle any chain and set use.
	for _, c := range t.chains {
		c.DeleteAllRules()
	}
	// Destroy all sets in the table before chains so that any element-level
	// operations or verdicts referencing chains release their chainUse count.
	for _, s := range t.sets {
		t.deleteSet(s)
	}
	// Destroy all chains in the table.
	for _, c := range t.chains {
		t.deleteChain(c)
	}
	t.name = ""
	t.chains = nil
	t.chainHandles = nil
	t.sets = nil
	t.setHandles = nil
	t.flagSet = nil
	t.userData = nil
	t.afFilter = nil
	t.handle = 0
	t.handleCounter.Store(0)
	t.owner = 0
}

// ChainCount returns the number of chains in the table.
func (t *Table) ChainCount() int {
	return len(t.chains)
}

// RenameChain renames an existing chain in the table.
// Ref: net/netfilter/nf_tables_api.c:nf_tables_updchain()
func (t *Table) RenameChain(c *Chain, newName string) *syserr.AnnotatedError {
	currName := c.name
	if currName == newName {
		return nil
	}
	// Check for existing chain with a same name.
	if existingChain, exists := t.chains[newName]; exists {
		if existingChain != c {
			return syserr.NewAnnotatedError(syserr.ErrExists, fmt.Sprintf("chain %s already exists for table %s", newName, t.name))
		}
		return nil
	}

	delete(t.chains, currName)
	c.name = newName
	t.chains[newName] = c
	return nil
}

//
// Chain Functions
//

// GetName returns the name of the chain.
func (c *Chain) GetName() string {
	return c.name
}

// SetName sets the name of the chain. This should only be called on
// a chain that is not yet attached to a table.
func (c *Chain) SetName(name string) *syserr.AnnotatedError {
	if c.table != nil {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("Cannot change the name of chain %s that is already attached to table %s", c.name, c.table.name))
	}

	c.name = name
	return nil
}

// GetAddressFamily returns the address family of the chain.
func (c *Chain) GetAddressFamily() stack.AddressFamily {
	return c.table.GetAddressFamily()
}

// GetTable returns the table that the chain belongs to.
func (c *Chain) GetTable() *Table {
	return c.table
}

// GetHandle returns the handle of the chain.
func (c *Chain) GetHandle() uint64 {
	return c.handle
}

// GetFlags returns the flags of the chain.
func (c *Chain) GetFlags() uint8 {
	return c.flags
}

// SetFlags sets the flags of the chain.
func (c *Chain) SetFlags(flags uint8) {
	c.flags = flags
}

// GetUserData returns the user data of the chain.
func (c *Chain) GetUserData() []byte {
	return c.userData
}

// SetUserData sets the user data of the chain.
func (c *Chain) SetUserData(data []byte) *syserr.AnnotatedError {
	// User data should only be set once.
	if c.userData != nil {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("chain %s already has user data", c.name))
	}
	c.userData = make([]byte, len(data))
	copy(c.userData, data)
	return nil
}

// HasUserData returns whether the chain has user data.
func (c *Chain) HasUserData() bool {
	return c.userData != nil
}

// IsBaseChain returns whether the chain is a base chain.
func (c *Chain) IsBaseChain() bool {
	return c.baseChainInfo != nil
}

// IsAnonymousChain returns true if the chain is anonymous.
func (c *Chain) IsAnonymousChain() bool {
	return (c.flags&linux.NFT_CHAIN_BINDING != 0)
}

// IsBound returns true if the chain is an anonymous chain currently bound to a rule.
func (c *Chain) IsBound() bool {
	return c.IsAnonymousChain() && c.GetChainUse() > 0
}

// IncrementChainUse increments the chain use value of the chain.
func (c *Chain) IncrementChainUse() bool {
	if c.chainUse == math.MaxUint32 {
		return false
	}

	c.chainUse++
	return true
}

// GetBaseChainInfo returns the base chain info of the chain.
// Note: Returns nil if the chain is not a base chain.
func (c *Chain) GetBaseChainInfo() *BaseChainInfo {
	return c.baseChainInfo
}

// SetPolicy sets the policy for a base chain.
func (c *Chain) SetPolicy(policy uint8) *syserr.AnnotatedError {
	if !c.IsBaseChain() {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, fmt.Sprintf("chain %s is not a base chain", c.name))
	}
	if policy != linux.NF_DROP && policy != linux.NF_ACCEPT {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("invalid policy %d", policy))
	}
	c.baseChainInfo.PolicyDrop = (policy == linux.NF_DROP)
	return nil
}

// SetBaseChainInfo attaches the specified chain to the netfilter pipeline (and
// detaches the chain from the pipeline if it was previously attached to a
// different hook) by setting the base chain info for the chain, returning an
// error if the base chain info is invalid.
func (c *Chain) setBaseChainInfo(info *BaseChainInfo) *syserr.AnnotatedError {
	// Ensures base chain info is valid if it's a base chain.
	if err := validateBaseChainInfo(info, c.GetAddressFamily()); err != nil {
		return err
	}

	hfStacks := c.table.afFilter.hfStacks

	// Detaches the chain if it was previously attached to a different hook.
	if c.baseChainInfo != nil && c.baseChainInfo.Hook != info.Hook {
		oldHfStack := hfStacks[c.baseChainInfo.Hook]
		if err := oldHfStack.detachBaseChain(c); err != nil {
			return err
		}
	}

	// Initializes hook function stack (and its slice of base chains) if
	// first base chain for this hook (for the given address family).
	if hfStacks[info.Hook] == nil {
		hfStacks[info.Hook] = &hookFunctionStack{}
	}

	// Sets the base chain info and attaches to the pipeline.
	c.baseChainInfo = info
	hfStacks[info.Hook].attachBaseChain(c)

	return nil
}

// GetChainUse returns the chain use value of the chain.
func (c *Chain) GetChainUse() uint32 {
	return c.chainUse
}

// GetComment returns the comment of the chain.
func (c *Chain) GetComment() string {
	return c.comment
}

// SetComment sets the comment of the chain.
func (c *Chain) SetComment(comment string) {
	c.comment = comment
}

// GetRules returns the rules of the chain.
func (c *Chain) GetRules() []*Rule {
	return c.rules
}

// RegisterRule assigns the chain to the rule and adds the rule to the chain's
// rule list at the given index.
// Valid indices are -1 (append) and [0, len]. Errors on invalid index.
// This also checks that the operations in the rule comply with the chain.
// Checks done:
// - All jump and goto operations have a valid target chain.
// - Loop checking for jump and goto operations.
// - TODO(b/345684870): Add more checks as more operations are supported.
// TODO - b/434244017: Update rules to be in a linked list for faster insertion and deletion.
func (c *Chain) RegisterRule(rule *Rule, index int) *syserr.AnnotatedError {
	// Error checks like these are not part of the nf_tables_api.c. Rather they are error
	// checked here for completeness for unit tests. Netfilter sockets should never attempt to register
	// the exact same rule struct twice.
	if rule.chain != nil {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "rule chain is malformed")
	}

	if index < -1 || index > c.RuleCount() {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("invalid index %d for rule registration with %d rule(s)", index, c.RuleCount()))
	}

	// Checks if there are loops from all jump and goto operations in the rule.
	for _, op := range rule.ops {
		if err := op.checkCompatibility(&opCompatCtx{chain: c}); err != nil {
			return err
		}
		isJumpOrGoto, nextChain := isJumpOrGotoOperation(op)
		if !isJumpOrGoto {
			continue
		}
		if nextChain == nil {
			return syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, "jump or goto operation does not have a target chain")
		}
		if err := nextChain.checkLoops(c, 0); err != nil {
			return err
		}
	}

	// Assigns chain to rule and adds rule to chain's rule list at given index with the given handle.
	rule.chain = c
	rule.handle = c.table.getNewHandle()
	c.handleToRule[rule.handle] = rule

	// Adds the rule to the chain's rule list at the correct index.
	if index == -1 || index == c.RuleCount() {
		c.rules = append(c.rules, rule)
	} else {
		c.rules = slices.Insert(c.rules, index, rule)
	}
	return nil
}

// RegisterBeforeExistingRule registers the new rule before the existing rule.
func (c *Chain) RegisterBeforeExistingRule(newRule *Rule, oldRule *Rule) *syserr.AnnotatedError {
	index, err := c.GetRuleIndex(oldRule)
	if err != nil {
		return err
	}

	return c.RegisterRule(newRule, index)
}

// RegisterAfterExistingRule registers the new rule after the existing rule.
func (c *Chain) RegisterAfterExistingRule(newRule *Rule, oldRule *Rule) *syserr.AnnotatedError {
	index, err := c.GetRuleIndex(oldRule)
	if err != nil {
		return err
	}
	return c.RegisterRule(newRule, index+1)
}

// UnregisterRuleByIndex removes the rule at the given index from the chain's rule list
// and un-assigns the chain from the rule then returns the unregistered rule.
// Valid indices are -1 (pop) and [0, len-1]. Errors on invalid index.
func (c *Chain) UnregisterRuleByIndex(index int) (*Rule, *syserr.AnnotatedError) {
	rule, err := c.GetRule(index)
	if err != nil {
		return nil, err
	}
	if index == -1 {
		index = c.RuleCount() - 1
	}
	c.rules = append(c.rules[:index], c.rules[index+1:]...)
	rule.chain = nil
	delete(c.handleToRule, rule.handle)
	return rule, nil
}

// GetRule returns the rule at the given index in the chain's rule list.
// Valid indices are -1 (last) and [0, len-1]. Errors on invalid index.
func (c *Chain) GetRule(index int) (*Rule, *syserr.AnnotatedError) {
	if index < -1 || index > c.RuleCount()-1 || (index == -1 && c.RuleCount() == 0) {
		return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("invalid index %d for rule retrieval with %d rule(s)", index, c.RuleCount()))
	}
	if index == -1 {
		return c.rules[c.RuleCount()-1], nil
	}
	return c.rules[index], nil
}

// GetRuleByHandle returns the rule with the specified handle from the chain's rule list.
// Errors on rule not found.
func (c *Chain) GetRuleByHandle(handle uint64) (*Rule, *syserr.AnnotatedError) {
	rule, exists := c.handleToRule[handle]
	if !exists {
		return nil, syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("rule with handle %d not found for chain %s", handle, c.name))
	}
	return rule, nil
}

// GetRuleIndex returns the index of the rule in the chain's rule list.
func (c *Chain) GetRuleIndex(r *Rule) (int, *syserr.AnnotatedError) {
	for i, rule := range c.rules {
		if rule == r {
			return i, nil
		}
	}
	return -1, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("index of rule with handle %d not found for chain %s", r.handle, c.name))
}

// RuleCount returns the number of rules in the chain.
func (c *Chain) RuleCount() int {
	return len(c.rules)
}

//
// Loop Checking Helper Functions
//

// isJumpOrGotoOperation returns whether the operation is an
// immediate operation that sets the verdict register
// to a jump or goto verdict, returns pointer to the target chain if so.
func isJumpOrGotoOperation(op operation) (bool, *Chain) {
	imm, ok := op.(*immediate)
	if !ok {
		return false, nil
	}
	if imm.dataType != linux.NFT_DATA_VERDICT {
		return false, nil
	}
	verdict := imm.verdict
	if verdict.Code != VC(linux.NFT_JUMP) && verdict.Code != VC(linux.NFT_GOTO) {
		return false, nil
	}
	return true, verdict.Chain
}

// checkLoops detects if there are any loops via jumps and gotos between chains
// by tracing all immediate operations starting from the destination chain
// of a jump or goto operation and checking that no jump or goto operations lead
// back to the original source chain.
// Note: this loop checking is done whenever a rule is registered to a chain.
func (c *Chain) checkLoops(source *Chain, depth int) *syserr.AnnotatedError {
	// Depth is checked here to prevent invalid rules from being registered. This implicitly
	// checks if we revisit the same chain more than once in a loop.
	// From linux/net/netfilter/nf_tables_api.c:nft_chain_validate
	if depth >= nestedJumpLimit {
		return syserr.NewAnnotatedError(syserr.ErrTooManyLinks, fmt.Sprintf("chain %s has exceeded the nested jump limit of %d", c.name, nestedJumpLimit))
	}

	// Jumping to the same chain is not allowed and although implicitly checked, we explcitly
	// check it here for clarity.
	if c == source {
		return syserr.NewAnnotatedError(syserr.ErrTooManyLinks, fmt.Sprintf("chain %s cannot jump to itself", c.name))
	}

	for _, rule := range c.rules {
		for _, op := range rule.ops {
			isJumpOrGoto, nextChain := isJumpOrGotoOperation(op)
			if !isJumpOrGoto {
				continue
			}
			if nextChain == nil {
				return syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, "jump or goto operation does not have a target chain")
			}

			// Depth is incremented regardless if the verdict is a NFT_JUMP or NFT_GOTO.
			// From net/netfilter/nft_immediate.c:nft_immediate_validate
			depth++
			if err := nextChain.checkLoops(source, depth); err != nil {
				return err
			}
			depth--
		}
	}
	return nil
}

//
// Rule Functions
//

// addOperation adds an operation to the rule. Adding operations is only allowed
// before the rule is registered to a chain. Returns an error if the operation
// is nil or if the rule is already registered to a chain.
func (r *Rule) addOperation(op operation) *syserr.AnnotatedError {
	// From net/netfilter/nf_tables_api.c:nft_expr_type
	if op == nil {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "operation is nil")
	}

	// Netfilter sockets should not try to register operations to rules that
	// have already been registered to a chain. Instead, old rules should be unregistered
	// and new rules should be created.
	if r.chain != nil {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, "cannot add operation to a rule that is already registered to a chain")
	}
	r.ops = append(r.ops, op)
	return nil
}

// AddOpFromExprInfo adds an operation to the rule given the expression information.
func (r *Rule) AddOpFromExprInfo(nf *NFTables, tab *Table, exprInfo ExprInfo) *syserr.AnnotatedError {
	// Centralized here so that operations can do their own validation when being created.
	var op operation
	var err *syserr.AnnotatedError
	exprOpType := ToOpType(exprInfo.ExprName)
	switch exprOpType {
	case OpTypeImmediate:
		if op, err = initImmediate(tab, exprInfo); err != nil {
			return err
		}
	case OpTypePayload:
		if op, err = initPayload(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeBitwise:
		if op, err = initBitwise(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeMeta:
		if op, err = initMeta(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeComparison:
		if op, err = initComparison(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeCounter:
		if op, err = initCounter(exprInfo); err != nil {
			return err
		}
	case OpTypeNAT:
		if op, err = initNATOp(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeLookup:
		if op, err = initLookup(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeFIB:
		if op, err = initFIB(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeCT:
		if op, err = initCT(tab, exprInfo); err != nil {
			return err
		}
	case OpTypeMasq:
		if op, err = initMasqOp(tab, exprInfo); err != nil {
			return err
		}

	default:
		return syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("unknown expression type not found: %s", exprInfo.ExprName))
	}

	if exprOpType == OpTypeCT || exprOpType == OpTypeNAT || exprOpType == OpTypeMasq {
		// NAT and Masq operations require connection tracking.
		nf.InitConnTrackOnce()
	}

	return r.addOperation(op)
}

// GetChain returns the chain that the rule is registered to.
func (r *Rule) GetChain() *Chain {
	return r.chain
}

// GetHandle returns the handle of the rule.
func (r *Rule) GetHandle() uint64 {
	return r.handle
}

// SetUserData sets the user data of the rule.
func (r *Rule) SetUserData(data []byte) *syserr.AnnotatedError {
	if r.udata != nil {
		return syserr.NewAnnotatedError(syserr.ErrNotSupported, "rule already has user data")
	}
	r.udata = make([]byte, len(data))
	copy(r.udata, data)
	return nil
}

// HasUserData returns whether the rule has user data.
func (r *Rule) HasUserData() bool {
	return r.udata != nil
}

// GetUserData returns the user data of the rule.
func (r *Rule) GetUserData() []byte {
	return r.udata
}

// GetAddressFamily returns the address family of the rule.
func (r *Rule) GetAddressFamily() stack.AddressFamily {
	return r.chain.GetAddressFamily()
}

// GetOperations returns the list of operations in the rule.
func (r *Rule) GetOperations() []operation {
	return r.ops
}

// appendBaseChain appends a base chain to the list in ascending priority order.
// Returns false if the chain is not a base chain.
func appendBaseChain(list []*Chain, newBaseChain *Chain) ([]*Chain, bool) {
	if newBaseChain.baseChainInfo == nil {
		return nil, false
	}
	if len(list) == 0 {
		return []*Chain{newBaseChain}, true
	}
	pos, _ := slices.BinarySearchFunc(list, newBaseChain, func(a, b *Chain) int {
		return a.baseChainInfo.Priority.GetValue() - b.baseChainInfo.Priority.GetValue()
	})
	return slices.Insert(list, pos, newBaseChain), true
}

// removeBaseChain removes a base chain with the specified pointer from the list.
// Returns false if the chain doesn't exist.
func removeBaseChain(list []*Chain, c *Chain) ([]*Chain, bool) {
	idx := slices.IndexFunc(list, func(chain *Chain) bool {
		return chain == c
	})
	if idx == -1 {
		return list, false
	}
	return slices.Delete(list, idx, idx+1), true
}

//
// Private hookFunctionStack functions
//

// attachBaseChain adds an (assumed/previously checked) base chain to the stack,
// maintaining ascending priority ordering.
// Note: assumes stack and base chains slice are initialized and is base chain.
func (hfStack *hookFunctionStack) attachBaseChain(chain *Chain) *syserr.AnnotatedError {
	ok := false
	if chain.baseChainInfo.BcType == BaseChainTypeNat {
		hfStack.natBaseChains, ok = appendBaseChain(hfStack.natBaseChains, chain)
	} else {
		hfStack.baseChains, ok = appendBaseChain(hfStack.baseChains, chain)
	}
	if ok {
		return nil
	}
	return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("failed to append base chain: %s", chain.name))
}

// detachBaseChain removes a base chain with the specified pointer from the stack,
// returning an error if the chain doesn't exist.
// Note: assumes stack is initialized.
func (hfStack *hookFunctionStack) detachBaseChain(c *Chain) *syserr.AnnotatedError {
	ok := false
	if hfStack.baseChains, ok = removeBaseChain(hfStack.baseChains, c); ok {
		return nil
	}
	if hfStack.natBaseChains, ok = removeBaseChain(hfStack.natBaseChains, c); ok {
		return nil
	}
	return syserr.NewAnnotatedError(syserr.ErrNoFileOrDir, fmt.Sprintf("failed to detach base chain: %s, chain not found", c.GetName()))
}

//
// NFTables Parser functions
//

// ParseExpr parses the expression attributes and returns the expression information.
func ParseExpr(attrs nlmsg.AttrsView) (*ExprInfo, *syserr.AnnotatedError) {
	exprAttrs, ok := NfParse(attrs)
	if !ok {
		return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "failed to parse attributes for expression")
	}

	exprNameBytes, ok := exprAttrs[linux.NFTA_EXPR_NAME]
	if !ok {
		return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "NFTA_EXPR_NAME attribute is malformed or not found")
	}

	// exprData holds the expression data for a specific operation.
	exprData := nlmsg.AttrsView{}
	// Only assign exprData if the data is present. Later validation will
	// check if it is needed for the specific operation type.
	// From linux/net/netfilter/nf_tables_api.c: nf_tables_expr_parse
	if exprDataBytes, ok := exprAttrs[linux.NFTA_EXPR_DATA]; ok {
		exprData = nlmsg.AttrsView(exprDataBytes)
	}

	return &ExprInfo{
		ExprName: exprNameBytes.String(),
		ExprData: exprData,
	}, nil
}

// ParseNestedExprs parses the nested expression attributes and
// returns the expression information.
func ParseNestedExprs(nestedAttrBytes nlmsg.AttrsView, maxExprs int) ([]ExprInfo, *syserr.AnnotatedError) {
	// Netlink message structure for rule expressions (NFTA_RULE_EXPRESSIONS):
	//
	// [ NFTA_RULE_EXPRESSIONS (Outer Array Container) ]
	//   ├── [ NFTA_LIST_ELEM (Element Wrapper #1) ]
	//   │     ├── [ NFTA_EXPR_NAME ] (e.g., "counter")
	//   │     └── [ NFTA_EXPR_DATA ] (Expression-specific attributes)
	//   │
	//   └── [ NFTA_LIST_ELEM (Element Wrapper #2) ]
	//         ├── [ NFTA_EXPR_NAME ] (e.g., "cmp")
	//         └── [ NFTA_EXPR_DATA ] (Expression-specific attributes)
	var exprInfos []ExprInfo
	numExprs := 0
	for !nestedAttrBytes.Empty() {
		hdr, value, rest, ok := nestedAttrBytes.ParseFirst()
		if !ok {
			return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "failed to parse list attribute for rules")
		}

		nestedAttrBytes = rest
		if hdr.Type&linux.NLA_TYPE_MASK != linux.NFTA_LIST_ELEM {
			return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "parsed attribute is not of type NFTA_LIST_ELEM")
		}

		if numExprs == maxExprs {
			return nil, syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "too many expressions specified for rule")
		}
		numExprs++
		exprInfo, err := ParseExpr(value)
		if err != nil {
			return nil, err
		}
		exprInfos = append(exprInfos, *exprInfo)
	}
	return exprInfos, nil
}

// DecrementChainUse decrements the chain use value of the chain.
func (c *Chain) DecrementChainUse() {
	if c.chainUse > 0 {
		c.chainUse--
	} else {
		log.BugTraceback(fmt.Errorf("chain: %s has chainUse underflow", c.name))
	}
}

func (r *Rule) destroy() {
	for _, op := range r.ops {
		op.destroy()
	}
	r.chain = nil
	r.ops = nil
	r.handle = 0
	r.udata = nil
}

// deleteRuleAtIndex deletes the rule at the index from the chain.
func (c *Chain) deleteRuleAtIndex(index int) *syserr.AnnotatedError {
	if index < 0 || index >= len(c.rules) {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, fmt.Sprintf("invalid rule index %d for chain %s", index, c.name))
	}
	rule := c.rules[index]
	rule.destroy()
	_, err := c.UnregisterRuleByIndex(index)
	return err
}

// DeleteRule removes the rule from the chain.
// Ref: net/netfilter/nf_tables_api.c:nft_delrule
func (c *Chain) DeleteRule(rule *Rule) *syserr.AnnotatedError {
	index, err := c.GetRuleIndex(rule)
	if err != nil {
		return err
	}
	return c.deleteRuleAtIndex(index)
}

// DeleteAllRules removes all rules from the chain.
// Ref: net/netfilter/nf_tables_api.c:nft_delrule_by_chain
func (c *Chain) DeleteAllRules() {
	for _, rule := range c.rules {
		rule.destroy()
	}
	c.rules = nil
	c.handleToRule = make(map[uint64]*Rule)
}

func (c *Chain) destroy() {
	if c.GetChainUse() != 0 {
		log.BugTraceback(fmt.Errorf("chain: %s has chainUse %d != 0", c.name, c.GetChainUse()))
	}
	c.DeleteAllRules()
	c.name = ""
	c.flags = 0
	c.table = nil
	c.baseChainInfo = nil
	c.handleToRule = nil
	c.rules = nil
	c.userData = nil
	c.comment = ""
	c.handle = 0
}

// DeleteRule handles netlink request: NFT_MSG_DELRULE / NFT_MSG_DESTROYRULE.
// Ref: net/netfilter/nf_tables_api.c:nf_tables_delrule
func (nf *NFTables) DeleteRule(attrs map[uint16]nlmsg.BytesView, family stack.AddressFamily, msgType linux.NfTableMsgType, ms *nlmsg.MessageSet) *syserr.AnnotatedError {
	// Get the table from the attributes.
	tabNameBytes, ok := attrs[linux.NFTA_RULE_TABLE]
	if !ok {
		return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "NFTA_RULE_TABLE attribute is malformed or not found")
	}
	tab, err := nf.GetTable(family, tabNameBytes.String(), uint32(ms.PortID))
	if err != nil {
		if err.GetError() == syserr.ErrNoFileOrDir && msgType == linux.NFT_MSG_DESTROYRULE {
			return nil
		}
		return err
	}

	// Find if a chain is specified.
	var chain *Chain
	if chainNameBytes, ok := attrs[linux.NFTA_RULE_CHAIN]; ok {
		chain, err = tab.GetChain(chainNameBytes.String())
		if err != nil {
			if err.GetError() == syserr.ErrNoFileOrDir && msgType == linux.NFT_MSG_DESTROYRULE {
				return nil
			}
			return err
		}
	}

	if chain == nil {
		// Delete all rules in all chains of the table.
		for _, c := range tab.GetChains() {
			if c.GetFlags()&linux.NFT_CHAIN_BINDING != 0 {
				continue
			}
			c.DeleteAllRules()
		}
		return nil
	}

	// Delete rule in the specified chain.
	{
		if chain.GetFlags()&linux.NFT_CHAIN_BINDING != 0 {
			return syserr.NewAnnotatedError(syserr.ErrNotSupported, "operation not supported on binding chains")
		}

		// If a rule is specified, delete it.
		if handleBytes, ok := attrs[linux.NFTA_RULE_HANDLE]; ok {
			ruleHandle, ok := handleBytes.Uint64()
			if !ok {
				return syserr.NewAnnotatedError(syserr.ErrInvalidArgument, "rule handle attribute is malformed or not found")
			}
			rule, err := chain.GetRuleByHandle(nlmsg.NetToHostU64(ruleHandle))
			if err != nil {
				if err.GetError() == syserr.ErrNoFileOrDir && msgType == linux.NFT_MSG_DESTROYRULE {
					return nil
				}
				return err
			}
			return chain.DeleteRule(rule)
		}

		// Delete all rules in chain to clean up operations and object references.
		chain.DeleteAllRules()
	}
	return nil
}
