shttpd/sHT/index.h

// SPDX-License-Identifier: GPL-2.0 or GPL-3.0
// Copyright © 2019 Ariadne Devos
// sHT -- operate on indices

#ifndef _sHT_INDEX_H
#define _sHT_INDEX_H

/** Array indices

  This module counts from 0 to any number. It eliminates most off-by-one
  errors, ensures the index is within bounds on out-of-order architectures
  (see Spectre) and results in very clear and terse code.

  Academic paper on Spectre: https://spectreattack.com (2018).
  Practical news articles on Spectre: https://lwn.net/Kernel/Index (2018-2019).
*/

#include <sHT/nospec.h>
#include <sHT/test.h>
#include <stddef.h>

/** Check that the variable @var{i} may be used as an index.

  It must be a @var{size_t}. */
#define sHT_index_check(i) \
	_Static_assert(_Generic(*&(i), size_t: 1, default: 0), \
		"size_t is an appropriate type for indices")

/** Check that the expression @var{n} may be used as an array length.

  All unsigned integral types are fine. */
#define sHT_size_check(n) \
	_Static_assert(_Generic((n), unsigned: 1, unsigned long: 1, \
		unsigned long long: 1, default: 0), \
		"size_t is an appropriate type for lengths")

/** Let `i` iterate `{ k | i <= k < n }` in order.

  i:
    the loop counter, `read ^ write ^ set` (type size_t).
  n:
    one-past-end value to stop at, a constant integral (unsigned)

  Speculatively, stop early or do some extra iterations afterwards
  with `0 <= i < n \/ i = 0`. Increment `i` at the end of each iteration.

  Lemma: the previous is in the past: at each iteration and after loop,
  `∀k, old i <= k < current i` `->` ∃ past iteration with `i = k`
  (follows from backwards induction).

  This iterator is preferred above a manual for-loop, because comparison
  operator is always correct, the index always is within bounds, even
  on out-of-order microarchitectures and it can be annotated for formal
  analysis.

  { braces surrounding sHT_index_continue(...) S; } are required. */
#define sHT_index_continue(i, n) \
	/* TODO: on x86, `i < n` is tested twice: when `sHT_index_nospec`
	  computes the mask, and in the exit condition. Create a specialised
	  copy. Somewhat tricky because GCC doesn't support asm goto with
	  output operands. */ \
	sHT_index_check((i)); \
	sHT_size_check((n)); \
	for(; sHT_lt((i), (n)) ? ((i) = sHT_index_nospec((i), (n)), 1) : 0; (i)++)

/** Let `i` iterate `{ k | 0 <= k < n }` in order.

  First set `i` to 0, then do `sHT_index_continue(i, n)`.
  { braces surrounding sHT_index_iterate(...) S; } are required. */
#define sHT_index_iterate(i, n) \
	(i) = 0u; \
	sHT_index_continue((i), (n))

#endif