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