"Fossies" - the Fresh Open Source Software Archive

Member "stress-ng-0.09.56/stress-tree.c" (15 Mar 2019, 12770 Bytes) of package /linux/privat/stress-ng-0.09.56.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "stress-tree.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 0.09.52_vs_0.09.54.

    1 /*
    2  * Copyright (C) 2016-2019 Canonical, Ltd.
    3  *
    4  * This program is free software; you can redistribute it and/or
    5  * modify it under the terms of the GNU General Public License
    6  * as published by the Free Software Foundation; either version 2
    7  * of the License, or (at your option) any later version.
    8  *
    9  * This program is distributed in the hope that it will be useful,
   10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   12  * GNU General Public License for more details.
   13  *
   14  * You should have received a copy of the GNU General Public License
   15  * along with this program; if not, write to the Free Software
   16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
   17  *
   18  * This code is a complete clean re-write of the stress tool by
   19  * Colin Ian King <colin.king@canonical.com> and attempts to be
   20  * backwardly compatible with the stress tool by Amos Waterland
   21  * <apw@rossby.metr.ou.edu> but has more stress tests and more
   22  * functionality.
   23  *
   24  */
   25 #include "stress-ng.h"
   26 
   27 struct tree_node;
   28 
   29 typedef void (*stress_tree_func)(const args_t *args,
   30                  const size_t n,
   31                  struct tree_node *data);
   32 
   33 typedef struct {
   34         const char              *name;  /* human readable form of stressor */
   35         const stress_tree_func   func;  /* the tree method function */
   36 } stress_tree_method_info_t;
   37 
   38 static const stress_tree_method_info_t tree_methods[];
   39 
   40 #if defined(HAVE_LIB_BSD) && !defined(__APPLE__)
   41 
   42 static volatile bool do_jmp = true;
   43 static sigjmp_buf jmp_env;
   44 
   45 struct binary_node {
   46     struct tree_node *left;
   47     struct tree_node *right;
   48 };
   49 
   50 #define LH  0
   51 #define EH  1
   52 #define RH  2
   53 
   54 struct avl_node {
   55     struct tree_node *left;
   56     struct tree_node *right;
   57     uint8_t bf;
   58 };
   59 
   60 struct tree_node {
   61     uint64_t value;
   62     union {
   63         RB_ENTRY(tree_node) rb;
   64         SPLAY_ENTRY(tree_node)  splay;
   65         struct binary_node  binary;
   66         struct avl_node     avl;
   67         uint64_t        padding[3];
   68     } u;
   69 };
   70 
   71 #endif
   72 
   73 /*
   74  *  stress_set_tree_size()
   75  *  set tree size
   76  */
   77 int stress_set_tree_size(const char *opt)
   78 {
   79     uint64_t tree_size;
   80 
   81     tree_size = get_uint64(opt);
   82     check_range("tree-size", tree_size,
   83         MIN_TREE_SIZE, MAX_TREE_SIZE);
   84     return set_setting("tree-size", TYPE_ID_UINT64, &tree_size);
   85 }
   86 
   87 #if defined(HAVE_LIB_BSD) && !defined(__APPLE__)
   88 
   89 /*
   90  *  stress_tree_handler()
   91  *  SIGALRM generic handler
   92  */
   93 static void MLOCKED_TEXT stress_tree_handler(int signum)
   94 {
   95     (void)signum;
   96 
   97     if (do_jmp) {
   98         do_jmp = false;
   99         siglongjmp(jmp_env, 1);     /* Ugly, bounce back */
  100     }
  101 }
  102 
  103 static int tree_node_cmp_fwd(struct tree_node *n1, struct tree_node *n2)
  104 {
  105     if (n1->value == n2->value)
  106         return 0;
  107     if (n1->value > n2->value)
  108         return 1;
  109     else
  110         return -1;
  111 }
  112 
  113 static RB_HEAD(stress_rb_tree, tree_node) rb_root;
  114 RB_PROTOTYPE(stress_rb_tree, tree_node, u.rb, tree_node_cmp_fwd);
  115 RB_GENERATE(stress_rb_tree, tree_node, u.rb, tree_node_cmp_fwd);
  116 
  117 static SPLAY_HEAD(stress_splay_tree, tree_node) splay_root;
  118 SPLAY_PROTOTYPE(stress_splay_tree, tree_node, u.splay, tree_node_cmp_fwd);
  119 SPLAY_GENERATE(stress_splay_tree, tree_node, u.splay, tree_node_cmp_fwd);
  120 
  121 static void stress_tree_rb(
  122     const args_t *args,
  123     const size_t n,
  124     struct tree_node *data)
  125 {
  126     size_t i;
  127     register struct tree_node *node, *next;
  128 
  129     RB_INIT(&rb_root);
  130 
  131     for (node = data, i = 0; i < n; i++, node++) {
  132         register struct tree_node *res;
  133 
  134         res = RB_FIND(stress_rb_tree, &rb_root, node);
  135         if (!res)
  136             RB_INSERT(stress_rb_tree, &rb_root, node);
  137     }
  138     for (node = data, i = 0; i < n; i++, node++) {
  139         struct tree_node *find;
  140 
  141         find = RB_FIND(stress_rb_tree, &rb_root, node);
  142         if (!find)
  143             pr_err("%s: rb tree node #%zd node found\n",
  144                 args->name, i);
  145     }
  146     for (node = RB_MIN(stress_rb_tree, &rb_root); node; node = next) {
  147         next = RB_NEXT(stress_rb_tree, &rb_root, node);
  148         RB_REMOVE(stress_rb_tree, &rb_root, node);
  149     }
  150 }
  151 
  152 static void stress_tree_splay(
  153     const args_t *args,
  154     const size_t n,
  155     struct tree_node *nodes)
  156 {
  157     size_t i;
  158     register struct tree_node *node, *next;
  159 
  160     SPLAY_INIT(&splay_root);
  161 
  162     for (node = nodes, i = 0; i < n; i++, node++) {
  163         register struct tree_node *res;
  164 
  165         res = SPLAY_FIND(stress_splay_tree, &splay_root, node);
  166         if (!res)
  167             SPLAY_INSERT(stress_splay_tree, &splay_root, node);
  168     }
  169     for (node = nodes, i = 0; i < n; i++, node++) {
  170         struct tree_node *find;
  171 
  172         find = SPLAY_FIND(stress_splay_tree, &splay_root, node);
  173         if (!find)
  174             pr_err("%s: splay tree node #%zd node found\n",
  175                 args->name, i);
  176     }
  177     for (node = SPLAY_MIN(stress_splay_tree, &splay_root); node; node = next) {
  178         next = SPLAY_NEXT(stress_splay_tree, &splay_root, node);
  179         SPLAY_REMOVE(stress_splay_tree, &splay_root, node);
  180         (void)memset(&node->u.splay, 0, sizeof(node->u.splay));
  181     }
  182 }
  183 
  184 static void binary_insert(
  185     struct tree_node **head,
  186     struct tree_node *node)
  187 {
  188     while (*head) {
  189         head = (node->value <= (*head)->value) ?
  190             &(*head)->u.binary.left :
  191             &(*head)->u.binary.right;
  192     }
  193     *head = node;
  194 }
  195 
  196 static struct tree_node *binary_find(
  197     struct tree_node *head,
  198     struct tree_node *node)
  199 {
  200     while (head) {
  201         if (node->value == head->value)
  202             return head;
  203         head = (node->value <= head->value) ?
  204                 head->u.binary.left :
  205                 head->u.binary.right;
  206     }
  207     return NULL;
  208 }
  209 
  210 static void binary_remove_tree(struct tree_node *node)
  211 {
  212     if (node) {
  213         binary_remove_tree(node->u.binary.left);
  214         binary_remove_tree(node->u.binary.right);
  215         node->u.binary.left = NULL;
  216         node->u.binary.right = NULL;
  217     }
  218 }
  219 
  220 
  221 static void stress_tree_binary(
  222     const args_t *args,
  223     const size_t n,
  224     struct tree_node *data)
  225 {
  226     size_t i;
  227     struct tree_node *node, *head = NULL;
  228 
  229     for (node = data, i = 0; i < n; i++, node++) {
  230         binary_insert(&head, node);
  231     }
  232 
  233     for (node = data, i = 0; i < n; i++, node++) {
  234         struct tree_node *find;
  235 
  236         find = binary_find(head, node);
  237         if (!find)
  238             pr_err("%s: binary tree node #%zd node found\n",
  239                 args->name, i);
  240     }
  241     binary_remove_tree(head);
  242 }
  243 
  244 static void avl_insert(
  245     struct tree_node **root,
  246     struct tree_node *node,
  247     bool *taller)
  248 {
  249     bool sub_taller = false;
  250     register struct tree_node *p, *q;
  251 
  252     if (!*root) {
  253         *root = node;
  254         (*root)->u.avl.left = NULL;
  255         (*root)->u.avl.right = NULL;
  256         (*root)->u.avl.bf = EH;
  257         *taller = true;
  258     } else {
  259         if (node->value < (*root)->value) {
  260             avl_insert(&(*root)->u.avl.left, node, &sub_taller);
  261             if (sub_taller) {
  262                 switch ((*root)->u.avl.bf) {
  263                 case EH:
  264                     (*root)->u.avl.bf = LH;
  265                     *taller = true;
  266                     break;
  267                 case RH:
  268                     (*root)->u.avl.bf = EH;
  269                     *taller = false;
  270                     break;
  271                 case LH:
  272                     /* Rebalance required */
  273                     p = (*root)->u.avl.left;
  274                     if (p->u.avl.bf == LH) {
  275                         /* Single rotation */
  276                         (*root)->u.avl.left = p->u.avl.right;
  277                         p->u.avl.right = *root;
  278                         p->u.avl.bf = EH;
  279                         (*root)->u.avl.bf = EH;
  280                         *root = p;
  281                     } else {
  282                         /* Double rotation */
  283                         q = p->u.avl.right;
  284                         (*root)->u.avl.left = q->u.avl.right;
  285                         q->u.avl.right = *root;
  286                         p->u.avl.right = q->u.avl.left;
  287                         q->u.avl.left = p;
  288 
  289                         /* Update balance factors */
  290                         switch (q->u.avl.bf) {
  291                         case RH:
  292                             (*root)->u.avl.bf = EH;
  293                             p->u.avl.bf = LH;
  294                             break;
  295                         case LH:
  296                             (*root)->u.avl.bf = RH;
  297                             p->u.avl.bf = EH;
  298                             break;
  299                         case EH:
  300                             (*root)->u.avl.bf = EH;
  301                             p->u.avl.bf = EH;
  302                             break;
  303                         }
  304                         q->u.avl.bf = EH;
  305                         *root = q;
  306                     }
  307                     *taller = false;
  308                     break;
  309                 }
  310             }
  311         } else if (node->value > (*root)->value) {
  312             avl_insert(&(*root)->u.avl.right, node, &sub_taller);
  313             if (sub_taller) {
  314                 switch ((*root)->u.avl.bf) {
  315                 case LH:
  316                     (*root)->u.avl.bf = EH;
  317                     *taller = false;
  318                     break;
  319                 case EH:
  320                     (*root)->u.avl.bf = RH;
  321                     *taller = true;
  322                     break;
  323                 case RH:
  324                     /* Rebalance required */
  325                     p = (*root)->u.avl.right;
  326                     if (p->u.avl.bf == RH) {
  327                         /* Single rotation */
  328                         (*root)->u.avl.right = p->u.avl.left;
  329                         p->u.avl.left = *root;
  330                         p->u.avl.bf = EH;
  331                         (*root)->u.avl.bf = EH;
  332                         *root = p;
  333                     } else {
  334                         /* Double rotation */
  335                         q = p->u.avl.left;
  336                         (*root)->u.avl.right = q->u.avl.left;
  337                         q->u.avl.left = *root;
  338                         p->u.avl.left = q->u.avl.right;
  339                         q->u.avl.right = p;
  340 
  341                         /* Update balance factors */
  342                         switch (q->u.avl.bf) {
  343                         case LH:
  344                             (*root)->u.avl.bf = EH;
  345                             p->u.avl.bf = RH;
  346                             break;
  347                         case RH:
  348                             (*root)->u.avl.bf = LH;
  349                             p->u.avl.bf = EH;
  350                             break;
  351                         case EH:
  352                             (*root)->u.avl.bf = EH;
  353                             p->u.avl.bf = EH;
  354                             break;
  355                         }
  356                         q->u.avl.bf = EH;
  357                         *root = q;
  358                     }
  359                     *taller = false;
  360                     break;
  361                 }
  362             } else {
  363                 /* tree not rebalanced.. */
  364                 *taller = false;
  365             }
  366         } else {
  367             *taller = false;
  368         }
  369     }
  370 }
  371 
  372 static struct tree_node *avl_find(
  373     struct tree_node *head,
  374     struct tree_node *node)
  375 {
  376     while (head) {
  377         if (node->value == head->value)
  378             return head;
  379         head = (node->value <= head->value) ?
  380                 head->u.avl.left :
  381                 head->u.avl.right;
  382     }
  383     return NULL;
  384 }
  385 
  386 static void avl_remove_tree(struct tree_node *node)
  387 {
  388     if (node) {
  389         avl_remove_tree(node->u.avl.left);
  390         avl_remove_tree(node->u.avl.right);
  391         node->u.avl.left = NULL;
  392         node->u.avl.right = NULL;
  393     }
  394 }
  395 
  396 static void stress_tree_avl(
  397     const args_t *args,
  398     const size_t n,
  399     struct tree_node *data)
  400 {
  401     size_t i;
  402     struct tree_node *node, *head = NULL;
  403 
  404     for (node = data, i = 0; i < n; i++, node++) {
  405         bool taller = false;
  406         avl_insert(&head, node, &taller);
  407     }
  408     for (node = data, i = 0; i < n; i++, node++) {
  409         struct tree_node *find;
  410 
  411         find = avl_find(head, node);
  412         if (!find)
  413             pr_err("%s: avl tree node #%zd node found\n",
  414                 args->name, i);
  415     }
  416     avl_remove_tree(head);
  417 }
  418 
  419 static void stress_tree_all(
  420     const args_t *args,
  421     const size_t n,
  422     struct tree_node *data)
  423 {
  424     stress_tree_rb(args, n, data);
  425     stress_tree_splay(args, n, data);
  426     stress_tree_binary(args, n, data);
  427     stress_tree_avl(args, n, data);
  428 }
  429 #endif
  430 
  431 /*
  432  * Table of tree stress methods
  433  */
  434 static const stress_tree_method_info_t tree_methods[] = {
  435 #if defined(HAVE_LIB_BSD) && !defined(__APPLE__)
  436     { "all",    stress_tree_all },
  437     { "avl",    stress_tree_avl },
  438     { "binary", stress_tree_binary },
  439     { "rb",     stress_tree_rb },
  440     { "splay",  stress_tree_splay },
  441 #endif
  442     { NULL,     NULL },
  443 };
  444 
  445 /*
  446  *  stress_set_tree_method()
  447  *  set the default funccal stress method
  448  */
  449 int stress_set_tree_method(const char *name)
  450 {
  451     stress_tree_method_info_t const *info;
  452 
  453     for (info = tree_methods; info->func; info++) {
  454         if (!strcmp(info->name, name)) {
  455             set_setting("tree-method", TYPE_ID_UINTPTR_T, &info);
  456             return 0;
  457         }
  458     }
  459 
  460     (void)fprintf(stderr, "tree-method must be one of:");
  461     for (info = tree_methods; info->func; info++) {
  462         (void)fprintf(stderr, " %s", info->name);
  463     }
  464     (void)fprintf(stderr, "\n");
  465 
  466     return -1;
  467 }
  468 
  469 #if defined(HAVE_LIB_BSD) && !defined(__APPLE__)
  470 
  471 /*
  472  *  Rotate right a 64 bit value, compiler
  473  *  optimizes this down to a rotate and store
  474  */
  475 static inline uint64_t ror64(const uint64_t val)
  476 {
  477     register uint64_t tmp = val;
  478     register const uint64_t bit0 = (tmp & 1) << 63;
  479 
  480     tmp >>= 1;
  481         return (tmp | bit0);
  482 }
  483 
  484 /*
  485  *  stress_tree()
  486  *  stress tree
  487  */
  488 static int stress_tree(const args_t *args)
  489 {
  490     uint64_t v, tree_size = DEFAULT_TREE_SIZE;
  491     struct tree_node *nodes, *node;
  492     size_t n, i, bit;
  493     struct sigaction old_action;
  494     int ret;
  495     stress_tree_method_info_t const *info = &tree_methods[0];
  496 
  497     (void)get_setting("tree-method", &info);
  498 
  499     if (!get_setting("tree-size", &tree_size)) {
  500         if (g_opt_flags & OPT_FLAGS_MAXIMIZE)
  501             tree_size = MAX_TREE_SIZE;
  502         if (g_opt_flags & OPT_FLAGS_MINIMIZE)
  503             tree_size = MIN_TREE_SIZE;
  504     }
  505     n = (size_t)tree_size;
  506 
  507     if ((nodes = calloc(n, sizeof(struct tree_node))) == NULL) {
  508         pr_fail_dbg("malloc");
  509         return EXIT_NO_RESOURCE;
  510     }
  511 
  512     if (stress_sighandler(args->name, SIGALRM, stress_tree_handler, &old_action) < 0) {
  513         free(nodes);
  514         return EXIT_FAILURE;
  515     }
  516 
  517     ret = sigsetjmp(jmp_env, 1);
  518     if (ret) {
  519         /*
  520          * We return here if SIGALRM jmp'd back
  521          */
  522         (void)stress_sigrestore(args->name, SIGALRM, &old_action);
  523         goto tidy;
  524     }
  525 
  526     v = 0;
  527     for (node = nodes, i = 0, bit = 0; i < n; i++, node++) {
  528         if (!bit) {
  529             v = mwc64();
  530             bit = 1;
  531         } else {
  532             v ^= bit;
  533             bit <<= 1;
  534         }
  535         node->value = v;
  536         v = ror64(v);
  537     }
  538 
  539     do {
  540         uint64_t rnd;
  541 
  542         info->func(args, n, nodes);
  543 
  544         rnd = mwc64();
  545         for (node = nodes, i = 0; i < n; i++, node++)
  546             node->value = ror64(node->value ^ rnd);
  547 
  548         inc_counter(args);
  549     } while (keep_stressing());
  550 
  551     do_jmp = false;
  552     (void)stress_sigrestore(args->name, SIGALRM, &old_action);
  553 tidy:
  554     free(nodes);
  555 
  556     return EXIT_SUCCESS;
  557 }
  558 
  559 stressor_info_t stress_tree_info = {
  560     .stressor = stress_tree,
  561     .class = CLASS_CPU_CACHE | CLASS_CPU | CLASS_MEMORY
  562 };
  563 #else
  564 stressor_info_t stress_tree_info = {
  565     .stressor = stress_not_implemented,
  566     .class = CLASS_CPU_CACHE | CLASS_CPU | CLASS_MEMORY
  567 };
  568 #endif