shttpd/tests/bitvec.c

// SPDX-License-Identifier: GPL-2.0 or GPL-3.0
// Copyright © 2018-2019 Ariadne Devos
/* sHT -- test the sHT_bit_test function */

#include <sHT/bitvec.h>
#include <sHT/index.h>
#include <sHT/test.h>

#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

/* This tests that:
   * the bit vector may be unaligned,
   * the bit order is correct.
   * the vector may be longer than 64-bits
   * no memory before or after the bitvector is accessed
     (on virtual-memory systems)
   * the bitvector may be read-only
     (on virtual-memory systems).

   The correctness of the bit vector is verified with a typical
   reference implementation, and a trivial table lookup. -- s^2
   does not always use the reference implementation, on x86, it
   uses a special instruction.

   Very hypothetical TODO: this test could be speculatively unsafe. */

/* A random bitvector, expanded to @var{reference}. */
const uint8_t compact[] = {
	0b00110101,

	0b11010101,
	0b01101110,
	0b10110110,
	0b11000101,

	0b00100111,
	0b00000010,
	0b10011001,
	0b00000000,

	0b10001111,
	0b10100001,
	0b11001001,
	0b00111001,

	0b11100001,
	0b10011110,
	0b10101010,
	0b00110101,
};

static const _Bool reference[] = {
	1, 0, 1, 0, 1, 1, 0, 0,

	1, 0, 1, 0, 1, 0, 1, 1,
	0, 1, 1, 1, 0, 1, 1, 0,
	0, 1, 1, 0, 1, 1, 0, 1,
	1, 0, 1, 0, 0, 0, 1, 1,

	1, 1, 1, 0, 0, 1, 0, 0,
	0, 1, 0, 0, 0, 0, 0, 0,
	1, 0, 0, 1, 1, 0, 0, 1,
	0, 0, 0, 0, 0, 0, 0, 0,

	1, 1, 1, 1, 0, 0, 0, 1,
	1, 0, 0, 0, 0, 1, 0, 1,
	1, 0, 0, 1, 0, 0, 1, 1,
	1, 0, 0, 1, 1, 1, 0, 0,

	1, 0, 0, 0, 0, 1, 1, 1,
	0, 1, 1, 1, 1, 0, 0, 1,
	0, 1, 0, 1, 0, 1, 0, 1,
	1, 0, 1, 0, 1, 1, 0, 0,
};

#define reference_test(i, vec) ((_Bool) ((vec)[(i) / 8] & (1 << ((i) % 8))))

int
main(void)
{
	/* Make three different tables:
	  one at the end of a page,
	  one the beginning of a page,
	  and the original table.

	  Allocate three pages, write the bitvector,
	  then disallow access to the start and the end
	  and only allow read access to the middle.
	  If the bit vector code then tries to trespass the boundary,
	  or write to the bitvector, a segfault results.

	  x86 has bit test instructions that change the bit vector,
	  so it makes sense to require read-only access. */
	unsigned long page_size;
#ifdef PAGE_SIZE
	page_size = PAGE_SIZE;
#else
	page_size = sysconf(_SC_PAGESIZE);
	if (page_size == (unsigned long) (long) -1) {
		perror("not posix: _SC_PAGESIZE");
		return 2;
	}
#endif
	if (2 * sizeof(compact) > page_size) {
		fprintf(stderr, "%s", "very small pages\n");
		return 2;
	}

	uint8_t *start = mmap(NULL, 3 * page_size, PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	if (sHT_eq_pointer(start, MAP_FAILED)) {
		perror("allocate memory");
		return 2;
	}
	memcpy(start + page_size, compact, sizeof(compact));
	memcpy(start + 2 * page_size - sizeof(compact), compact, sizeof(compact));
	if (mprotect(start, page_size, PROT_NONE))
		goto prot_change_error;
	if (mprotect(start + page_size, page_size, PROT_READ))
		goto prot_change_error;
	if (mprotect(start + 2 * page_size, page_size, PROT_NONE)) {
	prot_change_error:
		perror("change protections");
		return 2;
	}

	const uint8_t *vec1 = compact;
	const uint8_t *vec2 = start + page_size;
	const uint8_t *vec3 = start + 2 * page_size - sizeof(compact);

	/* Compare two implementations on the three bitvectors
	   with the reference table. */
	size_t i;
	sHT_index_iterate(i, 8 * sizeof(compact)) {
		int n = 0;
		n += reference[i];
		n += reference_test(i, vec1);
		n += sHT_bit_test(vec2, i);
		n += sHT_bit_test(vec3, i);
		if ((n != 4) && (n != 0)) {
			if (printf("FAIL: bitvec (%zu)\n", i) < 0)
				return 2;
			return 1;
		}
	}
	if (printf("PASS: bitvec\n", i) < 0)
		return 2;
	return 0;
}