sys/contrib/ck/include/ck_barrier.h

   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 #ifndef CK_BARRIER_H
  29 #define CK_BARRIER_H
  30
  31 #include <ck_spinlock.h>
  32
  33 struct ck_barrier_centralized {
  34         unsigned int value;
  35         unsigned int sense;
  36 };
  37 typedef struct ck_barrier_centralized ck_barrier_centralized_t;
  38
  39 struct ck_barrier_centralized_state {
  40         unsigned int sense;
  41 };
  42 typedef struct ck_barrier_centralized_state ck_barrier_centralized_state_t;
  43
  44 #define CK_BARRIER_CENTRALIZED_INITIALIZER       {0, 0}
  45 #define CK_BARRIER_CENTRALIZED_STATE_INITIALIZER {0}
  46
  47 void ck_barrier_centralized(ck_barrier_centralized_t *,
  48     ck_barrier_centralized_state_t *, unsigned int);
  49
  50 struct ck_barrier_combining_group {
  51         unsigned int k;
  52         unsigned int count;
  53         unsigned int sense;
  54         struct ck_barrier_combining_group *parent;
  55         struct ck_barrier_combining_group *left;
  56         struct ck_barrier_combining_group *right;
  57         struct ck_barrier_combining_group *next;
  58 } CK_CC_CACHELINE;
  59 typedef struct ck_barrier_combining_group ck_barrier_combining_group_t;
  60
  61 struct ck_barrier_combining_state {
  62         unsigned int sense;
  63 };
  64 typedef struct ck_barrier_combining_state ck_barrier_combining_state_t;
  65
  66 #define CK_BARRIER_COMBINING_STATE_INITIALIZER {~0}
  67
  68 struct ck_barrier_combining {
  69         struct ck_barrier_combining_group *root;
  70         ck_spinlock_fas_t mutex;
  71 };
  72 typedef struct ck_barrier_combining ck_barrier_combining_t;
  73
  74 void ck_barrier_combining_init(ck_barrier_combining_t *, ck_barrier_combining_group_t *);
  75
  76 void ck_barrier_combining_group_init(ck_barrier_combining_t *,
  77     ck_barrier_combining_group_t *, unsigned int);
  78
  79 void ck_barrier_combining(ck_barrier_combining_t *,
  80     ck_barrier_combining_group_t *,
  81     ck_barrier_combining_state_t *);
  82
  83 struct ck_barrier_dissemination_flag {
  84         unsigned int tflag;
  85         unsigned int *pflag;
  86 };
  87 typedef struct ck_barrier_dissemination_flag ck_barrier_dissemination_flag_t;
  88
  89 struct ck_barrier_dissemination {
  90         unsigned int nthr;
  91         unsigned int size;
  92         unsigned int tid;
  93         struct ck_barrier_dissemination_flag *flags[2];
  94 };
  95 typedef struct ck_barrier_dissemination ck_barrier_dissemination_t;
  96
  97 struct ck_barrier_dissemination_state {
  98         int             parity;
  99         unsigned int    sense;
 100         unsigned int    tid;
 101 };
 102 typedef struct ck_barrier_dissemination_state ck_barrier_dissemination_state_t;
 103
 104 void ck_barrier_dissemination_init(ck_barrier_dissemination_t *,
 105     ck_barrier_dissemination_flag_t **, unsigned int);
 106
 107 void ck_barrier_dissemination_subscribe(ck_barrier_dissemination_t *,
 108     ck_barrier_dissemination_state_t *);
 109
 110 unsigned int ck_barrier_dissemination_size(unsigned int);
 111
 112 void ck_barrier_dissemination(ck_barrier_dissemination_t *,
 113     ck_barrier_dissemination_state_t *);
 114
 115 struct ck_barrier_tournament_round {
 116         int role;
 117         unsigned int *opponent;
 118         unsigned int flag;
 119 };
 120 typedef struct ck_barrier_tournament_round ck_barrier_tournament_round_t;
 121
 122 struct ck_barrier_tournament {
 123         unsigned int tid;
 124         unsigned int size;
 125         struct ck_barrier_tournament_round **rounds;
 126 };
 127 typedef struct ck_barrier_tournament ck_barrier_tournament_t;
 128
 129 struct ck_barrier_tournament_state {
 130         unsigned int sense;
 131         unsigned int vpid;
 132 };
 133 typedef struct ck_barrier_tournament_state ck_barrier_tournament_state_t;
 134
 135 void ck_barrier_tournament_subscribe(ck_barrier_tournament_t *,
 136                                      ck_barrier_tournament_state_t *);
 137 void ck_barrier_tournament_init(ck_barrier_tournament_t *,
 138                                 ck_barrier_tournament_round_t **,
 139                                 unsigned int);
 140 unsigned int ck_barrier_tournament_size(unsigned int);
 141 void ck_barrier_tournament(ck_barrier_tournament_t *, ck_barrier_tournament_state_t *);
 142
 143 struct ck_barrier_mcs {
 144         unsigned int tid;
 145         unsigned int *children[2];
 146         unsigned int childnotready[4];
 147         unsigned int dummy;
 148         unsigned int havechild[4];
 149         unsigned int *parent;
 150         unsigned int parentsense;
 151 };
 152 typedef struct ck_barrier_mcs ck_barrier_mcs_t;
 153
 154 struct ck_barrier_mcs_state {
 155         unsigned int sense;
 156         unsigned int vpid;
 157 };
 158 typedef struct ck_barrier_mcs_state ck_barrier_mcs_state_t;
 159
 160 void ck_barrier_mcs_init(ck_barrier_mcs_t *, unsigned int);
 161 void ck_barrier_mcs_subscribe(ck_barrier_mcs_t *, ck_barrier_mcs_state_t *);
 162 void ck_barrier_mcs(ck_barrier_mcs_t *, ck_barrier_mcs_state_t *);
 163
 164 #endif /* CK_BARRIER_H */