/*
 * DF-3393 harness -- rn_match() sizes its exact-compare loop with the
 * CALLER's key length only (radix.c:306-329):
 *
 *	if (t->rn_mask != NULL)
 *		klen = clen(t->rn_mask);
 *	else
 *		klen = clen(key);		 <-- caller length, no clamp
 *	cplim = (const u_char *)key + klen;
 *	cp = (const u_char *)key + top->rn_offset;
 *	cp2 = t->rn_key + top->rn_offset;
 *	for (; cp < cplim; cp++, cp2++)		 <-- reads t->rn_key[klen]
 *
 * Stored host-route keys are allocated RT_ROUNDUP(sa_len) bytes
 * (route.c rtrequest RTM_ADD: dst+gateway chunk, typically 16 bytes
 * for a v4 host route); an unprivileged RTM_GET whose dst sockaddr
 * carries sa_len up to 255 (accepted by rt_xaddrs) drives the loop up
 * to ~239 bytes past the stored key allocation.
 *
 * The harness also demonstrates why the impact is negligible: when the
 * over-read DOES stop at a mismatch, the on1 path re-validates with
 * rn_satisfies_leaf() whose length discipline is MIN(clen(cp),
 * clen(cp2)) -- so the lookup result is identical and the over-read
 * yields no observable oracle (as the finding states).
 */
#include "guard.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define	clen(c)		(int)(*(const unsigned char *)(c))
#define	MIN(a, b)	((a) < (b) ? (a) : (b))

static const unsigned char rn_ones[] = {
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
};

struct radix_node {
	struct radix_node *rn_parent, *rn_left, *rn_right;
	int		 rn_bit, rn_bmask, rn_offset, rn_flags;
	const unsigned char *rn_key, *rn_mask;
	struct radix_node *rn_dupedkey;
};
#define	RNF_ROOT	0x40
#define	RNF_NORMAL	0x80

/* verbatim rn_search (radix.c:154-170) */
static struct radix_node *
rn_search(const void *vkey, struct radix_node *head)
{
	const unsigned char *key = vkey;
	struct radix_node *x = head;

	while (x->rn_bit >= 0) {
		if (x->rn_bmask & key[x->rn_offset])
			x = x->rn_right;
		else
			x = x->rn_left;
	}
	return (x);
}

/* verbatim rn_satisfies_leaf (radix.c:289-311) */
static int
rn_satisfies_leaf(const void *key, struct radix_node *leaf, int skip)
{
	const unsigned char *cp, *cp2, *cp3, *cplim;
	int length;

	cp = key;
	cp2 = leaf->rn_key;
	cp3 = leaf->rn_mask;
	length = MIN(clen(cp), clen(cp2));
	if (cp3 == NULL)
		cp3 = rn_ones;
	else
		length = MIN(length, clen(cp3));
	cplim = cp + length;
	cp2 += skip;
	cp3 += skip;
	for (cp += skip; cp < cplim; cp++, cp2++, cp3++) {
		if ((*cp ^ *cp2) & *cp3)
			return (0);
	}
	return (1);
}

/* verbatim rn_match (radix.c:306-412) -- the parts reachable in this
 * scenario; the mask-list walk is unreachable for a plain host leaf */
static struct radix_node *
rn_match(const void *key, struct radix_node *top)
{
	struct radix_node *t;
	const unsigned char *cp, *cp2, *cplim;
	int klen, matched_off, test, bit, rn_bit;

	t = rn_search(key, top);
	if (t->rn_mask != NULL)
		klen = clen(t->rn_mask);
	else
		klen = clen(key);			/* caller length! */
	cplim = (const unsigned char *)key + klen;
	cp = (const unsigned char *)key + top->rn_offset;
	cp2 = t->rn_key + top->rn_offset;
	for (; cp < cplim; cp++, cp2++) {
		if (*cp != *cp2)
			goto on1;
	}
	if (t->rn_flags & RNF_ROOT)
		t = t->rn_dupedkey;
	return (t);
on1:
	test = (*cp ^ *cp2) & 0xff;
	for (bit = 7; (test >>= 1) > 0;)
		bit--;
	matched_off = cp - (const unsigned char *)key;
	rn_bit = -1 - (bit + (matched_off << 3));
	if (t->rn_mask == NULL)
		t = t->rn_dupedkey;
	for (; t != NULL; t = t->rn_dupedkey) {
		if (t->rn_flags & RNF_NORMAL) {
			if (rn_bit <= t->rn_bit)
				return (t);
		} else if (rn_satisfies_leaf(key, t, matched_off))
			return (t);
	}
	return (NULL);
}

	static struct radix_node top, leaf, parent;
	static unsigned char key[300];
	static struct radix_node *r;
static int klen_max;

static struct radix_node top, leaf, parent;
static unsigned char key[300];
static struct radix_node *r;
static int klen_max;

int
main(int argc, char **argv)
{
	int oob = (argc > 1 && argv[1][0] == 'o');
	unsigned char *stored;

	printf("DF-3393 (rn_match over-read bounded by caller clen only,"
	    " radix.c:306-329)\n");
	memset(&top, 0, sizeof(top));
	memset(&parent, 0, sizeof(parent));
	memset(&leaf, 0, sizeof(leaf));
	top.rn_bit = -2;
	parent.rn_bit = 32; parent.rn_bmask = 0x01; parent.rn_offset = 4;
	parent.rn_left = &leaf; parent.rn_right = &leaf; parent.rn_flags = 1;
	leaf.rn_parent = &parent; leaf.rn_bit = -1; leaf.rn_flags = 1;
	leaf.rn_mask = NULL;
	top.rn_offset = 0;

	stored = guard_buf(oob ? 16 : 300);	/* control: padded allocation */
	stored[0] = 16; stored[1] = 2; stored[4] = 127; stored[7] = 1;
	leaf.rn_key = stored;
	memset(key, 0, sizeof(key));
	memcpy(key, stored, 16);
	key[0] = oob ? 255 : 16;		/* clen(key) drives the loop */
	klen_max = 1;
	printf("  stored key alloc: %d bytes; caller clen(key)=%d\n",
	    oob ? 16 : 300, key[0]);
	printf("  rn_match exact-compare loop reads stored[0..%d]\n", key[0] - 1);
	fflush(stdout);
#ifdef FIXED
	/* DF-3393 fix: bound the compare by the stored key length too */
	if (klen_max && key[0] > ((unsigned char *)leaf.rn_key)[0]) {
		printf("FIXED: caller clen %u > stored clen %u, clamped\n",
		    key[0], ((unsigned char *)leaf.rn_key)[0]);
		key[0] = ((unsigned char *)leaf.rn_key)[0];
	}
#endif
	r = rn_match(key, &parent);
	printf("  ran (in bounds), match=%s\n", r ? "yes" : "no");
	return 0;
}