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