[mirror_ubuntu-bionic-kernel.git] / net / core / filter.c

/*
 * Linux Socket Filter - Kernel level socket filtering
 *
 * Author:
 *     Jay Schulist <jschlst@samba.org>
 *
 * Based on the design of:
 *     - The Berkeley Packet Filter
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version
 * 2 of the License, or (at your option) any later version.
 *
 * Andi Kleen - Fix a few bad bugs and races.
 * Kris Katterjohn - Added many additional checks in sk_chk_filter()
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/mm.h>
#include <linux/fcntl.h>
#include <linux/socket.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/if_packet.h>
#include <linux/gfp.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/netlink.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <linux/errno.h>
#include <linux/timer.h>
#include <asm/system.h>
#include <asm/uaccess.h>
#include <asm/unaligned.h>
#include <linux/filter.h>
#include <linux/reciprocal_div.h>

enum {
	BPF_S_RET_K = 1,
	BPF_S_RET_A,
	BPF_S_ALU_ADD_K,
	BPF_S_ALU_ADD_X,
	BPF_S_ALU_SUB_K,
	BPF_S_ALU_SUB_X,
	BPF_S_ALU_MUL_K,
	BPF_S_ALU_MUL_X,
	BPF_S_ALU_DIV_X,
	BPF_S_ALU_AND_K,
	BPF_S_ALU_AND_X,
	BPF_S_ALU_OR_K,
	BPF_S_ALU_OR_X,
	BPF_S_ALU_LSH_K,
	BPF_S_ALU_LSH_X,
	BPF_S_ALU_RSH_K,
	BPF_S_ALU_RSH_X,
	BPF_S_ALU_NEG,
	BPF_S_LD_W_ABS,
	BPF_S_LD_H_ABS,
	BPF_S_LD_B_ABS,
	BPF_S_LD_W_LEN,
	BPF_S_LD_W_IND,
	BPF_S_LD_H_IND,
	BPF_S_LD_B_IND,
	BPF_S_LD_IMM,
	BPF_S_LDX_W_LEN,
	BPF_S_LDX_B_MSH,
	BPF_S_LDX_IMM,
	BPF_S_MISC_TAX,
	BPF_S_MISC_TXA,
	BPF_S_ALU_DIV_K,
	BPF_S_LD_MEM,
	BPF_S_LDX_MEM,
	BPF_S_ST,
	BPF_S_STX,
	BPF_S_JMP_JA,
	BPF_S_JMP_JEQ_K,
	BPF_S_JMP_JEQ_X,
	BPF_S_JMP_JGE_K,
	BPF_S_JMP_JGE_X,
	BPF_S_JMP_JGT_K,
	BPF_S_JMP_JGT_X,
	BPF_S_JMP_JSET_K,
	BPF_S_JMP_JSET_X,
	/* Ancillary data */
	BPF_S_ANC_PROTOCOL,
	BPF_S_ANC_PKTTYPE,
	BPF_S_ANC_IFINDEX,
	BPF_S_ANC_NLATTR,
	BPF_S_ANC_NLATTR_NEST,
	BPF_S_ANC_MARK,
	BPF_S_ANC_QUEUE,
	BPF_S_ANC_HATYPE,
	BPF_S_ANC_RXHASH,
	BPF_S_ANC_CPU,
};

/* No hurry in this branch */
static void *__load_pointer(const struct sk_buff *skb, int k, unsigned int size)
{
	u8 *ptr = NULL;

	if (k >= SKF_NET_OFF)
		ptr = skb_network_header(skb) + k - SKF_NET_OFF;
	else if (k >= SKF_LL_OFF)
		ptr = skb_mac_header(skb) + k - SKF_LL_OFF;

	if (ptr >= skb->head && ptr + size <= skb_tail_pointer(skb))
		return ptr;
	return NULL;
}

static inline void *load_pointer(const struct sk_buff *skb, int k,
				 unsigned int size, void *buffer)
{
	if (k >= 0)
		return skb_header_pointer(skb, k, size, buffer);
	return __load_pointer(skb, k, size);
}

/**
 *	sk_filter - run a packet through a socket filter
 *	@sk: sock associated with &sk_buff
 *	@skb: buffer to filter
 *
 * Run the filter code and then cut skb->data to correct size returned by
 * sk_run_filter. If pkt_len is 0 we toss packet. If skb->len is smaller
 * than pkt_len we keep whole skb->data. This is the socket level
 * wrapper to sk_run_filter. It returns 0 if the packet should
 * be accepted or -EPERM if the packet should be tossed.
 *
 */
int sk_filter(struct sock *sk, struct sk_buff *skb)
{
	int err;
	struct sk_filter *filter;

	err = security_sock_rcv_skb(sk, skb);
	if (err)
		return err;

	rcu_read_lock();
	filter = rcu_dereference(sk->sk_filter);
	if (filter) {
		unsigned int pkt_len = sk_run_filter(skb, filter->insns);

		err = pkt_len ? pskb_trim(skb, pkt_len) : -EPERM;
	}
	rcu_read_unlock();

	return err;
}
EXPORT_SYMBOL(sk_filter);

/**
 *	sk_run_filter - run a filter on a socket
 *	@skb: buffer to run the filter on
 *	@fentry: filter to apply
 *
 * Decode and apply filter instructions to the skb->data.
 * Return length to keep, 0 for none. @skb is the data we are
 * filtering, @filter is the array of filter instructions.
 * Because all jumps are guaranteed to be before last instruction,
 * and last instruction guaranteed to be a RET, we dont need to check
 * flen. (We used to pass to this function the length of filter)
 */
unsigned int sk_run_filter(const struct sk_buff *skb,
			   const struct sock_filter *fentry)
{
	void *ptr;
	u32 A = 0;			/* Accumulator */
	u32 X = 0;			/* Index Register */
	u32 mem[BPF_MEMWORDS];		/* Scratch Memory Store */
	u32 tmp;
	int k;

	/*
	 * Process array of filter instructions.
	 */
	for (;; fentry++) {
#if defined(CONFIG_X86_32)
#define	K (fentry->k)
#else
		const u32 K = fentry->k;
#endif

		switch (fentry->code) {
		case BPF_S_ALU_ADD_X:
			A += X;
			continue;
		case BPF_S_ALU_ADD_K:
			A += K;
			continue;
		case BPF_S_ALU_SUB_X:
			A -= X;
			continue;
		case BPF_S_ALU_SUB_K:
			A -= K;
			continue;
		case BPF_S_ALU_MUL_X:
			A *= X;
			continue;
		case BPF_S_ALU_MUL_K:
			A *= K;
			continue;
		case BPF_S_ALU_DIV_X:
			if (X == 0)
				return 0;
			A /= X;
			continue;
		case BPF_S_ALU_DIV_K:
			A = reciprocal_divide(A, K);
			continue;
		case BPF_S_ALU_AND_X:
			A &= X;
			continue;
		case BPF_S_ALU_AND_K:
			A &= K;
			continue;
		case BPF_S_ALU_OR_X:
			A |= X;
			continue;
		case BPF_S_ALU_OR_K:
			A |= K;
			continue;
		case BPF_S_ALU_LSH_X:
			A <<= X;
			continue;
		case BPF_S_ALU_LSH_K:
			A <<= K;
			continue;
		case BPF_S_ALU_RSH_X:
			A >>= X;
			continue;
		case BPF_S_ALU_RSH_K:
			A >>= K;
			continue;
		case BPF_S_ALU_NEG:
			A = -A;
			continue;
		case BPF_S_JMP_JA:
			fentry += K;
			continue;
		case BPF_S_JMP_JGT_K:
			fentry += (A > K) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JGE_K:
			fentry += (A >= K) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JEQ_K:
			fentry += (A == K) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JSET_K:
			fentry += (A & K) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JGT_X:
			fentry += (A > X) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JGE_X:
			fentry += (A >= X) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JEQ_X:
			fentry += (A == X) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_JMP_JSET_X:
			fentry += (A & X) ? fentry->jt : fentry->jf;
			continue;
		case BPF_S_LD_W_ABS:
			k = K;
load_w:
			ptr = load_pointer(skb, k, 4, &tmp);
			if (ptr != NULL) {
				A = get_unaligned_be32(ptr);
				continue;
			}
			return 0;
		case BPF_S_LD_H_ABS:
			k = K;
load_h:
			ptr = load_pointer(skb, k, 2, &tmp);
			if (ptr != NULL) {
				A = get_unaligned_be16(ptr);
				continue;
			}
			return 0;
		case BPF_S_LD_B_ABS:
			k = K;
load_b:
			ptr = load_pointer(skb, k, 1, &tmp);
			if (ptr != NULL) {
				A = *(u8 *)ptr;
				continue;
			}
			return 0;
		case BPF_S_LD_W_LEN:
			A = skb->len;
			continue;
		case BPF_S_LDX_W_LEN:
			X = skb->len;
			continue;
		case BPF_S_LD_W_IND:
			k = X + K;
			goto load_w;
		case BPF_S_LD_H_IND:
			k = X + K;
			goto load_h;
		case BPF_S_LD_B_IND:
			k = X + K;
			goto load_b;
		case BPF_S_LDX_B_MSH:
			ptr = load_pointer(skb, K, 1, &tmp);
			if (ptr != NULL) {
				X = (*(u8 *)ptr & 0xf) << 2;
				continue;
			}
			return 0;
		case BPF_S_LD_IMM:
			A = K;
			continue;
		case BPF_S_LDX_IMM:
			X = K;
			continue;
		case BPF_S_LD_MEM:
			A = mem[K];
			continue;
		case BPF_S_LDX_MEM:
			X = mem[K];
			continue;
		case BPF_S_MISC_TAX:
			X = A;
			continue;
		case BPF_S_MISC_TXA:
			A = X;
			continue;
		case BPF_S_RET_K:
			return K;
		case BPF_S_RET_A:
			return A;
		case BPF_S_ST:
			mem[K] = A;
			continue;
		case BPF_S_STX:
			mem[K] = X;
			continue;
		case BPF_S_ANC_PROTOCOL:
			A = ntohs(skb->protocol);
			continue;
		case BPF_S_ANC_PKTTYPE:
			A = skb->pkt_type;
			continue;
		case BPF_S_ANC_IFINDEX:
			if (!skb->dev)
				return 0;
			A = skb->dev->ifindex;
			continue;
		case BPF_S_ANC_MARK:
			A = skb->mark;
			continue;
		case BPF_S_ANC_QUEUE:
			A = skb->queue_mapping;
			continue;
		case BPF_S_ANC_HATYPE:
			if (!skb->dev)
				return 0;
			A = skb->dev->type;
			continue;
		case BPF_S_ANC_RXHASH:
			A = skb->rxhash;
			continue;
		case BPF_S_ANC_CPU:
			A = raw_smp_processor_id();
			continue;
		case BPF_S_ANC_NLATTR: {
			struct nlattr *nla;

			if (skb_is_nonlinear(skb))
				return 0;
			if (A > skb->len - sizeof(struct nlattr))
				return 0;

			nla = nla_find((struct nlattr *)&skb->data[A],
				       skb->len - A, X);
			if (nla)
				A = (void *)nla - (void *)skb->data;
			else
				A = 0;
			continue;
		}
		case BPF_S_ANC_NLATTR_NEST: {
			struct nlattr *nla;

			if (skb_is_nonlinear(skb))
				return 0;
			if (A > skb->len - sizeof(struct nlattr))
				return 0;

			nla = (struct nlattr *)&skb->data[A];
			if (nla->nla_len > A - skb->len)
				return 0;

			nla = nla_find_nested(nla, X);
			if (nla)
				A = (void *)nla - (void *)skb->data;
			else
				A = 0;
			continue;
		}
		default:
			WARN_ON(1);
			return 0;
		}
	}

	return 0;
}
EXPORT_SYMBOL(sk_run_filter);

/*
 * Security :
 * A BPF program is able to use 16 cells of memory to store intermediate
 * values (check u32 mem[BPF_MEMWORDS] in sk_run_filter())
 * As we dont want to clear mem[] array for each packet going through
 * sk_run_filter(), we check that filter loaded by user never try to read
 * a cell if not previously written, and we check all branches to be sure
 * a malicious user doesn't try to abuse us.
 */
static int check_load_and_stores(struct sock_filter *filter, int flen)
{
	u16 *masks, memvalid = 0; /* one bit per cell, 16 cells */
	int pc, ret = 0;

	BUILD_BUG_ON(BPF_MEMWORDS > 16);
	masks = kmalloc(flen * sizeof(*masks), GFP_KERNEL);
	if (!masks)
		return -ENOMEM;
	memset(masks, 0xff, flen * sizeof(*masks));

	for (pc = 0; pc < flen; pc++) {
		memvalid &= masks[pc];

		switch (filter[pc].code) {
		case BPF_S_ST:
		case BPF_S_STX:
			memvalid |= (1 << filter[pc].k);
			break;
		case BPF_S_LD_MEM:
		case BPF_S_LDX_MEM:
			if (!(memvalid & (1 << filter[pc].k))) {
				ret = -EINVAL;
				goto error;
			}
			break;
		case BPF_S_JMP_JA:
			/* a jump must set masks on target */
			masks[pc + 1 + filter[pc].k] &= memvalid;
			memvalid = ~0;
			break;
		case BPF_S_JMP_JEQ_K:
		case BPF_S_JMP_JEQ_X:
		case BPF_S_JMP_JGE_K:
		case BPF_S_JMP_JGE_X:
		case BPF_S_JMP_JGT_K:
		case BPF_S_JMP_JGT_X:
		case BPF_S_JMP_JSET_X:
		case BPF_S_JMP_JSET_K:
			/* a jump must set masks on targets */
			masks[pc + 1 + filter[pc].jt] &= memvalid;
			masks[pc + 1 + filter[pc].jf] &= memvalid;
			memvalid = ~0;
			break;
		}
	}
error:
	kfree(masks);
	return ret;
}

/**
 *	sk_chk_filter - verify socket filter code
 *	@filter: filter to verify
 *	@flen: length of filter
 *
 * Check the user's filter code. If we let some ugly
 * filter code slip through kaboom! The filter must contain
 * no references or jumps that are out of range, no illegal
 * instructions, and must end with a RET instruction.
 *
 * All jumps are forward as they are not signed.
 *
 * Returns 0 if the rule set is legal or -EINVAL if not.
 */
int sk_chk_filter(struct sock_filter *filter, int flen)
{
	/*
	 * Valid instructions are initialized to non-0.
	 * Invalid instructions are initialized to 0.
	 */
	static const u8 codes[] = {
		[BPF_ALU|BPF_ADD|BPF_K]  = BPF_S_ALU_ADD_K,
		[BPF_ALU|BPF_ADD|BPF_X]  = BPF_S_ALU_ADD_X,
		[BPF_ALU|BPF_SUB|BPF_K]  = BPF_S_ALU_SUB_K,
		[BPF_ALU|BPF_SUB|BPF_X]  = BPF_S_ALU_SUB_X,
		[BPF_ALU|BPF_MUL|BPF_K]  = BPF_S_ALU_MUL_K,
		[BPF_ALU|BPF_MUL|BPF_X]  = BPF_S_ALU_MUL_X,
		[BPF_ALU|BPF_DIV|BPF_X]  = BPF_S_ALU_DIV_X,
		[BPF_ALU|BPF_AND|BPF_K]  = BPF_S_ALU_AND_K,
		[BPF_ALU|BPF_AND|BPF_X]  = BPF_S_ALU_AND_X,
		[BPF_ALU|BPF_OR|BPF_K]   = BPF_S_ALU_OR_K,
		[BPF_ALU|BPF_OR|BPF_X]   = BPF_S_ALU_OR_X,
		[BPF_ALU|BPF_LSH|BPF_K]  = BPF_S_ALU_LSH_K,
		[BPF_ALU|BPF_LSH|BPF_X]  = BPF_S_ALU_LSH_X,
		[BPF_ALU|BPF_RSH|BPF_K]  = BPF_S_ALU_RSH_K,
		[BPF_ALU|BPF_RSH|BPF_X]  = BPF_S_ALU_RSH_X,
		[BPF_ALU|BPF_NEG]        = BPF_S_ALU_NEG,
		[BPF_LD|BPF_W|BPF_ABS]   = BPF_S_LD_W_ABS,
		[BPF_LD|BPF_H|BPF_ABS]   = BPF_S_LD_H_ABS,
		[BPF_LD|BPF_B|BPF_ABS]   = BPF_S_LD_B_ABS,
		[BPF_LD|BPF_W|BPF_LEN]   = BPF_S_LD_W_LEN,
		[BPF_LD|BPF_W|BPF_IND]   = BPF_S_LD_W_IND,
		[BPF_LD|BPF_H|BPF_IND]   = BPF_S_LD_H_IND,
		[BPF_LD|BPF_B|BPF_IND]   = BPF_S_LD_B_IND,
		[BPF_LD|BPF_IMM]         = BPF_S_LD_IMM,
		[BPF_LDX|BPF_W|BPF_LEN]  = BPF_S_LDX_W_LEN,
		[BPF_LDX|BPF_B|BPF_MSH]  = BPF_S_LDX_B_MSH,
		[BPF_LDX|BPF_IMM]        = BPF_S_LDX_IMM,
		[BPF_MISC|BPF_TAX]       = BPF_S_MISC_TAX,
		[BPF_MISC|BPF_TXA]       = BPF_S_MISC_TXA,
		[BPF_RET|BPF_K]          = BPF_S_RET_K,
		[BPF_RET|BPF_A]          = BPF_S_RET_A,
		[BPF_ALU|BPF_DIV|BPF_K]  = BPF_S_ALU_DIV_K,
		[BPF_LD|BPF_MEM]         = BPF_S_LD_MEM,
		[BPF_LDX|BPF_MEM]        = BPF_S_LDX_MEM,
		[BPF_ST]                 = BPF_S_ST,
		[BPF_STX]                = BPF_S_STX,
		[BPF_JMP|BPF_JA]         = BPF_S_JMP_JA,
		[BPF_JMP|BPF_JEQ|BPF_K]  = BPF_S_JMP_JEQ_K,
		[BPF_JMP|BPF_JEQ|BPF_X]  = BPF_S_JMP_JEQ_X,
		[BPF_JMP|BPF_JGE|BPF_K]  = BPF_S_JMP_JGE_K,
		[BPF_JMP|BPF_JGE|BPF_X]  = BPF_S_JMP_JGE_X,
		[BPF_JMP|BPF_JGT|BPF_K]  = BPF_S_JMP_JGT_K,
		[BPF_JMP|BPF_JGT|BPF_X]  = BPF_S_JMP_JGT_X,
		[BPF_JMP|BPF_JSET|BPF_K] = BPF_S_JMP_JSET_K,
		[BPF_JMP|BPF_JSET|BPF_X] = BPF_S_JMP_JSET_X,
	};
	int pc;

	if (flen == 0 || flen > BPF_MAXINSNS)
		return -EINVAL;

	/* check the filter code now */
	for (pc = 0; pc < flen; pc++) {
		struct sock_filter *ftest = &filter[pc];
		u16 code = ftest->code;

		if (code >= ARRAY_SIZE(codes))
			return -EINVAL;
		code = codes[code];
		if (!code)
			return -EINVAL;
		/* Some instructions need special checks */
		switch (code) {
		case BPF_S_ALU_DIV_K:
			/* check for division by zero */
			if (ftest->k == 0)
				return -EINVAL;
			ftest->k = reciprocal_value(ftest->k);
			break;
		case BPF_S_LD_MEM:
		case BPF_S_LDX_MEM:
		case BPF_S_ST:
		case BPF_S_STX:
			/* check for invalid memory addresses */
			if (ftest->k >= BPF_MEMWORDS)
				return -EINVAL;
			break;
		case BPF_S_JMP_JA:
			/*
			 * Note, the large ftest->k might cause loops.
			 * Compare this with conditional jumps below,
			 * where offsets are limited. --ANK (981016)
			 */
			if (ftest->k >= (unsigned)(flen-pc-1))
				return -EINVAL;
			break;
		case BPF_S_JMP_JEQ_K:
		case BPF_S_JMP_JEQ_X:
		case BPF_S_JMP_JGE_K:
		case BPF_S_JMP_JGE_X:
		case BPF_S_JMP_JGT_K:
		case BPF_S_JMP_JGT_X:
		case BPF_S_JMP_JSET_X:
		case BPF_S_JMP_JSET_K:
			/* for conditionals both must be safe */
			if (pc + ftest->jt + 1 >= flen ||
			    pc + ftest->jf + 1 >= flen)
				return -EINVAL;
			break;
		case BPF_S_LD_W_ABS:
		case BPF_S_LD_H_ABS:
		case BPF_S_LD_B_ABS:
#define ANCILLARY(CODE) case SKF_AD_OFF + SKF_AD_##CODE:	\
				code = BPF_S_ANC_##CODE;	\
				break
			switch (ftest->k) {
			ANCILLARY(PROTOCOL);
			ANCILLARY(PKTTYPE);
			ANCILLARY(IFINDEX);
			ANCILLARY(NLATTR);
			ANCILLARY(NLATTR_NEST);
			ANCILLARY(MARK);
			ANCILLARY(QUEUE);
			ANCILLARY(HATYPE);
			ANCILLARY(RXHASH);
			ANCILLARY(CPU);
			}
		}
		ftest->code = code;
	}

	/* last instruction must be a RET code */
	switch (filter[flen - 1].code) {
	case BPF_S_RET_K:
	case BPF_S_RET_A:
		return check_load_and_stores(filter, flen);
	}
	return -EINVAL;
}
EXPORT_SYMBOL(sk_chk_filter);

/**
 * 	sk_filter_release_rcu - Release a socket filter by rcu_head
 *	@rcu: rcu_head that contains the sk_filter to free
 */
void sk_filter_release_rcu(struct rcu_head *rcu)
{
	struct sk_filter *fp = container_of(rcu, struct sk_filter, rcu);

	kfree(fp);
}
EXPORT_SYMBOL(sk_filter_release_rcu);

/**
 *	sk_attach_filter - attach a socket filter
 *	@fprog: the filter program
 *	@sk: the socket to use
 *
 * Attach the user's filter code. We first run some sanity checks on
 * it to make sure it does not explode on us later. If an error
 * occurs or there is insufficient memory for the filter a negative
 * errno code is returned. On success the return is zero.
 */
int sk_attach_filter(struct sock_fprog *fprog, struct sock *sk)
{
	struct sk_filter *fp, *old_fp;
	unsigned int fsize = sizeof(struct sock_filter) * fprog->len;
	int err;

	/* Make sure new filter is there and in the right amounts. */
	if (fprog->filter == NULL)
		return -EINVAL;

	fp = sock_kmalloc(sk, fsize+sizeof(*fp), GFP_KERNEL);
	if (!fp)
		return -ENOMEM;
	if (copy_from_user(fp->insns, fprog->filter, fsize)) {
		sock_kfree_s(sk, fp, fsize+sizeof(*fp));
		return -EFAULT;
	}

	atomic_set(&fp->refcnt, 1);
	fp->len = fprog->len;

	err = sk_chk_filter(fp->insns, fp->len);
	if (err) {
		sk_filter_uncharge(sk, fp);
		return err;
	}

	old_fp = rcu_dereference_protected(sk->sk_filter,
					   sock_owned_by_user(sk));
	rcu_assign_pointer(sk->sk_filter, fp);

	if (old_fp)
		sk_filter_uncharge(sk, old_fp);
	return 0;
}
EXPORT_SYMBOL_GPL(sk_attach_filter);

int sk_detach_filter(struct sock *sk)
{
	int ret = -ENOENT;
	struct sk_filter *filter;

	filter = rcu_dereference_protected(sk->sk_filter,
					   sock_owned_by_user(sk));
	if (filter) {
		rcu_assign_pointer(sk->sk_filter, NULL);
		sk_filter_uncharge(sk, filter);
		ret = 0;
	}
	return ret;
}
EXPORT_SYMBOL_GPL(sk_detach_filter);
Commit	Line	Data
1da177e4 LT	1	/*
	2	* Linux Socket Filter - Kernel level socket filtering
	3	*
	4	* Author:
	5	* Jay Schulist <jschlst@samba.org>
	6	*
	7	* Based on the design of:
	8	* - The Berkeley Packet Filter
	9	*
	10	* This program is free software; you can redistribute it and/or
	11	* modify it under the terms of the GNU General Public License
	12	* as published by the Free Software Foundation; either version
	13	* 2 of the License, or (at your option) any later version.
	14	*
	15	* Andi Kleen - Fix a few bad bugs and races.
93699863	16	* Kris Katterjohn - Added many additional checks in sk_chk_filter()
1da177e4 LT	17	*/
	18
	19	#include <linux/module.h>
	20	#include <linux/types.h>
1da177e4 LT	21	#include <linux/mm.h>
	22	#include <linux/fcntl.h>
	23	#include <linux/socket.h>
	24	#include <linux/in.h>
	25	#include <linux/inet.h>
	26	#include <linux/netdevice.h>
	27	#include <linux/if_packet.h>
5a0e3ad6	28	#include <linux/gfp.h>
1da177e4 LT	29	#include <net/ip.h>
1da177e4 LT	30	#include <net/protocol.h>
4738c1db	31	#include <net/netlink.h>
1da177e4 LT	32	#include <linux/skbuff.h>
	33	#include <net/sock.h>
	34	#include <linux/errno.h>
	35	#include <linux/timer.h>
	36	#include <asm/system.h>
	37	#include <asm/uaccess.h>
40daafc8	38	#include <asm/unaligned.h>
1da177e4	39	#include <linux/filter.h>
c26aed40	40	#include <linux/reciprocal_div.h>
1da177e4	41
4c3710af	42	enum {
8c1592d6	43	BPF_S_RET_K = 1,
4c3710af CG	44	BPF_S_RET_A,
	45	BPF_S_ALU_ADD_K,
	46	BPF_S_ALU_ADD_X,
	47	BPF_S_ALU_SUB_K,
	48	BPF_S_ALU_SUB_X,
	49	BPF_S_ALU_MUL_K,
	50	BPF_S_ALU_MUL_X,
	51	BPF_S_ALU_DIV_X,
	52	BPF_S_ALU_AND_K,
	53	BPF_S_ALU_AND_X,
	54	BPF_S_ALU_OR_K,
	55	BPF_S_ALU_OR_X,
	56	BPF_S_ALU_LSH_K,
	57	BPF_S_ALU_LSH_X,
	58	BPF_S_ALU_RSH_K,
	59	BPF_S_ALU_RSH_X,
	60	BPF_S_ALU_NEG,
	61	BPF_S_LD_W_ABS,
	62	BPF_S_LD_H_ABS,
	63	BPF_S_LD_B_ABS,
	64	BPF_S_LD_W_LEN,
	65	BPF_S_LD_W_IND,
	66	BPF_S_LD_H_IND,
	67	BPF_S_LD_B_IND,
	68	BPF_S_LD_IMM,
	69	BPF_S_LDX_W_LEN,
	70	BPF_S_LDX_B_MSH,
	71	BPF_S_LDX_IMM,
	72	BPF_S_MISC_TAX,
	73	BPF_S_MISC_TXA,
	74	BPF_S_ALU_DIV_K,
	75	BPF_S_LD_MEM,
	76	BPF_S_LDX_MEM,
	77	BPF_S_ST,
	78	BPF_S_STX,
	79	BPF_S_JMP_JA,
	80	BPF_S_JMP_JEQ_K,
	81	BPF_S_JMP_JEQ_X,
	82	BPF_S_JMP_JGE_K,
	83	BPF_S_JMP_JGE_X,
	84	BPF_S_JMP_JGT_K,
	85	BPF_S_JMP_JGT_X,
	86	BPF_S_JMP_JSET_K,
	87	BPF_S_JMP_JSET_X,
12b16dad ED	88	/* Ancillary data */
	89	BPF_S_ANC_PROTOCOL,
	90	BPF_S_ANC_PKTTYPE,
	91	BPF_S_ANC_IFINDEX,
	92	BPF_S_ANC_NLATTR,
	93	BPF_S_ANC_NLATTR_NEST,
	94	BPF_S_ANC_MARK,
	95	BPF_S_ANC_QUEUE,
	96	BPF_S_ANC_HATYPE,
	97	BPF_S_ANC_RXHASH,
	98	BPF_S_ANC_CPU,
4c3710af CG	99	};
4c3710af CG	100
1da177e4	101	/* No hurry in this branch */
4bc65dd8	102	static void __load_pointer(const struct sk_buff skb, int k, unsigned int size)
1da177e4 LT	103	{
	104	u8 *ptr = NULL;
	105
	106	if (k >= SKF_NET_OFF)
d56f90a7	107	ptr = skb_network_header(skb) + k - SKF_NET_OFF;
1da177e4	108	else if (k >= SKF_LL_OFF)
98e399f8	109	ptr = skb_mac_header(skb) + k - SKF_LL_OFF;
1da177e4	110
4bc65dd8	111	if (ptr >= skb->head && ptr + size <= skb_tail_pointer(skb))
1da177e4 LT	112	return ptr;
	113	return NULL;
	114	}
	115
62ab0812	116	static inline void load_pointer(const struct sk_buff skb, int k,
4ec93edb	117	unsigned int size, void *buffer)
0b05b2a4 PM	118	{
	119	if (k >= 0)
	120	return skb_header_pointer(skb, k, size, buffer);
12b16dad	121	return __load_pointer(skb, k, size);
0b05b2a4 PM	122	}
0b05b2a4 PM	123
43db6d65 SH	124	/**
	125	* sk_filter - run a packet through a socket filter
	126	* @sk: sock associated with &sk_buff
	127	* @skb: buffer to filter
43db6d65 SH	128	*
	129	* Run the filter code and then cut skb->data to correct size returned by
	130	* sk_run_filter. If pkt_len is 0 we toss packet. If skb->len is smaller
	131	* than pkt_len we keep whole skb->data. This is the socket level
	132	* wrapper to sk_run_filter. It returns 0 if the packet should
	133	* be accepted or -EPERM if the packet should be tossed.
	134	*
	135	*/
	136	int sk_filter(struct sock sk, struct sk_buff skb)
	137	{
	138	int err;
	139	struct sk_filter *filter;
	140
	141	err = security_sock_rcv_skb(sk, skb);
	142	if (err)
	143	return err;
	144
80f8f102 ED	145	rcu_read_lock();
80f8f102 ED	146	filter = rcu_dereference(sk->sk_filter);
43db6d65	147	if (filter) {
93aaae2e	148	unsigned int pkt_len = sk_run_filter(skb, filter->insns);
0d7da9dd	149
43db6d65 SH	150	err = pkt_len ? pskb_trim(skb, pkt_len) : -EPERM;
43db6d65 SH	151	}
80f8f102	152	rcu_read_unlock();
43db6d65 SH	153
	154	return err;
	155	}
	156	EXPORT_SYMBOL(sk_filter);
	157
1da177e4	158	/**
2966b66c	159	* sk_run_filter - run a filter on a socket
1da177e4	160	* @skb: buffer to run the filter on
697d0e33	161	* @fentry: filter to apply
1da177e4 LT	162	*
1da177e4 LT	163	* Decode and apply filter instructions to the skb->data.
93aaae2e ED	164	* Return length to keep, 0 for none. @skb is the data we are
	165	* filtering, @filter is the array of filter instructions.
	166	* Because all jumps are guaranteed to be before last instruction,
	167	* and last instruction guaranteed to be a RET, we dont need to check
	168	* flen. (We used to pass to this function the length of filter)
1da177e4	169	*/
62ab0812 ED	170	unsigned int sk_run_filter(const struct sk_buff *skb,
62ab0812 ED	171	const struct sock_filter *fentry)
1da177e4	172	{
0b05b2a4	173	void *ptr;
2966b66c KK	174	u32 A = 0; /* Accumulator */
2966b66c KK	175	u32 X = 0; /* Index Register */
1da177e4	176	u32 mem[BPF_MEMWORDS]; /* Scratch Memory Store */
0b05b2a4	177	u32 tmp;
1da177e4	178	int k;
1da177e4 LT	179
	180	/*
	181	* Process array of filter instructions.
	182	*/
93aaae2e ED	183	for (;; fentry++) {
	184	#if defined(CONFIG_X86_32)
	185	#define K (fentry->k)
	186	#else
	187	const u32 K = fentry->k;
	188	#endif
4ec93edb	189
1da177e4	190	switch (fentry->code) {
01f2f3f6	191	case BPF_S_ALU_ADD_X:
1da177e4 LT	192	A += X;
1da177e4 LT	193	continue;
01f2f3f6	194	case BPF_S_ALU_ADD_K:
93aaae2e	195	A += K;
1da177e4	196	continue;
01f2f3f6	197	case BPF_S_ALU_SUB_X:
1da177e4 LT	198	A -= X;
1da177e4 LT	199	continue;
01f2f3f6	200	case BPF_S_ALU_SUB_K:
93aaae2e	201	A -= K;
1da177e4	202	continue;
01f2f3f6	203	case BPF_S_ALU_MUL_X:
1da177e4 LT	204	A *= X;
1da177e4 LT	205	continue;
01f2f3f6	206	case BPF_S_ALU_MUL_K:
93aaae2e	207	A *= K;
1da177e4	208	continue;
01f2f3f6	209	case BPF_S_ALU_DIV_X:
1da177e4 LT	210	if (X == 0)
	211	return 0;
	212	A /= X;
	213	continue;
01f2f3f6	214	case BPF_S_ALU_DIV_K:
c26aed40	215	A = reciprocal_divide(A, K);
1da177e4	216	continue;
01f2f3f6	217	case BPF_S_ALU_AND_X:
1da177e4 LT	218	A &= X;
1da177e4 LT	219	continue;
01f2f3f6	220	case BPF_S_ALU_AND_K:
93aaae2e	221	A &= K;
1da177e4	222	continue;
01f2f3f6	223	case BPF_S_ALU_OR_X:
1da177e4 LT	224	A \|= X;
1da177e4 LT	225	continue;
01f2f3f6	226	case BPF_S_ALU_OR_K:
93aaae2e	227	A \|= K;
1da177e4	228	continue;
01f2f3f6	229	case BPF_S_ALU_LSH_X:
1da177e4 LT	230	A <<= X;
1da177e4 LT	231	continue;
01f2f3f6	232	case BPF_S_ALU_LSH_K:
93aaae2e	233	A <<= K;
1da177e4	234	continue;
01f2f3f6	235	case BPF_S_ALU_RSH_X:
1da177e4 LT	236	A >>= X;
1da177e4 LT	237	continue;
01f2f3f6	238	case BPF_S_ALU_RSH_K:
93aaae2e	239	A >>= K;
1da177e4	240	continue;
01f2f3f6	241	case BPF_S_ALU_NEG:
1da177e4 LT	242	A = -A;
1da177e4 LT	243	continue;
01f2f3f6	244	case BPF_S_JMP_JA:
93aaae2e	245	fentry += K;
1da177e4	246	continue;
01f2f3f6	247	case BPF_S_JMP_JGT_K:
93aaae2e	248	fentry += (A > K) ? fentry->jt : fentry->jf;
1da177e4	249	continue;
01f2f3f6	250	case BPF_S_JMP_JGE_K:
93aaae2e	251	fentry += (A >= K) ? fentry->jt : fentry->jf;
1da177e4	252	continue;
01f2f3f6	253	case BPF_S_JMP_JEQ_K:
93aaae2e	254	fentry += (A == K) ? fentry->jt : fentry->jf;
1da177e4	255	continue;
01f2f3f6	256	case BPF_S_JMP_JSET_K:
93aaae2e	257	fentry += (A & K) ? fentry->jt : fentry->jf;
1da177e4	258	continue;
01f2f3f6	259	case BPF_S_JMP_JGT_X:
93aaae2e	260	fentry += (A > X) ? fentry->jt : fentry->jf;
1da177e4	261	continue;
01f2f3f6	262	case BPF_S_JMP_JGE_X:
93aaae2e	263	fentry += (A >= X) ? fentry->jt : fentry->jf;
1da177e4	264	continue;
01f2f3f6	265	case BPF_S_JMP_JEQ_X:
93aaae2e	266	fentry += (A == X) ? fentry->jt : fentry->jf;
1da177e4	267	continue;
01f2f3f6	268	case BPF_S_JMP_JSET_X:
93aaae2e	269	fentry += (A & X) ? fentry->jt : fentry->jf;
1da177e4	270	continue;
01f2f3f6	271	case BPF_S_LD_W_ABS:
93aaae2e	272	k = K;
e35bedf3	273	load_w:
0b05b2a4 PM	274	ptr = load_pointer(skb, k, 4, &tmp);
0b05b2a4 PM	275	if (ptr != NULL) {
d3e2ce3b	276	A = get_unaligned_be32(ptr);
0b05b2a4	277	continue;
1da177e4	278	}
12b16dad	279	return 0;
01f2f3f6	280	case BPF_S_LD_H_ABS:
93aaae2e	281	k = K;
e35bedf3	282	load_h:
0b05b2a4 PM	283	ptr = load_pointer(skb, k, 2, &tmp);
0b05b2a4 PM	284	if (ptr != NULL) {
d3e2ce3b	285	A = get_unaligned_be16(ptr);
0b05b2a4	286	continue;
1da177e4	287	}
12b16dad	288	return 0;
01f2f3f6	289	case BPF_S_LD_B_ABS:
93aaae2e	290	k = K;
1da177e4	291	load_b:
0b05b2a4 PM	292	ptr = load_pointer(skb, k, 1, &tmp);
	293	if (ptr != NULL) {
	294	A = (u8 )ptr;
	295	continue;
1da177e4	296	}
12b16dad	297	return 0;
01f2f3f6	298	case BPF_S_LD_W_LEN:
3154e540	299	A = skb->len;
1da177e4	300	continue;
01f2f3f6	301	case BPF_S_LDX_W_LEN:
3154e540	302	X = skb->len;
1da177e4	303	continue;
01f2f3f6	304	case BPF_S_LD_W_IND:
93aaae2e	305	k = X + K;
1da177e4	306	goto load_w;
01f2f3f6	307	case BPF_S_LD_H_IND:
93aaae2e	308	k = X + K;
1da177e4	309	goto load_h;
01f2f3f6	310	case BPF_S_LD_B_IND:
93aaae2e	311	k = X + K;
1da177e4	312	goto load_b;
01f2f3f6	313	case BPF_S_LDX_B_MSH:
93aaae2e	314	ptr = load_pointer(skb, K, 1, &tmp);
0b05b2a4 PM	315	if (ptr != NULL) {
	316	X = ((u8 )ptr & 0xf) << 2;
	317	continue;
	318	}
	319	return 0;
01f2f3f6	320	case BPF_S_LD_IMM:
93aaae2e	321	A = K;
1da177e4	322	continue;
01f2f3f6	323	case BPF_S_LDX_IMM:
93aaae2e	324	X = K;
1da177e4	325	continue;
01f2f3f6	326	case BPF_S_LD_MEM:
2d5311e4	327	A = mem[K];
1da177e4	328	continue;
01f2f3f6	329	case BPF_S_LDX_MEM:
2d5311e4	330	X = mem[K];
1da177e4	331	continue;
01f2f3f6	332	case BPF_S_MISC_TAX:
1da177e4 LT	333	X = A;
1da177e4 LT	334	continue;
01f2f3f6	335	case BPF_S_MISC_TXA:
1da177e4 LT	336	A = X;
1da177e4 LT	337	continue;
01f2f3f6	338	case BPF_S_RET_K:
93aaae2e	339	return K;
01f2f3f6	340	case BPF_S_RET_A:
4bad4dc9	341	return A;
01f2f3f6	342	case BPF_S_ST:
93aaae2e	343	mem[K] = A;
1da177e4	344	continue;
01f2f3f6	345	case BPF_S_STX:
93aaae2e	346	mem[K] = X;
1da177e4	347	continue;
12b16dad	348	case BPF_S_ANC_PROTOCOL:
252e3346	349	A = ntohs(skb->protocol);
1da177e4	350	continue;
12b16dad	351	case BPF_S_ANC_PKTTYPE:
1da177e4 LT	352	A = skb->pkt_type;
1da177e4 LT	353	continue;
12b16dad	354	case BPF_S_ANC_IFINDEX:
40eaf962 PLE	355	if (!skb->dev)
40eaf962 PLE	356	return 0;
1da177e4 LT	357	A = skb->dev->ifindex;
1da177e4 LT	358	continue;
12b16dad	359	case BPF_S_ANC_MARK:
7e75f93e	360	A = skb->mark;
7e75f93e	361	continue;
12b16dad	362	case BPF_S_ANC_QUEUE:
d19742fb ED	363	A = skb->queue_mapping;
d19742fb ED	364	continue;
12b16dad	365	case BPF_S_ANC_HATYPE:
40eaf962 PLE	366	if (!skb->dev)
	367	return 0;
	368	A = skb->dev->type;
	369	continue;
12b16dad	370	case BPF_S_ANC_RXHASH:
da2033c2 ED	371	A = skb->rxhash;
da2033c2 ED	372	continue;
12b16dad	373	case BPF_S_ANC_CPU:
da2033c2 ED	374	A = raw_smp_processor_id();
da2033c2 ED	375	continue;
12b16dad	376	case BPF_S_ANC_NLATTR: {
4738c1db PM	377	struct nlattr *nla;
	378
	379	if (skb_is_nonlinear(skb))
	380	return 0;
	381	if (A > skb->len - sizeof(struct nlattr))
	382	return 0;
	383
	384	nla = nla_find((struct nlattr *)&skb->data[A],
	385	skb->len - A, X);
	386	if (nla)
	387	A = (void )nla - (void )skb->data;
	388	else
	389	A = 0;
	390	continue;
	391	}
12b16dad	392	case BPF_S_ANC_NLATTR_NEST: {
d214c753 PNA	393	struct nlattr *nla;
	394
	395	if (skb_is_nonlinear(skb))
	396	return 0;
	397	if (A > skb->len - sizeof(struct nlattr))
	398	return 0;
	399
	400	nla = (struct nlattr *)&skb->data[A];
	401	if (nla->nla_len > A - skb->len)
	402	return 0;
	403
	404	nla = nla_find_nested(nla, X);
	405	if (nla)
	406	A = (void )nla - (void )skb->data;
	407	else
	408	A = 0;
	409	continue;
	410	}
1da177e4	411	default:
12b16dad	412	WARN_ON(1);
1da177e4 LT	413	return 0;
	414	}
	415	}
	416
	417	return 0;
	418	}
b715631f	419	EXPORT_SYMBOL(sk_run_filter);
1da177e4	420
2d5311e4 ED	421	/*
	422	* Security :
	423	* A BPF program is able to use 16 cells of memory to store intermediate
	424	* values (check u32 mem[BPF_MEMWORDS] in sk_run_filter())
	425	* As we dont want to clear mem[] array for each packet going through
	426	* sk_run_filter(), we check that filter loaded by user never try to read
	427	* a cell if not previously written, and we check all branches to be sure
25985edc	428	* a malicious user doesn't try to abuse us.
2d5311e4 ED	429	*/
	430	static int check_load_and_stores(struct sock_filter *filter, int flen)
	431	{
	432	u16 masks, memvalid = 0; / one bit per cell, 16 cells */
	433	int pc, ret = 0;
	434
	435	BUILD_BUG_ON(BPF_MEMWORDS > 16);
	436	masks = kmalloc(flen * sizeof(*masks), GFP_KERNEL);
	437	if (!masks)
	438	return -ENOMEM;
	439	memset(masks, 0xff, flen * sizeof(*masks));
	440
	441	for (pc = 0; pc < flen; pc++) {
	442	memvalid &= masks[pc];
	443
	444	switch (filter[pc].code) {
	445	case BPF_S_ST:
	446	case BPF_S_STX:
	447	memvalid \|= (1 << filter[pc].k);
	448	break;
	449	case BPF_S_LD_MEM:
	450	case BPF_S_LDX_MEM:
	451	if (!(memvalid & (1 << filter[pc].k))) {
	452	ret = -EINVAL;
	453	goto error;
	454	}
	455	break;
	456	case BPF_S_JMP_JA:
	457	/* a jump must set masks on target */
	458	masks[pc + 1 + filter[pc].k] &= memvalid;
	459	memvalid = ~0;
	460	break;
	461	case BPF_S_JMP_JEQ_K:
	462	case BPF_S_JMP_JEQ_X:
	463	case BPF_S_JMP_JGE_K:
	464	case BPF_S_JMP_JGE_X:
	465	case BPF_S_JMP_JGT_K:
	466	case BPF_S_JMP_JGT_X:
	467	case BPF_S_JMP_JSET_X:
	468	case BPF_S_JMP_JSET_K:
	469	/* a jump must set masks on targets */
	470	masks[pc + 1 + filter[pc].jt] &= memvalid;
	471	masks[pc + 1 + filter[pc].jf] &= memvalid;
	472	memvalid = ~0;
	473	break;
	474	}
	475	}
	476	error:
	477	kfree(masks);
	478	return ret;
	479	}
	480
1da177e4 LT	481	/**
	482	* sk_chk_filter - verify socket filter code
	483	* @filter: filter to verify
	484	* @flen: length of filter
	485	*
	486	* Check the user's filter code. If we let some ugly
	487	* filter code slip through kaboom! The filter must contain
93699863 KK	488	* no references or jumps that are out of range, no illegal
93699863 KK	489	* instructions, and must end with a RET instruction.
1da177e4	490	*
7b11f69f KK	491	* All jumps are forward as they are not signed.
	492	*
	493	* Returns 0 if the rule set is legal or -EINVAL if not.
1da177e4 LT	494	*/
	495	int sk_chk_filter(struct sock_filter *filter, int flen)
	496	{
cba328fc TH	497	/*
	498	* Valid instructions are initialized to non-0.
	499	* Invalid instructions are initialized to 0.
	500	*/
	501	static const u8 codes[] = {
8c1592d6 ED	502	[BPF_ALU\|BPF_ADD\|BPF_K] = BPF_S_ALU_ADD_K,
	503	[BPF_ALU\|BPF_ADD\|BPF_X] = BPF_S_ALU_ADD_X,
	504	[BPF_ALU\|BPF_SUB\|BPF_K] = BPF_S_ALU_SUB_K,
	505	[BPF_ALU\|BPF_SUB\|BPF_X] = BPF_S_ALU_SUB_X,
	506	[BPF_ALU\|BPF_MUL\|BPF_K] = BPF_S_ALU_MUL_K,
	507	[BPF_ALU\|BPF_MUL\|BPF_X] = BPF_S_ALU_MUL_X,
	508	[BPF_ALU\|BPF_DIV\|BPF_X] = BPF_S_ALU_DIV_X,
	509	[BPF_ALU\|BPF_AND\|BPF_K] = BPF_S_ALU_AND_K,
	510	[BPF_ALU\|BPF_AND\|BPF_X] = BPF_S_ALU_AND_X,
	511	[BPF_ALU\|BPF_OR\|BPF_K] = BPF_S_ALU_OR_K,
	512	[BPF_ALU\|BPF_OR\|BPF_X] = BPF_S_ALU_OR_X,
	513	[BPF_ALU\|BPF_LSH\|BPF_K] = BPF_S_ALU_LSH_K,
	514	[BPF_ALU\|BPF_LSH\|BPF_X] = BPF_S_ALU_LSH_X,
	515	[BPF_ALU\|BPF_RSH\|BPF_K] = BPF_S_ALU_RSH_K,
	516	[BPF_ALU\|BPF_RSH\|BPF_X] = BPF_S_ALU_RSH_X,
	517	[BPF_ALU\|BPF_NEG] = BPF_S_ALU_NEG,
	518	[BPF_LD\|BPF_W\|BPF_ABS] = BPF_S_LD_W_ABS,
	519	[BPF_LD\|BPF_H\|BPF_ABS] = BPF_S_LD_H_ABS,
	520	[BPF_LD\|BPF_B\|BPF_ABS] = BPF_S_LD_B_ABS,
	521	[BPF_LD\|BPF_W\|BPF_LEN] = BPF_S_LD_W_LEN,
	522	[BPF_LD\|BPF_W\|BPF_IND] = BPF_S_LD_W_IND,
	523	[BPF_LD\|BPF_H\|BPF_IND] = BPF_S_LD_H_IND,
	524	[BPF_LD\|BPF_B\|BPF_IND] = BPF_S_LD_B_IND,
	525	[BPF_LD\|BPF_IMM] = BPF_S_LD_IMM,
	526	[BPF_LDX\|BPF_W\|BPF_LEN] = BPF_S_LDX_W_LEN,
	527	[BPF_LDX\|BPF_B\|BPF_MSH] = BPF_S_LDX_B_MSH,
	528	[BPF_LDX\|BPF_IMM] = BPF_S_LDX_IMM,
	529	[BPF_MISC\|BPF_TAX] = BPF_S_MISC_TAX,
	530	[BPF_MISC\|BPF_TXA] = BPF_S_MISC_TXA,
	531	[BPF_RET\|BPF_K] = BPF_S_RET_K,
	532	[BPF_RET\|BPF_A] = BPF_S_RET_A,
	533	[BPF_ALU\|BPF_DIV\|BPF_K] = BPF_S_ALU_DIV_K,
	534	[BPF_LD\|BPF_MEM] = BPF_S_LD_MEM,
	535	[BPF_LDX\|BPF_MEM] = BPF_S_LDX_MEM,
	536	[BPF_ST] = BPF_S_ST,
	537	[BPF_STX] = BPF_S_STX,
	538	[BPF_JMP\|BPF_JA] = BPF_S_JMP_JA,
	539	[BPF_JMP\|BPF_JEQ\|BPF_K] = BPF_S_JMP_JEQ_K,
	540	[BPF_JMP\|BPF_JEQ\|BPF_X] = BPF_S_JMP_JEQ_X,
	541	[BPF_JMP\|BPF_JGE\|BPF_K] = BPF_S_JMP_JGE_K,
	542	[BPF_JMP\|BPF_JGE\|BPF_X] = BPF_S_JMP_JGE_X,
	543	[BPF_JMP\|BPF_JGT\|BPF_K] = BPF_S_JMP_JGT_K,
	544	[BPF_JMP\|BPF_JGT\|BPF_X] = BPF_S_JMP_JGT_X,
	545	[BPF_JMP\|BPF_JSET\|BPF_K] = BPF_S_JMP_JSET_K,
	546	[BPF_JMP\|BPF_JSET\|BPF_X] = BPF_S_JMP_JSET_X,
cba328fc	547	};
1da177e4 LT	548	int pc;
1da177e4 LT	549
1b93ae64	550	if (flen == 0 \|\| flen > BPF_MAXINSNS)
1da177e4 LT	551	return -EINVAL;
	552
	553	/* check the filter code now */
	554	for (pc = 0; pc < flen; pc++) {
cba328fc TH	555	struct sock_filter *ftest = &filter[pc];
cba328fc TH	556	u16 code = ftest->code;
93699863	557
cba328fc TH	558	if (code >= ARRAY_SIZE(codes))
	559	return -EINVAL;
	560	code = codes[code];
8c1592d6	561	if (!code)
cba328fc	562	return -EINVAL;
93699863	563	/* Some instructions need special checks */
cba328fc TH	564	switch (code) {
cba328fc TH	565	case BPF_S_ALU_DIV_K:
93699863 KK	566	/* check for division by zero */
93699863 KK	567	if (ftest->k == 0)
1da177e4	568	return -EINVAL;
c26aed40	569	ftest->k = reciprocal_value(ftest->k);
93699863	570	break;
cba328fc TH	571	case BPF_S_LD_MEM:
	572	case BPF_S_LDX_MEM:
	573	case BPF_S_ST:
	574	case BPF_S_STX:
	575	/* check for invalid memory addresses */
93699863 KK	576	if (ftest->k >= BPF_MEMWORDS)
	577	return -EINVAL;
	578	break;
cba328fc	579	case BPF_S_JMP_JA:
93699863 KK	580	/*
	581	* Note, the large ftest->k might cause loops.
	582	* Compare this with conditional jumps below,
	583	* where offsets are limited. --ANK (981016)
	584	*/
	585	if (ftest->k >= (unsigned)(flen-pc-1))
	586	return -EINVAL;
01f2f3f6	587	break;
01f2f3f6 HPP	588	case BPF_S_JMP_JEQ_K:
	589	case BPF_S_JMP_JEQ_X:
	590	case BPF_S_JMP_JGE_K:
	591	case BPF_S_JMP_JGE_X:
	592	case BPF_S_JMP_JGT_K:
	593	case BPF_S_JMP_JGT_X:
	594	case BPF_S_JMP_JSET_X:
	595	case BPF_S_JMP_JSET_K:
cba328fc	596	/* for conditionals both must be safe */
e35bedf3	597	if (pc + ftest->jt + 1 >= flen \|\|
93699863 KK	598	pc + ftest->jf + 1 >= flen)
93699863 KK	599	return -EINVAL;
cba328fc	600	break;
12b16dad ED	601	case BPF_S_LD_W_ABS:
	602	case BPF_S_LD_H_ABS:
	603	case BPF_S_LD_B_ABS:
	604	#define ANCILLARY(CODE) case SKF_AD_OFF + SKF_AD_##CODE: \
	605	code = BPF_S_ANC_##CODE; \
	606	break
	607	switch (ftest->k) {
	608	ANCILLARY(PROTOCOL);
	609	ANCILLARY(PKTTYPE);
	610	ANCILLARY(IFINDEX);
	611	ANCILLARY(NLATTR);
	612	ANCILLARY(NLATTR_NEST);
	613	ANCILLARY(MARK);
	614	ANCILLARY(QUEUE);
	615	ANCILLARY(HATYPE);
	616	ANCILLARY(RXHASH);
	617	ANCILLARY(CPU);
	618	}
01f2f3f6	619	}
cba328fc	620	ftest->code = code;
01f2f3f6	621	}
93699863	622
01f2f3f6 HPP	623	/* last instruction must be a RET code */
	624	switch (filter[flen - 1].code) {
	625	case BPF_S_RET_K:
	626	case BPF_S_RET_A:
2d5311e4	627	return check_load_and_stores(filter, flen);
cba328fc TH	628	}
cba328fc TH	629	return -EINVAL;
1da177e4	630	}
b715631f	631	EXPORT_SYMBOL(sk_chk_filter);
1da177e4	632
47e958ea	633	/**
46bcf14f	634	* sk_filter_release_rcu - Release a socket filter by rcu_head
47e958ea PE	635	* @rcu: rcu_head that contains the sk_filter to free
47e958ea PE	636	*/
46bcf14f	637	void sk_filter_release_rcu(struct rcu_head *rcu)
47e958ea PE	638	{
	639	struct sk_filter *fp = container_of(rcu, struct sk_filter, rcu);
	640
46bcf14f	641	kfree(fp);
47e958ea	642	}
46bcf14f	643	EXPORT_SYMBOL(sk_filter_release_rcu);
47e958ea	644
1da177e4 LT	645	/**
	646	* sk_attach_filter - attach a socket filter
	647	* @fprog: the filter program
	648	* @sk: the socket to use
	649	*
	650	* Attach the user's filter code. We first run some sanity checks on
	651	* it to make sure it does not explode on us later. If an error
	652	* occurs or there is insufficient memory for the filter a negative
	653	* errno code is returned. On success the return is zero.
	654	*/
	655	int sk_attach_filter(struct sock_fprog fprog, struct sock sk)
	656	{
d3904b73	657	struct sk_filter fp, old_fp;
1da177e4 LT	658	unsigned int fsize = sizeof(struct sock_filter) * fprog->len;
	659	int err;
	660
	661	/* Make sure new filter is there and in the right amounts. */
e35bedf3 KK	662	if (fprog->filter == NULL)
e35bedf3 KK	663	return -EINVAL;
1da177e4 LT	664
	665	fp = sock_kmalloc(sk, fsize+sizeof(*fp), GFP_KERNEL);
	666	if (!fp)
	667	return -ENOMEM;
	668	if (copy_from_user(fp->insns, fprog->filter, fsize)) {
4ec93edb	669	sock_kfree_s(sk, fp, fsize+sizeof(*fp));
1da177e4 LT	670	return -EFAULT;
	671	}
	672
	673	atomic_set(&fp->refcnt, 1);
	674	fp->len = fprog->len;
	675
	676	err = sk_chk_filter(fp->insns, fp->len);
d3904b73 PE	677	if (err) {
	678	sk_filter_uncharge(sk, fp);
	679	return err;
1da177e4 LT	680	}
1da177e4 LT	681
f91ff5b9 ED	682	old_fp = rcu_dereference_protected(sk->sk_filter,
f91ff5b9 ED	683	sock_owned_by_user(sk));
d3904b73	684	rcu_assign_pointer(sk->sk_filter, fp);
d3904b73	685
9b013e05	686	if (old_fp)
46bcf14f	687	sk_filter_uncharge(sk, old_fp);
d3904b73	688	return 0;
1da177e4	689	}
5ff3f073	690	EXPORT_SYMBOL_GPL(sk_attach_filter);
1da177e4	691
55b33325 PE	692	int sk_detach_filter(struct sock *sk)
	693	{
	694	int ret = -ENOENT;
	695	struct sk_filter *filter;
	696
f91ff5b9 ED	697	filter = rcu_dereference_protected(sk->sk_filter,
f91ff5b9 ED	698	sock_owned_by_user(sk));
55b33325 PE	699	if (filter) {
55b33325 PE	700	rcu_assign_pointer(sk->sk_filter, NULL);
46bcf14f	701	sk_filter_uncharge(sk, filter);
55b33325 PE	702	ret = 0;
55b33325 PE	703	}
55b33325 PE	704	return ret;
55b33325 PE	705	}
5ff3f073	706	EXPORT_SYMBOL_GPL(sk_detach_filter);