1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
2 /*
3 * Copyright (c) 2012-2016 Cisco Systems, Inc. All rights reserved.
4 * Copyright (c) 2012 Los Alamos National Security, LLC. All rights reserved
5 * Copyright (c) 2015-2019 Intel, Inc. All rights reserved.
6 * $COPYRIGHT$
7 *
8 * Additional copyrights may follow
9 *
10 * $HEADER$
11 */
12
13 /** @file
14 *
15 * This file provides a "hotel" class:
16 *
17 * - A hotel has a fixed number of rooms (i.e., storage slots)
18 * - An arbitrary data pointer can check into an empty room at any time
19 * - The occupant of a room can check out at any time
20 * - Optionally, the occupant of a room can be forcibly evicted at a
21 * given time (i.e., when an pmix timer event expires).
22 * - The hotel has finite occupancy; if you try to checkin a new
23 * occupant and the hotel is already full, it will gracefully fail
24 * to checkin.
25 *
26 * One use case for this class is for ACK-based network retransmission
27 * schemes (NACK-based retransmission schemes probably can use
28 * pmix_ring_buffer).
29 *
30 * For ACK-based retransmission schemes, a hotel might be used
31 * something like this:
32 *
33 * - when a message is sent, check it in to a hotel with a timer
34 * - if an ACK is received, check it out of the hotel (which also cancels
35 * the timer)
36 * - if an ACK isn't received in time, the timer will expire and the
37 * upper layer will get a callback with the message
38 * - if an ACK is received late (i.e., after its timer has expired),
39 * then checkout will gracefully fail
40 *
41 * Note that this class intentionally provides pretty minimal
42 * functionality. It is intended to be used in performance-critical
43 * code paths -- extra functionality would simply add latency.
44 *
45 * There is an pmix_hotel_init() function to create a hotel, but no
46 * corresponding finalize; the destructor will handle all finalization
47 * issues. Note that when a hotel is destroyed, it will delete all
48 * pending events from the event base (i.e., all pending eviction
49 * callbacks); no further eviction callbacks will be invoked.
50 */
51
52 #ifndef PMIX_HOTEL_H
53 #define PMIX_HOTEL_H
54
55 #include <src/include/pmix_config.h>
56 #include "src/include/types.h"
57 #include "src/include/prefetch.h"
58 #include "pmix_common.h"
59 #include "src/class/pmix_object.h"
60 #include PMIX_EVENT_HEADER
61
62 #include "src/util/output.h"
63
64 BEGIN_C_DECLS
65
66 struct pmix_hotel_t;
67
68 /* User-supplied function to be invoked when an occupant is evicted. */
69 typedef void (*pmix_hotel_eviction_callback_fn_t)(struct pmix_hotel_t *hotel,
70 int room_num,
71 void *occupant);
72
73 /* Note that this is an internal data structure; it is not part of the
74 public pmix_hotel interface. Public consumers of pmix_hotel
75 shouldn't need to use this struct at all (we only have it here in
76 this .h file because some functions are inlined for speed, and need
77 to get to the internals of this struct).
78
79 The room struct should be as small as possible to be cache
80 friendly. Specifically: it would be great if multiple rooms could
81 fit in a single cache line because we'll always allocate a
82 contiguous set of rooms in an array. */
83 typedef struct {
84 void *occupant;
85 pmix_event_t eviction_timer_event;
86 } pmix_hotel_room_t;
87
88 /* Note that this is an internal data structure; it is not part of the
89 public pmix_hotel interface. Public consumers of pmix_hotel
90 shouldn't need to use this struct at all (we only have it here in
91 this .h file because some functions are inlined for speed, and need
92 to get to the internals of this struct).
93
94 Use a unique struct for holding the arguments for eviction
95 callbacks. We *could* make the to-be-evicted pmix_hotel_room_t
96 instance as the argument, but we don't, for 2 reasons:
97
98 1. We want as many pmix_hotel_room_t's to fit in a cache line as
99 possible (i.e., to be as cache-friendly as possible). The
100 common/fast code path only needs to access the data in the
101 pmix_hotel_room_t (and not the callback argument data).
102
103 2. Evictions will be uncommon, so we don't mind penalizing them a
104 bit by making the data be in a separate cache line.
105 */
106 typedef struct {
107 struct pmix_hotel_t *hotel;
108 int room_num;
109 } pmix_hotel_room_eviction_callback_arg_t;
110
111 typedef struct pmix_hotel_t {
112 /* make this an object */
113 pmix_object_t super;
114
115 /* Max number of rooms in the hotel */
116 int num_rooms;
117
118 /* event base to be used for eviction timeout */
119 pmix_event_base_t *evbase;
120 struct timeval eviction_timeout;
121 pmix_hotel_eviction_callback_fn_t evict_callback_fn;
122
123 /* All rooms in this hotel */
124 pmix_hotel_room_t *rooms;
125
126 /* Separate array for all the eviction callback arguments (see
127 rationale above for why this is a separate array) */
128 pmix_hotel_room_eviction_callback_arg_t *eviction_args;
129
130 /* All currently unoccupied rooms in this hotel (not necessarily
131 in any particular order) */
132 int *unoccupied_rooms;
133 int last_unoccupied_room;
134 } pmix_hotel_t;
135 PMIX_CLASS_DECLARATION(pmix_hotel_t);
136
137 /**
138 * Initialize the hotel.
139 *
140 * @param hotel Pointer to a hotel (IN)
141 * @param num_rooms The total number of rooms in the hotel (IN)
142 * @param evbase Pointer to event base used for eviction timeout
143 * @param eviction_timeout Max length of a stay at the hotel before
144 * the eviction callback is invoked (in microseconds)
145 * @param evict_callback_fn Callback function invoked if an occupant
146 * does not check out before the eviction_timeout.
147 *
148 * NOTE: If the callback function is NULL, then no eviction timer
149 * will be set - occupants will remain checked into the hotel until
150 * explicitly checked out.
151 *
152 * Also note: the eviction_callback_fn should absolutely not call any
153 * of the hotel checkout functions. Specifically: the occupant has
154 * already been ("forcibly") checked out *before* the
155 * eviction_callback_fn is invoked.
156 *
157 * @return PMIX_SUCCESS if all initializations were succesful. Otherwise,
158 * the error indicate what went wrong in the function.
159 */
160 PMIX_EXPORT pmix_status_t pmix_hotel_init(pmix_hotel_t *hotel, int num_rooms,
161 pmix_event_base_t *evbase,
162 uint32_t eviction_timeout,
163 pmix_hotel_eviction_callback_fn_t evict_callback_fn);
164
165 /**
166 * Check in an occupant to the hotel.
167 *
168 * @param hotel Pointer to hotel (IN)
169 * @param occupant Occupant to check in (opaque to the hotel) (IN)
170 * @param room The room number that identifies this occupant in the
171 * hotel (OUT).
172 *
173 * If there is room in the hotel, the occupant is checked in and the
174 * timer for that occupant is started. The occupant's room is
175 * returned in the "room" param.
176 *
177 * Note that once a room's checkout_expire timer expires, the occupant
178 * is forcibly checked out, and then the eviction callback is invoked.
179 *
180 * @return PMIX_SUCCESS if the occupant is successfully checked in,
181 * and the room parameter will contain a valid value.
182 * @return PMIX_ERR_TEMP_OUT_OF_RESOURCE is the hotel is full. Try
183 * again later.
184 */
pmix_hotel_checkin(pmix_hotel_t * hotel,void * occupant,int * room_num)185 static inline pmix_status_t pmix_hotel_checkin(pmix_hotel_t *hotel,
186 void *occupant,
187 int *room_num)
188 {
189 pmix_hotel_room_t *room;
190
191 /* Do we have any rooms available? */
192 if (PMIX_UNLIKELY(hotel->last_unoccupied_room < 0)) {
193 *room_num = -1;
194 return PMIX_ERR_OUT_OF_RESOURCE;
195 }
196
197 /* Put this occupant into the first empty room that we have */
198 *room_num = hotel->unoccupied_rooms[hotel->last_unoccupied_room--];
199 room = &(hotel->rooms[*room_num]);
200 room->occupant = occupant;
201
202 /* Assign the event and make it pending */
203 if (NULL != hotel->evbase) {
204 pmix_event_add(&(room->eviction_timer_event),
205 &(hotel->eviction_timeout));
206 }
207
208 return PMIX_SUCCESS;
209 }
210
211 /**
212 * Same as pmix_hotel_checkin(), but slightly optimized for when the
213 * caller *knows* that there is a room available.
214 */
pmix_hotel_checkin_with_res(pmix_hotel_t * hotel,void * occupant,int * room_num)215 static inline void pmix_hotel_checkin_with_res(pmix_hotel_t *hotel,
216 void *occupant,
217 int *room_num)
218 {
219 pmix_hotel_room_t *room;
220
221 /* Put this occupant into the first empty room that we have */
222 *room_num = hotel->unoccupied_rooms[hotel->last_unoccupied_room--];
223 room = &(hotel->rooms[*room_num]);
224 assert(room->occupant == NULL);
225 room->occupant = occupant;
226
227 /* Assign the event and make it pending */
228 if (NULL != hotel->evbase) {
229 pmix_event_add(&(room->eviction_timer_event),
230 &(hotel->eviction_timeout));
231 }
232 }
233
234 /**
235 * Check the specified occupant out of the hotel.
236 *
237 * @param hotel Pointer to hotel (IN)
238 * @param room Room number to checkout (IN)
239 *
240 * If there is an occupant in the room, their timer is canceled and
241 * they are checked out.
242 *
243 * Nothing is returned (as a minor optimization).
244 */
pmix_hotel_checkout(pmix_hotel_t * hotel,int room_num)245 static inline void pmix_hotel_checkout(pmix_hotel_t *hotel, int room_num)
246 {
247 pmix_hotel_room_t *room;
248
249 /* Bozo check */
250 assert(room_num < hotel->num_rooms);
251 if (0 > room_num) {
252 /* occupant wasn't checked in */
253 return;
254 }
255
256 /* If there's an occupant in the room, check them out */
257 room = &(hotel->rooms[room_num]);
258 if (PMIX_LIKELY(NULL != room->occupant)) {
259 /* Do not change this logic without also changing the same
260 logic in pmix_hotel_checkout_and_return_occupant() and
261 pmix_hotel.c:local_eviction_callback(). */
262 room->occupant = NULL;
263 if (NULL != hotel->evbase) {
264 pmix_event_del(&(room->eviction_timer_event));
265 }
266 hotel->last_unoccupied_room++;
267 assert(hotel->last_unoccupied_room < hotel->num_rooms);
268 hotel->unoccupied_rooms[hotel->last_unoccupied_room] = room_num;
269 }
270
271 /* Don't bother returning whether we actually checked someone out
272 or not (because this is in the critical performance path) --
273 assume the upper layer knows what it's doing. */
274 }
275
276 /**
277 * Check the specified occupant out of the hotel and return the occupant.
278 *
279 * @param hotel Pointer to hotel (IN)
280 * @param room Room number to checkout (IN)
281 * @param void * occupant (OUT)
282 * If there is an occupant in the room, their timer is canceled and
283 * they are checked out.
284 *
285 * Use this checkout and when caller needs the occupant
286 */
pmix_hotel_checkout_and_return_occupant(pmix_hotel_t * hotel,int room_num,void ** occupant)287 static inline void pmix_hotel_checkout_and_return_occupant(pmix_hotel_t *hotel, int room_num, void **occupant)
288 {
289 pmix_hotel_room_t *room;
290
291 /* Bozo check */
292 assert(room_num < hotel->num_rooms);
293 if (0 > room_num) {
294 /* occupant wasn't checked in */
295 *occupant = NULL;
296 return;
297 }
298
299 /* If there's an occupant in the room, check them out */
300 room = &(hotel->rooms[room_num]);
301 if (PMIX_LIKELY(NULL != room->occupant)) {
302 pmix_output (10, "checking out occupant %p from room num %d", room->occupant, room_num);
303 /* Do not change this logic without also changing the same
304 logic in pmix_hotel_checkout() and
305 pmix_hotel.c:local_eviction_callback(). */
306 *occupant = room->occupant;
307 room->occupant = NULL;
308 if (NULL != hotel->evbase) {
309 event_del(&(room->eviction_timer_event));
310 }
311 hotel->last_unoccupied_room++;
312 assert(hotel->last_unoccupied_room < hotel->num_rooms);
313 hotel->unoccupied_rooms[hotel->last_unoccupied_room] = room_num;
314 }
315 else {
316 *occupant = NULL;
317 }
318 }
319
320 /**
321 * Returns true if the hotel is empty (no occupant)
322 * @param hotel Pointer to hotel (IN)
323 * @return bool true if empty false if there is a occupant(s)
324 *
325 */
pmix_hotel_is_empty(pmix_hotel_t * hotel)326 static inline bool pmix_hotel_is_empty (pmix_hotel_t *hotel)
327 {
328 if (hotel->last_unoccupied_room == hotel->num_rooms - 1)
329 return true;
330 else
331 return false;
332 }
333
334 /**
335 * Access the occupant of a room, but leave them checked into their room.
336 *
337 * @param hotel Pointer to hotel (IN)
338 * @param room Room number to checkout (IN)
339 * @param void * occupant (OUT)
340 *
341 * This accessor function is typically used to cycle across the occupants
342 * to check for someone already present that matches a description.
343 */
pmix_hotel_knock(pmix_hotel_t * hotel,int room_num,void ** occupant)344 static inline void pmix_hotel_knock(pmix_hotel_t *hotel, int room_num, void **occupant)
345 {
346 pmix_hotel_room_t *room;
347
348 /* Bozo check */
349 assert(room_num < hotel->num_rooms);
350
351 *occupant = NULL;
352 if (0 > room_num) {
353 /* occupant wasn't checked in */
354 return;
355 }
356
357 /* If there's an occupant in the room, have them come to the door */
358 room = &(hotel->rooms[room_num]);
359 if (PMIX_LIKELY(NULL != room->occupant)) {
360 pmix_output (10, "occupant %p in room num %d responded to knock", room->occupant, room_num);
361 *occupant = room->occupant;
362 }
363 }
364
365 END_C_DECLS
366
367 #endif /* PMIX_HOTEL_H */
368