From 7c0c75e990ca5395139c148f120042048b0ce091 Mon Sep 17 00:00:00 2001 From: Mark Adler Date: Wed, 26 Dec 2018 13:50:27 -0800 Subject: [PATCH] Use atomic test and set, if available, for dynamic CRC tables. --- crc32.c | 154 ++++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 112 insertions(+), 42 deletions(-) diff --git a/crc32.c b/crc32.c index f41dc6d..ed39710 100644 --- a/crc32.c +++ b/crc32.c @@ -112,7 +112,6 @@ local z_crc_t x2nmodp OF((z_off64_t n, unsigned k)); #ifdef DYNAMIC_CRC_TABLE -local volatile int crc_table_empty = 1; local z_crc_t FAR crc_table[256]; local z_crc_t FAR x2n_table[32]; local void make_crc_table OF((void)); @@ -128,6 +127,94 @@ local void make_crc_table OF((void)); local void write_table64 OF((FILE *, const z_word_t FAR *, int)); #endif /* MAKECRCH */ +/* + Define a once() function depending on the availability of atomics. If this is + compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in + multiple threads, and if atomics are not available, then get_crc_table() must + be called to initialize the tables and must return before any threads are + allowed to compute or combine CRCs. + */ + +/* Definition of once functionality. */ +typedef struct once_s once_t; +local void once OF((once_t *, void (*)(void))); + +/* Check for the availability of atomics. */ +#if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \ + !defined(__STDC_NO_ATOMICS__) + +#include + +/* Structure for once(), which must be initialized with ONCE_INIT. */ +struct once_s { + atomic_flag begun; + atomic_int done; +}; +#define ONCE_INIT {ATOMIC_FLAG_INIT, 0} + +/* + Run the provided init() function exactly once, even if multiple threads + invoke once() at the same time. The state must be a once_t initialized with + ONCE_INIT. + */ +local void once(state, init) + once_t *state; + void (*init)(void); +{ + if (!atomic_load(&state->done)) { + if (atomic_flag_test_and_set(&state->begun)) + while (!atomic_load(&state->done)) + ; + else { + init(); + atomic_store(&state->done, 1); + } + } +} + +#else /* no atomics */ + +/* Structure for once(), which must be initialized with ONCE_INIT. */ +struct once_s { + volatile int begun; + volatile int done; +}; +#define ONCE_INIT {0, 0} + +/* Test and set. Alas, not atomic, but tries to minimize the period of + vulnerability. */ +local int test_and_set OF((int volatile *)); +local int test_and_set(flag) + int volatile *flag; +{ + int was; + + was = *flag; + *flag = 1; + return was; +} + +/* Run the provided init() function once. This is not thread-safe. */ +local void once(state, init) + once_t *state; + void (*init)(void); +{ + if (!state->done) { + if (test_and_set(&state->begun)) + while (!state->done) + ; + else { + init(); + state->done = 1; + } + } +} + +#endif + +/* State for once(). */ +local once_t made = ONCE_INIT; + /* Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1. @@ -155,45 +242,31 @@ local void make_crc_table OF((void)); local void make_crc_table() { + unsigned i, j, n; z_crc_t p; - static volatile int first = 1; /* flag to limit concurrent making */ - - /* See if another task is already doing this (not thread-safe, but better - than nothing -- significantly reduces duration of vulnerability in - case the advice about DYNAMIC_CRC_TABLE is ignored) */ - if (first) { - unsigned i, j, n; - first = 0; - - /* initialize the CRC of bytes tables */ - for (i = 0; i < 256; i++) { - p = i; - for (j = 0; j < 8; j++) - p = p & 1 ? (p >> 1) ^ POLY : p >> 1; - crc_table[i] = p; + + /* initialize the CRC of bytes tables */ + for (i = 0; i < 256; i++) { + p = i; + for (j = 0; j < 8; j++) + p = p & 1 ? (p >> 1) ^ POLY : p >> 1; + crc_table[i] = p; #ifdef W - crc_big_table[i] = byte_swap(p); + crc_big_table[i] = byte_swap(p); #endif - } + } + + /* initialize the x^2^n mod p(x) table */ + p = (z_crc_t)1 << 30; /* x^1 */ + x2n_table[0] = p; + for (n = 1; n < 32; n++) + x2n_table[n] = p = multmodp(p, p); - /* initialize the x^2^n mod p(x) table */ - p = (z_crc_t)1 << 30; /* x^1 */ - x2n_table[0] = p; - for (n = 1; n < 32; n++) - x2n_table[n] = p = multmodp(p, p); #ifdef W - /* initialize the braiding tables -- needs x2n_table[] */ - braid(crc_braid_table, crc_braid_big_table, N, W); + /* initialize the braiding tables -- needs x2n_table[] */ + braid(crc_braid_table, crc_braid_big_table, N, W); #endif - /* mark tables as complete, in case someone else is waiting */ - crc_table_empty = 0; - } - else { /* not first */ - /* wait for the other guy to finish (not efficient, but rare) */ - while (crc_table_empty) - ; - } #ifdef MAKECRCH { /* @@ -532,13 +605,13 @@ local z_word_t crc_word_big(data) #endif /* W */ /* ========================================================================= - * This function can be used by asm versions of crc32() + * This function can be used by asm versions of crc32(), and to force the + * generation of the CRC tables in a threaded application. */ const z_crc_t FAR * ZEXPORT get_crc_table() { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return (const z_crc_t FAR *)crc_table; } @@ -553,8 +626,7 @@ unsigned long ZEXPORT crc32_z(crc, buf, len) if (buf == Z_NULL) return 0; #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ /* Pre-condition the CRC */ @@ -882,8 +954,7 @@ uLong ZEXPORT crc32_combine64(crc1, crc2, len2) z_off64_t len2; { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return multmodp(x2nmodp(len2, 3), crc1) ^ crc2; } @@ -902,8 +973,7 @@ uLong ZEXPORT crc32_combine_gen64(len2) z_off64_t len2; { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return x2nmodp(len2, 3); } -- 2.44.0