/*
 * str_harness.c -- pass-2 negative-evidence harness for
 *   sys/libkern/strlen.c  (compile without -DSTRNLEN)
 *   sys/libkern/strnlen.c (compile with -DSTRNLEN)
 *
 * 1) embeds the VERBATIM kernel algorithms (byte loops, sys/libkern/
 *    strlen.c:35-42 and sys/libkern/strnlen.c:31-41);
 * 2) differential vs libc strlen/strnlen over a randomized corpus and
 *    boundary maxlens -- must be byte-identical semantics;
 * 3) guard-page boundary proofs:
 *      - NUL as the very last byte of a page: kernel strlen completes
 *        without touching the guard page (reads exactly through the NUL);
 *      - strnlen(buf, n) over an n-byte non-NUL-terminated buffer ending
 *        at the guard boundary: returns n and never touches buf[n];
 *      - strnlen(buf, n+1) on the same buffer SIGSEGVs -- demonstrating
 *        the read bound is EXACTLY maxlen (the caller contract), so the
 *        implementation itself cannot over-read.
 *
 * Build: cc -O2 [-DSTRNLEN] -o str_harness str_harness.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <sys/mman.h>
#include <sys/wait.h>

/* ---- VERBATIM algorithm from sys/libkern/strlen.c:35-42 ---- */
static size_t
k_strlen(const char *str)
{
	const char *s;

	for (s = str; *s; ++s);
	return(s - str);
}

/* ---- VERBATIM algorithm from sys/libkern/strnlen.c:31-41 ---- */
static size_t
k_strnlen(const char *s, size_t maxlen)
{
	size_t len;

	for (len = 0; len < maxlen; len++, s++) {
		if (!*s)
			break;
	}
	return (len);
}

static unsigned char *pbuf;	/* page ending at a guard page */

static void *
buf_at_guard(size_t n)
{
	unsigned char *m = mmap(NULL, 2 * 4096, PROT_READ | PROT_WRITE,
				MAP_ANON | MAP_PRIVATE, -1, 0);
	if (m == MAP_FAILED) { perror("mmap"); exit(2); }
	if (mprotect(m + 4096, 4096, PROT_NONE) != 0) {
		perror("mprotect"); exit(2);
	}
	memset(m, 'A', 4096);
	return (m + 4096 - n);	/* buffer ends exactly at the boundary */
}

static volatile size_t sink;
static int failures;

static int
probe(void (*fn)(void))
{
	pid_t p = fork();
	int st;
	if (p == 0) { fn(); _exit(0); }
	waitpid(p, &st, 0);
	return (WIFSIGNALED(st) && WTERMSIG(st) == SIGSEGV);
}

#ifdef STRNLEN
static void pr_eq(void)   { sink = k_strnlen(pbuf, 300); }   /* == size */
static void pr_over(void) { sink = k_strnlen(pbuf, 301); }   /* size + 1 */
static void pr_zero(void) { sink = k_strnlen(pbuf, 0); }
#else
static void pr_nul_last(void) { pbuf[299] = 0; sink = k_strlen((char *)pbuf); }
#endif

int
main(void)
{
	setvbuf(stdout, NULL, _IONBF, 0);
	srand(0xdfb5d);

	/* ---- 1) randomized + boundary differential vs libc ---- */
	{
		static const size_t maxlens[] = { 0, 1, 2, 7, 63, 64, 255,
						  256, 511, 4095, 4096,
						  65535, (size_t)-1 };
		size_t cases = 0, bad = 0;
		size_t sz;
		for (sz = 0; sz <= 4096; sz += (sz < 4 ? 1 : (sz < 64 ? 13 :
		     (sz < 1024 ? 197 : 991)))) {
			char b[4097];
			size_t i;
			for (i = 0; i < sz; i++)
				b[i] = (rand() % 16) ? 'x' + (rand() & 3) : 0;
			b[sz] = 0;
			/* whole-string comparisons */
			if (k_strlen(b) != strlen(b)) bad++;
			cases++;
			/* insert a random early NUL and re-compare */
			if (sz > 1) {
				size_t z = (size_t)rand() % sz;
				char sv = b[z]; b[z] = 0;
				if (k_strlen(b) != strlen(b)) bad++;
				b[z] = sv;
				cases++;
			}
#ifdef STRNLEN
			{
				size_t mi;
				for (mi = 0; mi < sizeof(maxlens) /
				     sizeof(maxlens[0]); mi++) {
					size_t m = maxlens[mi];
					/* cap m to the allocation + 1 */
					if (m > sz + 1)
						m = sz + 1;
					if (k_strnlen(b, m) !=
					    strnlen(b, m)) bad++;
					cases++;
				}
			}
#endif
		}
		printf("libc differential: %zu cases, %zu mismatches -> %s\n",
		       cases, bad, bad ? "FAIL" : "IDENTICAL");
		failures += (bad != 0);
	}

	/* ---- 2) guard-page boundary proofs ---- */
#ifdef STRNLEN
	pbuf = buf_at_guard(300);	/* 300 non-NUL bytes, ends at guard */
	{
		size_t v = k_strnlen((char *)pbuf, 300);
		int f = probe(pr_eq);
		int o = probe(pr_over);
		int z = probe(pr_zero);
		printf("strnlen(buf,300) on 300-byte non-NUL buffer at guard:"
		       " value=%zu fault=%s (expect 0)\n", v,
		       f ? "YES" : "no");
		failures += (v != 300) || f;
		printf("strnlen(buf,301) same buffer            : fault=%s"
		       " (expect YES -- bound is exactly maxlen, this is the"
		       " caller contract, not an implementation over-read)\n",
		       o ? "YES" : "no");
		printf("strnlen(buf,0)                          : value=%zu"
		       " fault=%s (expect 0/no)\n",
		       k_strnlen((char *)pbuf, 0), z ? "YES" : "no");
		failures += z;
	}
#else
	pbuf = buf_at_guard(300);
	{
		int f;
		pbuf[299] = 0;	/* NUL is the last byte before the guard */
		f = probe(pr_nul_last);
		printf("strlen with NUL as final byte at guard page: value=%zu"
		       " fault=%s (expect no fault)\n",
		       k_strlen((char *)pbuf), f ? "YES" : "no");
		failures += f;
	}
#endif
	printf("%s: %s\n", __FILE__,
	       failures ? "FAILURES PRESENT" : "semantics identical to libc;"
	       " boundary reads exactly as contracted");
	return (failures ? 1 : 0);
}