/*--------------------------------------------------------------------------
 *
 * test_bloomfilter.c
 *		Test false positive rate of Bloom filter.
 *
 * Copyright (c) 2018-2021, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *		src/test/modules/test_bloomfilter/test_bloomfilter.c
 *
 * -------------------------------------------------------------------------
 */
#include "postgres.h"

#include "fmgr.h"
#include "lib/bloomfilter.h"
#include "miscadmin.h"

PG_MODULE_MAGIC;

/* Fits decimal representation of PG_INT64_MIN + 2 bytes: */
#define MAX_ELEMENT_BYTES		21
/* False positive rate WARNING threshold (1%): */
#define FPOSITIVE_THRESHOLD		0.01


/*
 * Populate an empty Bloom filter with "nelements" dummy strings.
 */
static void
populate_with_dummy_strings(bloom_filter *filter, int64 nelements)
{
	char		element[MAX_ELEMENT_BYTES];
	int64		i;

	for (i = 0; i < nelements; i++)
	{
		CHECK_FOR_INTERRUPTS();

		snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
		bloom_add_element(filter, (unsigned char *) element, strlen(element));
	}
}

/*
 * Returns number of strings that are indicated as probably appearing in Bloom
 * filter that were in fact never added by populate_with_dummy_strings().
 * These are false positives.
 */
static int64
nfalsepos_for_missing_strings(bloom_filter *filter, int64 nelements)
{
	char		element[MAX_ELEMENT_BYTES];
	int64		nfalsepos = 0;
	int64		i;

	for (i = 0; i < nelements; i++)
	{
		CHECK_FOR_INTERRUPTS();

		snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
		if (!bloom_lacks_element(filter, (unsigned char *) element,
								 strlen(element)))
			nfalsepos++;
	}

	return nfalsepos;
}

static void
create_and_test_bloom(int power, int64 nelements, int callerseed)
{
	int			bloom_work_mem;
	uint64		seed;
	int64		nfalsepos;
	bloom_filter *filter;

	bloom_work_mem = (1L << power) / 8L / 1024L;

	elog(DEBUG1, "bloom_work_mem (KB): %d", bloom_work_mem);

	/*
	 * Generate random seed, or use caller's.  Seed should always be a
	 * positive value less than or equal to PG_INT32_MAX, to ensure that any
	 * random seed can be recreated through callerseed if the need arises.
	 * (Don't assume that RAND_MAX cannot exceed PG_INT32_MAX.)
	 */
	seed = callerseed < 0 ? random() % PG_INT32_MAX : callerseed;

	/* Create Bloom filter, populate it, and report on false positive rate */
	filter = bloom_create(nelements, bloom_work_mem, seed);
	populate_with_dummy_strings(filter, nelements);
	nfalsepos = nfalsepos_for_missing_strings(filter, nelements);

	ereport((nfalsepos > nelements * FPOSITIVE_THRESHOLD) ? WARNING : DEBUG1,
			(errmsg_internal("seed: " UINT64_FORMAT " false positives: " INT64_FORMAT " (%.6f%%) bitset %.2f%% set",
							 seed, nfalsepos, (double) nfalsepos / nelements,
							 100.0 * bloom_prop_bits_set(filter))));

	bloom_free(filter);
}

PG_FUNCTION_INFO_V1(test_bloomfilter);

/*
 * SQL-callable entry point to perform all tests.
 *
 * If a 1% false positive threshold is not met, emits WARNINGs.
 *
 * See README for details of arguments.
 */
Datum
test_bloomfilter(PG_FUNCTION_ARGS)
{
	int			power = PG_GETARG_INT32(0);
	int64		nelements = PG_GETARG_INT64(1);
	int			seed = PG_GETARG_INT32(2);
	int			tests = PG_GETARG_INT32(3);
	int			i;

	if (power < 23 || power > 32)
		elog(ERROR, "power argument must be between 23 and 32 inclusive");

	if (tests <= 0)
		elog(ERROR, "invalid number of tests: %d", tests);

	if (nelements < 0)
		elog(ERROR, "invalid number of elements: %d", tests);

	for (i = 0; i < tests; i++)
	{
		elog(DEBUG1, "beginning test #%d...", i + 1);

		create_and_test_bloom(power, nelements, seed);
	}

	PG_RETURN_VOID();
}
