David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 1 | /* |
| 2 | * |
Craig Tiller | a93a25f | 2016-01-28 13:55:49 -0800 | [diff] [blame] | 3 | * Copyright 2015-2016, Google Inc. |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 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 are |
| 8 | * met: |
| 9 | * |
| 10 | * * Redistributions of source code must retain the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer. |
| 12 | * * Redistributions in binary form must reproduce the above |
| 13 | * copyright notice, this list of conditions and the following disclaimer |
| 14 | * in the documentation and/or other materials provided with the |
| 15 | * distribution. |
| 16 | * * Neither the name of Google Inc. nor the names of its |
| 17 | * contributors may be used to endorse or promote products derived from |
| 18 | * this software without specific prior written permission. |
| 19 | * |
| 20 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 21 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 22 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 23 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 24 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 25 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 26 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 27 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 28 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 29 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 30 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 31 | * |
| 32 | */ |
| 33 | |
| 34 | #include "src/core/client_config/lb_policies/round_robin.h" |
| 35 | |
| 36 | #include <string.h> |
| 37 | |
| 38 | #include <grpc/support/alloc.h> |
| 39 | #include "src/core/transport/connectivity_state.h" |
| 40 | |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 41 | typedef struct round_robin_lb_policy round_robin_lb_policy; |
| 42 | |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 43 | int grpc_lb_round_robin_trace = 0; |
| 44 | |
| 45 | /** List of entities waiting for a pick. |
| 46 | * |
| 47 | * Once a pick is available, \a target is updated and \a on_complete called. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 48 | typedef struct pending_pick { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 49 | struct pending_pick *next; |
| 50 | grpc_pollset *pollset; |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 51 | grpc_connected_subchannel **target; |
Craig Tiller | 10ee274 | 2015-09-22 09:25:57 -0700 | [diff] [blame] | 52 | grpc_closure *on_complete; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 53 | } pending_pick; |
| 54 | |
| 55 | /** List of subchannels in a connectivity READY state */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 56 | typedef struct ready_list { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 57 | grpc_subchannel *subchannel; |
| 58 | struct ready_list *next; |
| 59 | struct ready_list *prev; |
| 60 | } ready_list; |
| 61 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 62 | typedef struct { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 63 | /** index within policy->subchannels */ |
| 64 | size_t index; |
| 65 | /** backpointer to owning policy */ |
| 66 | round_robin_lb_policy *policy; |
| 67 | /** subchannel itself */ |
| 68 | grpc_subchannel *subchannel; |
| 69 | /** notification that connectivity has changed on subchannel */ |
| 70 | grpc_closure connectivity_changed_closure; |
| 71 | /** this subchannels current position in subchannel->ready_list */ |
| 72 | ready_list *ready_list_node; |
| 73 | /** last observed connectivity */ |
| 74 | grpc_connectivity_state connectivity_state; |
| 75 | } subchannel_data; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 76 | |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 77 | struct round_robin_lb_policy { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 78 | /** base policy: must be first */ |
| 79 | grpc_lb_policy base; |
| 80 | |
| 81 | /** all our subchannels */ |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 82 | size_t num_subchannels; |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 83 | subchannel_data **subchannels; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 84 | |
| 85 | /** mutex protecting remaining members */ |
| 86 | gpr_mu mu; |
| 87 | /** have we started picking? */ |
| 88 | int started_picking; |
| 89 | /** are we shutting down? */ |
| 90 | int shutdown; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 91 | /** List of picks that are waiting on connectivity */ |
| 92 | pending_pick *pending_picks; |
| 93 | |
| 94 | /** our connectivity state tracker */ |
| 95 | grpc_connectivity_state_tracker state_tracker; |
| 96 | |
| 97 | /** (Dummy) root of the doubly linked list containing READY subchannels */ |
| 98 | ready_list ready_list; |
| 99 | /** Last pick from the ready list. */ |
| 100 | ready_list *ready_list_last_pick; |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 101 | }; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 102 | |
| 103 | /** Returns the next subchannel from the connected list or NULL if the list is |
| 104 | * empty. |
| 105 | * |
| 106 | * Note that this function does *not* advance p->ready_list_last_pick. Use \a |
| 107 | * advance_last_picked_locked() for that. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 108 | static ready_list *peek_next_connected_locked(const round_robin_lb_policy *p) { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 109 | ready_list *selected; |
| 110 | selected = p->ready_list_last_pick->next; |
| 111 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 112 | while (selected != NULL) { |
| 113 | if (selected == &p->ready_list) { |
| 114 | GPR_ASSERT(selected->subchannel == NULL); |
| 115 | /* skip dummy root */ |
| 116 | selected = selected->next; |
| 117 | } else { |
| 118 | GPR_ASSERT(selected->subchannel != NULL); |
| 119 | return selected; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 120 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 121 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 122 | return NULL; |
| 123 | } |
| 124 | |
| 125 | /** Advance the \a ready_list picking head. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 126 | static void advance_last_picked_locked(round_robin_lb_policy *p) { |
| 127 | if (p->ready_list_last_pick->next != NULL) { /* non-empty list */ |
| 128 | p->ready_list_last_pick = p->ready_list_last_pick->next; |
| 129 | if (p->ready_list_last_pick == &p->ready_list) { |
| 130 | /* skip dummy root */ |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 131 | p->ready_list_last_pick = p->ready_list_last_pick->next; |
| 132 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 133 | } else { /* should be an empty list */ |
| 134 | GPR_ASSERT(p->ready_list_last_pick == &p->ready_list); |
| 135 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 136 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 137 | if (grpc_lb_round_robin_trace) { |
| 138 | gpr_log(GPR_DEBUG, "[READYLIST] ADVANCED LAST PICK. NOW AT NODE %p (SC %p)", |
| 139 | p->ready_list_last_pick, p->ready_list_last_pick->subchannel); |
| 140 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 141 | } |
| 142 | |
| 143 | /** Prepends (relative to the root at p->ready_list) the connected subchannel \a |
| 144 | * csc to the list of ready subchannels. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 145 | static ready_list *add_connected_sc_locked(round_robin_lb_policy *p, |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 146 | grpc_subchannel *sc) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 147 | ready_list *new_elem = gpr_malloc(sizeof(ready_list)); |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 148 | new_elem->subchannel = sc; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 149 | if (p->ready_list.prev == NULL) { |
| 150 | /* first element */ |
| 151 | new_elem->next = &p->ready_list; |
| 152 | new_elem->prev = &p->ready_list; |
| 153 | p->ready_list.next = new_elem; |
| 154 | p->ready_list.prev = new_elem; |
| 155 | } else { |
| 156 | new_elem->next = &p->ready_list; |
| 157 | new_elem->prev = p->ready_list.prev; |
| 158 | p->ready_list.prev->next = new_elem; |
| 159 | p->ready_list.prev = new_elem; |
| 160 | } |
| 161 | if (grpc_lb_round_robin_trace) { |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 162 | gpr_log(GPR_DEBUG, "[READYLIST] ADDING NODE %p (SC %p)", new_elem, sc); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 163 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 164 | return new_elem; |
| 165 | } |
| 166 | |
| 167 | /** Removes \a node from the list of connected subchannels */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 168 | static void remove_disconnected_sc_locked(round_robin_lb_policy *p, |
| 169 | ready_list *node) { |
| 170 | if (node == NULL) { |
| 171 | return; |
| 172 | } |
| 173 | if (node == p->ready_list_last_pick) { |
| 174 | /* If removing the lastly picked node, reset the last pick pointer to the |
| 175 | * dummy root of the list */ |
| 176 | p->ready_list_last_pick = &p->ready_list; |
| 177 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 178 | |
| 179 | /* removing last item */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 180 | if (node->next == &p->ready_list && node->prev == &p->ready_list) { |
| 181 | GPR_ASSERT(p->ready_list.next == node); |
| 182 | GPR_ASSERT(p->ready_list.prev == node); |
| 183 | p->ready_list.next = NULL; |
| 184 | p->ready_list.prev = NULL; |
| 185 | } else { |
| 186 | node->prev->next = node->next; |
| 187 | node->next->prev = node->prev; |
| 188 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 189 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 190 | if (grpc_lb_round_robin_trace) { |
| 191 | gpr_log(GPR_DEBUG, "[READYLIST] REMOVED NODE %p (SC %p)", node, |
| 192 | node->subchannel); |
| 193 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 194 | |
| 195 | node->next = NULL; |
| 196 | node->prev = NULL; |
| 197 | node->subchannel = NULL; |
| 198 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 199 | gpr_free(node); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 200 | } |
| 201 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 202 | void rr_destroy(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol) { |
| 203 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 204 | size_t i; |
| 205 | ready_list *elem; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 206 | for (i = 0; i < p->num_subchannels; i++) { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 207 | subchannel_data *sd = p->subchannels[i]; |
| 208 | GRPC_SUBCHANNEL_UNREF(exec_ctx, sd->subchannel, "round_robin"); |
| 209 | gpr_free(sd); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 210 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 211 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 212 | grpc_connectivity_state_destroy(exec_ctx, &p->state_tracker); |
| 213 | gpr_free(p->subchannels); |
| 214 | gpr_mu_destroy(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 215 | |
| 216 | elem = p->ready_list.next; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 217 | while (elem != NULL && elem != &p->ready_list) { |
| 218 | ready_list *tmp; |
| 219 | tmp = elem->next; |
| 220 | elem->next = NULL; |
| 221 | elem->prev = NULL; |
| 222 | elem->subchannel = NULL; |
| 223 | gpr_free(elem); |
| 224 | elem = tmp; |
| 225 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 226 | gpr_free(p); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 227 | } |
| 228 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 229 | void rr_shutdown(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 230 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 231 | pending_pick *pp; |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 232 | size_t i; |
| 233 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 234 | gpr_mu_lock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 235 | |
| 236 | p->shutdown = 1; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 237 | while ((pp = p->pending_picks)) { |
| 238 | p->pending_picks = pp->next; |
| 239 | *pp->target = NULL; |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 240 | grpc_exec_ctx_enqueue(exec_ctx, pp->on_complete, false, NULL); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 241 | gpr_free(pp); |
| 242 | } |
| 243 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
| 244 | GRPC_CHANNEL_FATAL_FAILURE, "shutdown"); |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 245 | for (i = 0; i < p->num_subchannels; i++) { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 246 | subchannel_data *sd = p->subchannels[i]; |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 247 | grpc_subchannel_notify_on_state_change(exec_ctx, sd->subchannel, NULL, NULL, |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 248 | &sd->connectivity_changed_closure); |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 249 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 250 | gpr_mu_unlock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 251 | } |
| 252 | |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 253 | static void rr_cancel_pick(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol, |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 254 | grpc_connected_subchannel **target) { |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 255 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
| 256 | pending_pick *pp; |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 257 | gpr_mu_lock(&p->mu); |
| 258 | pp = p->pending_picks; |
| 259 | p->pending_picks = NULL; |
| 260 | while (pp != NULL) { |
| 261 | pending_pick *next = pp->next; |
| 262 | if (pp->target == target) { |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 263 | grpc_pollset_set_del_pollset(exec_ctx, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 264 | pp->pollset); |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 265 | *target = NULL; |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 266 | grpc_exec_ctx_enqueue(exec_ctx, pp->on_complete, false, NULL); |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 267 | gpr_free(pp); |
| 268 | } else { |
| 269 | pp->next = p->pending_picks; |
| 270 | p->pending_picks = pp; |
| 271 | } |
| 272 | pp = next; |
| 273 | } |
| 274 | gpr_mu_unlock(&p->mu); |
| 275 | } |
| 276 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 277 | static void start_picking(grpc_exec_ctx *exec_ctx, round_robin_lb_policy *p) { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 278 | size_t i; |
| 279 | p->started_picking = 1; |
| 280 | |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 281 | gpr_log(GPR_DEBUG, "LB_POLICY: p=%p num_subchannels=%d", p, |
| 282 | p->num_subchannels); |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 283 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 284 | for (i = 0; i < p->num_subchannels; i++) { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 285 | subchannel_data *sd = p->subchannels[i]; |
| 286 | sd->connectivity_state = GRPC_CHANNEL_IDLE; |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 287 | grpc_subchannel_notify_on_state_change( |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 288 | exec_ctx, sd->subchannel, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 289 | &sd->connectivity_state, &sd->connectivity_changed_closure); |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 290 | GRPC_LB_POLICY_WEAK_REF(&p->base, "round_robin_connectivity"); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 291 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 292 | } |
| 293 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 294 | void rr_exit_idle(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol) { |
| 295 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
| 296 | gpr_mu_lock(&p->mu); |
| 297 | if (!p->started_picking) { |
| 298 | start_picking(exec_ctx, p); |
| 299 | } |
| 300 | gpr_mu_unlock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 301 | } |
| 302 | |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 303 | int rr_pick(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol, grpc_pollset *pollset, |
Craig Tiller | ab33b48 | 2015-11-21 08:11:04 -0800 | [diff] [blame] | 304 | grpc_metadata_batch *initial_metadata, |
| 305 | grpc_connected_subchannel **target, grpc_closure *on_complete) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 306 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 307 | pending_pick *pp; |
| 308 | ready_list *selected; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 309 | gpr_mu_lock(&p->mu); |
| 310 | if ((selected = peek_next_connected_locked(p))) { |
| 311 | gpr_mu_unlock(&p->mu); |
Craig Tiller | b5585d4 | 2015-11-17 07:18:31 -0800 | [diff] [blame] | 312 | *target = grpc_subchannel_get_connected_subchannel(selected->subchannel); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 313 | if (grpc_lb_round_robin_trace) { |
Craig Tiller | ab33b48 | 2015-11-21 08:11:04 -0800 | [diff] [blame] | 314 | gpr_log(GPR_DEBUG, |
| 315 | "[RR PICK] TARGET <-- CONNECTED SUBCHANNEL %p (NODE %p)", |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 316 | selected->subchannel, selected); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 317 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 318 | /* only advance the last picked pointer if the selection was used */ |
| 319 | advance_last_picked_locked(p); |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 320 | return 1; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 321 | } else { |
| 322 | if (!p->started_picking) { |
| 323 | start_picking(exec_ctx, p); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 324 | } |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 325 | grpc_pollset_set_add_pollset(exec_ctx, p->base.interested_parties, pollset); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 326 | pp = gpr_malloc(sizeof(*pp)); |
| 327 | pp->next = p->pending_picks; |
| 328 | pp->pollset = pollset; |
| 329 | pp->target = target; |
| 330 | pp->on_complete = on_complete; |
| 331 | p->pending_picks = pp; |
| 332 | gpr_mu_unlock(&p->mu); |
Craig Tiller | 577c9b2 | 2015-11-02 14:11:15 -0800 | [diff] [blame] | 333 | return 0; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 334 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 335 | } |
| 336 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 337 | static void rr_connectivity_changed(grpc_exec_ctx *exec_ctx, void *arg, |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 338 | bool iomgr_success) { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 339 | subchannel_data *sd = arg; |
| 340 | round_robin_lb_policy *p = sd->policy; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 341 | pending_pick *pp; |
| 342 | ready_list *selected; |
| 343 | |
| 344 | int unref = 0; |
| 345 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 346 | gpr_mu_lock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 347 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 348 | if (p->shutdown) { |
| 349 | unref = 1; |
| 350 | } else { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 351 | switch (sd->connectivity_state) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 352 | case GRPC_CHANNEL_READY: |
| 353 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
| 354 | GRPC_CHANNEL_READY, "connecting_ready"); |
| 355 | /* add the newly connected subchannel to the list of connected ones. |
| 356 | * Note that it goes to the "end of the line". */ |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 357 | sd->ready_list_node = add_connected_sc_locked(p, sd->subchannel); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 358 | /* at this point we know there's at least one suitable subchannel. Go |
| 359 | * ahead and pick one and notify the pending suitors in |
| 360 | * p->pending_picks. This preemtively replicates rr_pick()'s actions. */ |
| 361 | selected = peek_next_connected_locked(p); |
| 362 | if (p->pending_picks != NULL) { |
| 363 | /* if the selected subchannel is going to be used for the pending |
| 364 | * picks, update the last picked pointer */ |
| 365 | advance_last_picked_locked(p); |
| 366 | } |
| 367 | while ((pp = p->pending_picks)) { |
| 368 | p->pending_picks = pp->next; |
Craig Tiller | ab33b48 | 2015-11-21 08:11:04 -0800 | [diff] [blame] | 369 | *pp->target = |
| 370 | grpc_subchannel_get_connected_subchannel(selected->subchannel); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 371 | if (grpc_lb_round_robin_trace) { |
| 372 | gpr_log(GPR_DEBUG, |
| 373 | "[RR CONN CHANGED] TARGET <-- SUBCHANNEL %p (NODE %p)", |
| 374 | selected->subchannel, selected); |
| 375 | } |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 376 | grpc_pollset_set_del_pollset(exec_ctx, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 377 | pp->pollset); |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 378 | grpc_exec_ctx_enqueue(exec_ctx, pp->on_complete, true, NULL); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 379 | gpr_free(pp); |
| 380 | } |
| 381 | grpc_subchannel_notify_on_state_change( |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 382 | exec_ctx, sd->subchannel, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 383 | &sd->connectivity_state, &sd->connectivity_changed_closure); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 384 | break; |
| 385 | case GRPC_CHANNEL_CONNECTING: |
| 386 | case GRPC_CHANNEL_IDLE: |
| 387 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 388 | sd->connectivity_state, |
| 389 | "connecting_changed"); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 390 | grpc_subchannel_notify_on_state_change( |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 391 | exec_ctx, sd->subchannel, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 392 | &sd->connectivity_state, &sd->connectivity_changed_closure); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 393 | break; |
| 394 | case GRPC_CHANNEL_TRANSIENT_FAILURE: |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 395 | /* renew state notification */ |
| 396 | grpc_subchannel_notify_on_state_change( |
Craig Tiller | 69b093b | 2016-02-25 19:04:07 -0800 | [diff] [blame] | 397 | exec_ctx, sd->subchannel, p->base.interested_parties, |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 398 | &sd->connectivity_state, &sd->connectivity_changed_closure); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 399 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 400 | /* remove from ready list if still present */ |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 401 | if (sd->ready_list_node != NULL) { |
| 402 | remove_disconnected_sc_locked(p, sd->ready_list_node); |
| 403 | sd->ready_list_node = NULL; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 404 | } |
| 405 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
| 406 | GRPC_CHANNEL_TRANSIENT_FAILURE, |
| 407 | "connecting_transient_failure"); |
| 408 | break; |
| 409 | case GRPC_CHANNEL_FATAL_FAILURE: |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 410 | if (sd->ready_list_node != NULL) { |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 411 | remove_disconnected_sc_locked(p, sd->ready_list_node); |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 412 | sd->ready_list_node = NULL; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 413 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 414 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 415 | p->num_subchannels--; |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 416 | GPR_SWAP(subchannel_data *, p->subchannels[sd->index], |
| 417 | p->subchannels[p->num_subchannels]); |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 418 | GRPC_SUBCHANNEL_UNREF(exec_ctx, sd->subchannel, "round_robin"); |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 419 | p->subchannels[sd->index]->index = sd->index; |
| 420 | gpr_free(sd); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 421 | |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 422 | unref = 1; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 423 | if (p->num_subchannels == 0) { |
| 424 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
| 425 | GRPC_CHANNEL_FATAL_FAILURE, |
| 426 | "no_more_channels"); |
| 427 | while ((pp = p->pending_picks)) { |
| 428 | p->pending_picks = pp->next; |
| 429 | *pp->target = NULL; |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 430 | grpc_exec_ctx_enqueue(exec_ctx, pp->on_complete, true, NULL); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 431 | gpr_free(pp); |
| 432 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 433 | } else { |
| 434 | grpc_connectivity_state_set(exec_ctx, &p->state_tracker, |
| 435 | GRPC_CHANNEL_TRANSIENT_FAILURE, |
| 436 | "subchannel_failed"); |
| 437 | } |
| 438 | } /* switch */ |
| 439 | } /* !unref */ |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 440 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 441 | gpr_mu_unlock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 442 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 443 | if (unref) { |
Craig Tiller | 2a1bb7f | 2015-11-29 21:54:26 -0800 | [diff] [blame] | 444 | GRPC_LB_POLICY_WEAK_UNREF(exec_ctx, &p->base, "round_robin_connectivity"); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 445 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 446 | } |
| 447 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 448 | static grpc_connectivity_state rr_check_connectivity(grpc_exec_ctx *exec_ctx, |
| 449 | grpc_lb_policy *pol) { |
| 450 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 451 | grpc_connectivity_state st; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 452 | gpr_mu_lock(&p->mu); |
| 453 | st = grpc_connectivity_state_check(&p->state_tracker); |
| 454 | gpr_mu_unlock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 455 | return st; |
| 456 | } |
| 457 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 458 | static void rr_notify_on_state_change(grpc_exec_ctx *exec_ctx, |
| 459 | grpc_lb_policy *pol, |
| 460 | grpc_connectivity_state *current, |
| 461 | grpc_closure *notify) { |
| 462 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
| 463 | gpr_mu_lock(&p->mu); |
| 464 | grpc_connectivity_state_notify_on_state_change(exec_ctx, &p->state_tracker, |
| 465 | current, notify); |
| 466 | gpr_mu_unlock(&p->mu); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 467 | } |
| 468 | |
Craig Tiller | 28bf891 | 2015-12-07 16:07:04 -0800 | [diff] [blame] | 469 | static void rr_ping_one(grpc_exec_ctx *exec_ctx, grpc_lb_policy *pol, |
| 470 | grpc_closure *closure) { |
| 471 | round_robin_lb_policy *p = (round_robin_lb_policy *)pol; |
| 472 | ready_list *selected; |
| 473 | grpc_connected_subchannel *target; |
| 474 | gpr_mu_lock(&p->mu); |
| 475 | if ((selected = peek_next_connected_locked(p))) { |
| 476 | gpr_mu_unlock(&p->mu); |
| 477 | target = grpc_subchannel_get_connected_subchannel(selected->subchannel); |
| 478 | grpc_connected_subchannel_ping(exec_ctx, target, closure); |
| 479 | } else { |
| 480 | gpr_mu_unlock(&p->mu); |
Craig Tiller | 6c39686 | 2016-01-28 13:53:40 -0800 | [diff] [blame] | 481 | grpc_exec_ctx_enqueue(exec_ctx, closure, false, NULL); |
Craig Tiller | 28bf891 | 2015-12-07 16:07:04 -0800 | [diff] [blame] | 482 | } |
| 483 | } |
| 484 | |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 485 | static const grpc_lb_policy_vtable round_robin_lb_policy_vtable = { |
Craig Tiller | f40df23 | 2016-03-25 13:38:14 -0700 | [diff] [blame] | 486 | rr_destroy, |
| 487 | rr_shutdown, |
| 488 | rr_pick, |
| 489 | rr_cancel_pick, |
| 490 | rr_ping_one, |
| 491 | rr_exit_idle, |
| 492 | rr_check_connectivity, |
| 493 | rr_notify_on_state_change}; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 494 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 495 | static void round_robin_factory_ref(grpc_lb_policy_factory *factory) {} |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 496 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 497 | static void round_robin_factory_unref(grpc_lb_policy_factory *factory) {} |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 498 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 499 | static grpc_lb_policy *create_round_robin(grpc_lb_policy_factory *factory, |
| 500 | grpc_lb_policy_args *args) { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 501 | size_t i; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 502 | round_robin_lb_policy *p = gpr_malloc(sizeof(*p)); |
| 503 | GPR_ASSERT(args->num_subchannels > 0); |
| 504 | memset(p, 0, sizeof(*p)); |
| 505 | grpc_lb_policy_init(&p->base, &round_robin_lb_policy_vtable); |
David Garcia Quintas | a4c43a6 | 2015-09-11 13:33:57 -0700 | [diff] [blame] | 506 | p->num_subchannels = args->num_subchannels; |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 507 | p->subchannels = gpr_malloc(sizeof(*p->subchannels) * p->num_subchannels); |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 508 | memset(p->subchannels, 0, sizeof(*p->subchannels) * p->num_subchannels); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 509 | grpc_connectivity_state_init(&p->state_tracker, GRPC_CHANNEL_IDLE, |
| 510 | "round_robin"); |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 511 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 512 | gpr_mu_init(&p->mu); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 513 | for (i = 0; i < args->num_subchannels; i++) { |
Craig Tiller | e2a6510 | 2015-11-30 17:51:49 -0800 | [diff] [blame] | 514 | subchannel_data *sd = gpr_malloc(sizeof(*sd)); |
| 515 | memset(sd, 0, sizeof(*sd)); |
| 516 | p->subchannels[i] = sd; |
| 517 | sd->policy = p; |
| 518 | sd->index = i; |
| 519 | sd->subchannel = args->subchannels[i]; |
Craig Tiller | 1d881fb | 2015-12-01 07:39:04 -0800 | [diff] [blame] | 520 | grpc_closure_init(&sd->connectivity_changed_closure, |
| 521 | rr_connectivity_changed, sd); |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 522 | } |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 523 | |
| 524 | /* The (dummy node) root of the ready list */ |
| 525 | p->ready_list.subchannel = NULL; |
| 526 | p->ready_list.prev = NULL; |
| 527 | p->ready_list.next = NULL; |
| 528 | p->ready_list_last_pick = &p->ready_list; |
| 529 | |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 530 | return &p->base; |
| 531 | } |
| 532 | |
| 533 | static const grpc_lb_policy_factory_vtable round_robin_factory_vtable = { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 534 | round_robin_factory_ref, round_robin_factory_unref, create_round_robin, |
| 535 | "round_robin"}; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 536 | |
| 537 | static grpc_lb_policy_factory round_robin_lb_policy_factory = { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 538 | &round_robin_factory_vtable}; |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 539 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 540 | grpc_lb_policy_factory *grpc_round_robin_lb_factory_create() { |
David Garcia Quintas | 4fb049b | 2015-09-03 17:26:06 -0700 | [diff] [blame] | 541 | return &round_robin_lb_policy_factory; |
| 542 | } |