bist.c

   1 /*
   2  * Copyright (C) 2024 Mikulas Patocka
   3  *
   4  * This file is part of Ajla.
   5  *
   6  * Ajla is free software: you can redistribute it and/or modify it under the
   7  * terms of the GNU General Public License as published by the Free Software
   8  * Foundation, either version 3 of the License, or (at your option) any later
   9  * version.
  10  *
  11  * Ajla is distributed in the hope that it will be useful, but WITHOUT ANY
  12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  13  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along with
  16  * Ajla. If not, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #include "ajla.h"
  20
  21 #ifndef FILE_OMIT
  22
  23 #include "mem_al.h"
  24 #include "str.h"
  25 #include "data.h"
  26 #include "refcount.h"
  27 #include "tree.h"
  28 #include "array.h"
  29 #include "ipret.h"
  30 #include "code-op.h"
  31 #include "arithm-i.h"
  32 #include "thread.h"
  33 #include "rwlock.h"
  34 #include "os.h"
  35
  36 #include <stdio.h>
  37 #include <fcntl.h>
  38
  39 static attr_always_inline void verify_size(const char *str, size_t s1, size_t s2, size_t s3)
  40 {
  41         /*debug("verify_size: %s - %d", str, (int)s1);*/
  42         if (s1 != s3 ||
  43             s2 != s3)
  44                 internal(file_line, "bad type %s: %"PRIuMAX", %"PRIuMAX", %"PRIuMAX"",
  45                         str, (uintmax_t)s1, (uintmax_t)s2, (uintmax_t)s3);
  46 }
  47
  48 static attr_noinline void bist_constants(void)
  49 {
  50 #define f(n, s, u, sz, bits)    verify_size("int_" stringify(s), sizeof(s), sizeof(u), sz);
  51         for_all_int(f, for_all_empty)
  52 #undef f
  53 #define f(n, s, u, sz, bits)    verify_size(stringify(s), sizeof(s), sizeof(u), sz);
  54         for_all_fixed(f)
  55 #undef f
  56         verify_size("ip_t", sizeof(ip_t), sizeof(ip_t), SIZEOF_IP_T);
  57 }
  58
  59
  60 #ifdef DEBUG_BIST
  61
  62
  63 static attr_noinline void bist_memory(void)
  64 {
  65         int i;
  66         char *p, *q, *r;
  67         p = mem_alloc(char *, 11);
  68         (void)strcpy(p, "1234567890");
  69         q = mem_alloc(char *, 21);
  70         (void)strcpy(q, "1234567890abcdefghij");
  71         p = mem_realloc(char *, p, 101);
  72         for (i = 0; i < 9; i++)
  73                 (void)strcat(p, "abcdefghij");
  74         r = cast_cpp(char *, mempcpy(q + 4, q, 4));
  75         if (unlikely(r != q + 8))
  76                 internal("bist_memory: mempcpy result mismatch: %p != %p", r, q + 8);
  77         if (unlikely(strcmp(q, "1234123490abcdefghij")))
  78                 internal(file_line, "bist_memory: mempcpy string mismatch: %s", q);
  79         mem_free(p);
  80         mem_free(q);
  81
  82         p = mem_alloc(char *, 0);
  83         if (unlikely(!p))
  84                 internal(file_line, "mem_alloc(0) returns NULL");
  85         p = mem_realloc(char *, p, 0);
  86         if (unlikely(!p))
  87                 internal(file_line, "mem_realloc(0) returns NULL");
  88         mem_free(p);
  89         p = mem_calloc(char *, 0);
  90         if (unlikely(!p))
  91                 internal(file_line, "mem_calloc(0) returns NULL");
  92         p = mem_realloc(char *, p, 0);
  93         if (unlikely(!p))
  94                 internal(file_line, "mem_realloc(0) returns NULL");
  95         mem_free(p);
  96         p = mem_align(char *, 0, 1);
  97         if (unlikely(!p))
  98                 internal(file_line, "mem_align(0, 1) returns NULL");
  99         mem_free_aligned(p);
 100 }
 101
 102
 103 static attr_noinline void bist_string(void)
 104 {
 105         char *str;
 106         size_t str_l;
 107         char c;
 108 #ifndef DEBUG_TRACK_FILE_LINE
 109         str = position_string(bist_string);
 110 #endif
 111         str_init(&str, &str_l);
 112         str_add_string(&str, &str_l, "");
 113         for (c = 0; c < 127; c++)
 114                 str_add_bytes(&str, &str_l, &c, 1);
 115         for (c = 0; c < 127; c++)
 116                 if (unlikely(str[(int)c] != c))
 117                         internal(file_line, "bist_string: str[%d] == %d", c, str[(int)c]);
 118         str_finish(&str, &str_l);
 119         if (unlikely(str[127] != 0))
 120                 internal(file_line, "bist_string: bad string end: %d", str[127]);
 121         mem_free(str);
 122 }
 123
 124 static attr_noinline void bist_memarray(void)
 125 {
 126         int *array;
 127         size_t array_l;
 128         int i = 3;
 129         array_init(int, &array, &array_l);
 130         array_add_multiple(int, &array, &array_l, &i, 1);
 131         for (i = 0; i < 100; i++)
 132                 array_add(int, &array, &array_l, i * 2);
 133         for (i = 0; i < 100; i++)
 134                 if (unlikely(array[i + 1] != i * 2))
 135                         internal(file_line, "bist_memarray: array[%d] == %d", i, array[i]);
 136         mem_free(array);
 137 }
 138
 139
 140 static attr_noinline void bist_pointer(void)
 141 {
 142         pointer_t p;
 143         struct thunk *th;
 144         struct data *dat, *res_d;
 145         th = thunk_alloc_exception_error(error_ajla(EC_SYNC, AJLA_ERROR_NOT_SUPPORTED), NULL, NULL, NULL pass_file_line);
 146         dat = data_alloc(flat, NULL);
 147         p = pointer_thunk(th);
 148         if (unlikely(pointer_get_thunk(p) != th))
 149                 internal(file_line, "bist_pointer: bad thunk pointer %p != %p", (const void *)pointer_get_thunk(p), (const void *)th);
 150         p = pointer_data(dat);
 151         if (unlikely(pointer_get_data(p) != dat))
 152 bad_data:
 153                 internal(file_line, "bist_pointer: bad data pointer %p != %p", (const void *)pointer_get_data(p), (const void *)dat);
 154         pointer_follow(&p, false, res_d, PF_NOEVAL, NULL, NULL,
 155                 internal(file_line, "bist_pointer: thunk, execution control %p", (const void *)ex_),
 156                 internal(file_line, "bist_pointer: exception: %p", (const void *)thunk_)
 157         );
 158         if (unlikely(res_d != dat))
 159                 goto bad_data;
 160         thunk_free(th);
 161         data_free_r1(dat);
 162 }
 163
 164
 165 #define bist_refcount_is_one            name(bist_refcount_is_one)
 166 attr_noinline bool bist_refcount_is_one(refcount_t *ref);
 167 attr_noinline bool bist_refcount_is_one(refcount_t *ref)
 168 {
 169         return refcount_is_one(ref);
 170 }
 171
 172 #define bist_refcount_inc               name(bist_refcount_inc)
 173 attr_noinline void bist_refcount_inc(refcount_t *ref);
 174 attr_noinline void bist_refcount_inc(refcount_t *ref)
 175 {
 176         refcount_inc(ref);
 177 }
 178
 179 #define bist_refcount_dec_false         name(bist_refcount_dec_false)
 180 attr_noinline void bist_refcount_dec_false(refcount_t *ref, const char *position);
 181 attr_noinline void bist_refcount_dec_false(refcount_t *ref, const char *position)
 182 {
 183         if (unlikely(refcount_dec(ref)))
 184                 internal(position, "bist_refcount_dec_false: refcount_dec returned true");
 185 }
 186
 187 #define bist_refcount_dec_true          name(bist_refcount_dec_true)
 188 attr_noinline void bist_refcount_dec_true(refcount_t *ref, const char *position);
 189 attr_noinline void bist_refcount_dec_true(refcount_t *ref, const char *position)
 190 {
 191         if (unlikely(!refcount_dec(ref)))
 192                 internal(position, "bist_refcount_dec_true: refcount_dec returned false");
 193 }
 194
 195 #define bist_refcount_xchgcmp_false     name(bist_refcount_xchgcmp_false)
 196 attr_noinline void bist_refcount_xchgcmp_false(refcount_t *ref, refcount_int_t val, refcount_int_t cmp, const char *position);
 197 attr_noinline void bist_refcount_xchgcmp_false(refcount_t *ref, refcount_int_t val, refcount_int_t cmp, const char *position)
 198 {
 199         if (unlikely(refcount_xchgcmp(ref, val, cmp)))
 200                 internal(position, "bist_refcount_xchgcmp_false: refcount_xchgcmp returned true");
 201 }
 202
 203 #define bist_refcount_xchgcmp_true      name(bist_refcount_xchgcmp_true)
 204 attr_noinline void bist_refcount_xchgcmp_true(refcount_t *ref, refcount_int_t val, refcount_int_t cmp, const char *position);
 205 attr_noinline void bist_refcount_xchgcmp_true(refcount_t *ref, refcount_int_t val, refcount_int_t cmp, const char *position)
 206 {
 207         if (unlikely(!refcount_xchgcmp(ref, val, cmp)))
 208                 internal(position, "bist_refcount_xchgcmp_true: refcount_xchgcmp returned false");
 209 }
 210
 211 static attr_noinline void bist_refcount(void)
 212 {
 213         refcount_t ref;
 214
 215 #ifndef REFCOUNT_TAG
 216         refcount_init(&ref);
 217 #else
 218         refcount_init_tag(&ref, 5);
 219 #endif
 220         bist_refcount_inc(&ref);
 221         bist_refcount_inc(&ref);
 222 #ifdef REFCOUNT_TAG
 223         if (unlikely(refcount_tag_get(&ref) != 5)) internal(file_line, "bist_refcount: refcount tag is not 5");
 224 #endif
 225         if (unlikely(refcount_get_nonatomic(&ref) != 3) || unlikely(bist_refcount_is_one(&ref))) internal(file_line, "bist_refcount: refcount is not 3");
 226         bist_refcount_dec_false(&ref, file_line);
 227         if (unlikely(refcount_get_nonatomic(&ref) != 2) || unlikely(bist_refcount_is_one(&ref))) internal(file_line, "bist_refcount: refcount is not 2");
 228         bist_refcount_dec_false(&ref, file_line);
 229         if (unlikely(refcount_get_nonatomic(&ref) != 1) || unlikely(!bist_refcount_is_one(&ref))) internal(file_line, "bist_refcount: refcount is not 1");
 230         bist_refcount_dec_true(&ref, file_line);
 231
 232         refcount_init_val(&ref, 4);
 233         refcount_inc_nonatomic(&ref);
 234         if (unlikely(refcount_get_nonatomic(&ref) != 5) || unlikely(refcount_is_one_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount is not 5");
 235         bist_refcount_xchgcmp_true(&ref, 3, 5, file_line);
 236         if (unlikely(refcount_get_nonatomic(&ref) != 3) || unlikely(refcount_is_one_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount is not 3");
 237         bist_refcount_xchgcmp_false(&ref, 2, 1, file_line);
 238         if (unlikely(refcount_get_nonatomic(&ref) != 2) || unlikely(refcount_is_one_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount is not 2");
 239         if (unlikely(refcount_dec_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount should not be zero");
 240         if (unlikely(refcount_get_nonatomic(&ref) != 1) || unlikely(!refcount_is_one_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount is not 1");
 241         if (unlikely(!refcount_dec_nonatomic(&ref))) internal(file_line, "bist_refcount: nonatomic refcount should be zero");
 242 }
 243
 244
 245 static attr_noinline void bist_arithm(void)
 246 {
 247 #define f(n, s, u, sz, bits)                                            \
 248         {                                                               \
 249                 s op1 = 10;                                             \
 250                 s op2 = 20;                                             \
 251                 s res;                                                  \
 252                 s * volatile resp = &res; /* avoid failure with icc */  \
 253                 *resp = 25;                                             \
 254                 res = 25;                                               \
 255                 if (!cat(INT_binary_add_,s)(&op1, &op2, &res))          \
 256                         internal(file_line, "bist_arithm: %s failed", stringify(cat(INT_binary_add_,s)));\
 257                 if (res != 30)                                          \
 258                         internal(file_line, "bist_arithm: %s: bad result %s", stringify(cat(INT_binary_add_,s)), str_from_signed(res, 16));\
 259         }
 260         for_all_int(f, for_all_empty)
 261 #undef f
 262 }
 263
 264 #define bist_cat_(a, b) a##b
 265 #define bist_cat(a, b)  bist_cat_(a, b)
 266 #define bist_popcnt(type, utype)                                        \
 267 {                                                                       \
 268         type val, res1, res2 = 0;       /* avoid warning */             \
 269         val = (type)0x12345678UL;                                       \
 270         if (sizeof(type) >= sizeof(unsigned long)) {                    \
 271                 val = (type)((utype)val | ((utype)val << 31));          \
 272                 val = (type)((utype)val | ((utype)val << 31 << 31));    \
 273         }                                                               \
 274         if (unlikely(!bist_cat(INT_unary_popcnt_,type)(&val, &res1)))   \
 275                 internal(file_line, "bist_popcnt(%s) INT_unary_popcnt failed", stringify(type));\
 276         if ((cpu_feature_flags & FIXED_POPCNT_ALT1_FEATURES) == FIXED_POPCNT_ALT1_FEATURES) {\
 277                 if (unlikely(!bist_cat(INT_unary_popcnt_alt1_,type)(&val, &res2)))\
 278                         internal(file_line, "bist_popcnt(%s) INT_unary_popcnt_alt1 failed", stringify(type));\
 279         } else {                                                        \
 280                 res2 = 0;                                               \
 281                 while (val)                                             \
 282                         val &= val - 1, res2++;                         \
 283         }                                                               \
 284         if (unlikely(res1 != res2))                                     \
 285                 internal(file_line, "bist_popcnt(%s) mismatch: %"PRIdMAX" != %"PRIdMAX"", stringify(type), (intmax_t)res, (intmax_t)res1);\
 286 }
 287
 288 #if defined(INT_POPCNT_ALT1_TYPES) && INT_POPCNT_ALT1_TYPES & 1
 289 #define bist_popcnt_int8_t      bist_popcnt(int8_t, uint8_t)
 290 #else
 291 #define bist_popcnt_int8_t
 292 #endif
 293 #if defined(INT_POPCNT_ALT1_TYPES) && INT_POPCNT_ALT1_TYPES & 2
 294 #define bist_popcnt_int16_t     bist_popcnt(int16_t, uint16_t)
 295 #else
 296 #define bist_popcnt_int16_t
 297 #endif
 298 #if defined(INT_POPCNT_ALT1_TYPES) && INT_POPCNT_ALT1_TYPES & 4
 299 #define bist_popcnt_int32_t     bist_popcnt(int32_t, uint32_t)
 300 #else
 301 #define bist_popcnt_int32_t
 302 #endif
 303 #if defined(INT_POPCNT_ALT1_TYPES) && INT_POPCNT_ALT1_TYPES & 8
 304 #define bist_popcnt_int64_t     bist_popcnt(int64_t, uint64_t)
 305 #else
 306 #define bist_popcnt_int64_t
 307 #endif
 308 #if defined(INT_POPCNT_ALT1_TYPES) && INT_POPCNT_ALT1_TYPES & 16
 309 #define bist_popcnt_int128_t    bist_popcnt(int128_t, uint128_t)
 310 #else
 311 #define bist_popcnt_int128_t
 312 #endif
 313
 314 #define generate_bist_arithm(n, type, utype, sz, bits)                  \
 315 static attr_noinline void cat(bist_binary_,type)(                       \
 316         bool (*fn)(const type *, const type *, type *),                 \
 317         const char *fn_name,                                            \
 318         type op1, type op2, bool succeed, type result)                  \
 319 {                                                                       \
 320         type res;                                                       \
 321         type * volatile resp = &res; /* avoid failure with icc */       \
 322         *resp = -1;                                                     \
 323         res = -1;                                                       \
 324         if (unlikely(fn(&op1, &op2, &res) != succeed))                  \
 325                 internal(file_line, "bist_binary_%s: %s(%s, %s) %s",    \
 326                         stringify(type), fn_name,                       \
 327                         str_from_signed(op1, 16), str_from_signed(op2, 16),\
 328                         succeed ? "failed" : "succeeded");              \
 329         if (!succeed && unlikely(res != -1))                            \
 330                 internal(file_line, "bist_binary_%s: %s(%s, %s) modified result: %s",\
 331                         stringify(type), fn_name,                       \
 332                         str_from_signed(op1, 16), str_from_signed(op2, 16), str_from_signed(res, 16));\
 333         if (succeed && unlikely(res != result))                         \
 334                 internal(file_line, "bist_binary_%s: %s(%s, %s) returned wrong result: %s != %s",\
 335                         stringify(type), fn_name,                       \
 336                         str_from_signed(op1, 16), str_from_signed(op2, 16), str_from_signed(res, 16),\
 337                         str_from_signed(result, 16));                   \
 338 }                                                                       \
 339                                                                         \
 340 static attr_noinline void cat(bist_unary_,type)(                        \
 341         bool (*fn)(const type *, type *),                               \
 342         const char *fn_name,                                            \
 343         type op1, bool succeed, type result)                            \
 344 {                                                                       \
 345         type res;                                                       \
 346         type * volatile resp = &res; /* avoid failure with icc */       \
 347         *resp = -1;                                                     \
 348         res = -1;                                                       \
 349         if (unlikely(fn(&op1, &res) != succeed))                        \
 350                 internal(file_line, "bist_binary_%s: %s(%s) %s",        \
 351                         stringify(type), fn_name,                       \
 352                         str_from_signed(op1, 16),                       \
 353                         succeed ? "failed" : "succeeded");              \
 354         if (!succeed && unlikely(res != -1))                            \
 355                 internal(file_line, "bist_binary_%s: %s(%s) modified result: %s",\
 356                         stringify(type), fn_name,                       \
 357                         str_from_signed(op1, 16), str_from_signed(res, 16));\
 358         if (succeed && unlikely(res != result))                         \
 359                 internal(file_line, "bist_binary_%s: %s(%s) returned wrong result: %s != %s",\
 360                         stringify(type), fn_name,                       \
 361                         str_from_signed(op1, 16), str_from_signed(res, 16),\
 362                         str_from_signed(result, 16));                   \
 363 }                                                                       \
 364                                                                         \
 365 static attr_noinline void cat(bist_arithm_,type)(void)                  \
 366 {                                                                       \
 367         type op1 = 10;                                                  \
 368         type op2 = 20;                                                  \
 369         type res;                                                       \
 370         type * volatile resp = &res; /* avoid failure with icc */       \
 371         *resp = 25;                                                     \
 372         res = 25;                                                       \
 373         if (!cat(INT_binary_add_,type)(&op1, &op2, &res))               \
 374                 internal(file_line, "bist_arithm_%s: %s failed",        \
 375                         stringify(type),                                \
 376                         stringify(cat(add_,type)));                     \
 377         if (res != 30)                                                  \
 378                 internal(file_line, "bist_arithm_%s: %s: bad result %"PRIdMAX,\
 379                         stringify(type),                                \
 380                         stringify(cat(add_,type)), (intmax_t)res);      \
 381                                                                         \
 382         cat(bist_binary_,type)(cat(INT_binary_add_,type), stringify(cat(INT_binary_add_,type)), 10, 20, true, 30);\
 383         cat(bist_binary_,type)(cat(INT_binary_add_,type), stringify(cat(INT_binary_add_,type)), sign_bit(utype) / 2, sign_bit(utype) / 2, false, 0);\
 384         cat(bist_binary_,type)(cat(INT_binary_add_,type), stringify(cat(INT_binary_add_,type)), sign_bit(utype) / 2, sign_bit(utype) / 2 - 1, true, sign_bit(utype) - 1);\
 385         cat(bist_binary_,type)(cat(INT_binary_add_,type), stringify(cat(INT_binary_add_,type)), -(sign_bit(utype) / 2), -(sign_bit(utype) / 2) - 1, false, 0);\
 386         cat(bist_binary_,type)(cat(INT_binary_add_,type), stringify(cat(INT_binary_add_,type)), -(sign_bit(utype) / 2), -(sign_bit(utype) / 2), true, sign_bit(utype));\
 387                                                                         \
 388         cat(bist_binary_,type)(cat(INT_binary_subtract_,type), stringify(cat(INT_binary_subtract_,type)), 20, 30, true, -10);\
 389         cat(bist_binary_,type)(cat(INT_binary_subtract_,type), stringify(cat(INT_binary_subtract_,type)), sign_bit(utype) / 2, -(sign_bit(utype) / 2), false, 0);\
 390         cat(bist_binary_,type)(cat(INT_binary_subtract_,type), stringify(cat(INT_binary_subtract_,type)), sign_bit(utype) / 2, -(sign_bit(utype) / 2 - 1), true, sign_bit(utype) - 1);\
 391         cat(bist_binary_,type)(cat(INT_binary_subtract_,type), stringify(cat(INT_binary_subtract_,type)), -(sign_bit(utype) / 2), sign_bit(utype) / 2 + 1, false, 0);\
 392         cat(bist_binary_,type)(cat(INT_binary_subtract_,type), stringify(cat(INT_binary_subtract_,type)), -(sign_bit(utype) / 2), sign_bit(utype) / 2, true, sign_bit(utype));\
 393                                                                         \
 394         cat(bist_unary_,type)(cat(INT_unary_not_,type), stringify(cat(INT_unary_not_,type)), 0, true, -1);\
 395         cat(bist_unary_,type)(cat(INT_unary_not_,type), stringify(cat(INT_unary_not_,type)), 10, true, -11);\
 396         cat(bist_unary_,type)(cat(INT_unary_not_,type), stringify(cat(INT_unary_not_,type)), sign_bit(utype), true, sign_bit(utype) - 1);\
 397         cat(bist_unary_,type)(cat(INT_unary_not_,type), stringify(cat(INT_unary_not_,type)), sign_bit(utype) - 1, true, sign_bit(utype));\
 398         cat(bist_unary_,type)(cat(INT_unary_neg_,type), stringify(cat(INT_unary_neg_,type)), 0, true, 0);\
 399         cat(bist_unary_,type)(cat(INT_unary_neg_,type), stringify(cat(INT_unary_neg_,type)), 10, true, -10);\
 400         cat(bist_unary_,type)(cat(INT_unary_neg_,type), stringify(cat(INT_unary_neg_,type)), sign_bit(utype), false, 0);\
 401         cat(bist_unary_,type)(cat(INT_unary_neg_,type), stringify(cat(INT_unary_neg_,type)), sign_bit(utype) - 1, true, sign_bit(type) + 1);\
 402                                                                         \
 403         cat(bist_binary_,type)(cat(INT_binary_multiply_,type), stringify(cat(INT_binary_multiply_,type)), 10, 11, true, 110);\
 404         cat(bist_binary_,type)(cat(INT_binary_multiply_,type), stringify(cat(INT_binary_multiply_,type)), (type)1 << (sizeof(type) * 4 - 1), (type)1 << (sizeof(type) * 4), false, 0);\
 405         cat(bist_binary_,type)(cat(INT_binary_multiply_,type), stringify(cat(INT_binary_multiply_,type)), ((type)1 << (sizeof(type) * 4 - 1)) - 1, (type)1 << (sizeof(type) * 4), true, (((type)1 << (sizeof(type) * 4 - 1)) - 1) * ((type)1 << (sizeof(type) * 4)));\
 406         cat(bist_binary_,type)(cat(INT_binary_multiply_,type), stringify(cat(INT_binary_multiply_,type)), -((type)1 << (sizeof(type) * 4 - 1)), (type)1 << (sizeof(type) * 4), true, sign_bit(utype));\
 407         cat(bist_binary_,type)(cat(INT_binary_multiply_,type), stringify(cat(INT_binary_multiply_,type)), -((type)1 << (sizeof(type) * 4 - 1)), ((type)1 << (sizeof(type) * 4)) + 1, false, 0);\
 408                                                                         \
 409         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), 10, 0, false, 0);\
 410         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), 121, 11, true, 11);\
 411         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), 119, 11, true, 10);\
 412         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), -119, 11, true, -10);\
 413         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), 119, -11, true, -10);\
 414         cat(bist_binary_,type)(cat(INT_binary_divide_,type), stringify(cat(INT_binary_divide_,type)), -119, -11, true, 10);\
 415                                                                         \
 416         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), 10, 0, false, 0);\
 417         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), 121, 11, true, 0);\
 418         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), 119, 11, true, 9);\
 419         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), -119, 11, true, -9);\
 420         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), 119, -11, true, 9);\
 421         cat(bist_binary_,type)(cat(INT_binary_modulo_,type), stringify(cat(INT_binary_modulo_,type)), -119, -11, true, -9);\
 422                                                                         \
 423         cat(bist_popcnt_,type);                                         \
 424 }
 425 for_all_int(generate_bist_arithm, for_all_empty)
 426 #undef generate_bist_arithm
 427
 428
 429 #ifdef HAVE___FP16
 430 #define fp16    __fp16
 431 #else
 432 #define fp16    _Float16
 433 #endif
 434
 435 static attr_noinline void bist_conv_float_half(float f1, float f3, bool eq)
 436 {
 437         uint16_t n;
 438         float f2;
 439 #ifdef TEST_HALF_FLOAT_CONVERSION
 440         union {
 441                 uint16_t i;
 442                 fp16 fp;
 443         } u;
 444 #endif
 445         /*debug("f2h: %.9e", f1);*/
 446         n = float_to_half(f1);
 447 #ifdef TEST_HALF_FLOAT_CONVERSION
 448         u.fp = (fp16)f1;
 449         if (!((n & 0x7fff) > 0x7c00 && (u.i & 0x7fff) > 0x7c00))
 450                 if (unlikely(n != u.i))
 451                         internal(file_line, "bist_conv_float_half: test failed for %.9e: %u != %u", f1, (unsigned)n, (unsigned)u.i);
 452 #endif
 453         /*debug("h2f: %04x", n);*/
 454         f2 = half_to_float(n);
 455         /*debug("done: %.9e", f2);*/
 456         if (eq && memcmp(&f2, &f3, sizeof(float)))
 457                 internal(file_line, "bist_conv_float_half: test failed for %.9e -> %04x -> %.9e (should be %.9e)", f1, (unsigned)n, f2, f3);
 458 }
 459
 460 static attr_noinline void bist_conv(unsigned attr_unused flags)
 461 {
 462         uint32_t i;
 463         for (i = 0; i < 65536; i++) {
 464                 float f1;
 465                 uint16_t n;
 466 #ifdef TEST_HALF_FLOAT_CONVERSION
 467                 float f2;
 468                 union {
 469                         uint16_t i;
 470                         fp16 fp;
 471                 } u;
 472                 u.i = i;
 473 #endif
 474                 f1 = half_to_float(i);
 475 #ifdef TEST_HALF_FLOAT_CONVERSION
 476                 f2 = (float)u.fp;
 477                 if (unlikely(isnan_real32_t(f1) != isnan_real32_t(f2)))
 478                         internal(file_line, "bist_conv: nan test failed for %lx: %.9e != %.9e", (unsigned long)i, f1, f2);
 479                 if (likely(!isnan_real32_t(f1)) && memcmp(&f1, &f2, sizeof(float)))
 480                         internal(file_line, "bist_conv: test failed for %lx: %.9e != %.9e", (unsigned long)i, f1, f2);
 481 #endif
 482                 n = float_to_half(f1);
 483                 if (!((n & 0x7fff) > 0x7c00 && (i & 0x7fff) > 0x7c00))
 484                         if (unlikely(n != i))
 485                                 internal(file_line, "bist_conv: test failed for %lx -> %.9e -> %04x", (unsigned long)i, f1, (unsigned)n);
 486
 487         }
 488         for (i = 0; i < 131072; i++) {
 489                 uint32_t ri = i;
 490                 if (i >= 2048) {
 491                         uint32_t l, tr;
 492                         uint32_t ii;
 493                         for (ii = i, l = -1; ii; ii >>= 1) l++;
 494                         l -= 11;
 495                         tr = ri & ((2UL << l) - 1);
 496                         ri &= -(2UL << l);
 497                         if (tr >= (1UL << l) + !(ri & (2UL << l)))
 498                                 ri += 2UL << l;
 499                 }
 500 #ifdef HUGE_VAL
 501                 bist_conv_float_half((float)i, ri >= 0x10000 ? HUGE_VAL : (float)ri, true);
 502 #endif
 503                 bist_conv_float_half(-(float)(i * 2) + 1, -(float)(i * 2) + 1, i < 1024);
 504                 bist_conv_float_half((float)i / 0x400, (float)i / 0x400, i <= 2048);
 505                 bist_conv_float_half((float)i / 0x4000000, (float)i / 0x4000000, !(i & 0x003f));
 506                 bist_conv_float_half((float)(1. / (i + 1)), (float)(1. / (i + 1)), is_power_of_2(i + 1));
 507         }
 508         bist_conv_float_half(-0., -0., true);
 509 #ifdef HUGE_VAL
 510         bist_conv_float_half(HUGE_VAL, HUGE_VAL, true);
 511         bist_conv_float_half(-HUGE_VAL, -HUGE_VAL, true);
 512 #endif
 513 #ifdef NAN
 514         bist_conv_float_half(NAN, NAN, false);
 515 #endif
 516 }
 517
 518 #undef fp16
 519
 520
 521 #define left            children[0]
 522 #define right           children[1]
 523 #define rb_is_black(n)  ((n)->color == RB_BLACK)
 524
 525 struct rb_test {
 526         int value;
 527         struct tree_entry entry;
 528 };
 529
 530 #define TREE_SIZE       1024
 531 #define TREE_STEPS      10240
 532
 533 shared_var int rbtree_content[TREE_SIZE];
 534 shared_var int rbtree_content_n;
 535 shared_var struct tree rbtree;
 536 shared_var int rbtree_node_count;
 537
 538 shared_var int rbtree_verify_node_count;
 539
 540 static int bist_rbtree_verify_node(struct tree_entry *e, int from, int to)
 541 {
 542         struct rb_test *t;
 543         int depth_left, depth_right, depth_me;
 544         if (!e)
 545                 return 1;
 546         rbtree_verify_node_count++;
 547         t = get_struct(e, struct rb_test, entry);
 548         tree_verify_node(&t->entry);
 549         if (unlikely(t->value < from) || unlikely(t->value > to))
 550                 internal(file_line, "bist_rbtree_verify_node: value %d out of range %d,%d", t->value, from, to);
 551         if (!rb_is_black(e)) {
 552                 if (e->left && unlikely(!rb_is_black(e->left)))
 553                         internal(file_line, "bist_rbtree_verify_node: left node is not black");
 554                 if (e->right && unlikely(!rb_is_black(e->right)))
 555                         internal(file_line, "bist_rbtree_verify_node: right node is not black");
 556                 depth_me = 0;
 557         } else {
 558                 depth_me = 1;
 559         }
 560         depth_left = bist_rbtree_verify_node(e->left, from, (unsigned)t->value - 1);
 561         depth_right = bist_rbtree_verify_node(e->right, (unsigned)t->value + 1, to);
 562         if (unlikely(depth_left != depth_right))
 563                 internal(file_line, "bist_rbtree_verify_node: imbalanced node: %d != %d", depth_left, depth_right);
 564         return depth_left + depth_me;
 565 }
 566
 567 static void bist_rbtree_verify(struct tree *root)
 568 {
 569         rbtree_verify_node_count = 0;
 570         (void)bist_rbtree_verify_node(root->root, 0, signed_maximum(int));
 571         if (unlikely(rbtree_verify_node_count != rbtree_node_count))
 572                 internal(file_line, "bist_rbtree_verify: node count mismatch: %d != %d", rbtree_verify_node_count, rbtree_node_count);
 573 }
 574
 575 static int bist_rb_test(const struct tree_entry *e, uintptr_t i)
 576 {
 577         const struct rb_test *t = get_struct(e, struct rb_test, entry);
 578         if (t->value == (int)i) return 0;
 579         if (t->value > (int)i) return 1;
 580         return -1;
 581 }
 582
 583 static bool bist_rbtree_insert(int n)
 584 {
 585         struct tree_entry *found;
 586         struct rb_test *t;
 587         struct tree_insert_position ins;
 588         found = tree_find_for_insert(&rbtree, bist_rb_test, n, &ins);
 589         if (found)
 590                 return false;
 591         t = mem_alloc(struct rb_test *, sizeof(struct rb_test));
 592         /*debug("inserting %p:%d", t, n);*/
 593         t->value = n;
 594         tree_insert_after_find(&t->entry, &ins);
 595         rbtree_node_count++;
 596         bist_rbtree_verify(&rbtree);
 597         found = tree_find(&rbtree, bist_rb_test, n);
 598         if (found != &t->entry)
 599                 internal(file_line, "bist_rbtree_insert: number %d not found in tree: %p, %p", n, found, &t->entry);
 600         found = tree_find_next(&rbtree, bist_rb_test, n - 1);
 601         if (found != &t->entry)
 602                 internal(file_line, "bist_rbtree_insert: number %d not found in tree: %p, %p", n, found, &t->entry);
 603         return true;
 604 }
 605
 606 static void bist_rbtree_insert_into_content(int n)
 607 {
 608         rbtree_content[rbtree_content_n++] = n;
 609         (void)bist_rbtree_insert(n);
 610 }
 611
 612 static void bist_rbtree_delete(int n)
 613 {
 614         struct tree_entry *f;
 615         struct rb_test *t;
 616         f = tree_find(&rbtree, bist_rb_test, n);
 617         if (unlikely(!f))
 618                 internal(file_line, "bist_rbtree_delete: item %d not found", n);
 619         t = get_struct(f, struct rb_test, entry);
 620         tree_delete(&t->entry);
 621         rbtree_node_count--;
 622         bist_rbtree_verify(&rbtree);
 623         mem_free(t);
 624 }
 625
 626 static int rbtree_content_compare(const void *p1, const void *p2)
 627 {
 628         int i1 = *(int *)p1;
 629         int i2 = *(int *)p2;
 630         if (i1 < i2) return -1;
 631         if (likely(i1 > i2)) return 1;
 632         return 0;
 633 }
 634
 635 static attr_noinline void bist_rbtree(unsigned attr_unused flags)
 636 {
 637         int n, m, e;
 638         rbtree_content_n = 0;
 639         tree_init(&rbtree);
 640         rbtree_node_count = 0;
 641         for (n = 0; n < TREE_SIZE; n += 4) {
 642                 bist_rbtree_insert_into_content(n);
 643                 bist_rbtree_insert_into_content(rand());
 644                 bist_rbtree_insert_into_content(TREE_SIZE * 3 / 2 - n);
 645                 bist_rbtree_insert_into_content(rand() & 0xfff);
 646         }
 647         qsort(rbtree_content, rbtree_content_n, sizeof(rbtree_content[0]), rbtree_content_compare);
 648         for (e = 0, m = 0, n = 0; n < rbtree_content_n; n++) {
 649                 if (n + 1 < rbtree_content_n && rbtree_content[n] == rbtree_content[n + 1]) {
 650                         e++;
 651                         continue;
 652                 }
 653                 rbtree_content[m++] = rbtree_content[n];
 654                 /*printf("entry[%d]: %d\n", m - 1, rbtree_content[m - 1]);*/
 655         }
 656         rbtree_content_n = m;
 657         /*printf("used entries = %d\n", m);*/
 658         if (unlikely(rbtree_content_n != rbtree_node_count))
 659                 internal(file_line, "bist_rbtree: bad node count: %d != %d", rbtree_content_n, rbtree_node_count);
 660         while (1) {
 661                 int x;
 662                 struct tree_entry *q;
 663                 if (tree_is_empty(&rbtree)) break;
 664                 bist_rbtree_delete(get_struct(tree_first(&rbtree), struct rb_test, entry)->value);
 665                 if (tree_is_empty(&rbtree)) break;
 666                 bist_rbtree_delete(get_struct(tree_any(&rbtree), struct rb_test, entry)->value);
 667                 if (tree_is_empty(&rbtree)) break;
 668                 x = rand() % rbtree_content_n;
 669                 q = tree_find(&rbtree, bist_rb_test, rbtree_content[x]);
 670                 if (q) {
 671                         bist_rbtree_delete(get_struct(q, struct rb_test, entry)->value);
 672                 }
 673         }
 674
 675         if (unlikely(rbtree_node_count))
 676                 internal(file_line, "bist_rbtree: %d nodes leaked in test 1", rbtree_node_count);
 677
 678         /* 2nd test */
 679         tree_init(&rbtree);
 680         (void)memset(&rbtree_content, 0, sizeof rbtree_content);
 681         for (n = 0; n < TREE_STEPS; n++) {
 682                 int x = rand() % TREE_SIZE;
 683                 if (rbtree_content[x]) {
 684                         bist_rbtree_delete(x);
 685                         rbtree_content[x] = 0;
 686                 } else {
 687                         if (!bist_rbtree_insert(x))
 688                                 internal(file_line, "bist_rbtree: %d already present", x);
 689                         rbtree_content[x] = 1;
 690                 }
 691         }
 692
 693         while (!tree_is_empty(&rbtree)) {
 694                 int x = rand() % TREE_SIZE;
 695                 if (rbtree_content[x]) {
 696                         bist_rbtree_delete(x);
 697                         rbtree_content[x] = 0;
 698                 }
 699         }
 700
 701         if (unlikely(rbtree_node_count))
 702                 internal(file_line, "bist_rbtree: %d nodes leaked in test 2", rbtree_node_count);
 703 }
 704
 705
 706 #if INT_MASK & (1 << 2)
 707 #define int_bist_t      int32_t
 708 #define int_bist_type   type_get_fixed(2, false)
 709 #elif INT_MASK & (1 << 3)
 710 #define int_bist_t      int64_t
 711 #define int_bist_type   type_get_fixed(3, false)
 712 #elif INT_MASK & (1 << 4)
 713 #define int_bist_t      int128_t
 714 #define int_bist_type   type_get_fixed(4, false)
 715 #elif INT_MASK & (1 << 1)
 716 #define int_bist_t      int16_t
 717 #define int_bist_type   type_get_fixed(1, false)
 718 #else
 719 #define int_bist_t      int8_t
 720 #define int_bist_type   type_get_fixed(0, false)
 721 #endif
 722
 723 #define N_ARRAY_ENTRIES         minimum(192, signed_maximum(int_default_t))
 724 #define N_ARRAY_OPERATIONS      2048
 725 #define FLAT_ARRAY_LENGTH       3
 726 #define SAME_ARRAY_LENGTH       127
 727 #define ARRAY_STRIDE            3
 728 #define SAME_MAGIC              -123
 729
 730 #if 0
 731 static void bist_dump_array(const char *name, struct data *a)
 732 {
 733         if (name)
 734                 debug("%s", name);
 735         if (refcount_is_invalid(&a->refcount))
 736                 internal(file_line, "bist_light_array_check: invalid refcount");
 737         switch (da_tag(a)) {
 738                 case DATA_TAG_array_flat:
 739                         debug("           FLAT");
 740                         break;
 741                 case DATA_TAG_array_slice:
 742                         debug("           SLICE");
 743                         break;
 744                 case DATA_TAG_array_pointers:
 745                         debug("           POINTERS");
 746                         break;
 747                 case DATA_TAG_array_same:
 748                         debug("           SAME");
 749                         break;
 750                 case DATA_TAG_array_btree: {
 751                         btree_entries_t bt_pos;
 752                         debug("%.*sBTREE(%d)", 10 - da(a,array_btree)->depth, "          ", (int)da(a,array_btree)->n_used_btree_entries);
 753                         for (bt_pos = 0; bt_pos < da(a,array_btree)->n_used_btree_entries; bt_pos++) {
 754                                 struct btree_level *levels = da(a,array_btree)->btree;
 755                                 bist_dump_array(NULL, pointer_get_data(levels[bt_pos].node));
 756                         }
 757                         break;
 758                 }
 759
 760                 default:
 761                         internal(file_line, "bist_dump_array: invalid array tag %u", da_tag(a));
 762         }
 763 }
 764 #else
 765 #define bist_dump_array(name, a)        do { } while (0)
 766 #endif
 767
 768 struct bist_array_state {
 769         int8_t array_flag[N_ARRAY_ENTRIES];
 770         pointer_t array_ptr;
 771         int_bist_t array_n_same;
 772         struct data *array_same_pointer;
 773 };
 774
 775 static void bist_array_verify_node(struct bist_array_state *st, struct data *d, const array_index_t *size, int_bist_t abs_idx)
 776 {
 777         int_default_t i;
 778         btree_entries_t bi;
 779         int_bist_t n;
 780         struct data *s;
 781         switch (da_tag(d)) {
 782                 case DATA_TAG_array_flat:
 783                         if (unlikely(da(d,array_flat)->n_used_entries > da(d,array_flat)->n_allocated_entries))
 784                                 internal(file_line, "bist_array_verify_node: flat entries overflow");
 785
 786                         if (size && unlikely(index_to_int(*size) != da(d,array_flat)->n_used_entries))
 787                                 internal(file_line, "bist_array_verify_node: flat invalid size %"PRIdMAX" != %"PRIdMAX"", (intmax_t)index_to_int(*size), (intmax_t)da(d,array_flat)->n_used_entries);
 788
 789                         for (i = 0; i < da(d,array_flat)->n_used_entries; i++) {
 790                                 n = cast_ptr(int_bist_t *, da_array_flat(d))[i];
 791                                 if (unlikely(n != abs_idx + i))
 792                                         internal(file_line, "bist_array_verify_node: invalid flat value %"PRIdMAX" + %"PRIdMAX" != %"PRIdMAX"", (intmax_t)abs_idx, (intmax_t)i, (intmax_t)n);
 793                         }
 794
 795                         break;
 796                 case DATA_TAG_array_slice:
 797                         if (size && unlikely(index_to_int(*size) != da(d,array_slice)->n_entries))
 798                                 internal(file_line, "bist_array_verify_node: slice invalid size %"PRIdMAX" != %"PRIdMAX"", (intmax_t)index_to_int(*size), (intmax_t)da(d,array_slice)->n_entries);
 799                         break;
 800                 case DATA_TAG_array_pointers:
 801                         if (unlikely(da(d,array_pointers)->n_used_entries > da(d,array_pointers)->n_allocated_entries))
 802                                 internal(file_line, "bist_array_verify_node: pointers entries overflow");
 803
 804                         if (size && unlikely(index_to_int(*size) != da(d,array_pointers)->n_used_entries))
 805                                 internal(file_line, "bist_array_verify_node: pointers invalid size %"PRIdMAX" != %"PRIdMAX"", (intmax_t)index_to_int(*size), (intmax_t)da(d,array_pointers)->n_used_entries);
 806
 807                         for (i = 0; i < da(d,array_pointers)->n_used_entries; i++) {
 808                                 struct data *p = pointer_get_data(da(d,array_pointers)->pointer[i]);
 809                                 n = *cast_ptr(int_bist_t *, da_flat(p));
 810                                 if (unlikely(n != abs_idx + i))
 811                                         internal(file_line, "bist_array_verify_node: invalid pointer value %"PRIdMAX" + %"PRIdMAX" != %"PRIdMAX"", (intmax_t)abs_idx, (intmax_t)i, (intmax_t)n);
 812                         }
 813
 814                         break;
 815                 case DATA_TAG_array_same:
 816                         if (size && (unlikely(!index_ge_index(*size, da(d,array_same)->n_entries)) ||
 817                                      unlikely(!index_ge_index(da(d,array_same)->n_entries, *size))))
 818                                 internal(file_line, "bist_array_verify_node: same invalid size %"PRIdMAX" != %"PRIdMAX"", (intmax_t)index_to_int(*size), (intmax_t)index_to_int(da(d,array_same)->n_entries));
 819                         s = pointer_get_data(da(d,array_same)->pointer);
 820                         n = *cast_ptr(int_bist_t *, da_flat(s));
 821                         if (unlikely(n != SAME_MAGIC))
 822                                 internal(file_line, "bist_array_verify_node: invalid same value %ld", (long)n);
 823                         if (unlikely(!st->array_n_same))
 824                                 st->array_same_pointer = s;
 825                         else if (unlikely(st->array_same_pointer != s))
 826                                 internal(file_line, "bist_array_verify_node: same unexpectedly split");
 827                         st->array_n_same++;
 828                         break;
 829                 case DATA_TAG_array_btree:
 830                         if (unlikely(da(d,array_btree)->n_used_btree_entries > da(d,array_btree)->n_allocated_btree_entries))
 831                                 internal(file_line, "bist_array_verify_node: btree entries overflow");
 832
 833                         if (unlikely(da(d,array_btree)->n_used_btree_entries < (!size ? 2 : BTREE_MIN_SIZE)) ||
 834                             unlikely(da(d,array_btree)->n_used_btree_entries > BTREE_MAX_SIZE))
 835                                 internal(file_line, "bist_array_verify_node: btree entries not in range (%"PRIuMAX",%"PRIuMAX"): %"PRIuMAX"", (uintmax_t)(!size ? 2 : BTREE_MIN_SIZE), (uintmax_t)BTREE_MAX_SIZE, (uintmax_t)da(d,array_btree)->n_used_btree_entries);
 836
 837                         if (size && (unlikely(!index_ge_index(*size, da(d,array_btree)->btree[da(d,array_btree)->n_used_btree_entries - 1].end_index)) ||
 838                                      unlikely(!index_ge_index(da(d,array_btree)->btree[da(d,array_btree)->n_used_btree_entries - 1].end_index, *size))))
 839                                 internal(file_line, "bist_array_verify_node: btree invalid size: %"PRIdMAX" != %"PRIdMAX"", (intmax_t)index_to_int(*size), (intmax_t)index_to_int(da(d,array_btree)->btree[da(d,array_btree)->n_used_btree_entries - 1].end_index));
 840
 841                         for (bi = 0; bi < da(d,array_btree)->n_used_btree_entries; bi++) {
 842                                 struct data *sub;
 843                                 array_index_t sub_size;
 844                                 int_bist_t ab = abs_idx;
 845                                 index_copy(&sub_size, da(d,array_btree)->btree[bi].end_index);
 846                                 if (bi) {
 847                                         array_index_t *ei = &da(d,array_btree)->btree[bi - 1].end_index;
 848                                         if (unlikely(index_is_mp(*ei))) {
 849                                                 mpint_t mp;
 850                                                 int_bist_t mpi = (int_bist_t)-0x7fffffffL;      /* avoid warning */
 851                                                 index_to_mpint(*ei, &mp);
 852                                                 cat(mpint_export_to_,int_bist_t)(&mp, &mpi, NULL);
 853                                                 mpint_free(&mp);
 854                                                 ab += mpi;
 855                                         } else {
 856                                                 ab += (int_bist_t)index_to_int(*ei);
 857                                         }
 858                                         index_sub(&sub_size, *ei);
 859                                 }
 860
 861                                 sub = pointer_get_data(da(d,array_btree)->btree[bi].node);
 862                                 da_array_assert_son(d, sub);
 863                                 bist_array_verify_node(st, sub, &sub_size, ab);
 864                                 index_free(&sub_size);
 865                         }
 866                         break;
 867                 default:
 868                         internal(file_line, "bist_array_verify_node: invalid array tag %u", da_tag(d));
 869         }
 870 }
 871
 872 static void bist_array_verify(struct bist_array_state *st, bool test_same)
 873 {
 874         struct data *d = pointer_get_data(st->array_ptr);
 875         st->array_n_same = 0;
 876         bist_array_verify_node(st, d, NULL, 0);
 877 #if 1
 878         if (test_same && st->array_n_same && unlikely(st->array_n_same != (int_bist_t)refcount_get_nonatomic(&st->array_same_pointer->refcount_)))
 879                 internal(file_line, "bist_array_verify: same refcount mismatch: %ld != %ld", (long)st->array_n_same, (long)refcount_get_nonatomic(&st->array_same_pointer->refcount_));
 880 #endif
 881 }
 882
 883 static void bist_array_test_ptr(pointer_t ptr, int_bist_t want)
 884 {
 885         int_bist_t n = *cast_ptr(int_bist_t *, da_flat(pointer_get_data(ptr)));
 886         if (unlikely(n != want))
 887                 internal(file_line, "bist_array_test_ptr: invalid pointer value: %ld != %ld", (long)n, (long)want);
 888 }
 889
 890 static array_index_t int32_to_idx(int_bist_t i)
 891 {
 892         array_index_t idx;
 893         if (INT_DEFAULT_BITS >= sizeof(int_bist_t) * 8
 894 #ifdef MPINT_GMP
 895             && rand() & 1
 896 #endif
 897             ) {
 898                 index_from_int(&idx, (int_default_t)i);
 899         } else {
 900                 mpint_t mp;
 901                 cat(mpint_init_from_,int_bist_t)(&mp, i, NULL);
 902                 index_from_mp(&idx, &mp);
 903                 mpint_free(&mp);
 904         }
 905         return idx;
 906 }
 907
 908 static void bist_array_toggle(struct bist_array_state *st, int_bist_t i)
 909 {
 910         pointer_t *result_ptr;
 911         unsigned char *result_flat;
 912         const struct type *flat_type;
 913         struct data *d;
 914
 915         array_read(pointer_get_data(st->array_ptr), int32_to_idx(i), &result_ptr, &result_flat, &flat_type, NULL);
 916
 917         if (!st->array_flag[i]) {
 918                 if (unlikely(!result_flat))
 919                         internal(file_line, "bist_array_toggle: result_flat should be set at index %ld", (long)i);
 920                 if (unlikely(result_ptr != NULL))
 921                         internal(file_line, "bist_array_toggle: result_ptr should not be set at index %ld", (long)i);
 922                 if (unlikely(!type_is_equal(flat_type, int_bist_type)))
 923                         internal(file_line, "bist_array_toggle: invalid type at index %ld", (long)i);
 924                 if (unlikely(*cast_ptr(int_bist_t *, result_flat) != i))
 925                         internal(file_line, "bist_array_toggle: invalid flat value at index %ld: %ld", (long)i, (long)*cast_ptr(int_bist_t *, result_flat));
 926                 if (unlikely(!array_modify(&st->array_ptr, int32_to_idx(i), ARRAY_MODIFY_NEED_PTR, &result_ptr, &result_flat, &flat_type, NULL, NULL)))
 927                         fatal("bist_array_toggle: array_modify need ptr failed");
 928                         /*internal(file_line, "bist_array_toggle: array_modify failed");*/
 929                 bist_array_test_ptr(*result_ptr, i);
 930                 st->array_flag[i] = 1;
 931         } else {
 932                 int_bist_t should_be;
 933                 if (unlikely(result_flat != NULL))
 934                         internal(file_line, "bist_array_toggle: result_flat should not be set at index %ld", (long)i);
 935                 if (unlikely(!result_ptr))
 936                         internal(file_line, "bist_array_toggle: result_ptr should be set at index %ld", (long)i);
 937                 d = pointer_get_data(*result_ptr);
 938                 if (st->array_flag[i] == -1)
 939                         should_be = SAME_MAGIC;
 940                 else
 941                         should_be = i;
 942                 if (unlikely(*cast_ptr(int_bist_t *, da_flat(d)) != should_be))
 943                         internal(file_line, "bist_array_toggle: invalid pointed value at index %ld: %ld != %ld", (long)i, (long)*cast_ptr(int_bist_t *, da_flat(d)), (long)should_be);
 944                 flat_type = int_bist_type;
 945                 if (st->array_flag[i] == -1 && rand() & 1) {
 946                         struct data *flat;
 947                         int_bist_t di;
 948                         if (unlikely(!array_modify(&st->array_ptr, int32_to_idx(i), ARRAY_MODIFY_NEED_PTR, &result_ptr, &result_flat, &flat_type, NULL, NULL)))
 949                                 fatal("bist_array_toggle: array_modify from same need ptr failed");
 950                                 /*internal(file_line, "bist_array_toggle: array_modify failed");*/
 951                         bist_array_test_ptr(*result_ptr, SAME_MAGIC);
 952                         di = i;
 953                         flat = data_alloc_flat_mayfail(TYPE_TAG_N, cast_ptr(unsigned char *, &di), sizeof(int_bist_t), NULL pass_file_line);
 954                         pointer_dereference(*result_ptr);
 955                         *result_ptr = pointer_data(flat);
 956                         st->array_flag[i] = 1;
 957                 } else {
 958                         if (unlikely(!array_modify(&st->array_ptr, int32_to_idx(i), ARRAY_MODIFY_NEED_FLAT, &result_ptr, &result_flat, &flat_type, NULL, NULL)))
 959                                 fatal("bist_array_toggle: array_modify need ptr failed");
 960                                 /*internal(file_line, "bist_array_toggle: array_modify failed");*/
 961                         *cast_ptr(int_bist_t *, result_flat) = i;
 962                         st->array_flag[i] = 0;
 963                 }
 964         }
 965         bist_array_verify(st, true);
 966 }
 967
 968 static attr_noinline void bist_array_st(struct bist_array_state *st, unsigned flags)
 969 {
 970         unsigned rep;
 971         int_bist_t i, j, half, l;
 972         int_bist_t di;
 973         struct data *array, *flat;
 974         pointer_t array_ptr_2;
 975
 976         if (!(flags & 0x80)) {
 977                 array = data_alloc_array_flat_mayfail(int_bist_type, 0, 0, false, NULL pass_file_line);
 978                 st->array_ptr = pointer_data(array);
 979                 array_ptr_2 = pointer_data(array);
 980                 pointer_reference_owned(array_ptr_2);
 981
 982                 half = N_ARRAY_ENTRIES / 2;
 983                 half -= half % FLAT_ARRAY_LENGTH;
 984                 for (j = half; j < N_ARRAY_ENTRIES; j += l) {
 985                         l = minimum(N_ARRAY_ENTRIES - j, (int_bist_t)FLAT_ARRAY_LENGTH);
 986                         if (!(flags & 0x01)) {
 987                                 array = data_alloc_array_flat_mayfail(int_bist_type, l, l, false, NULL pass_file_line);
 988                                 for (i = 0; i < l; i++) {
 989                                         cast_ptr(int_bist_t *, da_array_flat(array))[i] = j + i;
 990                                         st->array_flag[j + i] = 0;
 991                                 }
 992                         } else {
 993                                 array = data_alloc_array_pointers_mayfail(l, l, NULL pass_file_line);
 994                                 for (i = 0; i < l; i++) {
 995                                         di = j + i;
 996                                         flat = data_alloc_flat_mayfail(TYPE_TAG_N, cast_ptr(unsigned char *, &di), sizeof(int_bist_t), NULL pass_file_line);
 997                                         da(array,array_pointers)->pointer[i] = pointer_data(flat);
 998                                         st->array_flag[j + i] = 1;
 999                                 }
1000                         }
1001                         st->array_ptr = pointer_data(array_join(pointer_get_data(st->array_ptr), array, NULL));
1002                 }
1003                 for (j = half - FLAT_ARRAY_LENGTH; j >= 0; j -= FLAT_ARRAY_LENGTH) {
1004                         l = FLAT_ARRAY_LENGTH;
1005                         if (!(flags & 0x01)) {
1006                                 array = data_alloc_array_flat_mayfail(int_bist_type, l, l, false, NULL pass_file_line);
1007                                 for (i = 0; i < l; i++) {
1008                                         cast_ptr(int_bist_t *, da_array_flat(array))[i] = j + i;
1009                                         st->array_flag[j + i] = 0;
1010                                 }
1011                         } else {
1012                                 array = data_alloc_array_pointers_mayfail(l, l, NULL pass_file_line);
1013                                 for (i = 0; i < l; i++) {
1014                                         di = j + i;
1015                                         flat = data_alloc_flat_mayfail(TYPE_TAG_N, cast_ptr(unsigned char *, &di), sizeof(int_bist_t), NULL pass_file_line);
1016                                         da(array,array_pointers)->pointer[i] = pointer_data(flat);
1017                                         st->array_flag[j + i] = 1;
1018                                 }
1019                         }
1020                         array_ptr_2 = pointer_data(array_join(array, pointer_get_data(array_ptr_2), NULL));
1021                 }
1022                 st->array_ptr = pointer_data(array_join(pointer_get_data(array_ptr_2), pointer_get_data(st->array_ptr), NULL));
1023         } else {
1024                 array = data_alloc_array_flat_mayfail(int_bist_type, N_ARRAY_ENTRIES, N_ARRAY_ENTRIES, false, NULL pass_file_line);
1025                 for (i = 0; i < N_ARRAY_ENTRIES; i++) {
1026                         st->array_flag[i] = 0;
1027                         cast_ptr(int_bist_t *, da_array_flat(array))[i] = i;
1028                 }
1029                 st->array_ptr = pointer_data(array);
1030         }
1031         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1032         for (rep = 0; rep < N_ARRAY_OPERATIONS; rep++) {
1033                 i = rand() % N_ARRAY_ENTRIES;
1034                 bist_array_toggle(st, i);
1035         }
1036         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1037         for (j = 0; j < ARRAY_STRIDE; j++)
1038                 for (i = j; i <= N_ARRAY_ENTRIES - ARRAY_STRIDE; i += ARRAY_STRIDE) {
1039                         if (!st->array_flag[i])
1040                                 bist_array_toggle(st, i);
1041                 }
1042         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1043         for (rep = 0; rep < N_ARRAY_OPERATIONS; rep++) {
1044                 i = rand() % N_ARRAY_ENTRIES;
1045                 bist_array_toggle(st, i);
1046         }
1047         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1048         for (j = 0; j < ARRAY_STRIDE; j++)
1049                 for (i = j; i <= N_ARRAY_ENTRIES - ARRAY_STRIDE; i += ARRAY_STRIDE) {
1050                         if (st->array_flag[i])
1051                                 bist_array_toggle(st, i);
1052                 }
1053         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1054         bist_array_verify(st, true);
1055         pointer_dereference(st->array_ptr);
1056 }
1057
1058 #if 0
1059 struct bist_array_state *global_st;
1060 void bist_g_verify(void)
1061 {
1062         bist_array_verify(global_st, false);
1063 }
1064 #endif
1065
1066 static attr_noinline void bist_array_2_st(struct bist_array_state *st)
1067 {
1068         unsigned rep;
1069         int_bist_t i, j, l;
1070         int_bist_t di;
1071         struct data *array, *flat;
1072         pointer_t flat_ptr;
1073
1074         di = SAME_MAGIC;
1075         flat = data_alloc_flat_mayfail(TYPE_TAG_N, cast_ptr(unsigned char *, &di), sizeof(int_bist_t), NULL pass_file_line);
1076         flat_ptr = pointer_data(flat);
1077         array = data_alloc_array_pointers_mayfail(0, 0, NULL pass_file_line);
1078         st->array_ptr = pointer_data(array);
1079         for (j = 0; j < N_ARRAY_ENTRIES; j += l) {
1080                 array_index_t ll;
1081                 l = minimum(N_ARRAY_ENTRIES - j, (int_bist_t)SAME_ARRAY_LENGTH);
1082                 if (j) pointer_reference_owned(flat_ptr);
1083                 index_from_int(&ll, l);
1084                 array = data_alloc_array_same_mayfail(ll, NULL pass_file_line);
1085                 da(array,array_same)->pointer = flat_ptr;
1086                 for (i = 0; i < l; i++) {
1087                         st->array_flag[j + i] = -1;
1088                 }
1089                 st->array_ptr = pointer_data(array_join(pointer_get_data(st->array_ptr), array, NULL));
1090         }
1091         for (rep = 0; rep < N_ARRAY_OPERATIONS; rep++) {
1092                 struct data *a1, *a2;
1093                 array_index_t z0, zi, zn;
1094                 i = rand() % (N_ARRAY_ENTRIES + 1);
1095                 /*debug("%d: %d/%d", rep, i, (int)N_ARRAY_ENTRIES);*/
1096                 bist_array_verify(st, true);
1097                 index_from_int(&z0, 0);
1098                 index_from_int(&zi, i);
1099                 a1 = array_sub(pointer_get_data(st->array_ptr), z0, zi, false, NULL);
1100                 bist_dump_array("a1", a1);
1101                 bist_array_verify(st, false);
1102                 index_from_int(&zi, i);
1103                 index_from_int(&zn, N_ARRAY_ENTRIES - i);
1104                 a2 = array_sub(pointer_get_data(st->array_ptr), zi, zn, false, NULL);
1105                 bist_dump_array("a2", a2);
1106 #if 0
1107                 data_dereference(a1);
1108                 data_dereference(a2);
1109 #else
1110                 bist_array_verify(st, false);
1111                 pointer_dereference(st->array_ptr);
1112                 bist_dump_array("a1", a1);
1113                 bist_dump_array("a2", a2);
1114                 st->array_ptr = pointer_data(array_join(a1, a2, NULL));
1115                 bist_dump_array("array_ptr", pointer_get_data(st->array_ptr));
1116 #endif
1117         }
1118         bist_array_verify(st, true);
1119         for (rep = 0; rep < N_ARRAY_OPERATIONS; rep++) {
1120                 i = rand() % N_ARRAY_ENTRIES;
1121                 bist_array_toggle(st, i);
1122         }
1123         /*debug("depth: %d", da_array_depth(pointer_get_data(st->array_ptr)));*/
1124         pointer_dereference(st->array_ptr);
1125 }
1126
1127 static attr_noinline void bist_array(unsigned flags)
1128 {
1129         struct bist_array_state *st = mem_alloc(struct bist_array_state *, sizeof(struct bist_array_state));
1130         if (!(flags & 0x100))
1131                 bist_array_st(st, flags);
1132         else
1133                 bist_array_2_st(st);
1134         mem_free(st);
1135 }
1136
1137
1138 #define BIST_THREADS    10
1139 static tls_decl(int, bist_tls);
1140 shared_var mutex_t bist_mutex;
1141 rwlock_decl(bist_rwlock);
1142 shared_var cond_t bist_cond_0;
1143 shared_var cond_t bist_cond_1;
1144 shared_var cond_t bist_cond_2;
1145 shared_var int bist_state;
1146 shared_var int bist_counter;
1147 shared_var int bist_terminating;
1148 shared_var int bist_rwlock_test;
1149
1150 #ifndef THREAD_NONE
1151 shared_var thread_t bist_threads[BIST_THREADS];
1152 #define bist_check_missing_stack_probe  name(bist_check_missing_stack_probe)
1153 attr_noinline void bist_check_missing_stack_probe(void);
1154 attr_noinline void bist_check_missing_stack_probe(void)
1155 {
1156         volatile char attr_unused array[8192];
1157         array[0] = 0;
1158 }
1159 thread_function_decl(bist_thread_fn,
1160         int tl;
1161         int myid = (int)(cast_ptr(thread_t *, arg) - bist_threads);
1162
1163         bist_check_missing_stack_probe();
1164
1165         tls_set(int, bist_tls, myid);
1166
1167         cond_lock(&bist_cond_0);
1168         cond_unlock_signal(&bist_cond_0);
1169
1170         cond_lock(&bist_cond_1);
1171         mutex_lock(&bist_mutex);
1172         bist_counter++;
1173         mutex_unlock(&bist_mutex);
1174         if (bist_counter == BIST_THREADS) cond_unlock_signal(&bist_cond_1);
1175         else cond_unlock(&bist_cond_1);
1176
1177         cond_lock(&bist_cond_2);
1178         while (1) {
1179                 if (bist_state == 1 && bist_counter == myid)
1180                         break;
1181                 cond_wait(&bist_cond_2);
1182         }
1183         cond_unlock(&bist_cond_2);
1184
1185         cond_lock(&bist_cond_1);
1186         bist_terminating = myid;
1187         cond_unlock_broadcast(&bist_cond_1);
1188
1189         rwlock_lock_read(&bist_rwlock);
1190         if (unlikely(bist_rwlock_test != myid))
1191                 internal(file_line, "bist_thread_fn: invalid rwlock value %d != %d", bist_rwlock_test, myid);
1192         rwlock_unlock_read(&bist_rwlock);
1193
1194         tl = tls_get(int, bist_tls);
1195         if (unlikely(tl != myid))
1196                 internal(file_line, "bist_thread_fn: invalid tls value %d != %d", tl, myid);
1197 )
1198 #endif
1199
1200 static attr_noinline void bist_thread(unsigned attr_unused flags)
1201 {
1202         int i;
1203         int tl;
1204         const char *thread_str;
1205         tls_init(int, bist_tls);
1206         tls_set(int, bist_tls, -1);
1207         mutex_init(&bist_mutex);
1208         rwlock_init(&bist_rwlock);
1209         cond_init(&bist_cond_0);
1210         cond_init(&bist_cond_1);
1211         cond_init(&bist_cond_2);
1212
1213         thread_str = getenv("AJLA_THREADS");
1214         if (thread_str && !strcmp(thread_str, "1"))
1215                 goto skip_bist_thread;
1216
1217         bist_state = 0;
1218         bist_counter = 0;
1219         bist_terminating = -1;
1220         bist_rwlock_test = -1;
1221         mutex_lock(&bist_mutex);
1222         for (i = 0; i < BIST_THREADS; i++) {
1223                 cond_lock(&bist_cond_0);
1224 #ifndef THREAD_NONE
1225                 thread_spawn(&bist_threads[i], bist_thread_fn, &bist_threads[i], PRIORITY_TIMER, NULL);
1226                 cond_wait(&bist_cond_0);
1227 #endif
1228                 cond_unlock(&bist_cond_0);
1229         }
1230         if (unlikely(bist_counter != 0))
1231                 internal(file_line, "bist_thread: mutex doesn't work, counter %d", bist_counter);
1232         mutex_unlock(&bist_mutex);
1233         cond_lock(&bist_cond_1);
1234 #ifdef THREAD_NONE
1235         bist_counter = BIST_THREADS;
1236 #endif
1237         while (1) {
1238                 if (bist_counter == BIST_THREADS)
1239                         break;
1240                 cond_wait(&bist_cond_1);
1241         }
1242         cond_unlock(&bist_cond_1);
1243         cond_lock(&bist_cond_2);
1244         bist_state = 1;
1245         while (bist_counter) {
1246                 bist_counter--;
1247                 rwlock_lock_write(&bist_rwlock);
1248                 cond_unlock_broadcast(&bist_cond_2);
1249                 cond_lock(&bist_cond_1);
1250 #ifndef THREAD_NONE
1251                 while (bist_terminating != bist_counter)
1252                         cond_wait(&bist_cond_1);
1253 #endif
1254                 cond_unlock(&bist_cond_1);
1255                 bist_rwlock_test = bist_counter;
1256                 rwlock_unlock_write(&bist_rwlock);
1257 #ifndef THREAD_NONE
1258                 thread_join(&bist_threads[bist_counter]);
1259 #endif
1260                 cond_lock(&bist_cond_2);
1261         }
1262         cond_unlock(&bist_cond_2);
1263
1264 skip_bist_thread:
1265         mutex_done(&bist_mutex);
1266         rwlock_done(&bist_rwlock);
1267         cond_done(&bist_cond_0);
1268         cond_done(&bist_cond_1);
1269         cond_done(&bist_cond_2);
1270         tl = tls_get(int, bist_tls);
1271         if (unlikely(tl != -1))
1272                 internal(file_line, "bist_thread: invalid tls value %d != -1", tl);
1273         tls_done(int, bist_tls);
1274 }
1275
1276
1277 #ifndef THREAD_NONE
1278
1279 struct bist_background_function {
1280         void (*fn)(unsigned);
1281         unsigned flags;
1282 };
1283
1284 shared_var thread_t *bist_background_threads shared_init(NULL);
1285 shared_var size_t bist_background_threads_n;
1286
1287 thread_function_decl(bist_background_thread,
1288         struct bist_background_function *bbf = arg;
1289         bbf->fn(bbf->flags);
1290         mem_free(bbf);
1291 )
1292
1293 #endif
1294
1295 static void bist_background(void (*fn)(unsigned), unsigned flags)
1296 {
1297 #ifndef THREAD_NONE
1298         if (!getenv("AJLA_BIST_ST")) {
1299                 struct bist_background_function *bbf;
1300                 thread_t thr;
1301                 if (!bist_background_threads) {
1302                         array_init(thread_t, &bist_background_threads, &bist_background_threads_n);
1303                 }
1304                 bbf = mem_alloc(struct bist_background_function *, sizeof(struct bist_background_function));
1305                 bbf->fn = fn;
1306                 bbf->flags = flags;
1307                 thread_spawn(&thr, bist_background_thread, bbf, PRIORITY_COMPUTE, NULL);
1308                 array_add(thread_t, &bist_background_threads, &bist_background_threads_n, thr);
1309         } else
1310 #endif
1311                 fn(flags);
1312 }
1313
1314 static void bist_background_done(void)
1315 {
1316 #ifndef THREAD_NONE
1317         if (bist_background_threads) {
1318                 size_t i;
1319                 for (i = 0; i < bist_background_threads_n; i++) {
1320                         thread_join(&bist_background_threads[i]);
1321                 }
1322                 mem_free(bist_background_threads);
1323                 bist_background_threads = NULL;
1324         }
1325 #endif
1326 }
1327
1328
1329 #endif
1330
1331
1332 void name(bist)(void)
1333 {
1334 #ifdef DEBUG_INFO
1335 #if defined(C_LITTLE_ENDIAN)
1336         const char *endian = "little endian";
1337 #elif defined(C_BIG_ENDIAN)
1338         const char *endian = "big endian";
1339 #else
1340         const char *endian = "unknown endian";
1341 #endif
1342         debug("sizeof(int) = %d, sizeof(long) = %d, sizeof(size_t) = %d, sizeof(void *) = %d, sizeof(int_default_t) = %d", (int)sizeof(int), (int)sizeof(long), (int)sizeof(size_t), (int)sizeof(void *), (int)sizeof(int_default_t));
1343         debug("align_of(int) = %d, align_of(long) = %d, align_of(size_t) = %d, align_of(void *) = %d, align_of(int_default_t) = %d", (int)align_of(int), (int)align_of(long), (int)align_of(size_t), (int)align_of(void *), (int)align_of(int_default_t));
1344 #if defined(HAVE_NATIVE_FP16) || !(REAL_MASK & 1)
1345 #define em      ""
1346 #else
1347 #define em      " (fp16 emulated)"
1348 #endif
1349         debug("fixed_mask = 0x%x, int_mask = 0x%x, real_mask = 0x%x%s", (1 << TYPE_FIXED_N) - 1, INT_MASK, REAL_MASK, em);
1350 #undef em
1351         debug("scalar_align = %d, frame_align = %d, max_frame_align = %d, slot_size = %d, %s", (int)scalar_align, (int)frame_align, (int)max_frame_align, (int)slot_size, endian);
1352 #endif
1353         bist_constants();
1354 #ifdef DEBUG_BIST
1355         if (!getenv("AJLA_NO_BIST")) {
1356                 bist_memory();
1357                 bist_string();
1358                 bist_memarray();
1359                 bist_pointer();
1360                 bist_refcount();
1361                 bist_arithm();
1362 #define f(n, s, u, sz, bits)    cat(bist_arithm_,s)();
1363                 for_all_int(f, for_all_empty)
1364 #undef f
1365                 bist_background(bist_conv, 0);
1366                 bist_background(bist_rbtree, 0);
1367                 bist_background(bist_array, 0x00);
1368                 bist_background(bist_array, 0x01);
1369                 bist_background(bist_array, 0x80);
1370                 bist_background(bist_array, 0x100);
1371                 bist_background(bist_thread, 0);
1372                 bist_background_done();
1373                 debug("bist passed");
1374         }
1375 #endif
1376         /*{
1377                 size_t len, i;
1378                 char **files;
1379                 dir_handle_t c = os_dir_cwd();
1380                 os_dir_read(c, &files, &len, NULL);
1381                 for (i = 0; i < len; i++) {
1382                         debug("%s", files[i]);
1383                 }
1384                 os_dir_free(files, len);
1385                 os_dir_close(c);
1386         }*/
1387 }
1388
1389 #endif