ck_barrier_tournament.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    1 /*
    2  * Copyright 2011-2015 Samy Al Bahra.
    3  * Copyright 2011 David Joseph.
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice, this list of conditions and the following disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   25  * SUCH DAMAGE.
   26  */
   27 
   28 #include <ck_barrier.h>
   29 #include <ck_pr.h>
   30 
   31 #include "ck_internal.h"
   32 
   33 /*
   34  * This is a tournament barrier implementation. Threads are statically
   35  * assigned roles to perform for each round of the barrier. Winners
   36  * move on to the next round, while losers spin in their current rounds
   37  * on their own flags. During the last round, the champion of the tournament
   38  * sets the last flag that begins the wakeup process.
   39  */
   40 
   41 enum {
   42         CK_BARRIER_TOURNAMENT_BYE,
   43         CK_BARRIER_TOURNAMENT_CHAMPION,
   44         CK_BARRIER_TOURNAMENT_DROPOUT,
   45         CK_BARRIER_TOURNAMENT_LOSER,
   46         CK_BARRIER_TOURNAMENT_WINNER
   47 };
   48 
   49 void
   50 ck_barrier_tournament_subscribe(struct ck_barrier_tournament *barrier,
   51     struct ck_barrier_tournament_state *state)
   52 {
   53 
   54         state->sense = ~0;
   55         state->vpid = ck_pr_faa_uint(&barrier->tid, 1);
   56         return;
   57 }
   58 
   59 void
   60 ck_barrier_tournament_init(struct ck_barrier_tournament *barrier,
   61     struct ck_barrier_tournament_round **rounds,
   62     unsigned int nthr)
   63 {
   64         unsigned int i, k, size, twok, twokm1, imod2k;
   65 
   66         ck_pr_store_uint(&barrier->tid, 0);
   67         barrier->size = size = ck_barrier_tournament_size(nthr);
   68 
   69         for (i = 0; i < nthr; ++i) {
   70                 /* The first role is always CK_BARRIER_TOURNAMENT_DROPOUT. */
   71                 rounds[i][0].flag = 0;
   72                 rounds[i][0].role = CK_BARRIER_TOURNAMENT_DROPOUT;
   73                 for (k = 1, twok = 2, twokm1 = 1; k < size; ++k, twokm1 = twok, twok <<= 1) {
   74                         rounds[i][k].flag = 0;
   75 
   76                         imod2k = i & (twok - 1);
   77                         if (imod2k == 0) {
   78                                 if ((i + twokm1 < nthr) && (twok < nthr))
   79                                         rounds[i][k].role = CK_BARRIER_TOURNAMENT_WINNER;
   80                                 else if (i + twokm1 >= nthr)
   81                                         rounds[i][k].role = CK_BARRIER_TOURNAMENT_BYE;
   82                         }
   83 
   84                         if (imod2k == twokm1)
   85                                 rounds[i][k].role = CK_BARRIER_TOURNAMENT_LOSER;
   86                         else if ((i == 0) && (twok >= nthr))
   87                                 rounds[i][k].role = CK_BARRIER_TOURNAMENT_CHAMPION;
   88 
   89                         if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_LOSER)
   90                                 rounds[i][k].opponent = &rounds[i - twokm1][k].flag;
   91                         else if (rounds[i][k].role == CK_BARRIER_TOURNAMENT_WINNER ||
   92                                  rounds[i][k].role == CK_BARRIER_TOURNAMENT_CHAMPION)
   93                                 rounds[i][k].opponent = &rounds[i + twokm1][k].flag;
   94                 }
   95         }
   96 
   97         ck_pr_store_ptr(&barrier->rounds, rounds);
   98         return;
   99 }
  100 
  101 unsigned int
  102 ck_barrier_tournament_size(unsigned int nthr)
  103 {
  104 
  105         return (ck_internal_log(ck_internal_power_2(nthr)) + 1);
  106 }
  107 
  108 void
  109 ck_barrier_tournament(struct ck_barrier_tournament *barrier,
  110     struct ck_barrier_tournament_state *state)
  111 {
  112         struct ck_barrier_tournament_round **rounds = ck_pr_load_ptr(&barrier->rounds);
  113         int round = 1;
  114 
  115         if (barrier->size == 1)
  116                 return;
  117 
  118         for (;; ++round) {
  119                 switch (rounds[state->vpid][round].role) {
  120                 case CK_BARRIER_TOURNAMENT_BYE:
  121                         break;
  122                 case CK_BARRIER_TOURNAMENT_CHAMPION:
  123                         /*
  124                          * The CK_BARRIER_TOURNAMENT_CHAMPION waits until it wins the tournament; it then
  125                          * sets the final flag before the wakeup phase of the barrier.
  126                          */
  127                         while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
  128                                 ck_pr_stall();
  129 
  130                         ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
  131                         goto wakeup;
  132                 case CK_BARRIER_TOURNAMENT_DROPOUT:
  133                         /* NOTREACHED */
  134                         break;
  135                 case CK_BARRIER_TOURNAMENT_LOSER:
  136                         /*
  137                          * CK_BARRIER_TOURNAMENT_LOSERs set the flags of their opponents and wait until
  138                          * their opponents release them after the tournament is over.
  139                          */
  140                         ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
  141                         while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
  142                                 ck_pr_stall();
  143 
  144                         goto wakeup;
  145                 case CK_BARRIER_TOURNAMENT_WINNER:
  146                         /*
  147                          * CK_BARRIER_TOURNAMENT_WINNERs wait until their current opponent sets their flag; they then
  148                          * continue to the next round of the tournament.
  149                          */
  150                         while (ck_pr_load_uint(&rounds[state->vpid][round].flag) != state->sense)
  151                                 ck_pr_stall();
  152                         break;
  153                 }
  154         }
  155 
  156 wakeup:
  157         for (round -= 1 ;; --round) {
  158                 switch (rounds[state->vpid][round].role) {
  159                 case CK_BARRIER_TOURNAMENT_BYE:
  160                         break;
  161                 case CK_BARRIER_TOURNAMENT_CHAMPION:
  162                         /* NOTREACHED */
  163                         break;
  164                 case CK_BARRIER_TOURNAMENT_DROPOUT:
  165                         goto leave;
  166                         break;
  167                 case CK_BARRIER_TOURNAMENT_LOSER:
  168                         /* NOTREACHED */
  169                         break;
  170                 case CK_BARRIER_TOURNAMENT_WINNER:
  171                         /*
  172                          * Winners inform their old opponents the tournament is over
  173                          * by setting their flags.
  174                          */
  175                         ck_pr_store_uint(rounds[state->vpid][round].opponent, state->sense);
  176                         break;
  177                 }
  178         }
  179 
  180 leave:
  181         ck_pr_fence_memory();
  182         state->sense = ~state->sense;
  183         return;
  184 }

Cache object: 5c70b90b069f53d152928520b30b0713

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/contrib/ck/src/ck_barrier_tournament.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/src/ck_barrier_tournament.c